VII FlyClient Guide: Merkle mountain ranges, the chain-history commitment, and the FlyClient sampling protocol 5 The FlyClient protocol 7 The deployment boundary

6 The chain-history commitment

This section states the commitment that Zcash block headers carry, each rule cited to the ZIP or the protocol specification section that fixes it, and each object before its first use: the upgrade epochs over which it ranges, the node vector of its Merkle mountain range, the hashing of the tree and its root commitment, the authorising-data root and the block commitment hash of ZIP 244 that wraps the root from NU5, the header consensus rules, and the range of blocks to which each header commits.

6.1 The deployed chain commitment

ZIP 221 (Final), “FlyClient - Consensus-Layer Changes”, changes the semantics of the block header and the consensus rules from Heartwood. The $32$ -byte header field that held the root of the Sapling note commitment tree instead commits to the root of a Merkle mountain range (Definition 3.1; ZIP 221, “Terminology”: a binary hash tree that admits appends of new leaves “without changing the value of existing nodes”) whose nodes carry aggregated metadata. Its leaves are the blocks from the last activation height below the committing block up to the parent of that block: the epoch tree of Definition 6.2. ZIP 221 thus deploys the invariant of Construction 5.1 restricted to one upgrade epoch, the heights from one activation height up to the next (Definition 6.1), and not from the genesis block. The tree and its node fields $1$ to $14$ are ZIP 221’s; fields $15$ to $17$ are ZIP 258’s (Draft, in force from NU6.3 by Definition 1.2); and from NU5 the root is committed as the first input of the block commitment hash, a personalised hash of the root together with the block’s authorising-data root (ZIP 244; “The block commitment hash”, §6.6). Seven node fields serve reasoning about difficulty without matching the node of Definition 5.6 (ePrint 2019/226, Definition 7) field for field (Remark 6.4). Each term of this paragraph carries here only its defining clause; its definition is in the subsection named.

The purpose of the commitment, after ZIP 221, “Motivation”, is to let a light client verify, with a number of headers logarithmic rather than linear in the chain length and correctly with high probability, the validity of a chain received from a full node, the inclusion of a block in it, and metadata of any block or range of blocks; the commitment also admits subtree proofs, which check only blocks later than the most recently verified one. Transaction inclusion within a block is left to ZIP 307 (Draft). No claim of this paragraph is proved in this section; the protocol that would realise it is that of “The FlyClient protocol” (§5), and its relation to the deployed commitment is classified in “The deployment boundary” (§7).

6.2 Upgrade epochs and epoch trees

Definition 6.1 (Upgrade epoch).

Let $0=A_{0}<A_{1}<A_{2}<\cdots$ be the distinct activation heights of the network upgrades of a chain (ZIP 200, “Activation mechanism”), height $0$ counted as an activation height (ZIP 221, “Specification”). The named upgrades and their order are those of Definition 1.1; the list of activation heights includes those of upgrades that definition does not name. The upgrade epoch beginning at $A_{i}$ is the interval of heights $[A_{i},A_{i+1})$ , unbounded for the last activation height. For $i\geq 1$ its blocks are validated under one consensus rule set and one consensus branch ID, the $32$ -bit identifier of the last upgrade that activates at $A_{i}$ (ZIP 200, “Specification”; Ironwood Guide, §“The transaction format”). The upgrade epoch is distinct, by name and by object, from the retarget epoch of Definition 4.5; the word “epoch” is not used alone. The Heartwood activation height is written $A_{H}$ , and $B_{A_{H}}$ is the Heartwood activation block.

Definition 6.2 (Epoch tree).

For a block height $\eta>0$ , the preceding activation height $\alpha(\eta)$ is the largest activation height $A_{i}<\eta$ , the “preceding network upgrade height” of ZIP 221, “Specification”; $\alpha(0)$ is undefined. For $\eta>A_{H}$ the epoch tree $\mathcal{T}_{\eta}$ is the Merkle mountain range $M^{L}_{n}$ under the left fold $\mathrm{Bag}_{L}$ (Definition 3.5), bagging nodes included as internal nodes, with the

n=\eta-\alpha(\eta)\geq 1

leaves $B_{\alpha(\eta)},\dots,B_{\eta-1}$ in height order: leaf $j$ is $B_{\alpha(\eta)+j-1}$ . Since $\alpha(\eta)$ is the last activation height below $\eta$ , all its leaves lie in the one upgrade epoch beginning at $\alpha(\eta)$ . Its node contents are fixed in “The node vector” (§6.3) and its hashing in “The epoch tree and its root commitment” (§6.4). No epoch tree is defined for $\eta\leq A_{H}$ .

Which header commits to $\mathcal{T}_{\eta}$ is not part of Definition 6.2: it is Definition 6.22 in “The header consensus rules” (§6.7), and its consequences for the committed ranges are stated in “The committed range” (§6.8).

6.3 The node vector

Definition 6.3 (Node vector).

The epoch tree $\mathcal{T}_{\eta}$ is an instance of Definition 3.19 under $\mathrm{Bag}_{L}$ . Every node $v$ of it, leaf, internal node, bagging node or root, carries one node vector of fields, serialised canonically by the map $\mathrm{ser}$ of Definition 6.5; that serialisation is used whenever a parent commitment is formed. The fields are numbered as in ZIP 221, “Tree Node specification”. For a block $B_{\eta^{\prime}}$ with header $\mathrm{hdr}^{\prime}$ , the leaf map sets both members of each earliest/latest pair from $B_{\eta^{\prime}}$ itself:

(1)

field $\mathsf{hashSubtreeCommitment}$ is $\mathsf{BlockHash}(\mathrm{hdr}^{\prime})$ (Definition 2.3), in internal byte order and unpersonalised;
(2), (3)

fields $\mathsf{nEarliestTimestamp}$ and $\mathsf{nLatestTimestamp}$ are the field $\mathsf{nTime}$ of $\mathrm{hdr}^{\prime}$ ;
(4), (5)

fields $\mathsf{nEarliestTargetBits}$ and $\mathsf{nLatestTargetBits}$ are the field $\mathsf{nBits}$ of $\mathrm{hdr}^{\prime}$ (the semantics of $\mathsf{nTime}$ and $\mathsf{nBits}$ : Consensus Guide, §“Difficulty in motion”);
(6), (7)

