merkl

A no_std + alloc sparse Merkle tree with a pluggable, namespaced key-value storage backend.

The initial version of this crate was vibe coded. Check it out on YouTube.

How it works

Each leaf is addressed by a key (a 32-byte hash). The key's bits, read MSB-first, determine the path from root to leaf: bit 0 selects left (0) or right (1) at the root, bit 1 at the next level, and so on. Internal nodes are stored in the backend keyed by their own hash, holding a 64-byte serialised Node (left ‖ right child hashes).

The root lives outside the tree. MerkleTree holds no state beyond its backend and hash-function marker. Every operation receives a root Hash and returns a new root — making historical roots and independent sub-trees free.

root ──► Node{ left, right }
              │          │
          Node{…}    leaf_hash   ← terminal: no backend entry
              │
          leaf_hash   ← terminal

An all-zero Hash (Hash::default()) is the canonical empty root.

Three ways to insert a leaf:

Feature flags

Quick start

SHA-256 hasher (sha2 feature)

[dependencies]
merkl = { version = "0.4", features = ["sha2"] }

#[cfg(feature = "sha2")] {
use merkl::{Hash, MemoryBackend, Sha256MerkleTree};

let tree = Sha256MerkleTree::<MemoryBackend>::new(MemoryBackend::new());
let root = [b"alpha" as &[u8], b"beta", b"gamma"]
    .iter()
    .fold(Hash::default(), |r, leaf| tree.insert("ns", r, leaf).unwrap());
}

Index-keyed inserts

Useful for append-like structures where each element has a stable numeric position. The index parameter is raw bytes (up to 32) zero-padded into a 32-byte key:

use merkl::{Hash, tree::MerkleTreeDummy};
let tree = MerkleTreeDummy::default();
// Use little-endian encoded integers as the index bytes.
let root = tree.insert_indexed("ns", Hash::default(), &0u64.to_le_bytes(), b"first").unwrap();
let root = tree.insert_indexed("ns", root, &1u64.to_le_bytes(), b"second").unwrap();

The key for index is the raw bytes copied into a 32-byte zero-padded buffer, giving each index a fixed, deterministic position in the tree.

redb backend (redb feature)

[dependencies]
merkl = { version = "0.4", features = ["redb", "sha2"] }

#[cfg(all(feature = "redb", feature = "sha2"))] {
use merkl::{Hash, Sha256Hasher, redb::{RedbBackend, RedbMerkleTree}};

// Ephemeral in-memory database — no files created.
let backend = RedbBackend::in_memory().unwrap();
let tree = RedbMerkleTree::<Sha256Hasher>::new(backend);
let root = tree.insert("ns", Hash::default(), b"hello").unwrap();
}

For a persistent file-backed database:

#[cfg(feature = "redb")] {
let backend = merkl::redb::RedbBackend::create("my_tree.redb").unwrap();
}

Cloning a RedbBackend is cheap — all clones share the same underlying Database via Arc (or Rc on targets without atomics).

Each set call opens, writes, and commits its own write transaction. For bulk tree construction, wrapping a single redb::WriteTransaction in a custom backend will give better throughput.

fjall backend (fjall feature)

[dependencies]
merkl = { version = "0.4", features = ["fjall"] }

#[cfg(feature = "fjall")] {
use merkl::fjall::{current::Database, FjallBackend};
let db = Database::builder("my_tree").open().unwrap();
let backend = FjallBackend::from(db);
}

Membership proofs

get_opening collects sibling hashes bottom-up. Verification is a pure hash computation — it never touches the backend:

use merkl::{Hash, tree::MerkleTreeDummy};
let (tree, root) = (MerkleTreeDummy::default(), Hash::default());
// create an opening proof
let proof = tree.get_opening("ns", root, b"alice").unwrap();
assert_eq!(proof.leaf_root(<() as merkl::Hasher>::hash(b"alice")), root); // membership verified

// For indexed inserts:
let proof = tree.get_indexed_opening("ns", root, &0u64.to_le_bytes()).unwrap();
assert_eq!(proof.leaf_indexed_root(&0u64.to_le_bytes(), <() as merkl::Hasher>::hash(b"first")).unwrap(), root);

Non-membership proofs

A sparse Merkle tree can also prove that a position is empty:

use merkl::{Hash, tree::MerkleTreeDummy};
let (tree, root) = (MerkleTreeDummy::default(), Hash::default());
// "carol" was never inserted; the path leads to an empty slot.
let proof = tree.get_opening("ns", root, b"carol").unwrap();
assert_eq!(proof.non_membership_leaf_root(b"carol"), root); // non-membership verified

Traversal directions are derived from the key at verification time — never stored in the proof — so the proof cannot be forged by manipulating direction bits.

Implementing KvsBackend

The KvsBackend trait is the only integration point:

use merkl::KvsBackend;
use anyhow::Result;

struct MyBackend { /* … */ }

impl KvsBackend for MyBackend {
    // `Get` must deref to `[u8]`. Use `Vec<u8>` for the simplest case.
    type Get = Vec<u8>;

    fn get(&self, ns: &str, key: &[u8]) -> Result<Option<Vec<u8>>> {
        // Look up `key` in namespace `ns`.
        todo!()
    }

    fn set(&self, ns: &str, key: &[u8], value: &[u8]) -> Result<()> {
        // Store `value` under `key` in namespace `ns`.
        todo!()
    }
}

Key facts:

• All methods take &self — use interior mutability (RefCell, Mutex, etc.) for the write path.
• ns is used by the tree to separate node storage (ns) from its internal key-mapping namespace ("{ns}-key"). Your backend only needs to use it as an extra scope for isolation.
• Tree node keys are 32-byte parent hashes; values are 64-byte Node encodings (left ‖ right).

For bare-metal targets, wrap your store in RefCell (single-core) or a critical_section::Mutex (multi-core / interrupt-driven):

License

MIT — see LICENSE.