VI Wallet Guide: The Zcash wallet layer: keys, transactions, and light-client synchronisation 6 Note discovery 8 Leakage to the light-client server

7 Commitment-tree synchronisation

This section states the tree information that a wallet retains in order to spend its notes. It shows that the witness maintenance of ZIP 307 forces a scan from each note to its anchor; decomposes each note commitment tree at level $16$ into subtrees and a cap built from downloaded subtree roots; shows that a frontier seeds every later witness; defines the information a wallet retains and proves it sufficient; states exactly when a witness is computable; and states the detection of reorganisations and the recovery from them, with the bound on the rollback height, the safety theorem and the correctness theorem of synchronisation.

Throughout, $P$ ranges over the shielded pools $\mathsf{Sapling}$ , $\mathsf{Orchard}$ and $\mathsf{Ironwood}$ , with the chain state $C(h)$ of Definition 6.1, the birthday $B$ of Definition 6.2, and the commitment count $n_{P}(b)$ and end size $S^{P}_{\mathsf{end}}(b)$ of a compact block $b$ (Definition 4.11). Assumption 5.2 is the server assumption; only its clause (a) is used here.

7.1 Witness maintenance by linear scanning

Remark 7.1 (What a spend needs).

A detected note is not yet spendable. A spend needs, besides the note, its position $p$ and the authentication path of $p$ to the anchor of a block at or after the note’s block (Ironwood Guide, §“Authentication paths”, Construction “Authentication path”; anchors as in §“Anchors”, Definition “Treestate and anchor”). By the Ironwood Guide’s Lemma “Authentication paths from public data” (§“Authentication paths”), that path is a function of $p$ and of the first $n$ leaves of the pool’s tree, $n$ being the tree size at the anchor. Path construction and anchor selection are cited, not re-derived; the anchor height is fixed in “Anchors, confirmations, and expiry” (§9). The lemma is stated for the trees of the Orchard protocol; its proof uses only the recurrence of the tree and applies unchanged to the Sapling tree, which has the same depth $32$ and the same layer convention (protocol specification, §“Note Commitment Trees” and §“Merkle Path Validity”). Everything below applies to each pool $P$ separately.

An incremental witness of a note at position $p$ , after $m>p$ leaves have been appended to the pool’s tree, is the information from which the authentication path of $p$ in the tree of size $m$ is computed: the position $p$ , the siblings of the path whose ranges lie below $m$ , and the frontier of the leaves appended after $p$ (ZIP 307, “Local processing”, “Creating and updating note witnesses”; Crypto Guide, §“Append-only and incrementally updatable trees”, Definition “Frontier”).

Construction 7.2 (Linear witness maintenance).

ZIP 307, “Local processing”, “Creating and updating note witnesses”, states the protocol for the Sapling pool and its commitments $\mathsf{cmu}$ ; it applies to each pool with that pool’s commitments, $\mathsf{cmx}$ for Actions. Compact blocks are processed in increasing height, with the order of transactions and outputs preserved. The wallet holds its copy of the pool’s tree as a frontier and one incremental witness per tracked note. For each note commitment $c$ of the block, in order:

(i)

append $c$ to the tree;
(ii)

append $c$ to every held witness;
(iii)

if the output of $c$ is accepted by Definition 4.9, create a witness of it from the current tree.

A witness updated through block $X$ yields the authentication path of its note to the anchor of block $X$ . No ZIP specifies any other tree-maintenance protocol.

Lemma 7.3 (Linear maintenance consumes every commitment).

Under linear witness maintenance, let a note be created in block $h_{n}$ and let $a\geq h_{n}$ . The wallet holds the authentication path of the note to the anchor of block $a$ only after it has processed, in order, every note commitment of the pool in every block from $h_{n}$ through $a$ . It creates the note’s witness only after it holds the tree state at the end of block $h_{n}-1$ , obtained either by processing every earlier block or from a chain state (Definition 6.1). In particular, a wallet restored from a seed spends no note created at $h_{n}$ before it has scanned forward from $h_{n}$ to the anchor.

Proof.

By induction on the processed commitments. Steps (i) and (ii) are the only operations on the tree and the witnesses, and each consumes the next commitment in chain order; step (iii) creates a witness from the current tree, which after the commitment of the note is the tree state at the end of block $h_{n}-1$ followed by the commitments of $h_{n}$ up to that of the note. A witness therefore reflects block $X$ only after every commitment through $X$ has passed through step (ii), and it yields no path to the anchor of $a$ before it reflects block $a$ . □

Remark 7.4 (The retained-information method).

The method of “Subtree roots and the cap” (§7.2) to “Witness readiness” (§7.5) removes the constraint of Lemma 7.3. It replaces per-note witnesses by subtree roots, obtained through the query $\mathsf{SubtreeRoots}$ (Definition 5.10), and a frontier, so that the path of a note needs the commitments of its own subtree only. The method is designed but unspecified (Definition 1.1): no ZIP specifies it or the subtree-root query.

7.2 Subtree roots and the cap

Definition 7.5 (Subtrees and the cap).

