This page is the Simplified Technical English version of ZIP 221. The source ZIP is the normative text. Read the writing rules to understand the marked words.
ZIP 221: FlyClient - Consensus-Layer Changes
ZIP: 221
Title: FlyClient - Consensus-Layer Changes
Owners: Jack Grigg <thestr4d@gmail.com>
Original-Authors: Ying Tong Lai
James Prestwich
Georgios Konstantopoulos
Status: Final
Category: Consensus
Created: 2019-03-30
License: MIT
Terminology
On this page, STE words are in the place of the BCP 14 key words of the source. Refer to the key word table.
These terms have the meanings that are in ZIP 200 [zip-0200]:
- consensus branch
- epoch
- network upgrade
- Light client
- A client that is not a full participant in the network of Zcash peers. A light client can send and receive payments. But it does not store a copy of the block chain, and it does not validate a copy of the block chain.
- High probability
- An event occurs with high probability if it occurs with probability \(1-O(1/2^\lambda)\). In this expression, \(\lambda\) is a security parameter.
- Negligible probability
- An event occurs with negligible probability if it occurs with probability \(O(1/2^\lambda)\). In this expression, \(\lambda\) is the security parameter.
- Merkle mountain range (MMR)
- A Merkle mountain range (MMR) is a binary hash tree. It is efficient to append new leaves to an MMR. When new leaves are appended, the values of the existing nodes stay the same.
Abstract
This ZIP contains changes to the semantics of the Zcash block header and to the consensus rules. The purpose of these changes is to support the FlyClient protocol [FlyClient]. FlyClient is a protocol for probabilistic verification.
In the block header, the hashFinalSaplingRoot commitment is replaced with a commitment to the root of a Merkle Mountain Range (MMR). This MMR commits to different features of the history of the chain. One of these features is the Sapling commitment tree.
Background
An MMR is a Merkle tree. With an MMR, these operations are efficient:
- appends
- proofs
- verifications.
Informally, an append of data to an MMR has two parts. First, a new leaf is created. Then, in a loop, neighboring subtrees that have the same size are merged. An append has a maximum of \(\log(n)\) operations. For an append, it is necessary to know only the previous subtree roots. There are fewer than \(\log(n)\) of these roots.
(This example is adapted from [mimblewimble].) As an example, use a list of 11 leaves. First, we construct the largest possible perfect binary subtrees. To do this, we join all balanced sibling trees that have the same size.
We start at the left and go to the right. We add a parent immediately when 2 children exist. The result is three subtrees ("mountains"). The altitudes of these subtrees are 3, 1 and 0:
/\ / \ /\ /\ /\/\/\/\ /\ /
Note: The first peak on the left is always the highest peak.
We can give numbers to the nodes of this structure in the sequence of their creation, if the leaves are inserted from left to right:
Altitude
3 14
/ \
/ \
/ \
/ \
2 6 13
/ \ / \
1 2 5 9 12 17
/ \ / \ / \ / \ / \ /
0 0 1 3 4 7 8 10 11 15 16 18
We can also show these numbers in a flat list:
| Position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Altitude | 0 | 0 | 1 | 0 | 0 | 1 | 2 | 0 | 0 | 1 | 0 | 0 | 1 | 2 | 3 | 0 | 0 | 1 | 0 |
Let \(h\) be the altitude of a node. If the node has a right sibling, we can easily go to it: add \(2^{h+1} - 1\) to the position of the node. If the node has a left child, we can easily go to it: subtract \(2^h\) from the position of the node.
Thus we can efficiently find the subtree roots ("peaks") of the mountains.
When we have the positions of the mountain peaks, we "bag" the peaks with this algorithm:
- Make a node that connects the 2 leftmost peaks, to make a new peak.
- Do step 1 again until there is only one peak.
Note: The rules above for movement from node to node do not apply to the extra nodes that are made during the bagging process.
Altitude
5 20g
/ \
4 19g \
/ \ \
/ \ \
/ \ \
3 14 \ \
/ \ \ \
/ \ \ \
/ \ \ \
/ \ \ \
2 6 13 \ \
/ \ / \ \ \
1 2 5 9 12 17 \
/ \ / \ / \ / \ / \ \
0 0 1 3 4 7 8 10 11 15 16 18
With MMR trees, incremental set update operations are efficient. These operations are:
- push
- pop
- prune.
Also, MMR update operations and Merkle proofs for recent additions to the leaf set are more efficient than in other incremental Merkle tree implementations. Examples of these other implementations are:
- the padded leafset of Bitcoin
- sparse Merkle trees
- the incremental note commitment trees of Zcash.
Motivation
MMR proofs are used in the FlyClient protocol [FlyClient]. Their purpose is to decrease the proof size that is necessary for light clients to verify these items:
- the validity of a block chain that a light client receives from a full node
- the inclusion of a block \(B\) in that chain
- specified metadata of any block or of any range of blocks in that chain.
The protocol has this requirement: for each block \(B_n\), an MMR must be formed that commits to the inclusion of all blocks since the preceding network upgrade \((B_x, \ldots, B_{n-1})\). The root \(M_n\) of the MMR must be included in the header of \(B_n\).
(\(\!x\) is the activation height of the preceding network upgrade.)
With FlyClient, fewer block headers are necessary when a light client verifies a valid chain. The number of headers changes from linear to logarithmic in the length of the block chain. (In the current reference protocol, the number is linear.) This verification is correct with high probability.
With FlyClient, subtree proofs can also be created. Thus it is only necessary for light clients to check the blocks that are later than the most recently verified block index. After that, the verification of the inclusion of a transaction in that block is as in the usual reference protocol [zip-0307].
With a smaller proof size, it can be possible to verify Zcash SPV Proofs in block chain protocols such as Ethereum. Then efficient cross-chain communication and pegs can be possible. Also, with a smaller proof size, clients with limited resources have smaller bandwidth and storage requirements. Examples of these clients are mobile devices and IoT devices.
Specification
Let \(B_n\) be a block at height \(n > 0\) in a block chain. The "preceding network upgrade height" \(x\) of \(B_n\) is the last network upgrade activation height in the chain that is less than \(n\). (For this definition, block height \(0\) is the height of a network upgrade activation. The preceding network upgrade height of the genesis block is not defined.)
The leaves of the MMR at block \(B_n\) are hash commitments to the header data and metadata of each previous block \(B_x, \ldots, B_{n-1}\). The value \(x\) has the definition above.
We extend the standard MMR so that metadata can move upwards through the tree. For this, as necessary, the metadata of the two children is added together, or the metadata of one specified child is inherited. Thus we can create efficient proofs of selected properties of a range of blocks. For these proofs, it is not necessary to send the full range of blocks or headers.
Tree Node specification
Unless an exception is noted, all hashes are BLAKE2b-256 hashes 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 that contains the commitment [zip-0200]. That is, each node in the tree commits to the consensus branch that produced it.
Each MMR node has these fields:
hashSubtreeCommitment- Leaf node
- The consensus-defined block hash of the corresponding block.
- This hash is encoded in internal byte order. The BLAKE2b-256 personalization string above does not apply to this hash.
- For clarity: in a given consensus branch,
hashSubtreeCommitmentof leaf \(n-1\) is exactly equal tohashPrevBlockin the header of the block at height \(x+n\). Here, \(x\) is the network upgrade activation height of that consensus branch.
- Internal or root node
- Both child nodes are serialized.
hashSubtreeCommitmentis the BLAKE2b-256 hash ofleft_child || right_child.- For clarity: the BLAKE2b-256 personalization string above applies to this digest.
This field is serialized as
char[32].nEarliestTimestamp- Leaf node
- The timestamp of the header.
- Internal or root node
- The value is inherited from the left child.
This field is serialized as
nTime(uint32).Note: A
uint32time value overflows on 2106-02-07. But this field can hold only values that occur in thenTimefield of a block header. (This also applies tonLatestTimestampbelow.) The type of thenTimefield is alsouint32.nLatestTimestamp- Leaf node
- The timestamp of the header.
- Internal or root node
- The value is inherited from the right child.
Note: Because of the timestamp consensus rules,
nLatestTimestampcan be smaller thannEarliestTimestampin some subtrees. This can occur in subtrees that are smaller thanPoWMedianBlockSpanblocks.This field is serialized as
nTime(uint32).nEarliestTargetBits- Leaf node
- The
nBitsfield of the header. - Internal or root node
- The value is inherited from the left child.
This field is serialized as
nBits(uint32).nLatestTargetBits- Leaf node
- The
nBitsfield of the header. - Internal or root node
- The value is inherited from the right child.
This field is serialized as
nBits(uint32).hashEarliestSaplingRoot- Leaf node
- The value is calculated as
hashFinalSaplingRoot, as implemented in Sapling. - Internal or root node
- The value is inherited from the left child.
This field is serialized as
char[32].hashLatestSaplingRoot- Leaf node
- The value is calculated as
hashFinalSaplingRoot, as implemented in Sapling. - Internal or root node
- The value is inherited from the right child.
This field is serialized as
char[32].nSubTreeTotalWork- Leaf node
- The protocol-defined work of the block: \(\mathsf{floor}(2^{256} / (\mathsf{ToTarget}(\mathsf{nBits}) + 1))\) [protocol-workdef].
- Internal or root node
- The sum of the
nSubTreeTotalWorkfields of the two children.Here, calculations modulo \(2^{256}\) are acceptable. In other parts of the Zcash ecosystem, there is a similar assumption that the cumulative chain work is a maximum of \(2^{256}\). (This assumption comes from Bitcoin.) On average, the calculated work factors are equal to the computational effort that was necessary to create the corresponding blocks. An aggregate effort of \(2^{256}\) or more is not possible in practice.
This field is serialized as
uint256.nEarliestHeight- Leaf node
- The block height.
- Internal or root node
- The value is inherited from the left child.
This field is serialized as
CompactSize uint.nLatestHeight- Leaf node
- The block height.
- Internal or root node
- The value is inherited from the right child.
This field is serialized as
CompactSize uint.nSaplingTxCount- Leaf node
- The number of transactions in the leaf block where at least one of
vSpendsSaplingandvOutputsSaplingis not empty. - Internal or root node
- The sum of the
nSaplingTxCountfields of the two children.
This field is serialized as
CompactSize uint.[NU5 onward]
hashEarliestOrchardRoot- Leaf node
- The value is calculated as the note commitment root of the final Orchard treestate. (This is similar to
hashEarliestSaplingRootin Sapling.) - Internal or root node
- The value is inherited from the left child.
This field is serialized as
char[32].[NU5 onward]
hashLatestOrchardRoot- Leaf node
- The value is calculated as the note commitment root of the final Orchard treestate. (This is similar to
hashLatestSaplingRootin Sapling.) - Internal or root node
- The value is inherited from the right child.
This field is serialized as
char[32].[NU5 onward]
nOrchardTxCount- Leaf node
- The number of transactions in the leaf block where
vActionsOrchardis not empty. - Internal or root node
- The sum of the
nOrchardTxCountfields of the two children.
This field is serialized as
CompactSize uint.
Before NU5 activation, the fields with the mark "[NU5 onward]" are not included [zip-0252].
The length of a serialized node is between 147 and 171 bytes. (After NU5 activation, the length is between 212 and 244 bytes.) The canonical serialized representation of a node is used each time that child commitments are created for future nodes. Except for the metadata commitments, the construction of the MMR tree is standard.
After the MMR is generated, we produce hashChainHistoryRoot. We define hashChainHistoryRoot 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)
For each new block \(B_n\), we append a new MMR leaf node that corresponds to block \(B_{n-1}\). The append operation is in the pseudocode below. (This pseudocode is adapted from [FlyClient].)
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])
If a block reorg occurs, we must delete the latest MMR leaf nodes (that is, the rightmost leaf nodes). The number of deleted nodes is a maximum of the reorg length. This operation is \(O(\log(k))\). Here, \(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 specification that follows is correct before NU5 activation. For the changes to header fields in NU5, refer to [zip-0244].
The hashFinalSaplingRoot block header field is renamed to hashLightClientRoot. The reason for the new name is the use of this field by light clients. (Before the Sapling network upgrade, the name of this field was hashReserved.) (In NU5, this field is renamed again to hashBlockCommitments, as specified in [zip-0244].)
Before the activation of the network upgrade that includes this ZIP, this existing consensus rule on block headers is enforced [protocol-blockheader]. (In the rule, the field has its new name.)
[Sapling onward]
hashLightClientRootmust be \(\mathsf{LEBS2OSP}_{256}(\mathsf{rt})\). Here, \(\mathsf{rt}\) is the root of the Sapling note commitment tree for the final Sapling tree state of this block.
In the activation block of this ZIP, hashLightClientRoot must be set to all zero bytes. This value must not be interpreted as a root hash.
In later blocks, hashLightClientRoot must be set to the value of hashChainHistoryRoot, as specified above.
The byte format and the version of the block header stay the same with this ZIP.
Rationale
Tree nodes
The nodes in the commitment tree are canonical and immutable. It is cheap to generate the nodes. The reason is this: except for nSaplingTxCount and nOrchardTxCount, all metadata is already generated during block construction or checked during block validation, or both. The nodes are relatively compact in memory.
At the time of the original publication of this ZIP, the chain had approximately 140,000 blocks after Sapling activation. If each of these blocks has a 164-byte commitment, the set of leaf nodes has an additional storage cost of approximately 24 MB. (The storage of intermediate nodes has an additional cost of approximately 24 MB.)
The structure of the commitment tree is formed by hashSubtreeCommitment. The other metadata commitments were selected for specific purposes. Originally, the variable-length commitments were put at the end, so that it was possible to index most metadata in a node directly. We considered fixed-length commitments here. But we selected variable-length commitments, to decrease by a small amount the memory requirements for the management and the update of the commitment trees.
The Orchard fields are put at the end, so that the existing uses of the other fields do not become more complex.
In leaf nodes, some information is repeated. We selected this design so that leaf nodes can be treated the same as internal nodes and root nodes. This applies to all algorithms and to all serializers and deserializers.
It is easy to identify a leaf node, for two reasons:
- The
hashSubtreeCommitmentfield of a leaf node contains proof of work. (For leaf nodes, this field commits to the block hash.) - The block range of a leaf node is exactly 1. The block range is calculated as
nLatestHeight- (nEarliestHeight- 1).
Personalized BLAKE2b-256 was selected so that it agrees with the existing Zcash conventions. The consensus branch ID is in the hash personalization string. Thus valid nodes from one consensus branch cannot be used to make false statements about parallel consensus branches.
FlyClient Requirements and Recommendations
With the commitments in the list below, FlyClient is possible in the variable-difficulty model. Specifically, with these commitments, light clients can reason about the application of the difficulty adjustment algorithm over a range of blocks. These commitments were selected in a discussion with an author of the FlyClient paper.
nEarliestTimestampnLatestTimestampnEarliestTargetBitsnLatestTargetBitsnEarliestHeightnLatestHeightnSubTreeTotalWork
Non-FlyClient Commitments
The additional metadata commitments were selected mainly to increase the security guarantees for light clients. We specified commitments where we saw an obvious security benefit. But other useful metadata that we did not find can exist. We are interested in feedback and suggestions from the implementers of the current light client.
We considered the addition of a commitment to the nullifier vector at each block. We ask light client teams for comments about the usefulness of this commitment. We also ask for comments about the correct serialization and commitment format for the nullifier vector. These comments are for a possible inclusion of the commitment in a future network upgrade.
hashEarliestSaplingRoot- This field commits to the earliest Sapling root of a range of blocks. With this commitment, light clients can check the consistency of treestate transitions over a range of blocks. It is not necessary for them to calculate the root again from genesis.
hashLatestSaplingRoot- This commitment has the same purpose as
hashFinalSaplingRootin the current Sapling semantics. - But the MMR tree commits to blocks \(B_x \ldots B_{n-1}\). Thus the latest commitment is to the final treestate of the previous block, and not to the final treestate of the current block.
- Concretely: in the current Sapling semantics, block 500 commits to the final treestate of block 500 in its header. With this ZIP, block 500 commits to all roots up to block 499, but not to the final root of block 500.
- We think that this tradeoff is acceptable. In reorgs, it is already unsafe to use the most recent treestate as a transaction anchor. We recommend that clients never use the most recent treestate to create transactions. Thus a delay of one block for the commitment is acceptable.
- This commitment has the same purpose as
nSaplingTxCount- This field commits to the number of Sapling transactions in blocks (and in ranges of blocks). Thus a light client can reliably know if a malicious server withholds any Sapling transactions.
- Also, with this commitment, light clients do not have to sync header ranges that do not contain Sapling transactions. The primary cost of a light client is the transmission of Equihash solution information in block headers. Thus, with this optimization, the bandwidth requirements of light clients become significantly smaller.
- An earlier draft of this ZIP had a commitment to the number of shielded transactions. This number included Sprout transactions and Sapling transactions. Such a commitment is not useful to light clients that support only Sapling addresses. These light clients cannot see the difference between Sapling transactions that are withheld maliciously and Sprout transactions that are not requested.
- A commitment to the number of Sprout transactions in blocks was not included. The reason is that Sprout addresses are effectively deprecated at this time, and light clients do not support Sprout addresses.
- If a future network upgrade has a new shielded pool, a new commitment to the transactions of that pool is added. This commitment has the same function for future light clients that do not support Sapling addresses.
hashEarliestOrchardRoot,hashLatestOrchardRoot, andnOrchardTxCount- These fields are included for the same reasons as the Sapling fields.
Header Format Change
The primary goal of the original authors was to make the header changes as small as possible. Specifically, they preferred not to introduce changes that can have an effect on mining hardware or embedded software. If the block header format changes, changes are necessary in all parts of the ecosystem. Thus we decided not to add hashChainHistoryRoot to the header as a new field.
ZIP 301 [zip-0301] has these rules for miner client software:
- It is recommended that the software alerts the user when it receives jobs with block header versions that it does not know about or support.
- The software must ignore such jobs.
The only formally defined block header version is 4. Thus, for any change to the header version, changes to miner client software are necessary so that miners can handle new jobs from mining pools. Thus we do not change the block version for this semantic change.
Block headers do not become ambiguous to interpret because of this. There are two reasons:
- Blocks commit to their block height in their coinbase transaction [bip-0034].
- Blocks are never handled in a standalone context. (Transactions are different, because they exist in the mempool outside of blocks.)
Because hashFinalSaplingRoot is replaced with hashChainHistoryRoot, a theoretical attack is possible. In this attack, a miner constructs a Sapling commitment tree update. The result of this update is the same 32-byte value as the MMR root. We do not think that this attack is realistic, for two reasons:
- The adversary must find a preimage over 32 layers of Pedersen hash.
- Light clients already must update their code to include the consensus branch ID for the Heartwood network upgrade. At the same time, they can change their code so that it does not use the value of this field as the Sapling tree root.
We also considered the option to put hashChainHistoryRoot in the hashPrevBlock field, because it commits to the full chain history. But we quickly found that, with this option, a very large refactor of the existing code base is necessary. Also, this option has a bad effect on performance. Reorgs in particular are fragile and performance-critical. Also, reorgs depend on backwards iteration over the chain history.
If a chain is designed from the start, it is possible that an efficient implementation can join these commitments. But such a design is clearly not applicable to Zcash as it exists.
For the genesis block, the calculation of hashChainHistoryRoot is not well defined. The reason is that \(n = 0\) for this block, and there is no block \(B_{n-1}\).
In some chains, the activation of this ZIP is after genesis. Zcash Mainnet and Testnet are two of these chains. For these chains, if there is no special case, the hashChainHistoryRoot of the activation block commits to the full previous epoch. It is not practical to calculate this commitment all at one time. Thus 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 is not encoded in that block. But it is committed to one block later, in the hashLatestSaplingRoot field of the MMR root commitment.
Security and Privacy Considerations
With this ZIP, there is an additional validation cost for new blocks. This validation cost is small. But existing DoS opportunities can become worse because of it, especially during abnormal events such as long reorgs. Fortunately, these costs are logarithmic in the number of delete and append operations.
In the worst case, an adversary with many resources can keep 2 chains of approximately equal length. The adversary can then extend the two chains in alternation. The result is repeated reorgs of increasing length.
Because of the performance of BLAKE2b, we expect that this validation cost is negligible. But it seems to be good practice to benchmark possible MMR implementations during the implementation process. If the validation cost is higher than expected, there are several possible mitigations. An example is to keep recently seen nodes in memory after a reorg.
Usually, header commitments have no effect on privacy. But FlyClient has additional security and privacy implications. FlyClient is a motivation for this ZIP. Thus it seems to be good practice to include a short overview. We recommend that a more detailed security analysis of FlyClient is done before the design of a FlyClient-based light client ecosystem for Zcash.
Like all light clients, FlyClient must have a connection to a light client server. That server can collect information about client requests. It can also use that information in an attempt to deanonymize clients. But FlyClient proofs are non-interactive and publicly verifiable. Thus, after the initial interaction with the server, these proofs can be shared among many light clients.
FlyClient proofs are probabilistic. If a proof is constructed correctly, the probability that the verifier accepts a dishonest chain commitment is negligible. The security analysis has these assumptions:
- The mining power of the adversary is a maximum of a known fraction of the combined mining power of honest nodes.
- The adversary cannot drop or tamper with messages between the client and full nodes.
- The client is connected to a minimum of one full node.
- The client knows the genesis block.
Also, the FlyClient paper [FlyClient] has an analysis of these security properties only for chain models with slowly adjusting difficulty, such as Bitcoin. For chains with rapidly adjusting difficulty (for example, Zcash or Ethereum), this analysis is an open problem in the paper. According to the paper, the security guarantees of the FlyClient protocol are only heuristic in that case.
But some additional commitments were added in a discussion with an author of the FlyClient paper. With these commitments, light clients can reason about the application of the difficulty adjustment algorithm. Refer to FlyClient Requirements and Recommendations. The academic security literature does not contain an analysis of the use of these fields. If deficiencies are found in a later security analysis, these fields can be updated in a future network upgrade.
Deployment
On the Zcash Mainnet and Testnet, this ZIP is deployed with the Heartwood network upgrade [zip-0250].
At the activation of the NU5 network upgrade [zip-0252], additional fields are added for the new Orchard shielded protocol.
Additional Reading
- Flyclient enabled geth fork by FlyClient authors
- Draft ECIP-1055: Succinct PoW Using Merkle Mountain Ranges
- Grin project MMR implementation in Rust
- Tari Project MMR implementation in Rust
- Beam Project MMR implementation in C++
- Mimblewimble MMR docs
- MMR Python implementation
- Tari MMR documentation
- opentimestamps-server Merkle Mountain Range documentation
References
- [BCP14]
- Information on BCP 14 — "RFC 2119: Key words for use in RFCs to Indicate Requirement Levels" and "RFC 8174: Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words"
- [FlyClient]
- FlyClient protocol
- [protocol-blockheader]
- Zcash Protocol Specification, Version 2021.2.16. Section 7.6: Block Header Encoding and Consensus
- [protocol-workdef]
- Zcash Protocol Specification, Version 2021.2.16. Section 7.7.5: Definition of Work
- [zcashBlock]
- Zcash block primitive
- [mimblewimble]
- MimbleWimble Grin MMR implementation
- [bip-0034]
- BIP 34: Block v2, Height in Coinbase
- [zip-0200]
- ZIP 200: Network Upgrade Mechanism
- [zip-0244]
- ZIP 244: Transaction Identifier Non-Malleability
- [zip-0250]
- ZIP 250: Deployment of the Heartwood Network Upgrade
- [zip-0252]
- ZIP 252: Deployment of the NU5 Network Upgrade
- [zip-0301]
- ZIP 301: Zcash Stratum Protocol
- [zip-0307]
- ZIP 307: Light Client Protocol for Payment Detection