Design: treestate (note commitment trees and nullifier sets)

[dconnolly]

Todo:

• Update treestate RFC for Orchard

Design

• figuring out what data exactly we need to store to check consistency with note commitment trees
  • including Orchard changes in https://zips.z.cash/protocol/nu5.pdf#transactions
• figuring out what interface we should have for the NCT implementation
• writing down the process for checking transactions in a block against whatever data we have (from first two points)

Each Sapling spend specifies the anchor of the tree it should be verified against.
That must be a valid anchor in the parent chain of the block the transaction is mined in, but it could be from anywhere in that chain.

Because the anchor is included in the spend, we can do a nice split between semantic and contextual verification. In semantic verification, we can check the proofs against the provided anchor, and in contextual verification, we can check the anchor against ???

the spec points out that the anchor identifies the nullifier set
but my guess is that we don’t want to have that linkage
since updates to the nullifier set are additive, we can maintain a single nullifier set and check membership while doing contextual validation in the state system

this is talking only about the finalized part of the chain
we would need per block nullifier sets for the in memory part, and potentially we would want to have a single container holding all the nullifiers of the current best chain so that in the happy path we don’t have to do 100 set queries

you want to check a transaction against the latest nullifier set, but the likely-historic anchor

for checking the anchor, i guess we need to check that the transaction was valid against some previous anchor
so perhaps we could have a tree of (anchor, height)
and check that for all spend anchors, the corresponding height exists (known anchor) and is less than the current block height
maybe we don't need the height check, if the tree only has prior anchors

for each block hash, we need the root of the sprout or sapling note commitment tree

for each proof, it includes an anchor that it was made with (it's view of the tree); during semantic validation, we check that the proof is valid, during contextual, we check that the anchor for the transaction is actually an anchor for a previous block (that is has previously existed). Then for block validations, we construct our note commitment tree from our transactions and get its root, then we check that the proofs we have validated are consistent with the chain state, including that the nullifiers have never been seen/revealed (as necessary). This reduces treestate management to a nullifier set and a seen anchor root set.

When we see a purported anchor, when we look it up, it will probably be one of the most recent blocks (of the chain, the 'unfinalized' part that hasn't been saved down to zebra-state).