Fix a pool $P$ and its note commitment tree of depth $32$ , with nodes $M^{h}_{i}$ in layer $h$ counted from the root (Ironwood Guide, §“The Merkle hash and the tree”, Definition “Note commitment tree”; protocol specification, §“Merkle Path Validity”). Let $\mathsf{MerkleCRH}_{P}$ be its Merkle hash, $\mathsf{MerkleCRH}^{\mathsf{Sapling}}$ for Sapling and $\mathsf{MerkleCRH}^{\mathsf{Orchard}}$ for either Orchard-protocol pool, and $\mathsf{Uncommitted}_{P}$ its unused-leaf value, $\mathsf{Uncommitted}^{\mathsf{Sapling}}$ or $\mathsf{Uncommitted}^{\mathsf{Orchard}}=2$ (protocol specification, §“Constants”). For $0\leq l\leq 32$ and $0\leq i<2^{32-l}$ , the node at level $l$ and index $i$ is

\mathsf{node}(l,i):=M^{32-l}_{i},

the root over the positions $[\,i\,2^{l},\ (i+1)\,2^{l})$ ; its range is that interval. The nodes satisfy the first line below, and the second defines the values $\mathsf{Empty}_{P,l}$ :

	$\displaystyle\mathsf{node}(l+1,i)$	$\displaystyle=\mathsf{MerkleCRH}_{P}(31-l,\,\mathsf{node}(l,2i),\,\mathsf{node% }(l,2i+1)),$
	$\displaystyle\mathsf{Empty}_{P,0}$	$\displaystyle:=\mathsf{Uncommitted}_{P},\qquad\mathsf{Empty}_{P,l+1}:=\mathsf{% MerkleCRH}_{P}(31-l,\,\mathsf{Empty}_{P,l},\,\mathsf{Empty}_{P,l})$

for $0\leq l<32$ . Each $\mathsf{Empty}_{P,l}$ is the root over a range of unused leaves (Ironwood Guide, §“Authentication paths”, Lemma “Authentication paths from public data”, for Orchard-protocol trees; the same recurrence for Sapling). Subtree $i$ is the node $\mathsf{node}(16,i)$ with its range, and its completeness, root and completing height are those of Definition 5.8. There are $2^{32}/2^{16}=2^{16}=65536$ subtrees, with indices $0$ to $2^{16}-1$ , each over $65536$ positions. The subtree of a position $p$ is $\sigma(p):=\lfloor p/2^{16}\rfloor$ . The cap is the tree formed by the nodes $\mathsf{node}(l,i)$ with $16\leq l\leq 32$ ; its leaves are the $2^{16}$ level- $16$ nodes, and its root is the root $\mathsf{node}(32,0)$ of the tree. The same geometry holds for the Sapling, Orchard-pool and Ironwood-pool trees.

Construction 7.6 (The cap over level-16 values).

For a pool $P$ and a list $r_{0},\dots,r_{2^{16}-1}$ of level- $16$ values, the cap over $(r_{i})$ is the append-only Merkle tree of depth $16$ (Crypto Guide, §“Append-only and incrementally updatable trees”, Definition “Append-only Merkle tree”) whose cap-level- $0$ labels are the $r_{i}$ , whose empty-leaf value is $\bot_{0}:=\mathsf{Empty}_{P,16}$ , and whose combination of two cap-level- $u$ labels into a cap-level- $(u+1)$ label is

\mathsf{NodeHash}_{u+1}:=\mathsf{MerkleCRH}_{P}(15-u,\,\cdot,\,\cdot)\qquad(0% \leq u<16),

the tree’s Merkle hash at level $u+16$ , that is, in layer $31-(u+16)$ . Complete subtree roots obtained from $\mathsf{SubtreeRoots}(P,i)$ enter at cap positions $i,i+1,\dots$ in index order.

Lemma 7.7 (Cap root equals the tree root).

Let the tree of $P$ hold $n$ leaves, and for each $i$ let $r_{i}:=\mathsf{node}(16,i)$ of that tree: the complete root when $(i+1)\,2^{16}\leq n$ ; the root over the appended leaves of subtree $i$ padded with $\mathsf{Uncommitted}_{P}$ when $i\,2^{16}<n<(i+1)\,2^{16}$ ; and $\mathsf{Empty}_{P,16}$ when $i\,2^{16}\geq n$ . Then the cap-level- $u$ node of index $i$ of the cap over $(r_{i})$ equals $\mathsf{node}(16+u,i)$ for $0\leq u\leq 16$ . In particular the root of the cap equals $\mathsf{node}(32,0)$ , the anchor of the pool for that tree (Ironwood Guide, §“Anchors”, Definition “Treestate and anchor”).

Proof.

Induction on $u$ . For $u=0$ the claim is the definition of $r_{i}$ . For the step, the cap combines the cap-level- $u$ nodes of indices $2i$ and $2i+1$ with $\mathsf{MerkleCRH}_{P}(15-u,\cdot,\cdot)$ ; by the induction hypothesis they are $\mathsf{node}(16+u,2i)$ and $\mathsf{node}(16+u,2i+1)$ , and the recurrence of the tree gives $\mathsf{node}(17+u,i)=\mathsf{MerkleCRH}_{P}(31-(16+u),\dots)$ , in the same layer $15-u$ . The value $r_{i}=\mathsf{Empty}_{P,16}$ for an unused subtree follows from the leaf rule, by which unused positions hold $\mathsf{Uncommitted}_{P}$ (Ironwood Guide, §“The Merkle hash and the tree”, Definition “Note commitment tree”, item “Leaves”), and from the induction in the proof of the Ironwood Guide’s Lemma “Authentication paths from public data” (§“Authentication paths”). The empty labels of the cap, $\bot_{u+1}:=\mathsf{NodeHash}_{u+1}(\bot_{u},\bot_{u})$ , are then $\mathsf{Empty}_{P,16+u}$ by the same induction, so the cap’s labels of empty ranges agree with the tree’s. □

