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 finalized root of the tree incorporates the leaf count to prevent proof malleability: root = hash(leaf_count || tree_root).

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

    Level 2 (tree_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)]
    Finalized root:       hash(3 || tree_root)

A proof for one or more leaves is generated by collecting the siblings needed to reconstruct the root. An external process can then use this proof (with some trusted root) to verify that the leaves are part of the tree.

Example

use commonware_storage::bmt::{Builder, Tree};
use commonware_cryptography::{Sha256, sha256::Digest, Hasher as _};

// Create transactions and compute their digests
let txs = [b"tx1", b"tx2", b"tx3", b"tx4"];
let digests: Vec<Digest> = txs.iter().map(|tx| Sha256::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 proof = tree.proof(1).unwrap();
assert!(proof.verify_element_inclusion::<Sha256>(&digests[1], 1, &root).is_ok());

Structs

Builder

Constructor for a Binary Merkle Tree (BMT).

Proof

A Merkle proof for multiple non-contiguous leaves 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).

Constants

MAX_LEVELS

There should never be more than 32 sibling levels in a proof. Because Proof::leaf_count is a u32, a tree can have at most u32::MAX leaves, which requires at most u32::BITS sibling hashes per proven item.