Struct BinaryMerkleTree 

pub struct BinaryMerkleTree<D: Send, A: Allocator = GlobalAllocator> {
    pub log_len: usize,
    pub inner_nodes: A::Vec<D>,
}

A binary Merkle tree that commits batches of vectors.

Overview

The entries sharing an index across a batch are hashed together into one leaf digest. A binary tree is then folded over those leaf digests.

All committed vectors must have the same length, and that length must be a power of two.

The nodes are drawn from an Allocator, so a prover can back the whole tree with pooled memory instead of the global heap. The default is GlobalAllocator, which is a plain Vec.

Fields

log_len: usize

Base-2 logarithm of the number of leaves.

inner_nodes: A::Vec<D>

The inner nodes, arranged as a flattened array of layers with the root at the end.

Implementations

impl<N: ArraySize, A: Allocator> BinaryMerkleTree<Array<u8, N>, A>

pub fn new<F, H>( elements: &[F], batch_size: usize, alloc: &A, ) -> Result<Self, Error>

where F: Field, H: ParallelHashSuite<LeafHash: OutputSizeUser<OutputSize = N>>,

Commits a slice of values, cutting it into consecutive leaves.

Arguments

• elements - the values to commit, in leaf order.
• batch_size - how many consecutive values are hashed together into one leaf.
• alloc - the allocator the tree’s nodes are drawn from.

Errors

• The value count is not a multiple of the batch size.
• The resulting leaf count is not a power of two.

pub fn from_leaves<F, H, ParIter>( leaves: ParIter, n_items_per_input: usize, alloc: &A, ) -> Self

where F: Field, H: ParallelHashSuite<LeafHash: OutputSizeUser<OutputSize = N>>, ParIter: IndexedParallelIterator<Item: IntoIterator<Item = F, IntoIter: Send>>,

Commits leaves drawn from a parallel iterator, one iterator item per leaf.

Overview

The tree is laid out as one flat buffer of layers, widest first:

    [ leaf digests | layer 1 | ... | root ]
       2^log_len      2^(log_len-1)    1

Each layer is written into the buffer’s spare capacity. It is then read back as the input to the layer above it.

Arguments

• leaves - one iterator per leaf, each yielding that leaf’s values.
• n_items_per_input - how many values every leaf iterator yields.
• alloc - the allocator the tree’s nodes are drawn from.

Panics

Panics unless the number of leaves is a power of two.

impl<D: Clone + Send, A: Allocator> BinaryMerkleTree<D, A>

pub fn root(&self) -> D

Clones the root digest, which sits last in the flattened layers.

pub fn layer(&self, layer_depth: usize) -> Result<&[D], Error>

Borrows one whole layer of the tree, counting depth from the root.

Errors

• The depth lies below the leaves.

pub fn branch(&self, index: usize, layer_depth: usize) -> Result<Vec<D>, Error>

Collects the sibling digests opening a leaf up to the layer at layer_depth.

Errors

• The leaf index lies outside the tree.
• The depth lies below the leaves.

Trait Implementations

impl<D: Debug + Send, A: Allocator> Debug for BinaryMerkleTree<D, A>

Written through the node slice rather than the buffer, so no allocator has to be Debug itself for a tree over it to be.

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

Formats the value using the given formatter.