Struct Smt

pub struct Smt { /* private fields */ }

Sparse Merkle tree mapping 256-bit keys to 256-bit values. Both keys and values are represented by 4 field elements.

All leaves sit at depth 64. The most significant element of the key is used to identify the leaf to which the key maps.

A leaf is either empty, or holds one or more key-value pairs. An empty leaf hashes to the empty word. Otherwise, a leaf hashes to the hash of its key-value pairs, ordered by key first, value second.

Implementations

impl Smt

pub const EMPTY_VALUE: Word = _

The default value used to compute the hash of empty leaves

pub fn new() -> Self

Returns a new Smt.

All leaves in the returned tree are set to Self::EMPTY_VALUE.

pub fn with_entries( entries: impl IntoIterator<Item = (RpoDigest, Word)>, ) -> Result<Self, MerkleError>

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

All leaves omitted from the entries list are set to Self::EMPTY_VALUE.

Errors

Returns an error if the provided entries contain multiple values for the same key.

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 get_leaf(&self, key: &RpoDigest) -> SmtLeaf

Returns the leaf to which key maps

pub fn get_value(&self, key: &RpoDigest) -> Word

Returns the value associated with key

pub fn open(&self, key: &RpoDigest) -> SmtProof

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 = (LeafIndex<SMT_DEPTH>, &SmtLeaf)>

Returns an iterator over the leaves of this Smt.

pub fn entries(&self) -> impl Iterator<Item = &(RpoDigest, Word)>

Returns an iterator over the key-value pairs of this Smt.

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

Returns an iterator over the inner nodes of this Smt.

pub fn insert(&mut self, key: RpoDigest, value: Word) -> Word

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 Self::EMPTY_VALUE.

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 = (RpoDigest, Word)>, ) -> MutationSet<SMT_DEPTH, RpoDigest, Word>

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, Smt::apply_mutations() can be called in order to commit these changes to the Merkle tree, or drop() to discard them.

Example

let mut smt = Smt::new();
let pair = (RpoDigest::default(), Word::default());
let mutations = smt.compute_mutations(vec![pair]);
assert_eq!(mutations.root(), *EmptySubtreeRoots::entry(SMT_DEPTH, 0));
smt.apply_mutations(mutations);
assert_eq!(smt.root(), *EmptySubtreeRoots::entry(SMT_DEPTH, 0));

pub fn apply_mutations( &mut self, mutations: MutationSet<SMT_DEPTH, RpoDigest, Word>, ) -> Result<(), MerkleError>

Apply the prospective mutations computed with Smt::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 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.

Trait Implementations

impl Clone for Smt

fn clone(&self) -> Smt

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for Smt

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

Formats the value using the given formatter.

impl Default for Smt

fn default() -> Self

Returns the “default value” for a type.

impl Deserializable for Smt

fn read_from<R: ByteReader>( source: &mut R, ) -> Result<Self, DeserializationError>

Reads a sequence of bytes from the provided source, attempts to deserialize these bytes into Self, and returns the result.

fn read_from_bytes(bytes: &[u8]) -> Result<Self, DeserializationError>

Attempts to deserialize the provided bytes into Self and returns the result.

impl<T: KvMap<RpoDigest, StoreNode>> From<&Smt> for MerkleStore<T>

fn from(value: &Smt) -> Self

Converts to this type from the input type.

impl PartialEq for Smt

fn eq(&self, other: &Smt) -> 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 Serializable for Smt

fn write_into<W: ByteWriter>(&self, target: &mut W)

Serializes self into bytes and writes these bytes into the target.

fn get_size_hint(&self) -> usize

Returns an estimate of how many bytes are needed to represent self.

fn to_bytes(&self) -> Vec<u8>

Serializes self into a vector of bytes.

impl Eq for Smt

impl StructuralPartialEq for Smt