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