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