fields $\mathsf{hashEarliestSaplingRoot}$ and $\mathsf{hashLatestSaplingRoot}$ are $\mathsf{LEBS2OSP}_{256}(\mathsf{rt})$ for $\mathsf{rt}$ the root of the Sapling note commitment tree of the final Sapling treestate of $B_{\eta^{\prime}}$ (protocol specification, §“Block Header Encoding and Consensus”), an opaque $32$ -byte value in this volume;
(8)

field $\mathsf{nSubTreeTotalWork}$ is the work $\lfloor 2^{256}/(\mathsf{ToTarget}(\mathsf{nBits})+1)\rfloor$ of $B_{\eta^{\prime}}$ (Consensus Guide, §“Work, and the best chain”, Definition “Work of a block”);
(9), (10)

fields $\mathsf{nEarliestHeight}$ and $\mathsf{nLatestHeight}$ are the height $\eta^{\prime}$ ;
(11)

field $\mathsf{nSaplingTxCount}$ is the number of transactions of $B_{\eta^{\prime}}$ in which $\mathsf{vSpendsSapling}$ or $\mathsf{vOutputsSapling}$ is non-empty;
(12), (13)

fields $\mathsf{hashEarliestOrchardRoot}$ and $\mathsf{hashLatestOrchardRoot}$ are the Orchard-pool anchor of $B_{\eta^{\prime}}$ , the root of the Orchard pool’s note commitment tree in the final treestate of $B_{\eta^{\prime}}$ (Ironwood Guide, §“Anchors”, Definition “Treestate and anchor”);
(14)

field $\mathsf{nOrchardTxCount}$ is the number of transactions of $B_{\eta^{\prime}}$ in which $\mathsf{vActionsOrchard}$ is non-empty (Ironwood Guide, §“The transaction format”);
(15)–(17)

fields $\mathsf{hashEarliestIronwoodRoot}$ , $\mathsf{hashLatestIronwoodRoot}$ and $\mathsf{nIronwoodTxCount}$ are the Ironwood-pool anchor of $B_{\eta^{\prime}}$ and the number of its transactions in which $\mathsf{vActionsIronwood}$ is non-empty, computed as fields $12$ to $14$ .

The parent rule: an internal node with left child $\ell$ and right child $r$ takes each earliest field ( $2$ , $4$ , $6$ , $9$ , $12$ , $15$ ) from $\ell$ and each latest field ( $3$ , $5$ , $7$ , $10$ , $13$ , $16$ ) from $r$ ; it sums the additive fields, field $8$ modulo $2^{256}$ and the per-pool counts $11$ , $14$ and $17$ in $\mathbb{Z}$ ; and it sets field $1$ by Construction 6.10, the personalised hash of $\mathrm{ser}(\ell)\,\|\,\mathrm{ser}(r)$ . Fields $12$ to $14$ are ZIP 221’s own, added at NU5 (ZIP 252). Fields $15$ to $17$ are ZIP 258’s, “Changes to ZIP 221” (Draft), whose rules apply from NU6.3 activation (Definition 1.2).

For field $8$ , ZIP 221, “Tree Node specification”, states that computations modulo $2^{256}$ are fine because cumulative chain work is assumed to be at most $2^{256}$ , an aggregate effort of $2^{256}$ or more being infeasible; under that assumption, with the total below $2^{256}$ , the field of a node is the integer sum of the work of its leaves (Lemma 3.21(2)). Table 2 summarises the definition.

	Field	Type	Leaf value for $B_{\eta^{\prime}}$	Internal node	ZIP
$1$	$\mathsf{hashSubtreeCommitment}$	char[32]	$\mathsf{BlockHash}(\mathrm{hdr}^{\prime})$	hash	221
$2$	$\mathsf{nEarliestTimestamp}$	uint32	$\mathsf{nTime}$	inherit left	221
$3$	$\mathsf{nLatestTimestamp}$	uint32	$\mathsf{nTime}$	inherit right	221
$4$	$\mathsf{nEarliestTargetBits}$	uint32	$\mathsf{nBits}$	inherit left	221
$5$	$\mathsf{nLatestTargetBits}$	uint32	$\mathsf{nBits}$	inherit right	221
$6$	$\mathsf{hashEarliestSaplingRoot}$	char[32]	final Sapling root	inherit left	221
$7$	$\mathsf{hashLatestSaplingRoot}$	char[32]	final Sapling root	inherit right	221
$8$	$\mathsf{nSubTreeTotalWork}$	uint256	work of the block	sum mod $2^{256}$	221
$9$	$\mathsf{nEarliestHeight}$	CompactSize	height $\eta^{\prime}$	inherit left	221
$10$	$\mathsf{nLatestHeight}$	CompactSize	height $\eta^{\prime}$	inherit right	221
$11$	$\mathsf{nSaplingTxCount}$	CompactSize	transactions with Sapling spends or outputs	sum	221
$12$	$\mathsf{hashEarliestOrchardRoot}$	char[32]	Orchard-pool anchor	inherit left	221
$13$	$\mathsf{hashLatestOrchardRoot}$	char[32]	Orchard-pool anchor	inherit right	221
$14$	$\mathsf{nOrchardTxCount}$	CompactSize	transactions with Orchard-pool Actions	sum	221
$15$	$\mathsf{hashEarliestIronwoodRoot}$	char[32]	Ironwood-pool anchor	inherit left	258
$16$	$\mathsf{hashLatestIronwoodRoot}$	char[32]	Ironwood-pool anchor	inherit right	258
$17$	$\mathsf{nIronwoodTxCount}$	CompactSize	transactions with Ironwood-pool Actions	sum	258

Table 2: The fields of the node vector of Definition 6.3: serialised type, value at the leaf for the block

B_{\eta^{\prime}}

with header

\mathrm{hdr}^{\prime}

, rule at an internal node (“hash” is Construction 6.10), and source: ZIP 221, “Tree Node specification”, for fields

1

14

, and ZIP 258, “Changes to ZIP 221”, for fields

15

17

Remark 6.4 (The FlyClient fields).

