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