- Feature Name: treestate
- Start Date: 2020-08-31
- Design PR: ZcashFoundation/zebra#983
- Zebra Issue: ZcashFoundation/zebra#958
To validate blocks involving shielded transactions, we have to check the computed treestate from the included transactions against the block header metadata (for Sapling and Orchard) or previously finalized state (for Sprout). This document describes how we compute and manage that data, assuming a finalized state service as described in the State Updates RFC.
Block validation requires checking that the treestate of the block (consisting of the note commitment tree and nullifier set) is consistent with the metadata we have in the block header (the root of the note commitment tree) or previously finalized state (for Sprout).
TODO: split up these definitions into common, Sprout, Sapling, and possibly Orchard sections
Many terms used here are defined in the Zcash Protocol Specification
notes: Represents a value bound to a shielded payment address (public key) which is spendable by the recipient who holds the spending key corresponding to a given shielded payment address.
nullifiers: Revealed by Spend descriptions when its associated Note is spent.
nullifier set: The set of unique Nullifiers revealed by any Transactions
within a Block. Nullifiers are enforced to be unique within a valid block chain
by committing to previous treestates in Spend descriptions, in order to prevent
double-spends.
note commitments: Pedersen commitment to the values consisting a Note. One
should not be able to construct a Note from its commitment.
note commitment tree: An incremental Merkle tree of fixed depth used to
store NoteCommitments that JoinSplit transfers or Spend transfers produce. It
is used to express the existence of value and the capability to spend it. It is
not the job of this tree to protect against double-spending, as it is
append-only: that's what the Nullifier set is for.
note position: The index of a NoteCommitment at the leafmost layer,
counting leftmost to rightmost. The position in the tree is determined by the
order of transactions in the block.
root: The layer 0 node of a Merkle tree.
anchor: A Merkle tree root of a NoteCommitment tree. It uniquely
identifies a NoteCommitment tree state given the assumed security properties
of the Merkle tree’s hash function. Since the Nullifier set is always updated
together with the NoteCommitment tree, this also identifies a particular state
of the associated Nullifier set.
spend descriptions: A shielded Sapling transfer that spends a Note. Includes
an anchor of some previous Block's NoteCommitment tree.
output descriptions: A shielded Sapling transfer that creates a
Note. Includes the u-coordinate of the NoteCommitment itself.
action descriptions: A shielded Orchard transfer that spends and/or creates a Note.
Does not include an anchor, because that is encoded once in the anchorOrchard
field of a V5 Transaction.
joinsplit: A shielded transfer that can spend Sprout Notes and transparent
value, and create new Sprout Notes and transparent value, in one Groth16 proof
statement.
TODO: split into common, Sprout, Sapling, and probably Orchard sections
As Blocks are validated, the NoteCommitments revealed by all the transactions
within that block are used to construct NoteCommitmentTrees, with the
NoteCommitments aligned in their note positions in the bottom layer of the
Sprout or Sapling tree from the left-most leaf to the right-most in
Transaction order in the Block. So the Sprout NoteCommitments revealed by
the first JoinSplit<Groth16> in a block would take note position 0 in the Sprout
note commitment tree, for example. Once all the transactions in a block are
parsed and the notes for each tree collected in their appropriate positions, the
root of each tree is computed. While the trees are being built, the respective
block nullifier sets are updated in memory as note nullifiers are revealed. If
the rest of the block is validated according to consensus rules, that root is
committed to its own data structure via our state service (Sprout anchors,
Sapling anchors). Sapling block validation includes comparing the specified
FinalSaplingRoot in its block header to the root of the Sapling NoteCommitment
tree that we have just computed to make sure they match.
As the transactions within a block are parsed, Sapling shielded transactions
including Spend descriptions and Output descriptions describe the spending and
creation of Zcash Sapling notes, and JoinSplit-on-Groth16 descriptions to
transfer/spend/create Sprout notes and transparent value. JoinSplit and Spend
descriptions specify an anchor, which references a previous NoteCommitment tree
root: for Spends, this is a previous block's anchor as defined in their block
header, for JoinSplits, it may be a previous block's anchor or the root
produced by a strictly previous JoinSplit description in its transaction. For
Spends, this is convenient because we can query our state service for
previously finalized Sapling block anchors, and if they are found, then that
consensus check has
been satisfied and the Spend description can be validated independently. For
JoinSplits, if it's not a previously finalized block anchor, it must be the
treestate anchor of previous JoinSplit in this transaction, and we have to wait
for that one to be parsed and its root computed to check that ours is
valid. Luckily, it can only be a previous JoinSplit in this transaction, and is
usually the immediately previous one, so the set of candidate anchors
is smaller for earlier JoinSplits in a transaction, but larger for the later
ones. For these JoinSplits, they can be validated independently of their
anchor's finalization status as long as the final check of the anchor is done,
when available, such as at the Transaction level after all the JoinSplits have
finished validating everything that can be validated without the context of
their anchor's finalization state.
So for each transaction, for both Spend descriptions and JoinSplits, we can
preemptively try to do our consensus check by looking up the anchors in our
finalized set first. For Spends, we then trigger the remaining validation and
when that finishes we are full done with those. For JoinSplits, the anchor
state check may pass early if it's a previous block Sprout NoteCommitment tree
root, but it may fail because it's an earlier JoinSplits root instead, so once
the JoinSplit validates independently of the anchor, we wait for all candidate
previous JoinSplits in that transaction finish validating before doing the
anchor consensus check again, but against the output treestate roots of earlier
JoinSplits.
Both Sprout and Sapling NoteCommitment trees must be computed for the whole
block to validate. For Sprout, we need to compute interstitial treestates in
between JoinSplits in order to do the final consensus check for each/all
JoinSplits, not just for the whole block, as in Sapling.
For Sapling, at the block layer, we can iterate over all the transactions in
order and if they have Spends and/or Outputs, we update our Nullifer set for
the block as nullifiers are revealed in Spend descriptions, and update our note
commitment tree as NoteCommitments are revealed in Output descriptions, adding
them as leaves in positions according to their order as they appear transaction
to transaction, output to output, in the block. This can be done independent of
the transaction validations. When the Sapling transactions are all validated,
the NoteCommitmentTree root should be computed: this is the anchor for this
block. For Sapling and Blossom blocks, we need to check that this root matches
the RootHash bytes in this block's header, as the FinalSaplingRoot. Once all
other consensus and validation checks are done, this will be saved down to our
finalized state to our sapling_anchors set, making it available for lookup by
other Sapling descriptions in future transactions.
TODO: explain Heartwood, Canopy, NU5 rule variants around anchors.
For Sprout, we must compute/update interstitial NoteCommitmentTrees between
JoinSplits that may reference an earlier one's root as its anchor. If we do
this at the transaction layer, we can iterate through all the JoinSplits and
compute the Sprout NoteCommitmentTree and nullifier set similar to how we do
the Sapling ones as described above, but at each state change (ie,
per-JoinSplit) we note the root and cache it for lookup later. As the
JoinSplits are validated without context, we check for its specified anchor
amongst the interstitial roots we've already calculated (according to the spec,
these interstitial roots don't have to be finalized or the result of an
independently validated JoinSplit, they just must refer to any prior JoinSplit
root in the same transaction). So we only have to wait for our previous root to
be computed via any of our candidates, which in the worst case is waiting for
all of them to be computed for the last JoinSplit. If our JoinSplits defined
root pops out, that JoinSplit passes that check.
To finalize the block, the Sprout and Sapling treestates are the ones resulting from the last transaction in the block, and determines the Sprout and Sapling anchors that will be associated with this block as we commit it to our finalized state. The Sprout and Sapling nullifiers revealed in the block will be merged with the existing ones in our finalized state (ie, it should strictly grow over time).
- There is a single copy of the latest Orchard Note Commitment Tree for the finalized tip.
- When finalizing a block, the finalized tip is updated with a serialization of the latest Orchard Note Commitment Tree. (The previous tree should be deleted as part of the same database transaction.)
- Each non-finalized chain gets its own copy of the Orchard note commitment tree, cloned from the note commitment tree of the finalized tip or fork root.
- When a block is added to a non-finalized chain tip, the Orchard note commitment tree is updated with the note commitments from that block.
- When a block is rolled back from a non-finalized chain tip... (TODO)
- There is a single copy of the latest Sapling Note Commitment Tree for the finalized tip.
- When finalizing a block, the finalized tip is updated with a serialization of the Sapling Note Commitment Tree. (The previous tree should be deleted as part of the same database transaction.)
- Each non-finalized chain gets its own copy of the Sapling note commitment tree, cloned from the note commitment tree of the finalized tip or fork root.
- When a block is added to a non-finalized chain tip, the Sapling note commitment tree is updated with the note commitments from that block.
- When a block is rolled back from a non-finalized chain tip... (TODO)
- Every finalized block stores a separate copy of the Sprout note commitment tree (😿), as of that block.
- When finalizing a block, the Sprout note commitment tree for that block is stored in the state. (The trees for previous blocks also remain in the state.)
- Every block in each non-finalized chain gets its own copy of the Sprout note commitment tree. The initial tree is cloned from the note commitment tree of the finalized tip or fork root.
- When a block is added to a non-finalized chain tip, the Sprout note commitment tree is cloned, then updated with the note commitments from that block.
- When a block is rolled back from a non-finalized chain tip, the trees for each block are deleted, along with that block.
We can't just compute a fresh tree with just the note commitments within a block, we are adding them to the tree referenced by the anchor, but we cannot update that tree with just the anchor, we need the 'frontier' nodes and leaves of the incremental merkle tree.