Trait MerkleTreeScheme 

pub trait MerkleTreeScheme<T: FixedSizeSerializeBytes> {
    type Digest: Clone + PartialEq + Eq;

    // Required methods
    fn optimal_verify_layer(&self, n_queries: usize, tree_depth: usize) -> usize;
    fn proof_size(
        &self,
        len: usize,
        n_queries: usize,
        layer_depth: usize,
    ) -> usize;
    fn verify_vector(
        &self,
        root: &Self::Digest,
        data: &[T],
        batch_size: usize,
    ) -> Result<(), Error>;
    fn verify_layer(
        &self,
        root: &Self::Digest,
        layer_depth: usize,
        layer_digests: &[Self::Digest],
    ) -> Result<(), Error>;
    fn verify_opening<B: Buf>(
        &self,
        index: usize,
        values: &[T],
        layer_depth: usize,
        tree_depth: usize,
        layer_digests: &[Self::Digest],
        proof: &mut TranscriptReader<'_, B>,
    ) -> Result<(), Error>;
}

A Merkle tree scheme.

Required Associated Types

type Digest: Clone + PartialEq + Eq

The digest of a leaf or an inner node.

Required Methods

fn optimal_verify_layer(&self, n_queries: usize, tree_depth: usize) -> usize

Returns the optimal layer that the verifier should verify only once.

Decommitting a layer at depth d costs 2^d digests but shortens every one of the n_queries branches by d, so the proof holds

(tree_depth - d) * n_queries + 2^d

digests. That is minimized at d = ceil(log2(n_queries)), clamped to the tree depth.

fn proof_size(&self, len: usize, n_queries: usize, layer_depth: usize) -> usize

Returns the total byte-size of a proof for multiple opening queries.

Arguments

• len - the length of the committed vector
• n_queries - the number of opening queries
• layer_depth - the depth of the internal layer the verifier decommits once and verifies all openings against (see Self::optimal_verify_layer)

Preconditions

• len must be a power of two.
• layer_depth must be at most log2(len).

fn verify_vector( &self, root: &Self::Digest, data: &[T], batch_size: usize, ) -> Result<(), Error>

Verify the opening of the full vector.

The committed values are the whole opening, so there is no decommitment advice to read.

Preconditions

• batch_size must be non-zero.
• data.len() must be a multiple of batch_size.
• data.len() / batch_size must be a non-zero power of two.

fn verify_layer( &self, root: &Self::Digest, layer_depth: usize, layer_digests: &[Self::Digest], ) -> Result<(), Error>

Verify a given layer of the Merkle tree.

When a protocol requires verification of many openings at independent and randomly sampled indices, it is more efficient for the verifier to verifier an internal layer once, then verify all openings with respect to that layer.

Preconditions

• layer_digests.len() must equal 2^layer_depth.

fn verify_opening<B: Buf>( &self, index: usize, values: &[T], layer_depth: usize, tree_depth: usize, layer_digests: &[Self::Digest], proof: &mut TranscriptReader<'_, B>, ) -> Result<(), Error>

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

Preconditions

• layer_digests.len() must equal 2^layer_depth.
• layer_depth must be at most tree_depth.
• index must be less than 2^tree_depth.

Dyn Compatibility

This trait is not dyn compatible.

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

Implementors

impl<T, H> MerkleTreeScheme<T> for BinaryMerkleTreeScheme<T, H>

where T: FixedSizeSerializeBytes, H: HashSuite,

type Digest = Array<u8, <<H as HashSuite>::LeafHash as OutputSizeUser>::OutputSize>