mmr.gno

  1// Package mmr implements a Merkle Mountain Range: an append-only log with a
  2// root that updates in O(log n) and inclusion proofs of O(log n) size.
  3//
  4// # Why not a plain Merkle tree
  5//
  6// gno.land/p/moul/x/merkle/v0 commits to a FIXED list. Adding a leaf means
  7// rebuilding from every leaf, which on chain means re-reading the whole set
  8// and re-hashing it, every time. An MMR never rebuilds: an append hashes at
  9// most log2(n) times and touches nothing else.
 10//
 11// That is the shape any on-chain log wants. A wiki committing to its revision
 12// history, a forge committing to its objects, an agent realm committing to the
 13// receipts it issued: all append, none rewrite.
 14//
 15// # The structure
 16//
 17// An MMR is a list of perfect binary trees ("mountains") of strictly
 18// decreasing height, one per set bit of the leaf count. Eleven leaves is
 19// 8 + 2 + 1, so three mountains of height 3, 1 and 0. Appending a leaf pushes
 20// a height-0 mountain and merges equal-height neighbours, exactly like
 21// incrementing a binary counter.
 22//
 23// The root is the peaks "bagged" right to left:
 24//
 25//	root = InnerHash(p0, InnerHash(p1, InnerHash(p2, …)))
 26//
 27// Hashing is gno.land/p/moul/x/merkle/v0's, which is Tendermint's: leaves are
 28// tagged 0x00 and inner nodes 0x01. Leaf and inner preimages therefore cannot
 29// collide, so the second-preimage forgery that works against untagged schemes
 30// does not apply here. See that package for the worked attack.
 31//
 32// # This IS the Tendermint tree
 33//
 34// The root above equals the Tendermint simple-tree root over the same leaves,
 35// at every size and not merely at powers of two. Tendermint splits an n-leaf
 36// tree at the largest power of two below n: that left half is exactly the
 37// first mountain, and the right half recurses through the remaining set bits,
 38// which is exactly the bagging. The two constructions coincide.
 39//
 40// So this package is a drop-in INCREMENTAL BUILDER for Tendermint roots.
 41// Append in O(log n) on chain and hand out a root that any Tendermint verifier
 42// accepts; proofs cross over in both directions, which
 43// TestMerkleProofVerifiesAgainstMMRRoot pins. Use merkle.New when the leaf set
 44// is fixed and you want the simpler proof encoding, use this when the log
 45// grows.
 46//
 47// # Proofs are bound to position and to size
 48//
 49// A Proof carries the leaf index and the leaf count the MMR had when it was
 50// issued. The verifier recomputes the whole peak structure from that count,
 51// which fixes the number of peaks, which mountain holds the leaf, the local
 52// index inside it, and therefore the exact expected length of every component
 53// of the proof. A proof cannot be replayed at another index, against another
 54// size, or padded.
 55//
 56// Because the root changes on every append, a proof is valid against the root
 57// at its own Total and no other. A realm that wants old proofs to keep
 58// verifying must keep the historical roots; Roots grow by one 32-byte hash per
 59// append, which is the price of an auditable log.
 60//
 61// # Storage
 62//
 63// Append stores one node per leaf plus one per merge, so 2n-popcount(n) hashes
 64// for n leaves, under 64 bytes per leaf amortised. That is what on-chain proof
 65// generation costs. A realm that only ever needs to VERIFY proofs, with the
 66// tree living off chain, should store the root alone and use
 67// gno.land/p/moul/x/merkle/v0's Verify instead.
 68//
 69// Live demo: gno.land/r/moul/x/provable/v0
 70package mmr
 71
 72import (
 73	"encoding/hex"
 74	"errors"
 75
 76	"gno.land/p/moul/x/merkle/v0"
 77)
 78
 79// HashSize is the length in bytes of every node hash.
 80const HashSize = merkle.HashSize
 81
 82// MaxPeaks caps the peak count a Proof may claim. A 64-peak MMR would hold
 83// more than 2^64 leaves.
 84const MaxPeaks = 64
 85
 86var (
 87	ErrEmpty      = errors.New("mmr: log is empty")
 88	ErrIndexRange = errors.New("mmr: leaf index out of range")
 89	ErrBadHex     = errors.New("mmr: hash is not valid hex")
 90	ErrBadSize    = errors.New("mmr: hash is not 32 bytes")
 91	ErrTooManyPeaks = errors.New("mmr: more peaks than MaxPeaks")
 92)
 93
 94// peak is one mountain: the position of its root in nodes, and its height.
 95type peak struct {
 96	pos    int
 97	height int
 98}
 99
