merkle_test.gno
10.80 Kb · 298 lines
1package merkle
2
3import (
4 "crypto/sha256"
5 "encoding/hex"
6 "strconv"
7 "testing"
8)
9
10// leaves returns n deterministic leaves, "leaf-0" … "leaf-n-1". The golden
11// vectors below were produced from these exact inputs by tm2's own
12// merkle.SimpleProofsFromByteSlices, so a mismatch means this package has
13// diverged from Tendermint, not that the expectation is stale.
14func leaves(n int) [][]byte {
15 out := make([][]byte, n)
16 for i := 0; i < n; i++ {
17 out[i] = []byte("leaf-" + strconv.Itoa(i))
18 }
19 return out
20}
21
22var goldenRoots = map[int]string{
23 1: "305df59f9590c3c9ac63d2b2743c388e3792449078cebf7fb3dbe6471643b2b7",
24 2: "60a53eed0de87a90c8e59427c59c46253c33a76a09502a51801300927b7e6bdc",
25 3: "cf763a041c81ceef1578a6083f75c61bef2e0014f2a3e683a97fcfca5be7f19a",
26 4: "bdd1c5ff55b19cb6b0e7c761bf9a6ccaa27fbbfc07b74f1fabb6e911a0bd2ab3",
27 5: "00d21829a5503145348abcf712513eacf2a274211ad83e970202bb5b6d80b286",
28 7: "0b007fb915eb9b2a146f54b1c86ec53b664f8e455b7660b0b6ee13edc0d921c0",
29}
30
31// goldenAunts[n][i] is the comma-separated hex sibling list tm2 produces for
32// leaf i of an n-leaf tree.
33var goldenAunts = map[int][]string{
34 1: {""},
35 2: {
36 "3145c409f259b7c53e32036090ff76751025a2498ba9823ef718cac50b4e616f",
37 "305df59f9590c3c9ac63d2b2743c388e3792449078cebf7fb3dbe6471643b2b7",
38 },
39 3: {
40 "3145c409f259b7c53e32036090ff76751025a2498ba9823ef718cac50b4e616f,fca89f57c9f8c8eb4047a7ff9d333acf9e0f3384b20b255bceab0f216dcca267",
41 "305df59f9590c3c9ac63d2b2743c388e3792449078cebf7fb3dbe6471643b2b7,fca89f57c9f8c8eb4047a7ff9d333acf9e0f3384b20b255bceab0f216dcca267",
42 "60a53eed0de87a90c8e59427c59c46253c33a76a09502a51801300927b7e6bdc",
43 },
44 4: {
45 "3145c409f259b7c53e32036090ff76751025a2498ba9823ef718cac50b4e616f,bd45ff28796704d88bdac51b1df553fda59837b616d6d1cb2114dbc3b087ff69",
46 "305df59f9590c3c9ac63d2b2743c388e3792449078cebf7fb3dbe6471643b2b7,bd45ff28796704d88bdac51b1df553fda59837b616d6d1cb2114dbc3b087ff69",
47 "f76836325aec5699d8d71f8e42e9d47c5c29b08059ba296384f7ca40ad3a40ae,60a53eed0de87a90c8e59427c59c46253c33a76a09502a51801300927b7e6bdc",
48 "fca89f57c9f8c8eb4047a7ff9d333acf9e0f3384b20b255bceab0f216dcca267,60a53eed0de87a90c8e59427c59c46253c33a76a09502a51801300927b7e6bdc",
49 },
50 7: {
51 "3145c409f259b7c53e32036090ff76751025a2498ba9823ef718cac50b4e616f,bd45ff28796704d88bdac51b1df553fda59837b616d6d1cb2114dbc3b087ff69,8eae6bd3b3a07f1f75ee72a531629e6eb31e42e62f760e47de52a53c3641ef23",
52 "305df59f9590c3c9ac63d2b2743c388e3792449078cebf7fb3dbe6471643b2b7,bd45ff28796704d88bdac51b1df553fda59837b616d6d1cb2114dbc3b087ff69,8eae6bd3b3a07f1f75ee72a531629e6eb31e42e62f760e47de52a53c3641ef23",
53 "f76836325aec5699d8d71f8e42e9d47c5c29b08059ba296384f7ca40ad3a40ae,60a53eed0de87a90c8e59427c59c46253c33a76a09502a51801300927b7e6bdc,8eae6bd3b3a07f1f75ee72a531629e6eb31e42e62f760e47de52a53c3641ef23",
54 "fca89f57c9f8c8eb4047a7ff9d333acf9e0f3384b20b255bceab0f216dcca267,60a53eed0de87a90c8e59427c59c46253c33a76a09502a51801300927b7e6bdc,8eae6bd3b3a07f1f75ee72a531629e6eb31e42e62f760e47de52a53c3641ef23",
55 "8f1593cb92f429d9340b9bbc1f0bb122adf8026c42a4a42142e2168931727236,676f3782f5b3a5fb4370ed49572cedc523f4a66322269c85f2af0509d17b0a4d,bdd1c5ff55b19cb6b0e7c761bf9a6ccaa27fbbfc07b74f1fabb6e911a0bd2ab3",
56 "ea9fc1a1b6e191b460d0d6306e3e870c173f39330f13cda1b70cfc72bdc398ba,676f3782f5b3a5fb4370ed49572cedc523f4a66322269c85f2af0509d17b0a4d,bdd1c5ff55b19cb6b0e7c761bf9a6ccaa27fbbfc07b74f1fabb6e911a0bd2ab3",
57 "985bb5d36b927800876871da925a7e82abe83a9ddba5882920a007a55ea2b376,bdd1c5ff55b19cb6b0e7c761bf9a6ccaa27fbbfc07b74f1fabb6e911a0bd2ab3",
58 },
59}
60
61func TestRootMatchesTendermint(t *testing.T) {
62 for _, n := range []int{1, 2, 3, 4, 5, 7} {
63 got := New(leaves(n)).RootHex()
64 if got != goldenRoots[n] {
65 t.Errorf("n=%d: root = %s, tm2 says %s", n, got, goldenRoots[n])
66 }
67 }
68}
69
70func TestProofMatchesTendermint(t *testing.T) {
71 for n, want := range goldenAunts {
72 tree := New(leaves(n))
73 for i, w := range want {
74 p, err := tree.Proof(i)
75 if err != nil {
76 t.Fatalf("n=%d i=%d: Proof: %v", n, i, err)
77 }
78 if got := p.Hex(); got != w {
79 t.Errorf("n=%d i=%d:\n got %s\n want %s", n, i, got, w)
80 }
81 }
82 }
83}
84
85// Every leaf of every tree shape up to 33 must produce a proof the native
86// verifier accepts. This is the property that matters; the golden vectors only
87// pin the encoding.
88func TestEveryProofVerifies(t *testing.T) {
89 for n := 1; n <= 33; n++ {
90 ls := leaves(n)
91 tree := New(ls)
92 root := tree.Root()
93 for i := 0; i < n; i++ {
94 p, err := tree.Proof(i)
95 if err != nil {
96 t.Fatalf("n=%d i=%d: Proof: %v", n, i, err)
97 }
98 if !p.Verify(root, ls[i]) {
99 t.Errorf("n=%d i=%d: valid proof rejected", n, i)
100 }
101 }
102 }
103}
104
105func TestRejects(t *testing.T) {
106 ls := leaves(8)
107 tree := New(ls)
108 root := tree.Root()
109 p0, _ := tree.Proof(0)
110 p1, _ := tree.Proof(1)
111
112 tests := []struct {
113 name string
114 proof Proof
115 root []byte
116 leaf []byte
117 }{
118 {"forged leaf", p0, root, []byte("not-a-leaf")},
119 {"another real leaf at the wrong index", p0, root, ls[1]},
120 {"proof replayed at a different index", Proof{Index: 1, Total: p0.Total, Siblings: p0.Siblings}, root, ls[1]},
121 {"sibling list of another leaf", Proof{Index: 0, Total: 8, Siblings: p1.Siblings}, root, ls[0]},
122 {"wrong root", p0, LeafHash([]byte("nope")), ls[0]},
123 {"index beyond total", Proof{Index: 8, Total: 8, Siblings: p0.Siblings}, root, ls[0]},
124 {"negative index", Proof{Index: -1, Total: 8, Siblings: p0.Siblings}, root, ls[0]},
125 {"zero total", Proof{Index: 0, Total: 0, Siblings: p0.Siblings}, root, ls[0]},
126 {"truncated proof", Proof{Index: 0, Total: 8, Siblings: p0.Siblings[:1]}, root, ls[0]},
127 {"short root", p0, root[:31], ls[0]},
128 }
129 for _, tc := range tests {
130 if tc.proof.Verify(tc.root, tc.leaf) {
131 t.Errorf("%s: accepted, must be rejected", tc.name)
132 }
133 }
134}
135
136func TestMaxDepthCap(t *testing.T) {
137 sibs := make([][]byte, MaxDepth+1)
138 for i := range sibs {
139 sibs[i] = make([]byte, HashSize)
140 }
141 p := Proof{Index: 0, Total: 1 << 20, Siblings: sibs}
142 if p.Verify(make([]byte, HashSize), []byte("x")) {
143 t.Error("proof deeper than MaxDepth accepted")
144 }
145 if !VerifySorted(make([]byte, HashSize), make([]byte, HashSize), sibs[:MaxDepth]) == false {
146 t.Error("unreachable")
147 }
148 if VerifySorted(make([]byte, HashSize), make([]byte, HashSize), sibs) {
149 t.Error("sorted proof deeper than MaxDepth accepted")
150 }
151}
152
153func TestParseProofRoundTrip(t *testing.T) {
154 tree := New(leaves(7))
155 for i := 0; i < 7; i++ {
156 want, _ := tree.Proof(i)
157 got, err := ParseProof(i, 7, want.Hex())
158 if err != nil {
159 t.Fatalf("i=%d: ParseProof: %v", i, err)
160 }
161 if got.Hex() != want.Hex() || got.Index != want.Index || got.Total != want.Total {
162 t.Errorf("i=%d: round trip lost data", i)
163 }
164 if !got.Verify(tree.Root(), []byte("leaf-"+strconv.Itoa(i))) {
165 t.Errorf("i=%d: reparsed proof does not verify", i)
166 }
167 }
168}
169
170func TestParseProofErrors(t *testing.T) {
171 tests := []struct {
172 name string
173 in string
174 want error
175 }{
176 {"not hex", "zz", ErrBadHex},
177 {"wrong size", "abcd", ErrBadHashSize},
178 {"too deep", tooDeepHex(), ErrProofTooDeep},
179 }
180 for _, tc := range tests {
181 if _, err := ParseProof(0, 2, tc.in); err != tc.want {
182 t.Errorf("%s: err = %v, want %v", tc.name, err, tc.want)
183 }
184 }
185 // An empty sibling list is the one-leaf proof, not an error.
186 p, err := ParseProof(0, 1, " ")
187 if err != nil {
188 t.Fatalf("empty siblings: %v", err)
189 }
190 one := New(leaves(1))
191 if !p.Verify(one.Root(), []byte("leaf-0")) {
192 t.Error("one-leaf proof with no siblings rejected")
193 }
194}
195
196func tooDeepHex() string {
197 h := hex.EncodeToString(make([]byte, HashSize))
198 out := h
199 for i := 0; i < MaxDepth; i++ {
200 out += "," + h
201 }
202 return out
203}
204
205func TestTreeErrors(t *testing.T) {
206 if _, err := New(nil).Proof(0); err != ErrEmptyTree {
207 t.Errorf("empty tree: err = %v, want %v", err, ErrEmptyTree)
208 }
209 if New(nil).Root() != nil {
210 t.Error("empty tree root should be nil, like Tendermint")
211 }
212 tree := New(leaves(3))
213 for _, i := range []int{-1, 3, 99} {
214 if _, err := tree.Proof(i); err != ErrIndexRange {
215 t.Errorf("index %d: err = %v, want %v", i, err, ErrIndexRange)
216 }
217 }
218}
219
220// New must copy its input: a caller mutating the slice afterwards cannot be
221// allowed to change what the tree committed to.
222func TestNewCopiesLeaves(t *testing.T) {
223 ls := [][]byte{[]byte("a"), []byte("b")}
224 tree := New(ls)
225 before := tree.RootHex()
226 ls[0][0] = 'z'
227 if tree.RootHex() != before {
228 t.Error("mutating the caller's slice changed the committed root")
229 }
230}
231
232// The reason this package exists. In a scheme without domain separation an
233// INNER NODE hash is also a valid LEAF hash, so anyone who can choose a
234// 64-byte leaf preimage can prove membership of a leaf that was never in the
235// tree. This test performs that forgery against VerifySorted, then shows the
236// Tendermint scheme refuses the same move.
237func TestSecondPreimageForgery(t *testing.T) {
238 // A 4-leaf commutative tree, built the OpenZeppelin way.
239 h := make([][]byte, 4)
240 for i := range h {
241 s := sha256.Sum256([]byte("leaf-" + strconv.Itoa(i)))
242 h[i] = s[:]
243 }
244 n01 := hashSortedPair(h[0], h[1])
245 n23 := hashSortedPair(h[2], h[3])
246 root := hashSortedPair(n01, n23)
247
248 // Sanity: a real leaf really does verify.
249 if !VerifySorted(root, h[0], [][]byte{h[1], n23}) {
250 t.Fatal("honest sorted proof rejected")
251 }
252
253 // The forgery: present the inner node n01 as if it were a leaf hash. Its
254 // preimage is the 64 bytes sorted(h0, h1), so an application whose leaves
255 // can be 64 bytes long hands the attacker a membership proof for data that
256 // was never committed.
257 if !VerifySorted(root, n01, [][]byte{n23}) {
258 t.Fatal("expected the second-preimage forgery to succeed against VerifySorted")
259 }
260
261 // Same shape, Tendermint scheme. Leaves are tagged 0x00 and inner nodes
262 // 0x01, so no leaf preimage can ever hash to an inner node, and the proof
263 // is bound to an index besides.
264 tree := New(leaves(4))
265 inner := InnerHash(LeafHash(tree.leaves[0]), LeafHash(tree.leaves[1]))
266 forged := Proof{Index: 0, Total: 2, Siblings: [][]byte{InnerHash(LeafHash(tree.leaves[2]), LeafHash(tree.leaves[3]))}}
267 if forged.Verify(tree.Root(), inner) {
268 t.Error("domain separation failed: an inner node was accepted as a leaf")
269 }
270}
271
272func TestLeafAndInnerHashAreTagged(t *testing.T) {
273 leafOfEmpty := LeafHash(nil)
274 taggedLeaf := sha256.Sum256([]byte{0x00})
275 if hex.EncodeToString(leafOfEmpty) != hex.EncodeToString(taggedLeaf[:]) {
276 t.Error("LeafHash is not SHA256(0x00 || leaf)")
277 }
278 l := make([]byte, 32)
279 r := make([]byte, 32)
280 r[0] = 1
281 got := InnerHash(l, r)
282 want := sha256.Sum256(append(append([]byte{0x01}, l...), r...))
283 if hex.EncodeToString(got) != hex.EncodeToString(want[:]) {
284 t.Error("InnerHash is not SHA256(0x01 || left || right)")
285 }
286}
287
288func TestSplitPointMatchesTendermint(t *testing.T) {
289 // largest power of two strictly below length
290 tests := []struct{ in, want int }{
291 {2, 1}, {3, 2}, {4, 2}, {5, 4}, {7, 4}, {8, 4}, {9, 8}, {16, 8}, {17, 16},
292 }
293 for _, tc := range tests {
294 if got := splitPoint(tc.in); got != tc.want {
295 t.Errorf("splitPoint(%d) = %d, want %d", tc.in, got, tc.want)
296 }
297 }
298}
