Tree Node specification

Unless otherwise noted, all hashes use BLAKE2b-256 with the personalization field set to 'ZcashHistory' || CONSENSUS_BRANCH_ID. CONSENSUS_BRANCH_ID is the 4-byte little-endian encoding of the consensus branch ID for the epoch of the block containing the commitment. 8 Which is to say, each node in the tree commits to the consensus branch that produced it.

Each MMR node is defined as follows:

1. hashSubtreeCommitment

   Leaf node

   The consensus-defined block hash for the corresponding block.

   • This hash is encoded in internal byte order, and does NOT use the BLAKE2b-256 personalization string described above.
   • For clarity, in a given consensus branch, the hashSubtreeCommitment field of leaf \(n-1\) is precisely equal to the hashPrevBlock field in the header of the block at height \(x+n\) , where \(x\) is the network upgrade activation height of that consensus branch.

   Internal or root node

   • Both child nodes are serialized.
   • hashSubtreeCommitment is the BLAKE2b-256 hash of left_child || right_child.
   • For clarity, this digest uses the BLAKE2b-256 personalization string described above.

   Serialized as char[32].

2. nEarliestTimestamp

   Leaf node

   The header's timestamp.

   Internal or root node

   Inherited from the left child.

   Serialized as nTime (uint32).

   Note that a uint32 time value would overflow on 2106-02-07, but this field (and nLatestTimestamp below) can only hold values that occur in the nTime field of a block header, which is also of type uint32.

3. nLatestTimestamp

   Leaf node

   The header's timestamp.

   Internal or root node

   Inherited from the right child.

   Note that due to timestamp consensus rules, nLatestTimestamp may be smaller than nEarliestTimestamp in some subtrees. This may occur within subtrees smaller than PoWMedianBlockSpan blocks.

   Serialized as nTime (uint32).

4. nEarliestTargetBits

   Leaf node

   The header's nBits field.

   Internal or root node

   Inherited from the left child.

   Serialized as nBits (uint32).

5. nLatestTargetBits

   Leaf node

   The header's nBits field.

   Internal or root node

   Inherited from the right child.

   Serialized as nBits (uint32).

6. hashEarliestSaplingRoot

   Leaf node

   Calculated as hashFinalSaplingRoot, as implemented in Sapling.

   Internal or root node

   Inherited from the left child.

   Serialized as char[32].

7. hashLatestSaplingRoot

   Leaf node

   Calculated as hashFinalSaplingRoot, as implemented in Sapling.

   Internal or root node

   Inherited from the right child.

   Serialized as char[32].

8. nSubTreeTotalWork

   Leaf node

   The protocol-defined work of the block: \(\mathsf{floor}(2^{256} / (\mathsf{ToTarget}(\mathsf{nBits}) + 1))\) . 4

   Internal or root node

   The sum of the nSubTreeTotalWork fields of both children.

   Computations modulo \(2^{256}\) are fine here; cumulative chain work is similarly assumed elsewhere in the Zcash ecosystem to be at most \(2^{256}\) (as inherited from Bitcoin). The computed work factors are, on average, equal to the computational efforts involved in the creation of the corresponding blocks, and an aggregate effort of \(2^{256}\) or more is infeasible in practice.

   Serialized as uint256.

9. nEarliestHeight

   Leaf node

   The height of the block.

   Internal or root node

   Inherited from the left child.

   Serialized as CompactSize uint.

10. nLatestHeight

    Leaf node

    The height of the block.

    Internal or root node

    Inherited from the right child.

    Serialized as CompactSize uint.

11. nSaplingTxCount

    Leaf node

    The number of transactions in the leaf block where either of vSpendsSapling or vOutputsSapling is non-empty.

    Internal or root node

    The sum of the nSaplingTxCount field of both children.

    Serialized as CompactSize uint.

12. [NU5 onward] hashEarliestOrchardRoot

    Leaf node

    Calculated as the note commitment root of the final Orchard treestate (similar to hashEarliestSaplingRoot in Sapling).

    Internal or root node

    Inherited from the left child.

    Serialized as char[32].

13. [NU5 onward] hashLatestOrchardRoot

    Leaf node

    Calculated as the note commitment root of the final Orchard treestate (similar to hashLatestSaplingRoot in Sapling).

    Internal or root node

    Inherited from the right child.

    Serialized as char[32].