100// MMR is an append-only Merkle mountain range.
101//
102// The zero value is an empty, ready-to-use log.
103type MMR struct {
104	nodes  [][]byte // every node, in postorder: [left subtree][right subtree][root]
105	peaks  []peak
106	leaves int
107}
108
109// New returns an empty MMR.
110func New() *MMR { return &MMR{} }
111
112// Size returns the number of leaves appended so far.
113func (m *MMR) Size() int { return m.leaves }
114
115// Nodes returns the number of stored hashes, leaves and merges together. Use
116// it to reason about storage growth.
117func (m *MMR) Nodes() int { return len(m.nodes) }
118
119// Append adds a leaf and returns its index. O(log n) hashes, no rebuild.
120func (m *MMR) Append(leaf []byte) int {
121	index := m.leaves
122	m.nodes = append(m.nodes, merkle.LeafHash(leaf))
123	m.peaks = append(m.peaks, peak{pos: len(m.nodes) - 1, height: 0})
124	for len(m.peaks) >= 2 {
125		right := m.peaks[len(m.peaks)-1]
126		left := m.peaks[len(m.peaks)-2]
127		if left.height != right.height {
128			break
129		}
130		m.nodes = append(m.nodes, merkle.InnerHash(m.nodes[left.pos], m.nodes[right.pos]))
131		m.peaks = m.peaks[:len(m.peaks)-2]
132		m.peaks = append(m.peaks, peak{pos: len(m.nodes) - 1, height: left.height + 1})
133	}
134	m.leaves++
135	return index
136}
137
138// Root returns the current root, nil while the log is empty.
139func (m *MMR) Root() []byte {
140	if len(m.peaks) == 0 {
141		return nil
142	}
143	return bag(m.peakHashes())
144}
145
146// RootHex returns Root hex-encoded.
147func (m *MMR) RootHex() string { return hex.EncodeToString(m.Root()) }
148
149// PeakHashes returns the current peak hashes, left to right. This is the whole
150// state a verifier needs, and it is O(log n).
151func (m *MMR) PeakHashes() [][]byte { return m.peakHashes() }
152
153func (m *MMR) peakHashes() [][]byte {
154	out := make([][]byte, len(m.peaks))
155	for i, p := range m.peaks {
156		out[i] = m.nodes[p.pos]
157	}
158	return out
159}
160
161// bag folds peaks right to left: InnerHash(p0, InnerHash(p1, …)).
162func bag(peaks [][]byte) []byte {
163	if len(peaks) == 0 {
164		return nil
165	}
166	acc := peaks[len(peaks)-1]
167	for i := len(peaks) - 2; i >= 0; i-- {
168		acc = merkle.InnerHash(peaks[i], acc)
169	}
170	return acc
171}
172
173// Proof is an inclusion proof for one leaf of a log that held Total leaves.
174//
175// Path holds the sibling hashes inside the leaf's own mountain, leaf first.
176// Before and After hold the other peak hashes, in left-to-right order.
177type Proof struct {
178	Index  int
179	Total  int
180	Path   [][]byte
181	Before [][]byte
182	After  [][]byte
183}
184
185// Proof returns the inclusion proof for the leaf at index, against the current
186// root.
187func (m *MMR) Proof(index int) (Proof, error) {
188	if m.leaves == 0 {
189		return Proof{}, ErrEmpty
190	}
191	if index < 0 || index >= m.leaves {
192		return Proof{}, ErrIndexRange
193	}
194	j, local := locate(m.leaves, index)
195	hashes := m.peakHashes()
196	return Proof{
197		Index:  index,
198		Total:  m.leaves,
199		Path:   m.pathIn(m.peaks[j], local),
200		Before: hashes[:j],
201		After:  hashes[j+1:],
202	}, nil
203}
204
205// pathIn walks down the perfect tree rooted at p, collecting the sibling at
206// each level, and returns them leaf first.
207//
208// The layout is postorder, so for a node at position pos and height h the
209// right child root sits at pos-1 and the left child root at pos-1-(2^h - 1),
210// a perfect subtree of height h-1 holding 2^h - 1 nodes.
211func (m *MMR) pathIn(p peak, local int) [][]byte {
212	var out [][]byte
213	pos, h := p.pos, p.height
214	for h > 0 {
215		rightRoot := pos - 1
216		leftRoot := pos - 1 - ((1 << uint(h)) - 1)
217		half := 1 << uint(h-1)
218		if local < half {
219			out = append([][]byte{m.nodes[rightRoot]}, out...)
220			pos = leftRoot
221		} else {
222			out = append([][]byte{m.nodes[leftRoot]}, out...)
223			pos = rightRoot
224			local -= half
225		}
226		h--
227	}
228	return out
229}