V Ironwood Guide: The Zcash Orchard protocol and its Ironwood pool 4 Notes and note commitments 6 Nullifiers

5 The note commitment tree

This section constructs the note commitment tree of a pool and its Merkle hash, defines the anchors, proves in Proposition 5.9 that a valid authentication path to an anchor exhibits a leaf of the anchored tree unless it yields a collision of the hash’s Sinsemilla instance or an input on which that instance returns $\bot$ , and proves in Lemma 5.15 that the authentication path of a leaf is a function of public data.

5.1 The Merkle hash and the tree

Remark 5.1 (Requirement R2).

Requirement R2 of “Requirements on a shielded payment” (§1.4) asks the consumer of a note of non-zero value to show that the note was previously committed, without identifying it. In the Orchard protocol the claim to be shown is that the extracted commitment $\mathsf{cmx}$ of the note (Definition 4.4) is a leaf of the note commitment tree of the note’s pool, and the leaf is not to be disclosed. Membership of a private leaf under a public root is provable in zero knowledge, with the root public and the leaf, its position and its authentication path private (Crypto Guide, §“Privacy-preserving membership via zero-knowledge paths”, Theorem “Privacy-preserving membership”). We construct the tree, its roots, called anchors, and its authentication paths; the relation proved for each Action is the Action statement, defined in “The Action statement” (§9.2).

Definition 5.2 (Note commitment tree).

Let

\mathsf{MerkleDepth}^{\mathsf{Orchard}}:=32,\qquad\mathsf{Uncommitted}^{% \mathsf{Orchard}}:=2\in\mathbb{F}_{p_{\mathsf{Pallas}}}

(protocol specification, §“Constants”). Each pool of the Orchard protocol has its own note commitment tree, an append-only Merkle tree (Crypto Guide, §“Binary Merkle trees” and §“Append-only and incrementally updatable trees”) of fixed depth $\mathsf{MerkleDepth}^{\mathsf{Orchard}}=32$ , hence with $2^{32}$ leaf positions. Its layers are numbered from layer $0$ , the root, to layer $32$ , the leaves; layer $h$ has $2^{h}$ nodes $M^{h}_{i}\in\mathbb{F}_{p_{\mathsf{Pallas}}}$ , $0\leq i<2^{h}$ .

1.

Appending. Each Action of the pool in a transaction publishes the extracted commitment $\mathsf{cmx}$ of its created note (§4.4). When the transaction enters the chain, each such $\mathsf{cmx}$ is appended to the pool’s tree: it occupies the leaf $M^{32}_{i}$ for the least unused index $i$ , and $i$ is the note position $\mathsf{pos}$ of that commitment. Every pool’s tree has no appended leaf before the first block of the chain.
2.

Leaves. After $n$ appends, the leaf $M^{32}_{i}$ is the value appended at position $i$ for $0\leq i<n$ , and $M^{32}_{i}:=\mathsf{Uncommitted}^{\mathsf{Orchard}}=2$ for $n\leq i<2^{32}$ .
3.

Internal nodes. For $0\leq h<32$ and $0\leq i<2^{h}$ ,

$M^{h}_{i}:=\mathsf{MerkleCRH}\bigl{(}h,\,M^{h+1}_{2i},\,M^{h+1}_{2i+1}\bigr{)},$

with $\mathsf{MerkleCRH}$ the Merkle hash constructed below; the root is $M^{0}_{0}$ .

(Protocol specification, §“Note Commitment Trees”, §“Merkle Path Validity”, §“Note Commitments” and §“Transactions and Treestates”.)

Construction 5.3 (Merkle hash).

Let $D:=\texttt{z.cash:Orchard-MerkleCRH}$ . The Merkle hash

\mathsf{MerkleCRH}\colon\{0,\dots,31\}\times\mathbb{F}_{p_{\mathsf{Pallas}}}% \times\mathbb{F}_{p_{\mathsf{Pallas}}}\to\mathbb{F}_{p_{\mathsf{Pallas}}}

\mathsf{MerkleCRH}(l,\mathit{left},\mathit{right}):=\begin{cases}0&\text{if }% \eta=\bot,\\ \eta&\text{otherwise},\end{cases}

where

