const HashSize
HashSize is the length in bytes of every node hash.
v0 source pure
Package mmr implements a Merkle Mountain Range: an append-only log with a root that updates in O(log n) and inclusion...
View source
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.
Related
- 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:
🧪 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.
Package mmr implements a Merkle Mountain Range: an append-only log with a root that updates in O(log n) and inclusion proofs of O(log n) size.
Why not a plain Merkle tree
gno.land/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, every time. 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 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 a leaf pushes a height-0 mountain and merges equal-height neighbours, exactly like incrementing a binary counter.
The root is the peaks "bagged" right to left:
Example
1root = InnerHash(p0, InnerHash(p1, InnerHash(p2, …)))
Hashing is gno.land/p/moul/x/merkle/v0's, which is Tendermint's: leaves are tagged 0x00 and inner nodes 0x01. Leaf and inner preimages therefore cannot collide, so the second-preimage forgery that works against untagged schemes does not apply here. See that package for the worked attack.
This IS the Tendermint tree
The root above equals the Tendermint simple-tree root over the same leaves, at every size and not merely 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 bagging. The two constructions coincide.
So this package is a drop-in INCREMENTAL BUILDER for Tendermint roots. Append in O(log n) on chain and hand out a root that any Tendermint verifier accepts; proofs cross over in both directions, which TestMerkleProofVerifiesAgainstMMRRoot pins. Use merkle.New when the leaf set is fixed and you want the simpler proof encoding, use this when the log grows.
Proofs are bound to position and to size
A Proof carries the leaf index and the leaf count the MMR had when it was issued. The verifier recomputes the whole peak structure from that count, which fixes the number of peaks, which mountain holds the leaf, the local index inside it, and therefore the exact expected length of every component of the proof. A proof cannot be replayed at another index, against another size, or padded.
Because the root changes 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; Roots grow by one 32-byte hash per append, which is the price of an auditable log.
Storage
Append stores one node per leaf plus one per merge, so 2n-popcount(n) hashes for n leaves, under 64 bytes per leaf amortised. 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 gno.land/p/moul/x/merkle/v0's Verify instead.
Live demo: gno.land/r/moul/x/provable/v0
2
1
3
func Verify
Verify reports whether leaf really sits at p.Index of a log that held p.Total leaves and whose root is root.
Every dimension of the proof is checked against p.Total rather than trusted: the peak count, which mountain holds the leaf, the local index, the path length and both peak-list lengths are all recomputed. A proof that does not have exactly the shape p.Total implies is rejected before any hashing.
Failures are false, never a panic, so a realm chooses whether a bad proof aborts or branches.
func New
New returns an empty MMR.
func ParseProof
ParseProof rebuilds a Proof from realm-call arguments. Each of path, before and after is a comma-separated hex list, possibly empty.
2
type MMR
structMMR is an append-only Merkle mountain range.
The zero value is an empty, ready-to-use log.
Methods on MMR
func Append
method on MMRAppend adds a leaf and returns its index. O(log n) hashes, no rebuild.
func Nodes
method on MMRNodes returns the number of stored hashes, leaves and merges together. Use it to reason about storage growth.
func PeakHashes
method on MMRPeakHashes returns the current peak hashes, left to right. This is the whole state a verifier needs, and it is O(log n).
func Proof
method on MMRProof returns the inclusion proof for the leaf at index, against the current root.
func Root
method on MMRRoot returns the current root, nil while the log is empty.
func RootHex
method on MMRRootHex returns Root hex-encoded.
func Size
method on MMRSize returns the number of leaves appended so far.
type Proof
structProof is an inclusion proof for one leaf of a log that held Total leaves.
Path holds the sibling hashes inside the leaf's own mountain, leaf first. Before and After hold the other peak hashes, in left-to-right order.
4
- encoding/hex stdlib
- errors stdlib
- gno.land/p/moul/x/merkle/v0 package
- strings stdlib