14. [NU5 onward] nOrchardTxCount

    Leaf node

    The number of transactions in the leaf block where vActionsOrchard is non-empty.

    Internal or root node

    The sum of the nOrchardTxCount field of both children.

    Serialized as CompactSize uint.

The fields marked "[NU5 onward]" are omitted before NU5 activation 11.

Each node, when serialized, is between 147 and 171 bytes long (between 212 and 244 bytes after NU5 activation). The canonical serialized representation of a node is used whenever creating child commitments for future nodes. Other than the metadata commitments, the MMR tree's construction is standard.

Once the MMR has been generated, we produce hashChainHistoryRoot, which we define as the BLAKE2b-256 digest of the serialization of the root node.

Tree nodes and hashing (pseudocode)

def H(msg: bytes, consensusBranchId: bytes) -> bytes:
    return blake2b256(msg, personalization=b'ZcashHistory' + consensusBranchId)

class ZcashMMRNode():
    # leaf nodes have no children
    left_child: Optional[ZcashMMRNode]
    right_child: Optional[ZcashMMRNode]

    # commitments
    hashSubtreeCommitment: bytes
    nEarliestTimestamp: int
    nLatestTimestamp: int
    nEarliestTargetBits: int
    nLatestTargetBits: int
    hashEarliestSaplingRoot: bytes # left child's Sapling root
    hashLatestSaplingRoot: bytes # right child's Sapling root
    nSubTreeTotalWork: int  # total difficulty accumulated within each subtree
    nEarliestHeight: int
    nLatestHeight: int
    nSaplingTxCount: int # number of Sapling transactions in block
    # NU5 only.
    hashEarliestOrchardRoot: Optional[bytes] # left child's Orchard root
    hashLatestOrchardRoot: Optional[bytes] # right child's Orchard root
    nSaplingTxCount: Optional[int] # number of Orchard transactions in block

    consensusBranchId: bytes

    @classmethod
    def from_block(Z, block: ZcashBlock) -> ZcashMMRNode:
        '''Create a leaf node from a block'''
        return Z(
            left_child=None,
            right_child=None,
            hashSubtreeCommitment=block.header_hash,
            nEarliestTimestamp=block.timestamp,
            nLatestTimestamp=block.timestamp,
            nEarliestTargetBits=block.nBits,
            nLatestTargetBits=block.nBits,
            hashEarliestSaplingRoot=block.sapling_root,
            hashLatestSaplingRoot=block.sapling_root,
            nSubTreeTotalWork=calculate_work(block.nBits),
            nEarliestHeight=block.height,
            nLatestHeight=block.height,
            nSaplingTxCount=block.sapling_tx_count,
            hashEarliestOrchardRoot=block.orchard_root,
            hashLatestOrchardRoot=block.orchard_root,
            nOrchardTxCount=block.orchard_tx_count,
            consensusBranchId=block.consensusBranchId)

    def serialize(self) -> bytes:
        '''serializes a node'''
        buf = (self.hashSubtreeCommitment
            + serialize_uint32(self.nEarliestTimestamp)
            + serialize_uint32(self.nLatestTimestamp)
            + serialize_uint32(self.nEarliestTargetBits)
            + serialize_uint32(self.nLatestTargetBits)
            + hashEarliestSaplingRoot
            + hashLatestSaplingRoot
            + serialize_uint256(self.nSubTreeTotalWork)
            + serialize_compact_uint(self.nEarliestHeight)
            + serialize_compact_uint(self.nLatestHeight)
            + serialize_compact_uint(self.nSaplingTxCount))
        if hashEarliestOrchardRoot is not None:
            buf += (hashEarliestOrchardRoot
                + hashLatestOrchardRoot
                + serialize_compact_uint(self.nOrchardTxCount))
        return buf


