The Zcash ArboretumII Crypto Guide
Contents
PDF
Theme

10 Merkle trees and commitments to sets

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.

10.1 Two statements about a set

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 v occurs at position i of the list”—or, forgetting the position, “v 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: {0,1}∗ is the set of finite binary strings, {0,1}n the strings of length exactly n, x∥y concatenation, and λ the security parameter. All algorithms are PPT in λ, and negl(λ) denotes a negligible function (Math Guide, §“Polynomial, exponential, and negligible functions”).

10.2 The compression function and collision resistance

The tree uses a single primitive, recalled in the keyed form in which its security is a meaningful asymptotic statement.

Definition 10.1 (Compression function).

Let H:𝒦×{0,1}∗→{0,1}ℓ be a keyed hash family exactly as in Definition 3.2: a key s∈𝒦 is sampled publicly at random and fixed, the digest length is ℓ=ℓ(λ), and Hs:=H(s,⋅) 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

hs:{0,1}2⁢ℓ⟶{0,1}ℓ,

taking two digests to one.

The key s 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 s and write h and H.

The tree needs collision resistance (Definition 3.7, §3.2): given the key s, every PPT adversary outputs x≠x′ with Hs(x)=Hs(x′) only with probability negl(λ). This is the strongest of the three classical hash notions (Proposition 3.8), and the generic birthday attack caps an ℓ-bit digest at ℓ/2 bits of collision security (Lemma 3.11); hence the 256-bit outputs used for the 128-bit level in this section. Merkle trees require full collision resistance, not merely second-preimage resistance, because the party that assembles the tree may itself be the adversary and choose every leaf (Theorem 10.12 makes the reason exact); this is the regime with both inputs adversarial, which Remark 3.10 assigns to collision resistance.

10.3 Binary Merkle trees

Definition 10.2 (Binary Merkle tree).

Fix a two-to-one compression function h:{0,1}2⁢ℓ→{0,1}ℓ, a depth d∈ℕ, and an ordered list L=(L0,…,L2d−1) of 2d leaf values in {0,1}ℓ. The Merkle tree of depth d over L is the complete binary tree with 2d leaves whose nodes carry labels in {0,1}ℓ, defined level by level from the leaves (level 0) to the root (level d) by

N0,j=Lj(0≤j<2d),Nt+1,j=h(Nt,2⁢j∥Nt,2⁢j+1)(0≤t<d, 0≤j<2d−t−1). (3)

Level t has 2d−t nodes, and Nt,j is the j-th node from the left at level t. The unique level-d node is the root: 𝗋𝗈𝗈𝗍(L):=Nd,0.

Example 10.3 (A depth-two tree).

With d=2 and leaves L0,L1,L2,L3, the tree has seven nodes: the four leaves, the two level-one nodes

N1,0=h⁢(L0∥L1),N1,1=h⁢(L2∥L3),

and the root

𝗋𝗈𝗈𝗍(L)=N2,0=h(h(L0∥L1)∥h(L2∥L3)).

The single ℓ-bit root depends on the whole list of four ℓ-bit strings.

A list whose length m is not a power of two is handled by fixing the depth d with 2d≥m and padding the remaining 2d−m leaf slots with a canonical value, for instance the all-zero string or the hash of the empty string. Padding must not create ambiguity: two different lists must never yield the same padded leaf sequence, since otherwise the root fails to determine the list whatever the properties of the hash. Binding the true length m into the root’s computation—one further compression of the top node with an encoding of m—removes any such ambiguity. In the alternative unbalanced tree, a node with a single child passes its child’s label upward unchanged; Remark 10.16 treats it together with second-preimage attacks.

That the root commits to the list is a security property, stated as a game in the style of Definition 1.15.

Definition 10.4 (Merkle commitment; binding).

The Merkle commitment to a list L of 2d leaves is 𝗋𝗈𝗈𝗍(L)∈{0,1}ℓ. The game 𝖡𝖨𝖭𝖣H,d𝒜(λ) runs as follows.

  1. 1.

    The challenger samples s←$𝒦, fixing the compression function h:=Hs, and sends s to the adversary.

  2. 2.

    The adversary outputs two lists L,L′, each of 2d leaves in {0,1}ℓ.

  3. 3.

    The game outputs 1 iff L≠L′ and 𝗋𝗈𝗈𝗍(L)=𝗋𝗈𝗈𝗍(L′).

