Struct zebra_chain::sprout::tree::NoteCommitmentTree

pub struct NoteCommitmentTree {
    inner: Frontier<Node, MERKLE_DEPTH>,
    cached_root: RwLock<Option<Root>>,
}

Sprout Note Commitment Tree.

An incremental Merkle tree of fixed depth used to store Sprout note commitments. 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; double-spending is prevented by maintaining the nullifier set for each shielded pool.

Internally this wraps [bridgetree::Frontier], so that we can maintain and increment the full tree with only the minimal amount of non-empty nodes/leaves required.

Note that the default value of the Root type is [0, 0, 0, 0]. However, this value differs from the default value of the root of the default tree (which is the empty tree) since it is the pair-wise root-hash of the tree’s empty leaves at the tree’s root level.

Fields

inner: Frontier<Node, MERKLE_DEPTH>

The tree represented as a [bridgetree::Frontier].

A [bridgetree::Frontier] is a subset of the tree that allows to fully specify it. It consists of nodes along the rightmost (newer) branch of the tree that has non-empty nodes. Upper (near root) empty nodes of the branch are not stored.

Consensus

A block MUST NOT add Sprout note commitments that would result in the Sprout note commitment tree exceeding its capacity of 2^(MerkleDepth^Sprout) leaf nodes.

https://zips.z.cash/protocol/protocol.pdf#merkletree

Note: MerkleDepth^Sprout = MERKLE_DEPTH = 29.

cached_root: RwLock<Option<Root>>

A cached root of the tree.

Every time the root is computed by Self::root, it is cached here, and the cached value will be returned by Self::root until the tree is changed by Self::append. This greatly increases performance because it avoids recomputing the root when the tree does not change between blocks. In the finalized state, the tree is read from disk for every block processed, which would also require recomputing the root even if it has not changed (note that the cached root is serialized with the tree). This is particularly important since we decided to instantiate the trees from the genesis block, for simplicity.

We use a RwLock for this cache, because it is only written once per tree update. Each tree has its own cached root, a new lock is created for each clone.

Implementations

impl NoteCommitmentTree

pub fn append( &mut self, cm: NoteCommitment, ) -> Result<(), NoteCommitmentTreeError>

Appends a note commitment to the leafmost layer of the tree.

Returns an error if the tree is full.

pub fn root(&self) -> Root

Returns the current root of the tree; used as an anchor in Sprout shielded transactions.

pub fn cached_root(&self) -> Option<Root>

Returns the current root of the tree, if it has already been cached.

pub fn recalculate_root(&self) -> Root

Calculates and returns the current root of the tree, ignoring any caching.

pub fn hash(&self) -> [u8; 32]

Returns a hash of the Sprout note commitment tree root.

pub fn uncommitted() -> [u8; 32]

Returns an as-yet unused leaf node value of a Sprout note commitment tree.

Uncommitted^Sprout = [0]^(l^Sprout_Merkle).

pub fn count(&self) -> u64

Counts the note commitments in the tree.

For Sprout, the tree is capped at 2^29 leaf nodes.

pub fn assert_frontier_eq(&self, other: &Self)

Checks if the tree roots and inner data structures of self and other are equal.

Panics

If they aren’t equal, with a message explaining the differences.

Only for use in tests.

Trait Implementations

impl Clone for NoteCommitmentTree

fn clone(&self) -> Self

Clones the inner tree, and creates a new RwLock with the cloned root data.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for NoteCommitmentTree

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for NoteCommitmentTree

fn default() -> Self

Returns the “default value” for a type.

impl<'de> Deserialize<'de> for NoteCommitmentTree

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl From<LegacyNoteCommitmentTree> for NoteCommitmentTree

fn from(nct: LegacyNoteCommitmentTree) -> Self

Converts to this type from the input type.

impl From<NoteCommitmentTree> for LegacyNoteCommitmentTree

fn from(nct: NoteCommitmentTree) -> Self

Converts to this type from the input type.

impl From<Vec<NoteCommitment>> for NoteCommitmentTree

fn from(values: Vec<NoteCommitment>) -> Self

Builds the tree from a vector of commitments at once.

impl PartialEq for NoteCommitmentTree

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Serialize for NoteCommitmentTree

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl Eq for NoteCommitmentTree