VI Wallet Guide: The Zcash wallet layer: keys, transactions, and light-client synchronisation 5 The light-client service 7 Commitment-tree synchronisation

6 Note discovery

This section states the protocol by which a wallet reconstructs its notes from the chain. It fixes the chain state and the account birthday that bound the scan, the keys an account is scanned with under the rules of ZIP 326, the note state of a wallet and the scan of one compact block that updates it, the continuity predicate and the conditions under which a scan in any order is correct, the theorems of sound and complete discovery and of recovery from the seed, and the work that scanning costs. The tree information a wallet retains for its witnesses is the subject of “Commitment-tree synchronisation” (§7).

Throughout, $P$ ranges over the shielded pools $\mathsf{Sapling}$ , $\mathsf{Orchard}$ and $\mathsf{Ironwood}$ ; $H_{\mathsf{S}}$ is the Sapling activation height, and $H_{\mathsf{NU6.3}}$ the NU6.3 activation height of ZIP 258. For a compact block $b$ , $n_{P}(b)$ and $S^{P}_{\mathsf{end}}(b)$ are the commitment count and the end size of Definition 4.11.

6.1 The account birthday

Definition 6.1 (Chain state).

For a height $h$ , the chain state at $h$ is

C(h):=\bigl{(}h,\ \mathsf{hash}_{h},\ (m_{P}(h),F_{P}(h))_{P\in\{\mathsf{% Sapling},\mathsf{Orchard},\mathsf{Ironwood}\}}\bigr{)},

where $\mathsf{hash}_{h}$ is the $32$ -byte hash of block $h$ ; $m_{P}(h)\in[0,2^{32}]$ is the number of leaves of the note commitment tree of pool $P$ in the final treestate of block $h$ ; and $F_{P}(h)$ is the frontier of that tree (Crypto Guide, §“Append-only and incrementally updatable trees”, Definition “Frontier”): for each set bit $t$ of $m_{P}(h)$ , the root of the completed left subtree of height $t$ on the rightmost filled path. The empty tree has $m_{P}(h)=0$ and the empty frontier, and the full tree, $m_{P}(h)=2^{32}$ , has its root as frontier. The three trees are distinct trees of depth $32$ ( $\mathsf{MerkleDepth}^{\mathsf{Sapling}}=\mathsf{MerkleDepth}^{\mathsf{Orchard}% }=32$ ; protocol specification, §“Constants” and §“Note Commitment Trees”): the Sapling tree of the specification, and the Orchard-pool and Ironwood-pool trees, each built with the Orchard Merkle hash (Ironwood Guide, §“The Merkle hash and the tree”, Definition “Note commitment tree”). The chain state $C(h)$ is the response of $\mathsf{TreeState}(h)$ (Table 4).

By the Crypto Guide’s Definition “Frontier” (§“Append-only and incrementally updatable trees”), the pair $(m_{P}(h),F_{P}(h))$ determines the root of the tree of $P$ after block $h$ and suffices to append every later leaf without any leaf appended before block $h+1$ . That it also yields every later authentication path is shown in “Frontiers as scan seeds” (§7.3).

Definition 6.2 (Account birthday).

The birthday of an account is a height $B$ , known to the wallet, that is a lower bound on the height of the first block in which the account could have received funds (ZIP 326, “Terminology”). With the birthday the wallet stores the chain state $C(B-1)$ , which summarises every note commitment of every pool before $B$ . The scan of the account starts at block $B$ , and no block below $B$ is scanned for it. The birthday of a wallet is the minimum of the birthdays of its accounts.

(i)

Added accounts. Let an account with birthday $B^{\prime}$ be added while the greatest height of a block the wallet has scanned exceeds $B^{\prime}$ . Every block of $[B^{\prime},\text{that height}]$ is then scanned again with the scanning keys of the new account (§6.2), since earlier scans did not try them; the results of the other accounts are unchanged.
(ii)

No recorded birthday. A wallet that restores a seed without a recorded birthday takes $B:=H_{\mathsf{S}}$ : no shielded address of a light client can have received a relevant transaction before Sapling activation (ZIP 307, “Client-server interaction”, “Importing a pre-existing seed”). The bound concerns shielded receipts only; the transparent history of the account’s addresses may lie below it.

Remark 6.3 (Choosing a birthday).

