go-merkletree-iden3/merkletree_test.go
merkletree_test.goRaw
1package merkletree
2
3import (
4 "bytes"
5 "encoding/hex"
6 "fmt"
7 "math/big"
8 "testing"
9
10 "github.com/iden3/go-iden3-crypto/constants"
11 cryptoUtils "github.com/iden3/go-iden3-crypto/utils"
12 "github.com/iden3/go-merkletree/db/memory"
13 "github.com/stretchr/testify/assert"
14 "github.com/stretchr/testify/require"
15)
16
17var debug = false
18
19type Fatalable interface {
20 Fatal(args ...interface{})
21}
22
23func newTestingMerkle(f Fatalable, numLevels int) *MerkleTree {
24 mt, err := NewMerkleTree(memory.NewMemoryStorage(), numLevels)
25 if err != nil {
26 f.Fatal(err)
27 return nil
28 }
29 return mt
30}
31
32func TestHashParsers(t *testing.T) {
33 h0 := NewHashFromBigInt(big.NewInt(0))
34 assert.Equal(t, "0", h0.String())
35 h1 := NewHashFromBigInt(big.NewInt(1))
36 assert.Equal(t, "1", h1.String())
37 h10 := NewHashFromBigInt(big.NewInt(10))
38 assert.Equal(t, "10", h10.String())
39
40 h7l := NewHashFromBigInt(big.NewInt(1234567))
41 assert.Equal(t, "1234567", h7l.String())
42 h8l := NewHashFromBigInt(big.NewInt(12345678))
43 assert.Equal(t, "12345678...", h8l.String())
44
45 b, ok := new(big.Int).SetString("4932297968297298434239270129193057052722409868268166443802652458940273154854", 10)
46 assert.True(t, ok)
47 h := NewHashFromBigInt(b)
48 assert.Equal(t, "4932297968297298434239270129193057052722409868268166443802652458940273154854", h.BigInt().String())
49 assert.Equal(t, "49322979...", h.String())
50 assert.Equal(t, "265baaf161e875c372d08e50f52abddc01d32efc93e90290bb8b3d9ceb94e70a", h.Hex())
51
52 b1, err := NewBigIntFromHashBytes(b.Bytes())
53 assert.Nil(t, err)
54 assert.Equal(t, new(big.Int).SetBytes(b.Bytes()).String(), b1.String())
55
56 b2, err := NewHashFromBytes(b.Bytes())
57 assert.Nil(t, err)
58 assert.Equal(t, b.String(), b2.BigInt().String())
59
60 h2, err := NewHashFromHex(h.Hex())
61 assert.Nil(t, err)
62 assert.Equal(t, h, h2)
63 _, err = NewHashFromHex("0x12")
64 assert.NotNil(t, err)
65
66 // check limits
67 a := new(big.Int).Sub(constants.Q, big.NewInt(1))
68 testHashParsers(t, a)
69 a = big.NewInt(int64(1))
70 testHashParsers(t, a)
71}
72
73func testHashParsers(t *testing.T, a *big.Int) {
74 require.True(t, cryptoUtils.CheckBigIntInField(a))
75 h := NewHashFromBigInt(a)
76 assert.Equal(t, a, h.BigInt())
77 hFromBytes, err := NewHashFromBytes(h.Bytes())
78 assert.Nil(t, err)
79 assert.Equal(t, h, hFromBytes)
80 assert.Equal(t, a, hFromBytes.BigInt())
81 assert.Equal(t, a.String(), hFromBytes.BigInt().String())
82 hFromHex, err := NewHashFromHex(h.Hex())
83 assert.Nil(t, err)
84 assert.Equal(t, h, hFromHex)
85
86 aBIFromHBytes, err := NewBigIntFromHashBytes(h.Bytes())
87 assert.Nil(t, err)
88 assert.Equal(t, a, aBIFromHBytes)
89 assert.Equal(t, new(big.Int).SetBytes(a.Bytes()).String(), aBIFromHBytes.String())
90}
91
92func TestNewTree(t *testing.T) {
93 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 10)
94 assert.Nil(t, err)
95 assert.Equal(t, "0", mt.Root().String())
96
97 // test vectors generated using https://github.com/iden3/circomlib smt.js
98 err = mt.Add(big.NewInt(1), big.NewInt(2))
99 assert.Nil(t, err)
100 assert.Equal(t, "6449712043256457369579901840927028403950625973089336675272087704159094984964", mt.Root().BigInt().String())
101
102 err = mt.Add(big.NewInt(33), big.NewInt(44))
103 assert.Nil(t, err)
104 assert.Equal(t, "11404118908468506234838877883514126008995570353394659302846433035311596046064", mt.Root().BigInt().String())
105
106 err = mt.Add(big.NewInt(1234), big.NewInt(9876))
107 assert.Nil(t, err)
108 assert.Equal(t, "12841932325181810040554102151615400973767747666110051836366805309524360490677", mt.Root().BigInt().String())
109
110 proof, v, err := mt.GenerateProof(big.NewInt(33), nil)
111 assert.Nil(t, err)
112 assert.Equal(t, big.NewInt(44), v)
113
114 assert.True(t, VerifyProof(mt.Root(), proof, big.NewInt(33), big.NewInt(44)))
115 assert.True(t, !VerifyProof(mt.Root(), proof, big.NewInt(33), big.NewInt(45)))
116}
117
118func TestAddDifferentOrder(t *testing.T) {
119 mt1 := newTestingMerkle(t, 140)
120 defer mt1.db.Close()
121 for i := 0; i < 16; i++ {
122 k := big.NewInt(int64(i))
123 v := big.NewInt(0)
124 if err := mt1.Add(k, v); err != nil {
125 t.Fatal(err)
126 }
127 }
128
129 mt2 := newTestingMerkle(t, 140)
130 defer mt2.db.Close()
131 for i := 16 - 1; i >= 0; i-- {
132 k := big.NewInt(int64(i))
133 v := big.NewInt(0)
134 if err := mt2.Add(k, v); err != nil {
135 t.Fatal(err)
136 }
137 }
138
139 assert.Equal(t, mt1.Root().Hex(), mt2.Root().Hex())
140 assert.Equal(t, "268e25964aa9d6ba42d66ae9eb44b5528540acb19a3644d1367d8c6f7cb23006", mt1.Root().Hex())
141}
142
143func TestAddRepeatedIndex(t *testing.T) {
144 mt := newTestingMerkle(t, 140)
145 defer mt.db.Close()
146 k := big.NewInt(int64(3))
147 v := big.NewInt(int64(12))
148 if err := mt.Add(k, v); err != nil {
149 t.Fatal(err)
150 }
151 err := mt.Add(k, v)
152 assert.NotNil(t, err)
153 assert.Equal(t, err, ErrEntryIndexAlreadyExists)
154}
155
156func TestGet(t *testing.T) {
157 mt := newTestingMerkle(t, 140)
158 defer mt.db.Close()
159
160 for i := 0; i < 16; i++ {
161 k := big.NewInt(int64(i))
162 v := big.NewInt(int64(i * 2))
163 if err := mt.Add(k, v); err != nil {
164 t.Fatal(err)
165 }
166 }
167 k, v, _, err := mt.Get(big.NewInt(10))
168 assert.Nil(t, err)
169 assert.Equal(t, big.NewInt(10), k)
170 assert.Equal(t, big.NewInt(20), v)
171
172 k, v, _, err = mt.Get(big.NewInt(15))
173 assert.Nil(t, err)
174 assert.Equal(t, big.NewInt(15), k)
175 assert.Equal(t, big.NewInt(30), v)
176
177 k, v, _, err = mt.Get(big.NewInt(16))
178 assert.NotNil(t, err)
179 assert.Equal(t, ErrKeyNotFound, err)
180 assert.Equal(t, "0", k.String())
181 assert.Equal(t, "0", v.String())
182}
183
184func TestUpdate(t *testing.T) {
185 mt := newTestingMerkle(t, 140)
186 defer mt.db.Close()
187
188 for i := 0; i < 16; i++ {
189 k := big.NewInt(int64(i))
190 v := big.NewInt(int64(i * 2))
191 if err := mt.Add(k, v); err != nil {
192 t.Fatal(err)
193 }
194 }
195 _, v, _, err := mt.Get(big.NewInt(10))
196 assert.Nil(t, err)
197 assert.Equal(t, big.NewInt(20), v)
198
199 _, err = mt.Update(big.NewInt(10), big.NewInt(1024))
200 assert.Nil(t, err)
201 _, v, _, err = mt.Get(big.NewInt(10))
202 assert.Nil(t, err)
203 assert.Equal(t, big.NewInt(1024), v)
204
205 _, err = mt.Update(big.NewInt(1000), big.NewInt(1024))
206 assert.Equal(t, ErrKeyNotFound, err)
207}
208
209func TestUpdate2(t *testing.T) {
210 mt1 := newTestingMerkle(t, 140)
211 defer mt1.db.Close()
212 mt2 := newTestingMerkle(t, 140)
213 defer mt2.db.Close()
214
215 err := mt1.Add(big.NewInt(1), big.NewInt(119))
216 assert.Nil(t, err)
217 err = mt1.Add(big.NewInt(2), big.NewInt(229))
218 assert.Nil(t, err)
219 err = mt1.Add(big.NewInt(9876), big.NewInt(6789))
220 assert.Nil(t, err)
221
222 err = mt2.Add(big.NewInt(1), big.NewInt(11))
223 assert.Nil(t, err)
224 err = mt2.Add(big.NewInt(2), big.NewInt(22))
225 assert.Nil(t, err)
226 err = mt2.Add(big.NewInt(9876), big.NewInt(10))
227 assert.Nil(t, err)
228
229 _, err = mt1.Update(big.NewInt(1), big.NewInt(11))
230 assert.Nil(t, err)
231 _, err = mt1.Update(big.NewInt(2), big.NewInt(22))
232 assert.Nil(t, err)
233 _, err = mt2.Update(big.NewInt(9876), big.NewInt(6789))
234 assert.Nil(t, err)
235
236 assert.Equal(t, mt1.Root(), mt2.Root())
237}
238
239func TestGenerateAndVerifyProof128(t *testing.T) {
240 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 140)
241 require.Nil(t, err)
242 defer mt.db.Close()
243
244 for i := 0; i < 128; i++ {
245 k := big.NewInt(int64(i))
246 v := big.NewInt(0)
247 if err := mt.Add(k, v); err != nil {
248 t.Fatal(err)
249 }
250 }
251 proof, v, err := mt.GenerateProof(big.NewInt(42), nil)
252 assert.Nil(t, err)
253 assert.Equal(t, "0", v.String())
254 assert.True(t, VerifyProof(mt.Root(), proof, big.NewInt(42), big.NewInt(0)))
255}
256
257func TestTreeLimit(t *testing.T) {
258 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 5)
259 require.Nil(t, err)
260 defer mt.db.Close()
261
262 for i := 0; i < 16; i++ {
263 err = mt.Add(big.NewInt(int64(i)), big.NewInt(int64(i)))
264 assert.Nil(t, err)
265 }
266
267 // here the tree is full, should not allow to add more data as reaches the maximum number of levels
268 err = mt.Add(big.NewInt(int64(16)), big.NewInt(int64(16)))
269 assert.NotNil(t, err)
270 assert.Equal(t, ErrReachedMaxLevel, err)
271}
272
273func TestSiblingsFromProof(t *testing.T) {
274 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 140)
275 require.Nil(t, err)
276 defer mt.db.Close()
277
278 for i := 0; i < 64; i++ {
279 k := big.NewInt(int64(i))
280 v := big.NewInt(0)
281 if err := mt.Add(k, v); err != nil {
282 t.Fatal(err)
283 }
284 }
285
286 proof, _, err := mt.GenerateProof(big.NewInt(4), nil)
287 if err != nil {
288 t.Fatal(err)
289 }
290
291 siblings := SiblingsFromProof(proof)
292 assert.Equal(t, 6, len(siblings))
293 assert.Equal(t, "5b478bdd58595ead03ebf494a74014cbb576ba0d9456aa0916885b9eefae592f", siblings[0].Hex())
294 assert.Equal(t, "c1e8ab120a4e475ea1bf00633228bfb9d248f7ddec2aa6367f98d0defb9fb22e", siblings[1].Hex())
295 assert.Equal(t, "f4dafd8ac2b9165adc3f6d125af67d5a4d8a7a263dcc90a373d0338929e16e0c", siblings[2].Hex())
296 assert.Equal(t, "a94aa346bd85f96aba2e85b67920e44fe6ed767b0e13bea602784e0b8b897515", siblings[3].Hex())
297 assert.Equal(t, "54791d7514030ded79301dbf221f5bf186facbc5800912411852fdc101b7151d", siblings[4].Hex())
298 assert.Equal(t, "435d28bc0511f8feb93b5f1649a049b460947702ce0baaefcf596175370fe01e", siblings[5].Hex())
299}
300
301func TestVerifyProofCases(t *testing.T) {
302 mt := newTestingMerkle(t, 140)
303 defer mt.DB().Close()
304
305 for i := 0; i < 8; i++ {
306 if err := mt.Add(big.NewInt(int64(i)), big.NewInt(0)); err != nil {
307 t.Fatal(err)
308 }
309 }
310
311 // Existence proof
312
313 proof, _, err := mt.GenerateProof(big.NewInt(4), nil)
314 if err != nil {
315 t.Fatal(err)
316 }
317 assert.Equal(t, proof.Existence, true)
318 assert.True(t, VerifyProof(mt.Root(), proof, big.NewInt(4), big.NewInt(0)))
319 assert.Equal(t, "0003000000000000000000000000000000000000000000000000000000000007a6d6b46fefe213a6b579844a1bb7ab5c2db4a13f8662d9c5e729c36728f42730211ddfcc8d30ebd157d1d6912769b8e4abdca41e5dc2b57b026a361c091a8c14c748530e61bf8ea80c987657c3d24b134ece1ef8e2d4bd3f74437bf4392a6b1e", hex.EncodeToString(proof.Bytes()))
320
321 for i := 8; i < 32; i++ {
322 proof, _, err = mt.GenerateProof(big.NewInt(int64(i)), nil)
323 assert.Nil(t, err)
324 if debug {
325 fmt.Println(i, proof)
326 }
327 }
328 // Non-existence proof, empty aux
329 proof, _, err = mt.GenerateProof(big.NewInt(12), nil)
330 if err != nil {
331 t.Fatal(err)
332 }
333 assert.Equal(t, proof.Existence, false)
334 // assert.True(t, proof.nodeAux == nil)
335 assert.True(t, VerifyProof(mt.Root(), proof, big.NewInt(12), big.NewInt(0)))
336 assert.Equal(t, "0303000000000000000000000000000000000000000000000000000000000007a6d6b46fefe213a6b579844a1bb7ab5c2db4a13f8662d9c5e729c36728f42730211ddfcc8d30ebd157d1d6912769b8e4abdca41e5dc2b57b026a361c091a8c14c748530e61bf8ea80c987657c3d24b134ece1ef8e2d4bd3f74437bf4392a6b1e04000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", hex.EncodeToString(proof.Bytes()))
337
338 // Non-existence proof, diff. node aux
339 proof, _, err = mt.GenerateProof(big.NewInt(10), nil)
340 if err != nil {
341 t.Fatal(err)
342 }
343 assert.Equal(t, proof.Existence, false)
344 assert.True(t, proof.NodeAux != nil)
345 assert.True(t, VerifyProof(mt.Root(), proof, big.NewInt(10), big.NewInt(0)))
346 assert.Equal(t, "0303000000000000000000000000000000000000000000000000000000000007a6d6b46fefe213a6b579844a1bb7ab5c2db4a13f8662d9c5e729c36728f42730e667e2ca15909c4a23beff18e3cc74348fbd3c1a4c765a5bbbca126c9607a42b77e008a73926f1280f8531b139dc1cacf8d83fcec31d405f5c51b7cbddfe152902000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", hex.EncodeToString(proof.Bytes()))
347}
348
349func TestVerifyProofFalse(t *testing.T) {
350 mt := newTestingMerkle(t, 140)
351 defer mt.DB().Close()
352
353 for i := 0; i < 8; i++ {
354 if err := mt.Add(big.NewInt(int64(i)), big.NewInt(0)); err != nil {
355 t.Fatal(err)
356 }
357 }
358
359 // Invalid existence proof (node used for verification doesn't
360 // correspond to node in the proof)
361 proof, _, err := mt.GenerateProof(big.NewInt(int64(4)), nil)
362 if err != nil {
363 t.Fatal(err)
364 }
365 assert.Equal(t, proof.Existence, true)
366 assert.True(t, !VerifyProof(mt.Root(), proof, big.NewInt(int64(5)), big.NewInt(int64(5))))
367
368 // Invalid non-existence proof (Non-existence proof, diff. node aux)
369 proof, _, err = mt.GenerateProof(big.NewInt(int64(4)), nil)
370 if err != nil {
371 t.Fatal(err)
372 }
373 assert.Equal(t, proof.Existence, true)
374 // Now we change the proof from existence to non-existence, and add e's
375 // data as auxiliary node.
376 proof.Existence = false
377 proof.NodeAux = &NodeAux{Key: NewHashFromBigInt(big.NewInt(int64(4))), Value: NewHashFromBigInt(big.NewInt(4))}
378 assert.True(t, !VerifyProof(mt.Root(), proof, big.NewInt(int64(4)), big.NewInt(0)))
379}
380
381func TestGraphViz(t *testing.T) {
382 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 10)
383 assert.Nil(t, err)
384
385 _ = mt.Add(big.NewInt(1), big.NewInt(0))
386 _ = mt.Add(big.NewInt(2), big.NewInt(0))
387 _ = mt.Add(big.NewInt(3), big.NewInt(0))
388 _ = mt.Add(big.NewInt(4), big.NewInt(0))
389 _ = mt.Add(big.NewInt(5), big.NewInt(0))
390 _ = mt.Add(big.NewInt(100), big.NewInt(0))
391
392 // mt.PrintGraphViz(nil)
393
394 expected := `digraph hierarchy {
395node [fontname=Monospace,fontsize=10,shape=box]
396"16053348..." -> {"19137630..." "14119616..."}
397"19137630..." -> {"19543983..." "19746229..."}
398"19543983..." -> {"empty0" "65773153..."}
399"empty0" [style=dashed,label=0];
400"65773153..." -> {"73498412..." "empty1"}
401"empty1" [style=dashed,label=0];
402"73498412..." -> {"53169236..." "empty2"}
403"empty2" [style=dashed,label=0];
404"53169236..." -> {"73522717..." "34811870..."}
405"73522717..." [style=filled];
406"34811870..." [style=filled];
407"19746229..." [style=filled];
408"14119616..." -> {"19419204..." "15569531..."}
409"19419204..." -> {"78154875..." "34589916..."}
410"78154875..." [style=filled];
411"34589916..." [style=filled];
412"15569531..." [style=filled];
413}
414`
415 w := bytes.NewBufferString("")
416 err = mt.GraphViz(w, nil)
417 assert.Nil(t, err)
418 assert.Equal(t, []byte(expected), w.Bytes())
419}
420
421func TestDelete(t *testing.T) {
422 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 10)
423 assert.Nil(t, err)
424 assert.Equal(t, "0", mt.Root().String())
425
426 // test vectors generated using https://github.com/iden3/circomlib smt.js
427 err = mt.Add(big.NewInt(1), big.NewInt(2))
428 assert.Nil(t, err)
429 assert.Equal(t, "6449712043256457369579901840927028403950625973089336675272087704159094984964", mt.Root().BigInt().String())
430
431 err = mt.Add(big.NewInt(33), big.NewInt(44))
432 assert.Nil(t, err)
433 assert.Equal(t, "11404118908468506234838877883514126008995570353394659302846433035311596046064", mt.Root().BigInt().String())
434
435 err = mt.Add(big.NewInt(1234), big.NewInt(9876))
436 assert.Nil(t, err)
437 assert.Equal(t, "12841932325181810040554102151615400973767747666110051836366805309524360490677", mt.Root().BigInt().String())
438
439 // mt.PrintGraphViz(nil)
440
441 err = mt.Delete(big.NewInt(33))
442 // mt.PrintGraphViz(nil)
443 assert.Nil(t, err)
444 assert.Equal(t, "16195585003843604118922861401064871511855368913846540536604351220077317790615", mt.Root().BigInt().String())
445
446 err = mt.Delete(big.NewInt(1234))
447 assert.Nil(t, err)
448 err = mt.Delete(big.NewInt(1))
449 assert.Nil(t, err)
450 assert.Equal(t, "0", mt.Root().String())
451}
452
453func TestDelete2(t *testing.T) {
454 mt := newTestingMerkle(t, 140)
455 defer mt.db.Close()
456 for i := 0; i < 8; i++ {
457 k := big.NewInt(int64(i))
458 v := big.NewInt(0)
459 if err := mt.Add(k, v); err != nil {
460 t.Fatal(err)
461 }
462 }
463
464 expectedRoot := mt.Root()
465
466 k := big.NewInt(8)
467 v := big.NewInt(0)
468 err := mt.Add(k, v)
469 require.Nil(t, err)
470
471 err = mt.Delete(big.NewInt(8))
472 assert.Nil(t, err)
473 assert.Equal(t, expectedRoot, mt.Root())
474
475 mt2 := newTestingMerkle(t, 140)
476 defer mt2.db.Close()
477 for i := 0; i < 8; i++ {
478 k := big.NewInt(int64(i))
479 v := big.NewInt(0)
480 if err := mt2.Add(k, v); err != nil {
481 t.Fatal(err)
482 }
483 }
484 assert.Equal(t, mt2.Root(), mt.Root())
485}
486
487func TestDelete3(t *testing.T) {
488 mt := newTestingMerkle(t, 140)
489 defer mt.db.Close()
490
491 err := mt.Add(big.NewInt(1), big.NewInt(1))
492 assert.Nil(t, err)
493
494 err = mt.Add(big.NewInt(2), big.NewInt(2))
495 assert.Nil(t, err)
496
497 assert.Equal(t, "6701939280963330813043570145125351311131831356446202146710280245621673558344", mt.Root().BigInt().String())
498 err = mt.Delete(big.NewInt(1))
499 assert.Nil(t, err)
500 assert.Equal(t, "10304354743004778619823249005484018655542356856535590307973732141291410579841", mt.Root().BigInt().String())
501
502 mt2 := newTestingMerkle(t, 140)
503 defer mt2.db.Close()
504 err = mt2.Add(big.NewInt(2), big.NewInt(2))
505 assert.Nil(t, err)
506 assert.Equal(t, mt2.Root(), mt.Root())
507}
508
509func TestDelete4(t *testing.T) {
510 mt := newTestingMerkle(t, 140)
511 defer mt.db.Close()
512
513 err := mt.Add(big.NewInt(1), big.NewInt(1))
514 assert.Nil(t, err)
515
516 err = mt.Add(big.NewInt(2), big.NewInt(2))
517 assert.Nil(t, err)
518
519 err = mt.Add(big.NewInt(3), big.NewInt(3))
520 assert.Nil(t, err)
521
522 assert.Equal(t, "6989694633650442615746486460134957295274675622748484439660143938730686550248", mt.Root().BigInt().String())
523 err = mt.Delete(big.NewInt(1))
524 assert.Nil(t, err)
525 assert.Equal(t, "1192610901536912535888866440319084773171371421781091005185759505381507049136", mt.Root().BigInt().String())
526
527 mt2 := newTestingMerkle(t, 140)
528 defer mt2.db.Close()
529 err = mt2.Add(big.NewInt(2), big.NewInt(2))
530 assert.Nil(t, err)
531 err = mt2.Add(big.NewInt(3), big.NewInt(3))
532 assert.Nil(t, err)
533 assert.Equal(t, mt2.Root(), mt.Root())
534}
535
536func TestDelete5(t *testing.T) {
537 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 10)
538 assert.Nil(t, err)
539
540 err = mt.Add(big.NewInt(1), big.NewInt(2))
541 assert.Nil(t, err)
542 err = mt.Add(big.NewInt(33), big.NewInt(44))
543 assert.Nil(t, err)
544 assert.Equal(t, "11404118908468506234838877883514126008995570353394659302846433035311596046064", mt.Root().BigInt().String())
545
546 err = mt.Delete(big.NewInt(1))
547 assert.Nil(t, err)
548 assert.Equal(t, "12802904154263054831102426711825443668153853847661287611768065280921698471037", mt.Root().BigInt().String())
549
550 mt2 := newTestingMerkle(t, 140)
551 defer mt2.db.Close()
552 err = mt2.Add(big.NewInt(33), big.NewInt(44))
553 assert.Nil(t, err)
554 assert.Equal(t, mt2.Root(), mt.Root())
555}
556
557func TestDeleteNonExistingKeys(t *testing.T) {
558 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 10)
559 assert.Nil(t, err)
560
561 err = mt.Add(big.NewInt(1), big.NewInt(2))
562 assert.Nil(t, err)
563 err = mt.Add(big.NewInt(33), big.NewInt(44))
564 assert.Nil(t, err)
565
566 err = mt.Delete(big.NewInt(33))
567 assert.Nil(t, err)
568 err = mt.Delete(big.NewInt(33))
569 assert.Equal(t, ErrKeyNotFound, err)
570
571 err = mt.Delete(big.NewInt(1))
572 assert.Nil(t, err)
573
574 assert.Equal(t, "0", mt.Root().String())
575
576 err = mt.Delete(big.NewInt(33))
577 assert.Equal(t, ErrKeyNotFound, err)
578}
579
580func TestDumpLeafsImportLeafs(t *testing.T) {
581 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 140)
582 require.Nil(t, err)
583 defer mt.db.Close()
584
585 q1 := new(big.Int).Sub(constants.Q, big.NewInt(1))
586 for i := 0; i < 10; i++ {
587 // use numbers near under Q
588 k := new(big.Int).Sub(q1, big.NewInt(int64(i)))
589 v := big.NewInt(0)
590 err = mt.Add(k, v)
591 require.Nil(t, err)
592
593 // use numbers near above 0
594 k = big.NewInt(int64(i))
595 err = mt.Add(k, v)
596 require.Nil(t, err)
597 }
598
599 d, err := mt.DumpLeafs(nil)
600 assert.Nil(t, err)
601
602 mt2, err := NewMerkleTree(memory.NewMemoryStorage(), 140)
603 require.Nil(t, err)
604 defer mt2.db.Close()
605 err = mt2.ImportDumpedLeafs(d)
606 assert.Nil(t, err)
607
608 assert.Equal(t, mt.Root(), mt2.Root())
609}
610
611func TestAddAndGetCircomProof(t *testing.T) {
612 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 10)
613 assert.Nil(t, err)
614 assert.Equal(t, "0", mt.Root().String())
615
616 // test vectors generated using https://github.com/iden3/circomlib smt.js
617 cpp, err := mt.AddAndGetCircomProof(big.NewInt(1), big.NewInt(2))
618 assert.Nil(t, err)
619 assert.Equal(t, "0", cpp.OldRoot.String())
620 assert.Equal(t, "64497120...", cpp.NewRoot.String())
621 assert.Equal(t, "0", cpp.OldKey.String())
622 assert.Equal(t, "0", cpp.OldValue.String())
623 assert.Equal(t, "1", cpp.NewKey.String())
624 assert.Equal(t, "2", cpp.NewValue.String())
625 assert.Equal(t, true, cpp.IsOld0)
626 assert.Equal(t, "[0 0 0 0 0 0 0 0 0 0 0]", fmt.Sprintf("%v", cpp.Siblings))
627
628 cpp, err = mt.AddAndGetCircomProof(big.NewInt(33), big.NewInt(44))
629 assert.Nil(t, err)
630 assert.Equal(t, "64497120...", cpp.OldRoot.String())
631 assert.Equal(t, "11404118...", cpp.NewRoot.String())
632 assert.Equal(t, "1", cpp.OldKey.String())
633 assert.Equal(t, "2", cpp.OldValue.String())
634 assert.Equal(t, "33", cpp.NewKey.String())
635 assert.Equal(t, "44", cpp.NewValue.String())
636 assert.Equal(t, false, cpp.IsOld0)
637 assert.Equal(t, "[0 0 0 0 0 0 0 0 0 0 0]", fmt.Sprintf("%v", cpp.Siblings))
638
639 cpp, err = mt.AddAndGetCircomProof(big.NewInt(55), big.NewInt(66))
640 assert.Nil(t, err)
641 assert.Equal(t, "11404118...", cpp.OldRoot.String())
642 assert.Equal(t, "18284203...", cpp.NewRoot.String())
643 assert.Equal(t, "0", cpp.OldKey.String())
644 assert.Equal(t, "0", cpp.OldValue.String())
645 assert.Equal(t, "55", cpp.NewKey.String())
646 assert.Equal(t, "66", cpp.NewValue.String())
647 assert.Equal(t, true, cpp.IsOld0)
648 assert.Equal(t, "[0 42948778... 0 0 0 0 0 0 0 0 0]", fmt.Sprintf("%v", cpp.Siblings))
649 // fmt.Println(cpp)
650}
651
652func TestUpdateCircomProcessorProof(t *testing.T) {
653 mt := newTestingMerkle(t, 10)
654 defer mt.db.Close()
655
656 for i := 0; i < 16; i++ {
657 k := big.NewInt(int64(i))
658 v := big.NewInt(int64(i * 2))
659 if err := mt.Add(k, v); err != nil {
660 t.Fatal(err)
661 }
662 }
663 _, v, _, err := mt.Get(big.NewInt(10))
664 assert.Nil(t, err)
665 assert.Equal(t, big.NewInt(20), v)
666
667 // test vectors generated using https://github.com/iden3/circomlib smt.js
668 cpp, err := mt.Update(big.NewInt(10), big.NewInt(1024))
669 assert.Nil(t, err)
670 assert.Equal(t, "14895645...", cpp.OldRoot.String())
671 assert.Equal(t, "75223641...", cpp.NewRoot.String())
672 assert.Equal(t, "10", cpp.OldKey.String())
673 assert.Equal(t, "20", cpp.OldValue.String())
674 assert.Equal(t, "10", cpp.NewKey.String())
675 assert.Equal(t, "1024", cpp.NewValue.String())
676 assert.Equal(t, false, cpp.IsOld0)
677 assert.Equal(t, "[19625419... 46910949... 18399594... 20473908... 0 0 0 0 0 0 0]", fmt.Sprintf("%v", cpp.Siblings))
678}