mmr.gno
7.61 Kb · 229 lines
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/nym-moultest123/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/nym-moultest123/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/nym-moultest123/x/merkle/v0's Verify instead.
68//
69// Live demo: gno.land/r/nym-moultest123/x/provable/v0
70package mmr
71
72import (
73 "encoding/hex"
74 "errors"
75
76 "gno.land/p/nym-moultest123/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}