Let the tip be at height $T$ when an account is created, and let $d$ be at least the wallet’s assumed maximum reorganisation depth. The birthday of the new account is taken as $B\leq T-d+1$ , with stored chain state $C(B-1)$ at height $T-d$ or below. A reorganisation that replaces at most $d$ blocks re-mines no transaction below height $T-d+1$ ; with $B$ closer to the tip, such a reorganisation could re-mine a transaction paying the account at a height below $B$ , which the wallet never scans, and the payment would be missed. Consensus imposes no maximum reorganisation depth (Consensus Guide, §“Reorg rails, maturity, and the finality floor”), so $d$ is a wallet parameter, not a guarantee. The rollback window of $600$ blocks that ZIP 218, “Block-count-based constants”, recommends concerns nodes and bounds no wallet’s choice of $d$ . An earlier birthday is always safe for discovery and costs scanning work (§6.5).

6.2 Scanning keys

Definition 6.4 (Scanning keys of an account).

Let an account $a$ have Sapling keys and Orchard-protocol keys derived as in “Hierarchical key derivation (ZIP 32)” (§2), the latter with the flag $\mathsf{use\_qsk}$ of Construction 2.10. Scopes are $s\in\{\mathsf{ext},\mathsf{int}\}$ .

(i)

Sapling. For each scope $s$ , the pair $(\mathsf{ivk}^{\mathsf{S}}_{s},\mathsf{nk}^{\mathsf{S}}_{s})$ of incoming viewing key and nullifier deriving key (ZIP 32, “Sapling internal key derivation”). Sapling outputs are scanned from $B$ .
(ii)

Orchard protocol. For each scope $s$ and each $u\in\{\mathsf{false},\mathsf{true}\}$ , the incoming viewing key $\mathsf{ivk}_{s,u}$ of scope $s$ computed with $\mathsf{use\_qsk}=u$ , and the nullifier deriving key $\mathsf{nk}$ , the same in both branches of Construction 2.10 and in both scopes (Construction 2.14).

A receiver and its $\mathsf{ivk}$ are scoped to the Orchard protocol, not to a pool: the same $\mathsf{ivk}$ trial-decrypts Orchard-pool and Ironwood-pool note ciphertexts (ZIP 326, “Scanning for Ironwood-pool and Orchard-pool notes”); the pool of an Action is that of the bundle that carries it, and Definition 4.9 admits lead byte $\mathtt{0x02}$ in the Orchard pool and $\mathtt{0x03}$ in the Ironwood pool. The use_qsk set $U_{a}$ is $\{u\}$ when the wallet knows the account’s value $u$ and $\{\mathsf{false},\mathsf{true}\}$ when it does not.

The following rules of ZIP 326, with their normative levels, fix which $\mathsf{ivk}$ is tried on which output.

(R1)

Restoration. A wallet restoring from a seed MUST take $U_{a}=\{\mathsf{false},\mathsf{true}\}$ and scan with both values until rule (R2) narrows it, because $\mathsf{use\_qsk}$ is not part of the recovery information (“Scanning when restoring from seed”).
(R2)

Narrowing. Once the wallet sees funds received in either Orchard-protocol pool under a value $u$ , it SHOULD stop scanning with the other value, $U_{a}:=\{u\}$ . The evidence stands if the transaction that provided it is later reorganised away, since it was valid on some chain (“Scan ranges”).
(R3)

Ironwood pool. The Ironwood pool is scanned from $\max(B,H_{\mathsf{NU6.3}})$ to the tip with $\mathsf{ivk}_{s,u}$ for $u\in U_{a}$ , hence with up to four keys ( $\{\mathsf{ext},\mathsf{int}\}\times\{\mathsf{false},\mathsf{true}\}$ ) while $\mathsf{use\_qsk}$ is unknown, subject to rule (R4). The value $u=\mathsf{true}$ is kept for an account whose birthday precedes NU6.3 activation, since a recorded birthday may be conservatively early (“Scan ranges”).
(R4)

First funds. ZIP 326 describes this rule as an optimisation and does not require it (“First-funds scanning in the Ironwood pool”). While the wallet knows that the account has received no Ironwood-pool funds in any block below the one scanned, only the external keys $\mathsf{ivk}_{\mathsf{ext},u}$ are needed for an output, except in a transaction whose $\mathsf{valueBalanceIronwood}$ is negative, where both scopes are used. The knowledge is kept only for the contiguous prefix of heights from $\max(B,H_{\mathsf{NU6.3}})$ scanned without a receipt, and a reorganisation whose last unchanged block is at height $h_{f}$ cuts the prefix back to $\max(h_{f},H_{\mathsf{NU6.3}})$ . A compact transaction carries no value balance (Definition 4.3), so a scan of compact blocks applies the exception only where it obtains $\mathsf{valueBalanceIronwood}$ otherwise; without it, both scopes are used.
(R5)