Lemma 7.8 (Path decomposition at level 16).

Let the tree hold $n$ leaves, let $p<n$ and $\sigma:=\sigma(p)$ , and let $(s_{0},\dots,s_{31})$ be the authentication path of $p$ (Ironwood Guide, §“Authentication paths”, Construction “Authentication path”), $s_{t}=\mathsf{node}(t,j_{t}\oplus 1)$ with $j_{t}:=\lfloor p/2^{t}\rfloor$ .

(i)

For $t<16$ , the range of $s_{t}$ lies inside subtree $\sigma$ , and $s_{t}$ is a function of the leaves of subtree $\sigma$ below $n$ ; it is $\mathsf{Empty}_{P,t}$ if its range starts at or beyond $n$ .
(ii)

For $t\geq 16$ , $s_{t}$ is the cap node of cap level $t-16$ and index $j_{t}\oplus 1$ , a function of the level- $16$ nodes $r_{i}$ with $i$ in its range and $i\neq\sigma$ . These are complete subtree roots; the root over the incomplete subtree $\lfloor(n-1)/2^{16}\rfloor$ when $n$ is not a multiple of $2^{16}$ , a function of the frontier of the tree after its $n$ -th leaf; and $\mathsf{Empty}_{P,16}$ .

Hence the leaves of subtree $\sigma$ , the roots of the complete subtrees other than $\sigma$ and the frontier of the tree of size $n$ suffice for the path, and the wallet needs the commitments of no subtree other than $\sigma$ .

Proof.

The range of $s_{t}$ is $[\,(j_{t}\oplus 1)\,2^{t},\ ((j_{t}\oplus 1)+1)\,2^{t})$ , and $s_{t}$ is a function of the leaves in its range (Ironwood Guide, §“Authentication paths”, Lemma “Authentication paths from public data”, whose proof shows this for every node). For $t<16$ the range lies inside $[\,\sigma\,2^{16},\ (\sigma+1)\,2^{16})$ , since $j_{t}$ and $j_{t}\oplus 1$ have the same quotient by $2^{16-t}$ , which is $\sigma$ . For $t\geq 16$ the range is a union of whole subtree ranges, and it excludes $\sigma$ because $j_{t}\oplus 1\neq j_{t}$ and $\lfloor\sigma/2^{t-16}\rfloor=j_{t}$ ; Lemma 7.7 computes $s_{t}$ from the level- $16$ nodes of its range. The root of the incomplete subtree is the fold, with the $\mathsf{Empty}_{P,\cdot}$ values as right siblings, of the carries below level $16$ of the frontier of the tree of size $n$ , one for each set bit of $n\bmod 2^{16}$ (Crypto Guide, §“Append-only and incrementally updatable trees”, Proposition “Incremental append in logarithmic time”, proof). □

Construction 7.9 (Acquisition of subtree roots).

At each synchronisation the wallet queries $\mathsf{SubtreeRoots}(P,0)$ for each pool $P\in\{\mathsf{Sapling},\mathsf{Orchard},\mathsf{Ironwood}\}$ (Table 4) and records, for each complete subtree $i$ , the pair (root, completing height) of Definition 5.8; the roots enter the cap at index $i$ (Construction 7.6). The roots are trusted under clause (a) of Assumption 5.2: no root is checked against a header, and a root is verified only if the wallet also computes it from scanned commitments (Proposition 5.3, item (iv)). The acquisition is designed but unspecified (Definition 1.1).

7.3 Frontiers as scan seeds

Lemma 7.10 (A frontier suffices to continue the tree).

Let $F$ be the frontier of the tree of pool $P$ after block $h-1$ (Crypto Guide, §“Append-only and incrementally updatable trees”, Definition “Frontier”), holding $m$ leaves, with carries $f_{t}$ for the set bits $t$ of $m$ , and let $c_{m},c_{m+1},\dots$ be the note commitments of $P$ in blocks $h,h+1,\dots$ in chain order. From $F$ and these commitments alone the wallet computes

(i)

the root of the tree after every block $b\geq h-1$ , and
(ii)

for every position $p\geq m$ appended by a block at most $b$ , the authentication path of $p$ to that root.

The commitments at positions below $m$ are not needed. Consequently the chain state $C(B-1)$ stored with the birthday $B$ of an account (Definitions 6.1 and 6.2) seeds every later witness of the account.

Proof.

(i) Repeated application of the Crypto Guide’s Proposition “Incremental append in logarithmic time” (§“Append-only and incrementally updatable trees”), each append producing the next frontier and root.