The commitment is binding if every PPT adversary wins with probability negl(λ).

Proposition 10.5 (Binding of the root).

If h is collision resistant, the Merkle commitment is binding. Concretely, there is a deterministic procedure that, from any two distinct equal-length lists L≠L′ with 𝗋𝗈𝗈𝗍(L)=𝗋𝗈𝗈𝗍(L′), extracts a collision for h in time linear in the tree size—one root-to-leaf walk of O(d) hash comparisons. The reduction is tight: an adversary winning 𝖡𝖨𝖭𝖣 with probability ε yields a collision finder succeeding with the same probability ε.

Proof.

Build both trees. The lists differ at some leaf index j0, so N0,j0≠N′0,j0, writing N and N′ for the labels of the two trees. Follow the leaf-to-root path

N0,j0,N1,⌊j0/2⌋,N2,⌊j0/4⌋,…,Nd,0

in both trees. The labels differ at level 0 and agree at level d—the common root—so there is a smallest level t at which they first agree: with j=⌊j0/2t⌋,

Nt,j=N′t,j,yetNt−1,2⁢j≠N′t−1,2⁢j⁢ or ⁢Nt−1,2⁢j+1≠N′t−1,2⁢j+1,

since one of the two children at level t−1 is the path node, at which the labels still disagree by minimality of t. By the recurrence (3),

h⁢(Nt−1,2⁢j∥Nt−1,2⁢j+1)=Nt,j=N′t,j=h⁢(N′t−1,2⁢j∥N′t−1,2⁢j+1),

while the two 2ℓ-bit inputs differ in at least one half: a collision for h, located after at most d 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. □

10.4 Authentication paths and membership proofs

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.

Definition 10.6 (Authentication path).

Let a depth-d tree over L be given, and let i be a leaf index, 0≤i<2d, with binary expansion i=bd−1bd−2⋯b0, so that bit bt records whether the level-t node on the leaf-to-root path is a left child (bt=0) or a right child (bt=1). The authentication path (also Merkle proof or membership witness) for index i is

πi=((s0,b0),(s1,b1),…,(sd−1,bd−1)),

where st is the label of the sibling of the level-t node on the path. Explicitly, with jt=⌊i/2t⌋ the path node’s index at level t,