Orchard pool (“Scan ranges”). Orchard-pool note ciphertexts SHOULD NOT be scanned with $\mathsf{use\_qsk}=\mathsf{true}$ keys. For an account with birthday after NU6.3 activation they SHOULD NOT be scanned at all. For an account with birthday before NU6.3 activation they SHOULD NOT be scanned with the external $\mathsf{use\_qsk}=\mathsf{false}$ key after NU6.3 activation. If the account’s Orchard-pool balance is known to be zero at a block at or after NU6.3 activation, they SHOULD NOT be scanned in any block that descends from it.
(R6)

Order. A wallet MAY scan blocks in any order (“First-funds scanning in the Ironwood pool”).
(R7)

Outgoing notes. Outgoing notes are detected with the $\mathsf{ovk}$ of the same $\mathsf{use\_qsk}$ value, which adds no key dimension (“Outgoing-note detection”).

Under (R5) the Orchard pool is scanned with $\mathsf{use\_qsk}=\mathsf{false}$ only: with $\mathsf{ivk}_{\mathsf{int},\mathsf{false}}$ from $B$ until the Orchard-pool balance is known to be zero after NU6.3 activation, and with $\mathsf{ivk}_{\mathsf{ext},\mathsf{false}}$ from $B$ to $H_{\mathsf{NU6.3}}-1$ . The scanning keys $K_{a}(P,b,t)$ of account $a$ for pool $P$ , block $b$ and transaction $t$ are the triples $(\mathsf{ivk},\mathsf{nk},s)$ that items (i) and (ii) and rules (R1) to (R5) select. Every $\mathsf{ivk}$ is labelled $(a,s)$ , which attributes each accepted note to its account and scope.

Transparent receipts are detected at the transparent addresses the wallet watches, which MUST include index $0$ of each account (“Deriving unified addresses”, §3.6; ZIP 316, “Deriving a Unified Address from a UIVK”). The Ironwood pool is scanned as a pool of its own: its outputs are accepted under its lead byte, its revealed nullifiers are matched only against nullifiers of Ironwood-pool notes, and its tree is its own (Ironwood Guide, §“Nullifier sets”, Remark “Pool locality”).

Remark 6.5 (Omitted keys and conformant senders).

Rules (R2), (R4) and (R5) omit a key only where the restrictions of ZIP 326, “Wallet key-generation restrictions”, exclude an output of the account under it. Every key of an account has one $\mathsf{use\_qsk}$ value (MUST). No wallet sends Orchard-pool funds to $\mathsf{use\_qsk}=\mathsf{true}$ keys, or to any external receiver after NU6.3 activation (MUST NOT). Internal receivers are exposed to no party outside the wallet (ZIP 326, “Scanning for Ironwood-pool and Orchard-pool notes”), so before the account’s first Ironwood-pool funds a note at its internal Ironwood receiver arises only from the account’s own transaction, funded by a negative $\mathsf{valueBalanceIronwood}$ (“First-funds scanning in the Ironwood pool”). No value enters the Orchard pool after NU6.3 activation, so a zero Orchard-pool balance stays zero (“Scan ranges”). An output created in violation of these restrictions by a non-conformant sender may be missed; this is the cost of the SHOULD NOT rules, and it is part of the statement of Theorem 6.14.

Proposition 6.6 (Spend detection requires the nullifier key).

The nullifier of an Orchard-protocol note is $\mathsf{DeriveNullifier}_{\mathsf{nk}}(\rho,\psi,\mathsf{cm})$ (Ironwood Guide, §“The nullifier”, Definition “Nullifier”), and that of a Sapling note is $\mathsf{PRF}^{\mathsf{nfSapling}}_{\mathsf{nk}^{\star}}(\rho^{\star})$ with $\rho^{\star}=\mathsf{repr}_{\mathbb{J}}\bigl{(}\mathsf{MixingPedersenHash}(% \mathsf{cm},\mathsf{pos})\bigr{)}$ , a function of the nullifier deriving key and of the note’s position (protocol specification, §“Computing $\rho$ values and Nullifiers”).

(a)

Let an Orchard-protocol account key have $\mathsf{use\_qsk}=\mathsf{false}$ . No efficient algorithm that receives the incoming viewing key $(\mathsf{dk},\mathsf{ivk})$ of one scope and $\mathsf{ak}^{\mathbb{P}}$ , but not $\mathsf{nk}$ , and is then given notes of its choice with pairwise distinct $\rho$ outputs the nullifier of one of them, except with negligible probability.
(b)