(ii) By the Ironwood Guide’s Lemma “Authentication paths from public data” (§“Authentication paths”), a right sibling of $p$ ( $b_{t}=0$ ) has a range above $p\geq m$ , hence over later leaves or unused positions, and is computed from the $c_{q}$ with $\mathsf{Empty}_{P,\cdot}$ values. A left sibling ( $b_{t}=1$ ) has the range $[\,(j_{t}-1)\,2^{t},\ j_{t}\,2^{t})$ . If the range starts at or above $m$ , it is computed from later leaves. If it lies below $m$ , then $j_{t}\,2^{t}\leq m$ and $j_{t}=\lfloor p/2^{t}\rfloor\geq\lfloor m/2^{t}\rfloor$ give $j_{t}=\lfloor m/2^{t}\rfloor$ , which is odd since $b_{t}=1$ ; so bit $t$ of $m$ is set and the range is the block of the frontier at level $t$ , whose root is the carry $f_{t}$ . If the range contains $m$ , its part below $m$ is the union of the frontier’s blocks at the set bits of $m$ below $t$ , since the range is aligned at level $t$ ; its root is the fold of those carries with the later leaves of the range. □

Definition 7.11 (Seeded batch).

A batch of consecutive blocks $b_{0},\dots,b_{k}$ , of heights increasing by one, is seeded with the chain state $C(h_{s})$ of the block preceding $b_{0}$ (Definition 6.1), with frontiers $F_{P}(h_{s})$ of sizes $m_{P}(h_{s})$ . Before any retained information is modified, the wallet accepts the batch only if $b_{0}$ continues the seed in the sense of Definition 6.10: $\mathrm{height}(b_{0})=h_{s}+1$ , $\mathsf{prevHash}(b_{0})=\mathsf{hash}_{h_{s}}$ , and $m_{P}(h_{s})+n_{P}(b_{0})=S^{P}_{\mathsf{end}}(b_{0})$ for each pool $P$ (Definition 4.2, Lemma 4.12); each later block is checked against its predecessor in the same way. A violation is a continuity error (Definition 6.10), handled in “Reorganisation detection and recovery” (§7.6). Under clause (a) of Assumption 5.2, the root of each seed frontier $F_{P}(h_{s})$ equals the anchor of block $h_{s}$ in $P$ ; nothing else checks it, since the abstract format does not guarantee a header (Proposition 5.3). The per-block sizes are designed but unspecified (Definition 4.2, Remark 4.1).

7.4 The information a wallet retains

Definition 7.12 (Retained tree information).

The retained tree information of a wallet is adjoined to its note state (Definition 6.7). It comprises a finite set $\mathcal{H}$ of heights, the retained block boundaries, chosen by the wallet and the same for every pool, which contains $B-1$ , and for each pool $P$ :

(a)

for each unspent note of the wallet in $P$ , its position $p$ and its leaf, and each sibling $s_{t}$ with $t<16$ of the path of $p$ (Lemma 7.8(i)) from the moment its range lies wholly below the tree size; such a node is a function of appended leaves and does not change thereafter (Ironwood Guide, §“Authentication paths”, Lemma “Authentication paths from public data”, items (i) and (ii) and proof);
(b)

the complete subtree roots with their completing heights (Definition 5.8), and the frontier of the tree after the last scanned block;
(c)

for each $r\in\mathcal{H}$ , the chain state $C(r)$ , whose frontiers are the tree states after block $r$ : the anchors of the blocks in $\mathcal{H}$ are the wallet’s candidate anchors, and the heights in $\mathcal{H}$ are its rollback points.

The rollback window is the span of $\mathcal{H}\setminus\{B-1\}$ . Because $\mathcal{H}$ is common to the pools, a rollback restores all trees to one block. Any other node may be discarded once no retained path needs it. An anchor older than the window is retained only by explicit choice: ZIP 318, “Anchor-height bucketing and cohorts”, requires the anchor of each migration transaction to be the tree state at a shared network-wide boundary height, so a wallet that follows it retains those boundaries; any other retention of old anchors is wallet policy. The definition fixes information, not a representation, and is designed but unspecified (Definition 1.1).

Proposition 7.13 (Sufficiency of the retained information).

Fix a pool $P$ .

(i)

Let $p$ be the position of a retained note, $\sigma:=\sigma(p)$ , and $A\in\mathcal{H}$ a retained block boundary with tree size $n>p$ . If the blocks that hold the commitments of subtree $\sigma$ below $n$ and at or above the birthday seed are scanned, the authentication path of $p$ to the anchor of $A$ is computable from the retained information.
(ii)

For every height $r$ at which the wallet holds a chain state $C(r)$ for all pools, with $n_{r}(P):=m_{P}(r)$ the size of the tree of $P$ after $r$ , discard every retained node over a range that meets $[n_{r}(P),2^{32})$ , every note position at or above $n_{r}(P)$ , every subtree root with completing height above $r$ and every $C(r^{\prime})$ with $r^{\prime}>r$ , and take the frontier of $C(r)$ as the frontier after the last scanned block. The result is a function of the blocks at heights at most $r$ , and it is information that a wallet which scanned only those blocks retains.

Proof.

