Struct IndexedMerkleTree

#[repr(C)]
pub struct IndexedMerkleTree<H, I, const HEIGHT: usize, const NET_HEIGHT: usize>
where
    H: Hasher,
    I: CheckedAdd + CheckedSub + Copy + Clone + Debug + PartialOrd + ToBytes + TryFrom<usize> + Unsigned,
    usize: From<I>,
{
    pub merkle_tree: ConcurrentMerkleTree<H, HEIGHT>,
    pub indexed_changelog: CyclicBoundedVec<IndexedChangelogEntry<I, NET_HEIGHT>>,
    /* private fields */
}

Fields

merkle_tree: ConcurrentMerkleTree<H, HEIGHT>

indexed_changelog: CyclicBoundedVec<IndexedChangelogEntry<I, NET_HEIGHT>>

Implementations

impl<H, I, const HEIGHT: usize, const NET_HEIGHT: usize> IndexedMerkleTree<H, I, HEIGHT, NET_HEIGHT>

where H: Hasher, I: CheckedAdd + CheckedSub + Copy + Clone + Debug + PartialOrd + ToBytes + TryFrom<usize> + Unsigned, usize: From<I>,

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, indexed_changelog_size: usize, ) -> usize

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

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

pub fn add_highest_element(&mut self) -> Result<(), IndexedMerkleTreeError>

Add the hightest element with a maximum value allowed by the prime field.

Initializing an indexed Merkle tree not only with the lowest element (mandatory for the IMT algorithm to work), but also the highest element, makes non-inclusion proofs easier - there is no special case needed for the first insertion.

However, it comes with a tradeoff - the space available in the tree becomes lower by 1.

pub fn indexed_changelog_index(&self) -> usize

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

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 patch_elements_and_proof( &mut self, indexed_changelog_index: usize, changelog_index: &mut usize, new_element: &mut IndexedElement<I>, low_element: &mut IndexedElement<I>, low_element_next_value: &mut BigUint, low_leaf_proof: &mut BoundedVec<[u8; 32]>, ) -> Result<(), IndexedMerkleTreeError>

Iterates over indexed changelog and every time an entry corresponding to the provided low_element is found, it patches:

• Changelog index - indexed changelog entries contain corresponding changelog indices.
• New element - changes might impact the next_index field, which in such case is updated.
• Low element - it might completely change if a change introduced an element in our range.
• Merkle proof.

pub fn update( &mut self, changelog_index: usize, indexed_changelog_index: usize, new_element_value: BigUint, low_element: IndexedElement<I>, low_element_next_value: BigUint, low_leaf_proof: &mut BoundedVec<[u8; 32]>, ) -> Result<IndexedMerkleTreeUpdate<I>, IndexedMerkleTreeError>

Methods from Deref<Target = ConcurrentMerkleTree<H, HEIGHT>>

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, I, const HEIGHT: usize, const NET_HEIGHT: usize> Debug for IndexedMerkleTree<H, I, HEIGHT, NET_HEIGHT>

where H: Hasher + Debug, I: CheckedAdd + CheckedSub + Copy + Clone + Debug + PartialOrd + ToBytes + TryFrom<usize> + Unsigned + Debug, usize: From<I>,

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

Formats the value using the given formatter.

impl<H, I, const HEIGHT: usize, const NET_HEIGHT: usize> Deref for IndexedMerkleTree<H, I, HEIGHT, NET_HEIGHT>

where H: Hasher, I: CheckedAdd + CheckedSub + Copy + Clone + Debug + PartialOrd + ToBytes + TryFrom<usize> + Unsigned, usize: From<I>,

type Target = ConcurrentMerkleTree<H, HEIGHT>

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl<H, I, const HEIGHT: usize, const NET_HEIGHT: usize> DerefMut for IndexedMerkleTree<H, I, HEIGHT, NET_HEIGHT>

where H: Hasher, I: CheckedAdd + CheckedSub + Copy + Clone + Debug + PartialOrd + ToBytes + TryFrom<usize> + Unsigned, usize: From<I>,

fn deref_mut(&mut self) -> &mut Self::Target

Mutably dereferences the value.

impl<H, I, const HEIGHT: usize, const NET_HEIGHT: usize> PartialEq for IndexedMerkleTree<H, I, HEIGHT, NET_HEIGHT>

where H: Hasher, I: CheckedAdd + CheckedSub + Copy + Clone + Debug + PartialOrd + ToBytes + TryFrom<usize> + Unsigned, usize: From<I>,

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.