\eta:=\mathsf{SinsemillaHash}\bigl{(}D,\ \mathrm{LE}_{10}(31-l)\,\|\,\mathrm{% LE}_{255}(\mathit{left})\,\|\,\mathrm{LE}_{255}(\mathit{right})\bigr{)}\in% \mathbb{F}_{p_{\mathsf{Pallas}}}\cup\{\bot\},

with $\mathsf{SinsemillaHash}$ the extracted Sinsemilla hash of §2.4 and field elements encoded through their integer representatives. The protocol specification names the map $\mathsf{MerkleCRH}^{\mathsf{Orchard}}$ and the width $255$ $\mathsf{MerkleHashLength}^{\mathsf{Orchard}}$ (§“ $\mathsf{MerkleCRH}^{\mathsf{Orchard}}$ Hash Function” and §“Constants”).

The prefix $\mathrm{LE}_{10}(31-l)=\mathrm{LE}_{10}(\mathsf{MerkleDepth}^{\mathsf{Orchard}% }-1-l)$ is defined because $31<2^{10}$ . It encodes $0$ for the combination of two leaves into a node of layer $l=31$ , and $31$ for the combination that yields the root, $l=0$ . Every message has the single length $10+255+255=520$ bits, $52$ chunks of $k=10$ bits, within the bound of $c=253$ chunks of §2.4 (Table 4). The encoding $\mathrm{LE}_{255}$ is injective on $\mathbb{F}_{p_{\mathsf{Pallas}}}$ because $p_{\mathsf{Pallas}}<2^{255}$ (§2.1), so for a fixed layer distinct argument pairs give distinct messages. The protocol specification requires that $\mathsf{SinsemillaHash}$ be collision resistant and that no input of $520$ bits yielding $\bot$ can feasibly be found (§“ $\mathsf{MerkleCRH}^{\mathsf{Orchard}}$ Hash Function”, security requirements). For the domain $D$ and $520$ -bit messages these are parts (i) and (iii) of Proposition 2.24, under Assumptions 2.22 and 2.8.

Remark 5.4 (Nodes as field elements).

Because $\mathsf{MerkleCRH}$ ends in $\mathsf{Extract}_{\mathbb{P}}$ , each layer’s output has the type of its inputs, and one hash composes from the leaves to the root. Proofs of the Action statement, defined in “The Action statement” (§9.2), are Halo 2 proofs with the Vesta curve (protocol specification, §“Zero-Knowledge Proving System”), whose scalar field is $\mathbb{F}_{p_{\mathsf{Pallas}}}$ (Math Guide, §“Base fields, scalar fields, and the Pasta cycle”). A node that is one element of $\mathbb{F}_{p_{\mathsf{Pallas}}}$ is one value of that proof’s arithmetic, whereas a point-valued node would carry two coordinates and a curve-equation condition at each of the $32$ layers.

Remark 5.5 (Dropping the $y$ -coordinate).

A node serves only as a digest, never to recover a point, and $\mathsf{Extract}_{\mathbb{P}}(P)=\mathsf{Extract}_{\mathbb{P}}(P^{\prime})$ only if $P^{\prime}=P$ or $P^{\prime}=-P$ (Lemma 2.4). A collision of $\mathsf{SinsemillaHash}(D,\cdot)$ on $520$ -bit messages is therefore either a collision of the underlying hash to a point or a pair of messages whose hash points are opposite. Proposition 2.24(i) excludes both, and part (iii) excludes a $\bot$ output, under Assumptions 2.22 and 2.8.

Remark 5.6 (Layer separation).

The prefix $\mathrm{LE}_{10}(31-l)$ separates the inputs of different layers (protocol specification, §“ $\mathsf{MerkleCRH}^{\mathsf{Orchard}}$ Hash Function”, note). The $32$ layer functions $\mathsf{MerkleCRH}(l,\cdot,\cdot)$ evaluate one instance $\mathsf{SinsemillaHash}(D,\cdot)$ on message sets with distinct prefixes. Every collision that the proof of Proposition 5.9 extracts therefore lies between two messages with the same prefix, and a node computed at one layer is accepted at another only through such a collision or a $\bot$ input (Crypto Guide, §“Layer and domain separation”, Proposition “Separation forces within-domain collisions”).

Lemma 5.7 (Uncommitted leaves).

