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