Struct SimpleSmt

Source

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

Expand description

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§

Source §

impl<const DEPTH: u8> SimpleSmt<DEPTH>

Source

pub const EMPTY_VALUE: [BaseElement; 4]

The default value used to compute the hash of empty leaves

Source

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.

Source

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.

Source

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.

Source

pub const fn depth(&self) -> u8

Returns the depth of the tree

Source

pub fn root(&self) -> RpoDigest

Returns the root of the tree

Source

pub fn num_leaves(&self) -> usize

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

Source

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

Returns the leaf at the specified index.

Source

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.

Source

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.

Source

pub fn is_empty(&self) -> bool

Returns a boolean value indicating whether the SMT is empty.

Source

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

Returns an iterator over the leaves of this SimpleSmt.

Source

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

Returns an iterator over the inner nodes of this SimpleSmt.

Source

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.

Source

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));

Source

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.

Source

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.

Source