Skip to main content

MerkleTreeProver

Trait MerkleTreeProver 

pub trait MerkleTreeProver<T>{
    type Scheme: MerkleTreeScheme<T>;
    type Committed;

    // Required methods
    fn scheme(&self) -> &Self::Scheme;
    fn commit_iterated<ParIter>(
        &self,
        leaves: ParIter,
        n_items_per_input: usize,
    ) -> (Commitment<<Self::Scheme as MerkleTreeScheme<T>>::Digest>, Self::Committed)
       where ParIter: IndexedParallelIterator,
             <ParIter as ParallelIterator>::Item: IntoIterator<Item = T>,
             <<ParIter as ParallelIterator>::Item as IntoIterator>::IntoIter: Send;
    fn layer<'a>(
        &self,
        committed: &'a Self::Committed,
        layer_depth: usize,
    ) -> &'a [<Self::Scheme as MerkleTreeScheme<T>>::Digest];
    fn prove_opening<B>(
        &self,
        committed: &Self::Committed,
        layer_depth: usize,
        index: usize,
        proof: &mut TranscriptWriter<'_, B>,
    )
       where B: BufMut;

    // Provided methods
    fn commit(
        &self,
        data: &[T],
        batch_size: usize,
    ) -> (Commitment<<Self::Scheme as MerkleTreeScheme<T>>::Digest>, Self::Committed)
       where T: Clone + Sync { ... }
    fn commit_field_buffer<P>(
        &self,
        buffer: FieldBuffer<P, FieldSliceData<'_, P>>,
        log_leaf_len: usize,
    ) -> (Commitment<<Self::Scheme as MerkleTreeScheme<T>>::Digest>, Self::Committed)
       where P: PackedField<Scalar = T> { ... }
}
Expand description

A Merkle tree prover for a particular scheme.

This is separate from MerkleTreeScheme so that it may be implemented using a hardware-accelerated backend.

Required Associated Types§

type Scheme: MerkleTreeScheme<T>

type Committed

Data generated during commitment required to generate opening proofs.

Required Methods§

fn scheme(&self) -> &Self::Scheme

Returns the Merkle tree scheme used by the prover.

fn commit_iterated<ParIter>( &self, leaves: ParIter, n_items_per_input: usize, ) -> (Commitment<<Self::Scheme as MerkleTreeScheme<T>>::Digest>, Self::Committed)
where ParIter: IndexedParallelIterator, <ParIter as ParallelIterator>::Item: IntoIterator<Item = T>, <<ParIter as ParallelIterator>::Item as IntoIterator>::IntoIter: Send,

Commit interleaved elements from iterator by val

Each leaf is built from exactly n_items_per_input elements, which lets the leaf hasher specialize for short, constant-length leaves.

§Preconditions
  • The number of leaves must be a power of two.
  • Each iterator in leaves yields exactly n_items_per_input elements.

fn layer<'a>( &self, committed: &'a Self::Committed, layer_depth: usize, ) -> &'a [<Self::Scheme as MerkleTreeScheme<T>>::Digest]

Returns the internal digest layer at the given depth.

§Preconditions
  • layer_depth must be at most the committed tree’s depth.

fn prove_opening<B>( &self, committed: &Self::Committed, layer_depth: usize, index: usize, proof: &mut TranscriptWriter<'_, B>, )
where B: BufMut,

Generate an opening proof for an entry in a committed vector at the given index.

§Arguments
  • committed - helper data generated during commitment
  • layer_depth - depth of the layer to prove inclusion in
  • index - the entry index
§Preconditions
  • index must be within the committed tree and layer_depth at most its depth.

Provided Methods§

fn commit( &self, data: &[T], batch_size: usize, ) -> (Commitment<<Self::Scheme as MerkleTreeScheme<T>>::Digest>, Self::Committed)
where T: Clone + Sync,

Commit a vector of values.

§Preconditions
  • data.len() must be a multiple of batch_size, and the resulting leaf count (data.len() / batch_size) must be a power of two.

fn commit_field_buffer<P>( &self, buffer: FieldBuffer<P, FieldSliceData<'_, P>>, log_leaf_len: usize, ) -> (Commitment<<Self::Scheme as MerkleTreeScheme<T>>::Digest>, Self::Committed)
where P: PackedField<Scalar = T>,

Commits a field buffer, packing 2^log_leaf_len scalars into each leaf.

Scalars fill leaves in order:

leaf i  <-  buffer[i * 2^log_leaf_len .. (i+1) * 2^log_leaf_len]

The leaf count is 2^(log_len - log_leaf_len), hence a power of two by construction. That is what commit_iterated requires of it.

§Preconditions
  • log_leaf_len must be at most the buffer’s log length.

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors§

§

impl<F, H, A> MerkleTreeProver<F> for BinaryMerkleTreeProver<F, H, A>

§

type Scheme = BinaryMerkleTreeScheme<F, H>

§

type Committed = BinaryMerkleTree<Array<u8, <<H as HashSuite>::LeafHash as OutputSizeUser>::OutputSize>, A>