ZIP 221, “FlyClient Requirements and Recommendations”, designates seven fields, $2$ to $5$ and $8$ to $10$ , which “enable FlyClient in the variable-difficulty model” by letting a light client reason about the application of the difficulty adjustment over a range of blocks. They serve the purpose of Definition 5.6 without matching it field for field. The leaf count of a node, the field $\mathsf{n}$ of the difficulty MMR, is $\mathsf{nLatestHeight}-\mathsf{nEarliestHeight}+1$ (Lemma 6.6). The field $\mathsf{w}$ of the difficulty MMR sums difficulty levels (Definition 4.2), whereas $\mathsf{nSubTreeTotalWork}$ sums work, a different normalisation. The field $\mathsf{nEarliestTargetBits}$ is a compact target, ordered inversely to $\mathsf{D}_{\mathsf{start}}$ . No field carries the elapsed time $\mathsf{t}$ ; the timestamps of the first and last block stand in its place. No field carries $\mathsf{D}_{\mathsf{next}}$ : the next target of a Zcash block is a function of an averaging window of preceding blocks (Consensus Guide, §“Difficulty in motion”), which the aggregates of a node do not determine.

Fields $6$ , $7$ and $11$ to $14$ are ZIP 221’s “Non-FlyClient Commitments”, chosen “primarily to improve light client security guarantees”, with no counterpart in ePrint 2019/226. Field $1$ “forms the structure of the commitment tree” (ZIP 221, “Tree nodes”), and fields $15$ to $17$ are the ZIP 258 counterparts for the Ironwood pool. The earliest roots let a client check the treestate transitions over a range of blocks without recomputing the roots from genesis. ZIP 221, “Non-FlyClient Commitments”, states that $\mathsf{hashLatestSaplingRoot}$ serves the purpose of the former header field $\mathsf{hashFinalSaplingRoot}$ , one block delayed (Proposition 6.23). The per-pool counts follow the rule of the same section that a new shielded pool adds a count of its transactions, applied at NU5 (fields $12$ to $14$ ) and at NU6.3 (fields $15$ to $17$ , ZIP 258).

Definition 6.5 (Field vector by upgrade epoch).

The fields are encoded as follows: a char[32] field as its $32$ bytes; a uint32 or uint256 field little-endian, as $\mathsf{I2LEOSP}_{32}$ or $\mathsf{I2LEOSP}_{256}$ (protocol specification, §“Integers, Bit Sequences, and Endianness”); a height or count as its CompactSize encoding in minimal form (Definition 2.2); and each pool-root field as $\mathsf{LEBS2OSP}_{256}$ of the root, as the specification encodes the Orchard anchor (protocol specification, §“Transaction Encoding and Consensus”). For a node $v$ , $\mathrm{ser}(v)$ is the concatenation of the encodings of its fields in field order. The field vector of an upgrade epoch is:

1.

fields $1$ to $11$ in the Heartwood and Canopy upgrade epochs;
2.

fields $1$ to $14$ in the NU5, NU6, NU6.1 and NU6.2 upgrade epochs;
3.

fields $1$ to $17$ in the NU6.3 and NU7 upgrade epochs.

The vectors are named by their fields. ZIP 221, “Tree Node specification”, omits fields $12$ to $14$ “before NU5 activation”, and ZIP 258, “Changes to ZIP 221”, omits fields $15$ to $17$ “before NU6.3 activation”; neither says whether the height of a leaf’s block or that of the committing block governs, and the two differ only for the tree committed by an activation block. Adopted reading, resolving that ambiguity: every node of $\mathcal{T}_{\eta}$ uses the field vector of the upgrade epoch beginning at $\alpha(\eta)$ , the upgrade epoch of its leaves.

The reading is adopted for the following reason. Under the other reading the tree $\mathcal{T}_{A}$ committed by $B_{A}$ , at an activation height $A$ that adds fields, would serialise every node of the previous upgrade epoch with the added fields; every internal node would change value, and $\mathcal{T}_{A}$ would not be an append of $\mathcal{T}_{A-1}$ , contrary to the property by which ZIP 221, “Terminology”, defines a Merkle mountain range. The ZIP’s pseudocode, which takes a leaf’s Orchard fields from the leaf’s own block and serialises them only when present, is consistent with the reading. Two consequences rest on it: $\mathcal{T}_{A}$ uses the previous upgrade epoch’s vector, and $\mathcal{T}_{A+1}$ is the first tree with the new one; under the other reading $\mathcal{T}_{A}$ would carry the new vector. For NU7, no ZIP among the sources of NU7 consensus changes listed in ZIP 259 (Draft), “NU7 consensus changes”, amends ZIP 221 or ZIP 244, so the nodes of the trees of the NU7 upgrade epoch carry fields $1$ to $17$ under either reading.

The fixed-width fields occupy $144$ , $208$ and $272$ bytes in the three vectors, and the three, four and five CompactSize fields $1$ to $9$ bytes each, so a serialised node has $147$ to $171$ , $212$ to $244$ and $277$ to $317$ bytes, the ranges that ZIP 221 and ZIP 258 state. A toy chain computed by script illustrates the reading, with an activation block that commits a tree of the previous vector and the next block the first to commit a tree of the new one; it establishes nothing.

Lemma 6.6 (Leaf count and shape).

Every node $v$ of $\mathcal{T}_{\eta}$ , bagging nodes included, spans a run of consecutive leaves $B_{\eta_{1}},\dots,B_{\eta_{2}}$ with $v.\mathsf{nEarliestHeight}=\eta_{1}$ and $v.\mathsf{nLatestHeight}=\eta_{2}$ , so its leaf count is $\mathsf{nLatestHeight}-\mathsf{nEarliestHeight}+1$ . The node $v$ roots a perfect subtree of $\mathcal{T}_{\eta}$ if and only if that count is a power of two. In particular a leaf is the only kind of node with count $1$ .

Proof.

By induction on the parent rule of Definition 6.3. A leaf has both heights equal to its block’s. An internal node inherits $\mathsf{nEarliestHeight}$ from its left child and $\mathsf{nLatestHeight}$ from its right child, and in a range under $\mathrm{Bag}_{L}$ the run of the left child immediately precedes that of the right child, the heights of the leaves of $\mathcal{T}_{\eta}$ being consecutive by Definition 6.2. A perfect subtree of altitude $a$ spans $2^{a}$ leaves (Definition 3.1), and every node inside a peak roots a perfect subtree. A bagging node of the left fold spans the peaks $P_{1},\dots,P_{i}$ for some $i\geq 2$ (Definition 3.5), whose sizes are distinct powers of two, set bits of $n$ (Definition 3.4); a sum of two or more distinct powers of two has at least two set bits and is not a power of two. An internal node spans at least two leaves. A script checks the statement for $1\leq n\leq 1{,}024$ . □