(i) By Lemma 7.8, each sibling $s_{t}$ is of one of the following sorts. A sibling whose range lies below $n$ is the same node at every later tree state: for $t<16$ it is in item (a), or, where its range lies below the birthday seed, it is a carry of the seed frontier (Lemma 7.10); for $t\geq 16$ it is a cap node over complete subtree roots of item (b) (Lemma 7.7). The sibling ranges are pairwise disjoint, so at most one contains $n-1$ without lying below $n$ . That sibling is the root over its range, whose part below $n$ is the union of the blocks of the frontier of $C(A)$ at the set bits of $n$ below its level; it is the fold of those carries with $\mathsf{Empty}_{P,\cdot}$ values, and the frontier of $C(A)$ is in item (c). A sibling whose range starts at or beyond $n$ is $\mathsf{Empty}_{P,t}$ .

(ii) After the discards, every retained node lies over a range below $n_{r}(P)$ and is a function of the leaves appended through block $r$ (Ironwood Guide, §“Authentication paths”, Lemma “Authentication paths from public data”); every retained subtree root has completing height at most $r$ , and is likewise such a function; the retained chain states are those at heights at most $r$ ; and the frontier after $r$ is that of $C(r)$ , which the wallet holds for every pool at the same $r$ . A wallet that scanned only the blocks at most $r$ can hold each of these items, and item (a) is satisfied, since a sibling whose range is not below $n_{r}(P)$ is not yet due. □

7.5 Witness readiness

Theorem 7.14 (Witness from retained information).

Let $A$ be a retained block boundary with tree size $n$ in pool $P$ , let $p$ be a position, $\sigma:=\sigma(p)$ , and let $(s_{0},\dots,s_{31})$ be the authentication path of $p$ to the anchor of $A$ . If $p\geq n$ , the Ironwood Guide’s Construction “Authentication path” (§“Authentication paths”) defines no path, and by its Proposition “Membership soundness” (§“Anchors”), item (iii), no valid path to that anchor with position $p$ exists, except with negligible probability, for the Orchard-protocol pools; for Sapling, by the same argument under the collision resistance of $\mathsf{PedersenHash}$ that the protocol specification requires of $\mathsf{MerkleCRH}^{\mathsf{Sapling}}$ (§“ $\mathsf{MerkleCRH}^{\mathsf{Sapling}}$ Hash Function”), since $\mathsf{Uncommitted}^{\mathsf{Sapling}}$ is not in the range of $\mathsf{NoteCommit}^{\mathsf{Sapling}}$ (§“Windowed Pedersen commitments”). Otherwise the path is computable from the wallet’s information if every $s_{t}$ is of one of the following kinds:

(a)

$t<16$ , and $s_{t}$ is computable from the commitments of subtree $\sigma$ below $n$ that the wallet has scanned or holds summarised in a carry, whose range lies below $n$ , of a seed frontier (Lemma 7.10) or in the frontier of $C(A)$ ;
(b)

$t=16$ , and $s_{t}$ is a complete subtree root that the wallet holds;
(c)

$t\geq 16$ , and $s_{t}$ is a cap node computed from held complete roots, carries at levels at least $16$ of the frontier of $C(A)$ or, with range below $n$ , of a seed frontier, $\mathsf{Empty}_{P,16}$ and, where its range meets the incomplete subtree, the root over that subtree’s leaves below $n$ , computed from the frontier of $C(A)$ ;
(d)

the range of $s_{t}$ starts at or beyond $n$ , and $s_{t}=\mathsf{Empty}_{P,t}$ ;
(e)

$t\geq 16$ , and $s_{t}$ is a carry of the frontier of $C(A)$ or a carry, whose range lies below $n$ , of a seed frontier.

Proof.

Kinds (a) to (d) are the sorts of sibling in the proof of Proposition 7.13(i), extended in kind (c) by frontier carries, and a sibling of kind (e) is a retained node. □

Example 7.15 (Kinds of the siblings of one path).

Let $p=65537$ , so $\sigma=1$ , and let the anchor’s tree hold $n=471098=7\cdot 65536+12346$ leaves, so that subtrees $0$ to $6$ are complete and subtree $7$ is incomplete. The siblings $s_{0},\dots,s_{15}$ are of kind (a); $s_{16}$ , the root of subtree $0$ , is of kind (b); $s_{17}$ , over subtrees $2$ and $3$ , and $s_{18}$ , over subtrees $4$ to $7$ , which meets the incomplete subtree, are of kind (c); and $s_{19},\dots,s_{31}$ , whose ranges start at $8\cdot 65536$ or beyond, are of kind (d).

Definition 7.16 (Block extent of a subtree).

For pool $P$ and subtree $s$ , let $c_{P}(s)$ be the completing height of subtree $s$ (Definition 5.8), and let $c_{P}(-1)$ be the activation height of $P$ . The block extent of subtree $s$ is the interval of heights $[\max(c_{P}(s-1),B),\ c_{P}(s)]$ , both ends included, the part below $B$ being summarised by the chain state $C(B-1)$ (Lemma 7.10); for the incomplete last subtree the interval ends at the anchor height. After detecting a note at position $p$ , the wallet scans the extent of subtree $\sigma(p)$ beyond the ranges it has already scanned. The incomplete subtree of every pool is covered by the range from $\max(B,h_{\mathsf{c}})$ to the tip, where $h_{\mathsf{c}}$ is the least, over the pools, of the completing height of the pool’s last complete subtree, or of the pool’s activation height if it has none.

The start of an extent is inclusive because the completing block of subtree $s-1$ may also hold the first commitments of subtree $s$ ; the positions within that block are fixed by Lemma 4.12.

