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 Sapling , Orchard and Ironwood ; H S is the Sapling activation height, and H NU6 .3 the NU6.3 activation height of ZIP 258. For a compact block b , n P (b) and S end P (b) are the commitment count and the end size of Definition 4.11.
For a height h , the chain state at h is
| C (h) := (h, hash h, (m P (h), F P (h)) P ∈ { Sapling, Orchard, Ironwood }), |
where hash h is the 32 -byte hash of block h ;
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
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
Added accounts. Let an account with birthday B ′ be added while the greatest height of a block the wallet has scanned exceeds B ′ . Every block of [B ′, 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.
No recorded birthday. A wallet that restores a seed without a
recorded birthday takes
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
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 use _ qsk of
Construction 2.10. Scopes are
Sapling. For each scope s , the pair (ivk s S, nk s S) of incoming viewing key and nullifier deriving key (ZIP 32, “Sapling internal key derivation”). Sapling outputs are scanned from B .
A receiver and its ivk are scoped to the Orchard protocol, not to a pool: the same 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 0x02 in the Orchard pool and 0x03 in the Ironwood pool. The use_qsk set U a is { u } when the wallet knows the account’s value u and { false, true } when it does not.
The following rules of ZIP 326, with their normative levels, fix which ivk is tried on which output.
Restoration. A wallet restoring from a seed MUST take
Narrowing. Once the wallet sees funds received in either
Orchard-protocol pool under a value u , it SHOULD stop scanning with the
other value,
Ironwood pool. The Ironwood pool is scanned from
max (B, H NU6 .3) to the tip with ivk s, u for
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 ivk ext, u are needed for an output, except in a transaction whose valueBalanceIronwood is negative, where both scopes are used. The knowledge is kept only for the contiguous prefix of heights from max (B, H 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 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 valueBalanceIronwood otherwise; without it, both scopes are used.
Orchard pool (“Scan ranges”). Orchard-pool note ciphertexts
SHOULD NOT be scanned with
Order. A wallet MAY scan blocks in any order (“First-funds scanning in the Ironwood pool”).
Outgoing notes. Outgoing notes are detected with the ovk of the same use _ qsk value, which adds no key dimension (“Outgoing-note detection”).
Under (R5) the Orchard pool is scanned with
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”).
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 use _ qsk value (MUST).
No wallet sends Orchard-pool funds to
The nullifier of an Orchard-protocol note is DeriveNullifier nk (ρ, ψ, cm) (Ironwood Guide, §“The nullifier”, Definition “Nullifier”), and that of a Sapling note is PRF nk ⋆ nfSapling (ρ ⋆) with
| ρ ⋆ = repr J (MixingPedersenHash (cm, pos)), |
a function of the nullifier deriving key and of the note’s position (protocol specification, §“Computing ρ values and Nullifiers”).
Let an Orchard-protocol account key have
Assume that PRF nfSapling , keyed by nk ⋆ 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 PRF 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 (dk, ivk) therefore detects receipts, since trial
decryption needs only 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
(a) Let C be an algorithm that outputs the nullifier of a submitted note with probability ε . It yields a distinguisher for the Ironwood Guide’s Proposition “Nullifier unlinkability” (§“Nullifier uniqueness and unlinkability”): the distinguisher runs C on its inputs (dk, ivk) and ak P , submits the notes C is given, and outputs 1 exactly when an answer equals the value C outputs for that note. In the real game it outputs 1 with probability at least ε . In the ideal game each answer is Extract P of a point uniform on E (F p Pallas) , independent of the notes, except with probability 1 / p Vesta ; it equals a given value with probability at most 2 / # E (F p Pallas) , since Extract P is at most two-to-one. Hence ε 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 (ivk int, dk int) is replaced by (Commit r ′ ivk (ak, nk), u 3) by Assumption 2.16, whose reduction, like that of H 2 , draws ak and 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 PRF nk ⋆ nfSapling (ρ ⋆) for a submitted ρ ⋆ not queried before distinguishes the function from a random function, which outputs that value with probability 2 − 256 , contradicting the assumption. □
The note state of a wallet consists of:
per account a and pool P , the set of detected notes, each with its value, scope, position pos (Definition 4.11), creating transaction, its nullifier when derivable, its memo once fetched, and a spent mark: either unspent or the triple (height, index in block, txid ) of the transaction that revealed its nullifier;
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;
for each wallet-relevant transaction, its mined height, or ⊥ if it is unmined;
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).
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.
Receipts. For each compact Sapling output (for
Spends. For each nullifier revealed in P by b (each compact Sapling spend, and the nf of each compact Action of P ): if it lies in W P , mark the matching note spent at (height (b), index, txid) and remove the nullifier from W P ; otherwise retain it in R P with its revealing transaction.
Chain state. Compute C (height (b)) from the stored
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).
Retrieval. For each wallet-relevant transaction the wallet may fetch the full transaction by Tx (txid) (phase C of ZIP 307, “Client-server interaction”), which yields the memo, by decryption of the full C enc , and the outgoing plaintexts recoverable under the account’s 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 retrieval 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.
ZIP 307, “Client-server interaction”, divides the interaction between client and server into four phases.
First start. The client obtains the tip height X and the
commitment tree state at X , or sets
First update. The client obtains the tip Y and the compact
blocks
Transactions. At user direction, the client fetches full transactions.
Later updates. The client obtains the tip Z and the blocks
In the queries of Table 4 the phases use Tip , TreeState or Block , Blocks and Tx .
Scanning a range [h, h ′] requires the chain state
Let the wallet hold the chain state
for every pool P , the start size of P in b ,
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
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).
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
Fix a chain. Let a note of an account in pool P be created at height
h n and its nullifier revealed at height
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
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
the results of each range be applied only after continuity is verified (Definition 6.10), and
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).
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. □
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
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 ;
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.
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 PRF nfSapling be collision-resistant across all keys (§“Pseudo Random Functions”), with ρ ⋆ distinct for distinct positions (§“Computing ρ values and Nullifiers”). Without clause (a), Remark 5.5 defeats completeness and Corollary 5.4(b) defeats soundness. □
Let an account have
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) Tx returns the transactions of the best chain. □
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:
SubtreeRoots (P, 0) for each pool, storing the roots of the complete subtrees;
Tip () ;
selection of ranges: those near the tip, and those completing the subtrees of found notes (§7.5), before historic ranges;
for each range [s, e] :
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).
Trial decryption costs one key agreement per compact output or Action per candidate 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.
At NU7’s target spacing of 25 seconds (ZIP 218, “Block target spacing”;
Consensus Guide, §“Confirmation times at 25-second spacing”), a target
day of
The counts are
| OrchardProtocolBlockActionLimit = 330, |
and every Orchard-pool Action, Ironwood-pool Action, Sapling spend and
Sapling output consumes one unit of a single shared budget