Struct winter_crypto::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
|   |   |   |

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 proof = tree.prove(2).unwrap();
assert_eq!(3, proof.len());
assert_eq!(leaves[2], proof[0]);

// verify proof
assert!(MerkleTree::<Blake3>::verify(*tree.root(), 2, &proof).is_ok());
assert!(MerkleTree::<Blake3>::verify(*tree.root(), 1, &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 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<Vec<H::Digest>, MerkleTreeError>

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

The leaf itself will be the first element in the path.

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<BatchMerkleProof<H>, MerkleTreeError>

Computes Merkle paths for the provided indexes and compresses the paths into a single proof.

Errors

Returns an error if:

• No indexes were provided (i.e., indexes is an empty slice).
• Number of provided indexes is greater than 255.
• 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,
    proof: &[H::Digest]
) -> Result<(), MerkleTreeError>

Checks whether the proof for 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],
    proof: &BatchMerkleProof<H>
) -> Result<(), MerkleTreeError>

Checks whether the batch proof contains Merkle paths for the of the specified indexes.

Errors

Returns an error if:

• No indexes were provided (i.e., indexes is an empty slice).
• Number of provided indexes is greater than 255.
• 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 paths 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,
    H::Digest: Debug, 

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

Formats the value using the given formatter.