Struct light_concurrent_merkle_tree::ConcurrentMerkleTree

#[repr(C)]
pub struct ConcurrentMerkleTree<'a, H, const HEIGHT: usize>
where
    H: Hasher,
{

    pub height: usize,
    pub changelog_capacity: usize,
    pub changelog_length: usize,
    pub current_changelog_index: usize,
    pub roots_capacity: usize,
    pub roots_length: usize,
    pub current_root_index: usize,
    pub canopy_depth: usize,
    pub next_index: usize,
    pub sequence_number: usize,
    pub rightmost_leaf: [u8; 32],
    pub filled_subtrees: BoundedVec<'a, [u8; 32]>,
    pub changelog: CyclicBoundedVec<'a, ChangelogEntry<HEIGHT>>,
    pub roots: CyclicBoundedVec<'a, [u8; 32]>,
    pub canopy: BoundedVec<'a, [u8; 32]>,
    pub _hasher: PhantomData<H>,
}

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

changelog_capacity: usize

changelog_length: usize

current_changelog_index: usize

roots_capacity: usize

roots_length: usize

current_root_index: usize

canopy_depth: usize

next_index: usize

sequence_number: usize

rightmost_leaf: [u8; 32]

filled_subtrees: BoundedVec<'a, [u8; 32]>

Hashes of subtrees.

changelog: CyclicBoundedVec<'a, ChangelogEntry<HEIGHT>>

History of Merkle proofs.

roots: CyclicBoundedVec<'a, [u8; 32]>

History of roots.

canopy: BoundedVec<'a, [u8; 32]>

Cached upper nodes.

_hasher: PhantomData<H>

Implementations

impl<'a, H, const HEIGHT: usize> ConcurrentMerkleTree<'a, 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 new( height: usize, changelog_size: usize, roots_size: usize, canopy_depth: usize ) -> Result<Self, ConcurrentMerkleTreeError>

pub unsafe fn copy_from_bytes( bytes_struct: &[u8], bytes_filled_subtrees: &[u8], bytes_changelog: &[u8], bytes_roots: &[u8], bytes_canopy: &[u8] ) -> Result<Self, ConcurrentMerkleTreeError>

Creates a copy of ConcurrentMerkleTree from the given byte slices.

• bytes_struct is casted directly into a reference of ConcurrentMerkleTree, then the value of the each primitive field is copied.
• bytes_filled_subtrees is used to create a BoundedVec directly. That BoundedVec is assigned to the struct.
• bytes_changelog is used to create a CyclicBoundedVec directly. That CyclicBoundedVec is assigned to the struct.
• bytes_roots is used to create a CyclicBoundedVec directly. That CyclicBoundedVec is assigned to the struct.

Purpose

This method is meant to be used mostly in the SDK code, to convert fetched Solana accounts to actual Merkle trees. Creating a copy is the safest way of conversion in async Rust.

Safety

This is highly unsafe. This method validates only sizes of slices. Ensuring the alignment and that the slices provide actual data of the Merkle tree is the caller’s responsibility.

It can be used correctly in async Rust.

