Struct SparseMerklePath 

pub struct SparseMerklePath { /* private fields */ }

A different representation of MerklePath designed for memory efficiency for Merkle paths with empty nodes.

Empty nodes in the path are stored only as their position, represented with a bitmask. A maximum of 64 nodes (SMT_MAX_DEPTH) can be stored (empty and non-empty). The more nodes in a path are empty, the less memory this struct will use. This type calculates empty nodes on-demand when iterated through, converted to a MerklePath, or an empty node is retrieved with SparseMerklePath::at_depth(), which will incur overhead.

NOTE: This type assumes that Merkle paths always span from the root of the tree to a leaf. Partial paths are not supported.

Implementations

impl SparseMerklePath

pub fn from_parts( empty_nodes_mask: u64, nodes: Vec<Word>, ) -> Result<SparseMerklePath, MerkleError>

Constructs a new sparse Merkle path from a bitmask of empty nodes and a vector of non-empty nodes.

The empty_nodes_mask is a bitmask where each set bit indicates that the node at that depth is empty. The least significant bit (bit 0) describes depth 1 node (root’s children). The bit index + 1 is equal to node’s depth. The nodes vector must contain the non-empty nodes in depth order.

Errors

• MerkleError::InvalidPathLength if the provided nodes vector is shorter than the minimum length required by the empty_nodes_mask.
• MerkleError::DepthTooBig if the total depth of the path (calculated from the empty_nodes_mask and nodes) is greater than SMT_MAX_DEPTH.

pub fn from_sized_iter<I>(iterator: I) -> Result<SparseMerklePath, MerkleError>

where I: IntoIterator<Item = Word>, <I as IntoIterator>::IntoIter: ExactSizeIterator,

Constructs a sparse Merkle path from an iterator over Merkle nodes that also knows its exact size (such as iterators created with Vec::into_iter). The iterator must be in order of deepest to shallowest.

Knowing the size is necessary to calculate the depth of the tree, which is needed to detect which nodes are empty nodes.

Errors

Returns MerkleError::DepthTooBig if tree_depth is greater than SMT_MAX_DEPTH.

pub fn depth(&self) -> u8

Returns the total depth of this path, i.e., the number of nodes this path represents.

pub fn at_depth(&self, node_depth: NonZero<u8>) -> Result<Word, MerkleError>

Get a specific node in this path at a given depth.

The depth parameter is defined in terms of self.depth(). Merkle paths conventionally do not include the root, so the shallowest depth is 1, and the deepest depth is self.depth().

Errors

Returns MerkleError::DepthTooBig if node_depth is greater than the total depth of this path.

pub fn into_parts(self) -> (u64, Vec<Word>)

Deconstructs this path into its component parts.

Returns a tuple containing:

• a bitmask where each set bit indicates that the node at that depth is empty. The least significant bit (bit 0) describes depth 1 node (root’s children).
• a vector of non-empty nodes in depth order.

pub fn iter(&self) -> impl ExactSizeIterator

Constructs a borrowing iterator over the nodes in this path. Starts from the leaf and iterates toward the root (excluding the root).

pub fn compute_root( &self, index: u64, node_to_prove: Word, ) -> Result<Word, MerkleError>

Computes the Merkle root for this opening.

pub fn verify( &self, index: u64, node: Word, _: &Word, ) -> Result<(), MerkleError>

Verifies the Merkle opening proof towards the provided root.

Errors

Returns an error if:

• provided node index is invalid.
• root calculated during the verification differs from the provided one.

pub fn authenticated_nodes( &self, index: u64, node_to_prove: Word, ) -> Result<InnerNodeIterator<'_>, MerkleError>

Given the node this path opens to, return an iterator of all the nodes that are known via this path.

Each item in the iterator is an InnerNodeInfo, containing the hash of a node as .value, and its two children as .left and .right. The very first item in that iterator will be the parent of node_to_prove as stored in this SparseMerklePath.

From there, the iterator will continue to yield every further parent and both of its children, up to and including the root node.

If node_to_prove is not the node this path is an opening to, or index is not the correct index for that node, the returned nodes will be meaningless.

Errors

Returns an error if the specified index is not valid for this path.

Trait Implementations

impl Clone for SparseMerklePath

fn clone(&self) -> SparseMerklePath

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for SparseMerklePath

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

Formats the value using the given formatter.

impl Default for SparseMerklePath

fn default() -> SparseMerklePath

Returns the “default value” for a type.

impl Deserializable for SparseMerklePath

fn read_from<R>( source: &mut R, ) -> Result<SparseMerklePath, 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.

impl From<SparseMerklePath> for MerklePath

fn from(sparse_path: SparseMerklePath) -> MerklePath

Converts to this type from the input type.

impl From<SparseMerklePath> for Vec<Word>

fn from(path: SparseMerklePath) -> Vec<Word>

Converts to this type from the input type.

impl<'p> IntoIterator for &'p SparseMerklePath

type Item = <SparseMerklePathIter<'p> as Iterator>::Item

The type of the elements being iterated over.

type IntoIter = SparseMerklePathIter<'p>

Which kind of iterator are we turning this into?

fn into_iter(self) -> SparseMerklePathIter<'p>

Creates an iterator from a value.

impl IntoIterator for SparseMerklePath

type IntoIter = SparseMerklePathIter<'static>

Which kind of iterator are we turning this into?

type Item = <<SparseMerklePath as IntoIterator>::IntoIter as Iterator>::Item

The type of the elements being iterated over.

fn into_iter(self) -> SparseMerklePathIter<'static>

Creates an iterator from a value.

impl PartialEq<MerklePath> for SparseMerklePath

fn eq(&self, rhs: &MerklePath) -> 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 PartialEq<SparseMerklePath> for MerklePath

fn eq(&self, rhs: &SparseMerklePath) -> 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 PartialEq for SparseMerklePath

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

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 TryFrom<MerklePath> for SparseMerklePath

fn try_from(path: MerklePath) -> Result<SparseMerklePath, MerkleError>

Errors

This conversion returns MerkleError::DepthTooBig if the path length is greater than SMT_MAX_DEPTH.

type Error = MerkleError

The type returned in the event of a conversion error.

impl Eq for SparseMerklePath

impl StructuralPartialEq for SparseMerklePath