# Merkle Tree

This is an implementation in Rust of [Merkle
Trees](https://search.proquest.com/openview/1ae50982b34bee7e3f1b8e232bb98e42/1?pq-origsite=gscholar&cbl=18750&diss=y).

## 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.

```rust
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, tree.leaves()[0].data(), tree.root().hash(), &hasher));
}
```

## Advanced example

1. Define an hasher.

```rust
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.

```rust
use mt_rs::proof::Proofer;

pub struct FooProofer;

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

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

3. Now we can proceed with the tree creation.

```rust
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(), &hasher));
```

## 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
```