Lemma 6.7 (Leaves and header linkage).

For $\alpha(\eta)\leq\eta^{\prime}\leq\eta-1$ , field $1$ of the leaf of $\mathcal{T}_{\eta}$ for $B_{\eta^{\prime}}$ equals the field $\mathsf{hashPrevBlock}$ of the header of $B_{\eta^{\prime}+1}$ , which for $\eta^{\prime}=\eta-1$ is the committing block $B_{\eta}$ . Consequently a received header is matched to its leaf by computing its block hash and comparing it with field $1$ , and the leaves add no hashing beyond the block hashes.

Proof.

By Definition 6.3, field $1$ of the leaf is $\mathsf{BlockHash}$ of the header of $B_{\eta^{\prime}}$ in internal byte order; by Definition 2.3, the field $\mathsf{hashPrevBlock}$ of $B_{\eta^{\prime}+1}$ is that same hash. ZIP 221, “Tree Node specification”, states the identity. □

Remark 6.8 (Non-monotone timestamps).

Consensus bounds the field $\mathsf{nTime}$ of a block below, strictly above the median of the timestamps of the preceding eleven blocks, and above, by that median plus $90$ minutes (protocol specification, §“Block Header Encoding and Consensus”; Consensus Guide, §“Difficulty in motion”). It orders two timestamps only at a distance: the median-time-past never decreases and rises by at least one second every eleven blocks, so a block at least $11\cdot 5{,}400=59{,}400$ heights after another has the strictly later timestamp. By the same count, $\mathsf{nLatestTimestamp}\geq\mathsf{nEarliestTimestamp}$ holds for every node with $\mathsf{nLatestHeight}-\mathsf{nEarliestHeight}\geq 11\cdot 5{,}399=59{,}389$ , and for a leaf, whose two timestamps are equal; for smaller spans this argument gives no order. ZIP 221, “Tree Node specification”, says that the reverse order “may occur within subtrees smaller than $\mathsf{PoWMedianBlockSpan}$ blocks”; this is an example, not a bound. A block whose timestamp lies up to $90$ minutes ahead of the median exceeds the timestamps of the later blocks whose timestamps track real time, until real time passes it, and $90$ minutes spans more than eleven target spacings (protocol specification, §“Constants”; from NU7, ZIP 218).

6.4 The epoch tree and its root commitment

The tree is defined from the prose of ZIP 221, “Background”, “Specification”, “Tree Node specification” and “Block header semantics and consensus rules”, with ZIP 258, “Changes to ZIP 221”. That prose is ambiguous at two points, both at an activation block: the field vector, settled by the adopted reading of Definition 6.5, and the branch ID of the personalisation, settled by Definition 6.9. The pseudocode of ZIP 221 is cited only as corroboration of the two readings; it carries editorial defects, among them in the serialisation of the Orchard fields, none of which bears on either reading.

Definition 6.9 (Branch ID of a tree).

ZIP 221, “Tree Node specification”, states that the personalisation encodes “the consensus branch ID for the epoch of the block containing the commitment”, and continues: “Which is to say, each node in the tree commits to the consensus branch that produced it.” The two sentences agree at every $\eta>A_{H}$ that is not an activation height, since $B_{\eta}$ and the leaves of $\mathcal{T}_{\eta}$ then lie in one upgrade epoch. At an activation height $A>A_{H}$ the first names the upgrade epoch beginning at $A$ and the second the upgrade epoch of the leaves $B_{\alpha(A)},\dots,B_{A-1}$ . At $A_{H}$ no epoch tree is defined (Definition 6.2). Adopted reading, resolving an ambiguity of specified text: the branch ID $b(\mathcal{T})$ of an epoch tree $\mathcal{T}$ is the consensus branch ID of the upgrade epoch whose blocks are the leaves of $\mathcal{T}$ , and every internal node and the root commitment of $\mathcal{T}$ are hashed under it.

The reading is adopted for three reasons. (1) “Which is to say” introduces the second sentence as a restatement of the first, and it is the sentence that assigns a branch ID to each node. (2) Under the first reading the tree committed by $B_{A}$ would not be an append of the tree committed by $B_{A-1}$ , every internal node changing value, contrary to the property by which ZIP 221, “Terminology”, defines a Merkle mountain range (the reason for which Definition 6.5 adopts the leaves’ vector); and the whole previous upgrade epoch would be rehashed in one block, the cost that ZIP 221, “Header Format Change”, calls impractical and avoids by a special case at the Heartwood activation block and at no later one. (3) The pseudocode of ZIP 221 hashes each parent under the branch ID of its left child and the root commitment under that of the root node, each leaf carrying the branch ID of its own block. Every later statement about the tree committed by an activation block rests on this reading and cites it; under the first reading each holds with the branch ID of the new upgrade epoch in place of $b(\mathcal{T}_{A})$ .

Construction 6.10 (Hashing of the epoch tree).

Let $\mathsf{h}(P,x)$ be BLAKE2b-256 with the $16$ -byte personalisation $P$ on input $x$ (Ironwood Guide, §“Transaction digests and signatures”; Crypto Guide, §“Domain separation and personalisation”), and let $\beta$ be the $4$ -byte little-endian encoding of $b(\mathcal{T}_{\eta})$ . The personalisation is the $12$ ASCII bytes ZcashHistory followed by $\beta$ , $16$ bytes in all. The tree $\mathcal{T}_{\eta}$ is the range $M^{L}_{n}$ whose nodes are node vectors (Definition 6.3) under the field vector of Definition 6.5. Its bagging nodes, which join the two leftmost remaining peaks until one remains,

\bigl{(}\cdots\bigl{(}(P_{1}\,\|\,P_{2})\,\|\,P_{3}\bigr{)}\cdots\bigr{)}\,\|% \,P_{d},

are ordinary internal nodes, and a single peak is the root node. For an internal node with children $\ell$ and $r$ , field $1$ is

\mathsf{h}\bigl{(}\texttt{ZcashHistory}\,\|\,\beta,\ \mathrm{ser}(\ell)\,\|\,% \mathrm{ser}(r)\bigr{)},