Assume that $\mathsf{PRF}^{\mathsf{nfSapling}}$ , keyed by $\mathsf{nk}^{\star}$ of a Sapling key generated as the specification prescribes, is pseudorandom to an efficient algorithm that holds the incoming viewing key and the spend validating key of that key: the specification’s requirement that $\mathsf{PRF}^{\mathsf{nfSapling}}$ be a pseudorandom function (§“Pseudo Random Functions”), applied to this key distribution. Then the statement of (a) holds for the Sapling key.

A holder of $(\mathsf{dk},\mathsf{ivk})$ therefore detects receipts, since trial decryption needs only $\mathsf{ivk}$ (Construction 4.8), and cannot recognise a revealed nullifier as that of its note. A wallet that holds only incoming viewing keys has an empty tracked-nullifier set, and the set of notes it considers unspent is a superset of the true set. Links through other public data are outside the statement (Ironwood Guide, §“Nullifier uniqueness and unlinkability”, Remark “Limits”). For $\mathsf{use\_qsk}=\mathsf{true}$ no claim is made (Remark 2.11).

Proof.

(a) Let $\mathcal{C}$ be an algorithm that outputs the nullifier of a submitted note with probability $\varepsilon$ . It yields a distinguisher for the Ironwood Guide’s Proposition “Nullifier unlinkability” (§“Nullifier uniqueness and unlinkability”): the distinguisher runs $\mathcal{C}$ on its inputs $(\mathsf{dk},\mathsf{ivk})$ and $\mathsf{ak}^{\mathbb{P}}$ , submits the notes $\mathcal{C}$ is given, and outputs $1$ exactly when an answer equals the value $\mathcal{C}$ outputs for that note. In the real game it outputs $1$ with probability at least $\varepsilon$ . In the ideal game each answer is $\mathsf{Extract}_{\mathbb{P}}$ of a point uniform on $\mathcal{E}(\mathbb{F}_{p_{\mathsf{Pallas}}})$ , independent of the notes, except with probability $1/p_{\mathsf{Vesta}}$ ; it equals a given value with probability at most $2/\#\mathcal{E}(\mathbb{F}_{p_{\mathsf{Pallas}}})$ , since $\mathsf{Extract}_{\mathbb{P}}$ is at most two-to-one. Hence $\varepsilon$ is bounded by the advantage bound of that proposition plus a negligible term, under the assumptions it names. For the internal scope the proof of that proposition applies with its hybrid $H_{2}$ changed: the pair $(\mathsf{ivk}_{\mathsf{int}},\mathsf{dk}_{\mathsf{int}})$ is replaced by $(\mathsf{Commit}^{\mathsf{ivk}}_{r^{\prime}}(\mathsf{ak},\mathsf{nk}),u_{3})$ by Assumption 2.16, whose reduction, like that of $H_{2}$ , draws $\mathsf{ak}$ and $\mathsf{nk}$ itself and passes on the fourth and fifth components of its tuple. The cost is the advantage against that assumption in place of the term for the Ironwood Guide’s Assumption “Joint hiding of the viewing keys” (§“Viewing keys”), and the later hybrids are unchanged, since the game after the hop is that of $H_{2}$ . That proposition concerns a key generated from a uniform spending key; for an account key the bound holds up to the loss of Lemma 2.9. (b) An algorithm that outputs $\mathsf{PRF}^{\mathsf{nfSapling}}_{\mathsf{nk}^{\star}}(\rho^{\star})$ for a submitted $\rho^{\star}$ not queried before distinguishes the function from a random function, which outputs that value with probability $2^{-256}$ , contradicting the assumption. □

6.3 Receipt and spend detection

Definition 6.7 (Note state of a wallet).

The note state of a wallet consists of:

(i)

per account $a$ and pool $P$ , the set of detected notes, each with its value, scope, position $\mathsf{pos}$ (Definition 4.11), creating transaction, its nullifier when derivable, its memo once fetched, and a spent mark: either $\mathsf{unspent}$ or the triple (height, index in block, $\mathsf{txid}$ ) of the transaction that revealed its nullifier;
(ii)

per pool $P$ , the tracked set $W_{P}$ of the nullifiers of detected notes of $P$ not marked spent, and the set $R_{P}$ of retained unlinked nullifiers, each with its revealing transaction;
(iii)

for each wallet-relevant transaction, its mined height, or $\bot$ if it is unmined;
(iv)

