Struct UnbalancedMerkleTree 

pub struct UnbalancedMerkleTree<H>(/* private fields */);

Merkle Tree variant that has pre-hashed leaves with arbitrary number of elements.

This can be considered a general case of BalancedMerkleTree. The root and proofs are identical for both in case the number of leaves is a power of two. BalancedMerkleTree is more efficient and should be preferred when possible.

The unbalanced tree is not padded, it is created the same way Merkle Mountain Range would be:

              Root
        /--------------\
       H3              H4
   /-------\         /----\
  H0       H1       H2     \
 /  \     /  \     /  \     \
L0  L1   L2  L3   L4  L5    L6

Inner nodes are hashed with H, which is created from the number of leaves. That is why methods that take an iterator of leaves require a TrustedLen iterator. Variants with dynamic_len in their name accept any iterator instead, but only support hashers that implement Default.

Implementations

impl<H> UnbalancedMerkleTree<H>

where H: MerkleHasher,

pub fn compute_root_only<'a, const MAX_N: u64, Item, Iter>( leaves: Iter, ) -> Option<[u8; <H as MerkleHasher>::OUT_LEN]>

where H: NewMerkleHasherForTreeSize, Item: Into<[u8; <H as MerkleHasher>::OUT_LEN]>, Iter: IntoIterator<Item = Item, IntoIter: TrustedLen> + 'a,

Compute Merkle Tree Root.

MAX_N generic constant defines the maximum number of elements supported and controls stack usage.

Returns None for an empty list of leaves, or if the number of leaves is larger than MAX_N.

pub fn compute_root_only_dynamic_len<'a, const MAX_N: u64, Item, Iter>( leaves: Iter, ) -> Option<[u8; <H as MerkleHasher>::OUT_LEN]>

where H: Default, Item: Into<[u8; <H as MerkleHasher>::OUT_LEN]>, Iter: IntoIterator<Item = Item> + 'a,

Similar to Self::compute_root_only(), but for iterators that are not TrustedLen

pub fn compute_root_only_sparse<const MAX_N: u64, Item, Iter>( num_leaves: u64, leaves: Iter, ) -> Option<[u8; <H as MerkleHasher>::OUT_LEN]>

where H: NewMerkleHasherForTreeSize, Item: Into<[u8; <H as MerkleHasher>::OUT_LEN]>, Iter: IntoIterator<Item = (u64, Item)>,

Compute Merkle Tree Root of num_leaves leaves, which are all zeroes except leaves.

leaves are pairs of leaf index and leaf, with strictly increasing indices. Produces the same root as Self::compute_root_only() with zeroes in all other positions, but hashes runs of zero leaves as whole subtrees, so the number of hashes is proportional to the number of leaves and the height of the tree rather than to num_leaves.

MAX_N generic constant defines the maximum number of elements supported and controls stack usage.

Returns None if num_leaves is zero or larger than MAX_N, or if indices aren’t strictly increasing or not smaller than num_leaves.

pub fn compute_root_only_array<const N: usize, Item>( leaves: &[Item; N], ) -> [u8; <H as MerkleHasher>::OUT_LEN]

where H: NewMerkleHasherForTreeSize, [(); _]:, Item: Into<[u8; <H as MerkleHasher>::OUT_LEN]> + Copy,

Compute Merkle Tree Root for an array of leaves.

Similar to Self::compute_root_only(), but for inputs that are small arrays where MAX_N is the same as the array length.

pub fn compute_root_and_proof<'a, const MAX_N: u64, Item, Iter>( leaves: Iter, target_index: usize, ) -> Option<([u8; <H as MerkleHasher>::OUT_LEN], Vec<[u8; <H as MerkleHasher>::OUT_LEN]>)>

where H: NewMerkleHasherForTreeSize, Item: Into<[u8; <H as MerkleHasher>::OUT_LEN]>, Iter: IntoIterator<Item = Item, IntoIter: TrustedLen> + 'a,

Compute Merkle Tree root and generate a proof for the leaf at target_index.

Returns Some((root, proof)) on success, None if index is outside of list of leaves.

MAX_N generic constant defines the maximum number of elements supported and controls stack usage.

pub fn compute_root_and_proof_dynamic_len<'a, const MAX_N: u64, Item, Iter>( leaves: Iter, target_index: usize, ) -> Option<([u8; <H as MerkleHasher>::OUT_LEN], Vec<[u8; <H as MerkleHasher>::OUT_LEN]>)>

where H: Default, Item: Into<[u8; <H as MerkleHasher>::OUT_LEN]>, Iter: IntoIterator<Item = Item> + 'a,

Similar to Self::compute_root_and_proof(), but for iterators that are not TrustedLen

pub fn compute_root_and_proof_in<'a, 'proof, const MAX_N: u64, Item, Iter>( leaves: Iter, target_index: usize, proof: &'proof mut [MaybeUninit<[u8; <H as MerkleHasher>::OUT_LEN]>; _], ) -> Option<([u8; <H as MerkleHasher>::OUT_LEN], &'proof mut [[u8; <H as MerkleHasher>::OUT_LEN]])>

where H: NewMerkleHasherForTreeSize, Item: Into<[u8; <H as MerkleHasher>::OUT_LEN]>, Iter: IntoIterator<Item = Item, IntoIter: TrustedLen> + 'a,

Compute Merkle Tree root and generate a proof for the leaf at target_index.

Returns Some((root, proof)) on success, None if index is outside of list of leaves.

MAX_N generic constant defines the maximum number of elements supported and controls stack usage.

pub fn compute_root_and_proof_dynamic_len_in<'a, 'proof, const MAX_N: u64, Item, Iter>( leaves: Iter, target_index: usize, proof: &'proof mut [MaybeUninit<[u8; <H as MerkleHasher>::OUT_LEN]>; _], ) -> Option<([u8; <H as MerkleHasher>::OUT_LEN], &'proof mut [[u8; <H as MerkleHasher>::OUT_LEN]])>

where H: Default, Item: Into<[u8; <H as MerkleHasher>::OUT_LEN]>, Iter: IntoIterator<Item = Item> + 'a,

Similar to Self::compute_root_and_proof_in(), but for iterators that are not TrustedLen

pub fn verify( root: &[u8; <H as MerkleHasher>::OUT_LEN], proof: &[[u8; <H as MerkleHasher>::OUT_LEN]], leaf_index: u64, leaf: [u8; <H as MerkleHasher>::OUT_LEN], num_leaves: u64, ) -> bool

where H: NewMerkleHasherForTreeSize,

Verify a Merkle proof for a leaf at the given index

Trait Implementations

impl<H: Debug> Debug for UnbalancedMerkleTree<H>

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

Formats the value using the given formatter.