Module bmt

Stateless Binary Merkle Tree (BMT).

The Binary Merkle Tree is constructed level-by-level. The first level consists of position-hashed leaf digests. On each additional level, pairs of nodes are hashed from the previous level (if a level contains an odd number of nodes, the last node is duplicated). The root of the tree is the digest of the node in the top level.

For example, given three leaves A, B, and C, the tree is constructed as follows:

    Level 2 (root):       [hash(hash(hash(0,A),hash(1,B)),hash(hash(2,C),hash(2,C)))]
    Level 1:              [hash(hash(0,A),hash(1,B)),hash(hash(2,C),hash(2,C))]
    Level 0 (leaves):     [hash(0,A),hash(1,B),hash(2,C)]

A proof for a given leaf is generated by collecting the sibling at each level (from the leaf up to the root). An external process can then use this proof (with some trusted root) to verify that the leaf (at a fixed position) is part of the tree.

Example

use commonware_storage::bmt::{Builder, Tree};
use commonware_cryptography::{hash, Sha256, sha256::Digest};

// Create transactions and compute their digests
let txs = [b"tx1", b"tx2", b"tx3", b"tx4"];
let digests: Vec<Digest> = txs.iter().map(|tx| hash(*tx)).collect();

// Build a Merkle Tree from the digests
let mut builder = Builder::<Sha256>::new(digests.len());
for digest in &digests {
   builder.add(digest);
}
let tree = builder.build();
let root = tree.root();

// Generate a proof for leaf at index 1
let mut hasher = Sha256::default();
let proof = tree.proof(1).unwrap();
assert!(proof.verify(&mut hasher, &digests[1], 1, &root).is_ok());

Structs

Builder

Constructor for a Binary Merkle Tree (BMT).

Proof

A Merkle proof for a leaf in a Binary Merkle Tree.

Tree

Constructed Binary Merkle Tree (BMT).

Enums

Error

Errors that can occur when working with a Binary Merkle Tree (BMT).