the chain state (Definition 6.1) of the last block of each maximal interval of scanned heights; for a scan in increasing height, that of the last scanned block.

A transaction is wallet-relevant if and only if it creates a detected note or reveals the nullifier of one. A light wallet stores no copy of the chain; its note state is reconstructed from compact blocks (Definition 4.2) and fetched full transactions alone, supplied by a server that the wallet does not trust for privacy (Assumption 5.2, clause (b)). The information retained for witnesses is adjoined in “The information a wallet retains” (§7.4).

Construction 6.8 (Scanning a block).

Let $b$ be a compact block that continues the wallet’s chain, in the sense fixed in “Scan order” (§6.4), scanned for a set $A$ of accounts. For each pool $P$ , in block, transaction and description order, the start size of $P$ in $b$ (Lemma 4.12) and Definition 4.11 give each compact output or Action its position.

1.

Receipts. For each compact Sapling output (for $P=\mathsf{Sapling}$ ) and each compact Action of $P$ (for an Orchard-protocol pool), in transaction $t$ , and each account $a\in A$ , run Construction 4.8 and Definition 4.9 under every $(\mathsf{ivk},\mathsf{nk},s)\in K_{a}(P,b,t)$ (Definition 6.4). Record an accepted note with its value, scope $s$ , position and transaction. When $\mathsf{nk}$ is held, compute its nullifier $\mathsf{nf}$ (for Sapling from its position), and: if $\mathsf{nf}\in R_{P}$ , mark the note spent at the retained transaction and remove $\mathsf{nf}$ from $R_{P}$ ; otherwise add $\mathsf{nf}$ to $W_{P}$ .
2.

Spends. For each nullifier revealed in $P$ by $b$ (each compact Sapling spend, and the $\mathsf{nf}$ of each compact Action of $P$ ): if it lies in $W_{P}$ , mark the matching note spent at $(\mathrm{height}(b),\text{index},\mathsf{txid})$ and remove the nullifier from $W_{P}$ ; otherwise retain it in $R_{P}$ with its revealing transaction.
3.

Chain state. Compute $C(\mathrm{height}(b))$ from the stored $C(\mathrm{height}(b)-1)$ and $b$ : the hash of $b$ , and for each pool the size $S^{P}_{\mathsf{end}}(b)$ and the frontier obtained by appending the commitments of $P$ in $b$ , in order, to $F_{P}(\mathrm{height}(b)-1)$ . It replaces $C(\mathrm{height}(b)-1)$ in the note state.

Step 1 precedes step 2, so a receipt and its spend in one block, or in one range scanned in increasing height, are both found in one pass. A nullifier is compared only with nullifiers of its own pool (Ironwood Guide, §“Nullifier sets”). The retention period of $R_{P}$ is fixed by Lemma 6.12 (§6.4).

Enhancement. For each wallet-relevant transaction the wallet may fetch the full transaction by $\mathsf{Tx}(\mathsf{txid})$ (phase C of ZIP 307, “Client-server interaction”), which yields the memo, by decryption of the full $C_{\mathsf{enc}}$ , and the outgoing plaintexts recoverable under the account’s $\mathsf{ovk}$ , at the privacy cost stated in “Leakage of transaction queries” (§8.4).

Class (Definition 1.1). Trial decryption, nullifier matching in increasing height and enhancement are specified (ZIP 307, “Local processing”, “Detecting spends” and “Client-server interaction”); the scanning keys are those of ZIP 326. The retained set $R_{P}$ and the chain state of step 3 are designed but unspecified.

6.4 Scan order

Remark 6.9 (The interaction of ZIP 307).

ZIP 307, “Client-server interaction”, divides the interaction between client and server into four phases.

(A)

First start. The client obtains the tip height $X$ and the commitment tree state at $X$ , or sets $X:=H_{\mathsf{S}}$ ; the ZIP leaves the choice open. For an imported seed $X:=H_{\mathsf{S}}$ (“Importing a pre-existing seed”).
(B)

First update. The client obtains the tip $Y$ and the compact blocks $X,\dots,Y$ . It checks that the hash of block $X$ equals its stored copy, a mismatch meaning that $X$ was orphaned by a reorganisation, and discards block $X$ without further processing. For each later block it validates the header if one is present, trial-decrypts for its notes, creates and updates witnesses of detected notes, and scans for their nullifiers.
(C)

Transactions. At user direction, the client fetches full transactions.
(D)

Later updates. The client obtains the tip $Z$ and the blocks $Y,\dots,Z$ , rechecks block $Y$ as in (B), updates witnesses, marks the notes whose nullifiers appear as spent at that height, and scans for new notes as in (B).

