Struct SparseMerkleTree

pub struct SparseMerkleTree<'a, const N: usize, const M: usize, F: FieldElement, H: FieldHasher<F, 2>, S: StorageAdapter<Value = F>> {
    store: S,
    hasher: H,
    empty_nodes: &'a [F; M],
}

The Sparse Merkle Tree struct.

SMT stores a set of leaves represented in a map and a set of empty hashes that it uses to represent the sparse areas of the tree.

The trait param N is the depth of the tree. A tree with a depth of N will have N + 1 levels.

Fields

store: S

A map from leaf indices to leaf data stored as field elements.

hasher: H

The hasher used to build the Merkle tree.

empty_nodes: &'a [F; M]

An array of empty hashes hashed with themselves N times.

Implementations

impl<'a, const N: usize, const M: usize, F: FieldElement, H: FieldHasher<F, 2>, S: StorageAdapter<Value = F>> SparseMerkleTree<'a, N, M, F, H, S>

pub fn new(store: S, hasher: H, empty_nodes: &'a [F; M]) -> Self

Creates a new SMT

pub fn insert_batch(&mut self, leaves: Vec<(F, F)>) -> ContractResult

Takes a batch of field elements, inserts these hashes into the tree, and updates the Merkle root.

pub fn remove_leaves(&mut self, leaves: Vec<(F, F)>) -> ContractResult

pub fn root(&self) -> F

Returns the Merkle tree root.

fn recompute_tree(&mut self, dirty_idxs: &mut Vec<BigUint>) -> ContractResult

Recomputes the Merkle tree depth first from the bottom of the tree

pub fn prove_membership(&self, pos: &F) -> Path<N, F, H>

Give the path leading from the leaf at index up to the root. This is a “proof” in the sense of “valid path in a Merkle tree”, not a ZK argument.

pub fn get_leaf(&self, pos: &F) -> F

Fast lookup for leaf. The SMT can be used as a generic container for objects with very little overhead using this method.

fn get_node(&self, idx: &BigUint) -> F

fn put_node(&mut self, key: BigUint, value: F) -> ContractResult

fn remove_node(&mut self, key: &BigUint) -> ContractResult

Trait Implementations

impl<'a, const N: usize, const M: usize, F: Clone + FieldElement, H: Clone + FieldHasher<F, 2>, S: Clone + StorageAdapter<Value = F>> Clone for SparseMerkleTree<'a, N, M, F, H, S>

fn clone(&self) -> SparseMerkleTree<'a, N, M, F, H, S>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<'a, const N: usize, const M: usize, F: Debug + FieldElement, H: Debug + FieldHasher<F, 2>, S: Debug + StorageAdapter<Value = F>> Debug for SparseMerkleTree<'a, N, M, F, H, S>

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

Formats the value using the given formatter.