Struct ConcurrentMerkleTree

#[repr(C)]
pub struct ConcurrentMerkleTree<H, const HEIGHT: usize>
where
    H: Hasher,
{
    pub height: usize,
    pub canopy_depth: usize,
    pub filled_subtrees: BoundedVec<[u8; 32]>,
    pub changelog: CyclicBoundedVec<ChangelogEntry<HEIGHT>>,
    pub roots: CyclicBoundedVec<[u8; 32]>,
    pub canopy: BoundedVec<[u8; 32]>,
    pub _hasher: PhantomData<H>,
    /* private fields */
}

Concurrent Merkle tree which allows for multiple requests of updating leaves, without making any of the requests invalid, as long as they are not modyfing the same leaf.

When any of the above happens, some of the concurrent requests are going to be invalid, forcing the clients to re-generate the Merkle proof. But that’s still better than having such a failure after any update happening in the middle of requesting the update.

Due to ability to make a decent number of concurrent update requests to be valid, no lock is necessary.

Fields

height: usize

canopy_depth: usize

filled_subtrees: BoundedVec<[u8; 32]>

Hashes of subtrees.

changelog: CyclicBoundedVec<ChangelogEntry<HEIGHT>>

History of Merkle proofs.

roots: CyclicBoundedVec<[u8; 32]>

History of roots.

canopy: BoundedVec<[u8; 32]>

Cached upper nodes.

_hasher: PhantomData<H>

Implementations

impl<H, const HEIGHT: usize> ConcurrentMerkleTree<H, HEIGHT>

where H: Hasher,

pub fn canopy_size(canopy_depth: usize) -> usize

Number of nodes to include in canopy, based on canopy_depth.

pub fn non_dyn_fields_size() -> usize

Size of the struct without dynamically sized fields (BoundedVec, CyclicBoundedVec).

pub fn size_in_account( height: usize, changelog_size: usize, roots_size: usize, canopy_depth: usize, ) -> usize

pub fn new( height: usize, changelog_size: usize, roots_size: usize, canopy_depth: usize, ) -> Result<Self, ConcurrentMerkleTreeError>

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

Initializes the Merkle tree.

pub fn changelog_index(&self) -> usize

Returns the index of the current changelog entry.

pub fn root_index(&self) -> usize

Returns the index of the current root in the tree’s root buffer.

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

Returns the current root.

pub fn current_index(&self) -> usize

pub fn next_index(&self) -> usize

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

pub fn sequence_number(&self) -> usize

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

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

pub fn update_proof_from_canopy( &self, leaf_index: usize, proof: &mut BoundedVec<[u8; 32]>, ) -> Result<(), ConcurrentMerkleTreeError>

pub fn changelog_entries( &self, changelog_index: usize, ) -> Result<Skip<CyclicBoundedVecIterator<'_, ChangelogEntry<HEIGHT>>>, ConcurrentMerkleTreeError>

Returns an iterator with changelog entries newer than the requested changelog_index.

pub fn update_proof_from_changelog( &self, changelog_index: usize, leaf_index: usize, proof: &mut BoundedVec<[u8; 32]>, ) -> Result<(), ConcurrentMerkleTreeError>

Updates the given Merkle proof.

The update is performed by checking whether there are any new changelog entries and whether they contain changes which affect the current proof. To be precise, for each changelog entry, it’s done in the following steps:

• Check if the changelog entry was directly updating the leaf_index we are trying to update.
  • If no (we check that condition first, since it’s more likely), it means that there is a change affecting the proof, but not the leaf. Check which element from our proof was affected by the change (using the critbit_index method) and update it (copy the new element from the changelog to our updated proof).
  • If yes, it means that the same leaf we want to update was already updated. In such case, updating the proof is not possible.

pub fn validate_proof( &self, leaf: &[u8; 32], leaf_index: usize, proof: &BoundedVec<[u8; 32]>, ) -> Result<(), ConcurrentMerkleTreeError>

Checks whether the given Merkle proof for the given node (with index i) is valid. The proof is valid when computing parent node hashes using the whole path of the proof gives the same result as the given root.

pub fn update( &mut self, changelog_index: usize, old_leaf: &[u8; 32], new_leaf: &[u8; 32], leaf_index: usize, proof: &mut BoundedVec<[u8; 32]>, ) -> Result<(usize, usize), ConcurrentMerkleTreeError>

Replaces the old_leaf under the leaf_index with a new_leaf, using the given proof and changelog_index (pointing to the changelog entry which was the newest at the time of preparing the proof).

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

Appends a new leaf to the tree.

pub fn append_with_proof( &mut self, leaf: &[u8; 32], proof: &mut BoundedVec<[u8; 32]>, ) -> Result<(usize, usize), ConcurrentMerkleTreeError>

Appends a new leaf to the tree. Saves Merkle proof to the provided proof reference.

pub fn append_batch( &mut self, leaves: &[&[u8; 32]], ) -> Result<(usize, usize), ConcurrentMerkleTreeError>

Appends a batch of new leaves to the tree.

pub fn append_batch_with_proofs( &mut self, leaves: &[&[u8; 32]], proofs: &mut [&mut BoundedVec<[u8; 32]>], ) -> Result<(usize, usize), ConcurrentMerkleTreeError>

Appends a batch of new leaves to the tree. Saves Merkle proofs to the provided proofs slice.

Trait Implementations

impl<H, const HEIGHT: usize> Debug for ConcurrentMerkleTree<H, HEIGHT>

where H: Hasher + Debug,

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

Formats the value using the given formatter.

impl<H, const HEIGHT: usize> Drop for ConcurrentMerkleTree<H, HEIGHT>

where H: Hasher,

fn drop(&mut self)

Executes the destructor for this type.

impl<H, const HEIGHT: usize> PartialEq for ConcurrentMerkleTree<H, HEIGHT>

where H: Hasher,

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.