In the queries of Table 4 the phases use $\mathsf{Tip}$ , $\mathsf{TreeState}$ or $\mathsf{Block}$ , $\mathsf{Blocks}$ and $\mathsf{Tx}$ .

Scanning a range $[h,h^{\prime}]$ requires the chain state $C(h-1)$ : its hash for the continuity check of block $h$ , and each pool’s size and frontier for positions and authentication paths. The wallet holds it after scanning block $h-1$ , or obtains it by $\mathsf{TreeState}(h-1)$ ; a server-supplied frontier is accepted under clause (a) of Assumption 5.2 and is checked against no header (Proposition 5.3).

Definition 6.10 (Continuity predicate).

Let the wallet hold the chain state $C(h)=(h,\mathsf{hash}_{h},(m_{P}(h),F_{P}(h))_{P})$ . A compact block $b$ continues the wallet’s chain at $h$ if and only if

(i)

$\mathrm{height}(b)=h+1$ ;
(ii)

$\mathsf{prevHash}(b)=\mathsf{hash}_{h}$ ; and
(iii)

for every pool $P$ , the start size of $P$ in $b$ , $S^{P}_{\mathsf{end}}(b)-n_{P}(b)$ (Lemma 4.12), equals $m_{P}(h)$ .

Within a range each block is checked against the chain state computed from its predecessor, and the first block against the stored chain state. When a range is scanned directly below an already scanned block $h^{\prime}+1$ , that block is checked again against the chain state $C(h^{\prime})$ that the new range computes. This extends ZIP 307’s single hash comparison at the start of each phase to every block and to both sides of every range boundary.

Rule (verify first). The scan results of a block are applied to the note state only after the block is checked to continue the wallet’s chain, and the results of a range only after each of its blocks is. Failure of the predicate is a continuity error, handled by rollback (“Reorganisation detection and recovery”, §7.6). A malformed or insufficient field is an error of the response, not a continuity error (“Architecture and authority”, §5.1). The predicate beyond ZIP 307’s comparison is designed but unspecified (Definition 1.1).

Definition 6.11 (Scanned heights).

For a wallet with birthday $B$ , the maximum scanned height is the greatest height of a scanned block, and the fully scanned height $f$ is the greatest $h\geq B-1$ such that every block of $[B,h]$ has been scanned. Under out-of-order scanning $f$ may lie below the maximum scanned height.

Lemma 6.12 (Out-of-order spend detection).

Fix a chain. Let a note of an account in pool $P$ be created at height $h_{n}$ and its nullifier revealed at height $h_{s}\geq h_{n}$ , and let the wallet hold the note’s nullifier deriving key. If each nullifier retained in $R_{P}$ (Construction 6.8) that was revealed at height $h$ is kept until the fully scanned height is at least $h$ , the note is marked spent at the revealing transaction whichever of the blocks $h_{n}$ and $h_{s}$ is scanned first. The retention bound is the least that guarantees this: if a nullifier revealed at $h$ is discarded while $f<h$ , some block below $h$ is unscanned, and a note of the account created there and spent at $h$ is never marked spent.

Proof.

If block $h_{n}$ is scanned no later than block $h_{s}$ , the note’s nullifier is in $W_{P}$ when block $h_{s}$ is scanned (steps 1 and 2 of Construction 6.8, in that order when $h_{n}=h_{s}$ ), and it is matched on arrival. Otherwise block $h_{s}$ is scanned first; the nullifier matches no tracked note and is retained in $R_{P}$ . Since $B\leq h_{n}\leq h_{s}$ (Definition 6.2), $f$ reaches $h_{s}$ only after block $h_{n}$ is scanned, so the nullifier is still in $R_{P}$ when step 1 finds the note, and the note is marked spent. Minimality: block $h$ has been scanned, since it revealed the nullifier, so $f<h$ means that some $h^{\prime}\in[B,h-1]$ is unscanned; a note created at $h^{\prime}$ and spent at $h$ has then lost the only record of its spend. □

Lemma 6.13 (Order independence of scanning).

Fix a chain and a range $[B,T]$ . Let a schedule scan every block of $[B,T]$ once, in any order and in ranges of any lengths, each block $b$ with key sets $K_{a}(P,b,t)$ , and let

(a)

the results of each range be applied only after continuity is verified (Definition 6.10), and
(b)

unlinked nullifiers be retained as Lemma 6.12 requires.

