#[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>,
}
Expand description
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
).
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§
source§impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>
impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>
pub fn new() -> Self
pub fn is_initialized(&self) -> bool
sourcepub fn initialize(&mut self) -> Result<Node, ConcurrentMerkleTreeError>
pub fn initialize(&mut self) -> Result<Node, ConcurrentMerkleTreeError>
This is the trustless initialization method that should be used in most cases.
sourcepub fn initialize_with_root(
&mut self,
root: Node,
rightmost_leaf: Node,
proof_vec: &[Node],
index: u32
) -> Result<Node, ConcurrentMerkleTreeError>
pub fn initialize_with_root( &mut self, root: Node, rightmost_leaf: Node, proof_vec: &[Node], index: u32 ) -> Result<Node, 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.
sourcepub fn prove_tree_is_empty(&self) -> Result<(), ConcurrentMerkleTreeError>
pub fn prove_tree_is_empty(&self) -> Result<(), ConcurrentMerkleTreeError>
Errors if one of the leaves of the current merkle tree is non-EMPTY
sourcepub fn get_change_log(&self) -> Box<ChangeLog<MAX_DEPTH>>
pub fn get_change_log(&self) -> Box<ChangeLog<MAX_DEPTH>>
Returns the most recent changelog
sourcepub fn prove_leaf(
&self,
current_root: Node,
leaf: Node,
proof_vec: &[Node],
leaf_index: u32
) -> Result<(), ConcurrentMerkleTreeError>
pub fn prove_leaf( &self, current_root: Node, leaf: Node, proof_vec: &[Node], leaf_index: u32 ) -> 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
.
sourcepub fn append(&mut self, node: Node) -> Result<Node, ConcurrentMerkleTreeError>
pub fn append(&mut self, node: Node) -> Result<Node, ConcurrentMerkleTreeError>
Appending a non-empty Node will always succeed .
sourcepub fn fill_empty_or_append(
&mut self,
current_root: Node,
leaf: Node,
proof_vec: &[Node],
index: u32
) -> Result<Node, ConcurrentMerkleTreeError>
pub fn fill_empty_or_append( &mut self, current_root: Node, leaf: Node, proof_vec: &[Node], index: u32 ) -> Result<Node, 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.
sourcepub fn set_leaf(
&mut self,
current_root: Node,
previous_leaf: Node,
new_leaf: Node,
proof_vec: &[Node],
index: u32
) -> Result<Node, ConcurrentMerkleTreeError>
pub fn set_leaf( &mut self, current_root: Node, previous_leaf: Node, new_leaf: Node, proof_vec: &[Node], index: u32 ) -> Result<Node, ConcurrentMerkleTreeError>
This method will update the leaf at index
.
However if the proof cannot be verified, this method will fail.
Trait Implementations§
source§impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> Clone for ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>
impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> Clone for ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>
source§fn clone(&self) -> ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>
fn clone(&self) -> ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read moresource§impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> Default for ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>
impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> Default for ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>
source§impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> Zeroable for ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>
impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> Zeroable for ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>
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>
Auto Trait Implementations§
impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> RefUnwindSafe for ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>
impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> Send for ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>
impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> Sync for ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>
impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> Unpin for ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>
impl<const MAX_DEPTH: usize, const MAX_BUFFER_SIZE: usize> UnwindSafe for ConcurrentMerkleTree<MAX_DEPTH, MAX_BUFFER_SIZE>
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> CheckedBitPattern for Twhere
T: AnyBitPattern,
impl<T> CheckedBitPattern for Twhere T: AnyBitPattern,
§type Bits = T
type Bits = T
Self
must have the same layout as the specified Bits
except for
the possible invalid bit patterns being checked during
is_valid_bit_pattern
.source§fn is_valid_bit_pattern(_bits: &T) -> bool
fn is_valid_bit_pattern(_bits: &T) -> bool
bits
as &Self
.