The adversary of this final section tells lies about a set. Her first lie is inclusion: she claims that a value sits in a committed collection it never entered—a payment out of thin air, spent against a ledger that never recorded it. Her second lie is equivocation: she publishes one short commitment and later produces two different collections that both explain it, so that the commitment pinned down nothing. Her third role is not a lie but a gaze: as an observer she watches an honest member prove that it belongs, and learns which member spoke—enough, in a payment system, to trace every coin. This section defeats all three with a single construction, built from nothing beyond the collision-resistant hash of §3, and closes the volume by spending everything the earlier sections banked: the commitments of §4 become the leaves, the algebraic hashes of §3 and §4 become the internal nodes, and the zero-knowledge arguments of §9 hide the path from leaf to root.
The plan runs from public to private. We first fix the two statements a verifier might want proved about a large collection, and recall the compression function and its collision game. The binary Merkle tree follows, with its root as a binding commitment to the whole list; a worked depth-two tree keeps every index honest. Authentication paths then give logarithmic-size membership proofs, complete and sound; the soundness proof introduces the one technique this section reuses until the end—extracting a hash collision from the first level at which two disagreeing computations agree. Layer and domain separation keep that extraction honest against structural confusion between leaves and nodes, with a deployed failure as the cautionary tale. Append-only trees and the frontier make the structure grow in logarithmic time; the vector-commitment abstraction names exactly what the root achieves; and zero-knowledge paths convert the public proof into a private one. The capstone assembles an Orchard shielded spend end to end.
The setting is asymmetric. A prover holds a large collection of values—transactions in a block, public keys in a directory, records in a log; for this volume, the ever-growing set of note commitments in a shielded payment system. A verifier wants conviction about that collection without storing it, indeed without ever seeing most of it. Two statements cover the uses that matter here.
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.”
What is wanted is a single short commitment that determines the whole collection, together with short membership proofs: “short” meaning of size independent of the number of elements, or at worst logarithmic in it. A commitment of that shape makes integrity a one-comparison check, and membership a small certificate that travels with the value it certifies. The construction achieving this—the Merkle tree, due to Ralph Merkle—needs nothing more than a collision-resistant hash function, and it is the membership backbone of Orchard: every shielded spend proves, against a published root, that some note commitment lies in the tree.
Notation is as fixed in §3.1 and carried throughout the volume: 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 consumes one ingredient, which we recall in the keyed form that makes its security a meaningful asymptotic statement.
Let be a keyed hash family exactly as in Definition 3.2: a key is sampled publicly at random and fixed, the digest length is , and is the family member in force. When the input length is restricted to a fixed multiple of the output length, the family is a compression function; a two-to-one compression function has signature
taking two digests to one.
The key models the choice of a concrete function from a family, which is what rescues collision resistance from the hardcoded-collision triviality discussed in §3.1: for a single fixed function a colliding pair exists and some small program outputs it, so only the keyed formulation supports a clean quantifier. In practice one deploys a fixed standardised function—or, inside arithmetic circuits, an algebraic hash in the sense of §3.8 and §4.8—and we suppress from the notation, writing and plain.
The security property the tree needs is collision resistance, exactly as in Definition 3.7 (§3.2): the game hands the adversary the key , the adversary outputs a pair , and it wins if while ; the family is collision resistant if every PPT adversary wins with probability . This is the strongest of the three classical hash notions (Proposition 3.8), and the generic birthday attack caps an -bit digest at bits of collision security (Lemma 3.11)—whence the -bit outputs used at the -bit level here. Merkle trees require full collision resistance, not merely second-preimage resistance, for a reason the soundness theorem (Theorem 10.12) makes exact: the party who assembles the tree may itself be the adversary, choosing every leaf, which is precisely the both-inputs-adversarial regime that Remark 3.10 assigns to collision resistance.
The construction hashes the collection pairwise, level by level, until one digest remains.
Fix a two-to-one compression function , a depth , and an ordered list of leaf values in . The Merkle tree of depth over is the complete binary tree with leaves whose nodes carry labels in , defined level by level from the leaves (level ) to the root (level ) by
| (3) |
Level has nodes, and is the -th node from the left at level . The unique level- node is the root: .
With and leaves , the tree has seven nodes: the four leaves, the two level-one nodes
and the root
The single -bit root summarises the whole list of four -bit strings; the example carries through the next two subsections.
A list whose length is not a power of two is handled by fixing the depth with and padding the remaining leaf slots with a canonical value—the all-zero string, say, or the hash of the empty string. Padding must not create ambiguity: two different lists must never yield the same padded leaf sequence, else the root fails to determine the list before any cryptography is consulted. Binding the true length into the root’s computation—one further compression of the top node with an encoding of —removes any such ambiguity. An alternative is the unbalanced tree, in which a node with a single child passes its child’s label upward unchanged; it is convenient but subtle, and we return to it alongside second-preimage attacks in Remark 10.16.
The root is short; the claim that it commits to the list is a security property, stated as a game in the tradition of Definition 1.15.
The Merkle commitment to a list of leaves is . The game runs as follows.
The challenger samples , fixing the compression function , and sends to the adversary.
The adversary outputs two lists , each of leaves in .
The game outputs iff and .
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 with , extracts a collision for in time linear in the tree size—one root-to-leaf walk of hash comparisons. The reduction is tight: an adversary winning with probability yields a collision finder succeeding with the same probability .
Build both trees. The lists differ at some leaf index , so , writing and for the labels of the two trees. Follow the leaf-to-root path
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 is the path node, at which the labels still disagree by minimality of . By the recurrence (3),
while the two -bit inputs differ in at least one half: a collision for , located after at most comparisons along one path. The reduction wrapping this extractor runs the adversary once and extracts whenever it wins, so collision resistance forces the winning probability to be negligible. □
The proof’s engine deserves its name now, because the section reuses it almost verbatim twice more: a discrepancy at the leaves and agreement at the root must, by this pigeonhole-like descent, manifest a collision somewhere on the path between them. There is a smallest level at which two disagreeing computations agree; the compression call producing that first agreement has two differing preimages. All three security theorems of this section are this one sentence wearing different inputs.
The root alone certifies integrity; membership needs a certificate relating one leaf to the root. The certificate is the list of siblings along the leaf’s path upward—everything the verifier needs to recompute the root from the leaf, and nothing more.
Let a depth- tree over be given, and let be a leaf index, , with binary expansion , so that bit records whether the level- node on the leaf-to-root path is a left child () or a right child (). The authentication path (also Merkle proof or membership witness) for index is
where is the label of the sibling of the level- node on the path. Explicitly, with the path node’s index at level ,
The path has exactly entries.
The verifier , on a root , an index , a claimed leaf value , and a path , proceeds in two stages. First the index-consistency check: reject unless, for every , the bit carried in equals bit of the binary expansion of . Then set and fold the path upward: for ,
| (4) |
Accept iff . We call the root recomputed from . The bit places the running value on the side matching the argument order of the tree-building recurrence: a left child is hashed on the left.
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 , the label of the level- node on the leaf-to-root path. The base is . For the step, the level- path node and its sibling are precisely the two children of the level- path node, and the fold (4) places on the side dictated by with on the other side—reproducing exactly the two arguments of in the recurrence (3), so . At this reads , and the verifier accepts. □
An authentication path in a depth- tree consists of sibling labels and direction bits, bits in all, and verification performs exactly evaluations of . Choosing the minimal sufficient depth for a list of leaves (any suffices) yields proofs of bits—logarithmic in the length of the list.
One sibling label, one direction bit, and one compression per level, over the levels above the leaves. □
The concrete scale is worth pausing on. For a set of a billion elements——a membership proof consists of hash values and direction bits. With a -bit hash the sibling labels occupy bits, which is bytes; direction bits included, bytes—under a kilobyte, however the billion elements are arranged. (The byte counts are the output of the volume’s companion script.) This logarithmic succinctness is the central objective: the verifier’s storage is one digest, the certificate fits in a packet, and neither grows meaningfully as the set does.
Continue Example 10.3, and prove membership of at index , so and . At level the path node is a left child, with sibling . At level the path node is a right child, with sibling . The path is
Verification folds upward: , then , and the verifier accepts. Note what the verifier never saw: neither nor themselves, only their digest —yet it is convinced that sits at index of the committed list.
Completeness says honest paths verify; the security question is whether dishonest ones can. The threat is the inclusion lie of the section’s opening: an adversary who convinces the verifier, against the genuine root, that position holds a value it does not.
Fix a list of leaves with root . The game runs as follows.
The challenger samples to fix , builds the tree over , and sends together with —equivalently, the whole tree—to the adversary.
The adversary outputs an index and a pair .
The game outputs iff and .
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 outputs a collision for , in time linear in the tree size—recomputing the genuine leaf-to-root labels from dominates; given the built tree, one verifier run plus a level-by-level comparison, work in all, completes the extraction.
Run the verifier’s fold (4) on , obtaining the chain (the final equality because the forgery is accepting). Alongside it place the genuine chain , the labels of the leaf-to-root path in the honest tree; by the induction of Proposition 10.8 this is the chain the fold produces on the genuine inputs, and .
The two chains disagree at the bottom, , and agree at the top, . Hence
exists, and by minimality. Because the forgery is accepting, the index-consistency check of Definition 10.7 forces the direction bits carried in to equal the bits of —the same bits the genuine path carries—so at level both chains place their running value on the same side of the compression call: both compute if , both if . Form the two -bit preimages accordingly,
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 hashes from the bare list . □
The reduction wrapping the extractor is immediate. 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 , and the reduction is tight: no advantage is lost in the translation.
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 by itself prevent an adversary who is free to choose the root from committing to a maliciously crafted tree; that threat is what binding (Proposition 10.5) rules out. With an untrusted party supplying the root, both properties are necessary and they divide the labour cleanly: binding ensures the root determines at most one list, and path soundness ensures openings are faithful to it. Together they make the root a sound, binding commitment with succinct openings—the abstraction §10.8 names, where a single argument will deliver both faces at once.
The soundness theorem has a structural blind spot, inherited from an innocent-looking convenience. 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—and one string can play both roles. An adversary exploits the ambiguity directly: she presents the internal node as if it were a leaf near the top of a shallower tree, equipped with the correspondingly shorter authentication path, and a verifier who does not know the depth accepts. The root now has a second list explaining it—a genuine second-preimage attack, with no collision of anywhere in sight. Absent a way for a label to assert “I am a leaf” or “I am an internal node”, the leaf-to-root structure that Theorem 10.12 relies on collapses.
The repair is the domain-separation discipline of §3.5, applied within a single structure: distinct structural positions get distinct tags.
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 both pass through . Both colliding preimages therefore begin with the same tag—, or —and the collision lies within a single domain. A cross-domain confusion, by contrast, would require two inputs with different leading tags and equal -images, which is again an -collision; either way the adversary has broken collision resistance, and the shallower-tree attack above is foreclosed because a leaf preimage and a node preimage can no longer be the same string. □
The subtleties are not hypothetical. 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 at length in Zcash’s inherited validator: zebra-chain crate, src/block/merkle.rs, which reproduces the upstream warning that the flawed algorithm must not be reused; the deployed defence—rejecting any block whose transaction hashes are not unique—lives in zebra-consensus, src/block/check.rs). The lesson generalises to three 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 . Poseidon (§3.8) is a low-degree permutation-based map computable in few constraints; Sinsemilla (§4.8) is cheap in constraints through lookups and incomplete curve additions, not through low degree. For Poseidon, layer and domain separation come not from byte tags but from distinct field constants—initial capacity values or round constants—fed into the permutation; the tree’s security argument is identical, with “collision” read as a collision of the field-valued compression function.
Orchard’s Merkle hash retains the tag mechanism of Definition 10.14 in encoded form. Each internal call prepends the -bit encoded layer index to the two -bit child encodings—a single fixed input length of bits (a total the volume’s companion script checks), exactly the fixed-length-per-personalisation regime in which the deployed Sinsemilla hash is collision resistant (§4.8)—with all layers sharing one Sinsemilla instance (MerkleHashOrchard::combine, prepending i2lebsp_k(level) to two L_ORCHARD_MERKLE -bit child encodings; protocol specification § 5.4.1.3). Separation between distinct Sinsemilla instances comes from the personalisation string—here z.cash:Orchard-MerkleCRH—fed to hash-to-curve to derive the instance-specific base point , while the generator table is shared across all instances (HashDomain::new derives from the personalisation via the z.cash:SinsemillaQ hash-to-curve domain; the table derives from the fixed z.cash:SinsemillaS). Sinsemilla is collision resistant under a discrete-logarithm assumption (Proposition 4.29), so the tree’s hashing and its commitment role fuse into one Pedersen-like map: the same structure that compresses the children also binds them.
A shielded pool’s set of note commitments only ever grows, and it grows one leaf at a time. Rebuilding a depth- tree from scratch on every insertion would cost hashes; the structure of the tree permits the update in hashes and state, and the state has a name.
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, —and supports one mutating operation , which places at leaf index and increments . Empty leaf slots carry a fixed empty-leaf value , and the labels of entirely empty subtrees follow by precomputation:
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 it holds at most one carry: the label of the left child of the next node to be completed at level , retained precisely when leaf index has a bit at position —a completed left sibling awaiting its right neighbour. Equivalently, writing in binary as , the frontier stores, for each with , the already-finalised left-sibling label at level along the rightmost filled path. Its size is at most labels—one per set bit of , hence state.
The right picture is arithmetic. 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 the roots of those subtrees: the pieces that are “complete and waiting for a right neighbour”. An append is then the Merkle analogue of incrementing a binary counter: a carry at level corresponds to combining two height- subtrees into one of height , and the chain of carries is as long as the run of trailing -bits of .
From the frontier of an append-only tree holding leaves, computes the new frontier and the new root using at most evaluations of and additional work, while storing only labels throughout.
The algorithm is carry propagation followed by an upward fold. Set the running label at level . While bit of is , the new path node at level is a right child whose left sibling is the stored carry : set , clear the carry , and increment . When bit of is , store as the new carry and stop. Writing for the number of trailing -bits of , the carry phase costs exactly hashes and deposits at level —the root of the just-completed height- subtree containing the new leaf, matching the binary increment , which clears trailing ones and sets bit .
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 , combine the running value with the stored carry as left sibling when bit of is —those carries lie above the cleared run and survive the append untouched—and with the precomputed empty-subtree label as right sibling otherwise; at level itself bit of is , so the first combination is with , never with the deposited carry. One hash per level makes hashes in all (zero if , when the tree has just filled). The total is exactly evaluations of , and the retained state is the at-most- carries: precisely the frontier for leaves. □
Take depth (capacity ) and insert in turn; the frontier evolves exactly as the binary counter of the leaf count .
After , : one completed height- subtree; the frontier is .
After , : leaf at index is a right child, triggering one carry —a completed height- subtree; the frontier is , with cleared.
After , : leaf at index is a left child and becomes a new height- carry; the frontier is —exactly the two set bits of .
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, which raises a question the definition of soundness so far does not answer: which root is a proof valid against?
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 chain records each block’s note-commitment-tree root—its anchor —and a spend may prove membership against any recorded 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, checked by membership in the set of recorded anchors (protocol specification § 3.7, ‘Action Transfers and their Descriptions’). Per-proof soundness is then the fixed-root soundness theorem, once per anchor. The frontier is likewise the deployed representation of the growing tree (incrementalmerkletree crate, types Frontier and NonEmptyFrontier; the empty-subtree labels are the EMPTY_ROOTS table of orchard).
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 a monotonicity it buys. 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. This is exactly what a shielded pool requires—a note, once added, can always be spent later by proving against some past anchor—and it spares the spender from tracking a moving target as the tree grows under everyone else’s insertions. The cost falls on the verifier, who must accept a window of historical roots rather than a single current one; the previous paragraph is that window, deployed.
The section has been proving properties of one construction; it pays to name the abstraction the construction inhabits, both to state precisely what the root achieves and to mark the boundary with its relatives. The abstraction is a commitment to an ordered vector that opens one position at a time. (Its unordered sibling—the cryptographic accumulator, which certifies set membership with no notion of position—exists in the literature, but Orchard never needs it: notes occupy positions, and the position is part of what the spend circuit witnesses. We do not develop it.)
A vector commitment is a tuple of PPT algorithms :
produces public parameters for vectors of length ;
outputs a short commitment and auxiliary state;
produces a proof that position holds ;
verifies an opening.
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 while both and accept. Note that the adversary chooses itself: binding must hold even for maliciously formed commitments, with no honest committer anywhere in the game.
Instantiate the syntax by: samples (and fixes with ); computes the tree and outputs with the full tree; returns the authentication path; and . If is collision resistant, this is a correct, succinct, position-binding vector commitment, with commitment size and opening size .
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 . Run the verifier’s fold (4) on each, obtaining two recomputed chains that disagree at the bottom () and agree at the top (both reach , since both openings accept). The index-consistency check forces both paths to carry the direction bits of , so at every level both chains place their running value on the same side of the compression call. The first-level-of-agreement extraction of Theorem 10.12 now applies verbatim to this pair of chains and yields two distinct -bit inputs with the same -image: a collision. The argument needed no honest reference tree—it pits the two forged openings against each other—so it binds even a maliciously chosen root, which is the strong form of position-binding the definition demands. □
The two theorems answer different verifiers. Path soundness (Theorem 10.12) fixes an honest root and forbids opening a position to anything but its true value; it speaks to a verifier who trusts where the root came from. The vector-commitment theorem (Theorem 10.25) forbids opening a single position two different ways even under an adversarial root; it speaks to a verifier who received the root from an untrusted source, and it is what “commitment” should mean— determines at most one value per position, whoever made . Both reduce to the same first-level-of-agreement collision extraction; the only difference is which pair of chains is collided, forged-against-genuine in the one case and forged-against-forged in the other.
The Merkle membership proof is succinct but not private—and for a shielded payment system, not private is fatal. Revealing the authentication path of §10.4 discloses the leaf value itself (here, the note commitment being spent) and the index at which it sits, and even the sibling labels can leak structural information about the neighbourhood of the leaf. An observer correlating spends with the appends that created their leaves links payments end to end: spending a note must not reveal which note is spent. The remedy is to prove the existence of a valid path in zero knowledge, treating the entire path as a private witness and publishing only the root.
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.24): 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 , and the siblings . It implements the compression calls of the fold (4)—the level- call being the position’s prescribed function, in the domain-separated construction, with no call since the leaf enters as the level- label (Definition 10.18)—each preceded by the conditional swap that selects the argument order or according to , and enforces the single output constraint . Its size is times the cost of one compression call plus constraints for the swaps. The position enters only through the bits —the binary decomposition of —so the index-consistency check of Definition 10.7 is enforced structurally: there is no separate index to disagree with its bits. Deployed Orchard matches this shape exactly: the circuit’s Merkle gadget decomposes the witnessed position into little-endian bits and applies a conditional swap per layer (protocol specification § 4.9, ‘Merkle Path Validity’).
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 knows—via the SNARK extractor—a witness with , and equals the genuine leaf unless a collision in is thereby found: the proven leaf is a real member of the committed list;
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 , that output is precisely a path forgery, hence yields a collision for , hence occurs with probability . Zero knowledge carries over verbatim from the SNARK simulator, which produces from alone a proof indistinguishable from the real one—so the real proof cannot be conveying , , or . □
The asymmetry in is the essential design point. 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, exactly as Remark 10.13 delimits. The path must be private so that observers cannot link the spend to a particular leaf. SNARK succinctness adds the final ingredient: 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 while simultaneously hiding it. This is the precise sense in which a Merkle root over note commitments, opened in zero knowledge, is a privacy-preserving membership primitive.
Deployment chooses where to pay for 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.
The volume closes by assembling the pieces. Every primitive below has been constructed in a previous section or in this one; the shielded spend is their composition, and the description follows the deployed Orchard sources.
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 protocol periodically publishes the current root—the anchor—on chain, one per block.
To spend a note, its owner:
locates the leaf in the public tree and reads off its authentication path and position (MerklePath::root recomputes the anchor from exactly these data);
chooses a recent anchor whose tree already contains the leaf—any recorded historical anchor serves, per §10.7;
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 the Ironwood Guide, §“The nullifier” (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.29) and the knowledge soundness of the proof system—while the network learns nothing about which note. (One refinement of the deployed circuit is worth recording: 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.
The spend consumes the whole volume. The note commitment is the hiding and binding envelope of §4; the tree hash and its personalised domains are the discipline of §3 instantiated by Sinsemilla; the nullifier is derived under the spender’s nullifier key from a PRF of §5, instantiated by Poseidon (§3.8), by the construction of the Ironwood Guide, §“The nullifier”; 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 the business of the Ironwood Guide.