Then the resulting notes, positions, nullifiers and spent marks equal those of a scan of $[B,T]$ in increasing height that applies to each block the same key sets, and the chain state held for height $T$ is $C(T)$ . The key sets of Definition 6.4 depend on the order only through rules (R2), (R4) and the last clause of (R5), whose omitted keys accept no output of the account under the restrictions of ZIP 326; under those restrictions every order of Definition 6.4 yields the note state of the scan in increasing height. The witness half of order independence is stated in “Witness readiness” (§7.5).

Proof.

Receipt detection of an output is local to its block: it depends only on the compact output and the key set (Construction 4.8, Definition 4.9). Positions are local: by Lemma 4.12 the start size of each pool in $b$ follows from the compact block $b$ alone, and (a) makes it agree with the end size of the predecessor. Nullifiers are functions of the note, the key and, for Sapling, the position. Spent marks follow from Lemma 6.12 in either order. The chain state at $T$ is computed by step 3 of Construction 6.8 from the chain state below the last range that ends at $T$ , which (a) makes the true one, by induction over the ranges. For the last clause, a key omitted by (R2), (R4) or the last clause of (R5) in one order and tried in another accepts no output of the account (the Remark on omitted keys above; for (R5), no value enters the Orchard pool after NU6.3 activation, so a zero Orchard-pool balance stays zero), so both orders accept the same outputs. □

Theorem 6.14 (Soundness and completeness of note discovery).

Assume clause (a) of Assumption 5.2, and let the server’s best chain be unchanged while an account $a$ with birthday $B$ is scanned by Construction 6.8 with the scanning keys of Definition 6.4, under conditions (a) and (b) of Lemma 6.13. Let $f$ be the fully scanned height. For every $h\leq f$ , restricted to notes created at heights at most $h$ and to spent marks set by nullifiers revealed at heights at most $h$ :

(i)

the note state holds a note of $a$ in pool $P$ at position $p$ if and only if the best chain has, at or below $h$ , an output of $P$ at position $p$ that Definition 4.9 accepts under a key of $K_{a}(P,b,t)$ for its block $b$ and transaction $t$ ;
(ii)

when the wallet holds the note’s nullifier deriving key, the note is marked spent if and only if its nullifier is revealed in pool $P$ of the best chain at or below $h$ , and, except with negligible probability, a revealed nullifier equal to it marks a spend of that note and of no other.

Completeness is over accepted outputs under the keys that Definition 6.4 applies, not over all outputs addressed to the account: an output that its sender encrypted malformed, one that acceptance rejects, and one that a non-conformant sender created under a key omitted by the rules of ZIP 326 are excluded. Ranges scanned out of order above $f$ add notes and spent marks above $h$ , which the statement does not cover. A holder of incoming viewing keys alone obtains (i) only (Proposition 6.6). The assumptions of (ii) are those named in the results cited in the proof.

Proof.

By clause (a) the scanned compact blocks are those of the best chain, and every output of each is trial-decrypted under the applicable keys (Construction 6.8). Soundness of acceptance is Proposition 4.10, and membership of the accepted note in the best chain is Corollary 5.4(a). Positions are exact by Lemma 4.12(a) and Definition 6.10. The result does not depend on the order, by Lemma 6.13; this gives (i).

For (ii), spent status is nullifier matching within $P$ , with spends found in either order by Lemma 6.12. For Orchard-protocol notes, one nullifier per note and distinct nullifiers for distinct notes are the Ironwood Guide’s Lemma “One nullifier per note” (§“Double-spend resistance”) and Proposition “Nullifier uniqueness” (§“Nullifier uniqueness and unlinkability”), under the assumptions they name. For Sapling notes they are the Spend statement, which fixes the nullifier of the consumed note (protocol specification, §“Spend Statement (Sapling)”), and the requirement that $\mathsf{PRF}^{\mathsf{nfSapling}}$ be collision-resistant across all keys (§“Pseudo Random Functions”), with $\rho^{\star}$ distinct for distinct positions (§“Computing $\rho$ values and Nullifiers”). Without clause (a), Remark 5.5 defeats completeness and Corollary 5.4(b) defeats soundness. □

Theorem 6.15 (Recovery from the seed).