pub unsafe fn struct_from_bytes( bytes_struct: &'a [u8] ) -> Result<&'a Self, ConcurrentMerkleTreeError>

Casts a byte slice into ConcurrentMerkleTree.

Safety

This is highly unsafe. Ensuring the size and alignment of the byte slice is the caller’s responsibility.

pub unsafe fn struct_from_bytes_mut( bytes_struct: &[u8] ) -> Result<&mut Self, ConcurrentMerkleTreeError>

Casts a byte slice into ConcurrentMerkleTree.

Safety

This is highly unsafe. Ensuring the size and alignment of the byte slice is the caller’s responsibility.

pub unsafe fn roots_from_bytes( bytes_roots: &[u8], length: usize, capacity: usize, first_index: usize, last_index: usize ) -> Result<CyclicBoundedVec<'_, [u8; 32]>, ConcurrentMerkleTreeError>

Casts a byte slice into a CyclicBoundedVec containing MErkle tree roots.

Purpose

This method is meant to be used mostly in Solana programs, where memory constraints are tight and we want to make sure no data is copied.

Safety

This is highly unsafe. This method validates only sizes of slices. Ensuring the alignment and that the slices provide actual data of the Merkle tree is the caller’s responsibility.

Calling it in async context (or anywhere where the underlying data can be moved in the memory) is certainly going to cause undefined behavior.

pub unsafe fn from_bytes( bytes_struct: &'a [u8], bytes_filled_subtrees: &'a [u8], bytes_changelog: &'a [u8], bytes_roots: &'a [u8], bytes_canopy: &'a [u8] ) -> Result<&'a Self, ConcurrentMerkleTreeError>

Casts byte slices into ConcurrentMerkleTree.

• bytes_struct is casted directly into a reference of ConcurrentMerkleTree.
• bytes_filled_subtrees is used to create a BoundedVec directly. That BoundedVec is assigned to the struct.
• bytes_changelog is used to create a CyclicBoundedVec directly. That CyclicBoundedVec is assigned to the struct.
• bytes_roots is used to create a CyclicBoundedVec directly. That CyclicBoundedVec is assigned to the struct.

Purpose

This method is meant to be used mostly in Solana programs, where memory constraints are tight and we want to make sure no data is copied.

Safety

This is highly unsafe. This method validates only sizes of slices. Ensuring the alignment and that the slices provide actual data of the Merkle tree is the caller’s responsibility.

Calling it in async context (or anywhere where the underlying data can be moved in the memory) is certainly going to cause undefined behavior.

pub unsafe fn fill_vectors_mut<'b>( &'b mut self, bytes_filled_subtrees: &'b mut [u8], bytes_changelog: &'b mut [u8], bytes_roots: &'b mut [u8], bytes_canopy: &'b mut [u8], subtrees_length: usize, changelog_length: usize, changelog_capacity: usize, changelog_first_index: usize, changelog_last_index: usize, roots_length: usize, roots_capacity: usize, roots_first_index: usize, roots_last_index: usize, canopy_length: usize ) -> Result<(), ConcurrentMerkleTreeError>

Assigns byte slices into vectors belonging to ConcurrentMerkleTree.

Safety

This is highly unsafe. Ensuring the size and alignment of the byte slices is the caller’s responsibility.

pub unsafe fn from_bytes_init( bytes_struct: &'a mut [u8], bytes_filled_subtrees: &'a mut [u8], bytes_changelog: &'a mut [u8], bytes_roots: &'a mut [u8], bytes_canopy: &'a mut [u8], height: usize, changelog_size: usize, roots_size: usize, canopy_depth: usize ) -> Result<&'a mut Self, ConcurrentMerkleTreeError>

Casts byte slices into ConcurrentMerkleTree.

• bytes_struct is casted directly into a reference of ConcurrentMerkleTree.
• bytes_filled_subtrees is used to create a BoundedVec directly. That BoundedVec is assigned to the struct.
• bytes_changelog is used to create a CyclicBoundedVec directly. That CyclicBoundedVec is assigned to the struct.
• bytes_roots is used to create a CyclicBoundedVec directly. That CyclicBoundedVec is assigned to the struct.

Purpose

This method is meant to be used mostly in Solana programs to initialize a new account which is supposed to store the Merkle tree.

Safety

This is highly unsafe. This method validates only sizes of slices. Ensuring the alignment is the caller’s responsibility.

Calling it in async context (or anywhere where the underlying data can be moved in the memory) is certainly going to cause undefined behavior.

pub unsafe fn from_bytes_mut<'b>( bytes_struct: &'b mut [u8], bytes_filled_subtrees: &'b mut [u8], bytes_changelog: &'b mut [u8], bytes_roots: &'b mut [u8], bytes_canopy: &'b mut [u8] ) -> Result<&'b mut Self, ConcurrentMerkleTreeError>

Casts byte slices into ConcurrentMerkleTree.

• bytes_struct is casted directly into a reference of ConcurrentMerkleTree.
• bytes_filled_subtrees is used to create a BoundedVec directly. That BoundedVec is assigned to the struct.
• bytes_changelog is used to create a CyclicBoundedVec directly. That CyclicBoundedVec is assigned to the struct.
• bytes_roots is used to create a CyclicBoundedVec directly. That CyclicBoundedVec is assigned to the struct.

Purpose

This method is meant to be used mostly in Solana programs, where memory constraints are tight and we want to make sure no data is copied.

Safety

This is highly unsafe. This method validates only sizes of slices. Ensuring the alignment and that the slices provide actual data of the Merkle tree is the caller’s responsibility.

Calling it in async context (or anywhere where the underlying data can be moved in the memory) is certainly going to cause undefined behavior.

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 update_proof_from_canopy( &self, leaf_index: usize, proof: &mut BoundedVec<'_, [u8; 32]> ) -> Result<(), ConcurrentMerkleTreeError>

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

Returns an updated 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_batch( &mut self, leaves: &[&[u8; 32]] ) -> Result<(usize, usize), ConcurrentMerkleTreeError>

Appends a batch of new leaves to the tree.

pub fn get_changelog_event( &self, merkle_tree_account_pubkey: [u8; 32], first_changelog_index: usize, first_sequence_number: usize, num_changelog_entries: usize ) -> Result<ChangelogEvent, ConcurrentMerkleTreeError>

Trait Implementations

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

where H: Hasher + Debug,

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

Formats the value using the given formatter.