def make_parent(
        left_child: ZcashMMRNode,
        right_child: ZcashMMRNode) -> ZcashMMRNode:
    return ZcashMMRNode(
        left_child=left_child,
        right_child=right_child,
        hashSubtreeCommitment=H(left_child.serialize() + right_child.serialize(),
                                left_child.consensusBranchId),
        nEarliestTimestamp=left_child.nEarliestTimestamp,
        nLatestTimestamp=right_child.nLatestTimestamp,
        nEarliestTargetBits=left_child.nEarliestTargetBits,
        nLatestTargetBits=right_child.nLatestTargetBits,
        hashEarliestSaplingRoot=left_child.sapling_root,
        hashLatestSaplingRoot=right_child.sapling_root,
        nSubTreeTotalWork=left_child.nSubTreeTotalWork + right_child.nSubTreeTotalWork,
        nEarliestHeight=left_child.nEarliestHeight,
        nLatestHeight=right_child.nLatestHeight,
        nSaplingTxCount=left_child.nSaplingTxCount + right_child.nSaplingTxCount,
        hashEarliestOrchardRoot=left_child.orchard_root,
        hashLatestOrchardRoot=right_child.orchard_root,
        nOrchardTxCount=(left_child.nOrchardTxCount + right_child.nOrchardTxCount
                         if left_child.nOrchardTxCount is not None and right_child.nOrchardTxCount is not None
                         else None),
        consensusBranchId=left_child.consensusBranchId)

def make_root_commitment(root: ZcashMMRNode) -> bytes:
    '''Makes the root commitment for a blockheader'''
    return H(root.serialize(), root.consensusBranchId)

Incremental push and pop (pseudocode)

With each new block \(B_n\) , we append a new MMR leaf node corresponding to block \(B_{n-1}\) . The append operation is detailed below in pseudocode (adapted from 2):

def get_peaks(node: ZcashMMRNode) -> List[ZcashMMRNode]:
    peaks: List[ZcashMMRNode] = []

    # Get number of leaves.
    leaves = latest_height - (earliest_height - 1)
    assert(leaves > 0)

    # Check if the number of leaves is a power of two.
    if (leaves & (leaves - 1)) == 0:
        # Tree is full, hence a single peak. This also covers the
        # case of a single isolated leaf.
        peaks.append(node)
    else:
        # If the number of leaves is not a power of two, then this
        # node must be internal, and cannot be a peak.
        peaks.extend(get_peaks(left_child))
        peaks.extend(get_peaks(right_child))

    return peaks


def bag_peaks(peaks: List[ZcashMMRNode]) -> ZcashMMRNode:
    '''
    "Bag" a list of peaks, and return the final root
    '''
    root = peaks[0]
    for i in range(1, len(peaks)):
        root = make_parent(root, peaks[i])
    return root


def append(root: ZcashMMRNode, leaf: ZcashMMRNode) -> ZcashMMRNode:
    '''Append a leaf to an existing tree, return the new tree root'''
    # recursively find a list of peaks in the current tree
    peaks: List[ZcashMMRNode] = get_peaks(root)
    merged: List[ZcashMMRNode] = []

    # Merge peaks from right to left.
    # This will produce a list of peaks in reverse order
    current = leaf
    for peak in peaks[::-1]:
        current_leaves = current.latest_height - (current.earliest_height - 1)
        peak_leaves = peak.latest_height - (peak.earliest_height - 1)

        if current_leaves == peak_leaves:
            current = make_parent(peak, current)
        else:
            merged.append(current)
            current = peak
    merged.append(current)

    # finally, bag the merged peaks
    return bag_peaks(merged[::-1])

In case of a block reorg, we have to delete the latest (i.e. rightmost) MMR leaf nodes, up to the reorg length. This operation is \(O(\log(k))\) where \(k\) is the number of leaves in the right subtree of the MMR root.

def delete(root: ZcashMMRNode) -> ZcashMMRNode:
    '''
    Delete the rightmost leaf node from an existing MMR
    Return the new tree root
    '''

    n_leaves = root.latest_height - (root.earliest_height - 1)
    # if there were an odd number of leaves,
    # simply replace root with left_child
    if n_leaves & 1:
        return root.left_child

    # otherwise, we need to re-bag the peaks.
    else:
        # first peak
        peaks = [root.left_child]

        # we do this traversing the right (unbalanced) side of the tree
        # we keep the left side (balanced subtree or leaf) of each subtree
        # until we reach a leaf
        subtree_root = root.right_child
        while subtree_root.left_child:
            peaks.push(subtree_root.left_child)
            subtree_root = subtree_root.right_child

    new_root = bag_peaks(peaks)
    return new_root

Block header semantics and consensus rules

The following specification is accurate before NU5 activation. See 9 for header field changes in NU5.

The hashFinalSaplingRoot block header field (which was named hashReserved prior to the Sapling network upgrade) is renamed to hashLightClientRoot, to reflect its usage by light clients. (In NU5, this field is renamed again to hashBlockCommitments as specified in 9.)

