Struct SimpleSmt

pub struct SimpleSmt<const DEPTH: u8> { /* private fields */ }

A sparse Merkle tree with 64-bit keys and 4-element leaf values, without compaction.

The root of the tree is recomputed on each new leaf update.

Implementations

impl<const DEPTH: u8> SimpleSmt<DEPTH>

pub const EMPTY_VALUE: [BaseElement; 4]

The default value used to compute the hash of empty leaves

pub fn new() -> Result<SimpleSmt<DEPTH>, MerkleError>

Returns a new SimpleSmt.

All leaves in the returned tree are set to [ZERO; 4].

Errors

Returns an error if DEPTH is 0 or is greater than 64.

pub fn with_leaves( entries: impl IntoIterator<Item = (u64, [BaseElement; 4])>, ) -> Result<SimpleSmt<DEPTH>, MerkleError>

Returns a new SimpleSmt instantiated with leaves set as specified by the provided entries.

All leaves omitted from the entries list are set to [ZERO; 4].

Errors

Returns an error if:

• If the depth is 0 or is greater than 64.
• The number of entries exceeds the maximum tree capacity, that is 2^{depth}.
• The provided entries contain multiple values for the same key.

pub fn with_contiguous_leaves( entries: impl IntoIterator<Item = [BaseElement; 4]>, ) -> Result<SimpleSmt<DEPTH>, MerkleError>

Wrapper around SimpleSmt::with_leaves which inserts leaves at contiguous indices starting at index 0.

pub const fn depth(&self) -> u8

Returns the depth of the tree

pub fn root(&self) -> RpoDigest

Returns the root of the tree

pub fn num_leaves(&self) -> usize

Returns the number of non-empty leaves in this tree.

pub fn get_leaf(&self, key: &LeafIndex<DEPTH>) -> [BaseElement; 4]

Returns the leaf at the specified index.

pub fn get_node(&self, index: NodeIndex) -> Result<RpoDigest, MerkleError>

Returns a node at the specified index.

Errors

Returns an error if the specified index has depth set to 0 or the depth is greater than the depth of this Merkle tree.

pub fn open(&self, key: &LeafIndex<DEPTH>) -> ValuePath

Returns an opening of the leaf associated with key. Conceptually, an opening is a Merkle path to the leaf, as well as the leaf itself.

pub fn is_empty(&self) -> bool

Returns a boolean value indicating whether the SMT is empty.

pub fn leaves(&self) -> impl Iterator<Item = (u64, &[BaseElement; 4])>

Returns an iterator over the leaves of this SimpleSmt.

pub fn inner_nodes(&self) -> impl Iterator<Item = InnerNodeInfo>

Returns an iterator over the inner nodes of this SimpleSmt.

pub fn insert( &mut self, key: LeafIndex<DEPTH>, value: [BaseElement; 4], ) -> [BaseElement; 4]

Inserts a value at the specified key, returning the previous value associated with that key. Recall that by definition, any key that hasn’t been updated is associated with EMPTY_WORD.

This also recomputes all hashes between the leaf (associated with the key) and the root, updating the root itself.

pub fn compute_mutations( &self, kv_pairs: impl IntoIterator<Item = (LeafIndex<DEPTH>, [BaseElement; 4])>, ) -> MutationSet<DEPTH, LeafIndex<DEPTH>, [BaseElement; 4]>

Computes what changes are necessary to insert the specified key-value pairs into this Merkle tree, allowing for validation before applying those changes.

This method returns a MutationSet, which contains all the information for inserting kv_pairs into this Merkle tree already calculated, including the new root hash, which can be queried with MutationSet::root(). Once a mutation set is returned, SimpleSmt::apply_mutations() can be called in order to commit these changes to the Merkle tree, or drop() to discard them.

Example

let mut smt: SimpleSmt<3> = SimpleSmt::new().unwrap();
let pair = (LeafIndex::default(), Word::default());
let mutations = smt.compute_mutations(vec![pair]);
assert_eq!(mutations.root(), *EmptySubtreeRoots::entry(3, 0));
smt.apply_mutations(mutations);
assert_eq!(smt.root(), *EmptySubtreeRoots::entry(3, 0));

pub fn apply_mutations( &mut self, mutations: MutationSet<DEPTH, LeafIndex<DEPTH>, [BaseElement; 4]>, ) -> Result<(), MerkleError>

Applies the prospective mutations computed with SimpleSmt::compute_mutations() to this tree.

Errors

If mutations was computed on a tree with a different root than this one, returns MerkleError::ConflictingRoots with a two-item alloc::vec::Vec. The first item is the root hash the mutations were computed against, and the second item is the actual current root of this tree.

pub fn apply_mutations_with_reversion( &mut self, mutations: MutationSet<DEPTH, LeafIndex<DEPTH>, [BaseElement; 4]>, ) -> Result<MutationSet<DEPTH, LeafIndex<DEPTH>, [BaseElement; 4]>, MerkleError>

Applies the prospective mutations computed with SimpleSmt::compute_mutations() to this tree and returns the reverse mutation set.

Applying the reverse mutation sets to the updated tree will revert the changes.

Errors

If mutations was computed on a tree with a different root than this one, returns MerkleError::ConflictingRoots with a two-item alloc::vec::Vec. The first item is the root hash the mutations were computed against, and the second item is the actual current root of this tree.

pub fn set_subtree<const SUBTREE_DEPTH: u8>( &mut self, subtree_insertion_index: u64, subtree: SimpleSmt<SUBTREE_DEPTH>, ) -> Result<RpoDigest, MerkleError>

Inserts a subtree at the specified index. The depth at which the subtree is inserted is computed as DEPTH - SUBTREE_DEPTH.

Returns the new root.

Trait Implementations

impl<const DEPTH: u8> Clone for SimpleSmt<DEPTH>

fn clone(&self) -> SimpleSmt<DEPTH>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<const DEPTH: u8> Debug for SimpleSmt<DEPTH>

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

Formats the value using the given formatter.

impl<T, const DEPTH: u8> From<&SimpleSmt<DEPTH>> for MerkleStore<T>

where T: KvMap<RpoDigest, StoreNode>,

fn from(value: &SimpleSmt<DEPTH>) -> MerkleStore<T>

Converts to this type from the input type.

impl<const DEPTH: u8> PartialEq for SimpleSmt<DEPTH>

fn eq(&self, other: &SimpleSmt<DEPTH>) -> 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.

impl<const DEPTH: u8> Eq for SimpleSmt<DEPTH>

impl<const DEPTH: u8> StructuralPartialEq for SimpleSmt<DEPTH>