#merkle-tree #tree #merkle

alloy-merkle-tree

Minimal Merkle Tree implementation

9 releases (breaking)

0.7.1 Oct 16, 2024
0.7.0 Sep 16, 2024
0.6.0 Jun 25, 2024
0.5.0 Feb 28, 2024
0.1.1 Feb 19, 2024

#50 in #merkle

Download history 67/week @ 2024-07-29 17/week @ 2024-08-05 23/week @ 2024-08-12 12/week @ 2024-08-19 24/week @ 2024-08-26 33/week @ 2024-09-02 40/week @ 2024-09-09 210/week @ 2024-09-16 36/week @ 2024-09-23 14/week @ 2024-09-30 176/week @ 2024-10-14 10/week @ 2024-10-21 13/week @ 2024-10-28 30/week @ 2024-11-04 24/week @ 2024-11-11

88 downloads per month
Used in 5 crates (4 directly)

Custom license

33KB
540 lines

alloy-merkle-tree

CI Crates.io Documentation

Minimal Merkle Tree implementation

  • various tree implementation
    • PerfectBinaryMerkleTree
    • IncrementalMerkleTree
    • StandardBinaryTree
  • type compatible with alloy-primitives
  • keccak hash as native hash
  • support features: insert, proof, verify

Install

 cargo add alloy-merkle-tree

Support

MerkleTree

Perfect Binary Merkle Tree

let mut tree = MerkleTree::new();
// Should be 2 ^ N leaves
let num_leaves = 16;
for i in 0..num_leaves {
    tree.insert(B256::from(U256::from(i)));
}
tree.finish();

for i in 0..num_leaves {
    let proof = tree.create_proof(&B256::from(U256::from(i))).unwrap();
    assert!(MerkleTree::verify_proof(&proof));
}

IncrementalMerkleTree

used in the ETH2 Deposit Contract

 let mut tree = IncrementalMerkleTree::<8>::new();
for i in 0..1 << (8 - 1) {
    tree.append([i as u8; 32].into()).unwrap();
}
for i in 0..1 << (8 - 1) {
    let leaf = [i as u8; 32].into();
    let proof = tree.proof_at_index(i).unwrap();
    assert!(tree.verify_proof(leaf, i, &proof));
}

StandardBinaryMerkleTree

StandardMerkleTree

let num_leaves = 1000;
let mut leaves = Vec::new();
for i in 0..num_leaves {
    leaves.push(i.to_string());
}
let tree = StandardMerkleTree::of(leaves.clone());

for leaf in leaves.iter() {
    let proof = tree.get_proof(leaf);
    let bool = tree.verify_proof(leaf.to_string(), proof);
    assert!(bool);
}

reference

Dependencies

~9.5MB
~171K SLoC