Trait MerkleTreeScheme

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

    // 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,
    ) -> Result<usize, Error>;
    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(
        &self,
        index: usize,
        values: &[T],
        layer_depth: usize,
        tree_depth: usize,
        layer_digests: &[Self::Digest],
        proof: Self::Proof,
    ) -> Result<(), Error>;
}

A Merkle tree scheme.

Required Associated Types

type Digest: Clone + PartialEq + Eq

type Proof

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.

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

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

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

Verify the opening of the full vector.

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.

fn verify_opening( &self, index: usize, values: &[T], layer_depth: usize, tree_depth: usize, layer_digests: &[Self::Digest], proof: Self::Proof, ) -> Result<(), Error>

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

Implementors

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

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

type Digest = D

type Proof = Vec<D>