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"
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 := db.NewBadgerDB(c.TempDir())
41 c.Assert(err, qt.IsNil)
42 tree1, err := NewTree(database1, 100, HashFunctionPoseidon)
43 c.Assert(err, qt.IsNil)
44
45 database2, err := db.NewBadgerDB(c.TempDir())
46 c.Assert(err, qt.IsNil)
47 tree2, err := NewTree(database2, 100, 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 := db.NewBadgerDB(c.TempDir())
72 c.Assert(err, qt.IsNil)
73 tree, err := NewTree(database, 100, HashFunctionPoseidon)
74 c.Assert(err, qt.IsNil)
75 defer tree.db.Close() //nolint:errcheck //nolint:errcheck
76
77 bLen := tree.HashFunction().Len()
78 start := time.Now()
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 if err := tree.Add(k, v); err != nil {
83 t.Fatal(err)
84 }
85 }
86 time1 := time.Since(start)
87
88 database2, err := db.NewBadgerDB(c.TempDir())
89 c.Assert(err, qt.IsNil)
90 tree2, err := NewTree(database2, 100, HashFunctionPoseidon)
91 c.Assert(err, qt.IsNil)
92 defer tree2.db.Close() //nolint:errcheck //nolint:errcheck
93 tree2.dbgInit()
94
95 var keys, values [][]byte
96 for i := 0; i < nLeafs; i++ {
97 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
98 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
99 keys = append(keys, k)
100 values = append(values, v)
101 }
102 start = time.Now()
103 indexes, err := tree2.AddBatch(keys, values)
104 c.Assert(err, qt.IsNil)
105 time2 := time.Since(start)
106 if debug {
107 debugTime("Case tree empty, AddBatch", time1, time2)
108 printTestContext(" ", nLeafs, "Poseidon", "memory")
109 tree2.dbg.print(" ")
110 }
111 c.Check(len(indexes), qt.Equals, 0)
112
113 // check that both trees roots are equal
114 c.Check(tree2.Root(), qt.DeepEquals, tree.Root())
115}
116
117func TestAddBatchTreeEmptyNotPowerOf2(t *testing.T) {
118 c := qt.New(t)
119
120 nLeafs := 1027
121
122 database, err := db.NewBadgerDB(c.TempDir())
123 c.Assert(err, qt.IsNil)
124 tree, err := NewTree(database, 100, HashFunctionPoseidon)
125 c.Assert(err, qt.IsNil)
126 defer tree.db.Close() //nolint:errcheck
127
128 bLen := tree.HashFunction().Len()
129 for i := 0; i < nLeafs; i++ {
130 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
131 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
132 if err := tree.Add(k, v); err != nil {
133 t.Fatal(err)
134 }
135 }
136
137 database2, err := db.NewBadgerDB(c.TempDir())
138 c.Assert(err, qt.IsNil)
139 tree2, err := NewTree(database2, 100, HashFunctionPoseidon)
140 c.Assert(err, qt.IsNil)
141 defer tree2.db.Close() //nolint:errcheck
142
143 var keys, values [][]byte
144 for i := 0; i < nLeafs; i++ {
145 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
146 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
147 keys = append(keys, k)
148 values = append(values, v)
149 }
150 indexes, err := tree2.AddBatch(keys, values)
151 c.Assert(err, qt.IsNil)
152 c.Check(len(indexes), qt.Equals, 0)
153
154 // check that both trees roots are equal
155 c.Check(tree2.Root(), qt.DeepEquals, tree.Root())
156}
157
158func randomBytes(n int) []byte {
159 b := make([]byte, n)
160 _, err := rand.Read(b)
161 if err != nil {
162 panic(err)
163 }
164 return b
165}
166
167func TestAddBatchTreeEmptyTestVector(t *testing.T) {
168 c := qt.New(t)
169 database1, err := db.NewBadgerDB(c.TempDir())
170 c.Assert(err, qt.IsNil)
171 tree1, err := NewTree(database1, 100, HashFunctionBlake2b)
172 c.Assert(err, qt.IsNil)
173 defer tree1.db.Close() //nolint:errcheck
174
175 database2, err := db.NewBadgerDB(c.TempDir())
176 c.Assert(err, qt.IsNil)
177 tree2, err := NewTree(database2, 100, HashFunctionBlake2b)
178 c.Assert(err, qt.IsNil)
179 defer tree2.db.Close() //nolint:errcheck
180
181 // leafs in 2nd level subtrees: [ 6, 0, 1, 1]
182 testvectorKeys := []string{
183 "1c7c2265e368314ca58ed2e1f33a326f1220e234a566d55c3605439dbe411642",
184 "2c9f0a578afff5bfa4e0992a43066460faaab9e8e500db0b16647c701cdb16bf",
185 "1c45cb31f2fa39ec7b9ebf0fad40e0b8296016b5ce8844ae06ff77226379d9a5",
186 "d8af98bbbb585129798ae54d5eabbc9d0561d583faf1663b3a3724d15bda4ec7",
187 }
188 var keys, values [][]byte
189 for i := 0; i < len(testvectorKeys); i++ {
190 key, err := hex.DecodeString(testvectorKeys[i])
191 c.Assert(err, qt.IsNil)
192 keys = append(keys, key)
193 values = append(values, []byte{0})
194 }
195
196 for i := 0; i < len(keys); i++ {
197 if err := tree1.Add(keys[i], values[i]); err != nil {
198 t.Fatal(err)
199 }
200 }
201
202 indexes, err := tree2.AddBatch(keys, values)
203 c.Assert(err, qt.IsNil)
204 c.Check(len(indexes), qt.Equals, 0)
205 // check that both trees roots are equal
206 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
207
208 // 2nd test vectors
209 database1, err = db.NewBadgerDB(c.TempDir())
210 c.Assert(err, qt.IsNil)
211 tree1, err = NewTree(database1, 100, HashFunctionBlake2b)
212 c.Assert(err, qt.IsNil)
213 defer tree1.db.Close() //nolint:errcheck
214
215 database2, err = db.NewBadgerDB(c.TempDir())
216 c.Assert(err, qt.IsNil)
217 tree2, err = NewTree(database2, 100, HashFunctionBlake2b)
218 c.Assert(err, qt.IsNil)
219 defer tree2.db.Close() //nolint:errcheck
220
221 testvectorKeys = []string{
222 "1c7c2265e368314ca58ed2e1f33a326f1220e234a566d55c3605439dbe411642",
223 "2c9f0a578afff5bfa4e0992a43066460faaab9e8e500db0b16647c701cdb16bf",
224 "9cb87ec67e875c61390edcd1ab517f443591047709a4d4e45b0f9ed980857b8e",
225 "9b4e9e92e974a589f426ceeb4cb291dc24893513fecf8e8460992dcf52621d4d",
226 "1c45cb31f2fa39ec7b9ebf0fad40e0b8296016b5ce8844ae06ff77226379d9a5",
227 "d8af98bbbb585129798ae54d5eabbc9d0561d583faf1663b3a3724d15bda4ec7",
228 "3cd55dbfb8f975f20a0925dfbdabe79fa2d51dd0268afbb8ba6b01de9dfcdd3c",
229 "5d0a9d6d9f197c091bf054fac9cb60e11ec723d6610ed8578e617b4d46cb43d5",
230 }
231 keys = [][]byte{}
232 values = [][]byte{}
233 for i := 0; i < len(testvectorKeys); i++ {
234 key, err := hex.DecodeString(testvectorKeys[i])
235 c.Assert(err, qt.IsNil)
236 keys = append(keys, key)
237 values = append(values, []byte{0})
238 }
239
240 for i := 0; i < len(keys); i++ {
241 if err := tree1.Add(keys[i], values[i]); err != nil {
242 t.Fatal(err)
243 }
244 }
245
246 indexes, err = tree2.AddBatch(keys, values)
247 c.Assert(err, qt.IsNil)
248 c.Check(len(indexes), qt.Equals, 0)
249 // check that both trees roots are equal
250 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
251}
252
253func TestAddBatchTreeEmptyRandomKeys(t *testing.T) {
254 c := qt.New(t)
255
256 nLeafs := 8
257
258 database1, err := db.NewBadgerDB(c.TempDir())
259 c.Assert(err, qt.IsNil)
260 tree1, err := NewTree(database1, 100, HashFunctionBlake2b)
261 c.Assert(err, qt.IsNil)
262 defer tree1.db.Close() //nolint:errcheck
263
264 database2, err := db.NewBadgerDB(c.TempDir())
265 c.Assert(err, qt.IsNil)
266 tree2, err := NewTree(database2, 100, HashFunctionBlake2b)
267 c.Assert(err, qt.IsNil)
268 defer tree2.db.Close() //nolint:errcheck
269
270 var keys, values [][]byte
271 for i := 0; i < nLeafs; i++ {
272 keys = append(keys, randomBytes(32))
273 values = append(values, randomBytes(32))
274 }
275
276 for i := 0; i < len(keys); i++ {
277 if err := tree1.Add(keys[i], values[i]); err != nil {
278 t.Fatal(err)
279 }
280 }
281
282 indexes, err := tree2.AddBatch(keys, values)
283 c.Assert(err, qt.IsNil)
284 c.Check(len(indexes), qt.Equals, 0)
285 // check that both trees roots are equal
286 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
287}
288
289func TestAddBatchTreeNotEmptyFewLeafs(t *testing.T) {
290 c := qt.New(t)
291
292 nLeafs := 1024
293 initialNLeafs := 99
294
295 tree1, tree2 := testInit(c, initialNLeafs)
296 tree2.dbgInit()
297
298 bLen := tree1.HashFunction().Len()
299 start := time.Now()
300 for i := initialNLeafs; i < nLeafs; i++ {
301 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
302 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
303 if err := tree1.Add(k, v); err != nil {
304 t.Fatal(err)
305 }
306 }
307 time1 := time.Since(start)
308
309 // prepare the key-values to be added
310 var keys, values [][]byte
311 for i := initialNLeafs; i < nLeafs; i++ {
312 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
313 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
314 keys = append(keys, k)
315 values = append(values, v)
316 }
317 start = time.Now()
318 indexes, err := tree2.AddBatch(keys, values)
319 c.Assert(err, qt.IsNil)
320 time2 := time.Since(start)
321 if debug {
322 debugTime("Case tree not empty w/ few leafs, AddBatch", time1, time2)
323 printTestContext(" ", nLeafs, "Poseidon", "memory")
324 tree2.dbg.print(" ")
325 }
326 c.Check(len(indexes), qt.Equals, 0)
327
328 // check that both trees roots are equal
329 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
330}
331
332func TestAddBatchTreeNotEmptyEnoughLeafs(t *testing.T) {
333 c := qt.New(t)
334
335 nLeafs := 1024
336 initialNLeafs := 500
337
338 tree1, tree2 := testInit(c, initialNLeafs)
339 tree2.dbgInit()
340
341 bLen := tree1.HashFunction().Len()
342 start := time.Now()
343 for i := initialNLeafs; i < nLeafs; i++ {
344 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
345 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
346 if err := tree1.Add(k, v); err != nil {
347 t.Fatal(err)
348 }
349 }
350 time1 := time.Since(start)
351
352 // prepare the key-values to be added
353 var keys, values [][]byte
354 for i := initialNLeafs; i < nLeafs; i++ {
355 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
356 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
357 keys = append(keys, k)
358 values = append(values, v)
359 }
360 start = time.Now()
361 indexes, err := tree2.AddBatch(keys, values)
362 c.Assert(err, qt.IsNil)
363 time2 := time.Since(start)
364 if debug {
365 debugTime("Case tree not empty w/ enough leafs, AddBatch", time1, time2)
366 printTestContext(" ", nLeafs, "Poseidon", "memory")
367 tree2.dbg.print(" ")
368 }
369 c.Check(len(indexes), qt.Equals, 0)
370 // check that both trees roots are equal
371 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
372}
373
374func TestAddBatchTreeEmptyRepeatedLeafs(t *testing.T) {
375 c := qt.New(t)
376
377 nLeafs := 1024
378 nRepeatedKeys := 99
379
380 tree1, tree2 := testInit(c, 0)
381
382 bLen := tree1.HashFunction().Len()
383 // prepare the key-values to be added
384 var keys, values [][]byte
385 for i := 0; i < nLeafs; i++ {
386 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
387 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
388 keys = append(keys, k)
389 values = append(values, v)
390 }
391 // add repeated key-values
392 for i := 0; i < nRepeatedKeys; i++ {
393 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
394 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
395 keys = append(keys, k)
396 values = append(values, v)
397 }
398
399 // add the non-repeated key-values in tree1 with .Add loop
400 for i := 0; i < nLeafs; i++ {
401 if err := tree1.Add(keys[i], values[i]); err != nil {
402 t.Fatal(err)
403 }
404 }
405
406 indexes, err := tree2.AddBatch(keys, values)
407 c.Assert(err, qt.IsNil)
408 c.Check(len(indexes), qt.Equals, nRepeatedKeys)
409 // check that both trees roots are equal
410 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
411}
412
413func TestAddBatchTreeNotEmptyFewLeafsRepeatedLeafs(t *testing.T) {
414 c := qt.New(t)
415
416 nLeafs := 1024
417 initialNLeafs := 99
418
419 tree1, tree2 := testInit(c, initialNLeafs)
420
421 bLen := tree1.HashFunction().Len()
422 // prepare the key-values to be added
423 var keys, values [][]byte
424 for i := 0; i < nLeafs; i++ {
425 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
426 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
427 keys = append(keys, k)
428 values = append(values, v)
429 }
430
431 // add the keys that will be existing when AddBatch is called
432 for i := initialNLeafs; i < nLeafs; i++ {
433 if err := tree1.Add(keys[i], values[i]); err != nil {
434 t.Fatal(err)
435 }
436 }
437
438 indexes, err := tree2.AddBatch(keys, values)
439 c.Assert(err, qt.IsNil)
440 c.Check(len(indexes), qt.Equals, initialNLeafs)
441 // check that both trees roots are equal
442 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
443}
444
445func TestSplitInBuckets(t *testing.T) {
446 c := qt.New(t)
447
448 bLen := HashFunctionPoseidon.Len()
449 nLeafs := 16
450 kvs := make([]kv, nLeafs)
451 for i := 0; i < nLeafs; i++ {
452 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
453 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
454 keyPath := make([]byte, 32)
455 copy(keyPath[:], k)
456 kvs[i].pos = i
457 kvs[i].keyPath = k
458 kvs[i].k = k
459 kvs[i].v = v
460 }
461
462 // check keyToBucket results for 4 buckets & 8 keys
463 c.Assert(keyToBucket(kvs[0].k, 4), qt.Equals, 0)
464 c.Assert(keyToBucket(kvs[1].k, 4), qt.Equals, 2)
465 c.Assert(keyToBucket(kvs[2].k, 4), qt.Equals, 1)
466 c.Assert(keyToBucket(kvs[3].k, 4), qt.Equals, 3)
467 c.Assert(keyToBucket(kvs[4].k, 4), qt.Equals, 0)
468 c.Assert(keyToBucket(kvs[5].k, 4), qt.Equals, 2)
469 c.Assert(keyToBucket(kvs[6].k, 4), qt.Equals, 1)
470 c.Assert(keyToBucket(kvs[7].k, 4), qt.Equals, 3)
471
472 // check keyToBucket results for 8 buckets & 8 keys
473 c.Assert(keyToBucket(kvs[0].k, 8), qt.Equals, 0)
474 c.Assert(keyToBucket(kvs[1].k, 8), qt.Equals, 4)
475 c.Assert(keyToBucket(kvs[2].k, 8), qt.Equals, 2)
476 c.Assert(keyToBucket(kvs[3].k, 8), qt.Equals, 6)
477 c.Assert(keyToBucket(kvs[4].k, 8), qt.Equals, 1)
478 c.Assert(keyToBucket(kvs[5].k, 8), qt.Equals, 5)
479 c.Assert(keyToBucket(kvs[6].k, 8), qt.Equals, 3)
480 c.Assert(keyToBucket(kvs[7].k, 8), qt.Equals, 7)
481
482 buckets := splitInBuckets(kvs, 4)
483
484 expected := [][]string{
485 {
486 "00000000", // bucket 0
487 "08000000",
488 "04000000",
489 "0c000000",
490 },
491 {
492 "02000000", // bucket 1
493 "0a000000",
494 "06000000",
495 "0e000000",
496 },
497 {
498 "01000000", // bucket 2
499 "09000000",
500 "05000000",
501 "0d000000",
502 },
503 {
504 "03000000", // bucket 3
505 "0b000000",
506 "07000000",
507 "0f000000",
508 },
509 }
510
511 for i := 0; i < len(buckets); i++ {
512 sortKvs(buckets[i])
513 c.Assert(len(buckets[i]), qt.Equals, len(expected[i]))
514 for j := 0; j < len(buckets[i]); j++ {
515 c.Check(hex.EncodeToString(buckets[i][j].k[:4]),
516 qt.Equals, expected[i][j])
517 }
518 }
519}
520
521// compareBytes compares byte slices where the bytes are compared from left to
522// right and each byte is compared by bit from right to left
523func compareBytes(a, b []byte) bool {
524 // WIP
525 for i := 0; i < len(a); i++ {
526 for j := 0; j < 8; j++ {
527 aBit := a[i] & (1 << j)
528 bBit := b[i] & (1 << j)
529 if aBit > bBit {
530 return false
531 } else if aBit < bBit {
532 return true
533 }
534 }
535 }
536 return false
537}
538
539// sortKvs sorts the kv by path
540func sortKvs(kvs []kv) {
541 sort.Slice(kvs, func(i, j int) bool {
542 return compareBytes(kvs[i].keyPath, kvs[j].keyPath)
543 })
544}
545
546func TestAddBatchTreeNotEmpty(t *testing.T) {
547 c := qt.New(t)
548
549 nLeafs := 4096
550 initialNLeafs := 900
551
552 tree1, tree2 := testInit(c, initialNLeafs)
553 tree2.dbgInit()
554
555 bLen := tree1.HashFunction().Len()
556 start := time.Now()
557 for i := initialNLeafs; i < nLeafs; i++ {
558 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
559 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
560 if err := tree1.Add(k, v); err != nil {
561 t.Fatal(err)
562 }
563 }
564 time1 := time.Since(start)
565
566 // prepare the key-values to be added
567 var keys, values [][]byte
568 for i := initialNLeafs; i < nLeafs; i++ {
569 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
570 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
571 keys = append(keys, k)
572 values = append(values, v)
573 }
574 start = time.Now()
575 indexes, err := tree2.AddBatch(keys, values)
576 c.Assert(err, qt.IsNil)
577 time2 := time.Since(start)
578 if debug {
579 debugTime("Case tree not empty, AddBatch", time1, time2)
580 printTestContext(" ", nLeafs, "Poseidon", "memory")
581 tree2.dbg.print(" ")
582 }
583 c.Check(len(indexes), qt.Equals, 0)
584
585 // check that both trees roots are equal
586 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
587}
588
589func TestAddBatchNotEmptyUnbalanced(t *testing.T) {
590 c := qt.New(t)
591
592 nLeafs := 4096
593 initialNLeafs := 900
594
595 tree1, _ := testInit(c, initialNLeafs)
596 bLen := tree1.HashFunction().Len()
597
598 start := time.Now()
599 for i := initialNLeafs; i < nLeafs; i++ {
600 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
601 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
602 if err := tree1.Add(k, v); err != nil {
603 t.Fatal(err)
604 }
605 }
606 time1 := time.Since(start)
607
608 database2, err := db.NewBadgerDB(c.TempDir())
609 c.Assert(err, qt.IsNil)
610 tree2, err := NewTree(database2, 100, HashFunctionPoseidon)
611 c.Assert(err, qt.IsNil)
612 defer tree2.db.Close() //nolint:errcheck
613 tree2.dbgInit()
614
615 var keys, values [][]byte
616 // add the initial leafs to fill a bit the tree before calling the
617 // AddBatch method
618 for i := 0; i < initialNLeafs; i++ {
619 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
620 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
621 // use only the keys of one bucket, store the not used ones for
622 // later
623 if i%4 != 0 {
624 keys = append(keys, k)
625 values = append(values, v)
626 continue
627 }
628 if err := tree2.Add(k, v); err != nil {
629 t.Fatal(err)
630 }
631 }
632
633 for i := initialNLeafs; i < nLeafs; i++ {
634 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
635 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
636 keys = append(keys, k)
637 values = append(values, v)
638 }
639 start = time.Now()
640 indexes, err := tree2.AddBatch(keys, values)
641 c.Assert(err, qt.IsNil)
642 time2 := time.Since(start)
643 if debug {
644 debugTime("Case tree not empty & unbalanced, AddBatch", time1, time2)
645 printTestContext(" ", nLeafs, "Poseidon", "memory")
646 tree2.dbg.print(" ")
647 }
648 c.Check(len(indexes), qt.Equals, 0)
649
650 // check that both trees roots are equal
651 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
652}
653
654func TestFlp2(t *testing.T) {
655 c := qt.New(t)
656 c.Assert(flp2(31), qt.Equals, 16)
657 c.Assert(flp2(32), qt.Equals, 32)
658 c.Assert(flp2(33), qt.Equals, 32)
659 c.Assert(flp2(63), qt.Equals, 32)
660 c.Assert(flp2(64), qt.Equals, 64)
661 c.Assert(flp2(9000), qt.Equals, 8192)
662}
663
664func TestAddBatchBench(t *testing.T) {
665 nLeafs := 50_000
666 printTestContext("TestAddBatchBench: ", nLeafs, "Blake2b", "badgerdb")
667
668 // prepare inputs
669 var ks, vs [][]byte
670 for i := 0; i < nLeafs; i++ {
671 k := randomBytes(32)
672 v := randomBytes(32)
673 ks = append(ks, k)
674 vs = append(vs, v)
675 }
676
677 benchAdd(t, ks, vs)
678
679 benchAddBatch(t, ks, vs)
680}
681
682func benchAdd(t *testing.T, ks, vs [][]byte) {
683 c := qt.New(t)
684
685 database, err := db.NewBadgerDB(c.TempDir())
686 c.Assert(err, qt.IsNil)
687 tree, err := NewTree(database, 140, HashFunctionBlake2b)
688 c.Assert(err, qt.IsNil)
689 defer tree.db.Close() //nolint:errcheck
690
691 start := time.Now()
692 for i := 0; i < len(ks); i++ {
693 err = tree.Add(ks[i], vs[i])
694 c.Assert(err, qt.IsNil)
695 }
696 if debug {
697 printRes(" Add loop", time.Since(start))
698 tree.dbg.print(" ")
699 }
700}
701
702func benchAddBatch(t *testing.T, ks, vs [][]byte) {
703 c := qt.New(t)
704
705 database, err := db.NewBadgerDB(c.TempDir())
706 c.Assert(err, qt.IsNil)
707 tree, err := NewTree(database, 140, HashFunctionBlake2b)
708 c.Assert(err, qt.IsNil)
709 defer tree.db.Close() //nolint:errcheck
710
711 tree.dbgInit()
712
713 start := time.Now()
714 invalids, err := tree.AddBatch(ks, vs)
715 if debug {
716 printRes(" AddBatch", time.Since(start))
717 tree.dbg.print(" ")
718 }
719 c.Assert(err, qt.IsNil)
720 c.Assert(len(invalids), qt.Equals, 0)
721}
722
723func TestDbgStats(t *testing.T) {
724 c := qt.New(t)
725
726 nLeafs := 10_000
727
728 // prepare inputs
729 var ks, vs [][]byte
730 for i := 0; i < nLeafs; i++ {
731 k := randomBytes(32)
732 v := randomBytes(32)
733 ks = append(ks, k)
734 vs = append(vs, v)
735 }
736
737 // 1
738 database1, err := db.NewBadgerDB(c.TempDir())
739 c.Assert(err, qt.IsNil)
740 tree1, err := NewTree(database1, 100, HashFunctionBlake2b)
741 c.Assert(err, qt.IsNil)
742 defer tree1.db.Close() //nolint:errcheck
743
744 tree1.dbgInit()
745
746 for i := 0; i < len(ks); i++ {
747 err = tree1.Add(ks[i], vs[i])
748 c.Assert(err, qt.IsNil)
749 }
750
751 // 2
752 database2, err := db.NewBadgerDB(c.TempDir())
753 c.Assert(err, qt.IsNil)
754 tree2, err := NewTree(database2, 100, HashFunctionBlake2b)
755 c.Assert(err, qt.IsNil)
756 defer tree2.db.Close() //nolint:errcheck
757
758 tree2.dbgInit()
759
760 invalids, err := tree2.AddBatch(ks, vs)
761 c.Assert(err, qt.IsNil)
762 c.Assert(len(invalids), qt.Equals, 0)
763
764 // 3
765 database3, err := db.NewBadgerDB(c.TempDir())
766 c.Assert(err, qt.IsNil)
767 tree3, err := NewTree(database3, 100, HashFunctionBlake2b)
768 c.Assert(err, qt.IsNil)
769 defer tree3.db.Close() //nolint:errcheck
770
771 tree3.dbgInit()
772
773 // add few key-values
774 // invalids, err = tree3.AddBatch(ks[:], vs[:])
775 invalids, err = tree3.AddBatch(ks[:1000], vs[:1000])
776 c.Assert(err, qt.IsNil)
777 c.Assert(len(invalids), qt.Equals, 0)
778
779 // add the rest of key-values
780 invalids, err = tree3.AddBatch(ks[1000:], vs[1000:])
781 c.Assert(err, qt.IsNil)
782 c.Assert(len(invalids), qt.Equals, 0)
783
784 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
785 c.Check(tree3.Root(), qt.DeepEquals, tree1.Root())
786
787 if debug {
788 fmt.Println("TestDbgStats")
789 tree1.dbg.print(" add in loop in emptyTree ")
790 tree2.dbg.print(" addbatch caseEmptyTree ")
791 tree3.dbg.print(" addbatch caseNotEmptyTree ")
792 }
793}
794
795func TestLoadVT(t *testing.T) {
796 c := qt.New(t)
797
798 nLeafs := 1024
799
800 database, err := db.NewBadgerDB(c.TempDir())
801 c.Assert(err, qt.IsNil)
802 tree, err := NewTree(database, 100, HashFunctionPoseidon)
803 c.Assert(err, qt.IsNil)
804 defer tree.db.Close() //nolint:errcheck
805
806 var keys, values [][]byte
807 for i := 0; i < nLeafs; i++ {
808 k := randomBytes(31)
809 v := randomBytes(31)
810 keys = append(keys, k)
811 values = append(values, v)
812 }
813 indexes, err := tree.AddBatch(keys, values)
814 c.Assert(err, qt.IsNil)
815 c.Check(len(indexes), qt.Equals, 0)
816
817 vt, err := tree.loadVT()
818 c.Assert(err, qt.IsNil)
819 _, err = vt.computeHashes()
820 c.Assert(err, qt.IsNil)
821
822 // check that tree & vt roots are equal
823 c.Check(tree.Root(), qt.DeepEquals, vt.root.h)
824}
825
826// TODO test adding batch with multiple invalid keys
827// TODO for tests of AddBatch, if the root does not match the Add root, bulk
828// all the leafs of both trees into a log file to later be able to debug and
829// recreate the case