arbo/addbatch_test.go
addbatch_test.goRaw
1package arbo
2
3import (
4 "crypto/rand"
5 "encoding/hex"
6 "fmt"
7 "math/big"
8 "runtime"
9 "sort"
10 "testing"
11 "time"
12
13 qt "github.com/frankban/quicktest"
14 "go.vocdoni.io/dvote/db/badgerdb"
15)
16
17var debug = true
18
19func printTestContext(prefix string, nLeafs int, hashName, dbName string) {
20 if debug {
21 fmt.Printf("%snCPU: %d, nLeafs: %d, hash: %s, db: %s\n",
22 prefix, runtime.NumCPU(), nLeafs, hashName, dbName)
23 }
24}
25
26func printRes(name string, duration time.Duration) {
27 if debug {
28 fmt.Printf("%s: %s \n", name, duration)
29 }
30}
31
32func debugTime(descr string, time1, time2 time.Duration) {
33 if debug {
34 fmt.Printf("%s was %.02fx times faster than without AddBatch\n",
35 descr, float64(time1)/float64(time2))
36 }
37}
38
39func testInit(c *qt.C, n int) (*Tree, *Tree) {
40 database1, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
41 c.Assert(err, qt.IsNil)
42 tree1, err := NewTree(database1, 256, HashFunctionPoseidon)
43 c.Assert(err, qt.IsNil)
44
45 database2, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
46 c.Assert(err, qt.IsNil)
47 tree2, err := NewTree(database2, 256, HashFunctionPoseidon)
48 c.Assert(err, qt.IsNil)
49
50 bLen := HashFunctionPoseidon.Len()
51 // add the initial leafs to fill a bit the trees before calling the
52 // AddBatch method
53 for i := 0; i < n; i++ {
54 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
55 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
56 if err := tree1.Add(k, v); err != nil {
57 c.Fatal(err)
58 }
59 if err := tree2.Add(k, v); err != nil {
60 c.Fatal(err)
61 }
62 }
63 return tree1, tree2
64}
65
66func TestAddBatchTreeEmpty(t *testing.T) {
67 c := qt.New(t)
68
69 nLeafs := 1024
70
71 database, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
72 c.Assert(err, qt.IsNil)
73 tree, err := NewTree(database, 256, HashFunctionPoseidon)
74 c.Assert(err, qt.IsNil)
75 defer tree.db.Close() //nolint:errcheck
76
77 bLen := 32
78 var keys, values [][]byte
79 for i := 0; i < nLeafs; i++ {
80 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
81 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
82 keys = append(keys, k)
83 values = append(values, v)
84 }
85
86 start := time.Now()
87 for i := 0; i < nLeafs; i++ {
88 if err := tree.Add(keys[i], values[i]); err != nil {
89 t.Fatal(err)
90 }
91 }
92 time1 := time.Since(start)
93
94 database2, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
95 c.Assert(err, qt.IsNil)
96 tree2, err := NewTree(database2, 256, HashFunctionPoseidon)
97 c.Assert(err, qt.IsNil)
98 defer tree2.db.Close() //nolint:errcheck
99 tree2.dbgInit()
100
101 start = time.Now()
102 indexes, err := tree2.AddBatch(keys, values)
103 c.Assert(err, qt.IsNil)
104 time2 := time.Since(start)
105 if debug {
106 debugTime("Case tree empty, AddBatch", time1, time2)
107 printTestContext(" ", nLeafs, "Poseidon", "memory")
108 tree2.dbg.print(" ")
109 }
110 c.Check(len(indexes), qt.Equals, 0)
111
112 // check that both trees roots are equal
113 checkRoots(c, tree, tree2)
114}
115
116func TestAddBatchTreeEmptyNotPowerOf2(t *testing.T) {
117 c := qt.New(t)
118
119 nLeafs := 1027
120
121 database, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
122 c.Assert(err, qt.IsNil)
123 tree, err := NewTree(database, 256, HashFunctionPoseidon)
124 c.Assert(err, qt.IsNil)
125 defer tree.db.Close() //nolint:errcheck
126
127 bLen := 32
128 for i := 0; i < nLeafs; i++ {
129 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
130 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
131 if err := tree.Add(k, v); err != nil {
132 t.Fatal(err)
133 }
134 }
135
136 database2, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
137 c.Assert(err, qt.IsNil)
138 tree2, err := NewTree(database2, 256, HashFunctionPoseidon)
139 c.Assert(err, qt.IsNil)
140 defer tree2.db.Close() //nolint:errcheck
141
142 var keys, values [][]byte
143 for i := 0; i < nLeafs; i++ {
144 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
145 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
146 keys = append(keys, k)
147 values = append(values, v)
148 }
149 indexes, err := tree2.AddBatch(keys, values)
150 c.Assert(err, qt.IsNil)
151 c.Check(len(indexes), qt.Equals, 0)
152
153 // check that both trees roots are equal
154 checkRoots(c, tree, tree2)
155}
156
157func randomBytes(n int) []byte {
158 b := make([]byte, n)
159 _, err := rand.Read(b)
160 if err != nil {
161 panic(err)
162 }
163 return b
164}
165
166func TestAddBatchTestVector1(t *testing.T) {
167 c := qt.New(t)
168 database1, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
169 c.Assert(err, qt.IsNil)
170 tree1, err := NewTree(database1, 256, HashFunctionBlake2b)
171 c.Assert(err, qt.IsNil)
172 defer tree1.db.Close() //nolint:errcheck
173
174 database2, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
175 c.Assert(err, qt.IsNil)
176 tree2, err := NewTree(database2, 256, HashFunctionBlake2b)
177 c.Assert(err, qt.IsNil)
178 defer tree2.db.Close() //nolint:errcheck
179
180 // leafs in 2nd level subtrees: [ 6, 0, 1, 1]
181 testvectorKeys := []string{
182 "1c7c2265e368314ca58ed2e1f33a326f1220e234a566d55c3605439dbe411642",
183 "2c9f0a578afff5bfa4e0992a43066460faaab9e8e500db0b16647c701cdb16bf",
184 "1c45cb31f2fa39ec7b9ebf0fad40e0b8296016b5ce8844ae06ff77226379d9a5",
185 "d8af98bbbb585129798ae54d5eabbc9d0561d583faf1663b3a3724d15bda4ec7",
186 }
187 var keys, values [][]byte
188 for i := 0; i < len(testvectorKeys); i++ {
189 key, err := hex.DecodeString(testvectorKeys[i])
190 c.Assert(err, qt.IsNil)
191 keys = append(keys, key)
192 values = append(values, []byte{0})
193 }
194
195 for i := 0; i < len(keys); i++ {
196 if err := tree1.Add(keys[i], values[i]); err != nil {
197 t.Fatal(err)
198 }
199 }
200
201 indexes, err := tree2.AddBatch(keys, values)
202 c.Assert(err, qt.IsNil)
203 c.Check(len(indexes), qt.Equals, 0)
204 // check that both trees roots are equal
205 checkRoots(c, tree1, tree2)
206
207 // 2nd test vectors
208 database1, err = badgerdb.New(badgerdb.Options{Path: c.TempDir()})
209 c.Assert(err, qt.IsNil)
210 tree1, err = NewTree(database1, 256, HashFunctionBlake2b)
211 c.Assert(err, qt.IsNil)
212 defer tree1.db.Close() //nolint:errcheck
213
214 database2, err = badgerdb.New(badgerdb.Options{Path: c.TempDir()})
215 c.Assert(err, qt.IsNil)
216 tree2, err = NewTree(database2, 256, HashFunctionBlake2b)
217 c.Assert(err, qt.IsNil)
218 defer tree2.db.Close() //nolint:errcheck
219
220 testvectorKeys = []string{
221 "1c7c2265e368314ca58ed2e1f33a326f1220e234a566d55c3605439dbe411642",
222 "2c9f0a578afff5bfa4e0992a43066460faaab9e8e500db0b16647c701cdb16bf",
223 "9cb87ec67e875c61390edcd1ab517f443591047709a4d4e45b0f9ed980857b8e",
224 "9b4e9e92e974a589f426ceeb4cb291dc24893513fecf8e8460992dcf52621d4d",
225 "1c45cb31f2fa39ec7b9ebf0fad40e0b8296016b5ce8844ae06ff77226379d9a5",
226 "d8af98bbbb585129798ae54d5eabbc9d0561d583faf1663b3a3724d15bda4ec7",
227 "3cd55dbfb8f975f20a0925dfbdabe79fa2d51dd0268afbb8ba6b01de9dfcdd3c",
228 "5d0a9d6d9f197c091bf054fac9cb60e11ec723d6610ed8578e617b4d46cb43d5",
229 }
230 keys = [][]byte{}
231 values = [][]byte{}
232 for i := 0; i < len(testvectorKeys); i++ {
233 key, err := hex.DecodeString(testvectorKeys[i])
234 c.Assert(err, qt.IsNil)
235 keys = append(keys, key)
236 values = append(values, []byte{0})
237 }
238
239 for i := 0; i < len(keys); i++ {
240 if err := tree1.Add(keys[i], values[i]); err != nil {
241 t.Fatal(err)
242 }
243 }
244
245 indexes, err = tree2.AddBatch(keys, values)
246 c.Assert(err, qt.IsNil)
247 c.Check(len(indexes), qt.Equals, 0)
248 // check that both trees roots are equal
249 checkRoots(c, tree1, tree2)
250}
251
252func TestAddBatchTestVector2(t *testing.T) {
253 // test vector with unbalanced tree
254 c := qt.New(t)
255
256 database, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
257 c.Assert(err, qt.IsNil)
258 tree1, err := NewTree(database, 256, HashFunctionPoseidon)
259 c.Assert(err, qt.IsNil)
260 defer tree1.db.Close() //nolint:errcheck
261
262 database2, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
263 c.Assert(err, qt.IsNil)
264 tree2, err := NewTree(database2, 256, HashFunctionPoseidon)
265 c.Assert(err, qt.IsNil)
266 defer tree2.db.Close() //nolint:errcheck
267
268 bLen := tree1.HashFunction().Len()
269 var keys, values [][]byte
270 // 1
271 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(1))))
272 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(1))))
273 // 2
274 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(2))))
275 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(2))))
276 // 3
277 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(3))))
278 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(3))))
279 // 5
280 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(5))))
281 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(5))))
282
283 for i := 0; i < len(keys); i++ {
284 if err := tree1.Add(keys[i], values[i]); err != nil {
285 t.Fatal(err)
286 }
287 }
288
289 indexes, err := tree2.AddBatch(keys, values)
290 c.Assert(err, qt.IsNil)
291 c.Check(len(indexes), qt.Equals, 0)
292
293 // check that both trees roots are equal
294 checkRoots(c, tree1, tree2)
295}
296
297func TestAddBatchTestVector3(t *testing.T) {
298 // test vector with unbalanced tree
299 c := qt.New(t)
300
301 database, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
302 c.Assert(err, qt.IsNil)
303 tree1, err := NewTree(database, 256, HashFunctionPoseidon)
304 c.Assert(err, qt.IsNil)
305 defer tree1.db.Close() //nolint:errcheck
306
307 database2, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
308 c.Assert(err, qt.IsNil)
309 tree2, err := NewTree(database2, 256, HashFunctionPoseidon)
310 c.Assert(err, qt.IsNil)
311 defer tree2.db.Close() //nolint:errcheck
312
313 bLen := tree1.HashFunction().Len()
314 var keys, values [][]byte
315 // 0
316 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(0))))
317 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(0))))
318 // 3
319 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(3))))
320 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(3))))
321 // 7
322 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(7))))
323 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(7))))
324 // 135
325 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(135))))
326 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(135))))
327
328 for i := 0; i < len(keys); i++ {
329 if err := tree1.Add(keys[i], values[i]); err != nil {
330 t.Fatal(err)
331 }
332 }
333
334 indexes, err := tree2.AddBatch(keys, values)
335 c.Assert(err, qt.IsNil)
336 c.Check(len(indexes), qt.Equals, 0)
337
338 // check that both trees roots are equal
339 checkRoots(c, tree1, tree2)
340 //
341 // tree1.PrintGraphvizFirstNLevels(nil, 100)
342 // tree2.PrintGraphvizFirstNLevels(nil, 100)
343}
344
345func TestAddBatchTreeEmptyRandomKeys(t *testing.T) {
346 c := qt.New(t)
347
348 nLeafs := 8
349
350 database1, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
351 c.Assert(err, qt.IsNil)
352 tree1, err := NewTree(database1, 256, HashFunctionBlake2b)
353 c.Assert(err, qt.IsNil)
354 defer tree1.db.Close() //nolint:errcheck
355
356 database2, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
357 c.Assert(err, qt.IsNil)
358 tree2, err := NewTree(database2, 256, HashFunctionBlake2b)
359 c.Assert(err, qt.IsNil)
360 defer tree2.db.Close() //nolint:errcheck
361
362 var keys, values [][]byte
363 for i := 0; i < nLeafs; i++ {
364 keys = append(keys, randomBytes(32))
365 values = append(values, randomBytes(32))
366 }
367
368 for i := 0; i < len(keys); i++ {
369 if err := tree1.Add(keys[i], values[i]); err != nil {
370 t.Fatal(err)
371 }
372 }
373
374 indexes, err := tree2.AddBatch(keys, values)
375 c.Assert(err, qt.IsNil)
376 c.Check(len(indexes), qt.Equals, 0)
377 // check that both trees roots are equal
378 checkRoots(c, tree1, tree2)
379}
380
381func TestAddBatchTreeNotEmptyFewLeafs(t *testing.T) {
382 c := qt.New(t)
383
384 nLeafs := 1024
385 initialNLeafs := 99
386
387 tree1, tree2 := testInit(c, initialNLeafs)
388 tree2.dbgInit()
389
390 bLen := tree1.HashFunction().Len()
391 start := time.Now()
392 for i := initialNLeafs; i < nLeafs; i++ {
393 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
394 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
395 if err := tree1.Add(k, v); err != nil {
396 t.Fatal(err)
397 }
398 }
399 time1 := time.Since(start)
400
401 // prepare the key-values to be added
402 var keys, values [][]byte
403 for i := initialNLeafs; i < nLeafs; i++ {
404 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
405 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
406 keys = append(keys, k)
407 values = append(values, v)
408 }
409 start = time.Now()
410 indexes, err := tree2.AddBatch(keys, values)
411 c.Assert(err, qt.IsNil)
412 time2 := time.Since(start)
413 if debug {
414 debugTime("Case tree not empty w/ few leafs, AddBatch", time1, time2)
415 printTestContext(" ", nLeafs, "Poseidon", "memory")
416 tree2.dbg.print(" ")
417 }
418 c.Check(len(indexes), qt.Equals, 0)
419
420 // check that both trees roots are equal
421 checkRoots(c, tree1, tree2)
422}
423
424func TestAddBatchTreeNotEmptyEnoughLeafs(t *testing.T) {
425 c := qt.New(t)
426
427 nLeafs := 1024
428 initialNLeafs := 500
429
430 tree1, tree2 := testInit(c, initialNLeafs)
431 tree2.dbgInit()
432
433 bLen := tree1.HashFunction().Len()
434 start := time.Now()
435 for i := initialNLeafs; i < nLeafs; i++ {
436 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
437 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
438 if err := tree1.Add(k, v); err != nil {
439 t.Fatal(err)
440 }
441 }
442 time1 := time.Since(start)
443
444 // prepare the key-values to be added
445 var keys, values [][]byte
446 for i := initialNLeafs; i < nLeafs; i++ {
447 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
448 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
449 keys = append(keys, k)
450 values = append(values, v)
451 }
452 start = time.Now()
453 indexes, err := tree2.AddBatch(keys, values)
454 c.Assert(err, qt.IsNil)
455 time2 := time.Since(start)
456 if debug {
457 debugTime("Case tree not empty w/ enough leafs, AddBatch", time1, time2)
458 printTestContext(" ", nLeafs, "Poseidon", "memory")
459 tree2.dbg.print(" ")
460 }
461 c.Check(len(indexes), qt.Equals, 0)
462 // check that both trees roots are equal
463 checkRoots(c, tree1, tree2)
464}
465
466func TestAddBatchTreeEmptyRepeatedLeafs(t *testing.T) {
467 c := qt.New(t)
468
469 nLeafs := 1024
470 nRepeatedKeys := 99
471
472 tree1, tree2 := testInit(c, 0)
473
474 bLen := tree1.HashFunction().Len()
475 // prepare the key-values to be added
476 var keys, values [][]byte
477 for i := 0; i < nLeafs; i++ {
478 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
479 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
480 keys = append(keys, k)
481 values = append(values, v)
482 }
483 // add repeated key-values
484 for i := 0; i < nRepeatedKeys; i++ {
485 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
486 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
487 keys = append(keys, k)
488 values = append(values, v)
489 }
490
491 // add the non-repeated key-values in tree1 with .Add loop
492 for i := 0; i < nLeafs; i++ {
493 if err := tree1.Add(keys[i], values[i]); err != nil {
494 t.Fatal(err)
495 }
496 }
497
498 indexes, err := tree2.AddBatch(keys, values)
499 c.Assert(err, qt.IsNil)
500 c.Check(len(indexes), qt.Equals, nRepeatedKeys)
501 // check that both trees roots are equal
502 checkRoots(c, tree1, tree2)
503}
504
505func TestAddBatchTreeNotEmptyFewLeafsRepeatedLeafs(t *testing.T) {
506 c := qt.New(t)
507
508 nLeafs := 1024
509 initialNLeafs := 99
510
511 tree1, tree2 := testInit(c, initialNLeafs)
512
513 bLen := tree1.HashFunction().Len()
514 // prepare the key-values to be added
515 var keys, values [][]byte
516 for i := 0; i < nLeafs; i++ {
517 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
518 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
519 keys = append(keys, k)
520 values = append(values, v)
521 }
522
523 // add the keys that will be existing when AddBatch is called
524 for i := initialNLeafs; i < nLeafs; i++ {
525 if err := tree1.Add(keys[i], values[i]); err != nil {
526 t.Fatal(err)
527 }
528 }
529
530 indexes, err := tree2.AddBatch(keys, values)
531 c.Assert(err, qt.IsNil)
532 c.Check(len(indexes), qt.Equals, initialNLeafs)
533 // check that both trees roots are equal
534 checkRoots(c, tree1, tree2)
535}
536
537func TestSplitInBuckets(t *testing.T) {
538 c := qt.New(t)
539
540 bLen := HashFunctionPoseidon.Len()
541 nLeafs := 16
542 kvs := make([]kv, nLeafs)
543 for i := 0; i < nLeafs; i++ {
544 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
545 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
546 keyPath := make([]byte, 32)
547 copy(keyPath[:], k)
548 kvs[i].pos = i
549 kvs[i].keyPath = k
550 kvs[i].k = k
551 kvs[i].v = v
552 }
553
554 // check keyToBucket results for 4 buckets & 8 keys
555 c.Assert(keyToBucket(kvs[0].k, 4), qt.Equals, 0)
556 c.Assert(keyToBucket(kvs[1].k, 4), qt.Equals, 2)
557 c.Assert(keyToBucket(kvs[2].k, 4), qt.Equals, 1)
558 c.Assert(keyToBucket(kvs[3].k, 4), qt.Equals, 3)
559 c.Assert(keyToBucket(kvs[4].k, 4), qt.Equals, 0)
560 c.Assert(keyToBucket(kvs[5].k, 4), qt.Equals, 2)
561 c.Assert(keyToBucket(kvs[6].k, 4), qt.Equals, 1)
562 c.Assert(keyToBucket(kvs[7].k, 4), qt.Equals, 3)
563
564 // check keyToBucket results for 8 buckets & 8 keys
565 c.Assert(keyToBucket(kvs[0].k, 8), qt.Equals, 0)
566 c.Assert(keyToBucket(kvs[1].k, 8), qt.Equals, 4)
567 c.Assert(keyToBucket(kvs[2].k, 8), qt.Equals, 2)
568 c.Assert(keyToBucket(kvs[3].k, 8), qt.Equals, 6)
569 c.Assert(keyToBucket(kvs[4].k, 8), qt.Equals, 1)
570 c.Assert(keyToBucket(kvs[5].k, 8), qt.Equals, 5)
571 c.Assert(keyToBucket(kvs[6].k, 8), qt.Equals, 3)
572 c.Assert(keyToBucket(kvs[7].k, 8), qt.Equals, 7)
573
574 buckets := splitInBuckets(kvs, 4)
575
576 expected := [][]string{
577 {
578 "00000000", // bucket 0
579 "08000000",
580 "04000000",
581 "0c000000",
582 },
583 {
584 "02000000", // bucket 1
585 "0a000000",
586 "06000000",
587 "0e000000",
588 },
589 {
590 "01000000", // bucket 2
591 "09000000",
592 "05000000",
593 "0d000000",
594 },
595 {
596 "03000000", // bucket 3
597 "0b000000",
598 "07000000",
599 "0f000000",
600 },
601 }
602
603 for i := 0; i < len(buckets); i++ {
604 sortKvs(buckets[i])
605 c.Assert(len(buckets[i]), qt.Equals, len(expected[i]))
606 for j := 0; j < len(buckets[i]); j++ {
607 c.Check(hex.EncodeToString(buckets[i][j].k[:4]),
608 qt.Equals, expected[i][j])
609 }
610 }
611}
612
613// compareBytes compares byte slices where the bytes are compared from left to
614// right and each byte is compared by bit from right to left
615func compareBytes(a, b []byte) bool {
616 // WIP
617 for i := 0; i < len(a); i++ {
618 for j := 0; j < 8; j++ {
619 aBit := a[i] & (1 << j)
620 bBit := b[i] & (1 << j)
621 if aBit > bBit {
622 return false
623 } else if aBit < bBit {
624 return true
625 }
626 }
627 }
628 return false
629}
630
631// sortKvs sorts the kv by path
632func sortKvs(kvs []kv) {
633 sort.Slice(kvs, func(i, j int) bool {
634 return compareBytes(kvs[i].keyPath, kvs[j].keyPath)
635 })
636}
637
638func TestAddBatchTreeNotEmpty(t *testing.T) {
639 c := qt.New(t)
640
641 nLeafs := 4096
642 initialNLeafs := 900
643
644 tree1, tree2 := testInit(c, initialNLeafs)
645 tree2.dbgInit()
646
647 bLen := tree1.HashFunction().Len()
648 start := time.Now()
649 for i := initialNLeafs; i < nLeafs; i++ {
650 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
651 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
652 if err := tree1.Add(k, v); err != nil {
653 t.Fatal(err)
654 }
655 }
656 time1 := time.Since(start)
657
658 // prepare the key-values to be added
659 var keys, values [][]byte
660 for i := initialNLeafs; i < nLeafs; i++ {
661 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
662 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
663 keys = append(keys, k)
664 values = append(values, v)
665 }
666 start = time.Now()
667 indexes, err := tree2.AddBatch(keys, values)
668 c.Assert(err, qt.IsNil)
669 time2 := time.Since(start)
670 if debug {
671 debugTime("Case tree not empty, AddBatch", time1, time2)
672 printTestContext(" ", nLeafs, "Poseidon", "memory")
673 tree2.dbg.print(" ")
674 }
675 c.Check(len(indexes), qt.Equals, 0)
676
677 // check that both trees roots are equal
678 checkRoots(c, tree1, tree2)
679}
680
681func TestAddBatchNotEmptyUnbalanced(t *testing.T) {
682 c := qt.New(t)
683
684 nLeafs := 4096
685 initialNLeafs := 900
686
687 tree1, _ := testInit(c, initialNLeafs)
688 bLen := tree1.HashFunction().Len()
689
690 start := time.Now()
691 for i := initialNLeafs; i < nLeafs; i++ {
692 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
693 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
694 if err := tree1.Add(k, v); err != nil {
695 t.Fatal(err)
696 }
697 }
698 time1 := time.Since(start)
699
700 database2, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
701 c.Assert(err, qt.IsNil)
702 tree2, err := NewTree(database2, 256, HashFunctionPoseidon)
703 c.Assert(err, qt.IsNil)
704 defer tree2.db.Close() //nolint:errcheck
705 tree2.dbgInit()
706
707 var keys, values [][]byte
708 // add the initial leafs to fill a bit the tree before calling the
709 // AddBatch method
710 for i := 0; i < initialNLeafs; i++ {
711 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
712 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
713 // use only the keys of one bucket, store the not used ones for
714 // later
715 if i%4 != 0 {
716 keys = append(keys, k)
717 values = append(values, v)
718 continue
719 }
720 if err := tree2.Add(k, v); err != nil {
721 t.Fatal(err)
722 }
723 }
724
725 for i := initialNLeafs; i < nLeafs; i++ {
726 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
727 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
728 keys = append(keys, k)
729 values = append(values, v)
730 }
731 start = time.Now()
732 indexes, err := tree2.AddBatch(keys, values)
733 c.Assert(err, qt.IsNil)
734 time2 := time.Since(start)
735 if debug {
736 debugTime("Case tree not empty & unbalanced, AddBatch", time1, time2)
737 printTestContext(" ", nLeafs, "Poseidon", "memory")
738 tree2.dbg.print(" ")
739 }
740 c.Check(len(indexes), qt.Equals, 0)
741
742 // check that both trees roots are equal
743 checkRoots(c, tree1, tree2)
744}
745
746func TestFlp2(t *testing.T) {
747 c := qt.New(t)
748 c.Assert(flp2(31), qt.Equals, 16)
749 c.Assert(flp2(32), qt.Equals, 32)
750 c.Assert(flp2(33), qt.Equals, 32)
751 c.Assert(flp2(63), qt.Equals, 32)
752 c.Assert(flp2(64), qt.Equals, 64)
753 c.Assert(flp2(9000), qt.Equals, 8192)
754}
755
756func TestAddBatchBench(t *testing.T) {
757 nLeafs := 50_000
758 printTestContext("TestAddBatchBench: ", nLeafs, "Blake2b", "badgerdb")
759
760 // prepare inputs
761 var ks, vs [][]byte
762 for i := 0; i < nLeafs; i++ {
763 k := randomBytes(32)
764 v := randomBytes(32)
765 ks = append(ks, k)
766 vs = append(vs, v)
767 }
768
769 benchAdd(t, ks, vs)
770
771 benchAddBatch(t, ks, vs)
772}
773
774func benchAdd(t *testing.T, ks, vs [][]byte) {
775 c := qt.New(t)
776
777 database, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
778 c.Assert(err, qt.IsNil)
779 tree, err := NewTree(database, 256, HashFunctionBlake2b)
780 c.Assert(err, qt.IsNil)
781 defer tree.db.Close() //nolint:errcheck
782
783 start := time.Now()
784 for i := 0; i < len(ks); i++ {
785 err = tree.Add(ks[i], vs[i])
786 c.Assert(err, qt.IsNil)
787 }
788 if debug {
789 printRes(" Add loop", time.Since(start))
790 tree.dbg.print(" ")
791 }
792}
793
794func benchAddBatch(t *testing.T, ks, vs [][]byte) {
795 c := qt.New(t)
796
797 database, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
798 c.Assert(err, qt.IsNil)
799 tree, err := NewTree(database, 256, HashFunctionBlake2b)
800 c.Assert(err, qt.IsNil)
801 defer tree.db.Close() //nolint:errcheck
802
803 tree.dbgInit()
804
805 start := time.Now()
806 invalids, err := tree.AddBatch(ks, vs)
807 if debug {
808 printRes(" AddBatch", time.Since(start))
809 tree.dbg.print(" ")
810 }
811 c.Assert(err, qt.IsNil)
812 c.Assert(len(invalids), qt.Equals, 0)
813}
814
815func TestDbgStats(t *testing.T) {
816 c := qt.New(t)
817
818 nLeafs := 10_000
819
820 // prepare inputs
821 var ks, vs [][]byte
822 for i := 0; i < nLeafs; i++ {
823 k := randomBytes(32)
824 v := randomBytes(32)
825 ks = append(ks, k)
826 vs = append(vs, v)
827 }
828
829 // 1
830 database1, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
831 c.Assert(err, qt.IsNil)
832 tree1, err := NewTree(database1, 256, HashFunctionBlake2b)
833 c.Assert(err, qt.IsNil)
834 defer tree1.db.Close() //nolint:errcheck
835
836 tree1.dbgInit()
837
838 for i := 0; i < len(ks); i++ {
839 err = tree1.Add(ks[i], vs[i])
840 c.Assert(err, qt.IsNil)
841 }
842
843 // 2
844 database2, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
845 c.Assert(err, qt.IsNil)
846 tree2, err := NewTree(database2, 256, HashFunctionBlake2b)
847 c.Assert(err, qt.IsNil)
848 defer tree2.db.Close() //nolint:errcheck
849
850 tree2.dbgInit()
851
852 invalids, err := tree2.AddBatch(ks, vs)
853 c.Assert(err, qt.IsNil)
854 c.Assert(len(invalids), qt.Equals, 0)
855
856 // 3
857 database3, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
858 c.Assert(err, qt.IsNil)
859 tree3, err := NewTree(database3, 256, HashFunctionBlake2b)
860 c.Assert(err, qt.IsNil)
861 defer tree3.db.Close() //nolint:errcheck
862
863 tree3.dbgInit()
864
865 // add few key-values
866 // invalids, err = tree3.AddBatch(ks[:], vs[:])
867 invalids, err = tree3.AddBatch(ks[:1000], vs[:1000])
868 c.Assert(err, qt.IsNil)
869 c.Assert(len(invalids), qt.Equals, 0)
870
871 // add the rest of key-values
872 invalids, err = tree3.AddBatch(ks[1000:], vs[1000:])
873 c.Assert(err, qt.IsNil)
874 c.Assert(len(invalids), qt.Equals, 0)
875
876 checkRoots(c, tree1, tree2)
877 checkRoots(c, tree1, tree3)
878
879 if debug {
880 fmt.Println("TestDbgStats")
881 tree1.dbg.print(" add in loop in emptyTree ")
882 tree2.dbg.print(" addbatch caseEmptyTree ")
883 tree3.dbg.print(" addbatch caseNotEmptyTree ")
884 }
885}
886
887func TestLoadVT(t *testing.T) {
888 c := qt.New(t)
889
890 nLeafs := 1024
891
892 database, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
893 c.Assert(err, qt.IsNil)
894 tree, err := NewTree(database, 256, HashFunctionPoseidon)
895 c.Assert(err, qt.IsNil)
896 defer tree.db.Close() //nolint:errcheck
897
898 var keys, values [][]byte
899 for i := 0; i < nLeafs; i++ {
900 k := randomBytes(31)
901 v := randomBytes(31)
902 keys = append(keys, k)
903 values = append(values, v)
904 }
905 indexes, err := tree.AddBatch(keys, values)
906 c.Assert(err, qt.IsNil)
907 c.Check(len(indexes), qt.Equals, 0)
908
909 rTx := tree.db.ReadTx()
910 defer rTx.Discard()
911 vt, err := tree.loadVT(rTx)
912 c.Assert(err, qt.IsNil)
913 _, err = vt.computeHashes()
914 c.Assert(err, qt.IsNil)
915
916 // check that tree & vt roots are equal
917 root, err := tree.Root()
918 c.Assert(err, qt.IsNil)
919 c.Check(root, qt.DeepEquals, vt.root.h)
920}
921
922// TestAddKeysWithEmptyValues calls AddBatch giving an array of empty values
923func TestAddKeysWithEmptyValues(t *testing.T) {
924 c := qt.New(t)
925
926 nLeafs := 1024
927
928 database, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
929 c.Assert(err, qt.IsNil)
930 tree, err := NewTree(database, 256, HashFunctionPoseidon)
931 c.Assert(err, qt.IsNil)
932 defer tree.db.Close() //nolint:errcheck
933
934 bLen := 32
935 var keys, values [][]byte
936 for i := 0; i < nLeafs; i++ {
937 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
938 v := []byte{}
939 keys = append(keys, k)
940 values = append(values, v)
941 }
942
943 for i := 0; i < nLeafs; i++ {
944 if err := tree.Add(keys[i], values[i]); err != nil {
945 t.Fatal(err)
946 }
947 }
948
949 database2, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
950 c.Assert(err, qt.IsNil)
951 tree2, err := NewTree(database2, 256, HashFunctionPoseidon)
952 c.Assert(err, qt.IsNil)
953 defer tree2.db.Close() //nolint:errcheck
954 tree2.dbgInit()
955
956 indexes, err := tree2.AddBatch(keys, values)
957 c.Assert(err, qt.IsNil)
958 c.Check(len(indexes), qt.Equals, 0)
959 // check that both trees roots are equal
960 checkRoots(c, tree, tree2)
961
962 // use tree3 to add nil value array
963 database3, err := badgerdb.New(badgerdb.Options{Path: c.TempDir()})
964 c.Assert(err, qt.IsNil)
965 tree3, err := NewTree(database3, 256, HashFunctionPoseidon)
966 c.Assert(err, qt.IsNil)
967 defer tree3.db.Close() //nolint:errcheck
968
969 indexes, err = tree3.AddBatch(keys, nil)
970 c.Assert(err, qt.IsNil)
971 c.Check(len(indexes), qt.Equals, 0)
972 checkRoots(c, tree, tree3)
973
974 kAux, proofV, siblings, existence, err := tree2.GenProof(keys[9])
975 c.Assert(err, qt.IsNil)
976 c.Assert(proofV, qt.DeepEquals, values[9])
977 c.Assert(keys[9], qt.DeepEquals, kAux)
978 c.Assert(existence, qt.IsTrue)
979
980 // check with empty array
981 root, err := tree.Root()
982 c.Assert(err, qt.IsNil)
983 verif, err := CheckProof(tree.hashFunction, keys[9], []byte{}, root, siblings)
984 c.Assert(err, qt.IsNil)
985 c.Check(verif, qt.IsTrue)
986
987 // check with array with only 1 zero
988 verif, err = CheckProof(tree.hashFunction, keys[9], []byte{0}, root, siblings)
989 c.Assert(err, qt.IsNil)
990 c.Check(verif, qt.IsTrue)
991
992 // check with array with 32 zeroes
993 e32 := []byte{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
994 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
995 c.Assert(len(e32), qt.Equals, 32)
996 verif, err = CheckProof(tree.hashFunction, keys[9], e32, root, siblings)
997 c.Assert(err, qt.IsNil)
998 c.Check(verif, qt.IsTrue)
999
1000 // check with array with value!=0 returns false at verification
1001 verif, err = CheckProof(tree.hashFunction, keys[9], []byte{0, 1}, root, siblings)
1002 c.Assert(err, qt.IsNil)
1003 c.Check(verif, qt.IsFalse)
1004}
1005
1006// TODO test adding batch with multiple invalid keys
1007// TODO for tests of AddBatch, if the root does not match the Add root, bulk
1008// all the leafs of both trees into a log file to later be able to debug and
1009// recreate the case