No point $P$ of the Pallas group satisfies $\mathsf{Extract}_{\mathbb{P}}(P)=2$ . Consequently $\mathsf{Uncommitted}^{\mathsf{Orchard}}=2$ equals the extracted commitment $\mathsf{cmx}=\mathsf{Extract}_{\mathbb{P}}^{\bot}(\mathsf{cm})$ of no note, and a leaf position holding $2$ holds the commitment of no note.

Proof.

By definition $\mathsf{Extract}_{\mathbb{P}}(\mathcal{O})=0\neq 2$ in $\mathbb{F}_{p_{\mathsf{Pallas}}}$ . A point $(x,y)\neq\mathcal{O}$ with $x=2$ on the curve $y^{2}=x^{3}+5$ over $\mathbb{F}_{p_{\mathsf{Pallas}}}$ would satisfy $y^{2}=2^{3}+5=13$ . By Euler’s criterion $13^{(p_{\mathsf{Pallas}}-1)/2}\equiv-1\pmod{p_{\mathsf{Pallas}}}$ (Math Guide, §“Quadratic residues and the Euler criterion”, Example “ $13$ is a non-square in both Pasta fields”), so $13$ is a non-square modulo $p_{\mathsf{Pallas}}$ and no such $y$ exists. Only the base-field modulus $p_{\mathsf{Pallas}}$ enters. For the consequence, $\mathsf{cmx}$ is $\bot$ when $\mathsf{cm}=\bot$ and otherwise $\mathsf{Extract}_{\mathbb{P}}$ of a point, so it is not $2$ . The protocol specification states the consequence as the theorem “ $\mathsf{Uncommitted}^{\mathsf{Orchard}}$ is not in the range of $\mathsf{NoteCommit}^{\mathsf{Orchard}}$ ” (§“Sinsemilla commitments”). □

The protocol specification, §“Note Commitment Trees”, and ZIP 258, “Changes to the Protocol Specification”, state the capacity rule: a block must not add Ironwood-pool note commitments that would make the Ironwood-pool note commitment tree exceed its capacity of $2^{\mathsf{MerkleDepth}^{\mathsf{Orchard}}}=2^{32}$ leaves; the same rule binds the Orchard-pool tree. The Ironwood-pool tree is a tree of its own, built by the construction above with the same depth, the same value $\mathsf{Uncommitted}^{\mathsf{Orchard}}$ at unused positions and the same hash; only the values $\mathsf{cmx}$ published by Ironwood-pool Actions are appended to it.

5.2 Anchors

Definition 5.8 (Treestate and anchor).

A pool’s treestate comprises its note commitment tree and its nullifier set, constructed in “Nullifier sets” (§6.2). Treestates are chained: the input treestate of the first block is empty; the input treestate of the first transaction of a block is the final treestate of the preceding block, and that of each later transaction the output treestate of the preceding transaction; the final treestate of a block is the output treestate of its last transaction (protocol specification, §“Transactions and Treestates”). The anchor of a block in a pool is the root $M^{0}_{0}$ of the pool’s tree in the block’s final treestate, an element of $\mathbb{F}_{p_{\mathsf{Pallas}}}$ ; every block has exactly one anchor per pool. A bundle carries one anchor field, $\mathsf{anchorIronwood}$ in the Ironwood pool and $\mathsf{anchorOrchard}$ in the Orchard pool, shared by all its Actions; an Action carries no anchor of its own (“Action descriptions and bundles”, §11.1; protocol specification, §“Action Transfers and their Descriptions”).

The protocol specification, §“Action Transfers and their Descriptions”, and ZIP 258, “Changes to the Protocol Specification”, state the anchor rule: whenever a transaction has Ironwood-pool Actions, its field $\mathsf{anchorIronwood}$ must refer to some earlier block’s final Ironwood-pool treestate, that is, equal the Ironwood-pool anchor of a block that precedes the transaction’s block in the chain. The field $\mathsf{anchorOrchard}$ is bound likewise to the Orchard pool. The rule sets no bound on how far back that block lies.

Proposition 5.9 (Membership soundness).

Let $\mathit{rt}$ be the anchor of a block in a pool, $n$ the number of leaves appended to the pool’s tree through that block, and $L_{0},\dots,L_{2^{32}-1}$ the leaves of the tree that $\mathit{rt}$ roots, so that $L_{i}=\mathsf{Uncommitted}^{\mathsf{Orchard}}$ for $i\geq n$ . For $v,s_{0},\dots,s_{31}\in\mathbb{F}_{p_{\mathsf{Pallas}}}$ and $\mathsf{pos}=\sum_{t=0}^{31}b_{t}2^{t}$ with $b_{t}\in\{0,1\}$ , let

