Crate merkle_light

light 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, 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 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])),

Link:

Implementation choices

Main idea was that the whole code must obtain specialization at compile time, hashes must be fixed size arrays known at compile time, hash algorithm must be interface (lib should not dep on crypto libs) and lib must somehow mimic std Rust api.

Standard way in Rust is to hash objects with a std::hash::Hasher, and mainly that is the reason behind the choice of the abstractions:

Object : Hashable<H> -> Hasher + Algorithm <- Merkle Tree

Custom [merkle::hash::Hashable] trait allows implementations differ from [std::collection] related hashes, different implementations for different hashing algorithms / schemas and conforms object-safety trait rules.

[Algorithm] complements [Hasher] to be reusable and follows the idea that the result hash is a mapping of the data stream.

Interface

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

Examples

[test_sip.rs]: algorithm implementation example for std sip hasher, u64 hash items [test_xor128.rs]: custom hash example xor128 [test_cmh.rs]: custom merkle hasher implementation example

Modules

hash	Hash infrastructure for items in Merkle tree. Hash infrastructure for items in Merkle Tree.
merkle	Merkle tree abstractions, implementation and algorithms.
proof	Merkle tree inclusion proof