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 0]", fmt.Sprintf("%v", cpp.Siblings))
628 assert.Equal(t, mt.maxLevels+1, len(cpp.Siblings))
629
630 cpp, err = mt.AddAndGetCircomProof(big.NewInt(33), big.NewInt(44))
631 assert.Nil(t, err)
632 assert.Equal(t, "64497120...", cpp.OldRoot.String())
633 assert.Equal(t, "11404118...", cpp.NewRoot.String())
634 assert.Equal(t, "1", cpp.OldKey.String())
635 assert.Equal(t, "2", cpp.OldValue.String())
636 assert.Equal(t, "33", cpp.NewKey.String())
637 assert.Equal(t, "44", cpp.NewValue.String())
638 assert.Equal(t, false, 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(55), big.NewInt(66))
643 assert.Nil(t, err)
644 assert.Equal(t, "11404118...", cpp.OldRoot.String())
645 assert.Equal(t, "18284203...", cpp.NewRoot.String())
646 assert.Equal(t, "0", cpp.OldKey.String())
647 assert.Equal(t, "0", cpp.OldValue.String())
648 assert.Equal(t, "55", cpp.NewKey.String())
649 assert.Equal(t, "66", cpp.NewValue.String())
650 assert.Equal(t, true, cpp.IsOld0)
651 assert.Equal(t, "[0 42948778... 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
655func TestUpdateCircomProcessorProof(t *testing.T) {
656 mt := newTestingMerkle(t, 10)
657 defer mt.db.Close()
658
659 for i := 0; i < 16; i++ {
660 k := big.NewInt(int64(i))
661 v := big.NewInt(int64(i * 2))
662 if err := mt.Add(k, v); err != nil {
663 t.Fatal(err)
664 }
665 }
666 _, v, _, err := mt.Get(big.NewInt(10))
667 assert.Nil(t, err)
668 assert.Equal(t, big.NewInt(20), v)
669
670 // test vectors generated using https://github.com/iden3/circomlib smt.js
671 cpp, err := mt.Update(big.NewInt(10), big.NewInt(1024))
672 assert.Nil(t, err)
673 assert.Equal(t, "14895645...", cpp.OldRoot.String())
674 assert.Equal(t, "75223641...", cpp.NewRoot.String())
675 assert.Equal(t, "10", cpp.OldKey.String())
676 assert.Equal(t, "20", cpp.OldValue.String())
677 assert.Equal(t, "10", cpp.NewKey.String())
678 assert.Equal(t, "1024", cpp.NewValue.String())
679 assert.Equal(t, false, cpp.IsOld0)
680 assert.Equal(t, "[19625419... 46910949... 18399594... 20473908... 0 0 0 0 0 0 0]", fmt.Sprintf("%v", cpp.Siblings))
681}
682
683func TestTypesMarshalers(t *testing.T) {
684 // test Hash marshalers
685 h, err := NewHashFromString("42")
686 assert.Nil(t, err)
687 s, err := json.Marshal(h)
688 assert.Nil(t, err)
689 var h2 *Hash
690 err = json.Unmarshal(s, &h2)
691 assert.Nil(t, err)
692 assert.Equal(t, h, h2)
693
694 // create CircomProcessorProof
695 mt := newTestingMerkle(t, 10)
696 defer mt.db.Close()
697 for i := 0; i < 16; i++ {
698 k := big.NewInt(int64(i))
699 v := big.NewInt(int64(i * 2))
700 if err := mt.Add(k, v); err != nil {
701 t.Fatal(err)
702 }
703 }
704 _, v, _, err := mt.Get(big.NewInt(10))
705 assert.Nil(t, err)
706 assert.Equal(t, big.NewInt(20), v)
707 cpp, err := mt.Update(big.NewInt(10), big.NewInt(1024))
708 assert.Nil(t, err)
709
710 // test CircomProcessorProof marshalers
711 b, err := json.Marshal(&cpp)
712 assert.Nil(t, err)
713
714 var cpp2 *CircomProcessorProof
715 err = json.Unmarshal(b, &cpp2)
716 assert.Nil(t, err)
717 assert.Equal(t, cpp, cpp2)
718}