Module mohan::merkle

MMR Tree Merkle Tree implementation.

Merkle tree (MT) implemented as a full binary tree allocated as a vec of statically sized hashes to give hashes more locality. MT specialized to the extent of hashing algorithm and hash item. [Hashable] trait is compatible to the std::hash::Hasher and supports custom hash algorithms. Implementation does not depend on any external crypto libraries, and tries to be as performant as possible.

This tree implementation uses encoding scheme as in Certificate Transparency by default. Encoding scheme for leafs and nodes can be overridden though. RFC 6962:

MTH({d(0)}) = ALG(0x00 || d(0)).
For n > 1, let k be the largest power of two smaller than n (i.e.,
k < n <= 2k).  The Merkle tree Hash of an n-element list D[n] is then
defined recursively as
MTH(D[n]) = ALG(0x01 || MTH(D[0:k]) || MTH(D[k:n])),

Interface

- build_tree (items) -> tree
- get_root -> hash
- gen_proof -> proof
- validate_proof (proof, leaf, root) -> bool

Quick start

 
extern crate mohan;
extern crate bacteria;

mod example {
    use std::fmt;
    use std::hash::Hasher;
    use std::iter::FromIterator;
    use mohan::hash::H256;
    use mohan::merkle::{Algorithm, Hashable};
    use bacteria::Strobe128;
        
    //This example is not the best way to use strobe
    pub struct ExampleAlgorithm(Strobe128);

    impl ExampleAlgorithm {
        pub fn new() -> ExampleAlgorithm {
            ExampleAlgorithm(Strobe128::new(b"Example Algorithm Strobe"))
        }
    }

    impl Default for ExampleAlgorithm {
        fn default() -> ExampleAlgorithm {
            ExampleAlgorithm::new()
        }
    }

    impl Hasher for ExampleAlgorithm {
        #[inline]
        fn write(&mut self, msg: &[u8]) {
            self.0.ad(msg, false);
        }

        #[inline]
        fn finish(&self) -> u64 {
            unimplemented!()
        }
    }

    impl Algorithm<H256> for ExampleAlgorithm {
        #[inline]
        fn hash(&mut self) -> H256 {
            let mut result = [0u8; 32];
            self.0.prf(&mut result, false);
            H256::from(result)
        }

        #[inline]
        fn reset(&mut self) {
            *self =
                 ExampleAlgorithm::new()
             
        }
    }
}

fn main() {
    use example::ExampleAlgorithm;
    use mohan::merkle::{MerkleTree,VecStore};
    use mohan::hash::H256;
    use std::iter::FromIterator;

    let mut h1 = H256::zero();
    let mut h2 = H256::from_vec(&vec![1u8, 1u8]);
    let mut h3 = H256::from_vec(&vec![2u8, 2u8]);

    let t: MerkleTree<H256, ExampleAlgorithm, VecStore<_>> = MerkleTree::from_iter(vec![h1, h2, h3]);
    println!("{:?}", t.root());
}

Structs

MerkleTree	Merkle Tree.
Proof	Merkle tree inclusion proof for data element, for which item = Leaf(Hash(Data Item)).
VecStore

Traits

Algorithm	A trait for hashing an arbitrary stream of bytes for calculating merkle tree nodes.
Element	Element stored in the merkle tree.
Hashable	A hashable type.
Store	Backing store of the merkle tree.