# 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`](../../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

```go
import "gno.land/p/moul/x/mmr/v0"

log := mmr.New()
i := log.Append([]byte("receipt-1"))   // O(log n), returns the leaf index
log.Append([]byte("receipt-2"))

root := log.RootHex()                  // commit or emit this
p, _ := log.Proof(i)                   // Index, Total, Path, Before, After

// anywhere, later:
if 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`](../../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`](../../merkle/v0)
- Live demo: [`r/moul/x/provable/v0`](../../../../../r/moul/x/provable/v0)

<!-- BEGIN GNOCONTRACTS FOOTER (generated by `make readmes`; do not edit below) -->

---

Part of **[moul/gno-contracts](https://github.com/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](https://raw.githubusercontent.com/moul/gno-contracts/main/_assets/gno.land/p/moul/x/mmr/v0/deps.png)

> 🧪 **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](https://github.com/moul/gno-contracts/blob/main/DISCLAIMER.md).

<!-- END GNOCONTRACTS FOOTER -->