2 releases
0.1.1 | Apr 18, 2024 |
---|---|
0.1.0 | Apr 18, 2024 |
#1 in #mintlayer
940 downloads per month
155KB
3.5K
SLoC
Merkle tree - Mintlayer
An implementation of merkle tree, and related tooling, such as inclusion proofs, done for the Mintlayer blockchain.
Introduction
This library was separated from the mintlayer-core repository because it is stable and to benefit the community, by providing a simple, and robust implementation of a merkle tree.
Advantages
- Heavily tested
- Simplistic
- Made to be extensible
- Minimal amount of dependencies
You can include scale-codec dependency for serialization, but it can be disabled too, in which case you choose your own serialization method, if needed.
Special assumptions
This library doesn't hash the leaves.
Examples
You can find examples for how to get started with this library in the examples directory. However, this is a quick example:
use blake2::{digest::typenum, Digest};
use merkletree_mintlayer::{hasher::PairHasher, tree::MerkleTree};
// You can use any hashing function you like, we use blake2b here as an example
type Blake2bHasher = blake2::Blake2b<typenum::U32>;
// A helper function that hashes data, not necessary for your application
pub fn hash_data<T: AsRef<[u8]>>(data: T) -> TreeNode {
let mut h = Blake2bHasher::new();
Digest::update(&mut h, data);
h.finalize_reset().into()
}
// You can use any node type you like, as long as you use it consistently in the tree
// See the PairHasher implementation
type TreeNode = [u8; 32];
// You have to define a type that implements `PairHasher` trait, which will tell the tree how to combine different nodes
#[derive(Clone)]
pub struct HashAlgo(Blake2bHasher);
impl HashAlgo {
pub fn new() -> Self {
Self(Blake2bHasher::new())
}
pub fn write<T: AsRef<[u8]>>(&mut self, in_bytes: T) {
Digest::update(&mut self.0, in_bytes);
}
pub fn finalize(&mut self) -> TreeNode {
self.0.finalize_reset().into()
}
}
// This is the important part, your hasher has to implement PairHasher
impl PairHasher for HashAlgo {
type NodeType = TreeNode;
fn hash_pair(left: &Self::NodeType, right: &Self::NodeType) -> Self::NodeType {
let mut h = Blake2bHasher::new();
Digest::update(&mut h, left);
Digest::update(&mut h, right);
h.finalize_reset().into()
}
fn hash_single(data: &Self::NodeType) -> Self::NodeType {
let mut h = Blake2bHasher::new();
Digest::update(&mut h, data);
h.finalize_reset().into()
}
}
fn main() {
// You have to hash the leaves or create them (any way you like)
let leaf0 = hash_data("0");
let leaf1 = hash_data("1");
let leaf2 = hash_data("2");
let leaf3 = hash_data("3");
// The tree is defined from a vector of leaves, from left to right
let tree =
MerkleTree::<TreeNode, HashAlgo>::from_leaves(vec![leaf0, leaf1, leaf2, leaf3]).unwrap();
// Let's get the root
let tree_root = tree.root();
println!("Merkle tree root: {}", hex::encode(tree_root));
// Let's verify some properties about this tree
// The number of leaves is 4
assert_eq!(tree.leaf_count().get(), 4);
// The number of levels is 3 (4 leaves -> 2 nodes -> 1 root)
assert_eq!(tree.level_count().get(), 3);
// Total number of nodes in the tree (4 + 2 + 1)
assert_eq!(tree.total_node_count().get(), 7);
// We attempt to recreate the expected root manually
let mut node10 = HashAlgo::new();
node10.write(leaf0);
node10.write(leaf1);
let mut node11 = HashAlgo::new();
node11.write(leaf2);
node11.write(leaf3);
let mut node00 = HashAlgo::new();
let n10 = node10.finalize();
node00.write(n10);
let n11 = node11.finalize();
node00.write(n11);
let root_that_we_created_manually = node00.finalize();
// the root calculated matches the one calculated by the tree
assert_eq!(tree.root(), root_that_we_created_manually);
}
Dependencies
~0.7–1.3MB
~28K SLoC