Crate merkle_cbt_lean

This crate is a no_std compatible tool to generate Merkle trees and and calculate root values in constrained RAM environments. Merkle tree elements are addressable from generalized “external” memory which could be anything from regular address space to address space on remote storage with arbitrary access rules, or even serial input pipes.

The crate is based on CBMT implementation of the crate merkle-cbt. The root calculation outcomes are matching those of the merkle-cbt crate.

Calculation sequence differs, and lemmas have different sorting. MerkleProof constructions of the two crates are not interchangeable.

In this crate, all lemmas of the proof are sorted strictly left-to-right. It is also assumed that the proof was generated strictly by this algorithm: if the proof is not optimized, i.e., there are lemmas that could be merged without supplying valuer of leaves to be checked, this process will fail.

In this crate, the root calculation is done with depth graph traverse, as opposed to width graph traverse in merkle-cbt. This approach substantially decreases memory requirements (other than lemmas and leaves storage space, it stores only one hash per tree layer to total ~log(n), opposed to storing whole layer in width traverse algorithms, ~n), at the cost of more time needed for the calculation (roughly O(n^2) versus O(n)).

Key definitions

Leaf is generalized Merkle tree node, it has a corresponding value, an array of pre-known length N. Trait Leaf describes how such arrays could be read and (for proof-gen feature) written in memory.

Hasher describes how the values of Merkle tree nodes are calculated and merged.

MerkleProof contains leaves and lemmas, and root value could be calculated for it.

Example

use external_memory_tools::ExternalMemory;
use merkle_cbt_lean::{Hasher, Leaf, MerkleProof};

const LEN: usize = 32;

#[derive(Debug)]
struct Blake3Hasher;

impl Hasher<LEN> for Blake3Hasher {
    fn make(bytes: &[u8]) -> [u8; LEN] {
        blake3::hash(bytes).into()
    }
    fn merge(left: &[u8; LEN], right: &[u8; LEN]) -> [u8; LEN] {
        blake3::hash(&[left.as_slice(), right.as_slice()].concat()).into()
    }
}

#[derive(Copy, Clone, Debug)]
struct Blake3Leaf([u8; LEN]);

impl<E: ExternalMemory> Leaf<LEN, E> for Blake3Leaf {
    fn read(&self, _ext_memory: &mut E) -> Result<[u8; LEN], E::ExternalMemoryError> {
        Ok(self.0)
    }
    fn write(value: [u8; LEN], _ext_memory: &mut E) -> Result<Self, E::ExternalMemoryError> {
        Ok(Self(value))
    }
}

// All leaf values, deterministically sorted.
let all_values = vec![[0; LEN], [1; LEN], [2; LEN], [3; LEN], [4; LEN], [5; LEN]];

// Values that remain as leaves in the proof structure, other leaves will be
// reduced to lemmas.
// Remaining leaves will be available during the proof de-serialization.
// It is assumed that the remaining leaf values are deterministically sorted
// during serialization and de-serialization.
let remaining_as_leaves = &[[0; LEN], [3; LEN], [1; LEN]];

// Calculate `MerkleProof` for known complete set of values and known subset
// of remaining values:
let merkle_proof: MerkleProof<LEN, Blake3Leaf, (), Blake3Hasher> =
    MerkleProof::for_leaves_subset(all_values, remaining_as_leaves, &mut ()).unwrap();

// Serialize `MerkleProof` for data transferring:

// Indices for remaining leaves:
let indices = merkle_proof.indices();

// Lemmas:
let lemmas = merkle_proof.lemmas;

// De-serialize `MerkleProof`:
let mut merkle_proof_restored: MerkleProof<LEN, Blake3Leaf, (), Blake3Hasher> =
    MerkleProof::new_with_external_indices(
        remaining_as_leaves.to_vec(),
        indices,
        lemmas,
    ).unwrap();

// Calculate root:
let root_restored = merkle_proof_restored.calculate_root(&mut ()).unwrap();

Features

Crate supports no_std in default-features = false mode.

With feature proof-gen (no-std compatible) MerkleProof could be generated for a subset of leaves. proof-gen is not needed to reconstruct MerkleProof from serialization, nor to calculate root for existing MerkleProof.

Structs

• Index
  Node index.
• MerkleProof
  Combination of lemmas and leaves, sufficient to calculate Merkle tree root.
• Node
  Node, a combination of index and hash value.

Enums

• ErrorMT
  Errors in Merkle tree construction and processing.

Traits

• Hasher
  Describes how Merkle tree leaves are generated and merged.
• Leaf
  Describes how Merkle tree leaves are accessed from memory.