Crate merkle_heapless

source ·
Expand description

§Static Tree

A Merkle Tree implementation that requires no dynamic memory allocations. This Merkle tree is implemented as a contiguous memory array and does not betake to dynamic allocations. As such it allows for certain optimizations and compile-time imposed constraints on arity and size boundaries.

  • no std dependencies (actually no dependencies)
  • 2, 4, 8,… power of 2 general branching arity
  • any hash function that takes &[u8] and returns something that implements AsRef<[u8]>
  • 99% safe Rust
  • optionally augmentable or reducible
  • optional Mountain Range proc macro (when compiled with a mmr-macro feature)

§Hashing

Leaves are prefixed with LEAF_HASH_PREPEND_VALUE prior to being hashed, while the intermediate nodes are prefixed with [1u8; 4].

§Mountain Range

Merkle Mountain Range offers append-only growable Merkle Tree semantics optimized for space.

The rules for this implementation of Mountain Range are:

  • space limitations are defined at compile-time (no dynamic allocations) by number of peaks only
  • an element is inserted by appending to the right-most peak having a capacity to append a new item
  • the left-most peak is the highest peak at any moment
  • when two adjacent peaks have the same height they are recursively merged into the left sibling
  • roots of the peaks form leaves for the “summit Merkle tree”
  • the Mountain Range proof is generated by chaining the proof of the corresponding peak with the proof generated by the relevant path in the summit tree
  • for MMR declared with N peaks, it will handle peaks with heights [0..N] thus simulating a tree with number of leaves in range [0..N*2^N] in case of a binary MMR

§Examples

§Hash implementation examples

use std::{
    collections::hash_map::DefaultHasher,
    hash::{Hash, Hasher},
};
use merkle_heapless::traits::HashT;

#[derive(Debug)]
struct Blake2_256Hash;
impl HashT for Blake2_256Hash {
    type Output = [u8; 32];

    fn hash(input: &[u8]) -> Self::Output {
        // from Parity's sp_core crate
        sp_core::blake2_256(input)
    }
}

#[derive(Debug)]
pub struct StdHash;
impl HashT for StdHash {
    type Output = [u8; 8];

    fn hash(input: &[u8]) -> Self::Output {
        let mut s = DefaultHasher::new();
        input.hash(&mut s);
        s.finish().to_ne_bytes()
    }
}

§Proof generation and verification

use merkle_heapless::{StaticBinaryTree};
use merkle_heapless::traits::{StaticTreeTrait, ProofValidator};
// tree height 3, 8 leaves, 15 total nodes
const MAX_HEIGHT: usize = 3;
// stands for the maximum possible length of the longest input word
const MAX_INPUT_WORD_LEN: usize = 10;
// supposing the YourHash struct exists
let mut tree = StaticBinaryTree::<MAX_HEIGHT, YourHash, MAX_INPUT_WORD_LEN>::try_from::<&[u8]>(
    &[b"apple", b"banana"]
).unwrap();

let proof = tree.generate_proof(0);
assert!(proof.validate(b"apple"));

§Replace and remove leaf

// snip
// replace
tree.replace(5, b"cherry");
let proof = tree.generate_proof(5);
assert!(proof.validate(b"cherry"));
// remove
tree.replace(1, &[]);
let proof = tree.generate_proof(1);
assert!(!proof.validate(b"banana"));
let proof = tree.generate_proof(1);
assert!(proof.validate(&[]));

§Arity other than 2

use merkle_heapless::{StaticTree};

const ARITY: usize = 4;
const MAX_INPUT_WORD_LEN: usize = 10;
let mut tree = StaticTree::<ARITY, MAX_HEIGHT, YourHash, MAX_INPUT_WORD_LEN>::try_from::<&[u8]>(
    &[b"apple", b"banana"]
).unwrap();
// same operations can be applied

§Mountain Range

Include [“mmr_macro”] feature in merkle-heapless dependency

§Declaration and instantiation

// compulsory at the beginning of the .rs file in order the macro to compile
#![allow(incomplete_features)]
#![feature(generic_const_exprs)]
// snip
use merkle_heapless::{mmr_macro};
// declaration with expicit type name for your MMR
mmr_macro::mmr!(Type = FooMMR, BranchFactor = 2, Peaks = 3, Hash = StdHash, MaxInputWordLength = 10);
let mmr = FooMMR::default();
// implicitly creates MerkleMountainRange type
mmr_macro::mmr!(BranchFactor = 2, Peaks = 5, Hash = StdHash, MaxInputWordLength = 10);
// create with default current peak of height 0
let mmr = MerkleMountainRange::default();
// or create with current peak of height 2
let mut mmr = MerkleMountainRange::from_peak(MerkleMountainRangePeak::Peak3(Default::default()));
assert_eq!(mmr.peaks()[0].height(), 5 - 3);

§Functionality

The functionality of Mountain Range is similar to that of the Merkle tree.

mmr.try_append(b"apple").unwrap();
// peak leaf numbers: [1, 0, 0, 0, 0]
assert_eq!(mmr.peaks()[0].height(), 0);
assert_eq!(mmr.peaks()[0].num_of_leaves(), 1);
assert_eq!(mmr.peaks()[1].num_of_leaves(), 0);
let proof = mmr.generate_proof(0);
assert!(proof.validate(b"apple"));

Modules§

  • augmentable
    contains implementation of an extention for a Merkle Tree that can be augmented into a bigger tree
  • compactable
    contains implementation of an extention for a Merkle Tree that can remove a leaf, compact and reduce the tree to a smaller tree.
  • prefixed
    prefixed hashes
  • proof
    module containing Proof implementation the StaticTree generates
  • traits
    module declaring basic traits for tree and proof

Macros§

  • is_pow2
    determines if a number is power of 2
  • layer_size
    size of a layer at index in a tree with given arity and height
  • max_leaves
    size of a layer at index in a tree with given arity and height
  • num_of_prefixed
  • total_size
    total size of elements in a tree with given arity and height

Structs§

Enums§

Constants§

Type Aliases§