Binary Merkle tree

use merkle_core::prelude::*;
use merkle_variants::BinaryMerkleTree;
use merkleforge_hash::Sha256;
 
fn main() -> Result<(), MerkleError> {
    // Empty tree, grows as you insert.
    let mut tree = BinaryMerkleTree::<Sha256>::new();
    assert!(tree.is_empty());
    assert_eq!(tree.root(), None);
 
    // Pre-size the leaf layer for at least 1,000 leaves (rounded up to 1,024).
    // Reserving storage adds no logical leaves.
    let reserved = BinaryMerkleTree::<Sha256>::with_capacity(1_000);
    assert_eq!(reserved.leaf_count(), 0);
 
    // Build from a known leaf set in one O(n) pass.
    let batch = BinaryMerkleTree::<Sha256>::from_leaves([b"tx1".as_slice(), b"tx2", b"tx3"])?;
    assert_eq!(batch.leaf_count(), 3);
 
    tree.insert(b"tx1")?;
    tree.insert(b"tx2")?;
    tree.insert(b"tx3")?;
    assert_eq!(tree.root(), batch.root());
    Ok(())
}

use merkle_core::prelude::*;
use merkle_variants::BinaryMerkleTree;
use merkleforge_hash::Sha256;
 
fn main() -> Result<(), MerkleError> {
    let mut tree = BinaryMerkleTree::<Sha256>::new();
 
    // insert returns the stable index of the new leaf.
    let alice = tree.insert(b"alice:100")?;
    let bob = tree.insert(b"bob:250")?;
    let carol = tree.insert(b"carol:75")?;
    assert_eq!((alice, bob, carol), (LeafIndex(0), LeafIndex(1), LeafIndex(2)));
    assert_eq!(tree.height(), 3); // 3 leaves pad to 4 slots: 4 -> 2 -> 1
 
    // Removing an interior leaf replaces it with H::empty(); later indices stay put.
    tree.remove(bob)?;
    assert_eq!(tree.leaf_count(), 3);
 
    // Removing the last leaf shrinks the logical leaf count.
    tree.remove(carol)?;
    assert_eq!(tree.leaf_count(), 1);
 
    // Empty data is rejected so it can't be confused with padding.
    assert_eq!(tree.insert(b""), Err(MerkleError::EmptyLeafData));
    Ok(())
}

use merkle_core::prelude::*;
use merkle_variants::BinaryMerkleTree;
use merkleforge_hash::Sha256;
 
fn main() -> Result<(), MerkleError> {
    let txs = ["tx:alice->bob:100", "tx:bob->carol:50", "tx:carol->dave:25"];
    let tree = BinaryMerkleTree::<Sha256>::from_leaves(txs)?;
    let root = tree.root().expect("non-empty");
 
    for (i, tx) in txs.iter().enumerate() {
        let proof = tree.generate_proof(LeafIndex(i))?;
        assert_eq!(proof.leaf_index, LeafIndex(i));
        assert_eq!(proof.depth(), 2);
        assert!(BinaryMerkleTree::<Sha256>::verify(root, tx.as_bytes(), &proof));
    }
 
    // Out-of-range indices are an error, not a panic.
    assert_eq!(
        tree.generate_proof(LeafIndex(9)).unwrap_err(),
        MerkleError::IndexOutOfBounds { index: 9, len: 3 },
    );
    Ok(())
}

use merkle_core::prelude::*;
use merkle_variants::BinaryMerkleTree;
use merkleforge_hash::Blake3;
 
fn verify_with<V: ProofVerifier<Blake3>>(
    root: &[u8; 32],
    leaf: &[u8],
    proof: &MerkleProof<[u8; 32]>,
) -> bool {
    V::verify(root, leaf, proof)
}
 
fn main() -> Result<(), MerkleError> {
    let mut tree = BinaryMerkleTree::<Blake3>::new();
    MerkleTree::insert(&mut tree, b"leaf")?;
    let proof = MerkleTree::generate_proof(&tree, LeafIndex(0))?;
    let root = *MerkleTree::root(&tree).expect("non-empty");
 
    assert!(verify_with::<BinaryMerkleTree<Blake3>>(&root, b"leaf", &proof));
    Ok(())
}