over the children’s full serialisations; its other fields follow the parent rule of Definition 6.3. The branch ID is not a node field: it enters only through the personalisation, and whoever recomputes a node hash supplies $b(\mathcal{T}_{\eta})$ by Definition 6.9, the upgrade epoch being fixed by the node’s heights. For the Heartwood branch ID $\mathtt{0xF5B9230B}$ the last four bytes of the personalisation are $\mathtt{0B}\ \mathtt{23}\ \mathtt{B9}\ \mathtt{F5}$ .

Upgrade epoch	Branch ID	Fixed by	Bytes $13$ to $16$ of the personalisation	Fields
Heartwood	$\mathtt{0xF5B9230B}$	ZIP 250	$\mathtt{0B\ 23\ B9\ F5}$	$1$ to $11$
Canopy	$\mathtt{0xE9FF75A6}$	ZIP 251	$\mathtt{A6\ 75\ FF\ E9}$	$1$ to $11$
NU5	$\mathtt{0xC2D6D0B4}$	ZIP 252	$\mathtt{B4\ D0\ D6\ C2}$	$1$ to $14$
NU6	$\mathtt{0xC8E71055}$	ZIP 253	$\mathtt{55\ 10\ E7\ C8}$	$1$ to $14$
NU6.1	$\mathtt{0x4DEC4DF0}$	ZIP 255	$\mathtt{F0\ 4D\ EC\ 4D}$	$1$ to $14$
NU6.2	$\mathtt{0x5437F330}$	ZIP 257	$\mathtt{30\ F3\ 37\ 54}$	$1$ to $14$
NU6.3	$\mathtt{0x37A5165B}$	ZIP 258 (Draft)	$\mathtt{5B\ 16\ A5\ 37}$	$1$ to $17$
NU7	$\mathtt{0x77190AD9}$	ZIP 259 (Draft)	$\mathtt{D9\ 0A\ 19\ 77}$	$1$ to $17$

Table 3: The branch IDs entering the personalisation

\texttt{ZcashHistory}\,\|\,\beta

of Construction 6.10: one row per upgrade epoch that bears an epoch tree, each tree hashed under its own personalisation, with the ZIP that fixes the branch ID (ZIP 258, “NU6.3 deployment”; ZIP 259, “NU7 network constants”), the little-endian bytes

\beta

and the field vector of Definition 6.5.

Definition 6.11 (Chain-history root).

For $\eta>A_{H}$ the chain-history root of $\mathcal{T}_{\eta}$ is

\mathsf{hashChainHistoryRoot}(\mathcal{T}_{\eta}):=\mathsf{h}\bigl{(}\texttt{% ZcashHistory}\,\|\,\beta,\ \mathrm{ser}(\text{root node of }\mathcal{T}_{\eta}% )\bigr{)},

with $\beta$ encoding $b(\mathcal{T}_{\eta})$ (ZIP 221, “Tree Node specification”). It is not field $1$ of the root node: the committed value covers the root’s aggregates, namely the total work modulo $2^{256}$ , the first and last timestamps, target bits and heights, the boundary pool roots and the per-pool counts. When $\alpha(\eta)=\eta-1$ the tree has one leaf, which is its root node, and the value is defined there too. ZIP 258, “Changes to ZIP 221”, leaves the definition unchanged apart from the added fields.

Definition 6.12 (History input of a block).

For $\eta\geq A_{H}$ the history input of $B_{\eta}$ is

\mathsf{hashLightClientRoot}(\eta):=\begin{cases}\text{the string of $32$ zero% bytes}&\text{if }\eta=A_{H},\\ \mathsf{hashChainHistoryRoot}(\mathcal{T}_{\eta})&\text{if }\eta>A_{H}.\end{cases}

The value at $A_{H}$ is the sentinel that ZIP 221, “Block header semantics and consensus rules”, requires in the Heartwood activation block and states “MUST NOT be interpreted as a root hash”. The history input is a total function of the height from $A_{H}$ on, and it is the value that ZIP 244, “Block Header Changes”, names “hashLightClientRoot (as described in ZIP 221)”.

Proposition 6.13 (Binding of the chain-history root).

Let $\mathcal{T}$ and $\mathcal{T}^{\prime}$ be epoch trees hashed under one branch ID $b$ . If $\mathsf{hashChainHistoryRoot}(\mathcal{T})=\mathsf{hashChainHistoryRoot}(% \mathcal{T}^{\prime})$ , then either $\mathcal{T}$ and $\mathcal{T}^{\prime}$ agree on every field of every node, or a collision of $\mathsf{h}(\texttt{ZcashHistory}\,\|\,\beta,\cdot)$ is computed from them efficiently. If in addition SHA-256d is collision resistant, the leaves’ block hashes bind the headers of the leaf blocks.

Proof.

The proposition is the ZIP 221 instance of Lemma 3.20(1), whose hypotheses are checked as follows. Serialisation. The branch ID $b$ fixes one upgrade epoch and hence one field vector for both trees (Table 3; Definitions 6.9 and 6.5). Its field order is fixed, and each field is of fixed width or a minimal CompactSize, whose first byte fixes its length (Definition 2.2). A serialised node therefore parses field by field: $\mathrm{ser}$ is injective, and no serialised node is a proper prefix of another, since the two parse to the same fields up to the end of the shorter and the number of fields is fixed; minimality makes $\mathrm{ser}$ a function of the node. Root and shape. If the root commitments are equal, then the two root serialisations are equal, or they are distinct inputs with equal images, a collision. Equal root nodes have equal $\mathsf{nEarliestHeight}$ and $\mathsf{nLatestHeight}$ , hence equal leaf count $n$ by Lemma 6.6, hence the same shape $M^{L}_{n}$ . The shape fixes which positions are leaves, so no leaf of one tree is compared with an internal node of the other, although the tree carries no layer tags (ZIP 221, “Tree nodes”, identifies leaves by their block range of $1$ ). Extraction. Lemma 3.20(1) then yields a collision at the first level of disagreement. Headers. Field $1$ of each leaf is the SHA-256d block hash of its header (Definition 2.3; Crypto Guide, §“The transparent layer’s hashes”); equal leaves with distinct headers are a collision of SHA-256d. □

Proposition 6.14 (Binding of range transaction counts).