st={Nt,jt+1if ⁢bt=0(sibling on the right),Nt,jt−1if ⁢bt=1(sibling on the left).

The path has exactly d entries.

Definition 10.7 (Path verification).

The verifier 𝖵𝖾𝗋𝗂𝖿𝗒(𝑟𝑡,i,v,πi), on a root 𝑟𝑡, an index i, a claimed leaf value v∈{0,1}ℓ, and a path πi=((s0,b0),…,(sd−1,bd−1)), proceeds in two stages. First the index-consistency check: reject unless, for every t, the bit bt carried in πi equals bit t of the binary expansion of i. Then set a0:=v and fold the path upward: for t=0,…,d−1,

at+1:={h⁢(at∥st)if ⁢bt=0,h⁢(st∥at)if ⁢bt=1. (4)

Accept iff ad=𝑟𝑡. We call ad the root recomputed from (i,v,πi). The bit bt places the running value on the side matching the argument order of the tree-building recurrence: a left child is hashed on the left.

Proposition 10.8 (Completeness).

For every list L, every index i, and πi the genuine authentication path for i in the tree over L,

𝖵𝖾𝗋𝗂𝖿𝗒⁢(𝗋𝗈𝗈𝗍⁢(L),i,Li,πi)=𝖺𝖼𝖼𝖾𝗉𝗍.
Proof.

The index-consistency check passes by construction, the genuine path carrying exactly the bits of i. We show by induction on t that at=Nt,⌊i/2t⌋, the label of the level-t node on the leaf-to-root path. The base is a0=Li=N0,i. For the step, the level-t path node and its sibling st are precisely the two children of the level-(t+1) path node, and the fold (4) places at on the side dictated by bt with st on the other side—reproducing exactly the two arguments of h in the recurrence (3), so at+1=Nt+1,⌊i/2t+1⌋. At t=d this reads ad=Nd,0=𝗋𝗈𝗈𝗍(L), and the verifier accepts. □

Proposition 10.9 (Logarithmic proof size).

An authentication path in a depth-d tree consists of d sibling labels and d direction bits, dℓ+d bits in all, and verification performs exactly d evaluations of h. Choosing the minimal sufficient depth d=⌈log2m⌉ for a list of m≥2 leaves (any 2d≥m suffices) yields proofs of ⌈log2m⌉(ℓ+1) bits—logarithmic in the length of the list.

Proof.

One sibling label, one direction bit, and one compression per level, over the d levels above the leaves. □

For a set of a billion elements, m=230=1 073 741 824, a membership proof consists of 30 hash values and 30 direction bits. With a 256-bit hash the sibling labels occupy 30⋅256=7680 bits, which is 960 bytes; with the direction bits, 964 bytes, less than a kilobyte for any arrangement of the billion elements. (The byte counts are the output of the volume’s companion script.) The verifier stores one digest, and the certificate fits in a single network packet.

Example 10.10 (A depth-two membership proof).

Continue Example 10.3, and prove membership of L2 at index i=2=(10)2, so b0=0 and b1=1. At level 0 the path node N0,2=L2 is a left child, with sibling s0=N0,3=L3. At level 1 the path node N1,1=h(L2∥L3) is a right child, with sibling s1=N1,0=h(L0∥L1). The path is

π2=((L3, 0),(h⁢(L0∥L1), 1)).

Verification folds upward:

a1=h⁢(L2∥L3),thena2=h⁢(h⁢(L0∥L1)∥a1)=𝗋𝗈𝗈𝗍⁢(L),

and the verifier accepts. The verifier never receives L0 or L1, only their digest h(L0∥L1), and is nevertheless convinced that L2 occupies index 2 of the committed list. Figure 16 draws this path.

Refer to caption
Figure 16: The authentication path of Example 10.10 in the depth-2 tree of Example 10.3. The path from the leaf at index i=2=(10)2 to the root, N0,2, N1,1, N2,0, is amber; the siblings s0=N0,3 and s1=N1,0, which form π2 with the bits, are blue. The bit b0=0 places the running value on the left at level 0 and b1=1 on the right at level 1; the fold (4) at the right recomputes the root from L2 and the two siblings alone.

10.5 Soundness: forging a path implies a collision

Soundness states that, against an honest root, a path for a value other than the genuine leaf verifies only with negligible probability.

Definition 10.11 (Path forgery).

Fix a list L of 2d leaves with root 𝑟𝑡=𝗋𝗈𝗈𝗍(L). The game 𝖯𝖠𝖳𝖧𝖥𝖮𝖱𝖦𝖤H,L𝒜(λ) runs as follows.

  1. 1.

    The challenger samples s←$𝒦 to fix h:=Hs, builds the tree over L, and sends s together with L—equivalently, the whole tree—to the adversary.

  2. 2.

    The adversary outputs an index i and a pair (v∗,π∗).

  3. 3.

    The game outputs 1 iff 𝖵𝖾𝗋𝗂𝖿𝗒(𝑟𝑡,i,v∗,π∗)=𝖺𝖼𝖼𝖾𝗉𝗍 and v∗≠Li.

A winning output is a path forgery at index i: the verifier accepts, against the honestly computed root, a leaf value different from the genuine one at position i.

Theorem 10.12 (Soundness of Merkle membership proofs).

Let h be collision resistant. Then no PPT adversary, given the list L and the whole tree, produces a path forgery except with probability negl(λ). In constructive form: there is a deterministic extractor that from any list L, index i, and accepting forgery (v∗,π∗) with v∗≠Li outputs a collision for h, in time linear in the tree size—recomputing the genuine leaf-to-root labels from L dominates; given the built tree, one verifier run plus a level-by-level comparison, O(d) work in all, completes the extraction.

Proof.

Run the verifier’s fold (4) on (i,v∗,π∗), obtaining the chain a0∗=v∗,a1∗,…,ad∗=𝑟𝑡 (the final equality because the forgery is accepting). Alongside it place the genuine chain at=Nt,⌊i/2t⌋, 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 ad=𝑟𝑡.

The two chains disagree at the bottom, a0∗=v∗≠Li=a0, and agree at the top, ad∗=ad=𝑟𝑡. Hence

t∗:=min⁡{t:at∗=at}∈{1,…,d}

exists, and at∗−1∗≠at∗−1 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 i—the same bits the genuine path carries—so at level t∗−1 both chains place their running value on the same side of the compression call: both compute h(⋅∥sibling) if bt∗−1=0, both h(sibling∥⋅) if bt∗−1=1. Form the two 2ℓ-bit preimages accordingly,

X∗={at∗−1∗∥st∗−1∗if ⁢bt∗−1=0,st∗−1∗∥at∗−1∗if ⁢bt∗−1=1,X={at∗−1∥st∗−1if ⁢bt∗−1=0,st∗−1∥at∗−1if ⁢bt∗−1=1,

where st∗−1∗ is the sibling claimed in π∗ and st∗−1 the genuine sibling. Then

h⁢(X∗)=at∗∗=at∗=h⁢(X),X∗≠X,

the inequality because the two preimages differ in the half occupied by the running value. The pair (X∗,X) is a collision for h, found deterministically in O(d) work once the genuine chain is at hand—a read-off from the built tree, or 2d−1 hashes from the bare list L. □

If a PPT adversary 𝒜 produces path forgeries with probability ε(λ), the collision finder ℬ that receives the key, samples or receives L, runs 𝒜, and applies the extractor outputs a collision whenever 𝒜 succeeds—hence with probability ε(λ), at an overhead of building the tree over L, which ℬ does in any case to play the challenger, plus one verifier run and O(d) comparisons. Collision resistance of h therefore forces ε(λ)∈negl(λ), and the reduction is tight.

Remark 10.13 (Scope: a fixed honest root).

Theorem 10.12 is a statement about a fixed honest root: relative to a root that genuinely is 𝗋𝗈𝗈𝗍(L), the only leaf value admitting an accepting path at position i is Li, up to a collision in h. 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.

10.6 Layer and domain separation

The soundness theorem does not cover the following structural confusion. Suppose the leaves are arbitrary-length data, hashed into {0,1}ℓ by the same function used internally. Then an internal label h(A∥B) is itself a well-formed leaf value—it has the right length. An adversary presents the internal node N1,0=h(L0∥L1) as a leaf near the top of a shallower tree, with the correspondingly shorter authentication path, and a verifier that does not know the depth accepts. The root then has a second list that produces it: a second-preimage attack that involves no collision of h. Unless each label determines whether it is a leaf or an internal node, the leaf-to-root structure on which Theorem 10.12 relies fails.

The remedy applies the domain-separation discipline of §3.5 within a single structure.

Definition 10.14 (Layer and domain separation).

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 H define

𝖫𝖾𝖺𝖿𝖧𝖺𝗌𝗁⁢(v):=H⁢(𝟶⁢𝚡⁢𝟶𝟶∥v),𝖭𝗈𝖽𝖾𝖧𝖺𝗌𝗁t⁢(A,B):=H⁢(𝟶⁢𝚡⁢𝟶𝟷⁢‖⟨t⟩‖⁢A∥B),

where the byte tags 𝟶𝚡𝟶𝟶 and 𝟶𝚡𝟶𝟷 distinguish the layer kind—leaf versus internal node—and ⟨t⟩ is a fixed-length encoding of the level index, distinguishing internal nodes by depth. The tree recurrence becomes

N0,j=𝖫𝖾𝖺𝖿𝖧𝖺𝗌𝗁⁢(Lj),Nt+1,j=𝖭𝗈𝖽𝖾𝖧𝖺𝗌𝗁t+1⁢(Nt,2⁢j,Nt,2⁢j+1),

and the verifier’s fold applies the same tagged functions at the same positions.

Proposition 10.15 (Separation forces within-domain collisions).

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 H between two inputs sharing the same leading tag: a leaf preimage against a leaf preimage, or a level-t node preimage against a level-t 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 H—which collision resistance forbids.

Proof sketch.

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 t≥1 both pass through 𝖭𝗈𝖽𝖾𝖧𝖺𝗌𝗁t. Both colliding preimages therefore begin with the same tag—𝟶𝚡𝟶𝟶, or 𝟶𝚡𝟶𝟷∥⟨t⟩—and the collision lies within a single domain. A cross-domain confusion, by contrast, would require two inputs with different leading tags and equal H-images, which is again an H-collision; in either case the adversary has broken collision resistance, and the shallower-tree attack above is excluded because a leaf preimage and a node preimage can no longer be the same string. □

Remark 10.16 (Unbalanced trees, padding, and a deployed failure).

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.

Remark 10.17 (Algebraic hashes in the tree; Orchard’s 𝖬𝖾𝗋𝗄𝗅𝖾𝖢𝖱𝖧).

When the Merkle path is verified inside a zero-knowledge circuit (§10.9), arithmetic gates over 𝔽p evaluate the compression function, and the choice of h 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 h:𝔽p2→𝔽p. 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 to the two 255-bit child encodings the 10-bit little-endian encoding of 31−k, where k is the layer of the computed node counted from the root of the depth-32 tree. The tag is thus the level of the two children counted from the leaves, one less than the index t+1 of Definition 10.14. Every call has the single fixed input length of 520 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 (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 Q, while the generator table S is shared across all instances (the base point is derived from the personalisation under the hash-to-curve domain z.cash:SinsemillaQ, the table under the fixed z.cash:SinsemillaS). Sinsemilla is collision resistant under a discrete-logarithm assumption (Proposition 4.30), so the tree’s hashing and its commitment role coincide in one Pedersen-like map.

10.7 Append-only and incrementally updatable trees

The set of note commitments of a shielded pool only grows, one leaf at a time. Rebuilding a depth-32 tree on every insertion would cost 232 hashes; the frontier defined below permits the update in d hashes and O(d) state.

Definition 10.18 (Append-only Merkle tree).

Fix a maximum depth d, giving capacity 2d, and the level-indexed 𝖭𝗈𝖽𝖾𝖧𝖺𝗌𝗁 functions of Definition 10.14. Leaf values here enter as level-0 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 m—the number of leaves inserted so far, 0≤m≤2d—and supports one mutating operation 𝖠𝗉𝗉𝖾𝗇𝖽(v), which places v at leaf index m and increments m. Empty leaf slots m,…,2d−1 carry a fixed empty-leaf value ⊥0, and the labels of entirely empty subtrees follow by precomputation:

⊥t+1:=𝖭𝗈𝖽𝖾𝖧𝖺𝗌𝗁t+1(⊥t,⊥t),0≤t<d.

The root after m appends, written 𝗋𝗈𝗈𝗍m, is the root of the depth-d tree, under this recurrence, whose first m level-0 labels are the inserted values and whose remaining ones are ⊥0.

Definition 10.19 (Frontier).

The frontier of an append-only tree holding m leaves is the minimal state needed to (i) compute the current root and (ii) update incrementally on the next 𝖠𝗉𝗉𝖾𝗇𝖽. For each level t∈{0,…,d−1} it holds at most one carry: the label of the left child of the next node to be completed at level t+1, retained precisely when leaf index m has a 1 bit at position t—a completed left sibling awaiting its right neighbour. Equivalently, writing m in binary as bd−1⋯b0, the frontier stores, for each t with bt=1, the already-finalised left-sibling label ft at level t along the rightmost filled path. Its size is at most d labels—one per set bit of m, hence O(logm) state.

The binary representation of m decomposes the inserted leaves into completed perfect subtrees of distinct heights, one of height t for each set bit bt, and the frontier holds exactly their roots. An append is the Merkle analogue of incrementing a binary counter: a carry at level t combines two height-t subtrees into one of height t+1, and the chain of carries is as long as the run of trailing 1-bits of m.

Proposition 10.20 (Incremental append in logarithmic time).

From the frontier of an append-only tree holding m<2d leaves, 𝖠𝗉𝗉𝖾𝗇𝖽(v) computes the new frontier and the new root 𝗋𝗈𝗈𝗍m+1 using at most d evaluations of 𝖭𝗈𝖽𝖾𝖧𝖺𝗌𝗁 and O(d) additional work, while storing only O(d) labels throughout.

Proof.

The algorithm is carry propagation followed by an upward fold. Set the running label c←v at level t←0. While bit t of m is 1, the new path node at level t is a right child whose left sibling is the stored carry ft: set c←𝖭𝗈𝖽𝖾𝖧𝖺𝗌𝗁t+1(ft,c), clear the carry ft, and increment t. When bit t of m is 0, store c as the new carry ft and stop. Writing z for the number of trailing 1-bits of m, the carry phase costs exactly z hashes and deposits fz at level z—the root of the just-completed height-z subtree containing the new leaf, matching the binary increment m↦m+1, which clears z trailing ones and sets bit z.

To obtain 𝗋𝗈𝗈𝗍m+1, fold upward from level z with the just-deposited fz as the running value—it is the path label at level z, not a sibling. For t=z,…,d−1, combine the running value with the stored carry ft as left sibling when bit t of m is 1—those carries lie above the cleared run and survive the append untouched—and with the precomputed empty-subtree label ⊥t as right sibling otherwise; at level z itself bit z of m is 0, so the first combination is with ⊥z, never with the deposited carry. One hash per level makes d−z hashes in all (zero if z=d, when the tree has just filled). The total is exactly z+(d−z)=d evaluations of 𝖭𝗈𝖽𝖾𝖧𝖺𝗌𝗁, and the retained state is the at-most-d carries: precisely the frontier for m+1 leaves. □

Example 10.21 (The frontier as a binary counter).

Take depth d=3 (capacity 8) and insert v0,v1,v2 in turn; the frontier evolves exactly as the binary counter of the leaf count m.

  • •

    After v0, m=1=(001)2: one completed height-0 subtree; the frontier is {f0=v0}.

  • •

    After v1, m=2=(010)2: leaf v1 at index 1 is a right child, triggering one carry c=𝖭𝗈𝖽𝖾𝖧𝖺𝗌𝗁1(v0,v1)—a completed height-1 subtree; the frontier is {f1=c}, with f0 cleared.

  • •

    After v2, m=3=(011)2: leaf v2 at index 2 is a left child and becomes a new height-0 carry; the frontier is {f1=𝖭𝗈𝖽𝖾𝖧𝖺𝗌𝗁1(v0,v1),f0=v2} —exactly the two set bits of 3.

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 m at every step.)

Figure 17 draws the three appends of Example 10.21.

Refer to caption
Figure 17: The frontier of Definition 10.19 across the three appends of Example 10.21, on a tree of depth d=3; grey leaves hold the empty-leaf value ⊥0. The frontier labels (amber) sit at the levels t of the set bits bt of the leaf count m, shown beside each tree: after v0 it is f0=v0; appending v1 carries f0 into f1=𝖭𝗈𝖽𝖾𝖧𝖺𝗌𝗁1(v0,v1), as (001)2+1 carries into (010)2; appending v2 deposits f0=v2 and leaves f1 in place.

Appending changes the root; the following definition fixes the root against which a proof is valid.

Definition 10.22 (History binding).

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 m is odd these labels are exactly the carries of Definition 10.19. When m is even, with lowest set bit z≥1, the leaf and its left siblings at levels below z hash to the single carry fz, and the remaining siblings are the carries above z. Either form serves both purposes (i) and (ii) of the definition.

Remark 10.23 (Why append-only, and what it costs).

Deletion or in-place update could be supported at O(logm) 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.

10.8 Vector commitments

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.

Definition 10.24 (Vector commitment).

A vector commitment is a tuple of PPT algorithms (𝖲𝖾𝗍𝗎𝗉,𝖢𝗈𝗆𝗆𝗂𝗍,𝖮𝗉𝖾𝗇,𝖵𝖿):

  • •

    𝖲𝖾𝗍𝗎𝗉(1λ,n)→𝑝𝑝 produces public parameters for vectors of length n;

  • •

    𝖢𝗈𝗆𝗆𝗂𝗍(𝑝𝑝,(v0,…,vn−1))→(C,𝑎𝑢𝑥) outputs a short commitment and auxiliary state;

  • •

    𝖮𝗉𝖾𝗇(𝑝𝑝,i,𝑎𝑢𝑥)→πi produces a proof that position i holds vi;

  • •

    𝖵𝖿(𝑝𝑝,C,i,v,π)→{𝖺𝖼𝖼𝖾𝗉𝗍,𝗋𝖾𝗃𝖾𝖼𝗍} verifies an opening.

The scheme is correct if honest openings always verify, and succinct if |C| and |πi| are bounded by a fixed polynomial in λ and logn. It is position-binding if every PPT adversary wins the following game with probability negl(λ): given 𝑝𝑝, the adversary outputs (C,i,v,v′,π,π′) and wins iff v≠v′ while both 𝖵𝖿(𝑝𝑝,C,i,v,π) and 𝖵𝖿(𝑝𝑝,C,i,v′,π′) accept. The adversary chooses C itself: binding must hold even for maliciously formed commitments, with no honest committer in the game.

Theorem 10.25 (Merkle trees are succinct position-binding vector commitments).

Instantiate the syntax by: 𝖲𝖾𝗍𝗎𝗉 samples h (and fixes d with n=2d); 𝖢𝗈𝗆𝗆𝗂𝗍 computes the tree and outputs C=𝗋𝗈𝗈𝗍 with 𝑎𝑢𝑥 the full tree; 𝖮𝗉𝖾𝗇 returns the authentication path; and 𝖵𝖿=𝖵𝖾𝗋𝗂𝖿𝗒. If h is collision resistant, this is a correct, succinct, position-binding vector commitment, with commitment size ℓ and opening size O(ℓlogn).

Proof.

Correctness is completeness (Proposition 10.8), and the size bounds are Proposition 10.9. For position-binding, suppose an adversary outputs two accepting openings (v,π) and (v′,π′) at the same index i under the same root C, with v≠v′. Run the verifier’s fold (4) on each, obtaining two recomputed chains that disagree at the bottom (v≠v′) and agree at the top (both reach C, since both openings accept). The index-consistency check forces both paths to carry the direction bits of i, 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 applies verbatim to this pair of chains and yields two distinct 2ℓ-bit inputs with the same h-image: a collision. The argument uses no honest reference tree—it compares the two forged openings with each other—so it applies even to a maliciously chosen root, which is the strong form of position-binding the definition requires. □

Remark 10.26 (Position-binding versus path soundness).

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 C determines at most one value per position, whoever produced C. 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.

10.9 Privacy-preserving membership via zero-knowledge paths

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 i, 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.

Definition 10.27 (The membership relation).

For the domain-separated Merkle construction of depth d, with leaves entering as level-0 labels under the convention of Definition 10.18, define

Rmem:={(𝑟𝑡;(v,i,π)):𝖵𝖾𝗋𝗂𝖿𝗒⁢(𝑟𝑡,i,v,π)=𝖺𝖼𝖼𝖾𝗉𝗍},

with the statement the public root 𝑟𝑡 and the witness comprising the leaf v, its index i, and the authentication path π. A zero-knowledge argument for Rmem lets a prover convince a verifier that some leaf lies in the tree with root 𝑟𝑡 while revealing none of v, i, 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).

Figure 18 draws the statement and the witness for the path of Example 10.10.

Refer to caption
Figure 18: The relation Rmem of Definition 10.27 on the depth-2 tree, for the path of Example 10.10 (i=2). Above the divider, the root 𝑟𝑡 alone is the public statement (green). Below it, the witness (grey, boxed) is the leaf v, its index i, entering the circuit only through the bits b0 and b1, and the siblings s0 and s1. The circuit Cmem of Construction 10.28 performs the fold (4) (amber) through the intermediate value a1 and enforces a2=𝑟𝑡; dotted nodes are neither public nor part of the witness.
Construction 10.28 (In-circuit path verification).

The Merkle-path circuit Cmem of depth d takes as public input the root 𝑟𝑡, and as private (witness) inputs the leaf v, the direction bits b0,…,bd−1, and the siblings s0,…,sd−1. It implements the d compression calls of the fold (4)—the level-t call being the position’s prescribed function, 𝖭𝗈𝖽𝖾𝖧𝖺𝗌𝗁t+1 in the domain-separated construction, with no 𝖫𝖾𝖺𝖿𝖧𝖺𝗌𝗁 call since the leaf enters as the level-0 label (Definition 10.18)—each preceded by the conditional swap that selects the argument order (at,st) or (st,at) according to bt, and enforces the single output constraint ad=𝑟𝑡. Its size is d times the cost of one compression call plus O(d) constraints for the swaps. The position enters only through the bits b0,…,bd−1—the binary decomposition of i—so the index-consistency check of Definition 10.7 is enforced structurally: there is no separate index to disagree with its bits. The deployed Sapling circuit has exactly this shape: each layer boolean-constrains one path bit and conditionally swaps the previous-layer and sibling hashes on it (protocol specification §“Merkle path check”), the path bits being those of the position, least significant at the leaf, that select the siblings of a Merkle path (§ 4.9, ‘Merkle Path Validity’).

Theorem 10.29 (Privacy-preserving membership).

Let h be collision resistant and let (P,V) be a zk-SNARK for Rmem—equivalently, for satisfiability of Cmem. Then the protocol “the prover sends a SNARK proof for the statement 𝑟𝑡; the verifier checks it” is a membership argument that is:

  1. 1.

    complete: a prover holding a genuine leaf and its path produces an accepting proof;

  2. 2.

    sound: any prover producing an accepting proof for an honest root 𝑟𝑡=𝗋𝗈𝗈𝗍(L) knows—via the SNARK extractor—a witness (v,i,π) with 𝖵𝖾𝗋𝗂𝖿𝗒(𝑟𝑡,i,v,π)=𝖺𝖼𝖼𝖾𝗉𝗍, and v equals the genuine leaf Li unless a collision in h is thereby found: the proven leaf is a real member of the committed list;

  3. 3.

    private: the proof reveals nothing about v, i, or π beyond the fact that some valid leaf exists under 𝑟𝑡.

Proof idea.

Completeness composes SNARK completeness with tree completeness (Proposition 10.8): the genuine (Li,i,πi) satisfies Cmem, 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 (v,i,π) accepted by 𝖵𝖾𝗋𝗂𝖿𝗒; if v≠Li, that output is precisely a path forgery, hence yields a collision for h, hence occurs with probability negl(λ). Zero knowledge is inherited directly from the SNARK simulator, which produces from 𝑟𝑡 alone a proof indistinguishable from the real one; hence the real proof conveys nothing about v, i, or π. □

Remark 10.30 (Public root, private path; deployment trade-offs).

In Rmem 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 d—polylogarithmic—even though the witness contains d 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.

10.10 A shielded spend, end to end

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.

Example 10.31 (An Orchard shielded spend).

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 x-coordinate

𝖼𝗆x=𝖤𝗑𝗍𝗋𝖺𝖼𝗍𝖯⁢(𝖼𝗆),

a 255-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:

  1. 1.

    locates the leaf 𝖼𝗆x in the public tree and reads off its authentication path π and position i;

  2. 2.

    chooses a recent anchor 𝑟𝑡=𝗋𝗈𝗈𝗍m whose tree already contains the leaf—any recorded historical anchor serves, per §10.7;

  3. 3.

    proves in zero knowledge, per Theorem 10.29, the statement 𝑟𝑡 with witness (𝖼𝗆x,i,π): 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’);

  4. 4.

    publishes the proof and the nullifier—but neither 𝖼𝗆, nor i, 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 Rmem 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.