Prior to activation of the network upgrade that deploys this ZIP, this existing consensus rule on block headers (adjusted for the renamed field) is enforced: 3

[Sapling onward] hashLightClientRoot MUST be \(\mathsf{LEBS2OSP}_{256}(\mathsf{rt})\) where \(\mathsf{rt}\) is the root of the Sapling note commitment tree for the final Sapling tree state of this block.

In the block that activates this ZIP, hashLightClientRoot MUST be set to all zero bytes. This MUST NOT be interpreted as a root hash.

In subsequent blocks, hashLightClientRoot MUST be set to the value of hashChainHistoryRoot as specified above.

The block header byte format and version are not altered by this ZIP.

Tree nodes

Nodes in the commitment tree are canonical and immutable. They are cheap to generate, as (with the exception of nSaplingTxCount and nOrchardTxCount) all metadata is already generated during block construction and/or checked during block validation. Nodes are relatively compact in memory. As of the original publication of this ZIP, approximately 140,000 blocks had elapsed since Sapling activation. Assuming a 164-byte commitment to each of these, we would have generated approximately 24 MB of additional storage cost for the set of leaf nodes (and an additional ~24 MB for storage of intermediate nodes).

hashSubtreeCommitment forms the structure of the commitment tree. Other metadata commitments were chosen to serve specific purposes. Originally variable-length commitments were placed last, so that most metadata in a node could be directly indexed. We considered using fixed-length commitments here, but opted for variable-length, in order to marginally reduce the memory requirements for managing and updating the commitment trees.

Orchard fields are placed last, in order to avoid complicating existing uses of the other fields.

In leaf nodes, some information is repeated. We chose to do this so that leaf nodes could be treated identically to internal and root nodes for all algorithms and (de)serializers. Leaf nodes are easily identifiable, as they will show proof of work in the hashSubtreeCommitment field (which commits to the block hash for leaf nodes), and their block range (calculated as nLatestHeight - (nEarliestHeight - 1)) will be precisely 1.

Personalized BLAKE2b-256 was selected to match existing Zcash conventions. Adding the consensus branch ID to the hash personalization string ensures that valid nodes from one consensus branch cannot be used to make false statements about parallel consensus branches.

Header Format Change

The primary goal of the original authors was to minimize header changes; in particular, they preferred not to introduce changes that could affect mining hardware or embedded software. Altering the block header format would require changes throughout the ecosystem, so we decided against adding hashChainHistoryRoot to the header as a new field.

ZIP 301 states that "[Miner client software] SHOULD alert the user upon receiving jobs containing block header versions they do not know about or support, and MUST ignore such jobs." 12 As the only formally defined block header version is 4, any header version change requires changes to miner client software in order for miners to handle new jobs from mining pools. We therefore do not alter the block version for this semantic change. This does not make block headers ambiguous to interpret, because blocks commit to their block height inside their coinbase transaction, 7 and they are never handled in a standalone context (unlike transactions, which exist in the mempool outside of blocks).

Replacing hashFinalSaplingRoot with hashChainHistoryRoot does introduce the theoretical possibility of an attack where a miner constructs a Sapling commitment tree update that results in the same 32-byte value as the MMR root. We don't consider this a realistic attack, both because the adversary would need to find a preimage over 32 layers of Pedersen hash, and because light clients already need to update their code to include the consensus branch ID for the Heartwood network upgrade, and can simultaneously make changes to not rely on the value of this header field being the Sapling tree root.

We also considered putting hashChainHistoryRoot in the hashPrevBlock field as it commits to the entire chain history, but quickly realized it would require massive refactoring of the existing code base and would negatively impact performance. Reorgs in particular are fragile, performance-critical, and rely on backwards iteration over the chain history. If a chain were to be designed from scratch there may be some efficient implementation that would join these commitments, but it is clearly not appropriate for Zcash as it exists.

The calculation of hashChainHistoryRoot is not well-defined for the genesis block, since then \(n = 0\) and there is no block \(B_{n-1}\) . Also, in the case of chains that activate this ZIP after genesis (including Zcash Mainnet and Testnet), the hashChainHistoryRoot of the activation block would commit to the whole previous epoch if a special case were not made. It would be impractical to calculate this commitment all at once, and so we specify that hashLightClientRoot is set to all zero bytes for that block instead. The hash of the final Sapling note commitment tree root for the activation block will not be encoded in that block, but will be committed to one block later in the hashLatestSaplingRoot field of the MMR root commitment.