Struct zebra_chain::orchard::tree::NoteCommitmentTree

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

Orchard Incremental Note Commitment Tree

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 hash of the root’s child nodes. The default tree is the empty tree which has all leaves empty.

Fields

inner: Frontier<Node, MERKLE_DEPTH>

The tree represented as a Frontier.

A 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

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

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

Note: MerkleDepth^Orchard = MERKLE_DEPTH = 32.

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_x: NoteCommitmentUpdate ) -> Result<(), NoteCommitmentTreeError>

Adds a note commitment x-coordinate to the tree.

The leaves of the tree are actually a base field element, the x-coordinate of the commitment, the data that is actually stored on the chain and input into the proof.

Returns an error if the tree is full.

fn frontier(&self) -> Option<&NonEmptyFrontier<Node>>

Returns frontier of non-empty tree, or None if the tree is empty.

pub fn position(&self) -> Option<u64>

Returns the position of the most recently appended leaf in the tree.

This method is used for debugging, use incrementalmerkletree::Address for tree operations.

pub fn contains_new_subtree(&self, prev_tree: &Self) -> bool

Returns true if this tree has at least one new subtree, when compared with prev_tree.

pub fn is_complete_subtree(&self) -> bool

Returns true if the most recently appended leaf completes the subtree

pub fn subtree_index(&self) -> Option<NoteCommitmentSubtreeIndex>

Returns the subtree index at TRACKED_SUBTREE_HEIGHT. This is the number of complete or incomplete subtrees that are currently in the tree. Returns None if the tree is empty.

pub fn remaining_subtree_leaf_nodes(&self) -> usize

Returns the number of leaf nodes required to complete the subtree at TRACKED_SUBTREE_HEIGHT.

Returns 2^TRACKED_SUBTREE_HEIGHT if the tree is empty.

pub fn completed_subtree_index_and_root( &self ) -> Option<(NoteCommitmentSubtreeIndex, Node)>

Returns subtree index and root if the most recently appended leaf completes the subtree

pub fn root(&self) -> Root

Returns the current root of the tree, used as an anchor in Orchard 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]

Get the Pallas-based Sinsemilla hash / root node of this merkle tree of note commitments.

pub fn uncommitted() -> Base

An as-yet unused Orchard note commitment tree leaf node.

Distinct for Orchard, a distinguished hash value of:

Uncommitted^Orchard = I2LEBSP_l_MerkleOrchard(2)

pub fn count(&self) -> u64

Count of note commitments added to the tree.

For Orchard, the tree is capped at 2^32.

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<&NoteCommitmentTree> for SerializedTree

fn from(tree: &NoteCommitmentTree) -> Self

Converts to this type from the input type.

impl From<LegacyNoteCommitmentTree> for NoteCommitmentTree

fn from(legacy_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<Fp>> for NoteCommitmentTree

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

Compute the tree from a whole bunch of note commitments at once.

impl PartialEq for NoteCommitmentTree

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

This method tests for self and other values to be equal, and is used by ==.

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

This method 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