Let a node $v$ of $\mathcal{T}_{\eta}$ be authenticated by an inclusion path (Definition 3.13, in the tuple form of Definition 3.19, siblings as full node vectors) accepted against the chain-history root of the epoch tree of a chain the client trusts. Barring a collision as in Proposition 6.13, $v.\mathsf{nSaplingTxCount}$ , and where present $v.\mathsf{nOrchardTxCount}$ and $v.\mathsf{nIronwoodTxCount}$ , equal the numbers of transactions in the blocks of the height range of $v$ in which $\mathsf{vSpendsSapling}$ or $\mathsf{vOutputsSapling}$ , $\mathsf{vActionsOrchard}$ and $\mathsf{vActionsIronwood}$ , respectively, are non-empty. Hence a client that obtains the transactions of those blocks, each authenticated against its block’s transaction root, detects the withholding of any such transaction by a count mismatch, and a range whose count is zero contains none and may be skipped; the count does not identify the missing transaction.

Proof.

By Lemma 3.20(2), an accepted path binds the full vector of every node it recomputes and of every sibling it carries, so $v$ is the node of the trusted tree at its position, barring a collision; the serialisation is prefix-free by the proof of Proposition 6.13. In that tree the count fields are consistent, and by the parent rule of Definition 6.3 and Lemma 6.6 the value of each count field of $v$ is its sum over the leaves of $v$ ’s height range. The reading as detection of withholding is ZIP 221, “Non-FlyClient Commitments”. □

Proposition 6.15 (Cross-branch separation).

For branch IDs $b\neq b^{\prime}$ with encodings $\beta\neq\beta^{\prime}$ the personalisations $\texttt{ZcashHistory}\,\|\,\beta$ and $\texttt{ZcashHistory}\,\|\,\beta^{\prime}$ differ. Model $\mathsf{h}(P,\cdot)$ , for each personalisation $P$ , as an independent random oracle with $256$ -bit output. An adversary making $q$ oracle queries, the queries of the verification of its output included, outputs $x,x^{\prime}$ with

\mathsf{h}(\texttt{ZcashHistory}\,\|\,\beta,x)=\mathsf{h}(\texttt{ZcashHistory% }\,\|\,\beta^{\prime},x^{\prime})

with probability at most $q^{2}/2^{256}$ . Hence no internal-node hash or root commitment computed under $b$ equals one computed under $b^{\prime}$ , except with that probability. Leaves are unpersonalised block hashes, identical in every branch, and are not separated.

Proof.

The modelling hypothesis is that of the Crypto Guide, §“Domain separation and personalisation”, Proposition “Domain separation yields independent oracles”: distinct tags give independent random oracles. Both values must be answers to queries, one to each oracle; each of the at most $q^{2}$ pairs of such queries agrees with probability $2^{-256}$ , and the union bound (Math Guide, §“The union bound and a birthday calculation”) gives the bound. ZIP 221, “Tree nodes”, states the design intent: “valid nodes from one consensus branch cannot be used to make false statements about parallel consensus branches”. □

6.5 The authorising-data root

The header field $\mathsf{hashMerkleRoot}$ (Definition 2.3) is the root of Bitcoin’s SHA-256d transaction Merkle tree over the transaction identifiers of the block (protocol specification, §“Block Header Encoding and Consensus”). The identifier of a version- $5$ or version- $6$ transaction excludes its authorising data (ZIP 244; Ironwood Guide, §“Transaction digests and signatures”, Definition “Authorising-data digest; effecting and authorising data”), so for such transactions $\mathsf{hashMerkleRoot}$ does not commit to the authorising data; the identifier of a version- $4$ transaction covers its whole encoding. The version- $4$ format is valid until NU7, from which ZIP 2003 (Draft), deployed by ZIP 259 (Draft), makes it invalid.

Construction 6.16 (Authorising-data root).

Let a block have the transactions $t_{1},\dots,t_{m}$ , where $m\geq 1$ because of the coinbase transaction. Leaf $i$ is the authorising-data commitment of $t_{i}$ : for version $5$ , the digest $\mathsf{auth\_digest}$ of ZIP 244, “Authorizing Data Commitment”; for version $6$ , the digest of the Ironwood Guide’s Definition “Authorising-data digest; effecting and authorising data” (ZIP 229 (Draft), “Block Commitments”: $\mathsf{hashAuthDataRoot}$ takes the version- $6$ digest “with no further structural change”); and for a transaction of a version before $5$ , the $32$ bytes $\mathtt{0xFF}$ , a placeholder used only in this tree and occurring only in blocks before NU7. The leaves are padded with leaves of $32$ zero bytes to $2^{\lceil\log_{2}m\rceil}$ , and $\mathsf{hashAuthDataRoot}$ is the root of the binary Merkle tree of height $\lceil\log_{2}m\rceil$ over them, each non-leaf node being $\mathsf{h}(\texttt{ZcashAuthDatHash},\mathit{left}\,\|\,\mathit{right})$ , under a $16$ -byte personalisation without branch ID. The insertion order MUST equal that of the transaction identifiers in the tree under $\mathsf{hashMerkleRoot}$ , so that one path identifies the same transaction in both trees (ZIP 244, “Block Header Changes”).

Proposition 6.17 (Joint binding of the two transaction roots).

Assume, with ZIP 244, “Authorizing Data Commitment”, that the pair of a transaction’s identifier and its authorising-data commitment is binding: distinct transactions with equal pairs form a collision of that pair map. Let two lists of $m$ transactions have equal $\mathsf{hashMerkleRoot}$ and equal $\mathsf{hashAuthDataRoot}$ . Then the lists are equal, or a collision of SHA-256d, of $\mathsf{h}(\texttt{ZcashAuthDatHash},\cdot)$ or of the pair map is computed from them. The binding is claimed for lists of the given length only: the identifier tree is Bitcoin’s transaction Merkle tree and inherits its duplicate-last-node caveat, and the header commits to no transaction count.

Proof.