Let an account have $\mathsf{use\_qsk}=\mathsf{false}$ and a valid account key (“Valid account keys”, §2.6), so that its keys are determined by the seed $S$ and the account index (Proposition 2.12). Under clause (a) of Assumption 5.2, scanning the best chain from a lower bound on the account’s birthday, or from $H_{\mathsf{S}}$ when none is recorded (Definition 6.2), with the scanning keys of Definition 6.4, in particular with $U_{a}=\{\mathsf{false},\mathsf{true}\}$ by (R1) until (R2) narrows it, reconstructs the note state of the account up to the fully scanned height, as characterised by Theorem 6.14. Memos, and the outgoing plaintexts of outputs that the account encrypted under its $\mathsf{ovk}$ , are recovered once the wallet-relevant transactions are fetched. Transparent funds are recovered at the addresses the wallet watches: index $0$ of each account by obligation (§3.6); how far beyond index $0$ a wallet looks is fixed by no ZIP and is designed but unspecified (Definition 1.1). Data that never reached the chain, such as the memos of transactions never mined, is not recoverable. An account with $\mathsf{use\_qsk}=\mathsf{true}$ , whose keys $S$ does not determine, is outside the theorem, although Definition 6.4 scans with both values when restoring.

Proof.

Proposition 2.12 gives the keys, hence the scanning keys. Definition 6.2 makes the scan start at or below the first receipt. Theorem 6.14 gives the note state. Memos and outgoing plaintexts are functions of the fetched full transactions and the keys, and under clause (a) $\mathsf{Tx}$ returns the transactions of the best chain. □

Remark 6.16 (A reference interaction).

The following interaction of a wallet that synchronises by ranges out of order is designed but unspecified (Definition 1.1). Per synchronisation the wallet runs:

1.

$\mathsf{SubtreeRoots}(P,0)$ for each pool, storing the roots of the complete subtrees;
2.

$\mathsf{Tip}()$ ;
3.

selection of ranges: those near the tip, and those completing the subtrees of found notes (§7.5), before historic ranges;
4.

for each range $[s,e]$ : $\mathsf{TreeState}(s-1)$ unless $C(s-1)$ is held, then $\mathsf{Blocks}(s,e,\mathcal{P})$ , the continuity check and the scan;
5.

a return to step 2 when a scan changes the selection: a newly found note, or a rollback after a continuity error.

The order is a wallet policy fixed by no ZIP, and it is observable by the server (“Leakage of range queries”, §8.3).

6.5 The cost of scanning

Trial decryption costs one key agreement per compact output or Action per candidate $\mathsf{ivk}$ , for every block from the birthday to the tip, independently of the wallet’s own activity. Compaction (Definition 4.5) reduces the bandwidth, not the number of trials. Restoring an account repeats this work from its birthday. Retrieval of full transactions and the maintenance of authentication paths scale with the wallet’s own notes, the latter linearly in its unspent notes.

Proposition 6.17 (Scanning work per target day).

At NU7’s target spacing of $25$ seconds (ZIP 218, “Block target spacing”; Consensus Guide, §“Zcash time: 25-second blocks”), a target day of $86{,}400$ seconds holds $3456$ blocks. A block holds at most $330$ Orchard-pool Actions (ZIP 218, “Shielded pool action limits”), so a target day holds at most $1{,}140{,}480$ compact Orchard-pool Actions, with at most $168{,}791{,}040$ bytes of their compact payload at $148$ bytes each (Definition 4.5), and requires at most $1{,}140{,}480$ trial decryptions of Orchard-pool Actions per candidate $\mathsf{ivk}$ ; the number of candidate keys of an account is fixed by Definition 6.4. The same bounds hold for Orchard-pool Actions, Sapling spends and Sapling outputs together, since the shared budget of the same section limits their sum to $330$ per block, and a compact Sapling output ( $116$ bytes) or spend ( $32$ bytes) is smaller than a compact Action. The figures count target blocks: the number of blocks mined in a day varies, and the target spacing is not a rate limit.

The bound covers no Ironwood-pool Action: ZIP 218 counts none against any limit, so the specified text bounds neither their number nor the trial decryptions they cost. A proposed amendment would charge them to the shared budget of $330$ units, under which the same figures would bound the Orchard-protocol total (Consensus Guide, §“A block budget for shielded work”). The Ironwood term is an open problem (Definition 1.1).

Proof.

The counts are $86{,}400/25=3456$ , $330\cdot 3456=1{,}140{,}480$ and $148\cdot 1{,}140{,}480=168{,}791{,}040$ . The per-block limits are $\mathsf{OrchardBlockActionLimit}=330$ and $\mathsf{GlobalShieldedBudget}=330$ of ZIP 218, “Shielded pool action limits”. Each compact Action, and each compact Sapling output, costs one trial decryption per candidate key (Construction 4.8); a compact Sapling spend costs none. □