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 from_raw_parts( inner_nodes: BTreeMap<NodeIndex, InnerNode>, leaves: BTreeMap<u64, [BaseElement; 4]>, root: RpoDigest, ) -> SimpleSmt<DEPTH>

Returns a new SimpleSmt instantiated from already computed leaves and nodes.

This function performs minimal consistency checking. It is the caller’s responsibility to ensure the passed arguments are correct and consistent with each other.

Panics

With debug assertions on, this function panics if root does not match the root node in inner_nodes.

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 duplicate 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>