For fixed $m$ , Bitcoin’s duplication rule and the zero padding of Construction 6.16 are fixed maps of the list, so the path argument of the Crypto Guide, §“Binary Merkle trees”, Proposition “Binding of the root”, applies to each tree: the two lists of identifiers agree, else a collision of SHA-256d is extracted, and the two lists of authorising-data commitments agree, else a collision of $\mathsf{h}(\texttt{ZcashAuthDatHash},\cdot)$ . The common insertion order aligns the two leaf sequences, so each position carries equal pairs, and distinct transactions there form a collision of the pair map. ZIP 244, “Authorizing Data Commitment”, states that the pair “constitutes a commitment to all the data of a serialized transaction”; for a transaction of a version before $5$ the identifier covers all data and the second member is the constant placeholder. The caveat is the Crypto Guide, §“Layer and domain separation”, Remark “Unbalanced trees, padding, and a deployed failure”. □

6.6 The block commitment hash

In this subsection $0^{32}$ denotes the string of $32$ zero bytes.

Definition 6.18 (Block commitment hash).

For a block $B_{\eta}$ at a height in or after the NU5 upgrade epoch, the block commitment hash is

\mathsf{hashBlockCommitments}(B_{\eta}):=\\ \mathsf{h}\bigl{(}\texttt{ZcashBlockCommit},\ \mathsf{hashLightClientRoot}(% \eta)\,\|\,\mathsf{hashAuthDataRoot}(B_{\eta})\,\|\,0^{32}\bigr{)},

with $\mathsf{hashLightClientRoot}(\eta)$ the history input of Definition 6.12, $\mathsf{hashAuthDataRoot}(B_{\eta})$ the root of Construction 6.16 for $B_{\eta}$ , and $0^{32}$ the terminator (ZIP 244, “Block Header Changes”). The input has $32+32+32=96$ bytes, and the $16$ -byte personalisation carries no branch ID. The history input is a function of the blocks before $B_{\eta}$ ; the authorising-data root is a function of $B_{\eta}$ itself.

Proposition 6.19 (Reopening the block commitment).

From NU5 the chain-history root appears in no header. Let $c$ be the value $\mathsf{hashBlockCommitments}(B_{\eta})$ of a block in or after the NU5 upgrade epoch. A verifier given a claimed history input $r$ , or a claimed root node vector from which it computes $r=\mathsf{h}(\texttt{ZcashHistory}\,\|\,\beta,\mathrm{ser}(\text{root}))$ with $\beta$ encoding the branch ID of Definition 6.9, and a $32$ -byte value $a$ , accepts $r$ if and only if

c=\mathsf{h}\bigl{(}\texttt{ZcashBlockCommit},\ r\,\|\,a\,\|\,0^{32}\bigr{)};

only the $32$ -byte value of $\mathsf{hashAuthDataRoot}$ is needed, not its tree. Two distinct accepted pairs $(r,a)\neq(r^{\prime},a^{\prime})$ exhibit a collision of $\mathsf{h}(\texttt{ZcashBlockCommit},\cdot)$ . Hence an accepted $r$ is the block’s history input except with that collision probability, and an inclusion path in the epoch tree is checked against a header through it.

Proof.

The pair $(\mathsf{hashLightClientRoot}(\eta),\mathsf{hashAuthDataRoot}(B_{\eta}))$ is accepted by Definition 6.18. The input $r\,\|\,a\,\|\,0^{32}$ has fixed length, so distinct pairs give distinct inputs, and two accepted pairs with equal image $c$ are a collision. □

Remark 6.20 (Extension of the block commitment hash).

ZIP 244, “Block Header Changes”, treats the value as “a linked list of hashes terminated by arbitrary data”: a later upgrade may replace the terminator by the hash of a new structure that ends in its own terminator. The same section states two interoperability rules: fully validating nodes MUST always use the entire structure defined by the latest activated protocol version they support, and a third-party server that supports a later protocol version SHOULD provide a value that can be used in place of the all-zero terminator, so that a light client can validate the parts it needs. No upgrade through NU7 replaces the terminator: ZIP 258, “Changes to ZIP 221”, leaves $\mathsf{hashBlockCommitments}$ “unaffected” beyond the added node fields; ZIP 229, “Block Commitments”, changes no structure; and no source of NU7 consensus changes listed in ZIP 259, “NU7 consensus changes”, amends ZIP 244.

6.7 The header consensus rules

Definition 6.21 (The commitment field by upgrade epoch).

The $32$ -byte header field that follows $\mathsf{hashMerkleRoot}$ (Definition 2.3) is named $\mathsf{hashReserved}$ before Sapling, $\mathsf{hashFinalSaplingRoot}$ in the Sapling and Blossom upgrade epochs, $\mathsf{hashLightClientRoot}$ in the Heartwood and Canopy upgrade epochs, and $\mathsf{hashBlockCommitments}$ from NU5 (protocol specification, §“Block Header Encoding and Consensus”; ZIP 221, “Block header semantics and consensus rules”; ZIP 244, “Block Header Changes”). The header byte format and version are unchanged by each renaming.

Definition 6.22 (Header commitment rule).

For a block $B_{\eta}$ the commitment field satisfies the following rules.

(i)

For $\eta<A_{H}$ it follows the earlier rules of the protocol specification, §“Block Header Encoding and Consensus”, not restated here: in the Sapling and Blossom upgrade epochs it is $\mathsf{LEBS2OSP}_{256}$ of the root of the Sapling note commitment tree of the block’s final Sapling treestate.
(ii)

For $A_{H}\leq\eta$ in the Heartwood or Canopy upgrade epoch it MUST equal the history input $\mathsf{hashLightClientRoot}(\eta)$ of Definition 6.12, which supplies the sentinel at $A_{H}$ .
(iii)

For $\eta$ in or after the NU5 upgrade epoch, the NU5 activation block included and without sentinel, it MUST equal $\mathsf{hashBlockCommitments}(B_{\eta})$ of Definition 6.18.

(ZIP 221, “Block header semantics and consensus rules”; ZIP 244, “Block Header Changes”; protocol specification, §“Block Header Encoding and Consensus”.) The value is undefined for the genesis block, which no case covers.

In the NU5 activation block $B_{A_{\mathrm{NU5}}}$ , $A_{\mathrm{NU5}}$ the NU5 activation height, the history input is $\mathsf{hashChainHistoryRoot}(\mathcal{T}_{A_{\mathrm{NU5}}})$ , the root of the completed tree of the Canopy upgrade epoch. It is hashed under the Canopy branch ID $\mathtt{0xE9FF75A6}$ (ZIP 251) by the adopted reading of Definition 6.9, the first sentence of ZIP 221 giving the NU5 branch ID instead, and it is built from nodes of fields $1$ to $11$ by the adopted reading of Definition 6.5. By Definition 6.22 every valid block after the Heartwood activation block commits to the root of its epoch tree: directly in the Heartwood and Canopy upgrade epochs, and from NU5 as the first input of the block commitment hash.

