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