Struct miden_core::crypto::merkle::MerkleStore

pub struct MerkleStore<T = BTreeMap<RpoDigest, StoreNode, Global>>where
    T: KvMap<RpoDigest, StoreNode>,{ /* private fields */ }

An in-memory data store for Merkelized data.

This is a in memory data store for Merkle trees, this store allows all the nodes of multiple trees to live as long as necessary and without duplication, this allows the implementation of space efficient persistent data structures.

Example usage:

let mut store: MerkleStore = MerkleStore::new();

// the store is initialized with the SMT empty nodes
assert_eq!(store.num_internal_nodes(), 255);

let tree1 = MerkleTree::new(vec![A, B, C, D, E, F, G, H0]).unwrap();
let tree2 = MerkleTree::new(vec![A, B, C, D, E, F, G, H1]).unwrap();

// populates the store with two merkle trees, common nodes are shared
store.extend(tree1.inner_nodes());
store.extend(tree2.inner_nodes());

// every leaf except the last are the same
for i in 0..7 {
    let idx0 = NodeIndex::new(3, i).unwrap();
    let d0 = store.get_node(ROOT0, idx0).unwrap();
    let idx1 = NodeIndex::new(3, i).unwrap();
    let d1 = store.get_node(ROOT1, idx1).unwrap();
    assert_eq!(d0, d1, "Both trees have the same leaf at pos {i}");
}

// The leafs A-B-C-D are the same for both trees, so are their 2 immediate parents
for i in 0..4 {
    let idx0 = NodeIndex::new(3, i).unwrap();
    let d0 = store.get_path(ROOT0, idx0).unwrap();
    let idx1 = NodeIndex::new(3, i).unwrap();
    let d1 = store.get_path(ROOT1, idx1).unwrap();
    assert_eq!(d0.path[0..2], d1.path[0..2], "Both sub-trees are equal up to two levels");
}

// Common internal nodes are shared, the two added trees have a total of 30, but the store has
// only 10 new entries, corresponding to the 10 unique internal nodes of these trees.
assert_eq!(store.num_internal_nodes() - 255, 10);

Implementations

impl<T> MerkleStore<T>where T: KvMap<RpoDigest, StoreNode>,

pub fn new() -> MerkleStore<T>

Creates an empty MerkleStore instance.

pub fn num_internal_nodes(&self) -> usize

Return a count of the non-leaf nodes in the store.

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

Returns the node at index rooted on the tree root.

Errors

This method can return the following errors:

• RootNotInStore if the root is not present in the store.
• NodeNotInStore if a node needed to traverse from root to index is not present in the store.

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

Returns the node at the specified index and its opening to the root.

The path starts at the sibling of the target leaf.

Errors

This method can return the following errors:

• RootNotInStore if the root is not present in the store.
• NodeNotInStore if a node needed to traverse from root to index is not present in the store.

pub fn get_leaf_depth( &self, root: RpoDigest, tree_depth: u8, index: u64 ) -> Result<u8, MerkleError>

Reconstructs a path from the root until a leaf or empty node and returns its depth.

The tree_depth parameter defines up to which depth the tree will be traversed, starting from root. The maximum value the argument accepts is u64::BITS.

The traversed path from leaf to root will start at the least significant bit of index, and will be executed for tree_depth bits.

Errors

Will return an error if:

• The provided root is not found.
• The path from the root continues to a depth greater than tree_depth.
• The provided tree_depth is greater than `64.
• The provided index is not valid for a depth equivalent to tree_depth. For more information, check NodeIndex::new.

pub fn subset<I, R>(&self, roots: I) -> MerkleStore<T>where I: Iterator<Item = R>, R: Borrow<RpoDigest>,

Returns a subset of this Merkle store such that the returned Merkle store contains all nodes which are descendants of the specified roots.

The roots for which no descendants exist in this Merkle store are ignored.

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

Iterator over the inner nodes of the MerkleStore.

pub fn add_merkle_path( &mut self, index: u64, node: RpoDigest, path: MerklePath ) -> Result<RpoDigest, MerkleError>

Adds all the nodes of a Merkle path represented by path, opening to node. Returns the new root.

This will compute the sibling elements determined by the Merkle path and node, and include all the nodes into the store.

pub fn add_merkle_paths<I>(&mut self, paths: I) -> Result<(), MerkleError>where I: IntoIterator<Item = (u64, RpoDigest, MerklePath)>,

Adds all the nodes of multiple Merkle paths into the store.

This will compute the sibling elements for each Merkle path and include all the nodes into the store.

For further reference, check MerkleStore::add_merkle_path.

pub fn add_merkle_path_set( &mut self, path_set: &MerklePathSet ) -> Result<RpoDigest, MerkleError>

Appends the provided MerklePathSet into the store.

For further reference, check MerkleStore::add_merkle_path.

pub fn set_node( &mut self, root: RpoDigest, index: NodeIndex, value: RpoDigest ) -> Result<RootPath, MerkleError>

Sets a node to value.

Errors

This method can return the following errors:

• RootNotInStore if the root is not present in the store.
• NodeNotInStore if a node needed to traverse from root to index is not present in the store.

pub fn merge_roots( &mut self, left_root: RpoDigest, right_root: RpoDigest ) -> Result<RpoDigest, MerkleError>

Merges two elements and adds the resulting node into the store.

Merges arbitrary values. They may be leafs, nodes, or a mixture of both.

pub fn into_inner(self) -> T

Returns the inner storage of this MerkleStore while consuming self.

Trait Implementations

impl<T> Clone for MerkleStore<T>where T: Clone + KvMap<RpoDigest, StoreNode>,

fn clone(&self) -> MerkleStore<T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> Debug for MerkleStore<T>where T: Debug + KvMap<RpoDigest, StoreNode>,

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

Formats the value using the given formatter.

impl<T> Default for MerkleStore<T>where T: KvMap<RpoDigest, StoreNode>,

fn default() -> MerkleStore<T>

Returns the “default value” for a type.

impl<T> Deserializable for MerkleStore<T>where T: KvMap<RpoDigest, StoreNode>,

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

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.

fn read_batch_from<R>( source: &mut R, num_elements: usize ) -> Result<Vec<Self, Global>, DeserializationError>where R: ByteReader,

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

impl<T> Extend<InnerNodeInfo> for MerkleStore<T>where T: KvMap<RpoDigest, StoreNode>,

fn extend<I>(&mut self, iter: I)where I: IntoIterator<Item = InnerNodeInfo>,

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

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

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

Converts to this type from the input type.

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

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

Converts to this type from the input type.

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

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

Converts to this type from the input type.

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

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

Converts to this type from the input type.

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

fn from(values: T) -> MerkleStore<T>

Converts to this type from the input type.

impl<T> FromIterator<(RpoDigest, StoreNode)> for MerkleStore<T>where T: KvMap<RpoDigest, StoreNode>,

fn from_iter<I>(iter: I) -> MerkleStore<T>where I: IntoIterator<Item = (RpoDigest, StoreNode)>,

Creates a value from an iterator.

impl<T> FromIterator<InnerNodeInfo> for MerkleStore<T>where T: KvMap<RpoDigest, StoreNode>,

fn from_iter<I>(iter: I) -> MerkleStore<T>where I: IntoIterator<Item = InnerNodeInfo>,

Creates a value from an iterator.

impl<T> PartialEq<MerkleStore<T>> for MerkleStore<T>where T: PartialEq<T> + KvMap<RpoDigest, StoreNode>,

fn eq(&self, other: &MerkleStore<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T> Serializable for MerkleStore<T>where T: KvMap<RpoDigest, StoreNode>,

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

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

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

Serializes self into a vector of bytes.

fn write_batch_into<W>(source: &[Self], target: &mut W)where W: ByteWriter,

Serializes all elements of the source 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.

impl<T> Eq for MerkleStore<T>where T: Eq + KvMap<RpoDigest, StoreNode>,

impl<T> StructuralEq for MerkleStore<T>where T: KvMap<RpoDigest, StoreNode>,

impl<T> StructuralPartialEq for MerkleStore<T>where T: KvMap<RpoDigest, StoreNode>,