Proposition 7.17 (Readiness of a witness).

Let a note of pool $P$ lie at position $p$ , $\sigma:=\sigma(p)$ , and let the anchor block $A$ , of height $a$ , have tree size $n>p$ and $\kappa:=\lfloor n/2^{16}\rfloor$ complete subtrees. The witness of $p$ at $A$ is computable if

(1)

the blocks of subtree $\sigma$ are scanned from the start of its extent (Definition 7.16) up to $a$ , or through its completing height if $\sigma<\kappa$ ;
(2)

the wallet holds the root of every complete subtree $i<\kappa$ with $i\neq\sigma$ , including those after $\sigma$ ; and
(3)

the frontier of $C(A)$ is retained, which scanning the extent of subtree $\kappa$ through $a$ yields when $n$ is not a multiple of $2^{16}$ .

Condition (2) can be weakened through frontier carries: every complete subtree $i\neq\sigma$ lies under a sibling of the path of $p$ , and the root of subtree $i$ is not needed when its range lies inside a carry, at a level at least $16$ and at most that of the sibling, of the frontier of $C(A)$ or, provided the carry’s range lies below $n$ , of a seed frontier. Note eligibility, anchor choice and confirmation depth are separate conditions (“Spendable notes”, §9.5).

Proof.

Each condition supplies one kind of Theorem 7.14: condition (1) kind (a); condition (2) kind (b) and the complete part of kind (c); condition (3) the incomplete part of kind (c). Kind (d) needs nothing. For condition (3), the carries of the frontier at levels $t\geq 16$ are cap nodes over complete roots, and those below level $16$ are functions of the leaves of subtree $\kappa$ below $n$ , appended in its extent. For the last claim, the ranges of $s_{16},\dots,s_{31}$ partition the subtree indices other than $\sigma$ ; if the range of subtree $i$ lies inside such a carry, which is the same node at $A$ , its range lying below $n$ , the sibling over it is that carry, of kind (e), or a cap node computed from it, of kind (c), without the root of subtree $i$ . □

Remark 7.18 (Scheduling).

Scanning the tip range and the extents of the subtrees of found notes before historic ranges is a priority rule of wallet policy, designed but unspecified (Definition 1.1). The order of range requests is observable by the server (“Leakage of range queries”, §8.3).

Corollary 7.19 (Witnesses under any scan order).

Under the hypotheses of Lemma 6.13, a schedule of ranges that covers $[B,T]$ in any order yields, for every note and every retained anchor, the witness of a scan in increasing height from $B$ , provided a note enters a witness only once the extent of its subtree (Definition 7.16) is scanned up to the anchor and the conditions of Proposition 7.17 hold.

Proof.

By the Ironwood Guide’s Lemma “Authentication paths from public data” (§“Authentication paths”), the path is a function of the position and of the leaves below $n$ , which do not depend on the scan order. Positions are local to their blocks by Lemma 4.12, and the detection of the note is order-independent by Lemma 6.13. Once the stated extents are scanned, Theorem 7.14 makes the path computable. □

Refer to caption — Figure 3: A note commitment tree cut at level $16$ , drawn with eight subtrees in place of $2^{16}$ and the cap above them compressed to three levels. Subtrees $0$ and $2$ are complete, subtree $\sigma=1$ holds the note at position $p$ , subtree $\kappa=3$ is incomplete at the anchor’s tree size $n$ , and subtrees $4$ to $7$ are unused. The route of $p$ to the anchor is drawn in red. Its siblings are marked by the kind of Theorem 7.14 and the source that supplies them: the siblings $s_{0},\dots,s_{15}$ inside subtree $\sigma$ , from its scanned leaves (a); $s_{16}$ , a downloaded complete subtree root (b); $s_{17}$ , a cap node over a complete root and the root of subtree $\kappa$ computed from the frontier after $A$ (c); and $s_{18}$ , the empty root beyond $n$ (d). The split of the path at level $16$ is Lemma 7.8.

Remark 7.20 (Cost of a restored wallet).

A restored wallet seeds each tree from the chain state $C(B-1)$ (Lemma 7.10), holds one root per complete subtree (Construction 7.6), and scans for witnesses only the extents of the subtrees of its notes and the tip range, instead of replaying the tree from the pool’s first block. By Proposition 7.17, the witness of a found note is ready once those ranges are scanned. The trial decryption of every block from $B$ onward (Proposition 6.17) remains, and so does the scanning of the extents.

7.6 Reorganisation detection and recovery

Remark 7.21 (What a reorganisation invalidates).

A reorganisation (Ironwood Guide, §“Anchors”, Definition “Reorganisation”) makes three kinds of wallet information wrong: the transactions of the wallet mined in replaced blocks become unmined; the anchors of replaced blocks vanish; and tree information over positions appended in replaced blocks no longer describes the chain.

Construction 7.22 (Detection of a reorganisation).

Each synchronisation after the first requests blocks from its previously synchronised height $X$ inclusive and checks that the hash of the received block $X$ equals the stored one; a mismatch implies that block $X$ was orphaned by a reorganisation (ZIP 307, “Client-server interaction”, phases B and D). This volume extends the check to every block and to both sides of every range boundary (Definition 6.10). Failure of the continuity predicate is a continuity error and triggers recovery (Construction 7.24). A malformed field, or a tree size that is absent, outside $[0,2^{32}]$ or below the block’s own commitment count (Lemma 4.12(b)), is an error of the response and triggers none. The extension beyond ZIP 307’s comparison is designed but unspecified (Definition 1.1).

