Merkle Tree

This is an implementation in Rust of Merkle Trees.

Basic example

You can test this library using the example merkletree_blake3.rs in the examples/ folder.

cargo run --example merkletree_blake3 -- tests/pics/cubbit.png.enc.0 tests/pics/cubbit.png.enc.1 tests/pics/cubbit.png.enc.2

And then check the proof with the proofer_blake3.rs example.

cargo run --example proofer_blake3 -- f03bad5df0a10c74de32ec9c7119b65db9c4dee145fa390c7f36af94411d04cb tests/pics/cubbit.png.enc.0 tests/pics/cubbit.png.enc.1 tests/pics/cubbit.png.enc.2

These two should be seen as a single Rust example code which check if the passed hash is the same generated by the Merkle tree algorithm.

use mt_rs::{
    hasher::Blake3Hasher,
    merkletree::MerkleTree,
    proof::{DefaultProofer, Proofer},
};

fn main() {
    let root_hash = match std::env::args().nth(1) {
        Some(hash) => hash,
        None => {
            std::process::exit(1);
        }
    };

    let filenames: Vec<String> = std::env::args().skip(2).collect();
    if filenames.is_empty() {
        std::process::exit(1);
    }

    let mut file_contents = Vec::new();
    for filename in &filenames {
        match std::fs::read(filename) {
            Ok(contents) => file_contents.push(contents),
            Err(e) => {
                eprintln!("Failed to read file '{}': {}", filename, e);
                std::process::exit(1);
            }
        }
    }

    let hasher = Blake3Hasher::new();
    let tree = MerkleTree::new(hasher.clone(), file_contents.clone());
    let proofer = DefaultProofer::new(hasher, tree.leaves());
    let proof = proofer.generate(0).expect("Couldn't generate proof");

    assert!(tree.root().hash() == root_hash);
    assert!(proofer.verify(&proof, std::fs::read(&filenames[0]).unwrap(), tree.root().hash()));
}

Advanced example

1. Define an hasher.

use mt_rs::hasher::Hasher;

pub struct FooHasher;

impl Hasher for FooHasher {
    fn hash(&self, input: &[u8]) -> String {
        let sum: u32 = input.iter().map(|&b| b as u32).sum();
        format!("foo_{:x}", sum)
    }
}

2. Define a proofer.

use mt_rs::proof::Proofer;

pub struct FooProofer;

impl<H> Proofer for FooProfer<H>
where
    H: Hasher,
{
    fn generate(&self, index: usize) -> Option<MerkleProof> {
        // ...
    }

    fn verify<T>(&self, proof: &MerkleProof, data: T, root_hash: &str) -> bool
    where
        T: AsRef<[u8]>,
    {
        // ...
    }
}

3. Now we can proceed with the tree creation.

let hasher = FooHasher;
let data: &[&[u8]; ...] = ...;
let tree = MerkleTree::new(hasher.clone(), data);

println!("{}", tree.root().hash());


let proofer = FooProofer::new(hasher, tree.leaves().clone());

let proof = proofer.generate(0).unwrap();
assert!(proofer.verify(&proof, data[0], tree.root().hash()));

Configuration

Currently we have tree hashers:

• SHA256HAsher
• Keccak256Hasher
• Blake3Hasher

And a proofer DefaultProofer.

Benchmark

You can run a benchmark to test which hasher is faster via

$ cargo bench --bench bigfile