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.
ZIP 221 (Final), “FlyClient - Consensus-Layer Changes”, changes the semantics of the block header and the consensus rules from Heartwood. The -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 to are ZIP 221’s; fields to 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).
Let
For a block height
leaves
The epoch tree is an instance of Definition 3.19 under . Every node of it, leaf, internal node, bagging node or root, carries one node vector of fields, serialised canonically by the map 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 with header , the leaf map sets both members of each earliest/latest pair from itself:
field is (Definition 2.3), in internal byte order and unpersonalised;
fields and are the field of ;
fields and are the field of (the semantics of and : Consensus Guide, §“Difficulty adjustment”);
fields and are for the root of the Sapling note commitment tree of the final Sapling treestate of (protocol specification, §“Block Header Encoding and Consensus”), an opaque -byte value in this volume;
fields and are the height ;
field is the number of transactions of in which or is non-empty;
fields and are the Orchard-pool anchor of , the root of the Orchard pool’s note commitment tree in the final treestate of (Ironwood Guide, §“Anchors”, Definition “Treestate and anchor”);
field is the number of transactions of in which is non-empty (Ironwood Guide, §“The transaction format”);
fields , and are the Ironwood-pool anchor of and the number of its transactions in which is non-empty, computed as fields to .
The parent rule: an internal node with left child and right child takes each earliest field (, , , , , ) from and each latest field (, , , , , ) from ; it sums the additive fields, field modulo and the per-pool counts , and in ; and it sets field by Construction 6.10, the personalised hash of . Fields to are ZIP 221’s own, added at NU5 (ZIP 252). Fields to are ZIP 258’s, “Changes to ZIP 221” (Draft), whose rules apply from NU6.3 activation (Definition 1.2).
For field , ZIP 221, “Tree Node specification”, states that computations modulo are fine because cumulative chain work is assumed to be at most , an aggregate effort of or more being infeasible; under that assumption, with the total below , 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 | Internal node | ZIP | |
|---|---|---|---|---|---|
| char[32] | hash | 221 | |||
| uint32 | inherit left | 221 | |||
| uint32 | inherit right | 221 | |||
| uint32 | inherit left | 221 | |||
| uint32 | inherit right | 221 | |||
| char[32] | final Sapling root | inherit left | 221 | ||
| char[32] | final Sapling root | inherit right | 221 | ||
| uint256 | work of the block | sum mod | 221 | ||
| CompactSize | height | inherit left | 221 | ||
| CompactSize | height | inherit right | 221 | ||
| CompactSize | transactions with Sapling spends or outputs | sum | 221 | ||
| char[32] | Orchard-pool anchor | inherit left | 221 | ||
| char[32] | Orchard-pool anchor | inherit right | 221 | ||
| CompactSize | transactions with Orchard-pool Actions | sum | 221 | ||
| char[32] | Ironwood-pool anchor | inherit left | 258 | ||
| char[32] | Ironwood-pool anchor | inherit right | 258 | ||
| CompactSize | transactions with Ironwood-pool Actions | sum | 258 |
ZIP 221, “FlyClient Requirements and Recommendations”, designates seven
fields, to and to , 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 of the difficulty
MMR, is
Fields , and to are ZIP 221’s “Non-FlyClient Commitments”, chosen “primarily to improve light client security guarantees”, with no counterpart in ePrint 2019/226. Field “forms the structure of the commitment tree” (ZIP 221, “Tree nodes”), and fields to 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 serves the purpose of the former header field , 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 to ) and at NU6.3 (fields to , ZIP 258).
The fields are encoded as follows: a char[32] field as its bytes; a uint32 or uint256 field little-endian, as or (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 of the root, as the specification encodes the Orchard anchor (protocol specification, §“Transaction Encoding and Consensus”). For a node , is the concatenation of the encodings of its fields in field order. The field vector of an upgrade epoch is:
fields to in the Heartwood and Canopy upgrade epochs;
fields to in the NU5, NU6, NU6.1 and NU6.2 upgrade epochs;
fields to in the NU6.3 and NU7 upgrade epochs.
The vectors are named by their fields. ZIP 221, “Tree Node specification”, omits fields to “before NU5 activation”, and ZIP 258, “Changes to ZIP 221”, omits fields to “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 uses the field vector of the upgrade epoch beginning at , the upgrade epoch of its leaves.
The reading is adopted for the following reason. Under the other reading the tree committed by , at an activation height that adds fields, would serialise every node of the previous upgrade epoch with the added fields; every internal node would change value, and would not be an append of , 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: uses the previous upgrade epoch’s vector, and is the first tree with the new one; under the other reading 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 to under either reading.
The fixed-width fields occupy , and bytes in the three vectors, and the three, four and five CompactSize fields to bytes each, so a serialised node has to , to and to 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.
Every node of , bagging nodes included, spans a run of
consecutive leaves
By induction on the parent rule of Definition 6.3. A leaf
has both heights equal to its block’s. An internal node inherits
from its left child and
from its right child, and in a range under the run of the
left child immediately precedes that of the right child, the heights of the
leaves of being consecutive by
Definition 6.2. A perfect subtree of altitude spans
leaves (Definition 3.1), and every node inside a peak roots a
perfect subtree. A bagging node of the left fold spans the peaks
For
Consensus bounds the field of a block below, strictly above
the median of the timestamps of the preceding eleven blocks, and above, by
that median plus minutes (protocol specification, §“Block Header
Encoding and Consensus”; Consensus Guide, §“Difficulty adjustment”). 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
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.
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
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 would not be an append of the tree committed by , 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 .
Let be BLAKE2b-256 with the -byte personalisation on input (Ironwood Guide, §“Transaction digests and signatures”; Crypto Guide, §“Domain separation and personalisation”), and let be the -byte little-endian encoding of . The personalisation is the ASCII bytes ZcashHistory followed by , bytes in all. The tree is the range 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,
are ordinary internal nodes, and a single peak is the root node. For an internal node with children and , field is
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 by Definition 6.9, the upgrade epoch being fixed by the node’s heights. For the Heartwood branch ID the last four bytes of the personalisation are .
| Upgrade epoch | Branch ID | Fixed by | Bytes to of the personalisation | Fields |
|---|---|---|---|---|
| Heartwood | ZIP 250 | to | ||
| Canopy | ZIP 251 | to | ||
| NU5 | ZIP 252 | to | ||
| NU6 | ZIP 253 | to | ||
| NU6.1 | ZIP 255 | to | ||
| NU6.2 | ZIP 257 | to | ||
| NU6.3 | ZIP 258 (Draft) | to | ||
| NU7 | ZIP 259 (Draft) | to |
For
with encoding (ZIP 221, “Tree Node
specification”). It is not field of the root node: the committed value
covers the root’s aggregates, namely the total work modulo , the
first and last timestamps, target bits and heights, the boundary pool roots
and the per-pool counts. When
For
The value at 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 on, and it is the value that ZIP 244, “Block Header Changes”, names “hashLightClientRoot (as described in ZIP 221)”.
Let and be epoch trees hashed under one branch
ID . If
The proposition is the ZIP 221 instance of Lemma 3.20(1), whose hypotheses are checked as follows. Serialisation. The branch ID 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: 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 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 and , hence equal leaf count by Lemma 6.6, hence the same shape . 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 ). Extraction. Lemma 3.20(1) then yields a collision at the first level of disagreement. Headers. Field 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. □
Let a node of 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, , and where present and , equal the numbers of transactions in the blocks of the height range of in which or , and , 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.
By Lemma 3.20(2), an accepted path binds the full vector of every node it recomputes and of every sibling it carries, so 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 is its sum over the leaves of ’s height range. The reading as detection of withholding is ZIP 221, “Non-FlyClient Commitments”. □
For branch IDs
with probability at most . Hence no internal-node hash or root commitment computed under equals one computed under , except with that probability. Leaves are unpersonalised block hashes, identical in every branch, and are not separated.
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 pairs of such queries agrees with probability , 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”. □
The header field (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- or version- 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 does not commit to the authorising data; the identifier of a version- transaction covers its whole encoding. The version- format is valid until NU7, from which ZIP 2003 (Draft), deployed by ZIP 259 (Draft), makes it invalid.
Let a block have the transactions
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 transactions have equal and
equal . Then the lists are equal, or a collision
of SHA-256d, of
For fixed , 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
In this subsection denotes the string of zero bytes.
For a block at a height in or after the NU5 upgrade epoch, the block commitment hash is
with the history input of
Definition 6.12, the
root of Construction 6.16 for , and the
terminator (ZIP 244, “Block Header Changes”). The input has
From NU5 the chain-history root appears in no header. Let be the value
of a block in or after the NU5
upgrade epoch. A verifier given a claimed history input , or a claimed
root node vector from which it computes
only the -byte value of is needed, not its
tree. Two distinct accepted pairs
The pair is accepted by Definition 6.18. The input has fixed length, so distinct pairs give distinct inputs, and two accepted pairs with equal image are a collision. □
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 “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.
The -byte header field that follows (Definition 2.3) is named before Sapling, in the Sapling and Blossom upgrade epochs, in the Heartwood and Canopy upgrade epochs, and 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.
For a block the commitment field satisfies the following rules.
For
For
For in or after the NU5 upgrade epoch, the NU5 activation block included and without sentinel, it MUST equal 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 , the NU5 activation height, the history input is , the root of the completed tree of the Canopy upgrade epoch. It is hashed under the Canopy branch ID (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 to 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.
For
Let
commits to the complete tree over
commits to the single-leaf tree over ;
for
the reset occurs at every upgrade, including those that leave the field vector unchanged (Canopy, NU6, NU6.1, NU6.2 and NU7).
By the definition of ,
Figure 4 shows the ranges of the theorem.
The height is an activation height below every
Let be the NU7 activation height. The block 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 by the adopted reading of Definition 6.9. The block commits to a new tree over , hashed under the NU7 branch ID (ZIP 259, Draft) with the field vector of Definition 6.5 for the NU7 upgrade epoch.