Skip to content

Warning

This project is in early development and is not production-ready. Use at your own risk.

MTS - Merkle Tree Store

What is MTS?

MTS (Merkle Tree Store) is a Haskell library providing a shared interface for authenticated key-value stores backed by Merkle tries. It ships with two implementations:

  • CSMT - Compact Sparse Merkle Tree: a binary trie with path compression, CBOR-encoded inclusion proofs, and completeness proofs via secondary indexing.
  • MPF - Merkle Patricia Forest: a 16-ary trie using hex nibble keys, with batch/streaming inserts and root hashes compatible with the Aiken reference implementation.

Both implementations conform to a single MerkleTreeStore record type parameterised by an implementation tag and a monad, so application code can be written once and run against either backend.

Features

  • Shared interface: MerkleTreeStore record with type families for key, value, hash, proof, leaf, and completeness proof types (MTS Interface)
  • 13 QuickCheck properties: Verify feature parity across implementations (insert-verify, order independence, batch equivalence, completeness round-trip, etc.)
  • Two trie backends: Binary (CSMT) and 16-ary (MPF), each with RocksDB and in-memory storage
  • Merkle proofs: Inclusion and exclusion proofs for both implementations; CSMT also supports completeness proofs over prefix-grouped subtrees
  • Batch and streaming inserts: MPF supports insertingBatch, insertingChunked, and insertingStream for large datasets
  • Aiken compatibility: MPF produces root hashes and proof-step encodings matching the Aiken MerkleTree implementation (verified against the 30-fruit test vector)
  • Browser demos: published static demos for read-only CSMT verify, CSMT write/prove/verify, and MPF write/prove/verify
  • CLI tool: Interactive command-line interface for CSMT tree operations
  • TypeScript verifier: Client-side CSMT proof verification for browser/Node.js
  • Pure MPF verifier: exact Aiken inclusion/exclusion verification in Haskell via MPF.Verify

Quick Start

import MTS.Interface (MerkleTreeStore(..))

example :: MerkleTreeStore imp IO -> IO ()
example store = do
    mtsInsert store "key" "value"
    proof <- mtsMkProof store "key"
    root  <- mtsRootHash store
    print (proof, root)

export CSMT_DB_PATH=./mydb
mts
> i key1 value1
> q key1
AQDjun1C8tTl1kdY1oon8sAQWL86/UMiJyZFswQ9Sf49XQAA

Status

Shared Interface (mts)

  • MerkleTreeStore record with type families
  • 13 shared QuickCheck properties
  • CSMT passes all 13 properties
  • MPF passes 10 of 13 (completeness proofs pending)

CSMT Implementation (mts:csmt)

  • Insertion and deletion
  • Inclusion proof generation and verification (CBOR)
  • Completeness proofs (prefix-based subtrees)
  • Persistent storage (RocksDB)
  • Secondary indexing via treePrefix
  • CLI tool
  • TypeScript proof verifier
  • Insertion benchmarks

MPF Implementation (mts:mpf)

  • Insertion and deletion
  • Inclusion and exclusion proof generation
  • Pure Aiken inclusion/exclusion verification (MPF.Verify)
  • Batch, chunked, and streaming inserts
  • Aiken-compatible root hashes and proof-step encoding
  • Browser write/prove/verify demo (mpf-write.wasm + mpf-verify.wasm)
  • Persistent storage (RocksDB)
  • Completeness proofs
  • Benchmarks

Tutorials And Demos

Start here if you want a guided path through the repository:

  1. Installation for local setup and build options
  2. CLI Manual for the CSMT command-line workflow
  3. CSMT WASM Verifier Demo for the read-only browser verifier
  4. CSMT WASM Write Demo for browser-side mutation + proof generation
  5. MPF WASM Write Demo for the MPF browser flow with Aiken-compatible proofs

Planned

  • HTTP service with RESTful API
  • MPF completeness proofs
  • Production-grade testing