Struct MerkleTree

pub struct MerkleTree<D> {
    pub log_len: usize,
    pub batch_size: usize,
    pub inner_nodes: Vec<D>,
    pub cap_height: usize,
}

A binary Merkle tree that commits batches of vectors.

The vector entries at each index in a batch are hashed together into leaf digests. Then a Merkle tree is constructed over the leaf digests. The implementation requires that the vector lengths are all equal to each other and a power of two.

Fields

log_len: usize

Base-2 logarithm of the number of leaves

batch_size: usize

Number of vectors that are committed in this batch

inner_nodes: Vec<D>

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

cap_height: usize

cap_height-th layer of the tree

Implementations

impl<D> MerkleTree<D>

where D: Copy + Default + Send + Sync,

pub fn build_strided<T, H, C>( compression: &C, log_len: usize, leaves: &[impl AsRef<[T]>], cap_height: usize, ) -> Result<Self, Error>

where T: Sync, H: Hasher<T, Digest = D> + Send, C: PseudoCompressionFunction<D, 2> + Sync,

pub fn build_interleaved<T, H, C>( compression: &C, log_len: usize, elements: &[T], cap_height: usize, ) -> Result<Self, Error>

where T: Sync, H: Hasher<T, Digest = D> + Send, C: PseudoCompressionFunction<D, 2> + Sync,

pub fn build_iterated<T, H, C, ParIter>( compression: &C, log_len: usize, iterated_chunks: ParIter, cap_height: usize, batch_size: usize, ) -> Result<Self, Error>

where H: Hasher<T, Digest = D> + Send, C: PseudoCompressionFunction<D, 2> + Sync, ParIter: IndexedParallelIterator<Item: IntoIterator<Item = T>>,

pub fn get_cap(&self) -> &[D]

Get the cap_height-th layer of the tree

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

Get a Merkle branch for the given index

Throws if the index is out of range

pub fn truncated_branch(&self, indices: Range<usize>) -> Result<Vec<D>, Error>

Get a truncated Merkle branch for the given range corresponding to the subtree

Throws if the index is out of range

Trait Implementations

impl<D: Clone> Clone for MerkleTree<D>

fn clone(&self) -> MerkleTree<D>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<D: Debug> Debug for MerkleTree<D>

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

Formats the value using the given formatter.