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 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, ranges over the shielded pools , and , with the chain state of Definition 6.1, the birthday of Definition 6.2, and the commitment count and end size of a compact block (Definition 4.11). Assumption 5.2 is the server assumption; only its clause (a) is used here.
A detected note is not yet spendable. A spend needs, besides the note, its position and the authentication path of 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 and of the first leaves of the pool’s tree, 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 and the same layer convention (protocol specification, §“Note Commitment Trees” and §“Merkle Path Validity”). Everything below applies to each pool separately.
An incremental witness of a note at position , after
ZIP 307, “Local processing”, “Creating and updating note witnesses”, states the protocol for the Sapling pool and its commitments ; it applies to each pool with that pool’s commitments, 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 of the block, in order:
append to the tree;
append to every held witness;
if the output of is accepted by Definition 4.9, create a witness of it from the current tree.
A witness updated through block yields the authentication path of its note to the anchor of block . No ZIP specifies any other tree-maintenance protocol.
Under linear witness maintenance, let a note be created in block and
let
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
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 (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.
Fix a pool and its note commitment tree of depth , with nodes
in layer counted from the root (Ironwood Guide,
§“The Merkle hash and the tree”, Definition “Note commitment tree”;
protocol specification, §“Merkle Path Validity”). Let
be its Merkle hash, for Sapling and
for either Orchard-protocol pool, and its
unused-leaf value, or
the root over the positions
for
For a pool and a list
the tree’s Merkle hash at level
Let the tree of hold leaves, and for each let
Induction on . For
Let the tree hold leaves, let
For
For
Hence the leaves of subtree , the roots of the complete subtrees other than and the frontier of the tree of size suffice for the path, and the wallet needs the commitments of no subtree other than .
The range of is
At each synchronisation the wallet queries for
each pool
Let be the frontier of the tree of pool after block
the root of the tree after every block
for every position
The commitments at positions below are not needed. Consequently the
chain state
(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 (
A batch of consecutive blocks
The retained tree information of a wallet is adjoined to its note
state (Definition 6.7). It comprises a finite set
of heights, the retained block boundaries, chosen by
the wallet and the same for every pool, which contains
for each unspent note of the wallet in , its position and its
leaf, and each sibling with
the complete subtree roots with their completing heights (Definition 5.8), and the frontier of the tree after the last scanned block;
for each
The rollback window is the span of
Fix a pool .
Let be the position of a retained note,
For every height at which the wallet holds a chain state
for all pools, with
(i) By Lemma 7.8, each sibling is of one of the
following sorts. A sibling whose range lies below is the same node at
every later tree state: for
(ii) After the discards, every retained node lies over a range below and is a function of the leaves appended through block (Ironwood Guide, §“Authentication paths”, Lemma “Authentication paths from public data”); every retained subtree root has completing height at most , and is likewise such a function; the retained chain states are those at heights at most ; and the frontier after is that of , which the wallet holds for every pool at the same . A wallet that scanned only the blocks at most can hold each of these items, and item (a) is satisfied, since a sibling whose range is not below is not yet due. □
Let be a retained block boundary with tree size in pool , let
be a position,
the range of starts at or beyond , and
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. □
Let
For pool and subtree , let be the completing height of
subtree (Definition 5.8), and let be the
activation height of . The block extent of subtree is the
interval of heights
The start of an extent is inclusive because the completing block of
subtree
Let a note of pool lie at position ,
the blocks of subtree are scanned from the start of its
extent (Definition 7.16) up to , or through its
completing height if
the wallet holds the root of every complete subtree
the frontier of is retained, which scanning the extent of subtree through yields when is not a multiple of .
Condition (2) can be weakened through frontier carries: every complete
subtree
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
Under the hypotheses of Lemma 6.13, a schedule of ranges that covers in any order yields, for every note and every retained anchor, the witness of a scan in increasing height from , 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.
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 , 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. □
A restored wallet seeds each tree from the chain state
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.
Each synchronisation after the first requests blocks from its previously synchronised height inclusive and checks that the hash of the received block equals the stored one; a mismatch implies that block 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 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).
Rollback to a height at which the wallet holds a chain state consists of the following changes.
The chain state of the wallet becomes , and each pool’s retained tree information becomes that of Proposition 7.13(ii) for .
Every transaction mined above 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 of its pool.
Scan results above are discarded: the unlinked nullifiers of revealed above , and the scanned ranges above , so that the scanned heights of Definition 6.11 are at most . 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.
The knowledge of rule (R4) of Definition 6.4 is cut back as that rule states; the evidence of rule (R2) stands.
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).
Let
If
Otherwise let be the greatest height with
If
It restarts synchronisation from the query .
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 lie on the server’s chain, and results from replaced blocks below would survive. The construction is designed but unspecified (Definition 1.1).
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 form the interval
A continuity error at implies
Repeated recovery by Construction 7.24 strictly
decreases the rollback height until
No offset below guarantees progress: a rollback to
(i) Under clause (a) the server’s block has the requested height, so
the failing clause of Definition 6.10 is (ii)
or (iii). The server’s block has as parent its chain’s block
(ii) Consider one recovery, with rollback height
(iii) After a rollback to
Under the hypotheses of Proposition 7.25, recovery by
Construction 7.24 ends at a height such that every
block of the wallet at most is a block of the server’s chain: either a
retained boundary or a recorded height
Proposition 7.25 gives the end height and its property.
After the rollback, the retained information is a function of the blocks at
most (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
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 be the height of a tip of the final chain that the wallet obtains after that time. Let the wallet
check continuity before applying the results of a range (Definition 6.10), on both sides of every range boundary;
retain unlinked nullifiers as Lemma 6.12 requires;
take positions from consistent sizes (Lemma 4.12);
recover from every continuity error by Construction 7.24, scanning a height again only after a rollback below it;
enter a note into a witness only once the extent of its subtree is scanned up to the anchor (Definition 7.16);
scan the range that contains after obtaining , with continuity checked at its lower boundary (Definition 6.10), and discard scan results above ; and
hold, as its complete subtree roots, those returned by a query made after obtaining , restricted to completing height at most .
If, after its last rollback, its scanned ranges cover , 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 .
The theorem composes earlier results and adds no mechanism. By (6) the
range that contains was requested after the tip query that returned
, so under clause (a) the wallet’s block is that of the final chain.
By (1), each block of 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
Consensus bounds no reorganisation depth, and node rollback windows are local policy (Consensus Guide, §“Rollback limits, coinbase maturity, and finality”). ZIP 307, “Local processing”, advises caching tree and witness state for recent blocks, on the ground that no full node rolls back the chain by more than blocks. That ground no longer holds: ZIP 218, “Block-count-based constants”, recommends a node rollback limit of blocks at its -second target spacing and keeps coinbase maturity at 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 at a height whose hash the wallet has recorded extends it under clause (a) of Assumption 5.2 (Construction 7.24).