Struct BalancedHashedMerkleTree

pub struct BalancedHashedMerkleTree<'a, const N: usize>
where
    [(); { _ }]:,
{ /* private fields */ }

Merkle Tree variant that has hash-sized leaves and is fully balanced according to configured generic parameter.

This can be considered a general case of UnbalancedHashedMerkleTree. The root and proofs are identical for both in case the number of leaves is a power of two. For the number of leaves that is a power of two UnbalancedHashedMerkleTree is useful when a single proof needs to be generated and the number of leaves is very large (it can generate proofs with very little RAM usage compared to this version).

This Merkle Tree implementation is best suited for use cases when proofs for all (or most) of the elements need to be generated and the whole tree easily fits into memory. It can also be constructed and proofs can be generated efficiently without heap allocations.

With all parameters of the tree known statically, it results in the most efficient version of the code being generated for a given set of parameters.

Implementations

impl<'a, const N: usize> BalancedHashedMerkleTree<'a, N>

where [(); { _ }]:,

pub fn new(leaves: &'a [[u8; 32]; N]) -> Self

Create a new tree from a fixed set of elements.

The data structure is statically allocated and might be too large to fit on the stack! If that is the case, use new_boxed() method.

pub fn new_in<'b>( instance: &'b mut MaybeUninit<Self>, leaves: &'a [[u8; 32]; N], ) -> &'b mut Self

Like Self::new(), but used pre-allocated memory for instantiation

pub fn new_boxed(leaves: &'a [[u8; 32]; N]) -> Box<Self>

Like Self::new(), but creates heap-allocated instance, avoiding excessive stack usage for large trees

pub fn compute_root_only(leaves: &[[u8; 32]; N]) -> [u8; 32]

where [(); { _ }]:,

Compute Merkle Tree Root.

This is functionally equivalent to creating an instance first and calling Self::root() method, but is faster and avoids heap allocation when root is the only thing that is needed.

pub fn root(&self) -> [u8; 32]

Get the root of Merkle Tree.

In case a tree contains a single leaf hash, that leaf hash is returned.

pub fn all_proofs( &self, ) -> impl ExactSizeIterator<Item = [[u8; 32]; { _ }]> + TrustedLen

where [(); { _ }]:,

Iterator over proofs in the same order as provided leaf hashes

pub fn verify( root: &[u8; 32], proof: &[[u8; 32]; { _ }], leaf_index: usize, leaf: [u8; 32], ) -> bool

where [(); { _ }]:,

Verify previously generated proof

Trait Implementations

impl<'a, const N: usize> Debug for BalancedHashedMerkleTree<'a, N>

where [(); { _ }]:,

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

Formats the value using the given formatter.