6.8 The committed range

Proposition 6.23 (One-block delay).

For $\eta>A_{H}$ the tree to which $B_{\eta}$ commits (Definition 6.22) has the leaves $B_{\alpha(\eta)},\dots,B_{\eta-1}$ . No header commits to a tree that contains its own block, and $B_{\eta-1}$ first enters a committed tree at $B_{\eta}$ . Consequently the final Sapling root of a block at a height of at least $A_{H}$ is committed one block later, as the field $\mathsf{hashLatestSaplingRoot}$ of the root node committed by the next block. ZIP 221, “Non-FlyClient Commitments”, accepts the delay because “using the most recent treestate as a transaction anchor is already unsafe in reorgs”.

Proof.

By Definition 6.2, $\eta$ lies outside $[\alpha(\eta),\eta-1]$ . Since $\eta-1\geq A_{H}$ and $\alpha(\eta)$ is the largest activation height below $\eta$ , $\alpha(\eta)\leq\eta-1$ , so $B_{\eta-1}$ is the last leaf of $\mathcal{T}_{\eta}$ ; it is no leaf of $\mathcal{T}_{\eta^{\prime}}$ for $\eta^{\prime}\leq\eta-1$ , whose leaves lie below $\eta^{\prime}$ . Then Definition 6.22. The latest-root field of the root node is that of its last leaf, by the parent rule of Definition 6.3. □

Theorem 6.24 (Reset at each activation height).

Let $A>A_{H}$ be an activation height and $A^{\prime}=\alpha(A)$ the preceding one. Then:

1.

$B_{A}$ commits to the complete tree $\mathcal{T}_{A}$ over $B_{A^{\prime}},\dots,B_{A-1}$ , the whole upgrade epoch beginning at $A^{\prime}$ , hashed under that upgrade epoch’s branch ID $b(\mathcal{T}_{A})$ by the adopted reading of Definition 6.9 and built with that upgrade epoch’s field vector by the adopted reading of Definition 6.5; the commitment field equals $\mathsf{hashChainHistoryRoot}(\mathcal{T}_{A})$ before NU5, and $\mathsf{hashBlockCommitments}(B_{A})$ with it as first input from NU5;
2.

$B_{A+1}$ commits to the single-leaf tree over $B_{A}$ ;
3.

for $A^{\prime}<\eta<A$ , the leaves of $\mathcal{T}_{\eta}$ are a proper prefix of those of $\mathcal{T}_{A}$ , so every ended upgrade epoch from Heartwood on is committed completely by exactly one header, that of the next activation block;
4.

the reset occurs at every upgrade, including those that leave the field vector unchanged (Canopy, NU6, NU6.1, NU6.2 and NU7).

Proof.

By the definition of $\alpha$ , $\alpha(A)=A^{\prime}$ and $\alpha(A+1)=A$ . For $A^{\prime}<\eta<A$ , $\alpha(\eta)=A^{\prime}$ , so $\mathcal{T}_{\eta}$ has the leaves $B_{A^{\prime}},\dots,B_{\eta-1}$ , a proper prefix of those of $\mathcal{T}_{A}$ ; only $\mathcal{T}_{A}$ has the full leaf set, and for $\eta>A$ no tree has the leaf $B_{A^{\prime}}$ , since $\alpha(\eta)\geq A$ . The commitment fields follow from Definition 6.22. Part (4) holds because $\alpha$ depends on the activation heights alone. A script illustrates (1) to (3) on a toy chain, a one-block upgrade epoch included; it establishes nothing. □

Figure 4 shows the ranges of the theorem.

Refer to caption — Figure 4: Committed ranges on a height axis, one cell per block, with the Heartwood activation height $A_{H}$ and two later activation heights $A^{\prime}<A$ , consecutive, and $A^{\prime}<\eta<A$ . Grey: heights below $A_{H}$ , a leaf of no epoch tree (Corollary 6.25). The Heartwood activation block carries the sentinel of Definition 6.12 and commits no tree. Each bar is the leaf range of the tree to which the header at the arrow’s head commits: $B_{\eta}$ commits $B_{A^{\prime}},\dots,B_{\eta-1}$ ; the activation block $B_{A}$ commits the whole upgrade epoch $B_{A^{\prime}},\dots,B_{A-1}$ (Theorem 6.24(1)); and $B_{A+1}$ commits the single leaf $B_{A}$ (Theorem 6.24(2)). No bar reaches below $A_{H}$ .

Corollary 6.25 (No commitment below the Heartwood activation height).

The Heartwood activation block $B_{A_{H}}$ commits to no tree, its history input being the sentinel of Definition 6.12. For $\eta>A_{H}$ , $\alpha(\eta)\geq A_{H}$ , so no committed tree has a leaf below $A_{H}$ . Below $A_{H}$ the commitment field holds a Sapling root or is reserved (Definition 6.21).

Proof.

The height $A_{H}$ is an activation height below every $\eta>A_{H}$ , and $\alpha(\eta)$ is the largest such; then Definition 6.22, item (ii). □

Corollary 6.26 (The NU7 upgrade epoch).

Let $A_{\mathrm{NU7}}$ be the NU7 activation height. The block $B_{A_{\mathrm{NU7}}}$ commits, as the first input of its block commitment hash, to the completed tree of the NU6.3 upgrade epoch, hashed under the NU6.3 branch ID $\mathtt{0x37A5165B}$ by the adopted reading of Definition 6.9. The block $B_{A_{\mathrm{NU7}}+1}$ commits to a new tree over $B_{A_{\mathrm{NU7}}}$ , hashed under the NU7 branch ID $\mathtt{0x77190AD9}$ (ZIP 259, Draft) with the field vector of Definition 6.5 for the NU7 upgrade epoch.

Proof.

The instance $A=A_{\mathrm{NU7}}$ of Theorem 6.24, NU6.3 being the upgrade that precedes NU7 (Definition 1.1), with the constants of ZIP 259, “NU7 network constants”, and ZIP 258, “NU6.3 deployment”. □