Struct ConcurrentMerkleTree

#[repr(C)]
pub struct ConcurrentMerkleTree<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> {
    pub sequence_number: u64,
    pub active_index: u64,
    pub buffer_size: u64,
    pub change_logs: [ChangeLog<MAX_DEPTH>; MAX_BUFFER_SIZE],
    pub rightmost_proof: Path<MAX_DEPTH>,
}

Exported for Anchor / Solita Conurrent Merkle Tree is a Merkle Tree that allows multiple tree operations targeted for the same tree root to succeed.

In a normal merkle tree, only the first tree operation will succeed because the following operations will have proofs for the unmodified tree state. ConcurrentMerkleTree avoids this by storing a buffer of modified nodes (change_logs) which allows it to implement fast-forwarding of concurrent merkle tree operations.

As long as the concurrent merkle tree operations have proofs that are valid for a previous state of the tree that can be found in the stored buffer, that tree operation’s proof can be fast-forwarded and the tree operation can be applied.

There are two primitive operations for Concurrent Merkle Trees: set_leaf and append. Setting a leaf value requires passing a proof to perform that tree operation, but appending does not require a proof.

An additional key property of ConcurrentMerkleTree is support for append operations, which do not require any proofs to be passed. This is accomplished by keeping track of the proof to the rightmost leaf in the tree (rightmost_proof).

The ConcurrentMerkleTree is a generic struct that may be interacted with using macros. Those macros may wrap up the construction and both mutable and immutable calls to the ConcurrentMerkleTree struct. If the macro contains a big match statement over different sizes of a tree and buffer, it might create a huge stack footprint. This in turn might lead to a stack overflow given the max stack offset of just 4kb. In order to minimize the stack frame size, the arguments for the ConcurrentMerkleTree methods that contain the proofs are passed as references to structs.

Fields

sequence_number: u64

active_index: u64

Index of most recent root & changes

buffer_size: u64

Number of active changes we are tracking

change_logs: [ChangeLog<MAX_DEPTH>; MAX_BUFFER_SIZE]

Proof for respective root

rightmost_proof: Path<MAX_DEPTH>

Implementations

impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>

pub fn new() -> ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>

pub fn is_initialized(&self) -> bool

pub fn initialize(&mut self) -> Result<[u8; 32], ConcurrentMerkleTreeError>

This is the trustless initialization method that should be used in most cases.

pub fn initialize_with_root( &mut self, args: &InitializeWithRootArgs, ) -> Result<[u8; 32], ConcurrentMerkleTreeError>

This is a trustful initialization method that assumes the root contains the expected leaves.

At the time of this crate’s publishing, there is no supported way to efficiently verify a pre-initialized root on-chain. Using this method before having a method for on-chain verification will prevent other applications from indexing the leaf data stored in this tree.

pub fn prove_tree_is_empty(&self) -> Result<(), ConcurrentMerkleTreeError>

Errors if one of the leaves of the current merkle tree is non-EMPTY

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

Returns the current root of the merkle tree

pub fn get_change_log(&self) -> Box<ChangeLog<MAX_DEPTH>>

Returns the most recent changelog

pub fn prove_leaf( &self, args: &ProveLeafArgs, ) -> Result<(), ConcurrentMerkleTreeError>

This method will fail if the leaf cannot be proven to exist in the current tree root.

This method will attempts to prove the leaf first using the proof nodes provided. However if this fails, then a proof will be constructed by inferring a proof from the changelog buffer.

Note: this is not the same as verifying that a (proof, leaf) combination is valid for the given root. That functionality is provided by check_valid_proof.

pub fn append( &mut self, node: [u8; 32], ) -> Result<[u8; 32], ConcurrentMerkleTreeError>

Appending a non-empty Node will always succeed .

pub fn fill_empty_or_append( &mut self, args: &FillEmptyOrAppendArgs, ) -> Result<[u8; 32], ConcurrentMerkleTreeError>

Convenience function for set_leaf

This method will set_leaf if the leaf at index is an empty node, otherwise it will append the new leaf.

pub fn set_leaf( &mut self, args: &SetLeafArgs, ) -> Result<[u8; 32], ConcurrentMerkleTreeError>

This method will update the leaf at index.

However if the proof cannot be verified, this method will fail.

pub fn get_seq(&self) -> u64

Returns the Current Seq of the tree, the seq is the monotonic counter of the tree operations that is incremented every time a mutable operation is performed on the tree.

pub fn check_valid_proof( &self, leaf: [u8; 32], proof: &[[u8; 32]; MAX_DEPTH], leaf_index: u32, ) -> bool

Checks that the proof provided is valid for the current root.

Trait Implementations

impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> Clone for ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>

fn clone(&self) -> ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> Default for ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>

fn default() -> ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>

Returns the “default value” for a type.

impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> ZeroCopy for ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>

fn load_mut_bytes<'a>(data: &'a mut [u8]) -> Result<&'a mut Self>

fn load_bytes<'a>(data: &'a [u8]) -> Result<&'a Self>

impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> Zeroable for ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>

fn zeroed() -> Self

Calls zeroed.

impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> Copy for ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>

impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> Pod for ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>