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) //nolint:lll
47 assert.True(t, ok)
48 h := NewHashFromBigInt(b)
49 assert.Equal(t, "4932297968297298434239270129193057052722409868268166443802652458940273154854", h.BigInt().String()) //nolint:lll
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, "13578938674299138072471463694055224830892726234048532520316387704878000008795", mt.Root().BigInt().String()) //nolint:lll
102
103 err = mt.Add(big.NewInt(33), big.NewInt(44))
104 assert.Nil(t, err)
105 assert.Equal(t, "5412393676474193513566895793055462193090331607895808993925969873307089394741", mt.Root().BigInt().String()) //nolint:lll
106
107 err = mt.Add(big.NewInt(1234), big.NewInt(9876))
108 assert.Nil(t, err)
109 assert.Equal(t, "14204494359367183802864593755198662203838502594566452929175967972147978322084", mt.Root().BigInt().String()) //nolint:lll
110
111 dbRoot, err := mt.dbGetRoot()
112 require.Nil(t, err)
113 assert.Equal(t, mt.Root(), dbRoot)
114
115 proof, v, err := mt.GenerateProof(big.NewInt(33), nil)
116 assert.Nil(t, err)
117 assert.Equal(t, big.NewInt(44), v)
118
119 assert.True(t, VerifyProof(mt.Root(), proof, big.NewInt(33), big.NewInt(44)))
120 assert.True(t, !VerifyProof(mt.Root(), proof, big.NewInt(33), big.NewInt(45)))
121}
122
123func TestAddDifferentOrder(t *testing.T) {
124 mt1 := newTestingMerkle(t, 140)
125 defer mt1.db.Close()
126 for i := 0; i < 16; i++ {
127 k := big.NewInt(int64(i))
128 v := big.NewInt(0)
129 if err := mt1.Add(k, v); err != nil {
130 t.Fatal(err)
131 }
132 }
133
134 mt2 := newTestingMerkle(t, 140)
135 defer mt2.db.Close()
136 for i := 16 - 1; i >= 0; i-- {
137 k := big.NewInt(int64(i))
138 v := big.NewInt(0)
139 if err := mt2.Add(k, v); err != nil {
140 t.Fatal(err)
141 }
142 }
143
144 assert.Equal(t, mt1.Root().Hex(), mt2.Root().Hex())
145 assert.Equal(t, "3b89100bec24da9275c87bc188740389e1d5accfc7d88ba5688d7fa96a00d82f", mt1.Root().Hex()) //nolint:lll
146}
147
148func TestAddRepeatedIndex(t *testing.T) {
149 mt := newTestingMerkle(t, 140)
150 defer mt.db.Close()
151 k := big.NewInt(int64(3))
152 v := big.NewInt(int64(12))
153 if err := mt.Add(k, v); err != nil {
154 t.Fatal(err)
155 }
156 err := mt.Add(k, v)
157 assert.NotNil(t, err)
158 assert.Equal(t, err, ErrEntryIndexAlreadyExists)
159}
160
161func TestGet(t *testing.T) {
162 mt := newTestingMerkle(t, 140)
163 defer mt.db.Close()
164
165 for i := 0; i < 16; i++ {
166 k := big.NewInt(int64(i))
167 v := big.NewInt(int64(i * 2))
168 if err := mt.Add(k, v); err != nil {
169 t.Fatal(err)
170 }
171 }
172 k, v, _, err := mt.Get(big.NewInt(10))
173 assert.Nil(t, err)
174 assert.Equal(t, big.NewInt(10), k)
175 assert.Equal(t, big.NewInt(20), v)
176
177 k, v, _, err = mt.Get(big.NewInt(15))
178 assert.Nil(t, err)
179 assert.Equal(t, big.NewInt(15), k)
180 assert.Equal(t, big.NewInt(30), v)
181
182 k, v, _, err = mt.Get(big.NewInt(16))
183 assert.NotNil(t, err)
184 assert.Equal(t, ErrKeyNotFound, err)
185 assert.Equal(t, "0", k.String())
186 assert.Equal(t, "0", v.String())
187}
188
189func TestUpdate(t *testing.T) {
190 mt := newTestingMerkle(t, 140)
191 defer mt.db.Close()
192
193 for i := 0; i < 16; i++ {
194 k := big.NewInt(int64(i))
195 v := big.NewInt(int64(i * 2))
196 if err := mt.Add(k, v); err != nil {
197 t.Fatal(err)
198 }
199 }
200 _, v, _, err := mt.Get(big.NewInt(10))
201 assert.Nil(t, err)
202 assert.Equal(t, big.NewInt(20), v)
203
204 _, err = mt.Update(big.NewInt(10), big.NewInt(1024))
205 assert.Nil(t, err)
206 _, v, _, err = mt.Get(big.NewInt(10))
207 assert.Nil(t, err)
208 assert.Equal(t, big.NewInt(1024), v)
209
210 _, err = mt.Update(big.NewInt(1000), big.NewInt(1024))
211 assert.Equal(t, ErrKeyNotFound, err)
212
213 dbRoot, err := mt.dbGetRoot()
214 require.Nil(t, err)
215 assert.Equal(t, mt.Root(), dbRoot)
216}
217
218func TestUpdate2(t *testing.T) {
219 mt1 := newTestingMerkle(t, 140)
220 defer mt1.db.Close()
221 mt2 := newTestingMerkle(t, 140)
222 defer mt2.db.Close()
223
224 err := mt1.Add(big.NewInt(1), big.NewInt(119))
225 assert.Nil(t, err)
226 err = mt1.Add(big.NewInt(2), big.NewInt(229))
227 assert.Nil(t, err)
228 err = mt1.Add(big.NewInt(9876), big.NewInt(6789))
229 assert.Nil(t, err)
230
231 err = mt2.Add(big.NewInt(1), big.NewInt(11))
232 assert.Nil(t, err)
233 err = mt2.Add(big.NewInt(2), big.NewInt(22))
234 assert.Nil(t, err)
235 err = mt2.Add(big.NewInt(9876), big.NewInt(10))
236 assert.Nil(t, err)
237
238 _, err = mt1.Update(big.NewInt(1), big.NewInt(11))
239 assert.Nil(t, err)
240 _, err = mt1.Update(big.NewInt(2), big.NewInt(22))
241 assert.Nil(t, err)
242 _, err = mt2.Update(big.NewInt(9876), big.NewInt(6789))
243 assert.Nil(t, err)
244
245 assert.Equal(t, mt1.Root(), mt2.Root())
246}
247
248func TestGenerateAndVerifyProof128(t *testing.T) {
249 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 140)
250 require.Nil(t, err)
251 defer mt.db.Close()
252
253 for i := 0; i < 128; i++ {
254 k := big.NewInt(int64(i))
255 v := big.NewInt(0)
256 if err := mt.Add(k, v); err != nil {
257 t.Fatal(err)
258 }
259 }
260 proof, v, err := mt.GenerateProof(big.NewInt(42), nil)
261 assert.Nil(t, err)
262 assert.Equal(t, "0", v.String())
263 assert.True(t, VerifyProof(mt.Root(), proof, big.NewInt(42), big.NewInt(0)))
264}
265
266func TestTreeLimit(t *testing.T) {
267 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 5)
268 require.Nil(t, err)
269 defer mt.db.Close()
270
271 for i := 0; i < 16; i++ {
272 err = mt.Add(big.NewInt(int64(i)), big.NewInt(int64(i)))
273 assert.Nil(t, err)
274 }
275
276 // here the tree is full, should not allow to add more data as reaches the maximum number of levels
277 err = mt.Add(big.NewInt(int64(16)), big.NewInt(int64(16)))
278 assert.NotNil(t, err)
279 assert.Equal(t, ErrReachedMaxLevel, err)
280}
281
282func TestSiblingsFromProof(t *testing.T) {
283 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 140)
284 require.Nil(t, err)
285 defer mt.db.Close()
286
287 for i := 0; i < 64; i++ {
288 k := big.NewInt(int64(i))
289 v := big.NewInt(0)
290 if err := mt.Add(k, v); err != nil {
291 t.Fatal(err)
292 }
293 }
294
295 proof, _, err := mt.GenerateProof(big.NewInt(4), nil)
296 if err != nil {
297 t.Fatal(err)
298 }
299
300 siblings := SiblingsFromProof(proof)
301 assert.Equal(t, 6, len(siblings))
302 assert.Equal(t,
303 "d6e368bda90c5ee3e910222c1fc1c0d9e23f2d350dbc47f4a92de30f1be3c60b",
304 siblings[0].Hex())
305 assert.Equal(t,
306 "9dbd03b1bcd580e0f3e6668d80d55288f04464126feb1624ec8ee30be8df9c16",
307 siblings[1].Hex())
308 assert.Equal(t,
309 "de866af9545dcd1c5bb7811e7f27814918e037eb9fead40919e8f19525896e27",
310 siblings[2].Hex())
311 assert.Equal(t,
312 "5f4182212a84741d1174ba7c42e369f2e3ad8ade7d04eea2d0f98e3ed8b7a317",
313 siblings[3].Hex())
314 assert.Equal(t,
315 "77639098d513f7aef9730fdb1d1200401af5fe9da91b61772f4dd142ac89a122",
316 siblings[4].Hex())
317 assert.Equal(t,
318 "943ee501f4ba2137c79b54af745dfc5f105f539fcc449cd2a356eb5c030e3c07",
319 siblings[5].Hex())
320}
321
322func TestVerifyProofCases(t *testing.T) {
323 mt := newTestingMerkle(t, 140)
324 defer mt.DB().Close()
325
326 for i := 0; i < 8; i++ {
327 if err := mt.Add(big.NewInt(int64(i)), big.NewInt(0)); err != nil {
328 t.Fatal(err)
329 }
330 }
331
332 // Existence proof
333 proof, _, err := mt.GenerateProof(big.NewInt(4), nil)
334 if err != nil {
335 t.Fatal(err)
336 }
337 assert.Equal(t, proof.Existence, true)
338 assert.True(t, VerifyProof(mt.Root(), proof, big.NewInt(4), big.NewInt(0)))
339 assert.Equal(t, "0003000000000000000000000000000000000000000000000000000000000007529cbedbda2bdd25fd6455551e55245fa6dc11a9d0c27dc0cd38fca44c17e40344ad686a18ba78b502c0b6f285c5c8393bde2f7a3e2abe586515e4d84533e3037b062539bde2d80749746986cf8f0001fd2cdbf9a89fcbf981a769daef49df06", hex.EncodeToString(proof.Bytes())) //nolint:lll
340
341 for i := 8; i < 32; i++ {
342 proof, _, err = mt.GenerateProof(big.NewInt(int64(i)), nil)
343 assert.Nil(t, err)
344 if debug {
345 fmt.Println(i, proof)
346 }
347 }
348 // Non-existence proof, empty aux
349 proof, _, err = mt.GenerateProof(big.NewInt(12), nil)
350 if err != nil {
351 t.Fatal(err)
352 }
353 assert.Equal(t, proof.Existence, false)
354 // assert.True(t, proof.nodeAux == nil)
355 assert.True(t, VerifyProof(mt.Root(), proof, big.NewInt(12), big.NewInt(0)))
356 assert.Equal(t, "0303000000000000000000000000000000000000000000000000000000000007529cbedbda2bdd25fd6455551e55245fa6dc11a9d0c27dc0cd38fca44c17e40344ad686a18ba78b502c0b6f285c5c8393bde2f7a3e2abe586515e4d84533e3037b062539bde2d80749746986cf8f0001fd2cdbf9a89fcbf981a769daef49df0604000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", hex.EncodeToString(proof.Bytes())) //nolint:lll
357
358 // Non-existence proof, diff. node aux
359 proof, _, err = mt.GenerateProof(big.NewInt(10), nil)
360 if err != nil {
361 t.Fatal(err)
362 }
363 assert.Equal(t, proof.Existence, false)
364 assert.True(t, proof.NodeAux != nil)
365 assert.True(t, VerifyProof(mt.Root(), proof, big.NewInt(10), big.NewInt(0)))
366 assert.Equal(t, "0303000000000000000000000000000000000000000000000000000000000007529cbedbda2bdd25fd6455551e55245fa6dc11a9d0c27dc0cd38fca44c17e4030acfcdd2617df9eb5aef744c5f2e03eb8c92c61f679007dc1f2707fd908ea41a9433745b469c101edca814c498e7f388100d497b24f1d2ac935bced3572f591d02000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", hex.EncodeToString(proof.Bytes())) //nolint:lll
367}
368
369func TestVerifyProofFalse(t *testing.T) {
370 mt := newTestingMerkle(t, 140)
371 defer mt.DB().Close()
372
373 for i := 0; i < 8; i++ {
374 if err := mt.Add(big.NewInt(int64(i)), big.NewInt(0)); err != nil {
375 t.Fatal(err)
376 }
377 }
378
379 // Invalid existence proof (node used for verification doesn't
380 // correspond to node in the proof)
381 proof, _, err := mt.GenerateProof(big.NewInt(int64(4)), nil)
382 if err != nil {
383 t.Fatal(err)
384 }
385 assert.Equal(t, proof.Existence, true)
386 assert.True(t, !VerifyProof(mt.Root(), proof, big.NewInt(int64(5)), big.NewInt(int64(5))))
387
388 // Invalid non-existence proof (Non-existence proof, diff. node aux)
389 proof, _, err = mt.GenerateProof(big.NewInt(int64(4)), nil)
390 if err != nil {
391 t.Fatal(err)
392 }
393 assert.Equal(t, proof.Existence, true)
394 // Now we change the proof from existence to non-existence, and add e's
395 // data as auxiliary node.
396 proof.Existence = false
397 proof.NodeAux = &NodeAux{Key: NewHashFromBigInt(big.NewInt(int64(4))),
398 Value: NewHashFromBigInt(big.NewInt(4))}
399 assert.True(t, !VerifyProof(mt.Root(), proof, big.NewInt(int64(4)), big.NewInt(0)))
400}
401
402func TestGraphViz(t *testing.T) {
403 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 10)
404 assert.Nil(t, err)
405
406 _ = mt.Add(big.NewInt(1), big.NewInt(0))
407 _ = mt.Add(big.NewInt(2), big.NewInt(0))
408 _ = mt.Add(big.NewInt(3), big.NewInt(0))
409 _ = mt.Add(big.NewInt(4), big.NewInt(0))
410 _ = mt.Add(big.NewInt(5), big.NewInt(0))
411 _ = mt.Add(big.NewInt(100), big.NewInt(0))
412
413 // mt.PrintGraphViz(nil)
414
415 expected := `digraph hierarchy {
416node [fontname=Monospace,fontsize=10,shape=box]
417"56332309..." -> {"18483622..." "20902180..."}
418"18483622..." -> {"75768243..." "16893244..."}
419"75768243..." -> {"empty0" "21857056..."}
420"empty0" [style=dashed,label=0];
421"21857056..." -> {"51072523..." "empty1"}
422"empty1" [style=dashed,label=0];
423"51072523..." -> {"17311038..." "empty2"}
424"empty2" [style=dashed,label=0];
425"17311038..." -> {"69499803..." "21008290..."}
426"69499803..." [style=filled];
427"21008290..." [style=filled];
428"16893244..." [style=filled];
429"20902180..." -> {"12496585..." "18055627..."}
430"12496585..." -> {"19374975..." "15739329..."}
431"19374975..." [style=filled];
432"15739329..." [style=filled];
433"18055627..." [style=filled];
434}
435`
436 w := bytes.NewBufferString("")
437 err = mt.GraphViz(w, nil)
438 assert.Nil(t, err)
439 assert.Equal(t, []byte(expected), w.Bytes())
440}
441
442func TestDelete(t *testing.T) {
443 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 10)
444 assert.Nil(t, err)
445 assert.Equal(t, "0", mt.Root().String())
446
447 // test vectors generated using https://github.com/iden3/circomlib smt.js
448 err = mt.Add(big.NewInt(1), big.NewInt(2))
449 assert.Nil(t, err)
450 assert.Equal(t, "13578938674299138072471463694055224830892726234048532520316387704878000008795", mt.Root().BigInt().String()) //nolint:lll
451
452 err = mt.Add(big.NewInt(33), big.NewInt(44))
453 assert.Nil(t, err)
454 assert.Equal(t, "5412393676474193513566895793055462193090331607895808993925969873307089394741", mt.Root().BigInt().String()) //nolint:lll
455
456 err = mt.Add(big.NewInt(1234), big.NewInt(9876))
457 assert.Nil(t, err)
458 assert.Equal(t, "14204494359367183802864593755198662203838502594566452929175967972147978322084", mt.Root().BigInt().String()) //nolint:lll
459
460 // mt.PrintGraphViz(nil)
461
462 err = mt.Delete(big.NewInt(33))
463 // mt.PrintGraphViz(nil)
464 assert.Nil(t, err)
465 assert.Equal(t, "15550352095346187559699212771793131433118240951738528922418613687814377955591", mt.Root().BigInt().String()) //nolint:lll
466
467 err = mt.Delete(big.NewInt(1234))
468 assert.Nil(t, err)
469 err = mt.Delete(big.NewInt(1))
470 assert.Nil(t, err)
471 assert.Equal(t, "0", mt.Root().String())
472
473 dbRoot, err := mt.dbGetRoot()
474 require.Nil(t, err)
475 assert.Equal(t, mt.Root(), dbRoot)
476}
477
478func TestDelete2(t *testing.T) {
479 mt := newTestingMerkle(t, 140)
480 defer mt.db.Close()
481 for i := 0; i < 8; i++ {
482 k := big.NewInt(int64(i))
483 v := big.NewInt(0)
484 if err := mt.Add(k, v); err != nil {
485 t.Fatal(err)
486 }
487 }
488
489 expectedRoot := mt.Root()
490
491 k := big.NewInt(8)
492 v := big.NewInt(0)
493 err := mt.Add(k, v)
494 require.Nil(t, err)
495
496 err = mt.Delete(big.NewInt(8))
497 assert.Nil(t, err)
498 assert.Equal(t, expectedRoot, mt.Root())
499
500 mt2 := newTestingMerkle(t, 140)
501 defer mt2.db.Close()
502 for i := 0; i < 8; i++ {
503 k := big.NewInt(int64(i))
504 v := big.NewInt(0)
505 if err := mt2.Add(k, v); err != nil {
506 t.Fatal(err)
507 }
508 }
509 assert.Equal(t, mt2.Root(), mt.Root())
510}
511
512func TestDelete3(t *testing.T) {
513 mt := newTestingMerkle(t, 140)
514 defer mt.db.Close()
515
516 err := mt.Add(big.NewInt(1), big.NewInt(1))
517 assert.Nil(t, err)
518
519 err = mt.Add(big.NewInt(2), big.NewInt(2))
520 assert.Nil(t, err)
521
522 assert.Equal(t, "19060075022714027595905950662613111880864833370144986660188929919683258088314", mt.Root().BigInt().String()) //nolint:lll
523 err = mt.Delete(big.NewInt(1))
524 assert.Nil(t, err)
525 assert.Equal(t, "849831128489032619062850458217693666094013083866167024127442191257793527951", mt.Root().BigInt().String()) //nolint:lll
526
527 mt2 := newTestingMerkle(t, 140)
528 defer mt2.db.Close()
529 err = mt2.Add(big.NewInt(2), big.NewInt(2))
530 assert.Nil(t, err)
531 assert.Equal(t, mt2.Root(), mt.Root())
532}
533
534func TestDelete4(t *testing.T) {
535 mt := newTestingMerkle(t, 140)
536 defer mt.db.Close()
537
538 err := mt.Add(big.NewInt(1), big.NewInt(1))
539 assert.Nil(t, err)
540
541 err = mt.Add(big.NewInt(2), big.NewInt(2))
542 assert.Nil(t, err)
543
544 err = mt.Add(big.NewInt(3), big.NewInt(3))
545 assert.Nil(t, err)
546
547 assert.Equal(t, "14109632483797541575275728657193822866549917334388996328141438956557066918117", mt.Root().BigInt().String()) //nolint:lll
548 err = mt.Delete(big.NewInt(1))
549 assert.Nil(t, err)
550 assert.Equal(t, "159935162486187606489815340465698714590556679404589449576549073038844694972", mt.Root().BigInt().String()) //nolint:lll
551
552 mt2 := newTestingMerkle(t, 140)
553 defer mt2.db.Close()
554 err = mt2.Add(big.NewInt(2), big.NewInt(2))
555 assert.Nil(t, err)
556 err = mt2.Add(big.NewInt(3), big.NewInt(3))
557 assert.Nil(t, err)
558 assert.Equal(t, mt2.Root(), mt.Root())
559}
560
561func TestDelete5(t *testing.T) {
562 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 10)
563 assert.Nil(t, err)
564
565 err = mt.Add(big.NewInt(1), big.NewInt(2))
566 assert.Nil(t, err)
567 err = mt.Add(big.NewInt(33), big.NewInt(44))
568 assert.Nil(t, err)
569 assert.Equal(t, "5412393676474193513566895793055462193090331607895808993925969873307089394741", mt.Root().BigInt().String()) //nolint:lll
570
571 err = mt.Delete(big.NewInt(1))
572 assert.Nil(t, err)
573 assert.Equal(t, "18869260084287237667925661423624848342947598951870765316380602291081195309822", mt.Root().BigInt().String()) //nolint:lll
574
575 mt2 := newTestingMerkle(t, 140)
576 defer mt2.db.Close()
577 err = mt2.Add(big.NewInt(33), big.NewInt(44))
578 assert.Nil(t, err)
579 assert.Equal(t, mt2.Root(), mt.Root())
580}
581
582func TestDeleteNonExistingKeys(t *testing.T) {
583 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 10)
584 assert.Nil(t, err)
585
586 err = mt.Add(big.NewInt(1), big.NewInt(2))
587 assert.Nil(t, err)
588 err = mt.Add(big.NewInt(33), big.NewInt(44))
589 assert.Nil(t, err)
590
591 err = mt.Delete(big.NewInt(33))
592 assert.Nil(t, err)
593 err = mt.Delete(big.NewInt(33))
594 assert.Equal(t, ErrKeyNotFound, err)
595
596 err = mt.Delete(big.NewInt(1))
597 assert.Nil(t, err)
598
599 assert.Equal(t, "0", mt.Root().String())
600
601 err = mt.Delete(big.NewInt(33))
602 assert.Equal(t, ErrKeyNotFound, err)
603}
604
605func TestDumpLeafsImportLeafs(t *testing.T) {
606 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 140)
607 require.Nil(t, err)
608 defer mt.db.Close()
609
610 q1 := new(big.Int).Sub(constants.Q, big.NewInt(1))
611 for i := 0; i < 10; i++ {
612 // use numbers near under Q
613 k := new(big.Int).Sub(q1, big.NewInt(int64(i)))
614 v := big.NewInt(0)
615 err = mt.Add(k, v)
616 require.Nil(t, err)
617
618 // use numbers near above 0
619 k = big.NewInt(int64(i))
620 err = mt.Add(k, v)
621 require.Nil(t, err)
622 }
623
624 d, err := mt.DumpLeafs(nil)
625 assert.Nil(t, err)
626
627 mt2, err := NewMerkleTree(memory.NewMemoryStorage(), 140)
628 require.Nil(t, err)
629 defer mt2.db.Close()
630 err = mt2.ImportDumpedLeafs(d)
631 assert.Nil(t, err)
632
633 assert.Equal(t, mt.Root(), mt2.Root())
634}
635
636func TestAddAndGetCircomProof(t *testing.T) {
637 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 10)
638 assert.Nil(t, err)
639 assert.Equal(t, "0", mt.Root().String())
640
641 // test vectors generated using https://github.com/iden3/circomlib smt.js
642 cpp, err := mt.AddAndGetCircomProof(big.NewInt(1), big.NewInt(2))
643 assert.Nil(t, err)
644 assert.Equal(t, "0", cpp.OldRoot.String())
645 assert.Equal(t, "13578938...", cpp.NewRoot.String())
646 assert.Equal(t, "0", cpp.OldKey.String())
647 assert.Equal(t, "0", cpp.OldValue.String())
648 assert.Equal(t, "1", cpp.NewKey.String())
649 assert.Equal(t, "2", cpp.NewValue.String())
650 assert.Equal(t, true, cpp.IsOld0)
651 assert.Equal(t, "[0 0 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 cpp, err = mt.AddAndGetCircomProof(big.NewInt(33), big.NewInt(44))
655 assert.Nil(t, err)
656 assert.Equal(t, "13578938...", cpp.OldRoot.String())
657 assert.Equal(t, "54123936...", cpp.NewRoot.String())
658 assert.Equal(t, "1", cpp.OldKey.String())
659 assert.Equal(t, "2", cpp.OldValue.String())
660 assert.Equal(t, "33", cpp.NewKey.String())
661 assert.Equal(t, "44", cpp.NewValue.String())
662 assert.Equal(t, false, cpp.IsOld0)
663 assert.Equal(t, "[0 0 0 0 0 0 0 0 0 0 0]", fmt.Sprintf("%v", cpp.Siblings))
664 assert.Equal(t, mt.maxLevels+1, len(cpp.Siblings))
665
666 cpp, err = mt.AddAndGetCircomProof(big.NewInt(55), big.NewInt(66))
667 assert.Nil(t, err)
668 assert.Equal(t, "54123936...", cpp.OldRoot.String())
669 assert.Equal(t, "50943640...", cpp.NewRoot.String())
670 assert.Equal(t, "0", cpp.OldKey.String())
671 assert.Equal(t, "0", cpp.OldValue.String())
672 assert.Equal(t, "55", cpp.NewKey.String())
673 assert.Equal(t, "66", cpp.NewValue.String())
674 assert.Equal(t, true, cpp.IsOld0)
675 assert.Equal(t, "[0 21312042... 0 0 0 0 0 0 0 0 0]", fmt.Sprintf("%v", cpp.Siblings))
676 assert.Equal(t, mt.maxLevels+1, len(cpp.Siblings))
677}
678
679func TestUpdateCircomProcessorProof(t *testing.T) {
680 mt := newTestingMerkle(t, 10)
681 defer mt.db.Close()
682
683 for i := 0; i < 16; i++ {
684 k := big.NewInt(int64(i))
685 v := big.NewInt(int64(i * 2))
686 if err := mt.Add(k, v); err != nil {
687 t.Fatal(err)
688 }
689 }
690 _, v, _, err := mt.Get(big.NewInt(10))
691 assert.Nil(t, err)
692 assert.Equal(t, big.NewInt(20), v)
693
694 // test vectors generated using https://github.com/iden3/circomlib smt.js
695 cpp, err := mt.Update(big.NewInt(10), big.NewInt(1024))
696 assert.Nil(t, err)
697 assert.Equal(t, "39010880...", cpp.OldRoot.String())
698 assert.Equal(t, "18587862...", cpp.NewRoot.String())
699 assert.Equal(t, "10", cpp.OldKey.String())
700 assert.Equal(t, "20", cpp.OldValue.String())
701 assert.Equal(t, "10", cpp.NewKey.String())
702 assert.Equal(t, "1024", cpp.NewValue.String())
703 assert.Equal(t, false, cpp.IsOld0)
704 assert.Equal(t,
705 "[34930557... 20201609... 18790542... 15930030... 0 0 0 0 0 0 0]",
706 fmt.Sprintf("%v", cpp.Siblings))
707}
708
709func TestSmtVerifier(t *testing.T) {
710 mt, err := NewMerkleTree(memory.NewMemoryStorage(), 4)
711 assert.Nil(t, err)
712
713 err = mt.Add(big.NewInt(1), big.NewInt(11))
714 assert.Nil(t, err)
715
716 cvp, err := mt.GenerateSCVerifierProof(big.NewInt(1), nil)
717 assert.Nil(t, err)
718 jCvp, err := json.Marshal(cvp)
719 assert.Nil(t, err)
720 // expect siblings to be '[]', instead of 'null'
721 expected := `{"root":"6525056641794203554583616941316772618766382307684970171204065038799368146416","siblings":[],"oldKey":"0","oldValue":"0","isOld0":false,"key":"1","value":"11","fnc":0}` //nolint:lll
722
723 assert.Equal(t, expected, string(jCvp))
724 err = mt.Add(big.NewInt(2), big.NewInt(22))
725 assert.Nil(t, err)
726 err = mt.Add(big.NewInt(3), big.NewInt(33))
727 assert.Nil(t, err)
728 err = mt.Add(big.NewInt(4), big.NewInt(44))
729 assert.Nil(t, err)
730
731 cvp, err = mt.GenerateCircomVerifierProof(big.NewInt(2), nil)
732 assert.Nil(t, err)
733
734 jCvp, err = json.Marshal(cvp)
735 assert.Nil(t, err)
736 // Test vectors generated using https://github.com/iden3/circomlib smt.js
737 // Expect siblings with the extra 0 that the circom circuits need
738 expected = `{"root":"13558168455220559042747853958949063046226645447188878859760119761585093422436","siblings":["11620130507635441932056895853942898236773847390796721536119314875877874016518","5158240518874928563648144881543092238925265313977134167935552944620041388700","0","0","0"],"oldKey":"0","oldValue":"0","isOld0":false,"key":"2","value":"22","fnc":0}` //nolint:lll
739 assert.Equal(t, expected, string(jCvp))
740
741 cvp, err = mt.GenerateSCVerifierProof(big.NewInt(2), nil)
742 assert.Nil(t, err)
743
744 jCvp, err = json.Marshal(cvp)
745 assert.Nil(t, err)
746 // Test vectors generated using https://github.com/iden3/circomlib smt.js
747 // Without the extra 0 that the circom circuits need, but that are not
748 // needed at a smart contract verification
749 expected = `{"root":"13558168455220559042747853958949063046226645447188878859760119761585093422436","siblings":["11620130507635441932056895853942898236773847390796721536119314875877874016518","5158240518874928563648144881543092238925265313977134167935552944620041388700"],"oldKey":"0","oldValue":"0","isOld0":false,"key":"2","value":"22","fnc":0}` //nolint:lll
750 assert.Equal(t, expected, string(jCvp))
751}
752
753func TestTypesMarshalers(t *testing.T) {
754 // test Hash marshalers
755 h, err := NewHashFromString("42")
756 assert.Nil(t, err)
757 s, err := json.Marshal(h)
758 assert.Nil(t, err)
759 var h2 *Hash
760 err = json.Unmarshal(s, &h2)
761 assert.Nil(t, err)
762 assert.Equal(t, h, h2)
763
764 // create CircomProcessorProof
765 mt := newTestingMerkle(t, 10)
766 defer mt.db.Close()
767 for i := 0; i < 16; i++ {
768 k := big.NewInt(int64(i))
769 v := big.NewInt(int64(i * 2))
770 if err := mt.Add(k, v); err != nil {
771 t.Fatal(err)
772 }
773 }
774 _, v, _, err := mt.Get(big.NewInt(10))
775 assert.Nil(t, err)
776 assert.Equal(t, big.NewInt(20), v)
777 cpp, err := mt.Update(big.NewInt(10), big.NewInt(1024))
778 assert.Nil(t, err)
779
780 // test CircomProcessorProof marshalers
781 b, err := json.Marshal(&cpp)
782 assert.Nil(t, err)
783
784 var cpp2 *CircomProcessorProof
785 err = json.Unmarshal(b, &cpp2)
786 assert.Nil(t, err)
787 assert.Equal(t, cpp, cpp2)
788}