Struct MerkleStore 

pub struct MerkleStore { /* 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 leaves 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 MerkleStore

pub fn new() -> MerkleStore

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: Word, index: NodeIndex, ) -> Result<Word, 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: Word, index: NodeIndex, ) -> Result<MerkleProof, 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 has_path(&self, root: Word, index: NodeIndex) -> bool

Returns true if a valid path exists from root to the specified index, false otherwise.

This method checks if all nodes needed to traverse from root to index are present in the store, without building the actual path. It is more efficient than get_path when only existence verification is needed.

pub fn get_leaf_depth( &self, root: Word, 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: Word, root_index: NodeIndex, tree_depth: u8, ) -> Result<Option<(NodeIndex, Word)>, 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

where I: Iterator<Item = R>, R: Borrow<Word>,

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: Word, max_depth: u8, ) -> impl Iterator<Item = (NodeIndex, Word)>

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: Word, path: MerklePath, ) -> Result<Word, 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, Word, 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: Word, index: NodeIndex, value: Word, ) -> 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: Word, right_root: Word, ) -> Result<Word, MerkleError>

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

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

pub fn into_inner(self) -> HashMap<Word, StoreNode>

Returns the inner storage of this MerkleStore while consuming self.

Trait Implementations

impl Clone for MerkleStore

fn clone(&self) -> MerkleStore

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for MerkleStore

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

Formats the value using the given formatter.

impl Default for MerkleStore

fn default() -> MerkleStore

Returns the “default value” for a type.

impl Deserializable for MerkleStore

fn min_serialized_size() -> usize

Minimum serialized size: u64 length prefix (0 entries).

fn read_from<R>(source: &mut R) -> Result<MerkleStore, 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_from_bytes_with_budget( bytes: &[u8], budget: usize, ) -> Result<Self, DeserializationError>

Deserializes Self from bytes with a byte budget limit.

impl<'de> Deserialize<'de> for MerkleStore

fn deserialize<__D>( __deserializer: __D, ) -> Result<MerkleStore, <__D as Deserializer<'de>>::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Extend<InnerNodeInfo> for MerkleStore

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 From<&MerkleTree> for MerkleStore

fn from(value: &MerkleTree) -> MerkleStore

Converts to this type from the input type.

impl From<&Mmr> for MerkleStore

fn from(value: &Mmr) -> MerkleStore

Converts to this type from the input type.

impl From<&PartialMerkleTree> for MerkleStore

fn from(value: &PartialMerkleTree) -> MerkleStore

Converts to this type from the input type.

impl<const DEPTH: u8> From<&SimpleSmt<DEPTH>> for MerkleStore

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

Converts to this type from the input type.

impl From<&Smt> for MerkleStore

fn from(value: &Smt) -> MerkleStore

Converts to this type from the input type.

impl FromIterator<(Word, StoreNode)> for MerkleStore

fn from_iter<I>(iter: I) -> MerkleStore

where I: IntoIterator<Item = (Word, StoreNode)>,

Creates a value from an iterator.

impl FromIterator<InnerNodeInfo> for MerkleStore

fn from_iter<I>(iter: I) -> MerkleStore

where I: IntoIterator<Item = InnerNodeInfo>,

Creates a value from an iterator.

impl PartialEq for MerkleStore

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

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>

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 Serialize for MerkleStore

fn serialize<__S>( &self, __serializer: __S, ) -> Result<<__S as Serializer>::Ok, <__S as Serializer>::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl Eq for MerkleStore

impl StructuralPartialEq for MerkleStore