a_{0}:=v,\qquad a_{t+1}:=\begin{cases}\mathsf{MerkleCRH}(31-t,\,a_{t},\,s_{t})% &\text{if }b_{t}=0,\\ \mathsf{MerkleCRH}(31-t,\,s_{t},\,a_{t})&\text{if }b_{t}=1\end{cases}\qquad(0% \leq t<32).

(2)

The triple $(v,\mathsf{pos},(s_{0},\dots,s_{31}))$ is a valid path to $\mathit{rt}$ if $a_{32}=\mathit{rt}$ . This is the path verification of the Crypto Guide (§“Authentication paths and membership proofs”, Definition “Path verification”), with level- $t$ compression $\mathsf{MerkleCRH}(31-t,\cdot,\cdot)$ and the bits of $\mathsf{pos}$ as direction bits; “Authentication paths” (§5.3) constructs the path of an appended leaf.

(i)

From a valid path to $\mathit{rt}$ with $v\neq L_{\mathsf{pos}}$ and the leaves $L_{0},\dots,L_{n-1}$ one computes efficiently either two distinct $520$ -bit messages with a common $10$ -bit prefix and equal values of $\mathsf{SinsemillaHash}(D,\cdot)$ , for $D=\texttt{z.cash:Orchard-MerkleCRH}$ , or a $520$ -bit message on which $\mathsf{SinsemillaHash}(D,\cdot)$ returns $\bot$ .
(ii)

Under Assumptions 2.22 and 2.8, an efficient adversary, even one that chooses the appended leaves, outputs a valid path to $\mathit{rt}$ with $v\neq L_{\mathsf{pos}}$ with at most negligible probability.
(iii)

In particular, if $v=\mathsf{Extract}_{\mathbb{P}}(P)$ for a point $P$ of the Pallas group, as the extracted commitment $\mathsf{cmx}\neq\bot$ of every note is, then, except with negligible probability, $\mathsf{pos}<n$ and $v$ is the value appended at position $\mathsf{pos}$ , in the anchoring block or earlier.

Proof.

The argument is the Crypto Guide’s Theorem “Soundness of Merkle membership proofs” (§“Soundness: forging a path implies a collision”), with layer-dependent compressions.

(i) Let $j_{t}:=\lfloor\mathsf{pos}/2^{t}\rfloor$ , and write $j\oplus 1$ for the integer $j$ with its lowest bit complemented. The genuine chain is $\bar{a}_{t}:=M^{32-t}_{j_{t}}$ for $0\leq t\leq 32$ , with genuine siblings $\bar{s}_{t}:=M^{32-t}_{j_{t}\oplus 1}$ for $0\leq t<32$ . Since $j_{t}=2j_{t+1}+b_{t}$ , the node $\bar{a}_{t+1}=M^{31-t}_{j_{t+1}}$ is $\mathsf{MerkleCRH}(31-t,\cdot,\cdot)$ of its two children, of which $\bar{a}_{t}$ is the left one if $b_{t}=0$ and the right one if $b_{t}=1$ , the other being $\bar{s}_{t}$ . The genuine chain therefore satisfies (2) with $\bar{s}_{t}$ in place of $s_{t}$ , and $\bar{a}_{0}=L_{\mathsf{pos}}$ , $\bar{a}_{32}=M^{0}_{0}=\mathit{rt}$ (Crypto Guide, §“Authentication paths and membership proofs”, Proposition “Completeness”, whose induction this is). The fold on the given path has $a_{0}=v\neq\bar{a}_{0}$ and $a_{32}=\mathit{rt}=\bar{a}_{32}$ . Let $t^{*}$ be the least $t\geq 1$ with $a_{t}=\bar{a}_{t}$ ; it exists, and $a_{t^{*}-1}\neq\bar{a}_{t^{*}-1}$ by minimality. At level $t^{*}-1$ both chains evaluate $\mathsf{MerkleCRH}(32-t^{*},\cdot,\cdot)$ with the running value on the side fixed by $b_{t^{*}-1}$ : the first on $a_{t^{*}-1}$ and $s_{t^{*}-1}$ , the second on $\bar{a}_{t^{*}-1}$ and $\bar{s}_{t^{*}-1}$ . The two $520$ -bit messages hashed there share the prefix $\mathrm{LE}_{10}(31-(32-t^{*}))=\mathrm{LE}_{10}(t^{*}-1)$ , the layer tag of the Crypto Guide’s Proposition “Separation forces within-domain collisions” (§“Layer and domain separation”). They differ in the half that encodes the running value, $\mathrm{LE}_{255}$ being injective on $\mathbb{F}_{p_{\mathsf{Pallas}}}$ , and their values under $\mathsf{MerkleCRH}$ , $a_{t^{*}}=\bar{a}_{t^{*}}$ , agree. If $\mathsf{SinsemillaHash}(D,\cdot)$ returns $\bot$ on either message, that message is the second output. Otherwise both values of $\mathsf{MerkleCRH}$ are values of $\mathsf{SinsemillaHash}(D,\cdot)$ , and the pair is the first output. The genuine chain is computed from $L_{0},\dots,L_{n-1}$ by the recurrence of the tree. A node whose leaves all lie at positions at least $n$ depends only on its layer, so the computation takes a number of evaluations of $\mathsf{MerkleCRH}$ linear in $n+32$ ; the fold takes $32$ more.

