Struct MerkleTree 

pub struct MerkleTree<H: Hasher> { /* private fields */ }

A fully-balanced Merkle tree.

In this implementation, a Merkle tree consists of two types of nodes: leaves and internal nodes (one of which is a tree root). All nodes must be instances of the digest specified by the Hasher used to build the tree.

      *        <- tree root
    /   \
   /     \
  *       *    <- internal nodes
 / \     / \
o   o   o   o  <- leaves
|   |   |   |
#   #   #   #  <- values

A tree can be built from a slice of leaves using MerkleTree::new() function. Thus, the user is responsible for performing the first level of hashing (i.e., hashing values into leaf nodes). The number of leaves must always be a power of two so that the tree is fully balanced, and a tree must contain at least two leaves.

The depth of a tree is zero-based. Thus, a tree with two leaves has depth 1, a tree with four leaves has depth 2 etc.

When the crate is compiled with concurrent feature enabled, tree construction will be performed in multiple threads (usually, as many threads as there are logical cores on the machine). The number of threads can be configured via RAYON_NUM_THREADS environment variable.

To generate an inclusion proof for a given leaf, MerkleTree::prove() method can be used. You can also use MerkleTree::prove_batch() method to generate inclusion proofs for multiple leaves. The advantage of the batch method is that redundant internal nodes are removed from the batch proof, thereby compressing it (we use a variation of the Octopus algorithm).

To verify proofs, MerkleTree::verify() and MerkleTree::verify_batch() functions can be used respectively.

Examples

type Blake3 = Blake3_256<BaseElement>;

// build a tree
let leaves = [
    Blake3::hash(&[1u8]),
    Blake3::hash(&[2u8]),
    Blake3::hash(&[3u8]),
    Blake3::hash(&[4u8]),
];
let tree = MerkleTree::<Blake3>::new(leaves.to_vec()).unwrap();
assert_eq!(2, tree.depth());
assert_eq!(leaves, tree.leaves());

// generate a proof
let (leaf, proof) = tree.prove(2).unwrap();
assert_eq!(2, proof.len());
assert_eq!(leaves[2], leaf);

// verify proof
assert!(MerkleTree::<Blake3>::verify(*tree.root(), 2, leaf, &proof).is_ok());
assert!(MerkleTree::<Blake3>::verify(*tree.root(), 1, leaf, &proof).is_err());

Implementations

impl<H: Hasher> MerkleTree<H>

pub fn new(leaves: Vec<H::Digest>) -> Result<Self, MerkleTreeError>

Returns new Merkle tree built from the provide leaves using hash function specified by the H generic parameter.

When concurrent feature is enabled, the tree is built using multiple threads.

Errors

Returns an error if:

• Fewer than two leaves were provided.
• Number of leaves is not a power of two.

pub fn from_raw_parts( nodes: Vec<H::Digest>, leaves: Vec<H::Digest>, ) -> Result<Self, MerkleTreeError>

Forms a MerkleTree from a list of nodes and leaves.

Nodes are supplied as a vector where the root is stored at position 1.

Errors

Returns an error if:

• Fewer than two leaves were provided.
• Number of leaves is not a power of two.

Panics

Panics if nodes doesn’t have the same length as leaves.

pub fn root(&self) -> &H::Digest

Returns the root of the tree.

pub fn depth(&self) -> usize

Returns depth of the tree.

The depth of a tree is zero-based. Thus, a tree with two leaves has depth 1, a tree with four leaves has depth 2 etc.

pub fn leaves(&self) -> &[H::Digest]

Returns leaf nodes of the tree.

pub fn prove( &self, index: usize, ) -> Result<(<H as Hasher>::Digest, Vec<<H as Hasher>::Digest>), MerkleTreeError>

Returns a Merkle proof to a leaf at the specified index.

The leaf itself will be the first element of the returned tuple.

Errors

Returns an error if the specified index is greater than or equal to the number of leaves in the tree.

pub fn prove_batch( &self, indexes: &[usize], ) -> Result<(Vec<H::Digest>, BatchMerkleProof<H>), MerkleTreeError>

Computes Merkle proofs for the provided indexes, compresses the proofs into a single batch and returns the batch proof alongside the leaves at the provided indexes.

Errors

Returns an error if:

• No indexes were provided (i.e., indexes is an empty slice).
• Any of the provided indexes are greater than or equal to the number of leaves in the tree.
• List of indexes contains duplicates.

pub fn verify( root: H::Digest, index: usize, leaf: H::Digest, proof: &[H::Digest], ) -> Result<(), MerkleTreeError>

Checks whether the proof for the given leaf at the specified index is valid.

Errors

Returns an error if the specified proof (which is a Merkle path) does not resolve to the specified root.

pub fn verify_batch( root: &H::Digest, indexes: &[usize], leaves: &[H::Digest], proof: &BatchMerkleProof<H>, ) -> Result<(), MerkleTreeError>

Checks whether the batch proof contains Merkle proofs resolving to root for the provided leaves at the specified indexes.

Errors

Returns an error if:

• No indexes were provided (i.e., indexes is an empty slice).
• Any of the specified indexes is greater than or equal to the number of leaves in the tree from which the batch proof was generated.
• List of indexes contains duplicates.
• Any of the proofs in the batch proof does not resolve to the specified root.

Trait Implementations

impl<H: Debug + Hasher> Debug for MerkleTree<H>

where H::Digest: Debug,

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

Formats the value using the given formatter.

impl<H: Hasher> VectorCommitment<H> for MerkleTree<H>

type Options = ()

Options defining the VC i.e., public parameters.

type Proof = Vec<<H as Hasher>::Digest>

Opening proof of some value at some position index.

type MultiProof = BatchMerkleProof<H>

Batch opening proof of a number of {(i, v_i)}_{i ∈ S} for an index set.

type Error = MerkleTreeError

Error returned by the scheme.

fn with_options( items: Vec<H::Digest>, _options: Self::Options, ) -> Result<Self, Self::Error>

Creates a commitment to a vector of values (v_0, …, v_{n-1}) given a set of options.

fn commitment(&self) -> H::Digest

Returns the commitment string to the committed values.

fn domain_len(&self) -> usize

Returns the length of the vector committed to for Self.

fn get_proof_domain_len(proof: &Self::Proof) -> usize

Returns the length of the vector committed to for Self::Proof.

fn get_multiproof_domain_len(proof: &Self::MultiProof) -> usize

Returns the length of the vector committed to for Self::MultiProof.

fn open(&self, index: usize) -> Result<(H::Digest, Self::Proof), Self::Error>

Opens the value at a given index and provides a proof for the correctness of claimed value.

fn open_many( &self, indexes: &[usize], ) -> Result<(Vec<H::Digest>, Self::MultiProof), Self::Error>

Opens the values at a given index set and provides a proof for the correctness of claimed values.

fn verify( commitment: H::Digest, index: usize, item: H::Digest, proof: &Self::Proof, ) -> Result<(), Self::Error>

Verifies that the claimed value is at the given index using a proof.

fn verify_many( commitment: H::Digest, indexes: &[usize], items: &[H::Digest], proof: &Self::MultiProof, ) -> Result<(), Self::Error>

Verifies that the claimed values are at the given set of indices using a batch proof.

fn new(items: Vec<H::Digest>) -> Result<Self, Self::Error>

Creates a commitment to a vector of values (v_0, …, v_{n-1}) using the default options.