This final section constructs, from the collision-resistant hash of §3 alone, the Merkle tree: a short commitment to a list of values with membership proofs of logarithmic size. It proves, by reduction to collision resistance, that the root is binding—no party can publish one root and later open it to two different lists (equivocation)—and that membership proofs are sound—no party can prove membership of a value absent from the committed list, which in a payment system would spend a note the ledger never recorded (Proposition 10.5, Theorems 10.12 and 10.25). It constructs the append-only tree of a shielded pool, updated in logarithmic time (Proposition 10.20), and makes membership private by hiding the path from leaf to root in a zero-knowledge argument of §9: an observer of an honest proof learns nothing about which member it concerns, information that would trace every coin (Theorem 10.29). The commitments of §4 are the leaves, and the algebraic hashes of §3 and §4 compute the internal nodes; the section ends with an Orchard shielded spend assembled end to end.
A prover holds a large collection of values—transactions in a block, public keys in a directory; in this volume, the growing set of note commitments of a shielded payment system. A verifier must be convinced of two statements about it without storing it or seeing most of it.
Membership. “Value occurs at position of the list”—or, forgetting the position, “ belongs to the set.”
Integrity. “The collection is exactly the one committed to earlier, unaltered.”
Both are served by a single short commitment that determines the whole collection and short membership proofs, where “short” means of size independent of the number of elements, or at most logarithmic in it: integrity becomes one comparison, and membership a small certificate sent with the value. The Merkle tree, due to Ralph Merkle, achieves this from a collision-resistant hash function alone. It is the membership mechanism of Orchard: every shielded spend proves, against a published root, that some note commitment lies in the tree.
Notation follows §3.1: is the set of finite binary strings, the strings of length exactly , concatenation, and the security parameter. All algorithms are PPT in , and denotes a negligible function (Math Guide, §“Polynomial, exponential, and negligible functions”).
The tree uses a single primitive, recalled in the keyed form in which its security is a meaningful asymptotic statement.
Let
taking two digests to one.
The key models the choice of a concrete function from a family. For a single fixed function a colliding pair exists and some small program outputs it (the hardcoded-collision triviality discussed in §3.1), so only the keyed formulation admits a non-trivial quantification over adversaries. Deployments use a fixed standardised function or, inside arithmetic circuits, an algebraic hash in the sense of §3.8 and §4.8; we suppress and write and .
The tree needs collision resistance (Definition 3.7,
§3.2): given the key , every PPT adversary
outputs
Fix a two-to-one compression function
| (3) |
Level has nodes, and is the -th
node from the left at level . The unique level- node is the
root:
With
and the root
The single -bit root depends on the whole list of four -bit strings.
A list whose length is not a power of two is handled by fixing
the depth with
That the root commits to the list is a security property, stated as a game in the style of Definition 1.15.
The Merkle commitment to a list of leaves is
The challenger samples
The adversary outputs two lists
The game outputs iff
The commitment is binding if every PPT adversary wins with probability .
If is collision resistant, the Merkle commitment is binding.
Concretely, there is a deterministic procedure that, from any two
distinct equal-length lists
Build both trees. The lists differ at some leaf index , so
in both trees. The labels differ at level and agree at level
—the common root—so there is a smallest level at
which they first agree: with
since one of the two children at level
while the two -bit inputs differ in at least one half: a collision for , located after at most comparisons along one path. The reduction built on this extractor runs the adversary once and extracts whenever it wins, so collision resistance forces the winning probability to be negligible. □
Membership needs a certificate relating one leaf to the root: the siblings along the leaf’s path, which are exactly the data needed to recompute the root from the leaf.
Let a depth- tree over be given, and let be a leaf
index,
where is the label of the sibling of the level-
node on the path. Explicitly, with
The path has exactly entries.
The verifier , on a root
, an index , a claimed leaf value
| (4) |
Accept iff
For every list , every index , and the genuine authentication path for in the tree over ,
The index-consistency check passes by construction, the genuine path
carrying exactly the bits of . We show by induction on
that
An authentication path in a depth- tree consists of
sibling labels and direction bits,
One sibling label, one direction bit, and one compression per level, over the levels above the leaves. □
For a set of a billion elements,
Continue Example 10.3, and prove membership of
at index
Verification folds upward:
and the verifier accepts. The verifier never receives or , only their digest , and is nevertheless convinced that occupies index of the committed list. Figure 16 draws this path.
Soundness states that, against an honest root, a path for a value other than the genuine leaf verifies only with negligible probability.
Fix a list of leaves with root
The challenger samples
The adversary outputs an index and a pair .
The game outputs iff
A winning output is a path forgery at index : the verifier accepts, against the honestly computed root, a leaf value different from the genuine one at position .
Let be collision resistant. Then no PPT adversary, given the
list and the whole tree, produces a path forgery except with
probability . In constructive form: there is a
deterministic extractor that from any list , index , and
accepting forgery with
Run the verifier’s fold (4) on
, obtaining the chain
The two chains disagree at the bottom,
exists, and
where is the sibling claimed in and the genuine sibling. Then
the inequality because the two preimages differ in the half occupied
by the running value. The pair is a collision for
, found deterministically in work once the genuine
chain is at hand—a read-off from the built tree, or
If a PPT adversary produces path forgeries with
probability , the collision finder
that receives the key, samples or receives , runs
, and applies the extractor outputs a collision whenever
succeeds—hence with probability
, at an overhead of building the tree over
, which does in any case to play the challenger,
plus one verifier run and comparisons. Collision resistance
of therefore forces
Theorem 10.12 is a statement about a fixed honest root: relative to a root that genuinely is , the only leaf value admitting an accepting path at position is , up to a collision in . It does not prevent an adversary free to choose the root from committing to a maliciously crafted tree; binding (Proposition 10.5) rules that out. With an untrusted party supplying the root, both properties are necessary: binding ensures the root determines at most one list, and path soundness ensures openings are faithful to it. The vector-commitment theorem of §10.8 establishes both by a single argument.
The soundness theorem does not cover the following structural
confusion. Suppose the leaves are arbitrary-length data, hashed into
by the same function used internally. Then an
internal label is itself a well-formed leaf value—it
has the right length. An adversary presents the internal node
The remedy applies the domain-separation discipline of §3.5 within a single structure.
A Merkle construction has domain separation if the function applied at distinct structural positions is forced to differ, by prepending a position-dependent tag to every hash input. Concretely, from a variable-input-length hash define
where the byte tags and distinguish the layer kind—leaf versus internal node—and is a fixed-length encoding of the level index, distinguishing internal nodes by depth. The tree recurrence becomes
and the verifier’s fold applies the same tagged functions at the same positions.
With the tagging of Definition 10.14, any collision extracted by the binding proof (Proposition 10.5) or the soundness proof (Theorem 10.12) is a collision for between two inputs sharing the same leading tag: a leaf preimage against a leaf preimage, or a level- node preimage against a level- node preimage. In particular, no accepting forgery can substitute an internal node for a leaf, or a node at one level for a node at another, without exhibiting a within-domain collision of —which collision resistance forbids.
The extractors of both proofs locate the smallest level at which two
disagreeing computations agree, and collide the two preimages of the
compression call at that position. Under the tagged recurrence, the
verifier’s recomputation applies the position’s prescribed function
exactly as the honest tree does: at the leaves both preimages pass
through , at level
The handling of lists whose length is not a power of two has failed in deployment. Bitcoin’s transaction Merkle tree handles an odd level by duplicating its last node before hashing pairwise, and the duplication rule is not injective: a list of transactions and the same list with its tail duplicated can yield the same root. This is CVE-2012-2459, a consensus-splitting vulnerability—an attacker could present two different transaction lists sharing a root, one valid and one invalid, and nodes could be made to cache the invalid one as permanently rejected (documented in Zebra: the zebra-chain crate reproduces the upstream warning that the flawed algorithm must not be reused, and the deployed defence in zebra-consensus rejects any block whose transaction hashes are not unique). The failure yields three general rules. First, layer-separate leaves from internal nodes, as Definition 10.14 prescribes. Second, make every padding or duplication rule injective on admissible lists—for instance by binding the true leaf count into the root’s computation. Third, feed only fixed-length inputs, so that no length-extension structure of the underlying hash (§3.5) can intervene between layers.
When the Merkle path is verified inside a zero-knowledge circuit
(§10.9), arithmetic gates over evaluate the
compression function, and the choice of dominates the cost. A
bit-oriented hash such as SHA-256 costs tens of thousands of
constraints per call; one therefore uses an algebraic hash
with compression
Orchard’s Merkle hash retains the tag
mechanism of Definition 10.14 in encoded form. Each
internal call prepends to the two -bit child encodings the
-bit little-endian encoding of
The set of note commitments of a shielded pool only grows, one leaf at a time. Rebuilding a depth- tree on every insertion would cost hashes; the frontier defined below permits the update in hashes and state.
Fix a maximum depth , giving capacity , and the
level-indexed functions of
Definition 10.14. Leaf values here enter as
level- labels directly, with no : the
leaves are already digests, and the fixed depth together with the
level tags (Remark 10.17) carries the layer
separation—the convention of deployed Orchard, whose leaf is the
extracted coordinate itself (Example 10.31). An
append-only (or incremental) Merkle tree
maintains a position counter —the number of leaves inserted so
far,
The root after appends, written , is the root of the depth- tree, under this recurrence, whose first level- labels are the inserted values and whose remaining ones are .
The frontier of an append-only tree holding leaves is
the minimal state needed to (i) compute the current root and (ii)
update incrementally on the next . For each level
The binary representation of decomposes the inserted leaves into
completed perfect subtrees of distinct heights, one of height for
each set bit , and the frontier holds exactly their roots. An
append is the Merkle analogue of incrementing a binary counter: a carry
at level combines two height- subtrees into one of height
From the frontier of an append-only tree holding
The algorithm is carry propagation followed by an upward fold. Set
the running label
To obtain , fold upward from level with
the just-deposited as the running value—it is the path
label at level , not a sibling. For
Take depth
After ,
After ,
After ,
Each append touched only the carry chain to the new leaf, never the whole tree. (The trace involves no numeric hash values and follows mechanically from the algorithm of Proposition 10.20; the volume’s companion script replays it symbolically and checks the occupied frontier levels against the set bits of at every step.)
Appending changes the root; the following definition fixes the root against which a proof is valid.
An append-only tree is history-binding when the surrounding protocol treats every historical root as an acceptable commitment in its own right: each membership proof verifies against the root it was formed for, and appending further leaves never invalidates a previously valid triple for that root. The soundness of each individual proof is exactly Theorem 10.12 applied to the corresponding fixed root.
Deployed Orchard is history-binding by construction. The root of the
note-commitment tree at the end of each block is an anchor, and
a spend may prove membership against any historical anchor:
consensus requires the anchor named by a transaction to be the root
of the Orchard note-commitment tree as it stood at the end of some
earlier block (protocol specification
§ 3.7, ‘Action
Transfers and their Descriptions’). The deployed representation of the
growing tree, the newest leaf with its left siblings on the path to
the root, is equivalent to the frontier. When is odd these
labels are exactly the carries of Definition 10.19.
When is even, with lowest set bit
Deletion or in-place update could be supported at per operation, given the relevant siblings; the restriction to appends is a design choice, made for monotonicity. Once a leaf is inserted it is never removed, so a membership proof valid against the root at insertion time remains valid against that historical root forever. A shielded pool requires this property: a note, once added, can be spent later by proving against some past anchor, without the spender following the current root as other parties’ insertions change it. The cost falls on the verifier, which must accept a window of historical roots rather than a single current one; in the deployed protocol that window is the set of recorded anchors.
The Merkle construction instantiates the following abstraction: a commitment to an ordered vector that opens one position at a time. Its unordered counterpart, the cryptographic accumulator, certifies set membership with no notion of position; Orchard does not use it, since notes occupy positions and the position is part of the spend circuit’s witness.
A vector commitment is a tuple of PPT algorithms :
The scheme is correct if honest openings always verify, and
succinct if and are bounded by a
fixed polynomial in and . It is
position-binding if every PPT adversary wins the following
game with probability : given , the
adversary outputs and wins iff
Instantiate the syntax by: samples (and
fixes with
Correctness is completeness
(Proposition 10.8), and the size bounds are
Proposition 10.9. For position-binding, suppose an
adversary outputs two accepting openings and
at the same index under the same root ,
with
The two theorems serve different verifiers. Path soundness (Theorem 10.12) fixes an honest root and forbids opening a position to anything but its true value, for a verifier that trusts the origin of the root. The vector-commitment theorem (Theorem 10.25) forbids opening a single position two different ways even under an adversarial root, for a verifier that received the root from an untrusted source; it expresses the intended meaning of “commitment”: a commitment determines at most one value per position, whoever produced . Both proofs collide two chains at their first level of agreement, forged against genuine in the first case and forged against forged in the second.
The membership proof of §10.4 is succinct but not private: it discloses the leaf value (here, the note commitment being spent) and its index , and the sibling labels can leak structural information about the neighbourhood of the leaf. An observer correlating spends with the appends that created their leaves would link payments end to end. The remedy proves the existence of a valid path in zero knowledge, with the entire path a private witness and only the root public.
For the domain-separated Merkle construction of depth , with leaves entering as level- labels under the convention of Definition 10.18, define
with the statement the public root and the witness comprising the leaf , its index , and the authentication path . A zero-knowledge argument for lets a prover convince a verifier that some leaf lies in the tree with root while revealing none of , , or . We assume a zk-SNARK as §9 develops it (Definition 9.25): completeness (honest provers convince), knowledge soundness (an accepting prover “knows” a witness, formalised by an extractor), and zero knowledge (the proof reveals nothing beyond the truth of the statement, formalised by a simulator).
The Merkle-path circuit of depth takes as
public input the root , and as private (witness)
inputs the leaf , the direction bits
Let be collision resistant and let be a zk-SNARK for —equivalently, for satisfiability of . Then the protocol “the prover sends a SNARK proof for the statement ; the verifier checks it” is a membership argument that is:
complete: a prover holding a genuine leaf and its path produces an accepting proof;
sound: any prover producing an accepting proof for an
honest root
private: the proof reveals nothing about , , or beyond the fact that some valid leaf exists under .
Completeness composes SNARK completeness with tree completeness
(Proposition 10.8): the genuine
satisfies , and the honest
prover proves it. Soundness composes the SNARK knowledge extractor
with the path-forgery-to-collision extractor of
Theorem 10.12: from an accepting prover, the
SNARK extractor produces accepted by
; if
In the root must be public so that the verifier checks the proof against a state everyone agrees on—a previously published note-commitment-tree anchor—and soundness is relative to that public root, as Remark 10.13 delimits. The path must be private so that observers cannot link the spend to a particular leaf. SNARK succinctness adds a third property: the verifier checks a proof whose size is essentially independent of —polylogarithmic—even though the witness contains siblings, so the construction compresses the membership proof as well as hiding it.
Deployments differ in where they bear the cost of that verification. Pairing-based schemes such as KZG (§4.9) achieve constant-size proofs with fast verification, at the price of a trusted setup. Halo 2’s IPA-based proofs grow logarithmically in size, but their verification is linear in the circuit size; the deployment amortises it by batch-verifying many proofs in a single multiexponentiation. The accumulation technique of the Halo lineage—which would make per-proof verifier work sublinear by deferring the linear check across recursively composed proofs—is not deployed: each Orchard proof is verified, in batch, directly.
This subsection composes the constructions of the volume into an Orchard shielded spend; every primitive it uses is constructed in this volume, and the description follows deployed Orchard.
Each shielded output of a transaction appends a note commitment —itself a hiding, binding Sinsemilla commitment to the note’s value, recipient, and randomness (§4.8)—as a leaf of an append-only Merkle tree built with the Sinsemilla compression function of Remark 10.17. Strictly, the leaf is the extracted -coordinate
a -bit Pallas base-field element (Math Guide, §“Pallas and Vesta assembled”) matching the child encodings of Remark 10.17. The tree as it stands at the end of each block has a root, and a transaction names one such root of an earlier block as its anchor (protocol specification § 3.7).
To spend a note, its owner:
locates the leaf in the public tree and reads off its authentication path and position ;
chooses a recent anchor
proves in zero knowledge, per Theorem 10.29, the statement with witness : membership of the note commitment under the anchor, well-formedness of the note opening, and correct derivation of a nullifier—a deterministic tag whose on-chain uniqueness prevents double-spending, computed from the note and the spender’s nullifier key on of §3.8 by a construction of a later volume (the recomputed root is constrained to equal the public anchor, and the instance carries the anchor and the nullifier; protocol specification § 4.9, ‘Merkle Path Validity’, and § 4.18.4, ‘Action Statement’);
publishes the proof and the nullifier—but neither , nor , nor .
By Theorem 10.29, the spend convinces the network that the spender owns some note genuinely added to the tree—soundness resting on the collision resistance of Sinsemilla (Proposition 4.30) and the knowledge soundness of the proof system—while the network learns nothing about which note. (In the deployed circuit the root-equals-anchor constraint is enforced for notes of nonzero value, while zero-valued dummy spends may witness an arbitrary path—by design, so that every action carries a spend whether or not a real note backs it.) The Merkle root is thus a succinct, binding, privacy-preserving commitment to the set of all notes ever created.
In the spend, the note commitment is the hiding and binding commitment of §4; the tree hash and its personalised domains apply the domain-separation discipline of §3, instantiated by Sinsemilla; the nullifier is derived from a PRF of §5 instantiated by Poseidon; the proof is a zk-SNARK of §9 for the relation extended with the note’s opening; and the authorising signatures over the spend—re-randomised RedDSA for spend authority, the binding signature for value balance—are those of §8. How the pieces sit inside a transaction, per Action, with the key hierarchy and note-delivery encryption around them, is treated in a later volume of the series.