(ii) The extraction of (i) is deterministic and defined for every list of leaves, so it applies to leaves that an adversary chose. An adversary that outputs a valid path with $v\neq L_{\mathsf{pos}}$ with probability $\epsilon$ therefore yields an algorithm that outputs, with probability $\epsilon$ , a collision of $\mathsf{SinsemillaHash}(D,\cdot)$ on $520$ -bit messages or a $520$ -bit message with output $\bot$ . Equal values of $\mathsf{SinsemillaHash}$ other than $\bot$ come from hash points that are equal on distinct messages or opposite (Lemma 2.4). Proposition 2.24, parts (i) and (iii), excludes both outputs except with negligible probability, under Assumptions 2.22 and 2.8; hence $\epsilon$ is negligible.

(iii) If $\mathsf{pos}\geq n$ , then $L_{\mathsf{pos}}=2$ , and $v\neq 2$ by Lemma 5.7, so the path is one with $v\neq L_{\mathsf{pos}}$ , which (ii) excludes except with negligible probability. Otherwise $\mathsf{pos}<n$ , and outside the same event $v=L_{\mathsf{pos}}$ , the value appended at position $\mathsf{pos}$ ; the $n$ leaves of the tree that $\mathit{rt}$ roots are those appended through the anchoring block. □

Remark 5.10 (Old anchors).

Appending leaves changes the final treestates of later blocks and of no earlier one. Once a block $B$ is in the chain, its anchor therefore roots one fixed tree: a valid path to it stays valid after later appends, the anchor stays admissible under the anchor rule while $B$ remains in the chain, and Proposition 5.9 applies to it at any later time. A valid path to the anchor of $B$ for an extracted note commitment shows that the commitment was appended in $B$ or earlier, which is what R2 requires. Excluding a second consumption of a note is not the task of the tree, which is append-only (protocol specification, §“Note Commitment Trees”), but that of the nullifier, constructed in “Nullifiers” (§6).

Definition 5.11 (Reorganisation).

A reorganisation is the replacement of the chain’s most recent blocks by a competing branch.

With the height of a block as in §1.1, the tip is the last block of the chain. A reorganisation that removes the block whose final treestate a bundle’s anchor refers to leaves the transaction in violation of the anchor rule on the new chain, unless a block of the new chain that precedes the transaction’s block has the same anchor; to be included in the new chain, the transaction must then be rebuilt against an anchor of that chain. The block $d$ blocks below a tip of height $H$ , the block at height $H-d$ , is removed only by a reorganisation that replaces at least $d+1$ blocks, since a reorganisation that replaces $k$ blocks removes the blocks at heights $H-k+1$ to $H$ (ZIP 315, “Rationale for anchor selection”; ZIP 218, “Anchor selection depth”).

The block target spacing, the intended mean interval between consecutive blocks, is $25$ seconds (ZIP 218, “Block target spacing”).

Remark 5.12 (Recommended anchor depth).

