README.md

4.27 Kb · 101 lines

mmr

A Merkle Mountain Range: an append-only log whose root updates in O(log n) and whose inclusion proofs are O(log n) big.

Why not a plain Merkle tree

p/moul/x/merkle/v0 commits to a fixed list. Adding a leaf means rebuilding from every leaf, which on chain means re-reading the whole set and re-hashing it, on every append. An MMR never rebuilds: an append hashes at most log2(n) times and touches nothing else.

That is the shape any on-chain log wants. A wiki committing to its revision history, a forge committing to its objects, an agent realm committing to the receipts it issued: all append, none rewrite.

The headline property: this is the Tendermint tree

The MMR root equals the Tendermint simple-tree root over the same leaves, at every size, not only at powers of two.

Tendermint splits an n-leaf tree at the largest power of two below n. That left half is exactly the first mountain, and the right half recurses through the remaining set bits, which is exactly the peak bagging. The two constructions coincide.

So this package is a drop-in incremental builder for Tendermint roots: append in O(log n) on chain, hand out a root any Tendermint verifier accepts. Proofs cross over in both directions, pinned by TestMerkleProofVerifiesAgainstMMRRoot.

Use merkle.New when the leaf set is fixed and you want the simpler proof encoding. Use this when the log grows.

Structure

An MMR is a list of perfect binary trees ("mountains") of strictly decreasing height, one per set bit of the leaf count. Eleven leaves is 8 + 2 + 1, so three mountains of height 3, 1 and 0. Appending pushes a height-0 mountain and merges equal-height neighbours, exactly like incrementing a binary counter. The root bags the peaks right to left:

root = InnerHash(p0, InnerHash(p1, InnerHash(p2, …)))

Usage

 1import "gno.land/p/moul/x/mmr/v0"
 2
 3log := mmr.New()
 4i := log.Append([]byte("receipt-1"))   // O(log n), returns the leaf index
 5log.Append([]byte("receipt-2"))
 6
 7root := log.RootHex()                  // commit or emit this
 8p, _ := log.Proof(i)                   // Index, Total, Path, Before, After
 9
10// anywhere, later:
11if mmr.Verify(root, []byte("receipt-1"), p) { … }

Proofs are bound to position and to size

A proof carries the leaf index and the leaf count the log had when it was issued. The verifier recomputes the entire peak structure from that count, which fixes the peak count, which mountain holds the leaf, the local index inside it, and therefore the exact expected length of every component. A proof cannot be replayed at another index, against another size, or padded. TestRejects covers thirteen such attempts.

Because the root moves on every append, a proof is valid against the root at its own Total and no other. A realm that wants old proofs to keep verifying must keep the historical roots: one 32-byte hash per append, the price of an auditable log.

Storage

Append stores one node per leaf plus one per merge: 2n - popcount(n) hashes for n leaves, under 64 bytes per leaf amortised, pinned by TestNodeCount. That is what on-chain proof generation costs.

A realm that only ever needs to verify proofs, with the tree living off chain, should store the root alone and use p/moul/x/merkle/v0 instead. PeakHashes() returns the whole verifier-side state and stays logarithmic: 10 hashes at 1023 leaves, 1 at 1024.

Fixed-list trees and the scheme rationale: p/moul/x/merkle/v0
Live demo: r/moul/x/provable/v0

Part of moul/gno-contracts — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage.

Dependency graph:

gno.land/p/moul/x/mmr/v0 dependency graph

🧪 Highly experimental — potentially vibe-coded. Not audited; may break, change, or be removed at any time. Do not use with anything of value. Full disclaimer: DISCLAIMER.

mmr