Definition 7.23 (Rollback to a height).

Rollback to a height $r$ at which the wallet holds a chain state $C(r)$ consists of the following changes.

(i)

The chain state of the wallet becomes $C(r)$ , and each pool’s retained tree information becomes that of Proposition 7.13(ii) for $r$ .
(ii)

Every transaction mined above $r$ is marked unmined. The spend marks that such transactions set, on shielded notes and on transparent outputs, are cleared, and the nullifier of each note so unmarked returns to the tracked set $W_{P}$ of its pool.
(iii)

Scan results above $r$ are discarded: the unlinked nullifiers of $R_{P}$ revealed above $r$ , and the scanned ranges above $r$ , so that the scanned heights of Definition 6.11 are at most $r$ . A note whose creating transaction is now unmined loses its position and, for Sapling, its nullifier, which depends on the position; both are derived again if a later scan detects the note.
(iv)

The knowledge of rule (R4) of Definition 6.4 is cut back as that rule states; the evidence of rule (R2) stands.
(v)

Local-only data is kept: sent and received notes stay recorded, since the memos and transactions that the wallet created may be unrecoverable from the chain, while a note whose transaction is unmined is excluded from balances and from spendability (“Spendable notes”, §9.5).

Construction 7.24 (Recovery from a continuity error).

Let $k\geq 2$ be an offset, a wallet parameter. On a continuity error at height $e$ , that is, when a block of height $e$ fails Definition 6.10 against the wallet’s chain state $C(e-1)$ , the wallet runs the following steps.

(1)

If $e-k<B-1$ , it obtains $C^{\prime}(B-1):=\mathsf{TreeState}(B-1)$ , replaces its stored chain state at $B-1$ by $C^{\prime}(B-1)$ , rolls back to $B-1$ (Definition 7.23), and goes to step (4).
(2)

Otherwise let $r$ be the greatest height with $B-1\leq r\leq e-k$ that is a retained block boundary ( $r\in\mathcal{H}$ ) or at which the wallet has recorded the hash of its scanned block. The height $B-1$ qualifies, since $B-1\in\mathcal{H}$ .
(3)

If $r\in\mathcal{H}$ , the wallet rolls back to $r$ . Otherwise it obtains $C^{\prime}(r):=\mathsf{TreeState}(r)$ (Definition 6.1), trusted under clause (a) of Assumption 5.2. If the hash of $C^{\prime}(r)$ equals the recorded hash, the wallet takes the frontiers of $C^{\prime}(r)$ as its tree states after $r$ , discards every retained node over a position at or above their sizes, and rolls back to $r$ . If the hashes differ, its block $r$ is off the server’s chain, and it repeats step (1) with $e:=r+1$ .
(4)

It restarts synchronisation from the query $\mathsf{Tip}()$ .

A fetched chain state extends the depth to which the wallet recovers beyond its rollback window, but only at a height whose hash the wallet has recorded: without that comparison, a fetched chain state cannot show that the wallet’s blocks at most $r$ lie on the server’s chain, and results from replaced blocks below $r$ would survive. The construction is designed but unspecified (Definition 1.1).

Proposition 7.25 (Recovery reaches the fork).

Assume clause (a) of Assumption 5.2, let the server’s best chain be unchanged during recovery, and exclude collisions of the block hash. Let the wallet’s scanned heights below $e$ form the interval $[B,e-1]$ , as in a scan in increasing height. The wallet’s block at a height $h\in[B-1,e-1]$ is the block it scanned at $h$ , or for $h=B-1$ the block of its stored $C(B-1)$ . The fork point $h_{\mathsf{f}}$ is the greatest $h\in[B-1,e-1]$ at which the wallet’s block is the server’s block at $h$ , and $h_{\mathsf{f}}<B-1$ if there is none. Agreement at a height implies agreement at every lower height of $[B-1,e-1]$ : the wallet’s blocks are linked by the checks of Definition 6.10, and each header contains the hash of its parent (protocol specification, §“Block Header Encoding and Consensus”).

(i)

A continuity error at $e$ implies $h_{\mathsf{f}}\leq e-2$ .
(ii)

Repeated recovery by Construction 7.24 strictly decreases the rollback height $r$ until $r\leq h_{\mathsf{f}}$ , or until step (1) replaces the stored chain state at $B-1$ ; after either, no continuity error recurs.
(iii)

No offset below $2$ guarantees progress: a rollback to $e-1$ keeps the orphaned block, and the next scan fails again at $e$ .

Proof.

(i) Under clause (a) the server’s block $e$ has the requested height, so the failing clause of Definition 6.10 is (ii) or (iii). The server’s block $e$ has as parent its chain’s block $e-1$ , and its sizes are functions of that chain’s prefix (Lemma 4.12(a)). If the wallet’s block $e-1$ were the server’s block $e-1$ , its hash and its sizes, which the wallet computed from the same prefix, would satisfy both clauses. So the chains disagree at $e-1$ , and $h_{\mathsf{f}}\leq e-2$ .