ZIP 315 recommends that a transaction built when the tip is at height $H$ use as its anchor the final treestate of the block at height $H-3$ , three blocks below the tip (ZIP 315, “Anchor selection”); ZIP 218 recommends the same depth of $3$ blocks (“Anchor selection depth”). At the $25$ -second target spacing this depth is $3\times 25=75$ seconds. The depth is a recommendation to the builder of a transaction, not a consensus rule: the anchor rule admits the final treestate of any earlier block.

Remark 5.13 (Anchor choice as public data).

The anchor is published with the bundle. Call the set $\{0,\dots,n-1\}$ of positions of the leaves appended to the tree that an anchor roots the candidate set of the anchor; by Proposition 5.9(iii), a valid path to the anchor for an extracted note commitment has its position in this set, except with negligible probability. A later anchor roots a tree that contains every appended leaf of an earlier one, so its candidate set is at least as large. An anchor at a depth other than the one that other builders of transactions use distinguishes its builder. These two observations are not ZIP 315’s stated rationale for a fixed depth, which is that too small a depth risks invalidation by a reorganisation, that too large a depth prevents recently received notes from being spent, and that a depth varying with the notes spent leaks information about them (ZIP 315, “Rationale for anchor selection”).

5.3 Authentication paths

Construction 5.14 (Authentication path).

Let the pool’s tree hold $n$ leaves, namely the tree that the anchor $\mathit{rt}$ of a block roots, for a block at or after the one that appended the note’s commitment, so that the note position satisfies $\mathsf{pos}<n$ . Write $\mathsf{pos}=\sum_{t=0}^{31}b_{t}2^{t}$ with $b_{t}\in\{0,1\}$ , and $j_{t}:=\lfloor\mathsf{pos}/2^{t}\rfloor$ . Levels $t=0,\dots,31$ count from the leaves: the level- $t$ route node is $M^{32-t}_{j_{t}}$ , a left child if $b_{t}=0$ and a right child if $b_{t}=1$ . The authentication path of $\mathsf{pos}$ is

(s_{0},\dots,s_{31})\in\mathbb{F}_{p_{\mathsf{Pallas}}}^{32},\qquad s_{t}:=M^{% 32-t}_{j_{t}\oplus 1},

the sibling of the level- $t$ route node in the tree of size $n$ , with $j\oplus 1$ the integer $j$ with its lowest bit complemented. Verification of $(v,\mathsf{pos},(s_{0},\dots,s_{31}))$ against $\mathit{rt}$ is the fold (2): the level- $t$ step evaluates $\mathsf{MerkleCRH}(31-t,\cdot,\cdot)$ , whose message carries the prefix $\mathrm{LE}_{10}(t)$ , with the running value on the left if $b_{t}=0$ and on the right if $b_{t}=1$ ; verification accepts if and only if $a_{32}=\mathit{rt}$ , that is, if the triple is a valid path to $\mathit{rt}$ in the sense of Proposition 5.9. In the protocol specification, §“Merkle Path Validity”, the entry $s_{t}$ is the node $M^{h}_{\mathsf{MerkleSibling}(h,\mathsf{pos})}$ with $h=32-t$ .

The genuine path of an appended leaf is accepted: the fold on $(L_{\mathsf{pos}},\mathsf{pos},(s_{0},\dots,s_{31}))$ reproduces the route nodes, $a_{t}=M^{32-t}_{j_{t}}$ for every $t$ , and ends at $M^{0}_{0}=\mathit{rt}$ (Crypto Guide, §“Authentication paths and membership proofs”, Proposition “Completeness”, whose induction applies with the level- $t$ compression $\mathsf{MerkleCRH}(31-t,\cdot,\cdot)$ , as in the proof of Proposition 5.9). A note’s commitment therefore has a valid path to the anchor of every block from the one that appended it onward.

Lemma 5.15 (Authentication paths from public data).

Let the tree hold $n$ leaves, let $\mathsf{pos}<n$ , and let

	$\displaystyle\mathsf{Empty}_{0}$	$\displaystyle:=\mathsf{Uncommitted}^{\mathsf{Orchard}}=2,$
	$\displaystyle\mathsf{Empty}_{t+1}$	$\displaystyle:=\mathsf{MerkleCRH}(31-t,\,\mathsf{Empty}_{t},\,\mathsf{Empty}_{% t})\qquad(0\leq t<32).$

For each level $t$ the entry $s_{t}$ of the authentication path of $\mathsf{pos}$ is as follows.

(i)

