Struct MerkleStore

pub struct MerkleStore<T: KvMap<RpoDigest, StoreNode> = BTreeMap<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: KvMap<RpoDigest, StoreNode>> MerkleStore<T>

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>

Returns the depth of the first leaf or an empty node encountered while traversing the tree from the specified root down according to the provided index.

The tree_depth parameter specifies the depth of the tree rooted at root. The maximum value the argument accepts is u64::BITS.

Errors

Will return an error if:

• The provided root is not found.
• The provided tree_depth is greater than 64.
• The provided index is not valid for a depth equivalent to tree_depth.
• No leaf or an empty node was found while traversing the tree down to tree_depth.

pub fn find_lone_leaf( &self, root: RpoDigest, root_index: NodeIndex, tree_depth: u8, ) -> Result<Option<(NodeIndex, RpoDigest)>, MerkleError>

Returns index and value of a leaf node which is the only leaf node in a subtree defined by the provided root. If the subtree contains zero or more than one leaf nodes None is returned.

The tree_depth parameter specifies the depth of the parent tree such that root is located in this tree at root_index. The maximum value the argument accepts is u64::BITS.

Errors

Will return an error if:

• The provided root is not found.
• The provided tree_depth is greater than 64.
• The provided root_index has depth greater than tree_depth.
• A lone node at depth tree_depth is not a leaf node.

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 non_empty_leaves( &self, root: RpoDigest, max_depth: u8, ) -> impl Iterator<Item = (NodeIndex, RpoDigest)> + '_

Iterator over the non-empty leaves of the Merkle tree associated with the specified root and max_depth.

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 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 + KvMap<RpoDigest, StoreNode>> Clone for MerkleStore<T>

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 + KvMap<RpoDigest, StoreNode>> Debug for MerkleStore<T>

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

Formats the value using the given formatter.

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

fn default() -> Self

Returns the “default value” for a type.

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

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>> Extend<InnerNodeInfo> for MerkleStore<T>

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

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: KvMap<RpoDigest, StoreNode>> From<&MerkleTree> for MerkleStore<T>

fn from(value: &MerkleTree) -> Self

Converts to this type from the input type.

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

fn from(value: &Mmr) -> Self

Converts to this type from the input type.

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

fn from(value: &PartialMerkleTree) -> Self

Converts to this type from the input type.

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

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

Converts to this type from the input type.

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

fn from(value: &Smt) -> Self

Converts to this type from the input type.

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

fn from(values: T) -> Self

Converts to this type from the input type.

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

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

Creates a value from an iterator.

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

fn from_iter<I: IntoIterator<Item = InnerNodeInfo>>(iter: I) -> Self

Creates a value from an iterator.

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

fn eq(&self, other: &MerkleStore<T>) -> 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<T: KvMap<RpoDigest, StoreNode>> Serializable for MerkleStore<T>

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

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

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

Serializes self into a vector of bytes.

fn get_size_hint(&self) -> usize

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

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

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