(ii) Consider one recovery, with rollback height $r\leq e-k\leq e-2$ . If $r$ is a retained boundary and $r>h_{\mathsf{f}}$ , the wallet’s block $r$ is off the server’s chain, so the server’s block $r+1$ , whose $\mathsf{prevHash}$ is the hash of the server’s block $r$ , fails continuity at $e^{\prime}=r+1$ , and the next rollback height is at most $e^{\prime}-2<r$ . If $r$ is a recorded height and the hashes differ, step (3) repeats with $e:=r+1$ and the next height is at most $r+1-k<r$ . If the hashes agree, $r\leq h_{\mathsf{f}}$ by the definition of the fork point. Heights are bounded below by $B-1$ , and a rollback height that would lie below it is replaced by step (1). Once $r\leq h_{\mathsf{f}}$ , the wallet’s block $r$ is on the server’s chain, and every later block of that chain continues its predecessor. After step (1) the wallet’s chain state at $B-1$ is the server’s and every result above it is discarded, so the same holds.

(iii) After a rollback to $e-1$ the wallet’s block $e-1$ is unchanged, and by (i) it is off the server’s chain; the server’s block $e$ fails against it again. □

Theorem 7.26 (Reorganisation safety).

Under the hypotheses of Proposition 7.25, recovery by Construction 7.24 ends at a height $r$ such that every block of the wallet at most $r$ is a block of the server’s chain: either a retained boundary or a recorded height $r\leq h_{\mathsf{f}}$ , the latter with the chain state $\mathsf{TreeState}(r)$ , or $r=B-1$ with the chain state $\mathsf{TreeState}(B-1)$ . Scanning the server’s chain from $r+1$ then yields the note state and the retained tree information of a scan of that chain from the birthday, with local-only data kept.

Proof.

Proposition 7.25 gives the end height $r$ and its property. After the rollback, the retained information is a function of the blocks at most $r$ (Proposition 7.13(ii), Definition 7.23), and those blocks are shared by both chains; where a fetched chain state is used, its frontiers are those of the server’s chain under clause (a). Theorem 6.14 and Lemma 7.10 then apply to the server’s chain from $r+1$ , seeded with $C(r)$ . □

Theorem 7.27 (Correctness of synchronisation).

Assume clause (a) of Assumption 5.2 and exclude collisions of the block hash. Let the server’s best chain be unchanged from some time on, the final chain, and let $T$ be the height of a tip of the final chain that the wallet obtains after that time. Let the wallet

(1)

check continuity before applying the results of a range (Definition 6.10), on both sides of every range boundary;
(2)

retain unlinked nullifiers as Lemma 6.12 requires;
(3)

take positions from consistent sizes (Lemma 4.12);
(4)

recover from every continuity error by Construction 7.24, scanning a height again only after a rollback below it;
(5)

enter a note into a witness only once the extent of its subtree is scanned up to the anchor (Definition 7.16);
(6)

scan the range that contains $T$ after obtaining $T$ , with continuity checked at its lower boundary (Definition 6.10), and discard scan results above $T$ ; and
(7)

hold, as its complete subtree roots, those returned by a $\mathsf{SubtreeRoots}$ query made after obtaining $T$ , restricted to completing height at most $T$ .

If, after its last rollback, its scanned ranges cover $[B,T]$ , in any order, the wallet holds the note state and the retained tree information of a scan of the final chain in increasing height from $B$ .

Proof.

The theorem composes earlier results and adds no mechanism. By (6) the range that contains $T$ was requested after the tip query that returned $T$ , so under clause (a) the wallet’s block $T$ is that of the final chain. By (1), each block of $[B,T]$ was checked against the wallet’s chain state of its predecessor, and by (4) no height below it was scanned again afterwards without a rollback that also discarded the block; so the wallet’s blocks of $[B-1,T]$ are linked by $\mathsf{prevHash}$ , and by the hash chain of the headers each of them is the final chain’s block at its height. By (4) a height is scanned again only after a rollback below it, which discards the earlier result at that height (Definition 7.23 (iii)), so every kept result of $[B,T]$ is that of the wallet’s current block; by (6) no result above $T$ is kept. The scan of $[B,T]$ is therefore one of the final chain without a continuity error. By (7) and clause (a), the retained subtree roots are those of the final chain with completing height at most $T$ . Lemma 6.13 gives the note state of the scan in increasing height, Corollary 7.19 the witnesses, and Theorem 6.14 characterises the notes found. □

Remark 7.28 (The rollback window).

Consensus bounds no reorganisation depth, and node rollback windows are local policy (Consensus Guide, §“Reorg rails, maturity, and the finality floor”). ZIP 307, “Local processing”, advises caching tree and witness state for $100$ recent blocks, on the ground that no full node rolls back the chain by more than $100$ blocks. That ground no longer holds: ZIP 218, “Block-count-based constants”, recommends a node rollback limit of $600$ blocks at its $25$ -second target spacing and keeps coinbase maturity at $100$ blocks, and neither figure bounds the window of a wallet. The depth that a wallet repairs from its retained information is the span of its retained block boundaries, a wallet parameter; a chain state fetched by $\mathsf{TreeState}$ at a height whose hash the wallet has recorded extends it under clause (a) of Assumption 5.2 (Construction 7.24).