If $b_{t}=1$ , then $s_{t}$ is the root of the complete subtree over the positions $[(j_{t}-1)\,2^{t},\ j_{t}\,2^{t})$ , all below $\mathsf{pos}$ ; it is a function of the leaves at those positions alone, and the same in every tree of size greater than $\mathsf{pos}$ .
(ii)

If $b_{t}=0$ , then $s_{t}$ is the root of the subtree over the positions $[(j_{t}+1)\,2^{t},\ (j_{t}+2)\,2^{t})$ , a function of the leaves appended in that range, with $\mathsf{Uncommitted}^{\mathsf{Orchard}}$ at its unused positions; it equals $\mathsf{Empty}_{t}$ when $(j_{t}+1)\,2^{t}\geq n$ .

Hence the authentication path is a deterministic function of $\mathsf{pos}$ and of the first $n$ leaves, which are the values $\mathsf{cmx}$ published by the pool’s Actions in the chain through the anchoring block. A holder of the note who has these leaves computes the path without communicating $\mathsf{pos}$ , and verification needs, besides the path, only the public anchor.

Proof.

By the recurrence of the tree, the node $M^{h}_{i}$ is a function of the leaves at positions $[i\,2^{32-h},\ (i+1)\,2^{32-h})$ , by induction on $32-h$ . Apply this with $h=32-t$ and $i=j_{t}\oplus 1$ , which equals $j_{t}-1$ when $b_{t}=1$ and $j_{t}+1$ when $b_{t}=0$ , since $b_{t}$ is the parity of $j_{t}$ . When $b_{t}=1$ the range ends at $j_{t}\,2^{t}\leq\mathsf{pos}<n$ , so every position in it is appended, and its leaf is fixed once appended because the tree is append-only. When the range starts at or beyond $n$ , every leaf in it is $2$ , and its root is $\mathsf{Empty}_{t}$ by induction on $t$ : a level- $(t+1)$ node over an unused range is $\mathsf{MerkleCRH}(31-t,\cdot,\cdot)$ of two level- $t$ nodes over unused ranges. Positions below $n$ hold the appended values $\mathsf{cmx}$ , published in the chain. □

Refer to caption — Figure 2: A depth- $3$ instance of the note commitment tree of §5.1; the protocol’s tree has depth $32$ . Leaves $L_{0}$ to $L_{5}$ are appended ( $n=6$ ); positions $6$ and $7$ hold $\mathsf{Uncommitted}^{\mathsf{Orchard}}=2$ , so $D=\mathsf{Empty}_{1}$ . The consumed note’s leaf is $L_{2}$ , at position $2$ with bits $b_{0}=0$ , $b_{1}=1$ , $b_{2}=0$ . Its authentication path is $(s_{0},s_{1},s_{2})=(L_{3},A,F)$ , each entry the sibling of the route node at its level. The bold fold $L_{2}\to B\to E\to R$ evaluates $\mathsf{MerkleCRH}$ at each level with the prefix $\mathrm{LE}_{10}(t)$ , shown as tag $t$ , and the running value on the side given by $b_{t}$ ; it ends at the root $R$ , the anchor. By Lemma 5.15, the entry $A$ , left of the route, is the root of a complete subtree and the same at every later anchor; the entry $F$ , right of the route and the root over positions $4$ to $7$ , is a function of the leaves appended at the anchor, with $2$ at unused positions, and changes when $L_{6}$ or $L_{7}$ is appended; the entry $L_{3}$ , right of the route but already appended, is fixed at every later anchor. The boxed subtree enters the path only through its root $F$ . Every entry is computed from $\mathsf{pos}$ and the first $n$ leaves.

Figure 2 shows the construction and Lemma 5.15 on a tree of depth $3$ .

Remark 5.16 (Scope of hiding).

The anchor is public. The position, the consumed note’s $\mathsf{cmx}$ and its authentication path are not fields of the bundle, and the holder of the note computes the path locally (Lemma 5.15): obtaining the path of a particular position from another party would disclose $\mathsf{pos}$ to that party. The candidate set for the consumed note is the candidate set of the anchor (§5.2), the positions of the $n$ appended leaves of the anchored tree. Leaves that an observer knows by other means to be commitments of dummy created notes (§4.4) or of notes already consumed, and other data of the transaction, reduce the effective set, so $n$ alone does not measure it. What an Action reveals is stated in Theorem 12.12 (“Privacy”, §12.4).