1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190
//! 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. [`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](https://tools.ietf.org/html/rfc6962): //! //! ```text //! 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: [](https://en.wikipedia.org/wiki/Merkle_tree) //! //! # Implementation choices //! //! Main idea is the whole code must obtain specialization at compile time with //! minimum allocations calls, hashes must be of fixed size arrays known at //! compile time, hash algorithm must be a trait and must not depend on any //! external cryptographic libraries and the lib itself 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. //! //! [`Algorithm.hash`] had to change its signature to be `&mut self` (`&self`) because //! most of the cryptographic digest algorithms breaks current state on finalization //! into unusable. `ring` libra tho contains interfaces incompatible to //! `start-update-finish-reset` lifecycle. It requires either `cloning()` its state //! on finalization, or `Cell`-ing via unsafe. //! //! Turning back to having [`Algorithm.write(&mut self, &[u8])`] instead of //! `write(T)` allows to relax [`Algorithm`] trait [`Hasher`] constraint, even tho //! works together well still. //! //! # Interface //! //! ```text //! - 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 //! [`crypto_bitcoin_mt.rs`]: bitcoin merkle tree using crypto lib //! [`crypto_chaincore_mt.rs`]: chain core merkle tree using crypto lib //! [`ring_bitcoin_mt.rs`]: bitcoin merkle tree using ring lib //! //! # Quick start //! //! ``` //! #[cfg(feature = "chaincore")] //! extern crate crypto; //! extern crate merkle_light; //! //! #[cfg(feature = "chaincore")] //! mod example { //! use std::fmt; //! use std::hash::Hasher; //! use std::iter::FromIterator; //! use crypto::sha3::{Sha3, Sha3Mode}; //! use crypto::digest::Digest; //! use merkle_light::hash::{Algorithm, Hashable}; //! //! pub struct ExampleAlgorithm(Sha3); //! //! impl ExampleAlgorithm { //! pub fn new() -> ExampleAlgorithm { //! ExampleAlgorithm(Sha3::new(Sha3Mode::Sha3_256)) //! } //! } //! //! impl Default for ExampleAlgorithm { //! fn default() -> ExampleAlgorithm { //! ExampleAlgorithm::new() //! } //! } //! //! impl Hasher for ExampleAlgorithm { //! #[inline] //! fn write(&mut self, msg: &[u8]) { //! self.0.input(msg) //! } //! //! #[inline] //! fn finish(&self) -> u64 { //! unimplemented!() //! } //! } //! //! impl Hashable<ExampleAlgorithm> for [u8; 32] { //! fn hash(&self, state: &mut ExampleAlgorithm) { //! Hasher::write(state, self.as_ref()) //! } //! } //! //! impl Algorithm<[u8; 32]> for ExampleAlgorithm { //! #[inline] //! fn hash(&mut self) -> [u8; 32] { //! let mut h = [0u8; 32]; //! self.0.result(&mut h); //! h //! } //! //! #[inline] //! fn reset(&mut self) { //! self.0.reset(); //! } //! } //! } //! //! fn main() { //! #[cfg(feature = "chaincore")] //! { //! use example::ExampleAlgorithm; //! use merkle_light::merkle::MerkleTree; //! use std::iter::FromIterator; //! //! let mut h1 = [0u8; 32]; //! let mut h2 = [0u8; 32]; //! let mut h3 = [0u8; 32]; //! h1[0] = 0x11; //! h2[0] = 0x22; //! h3[0] = 0x33; //! //! let t: MerkleTree<[u8; 32], ExampleAlgorithm> = MerkleTree::from_iter(vec![h1, h2, h3]); //! println!("{:?}", t.root()); //! } //! } //! ``` #![deny( missing_docs, unused_qualifications, missing_debug_implementations, missing_copy_implementations, trivial_casts, trivial_numeric_casts, unsafe_code, unstable_features, unused_import_braces )] #![cfg_attr(feature="nightly", allow(unstable_features))] /// Hash infrastructure for items in Merkle tree. pub mod hash; /// Common implementations for [`Hashable`]. mod hash_impl; /// Merkle tree inclusion proof pub mod proof; /// Merkle tree abstractions, implementation and algorithms. pub mod merkle; /// Tests data. #[cfg(test)] mod test_item; /// Tests XOR128. #[cfg(test)] mod test_xor128; /// Tests SIP. #[cfg(test)] mod test_sip; /// Tests for Merkle Hasher Customization #[cfg(test)] mod test_cmh;