mmr_test.gno
7.62 Kb · 257 lines
1package mmr
2
3import (
4 "strconv"
5 "testing"
6
7 "gno.land/p/moul/x/merkle/v0"
8)
9
10func leafAt(i int) []byte { return []byte("entry-" + strconv.Itoa(i)) }
11
12func build(n int) *MMR {
13 m := New()
14 for i := 0; i < n; i++ {
15 if got := m.Append(leafAt(i)); got != i {
16 panic("Append returned the wrong index")
17 }
18 }
19 return m
20}
21
22// The property that matters: for every log size up to 40, every leaf ever
23// appended has a proof that verifies against the root at that size.
24func TestEveryProofVerifies(t *testing.T) {
25 for n := 1; n <= 40; n++ {
26 m := build(n)
27 root := m.Root()
28 for i := 0; i < n; i++ {
29 p, err := m.Proof(i)
30 if err != nil {
31 t.Fatalf("n=%d i=%d: Proof: %v", n, i, err)
32 }
33 if !Verify(root, leafAt(i), p) {
34 t.Errorf("n=%d i=%d: valid proof rejected", n, i)
35 }
36 }
37 }
38}
39
40// A one-leaf MMR is a single height-0 mountain, so its root is just the
41// tagged leaf hash and the proof is empty.
42func TestSingleLeaf(t *testing.T) {
43 m := build(1)
44 if string(m.Root()) != string(merkle.LeafHash(leafAt(0))) {
45 t.Error("one-leaf root is not the leaf hash")
46 }
47 p, err := m.Proof(0)
48 if err != nil {
49 t.Fatal(err)
50 }
51 if len(p.Path) != 0 || len(p.Before) != 0 || len(p.After) != 0 {
52 t.Error("one-leaf proof should be empty")
53 }
54}
55
56// The Tendermint simple tree and a right-bagged MMR are the SAME tree, at
57// every size and not only at powers of two. Tendermint splits an n-leaf tree
58// at the largest power of two below n: that left half is exactly the first
59// mountain, and the right half recurses into the remaining set bits, which is
60// exactly the bagging. So an MMR is a drop-in incremental builder for
61// Tendermint roots: append in O(log n) on chain, hand out a root any
62// Tendermint verifier accepts.
63func TestRootMatchesTendermintTreeAtEverySize(t *testing.T) {
64 for n := 1; n <= 40; n++ {
65 ls := make([][]byte, n)
66 for i := range ls {
67 ls[i] = leafAt(i)
68 }
69 if got, want := build(n).RootHex(), merkle.New(ls).RootHex(); got != want {
70 t.Errorf("n=%d: MMR root %s, Tendermint tree root %s", n, got, want)
71 }
72 }
73}
74
75// The consequence of the equality above: a proof produced by the fixed-list
76// Tendermint tree verifies against the root an MMR maintained incrementally,
77// and both packages agree leaf by leaf.
78func TestMerkleProofVerifiesAgainstMMRRoot(t *testing.T) {
79 for _, n := range []int{1, 2, 3, 5, 7, 11, 16, 23} {
80 ls := make([][]byte, n)
81 for i := range ls {
82 ls[i] = leafAt(i)
83 }
84 m := build(n)
85 tree := merkle.New(ls)
86 for i := 0; i < n; i++ {
87 tp, err := tree.Proof(i)
88 if err != nil {
89 t.Fatalf("n=%d i=%d: %v", n, i, err)
90 }
91 if !tp.Verify(m.Root(), leafAt(i)) {
92 t.Errorf("n=%d i=%d: Tendermint proof rejected by the MMR root", n, i)
93 }
94 mp, err := m.Proof(i)
95 if err != nil {
96 t.Fatalf("n=%d i=%d: %v", n, i, err)
97 }
98 if !Verify(tree.Root(), leafAt(i), mp) {
99 t.Errorf("n=%d i=%d: MMR proof rejected by the tree root", n, i)
100 }
101 }
102 }
103}
104
105func TestPeakStructure(t *testing.T) {
106 tests := []struct {
107 leaves int
108 want []int
109 }{
110 {1, []int{0}},
111 {2, []int{1}},
112 {3, []int{1, 0}},
113 {4, []int{2}},
114 {7, []int{2, 1, 0}},
115 {11, []int{3, 1, 0}},
116 {16, []int{4}},
117 }
118 for _, tc := range tests {
119 if got := len(peakHeights(tc.leaves)); got != len(tc.want) {
120 t.Errorf("n=%d: %d peaks, want %d", tc.leaves, got, len(tc.want))
121 continue
122 }
123 for i, h := range peakHeights(tc.leaves) {
124 if h != tc.want[i] {
125 t.Errorf("n=%d: peak %d height %d, want %d", tc.leaves, i, h, tc.want[i])
126 }
127 }
128 if got := len(build(tc.leaves).peaks); got != len(tc.want) {
129 t.Errorf("n=%d: MMR built %d peaks, want %d", tc.leaves, got, len(tc.want))
130 }
131 }
132}
133
134func TestRejects(t *testing.T) {
135 m := build(11)
136 root := m.Root()
137 p3, _ := m.Proof(3)
138 p7, _ := m.Proof(7)
139
140 tests := []struct {
141 name string
142 root []byte
143 leaf []byte
144 proof Proof
145 }{
146 {"forged leaf", root, []byte("never-appended"), p3},
147 {"another real leaf", root, leafAt(4), p3},
148 {"proof replayed at another index", root, leafAt(3), Proof{Index: 4, Total: p3.Total, Path: p3.Path, Before: p3.Before, After: p3.After}},
149 {"another leaf's proof", root, leafAt(3), p7},
150 {"wrong total", root, leafAt(3), Proof{Index: 3, Total: 10, Path: p3.Path, Before: p3.Before, After: p3.After}},
151 {"padded path", root, leafAt(3), Proof{Index: 3, Total: 11, Path: append(append([][]byte{}, p3.Path...), make([]byte, HashSize)), Before: p3.Before, After: p3.After}},
152 {"truncated path", root, leafAt(3), Proof{Index: 3, Total: 11, Path: p3.Path[:len(p3.Path)-1], Before: p3.Before, After: p3.After}},
153 {"peaks swapped", root, leafAt(3), Proof{Index: 3, Total: 11, Path: p3.Path, Before: p3.After, After: p3.Before}},
154 {"index beyond total", root, leafAt(3), Proof{Index: 11, Total: 11, Path: p3.Path, Before: p3.Before, After: p3.After}},
155 {"negative index", root, leafAt(3), Proof{Index: -1, Total: 11, Path: p3.Path, Before: p3.Before, After: p3.After}},
156 {"zero total", root, leafAt(3), Proof{Index: 0, Total: 0}},
157 {"short root", root[:31], leafAt(3), p3},
158 {"short hash in path", root, leafAt(3), Proof{Index: 3, Total: 11, Path: [][]byte{{1, 2, 3}, p3.Path[1]}, Before: p3.Before, After: p3.After}},
159 }
160 for _, tc := range tests {
161 if Verify(tc.root, tc.leaf, tc.proof) {
162 t.Errorf("%s: accepted, must be rejected", tc.name)
163 }
164 }
165}
166
167// A proof is issued against one size. Appending moves the root, and the old
168// proof must stop verifying against the new one rather than quietly pass.
169func TestProofIsBoundToItsSize(t *testing.T) {
170 m := build(5)
171 old, _ := m.Proof(2)
172 oldRoot := m.Root()
173 if !Verify(oldRoot, leafAt(2), old) {
174 t.Fatal("proof does not verify against its own root")
175 }
176 m.Append(leafAt(5))
177 if Verify(m.Root(), leafAt(2), old) {
178 t.Error("a stale proof verified against the new root")
179 }
180 fresh, _ := m.Proof(2)
181 if !Verify(m.Root(), leafAt(2), fresh) {
182 t.Error("a reissued proof does not verify")
183 }
184 if !Verify(oldRoot, leafAt(2), old) {
185 t.Error("the old proof stopped verifying against the old root")
186 }
187}
188
189func TestEmptyAndRange(t *testing.T) {
190 m := New()
191 if m.Size() != 0 || m.Root() != nil || m.Nodes() != 0 {
192 t.Error("a fresh MMR is not empty")
193 }
194 if _, err := m.Proof(0); err != ErrEmpty {
195 t.Errorf("empty Proof: err = %v, want %v", err, ErrEmpty)
196 }
197 m.Append(leafAt(0))
198 for _, i := range []int{-1, 1, 99} {
199 if _, err := m.Proof(i); err != ErrIndexRange {
200 t.Errorf("index %d: err = %v, want %v", i, err, ErrIndexRange)
201 }
202 }
203}
204
205// Storage claim from the package doc: 2n - popcount(n) stored hashes.
206func TestNodeCount(t *testing.T) {
207 for n := 1; n <= 40; n++ {
208 want := 2*n - popcount(n)
209 if got := build(n).Nodes(); got != want {
210 t.Errorf("n=%d: %d nodes, want 2n-popcount(n) = %d", n, got, want)
211 }
212 }
213}
214
215func popcount(n int) int {
216 c := 0
217 for n != 0 {
218 c += n & 1
219 n >>= 1
220 }
221 return c
222}
223
224func TestParseProofRoundTrip(t *testing.T) {
225 m := build(11)
226 for i := 0; i < 11; i++ {
227 want, _ := m.Proof(i)
228 path, before, after := want.Hex()
229 got, err := ParseProof(i, 11, path, before, after)
230 if err != nil {
231 t.Fatalf("i=%d: ParseProof: %v", i, err)
232 }
233 if !Verify(m.Root(), leafAt(i), got) {
234 t.Errorf("i=%d: reparsed proof does not verify", i)
235 }
236 }
237}
238
239func TestParseProofErrors(t *testing.T) {
240 if _, err := ParseProof(0, 2, "zz", "", ""); err != ErrBadHex {
241 t.Errorf("bad hex: err = %v", err)
242 }
243 if _, err := ParseProof(0, 2, "abcd", "", ""); err != ErrBadSize {
244 t.Errorf("bad size: err = %v", err)
245 }
246}
247
248// PeakHashes is the whole verifier-side state, and it must stay logarithmic.
249func TestPeakCountIsLogarithmic(t *testing.T) {
250 m := build(1023)
251 if got := len(m.PeakHashes()); got != 10 {
252 t.Errorf("1023 leaves: %d peaks, want 10", got)
253 }
254 if got := len(build(1024).PeakHashes()); got != 1 {
255 t.Errorf("1024 leaves: %d peaks, want 1", got)
256 }
257}
