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
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
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 checkRoots(c, tree, tree2)
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 checkRoots(c, tree, tree2)
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 TestAddBatchTestVector1(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 checkRoots(c, tree1, tree2)
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 checkRoots(c, tree1, tree2)
251}
252
253func TestAddBatchTestVector2(t *testing.T) {
254 // test vector with unbalanced tree
255 c := qt.New(t)
256
257 database, err := db.NewBadgerDB(c.TempDir())
258 c.Assert(err, qt.IsNil)
259 tree1, err := NewTree(database, 100, HashFunctionPoseidon)
260 c.Assert(err, qt.IsNil)
261 defer tree1.db.Close() //nolint:errcheck
262
263 database2, err := db.NewBadgerDB(c.TempDir())
264 c.Assert(err, qt.IsNil)
265 tree2, err := NewTree(database2, 100, HashFunctionPoseidon)
266 c.Assert(err, qt.IsNil)
267 defer tree2.db.Close() //nolint:errcheck
268
269 bLen := tree1.HashFunction().Len()
270 var keys, values [][]byte
271 // 1
272 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(1))))
273 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(1))))
274 // 2
275 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(2))))
276 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(2))))
277 // 3
278 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(3))))
279 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(3))))
280 // 5
281 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(5))))
282 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(5))))
283
284 for i := 0; i < len(keys); i++ {
285 if err := tree1.Add(keys[i], values[i]); err != nil {
286 t.Fatal(err)
287 }
288 }
289
290 indexes, err := tree2.AddBatch(keys, values)
291 c.Assert(err, qt.IsNil)
292 c.Check(len(indexes), qt.Equals, 0)
293
294 // check that both trees roots are equal
295 checkRoots(c, tree1, tree2)
296}
297
298func TestAddBatchTestVector3(t *testing.T) {
299 // test vector with unbalanced tree
300 c := qt.New(t)
301
302 database, err := db.NewBadgerDB(c.TempDir())
303 c.Assert(err, qt.IsNil)
304 tree1, err := NewTree(database, 100, HashFunctionPoseidon)
305 c.Assert(err, qt.IsNil)
306 defer tree1.db.Close() //nolint:errcheck
307
308 database2, err := db.NewBadgerDB(c.TempDir())
309 c.Assert(err, qt.IsNil)
310 tree2, err := NewTree(database2, 100, HashFunctionPoseidon)
311 c.Assert(err, qt.IsNil)
312 defer tree2.db.Close() //nolint:errcheck
313
314 bLen := tree1.HashFunction().Len()
315 var keys, values [][]byte
316 // 0
317 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(0))))
318 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(0))))
319 // 3
320 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(3))))
321 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(3))))
322 // 7
323 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(7))))
324 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(7))))
325 // 135
326 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(135))))
327 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(135))))
328
329 for i := 0; i < len(keys); i++ {
330 if err := tree1.Add(keys[i], values[i]); err != nil {
331 t.Fatal(err)
332 }
333 }
334
335 indexes, err := tree2.AddBatch(keys, values)
336 c.Assert(err, qt.IsNil)
337 c.Check(len(indexes), qt.Equals, 0)
338
339 // check that both trees roots are equal
340 checkRoots(c, tree1, tree2)
341 //
342 // tree1.PrintGraphvizFirstNLevels(nil, 100)
343 // tree2.PrintGraphvizFirstNLevels(nil, 100)
344}
345
346func TestAddBatchTreeEmptyRandomKeys(t *testing.T) {
347 c := qt.New(t)
348
349 nLeafs := 8
350
351 database1, err := db.NewBadgerDB(c.TempDir())
352 c.Assert(err, qt.IsNil)
353 tree1, err := NewTree(database1, 100, HashFunctionBlake2b)
354 c.Assert(err, qt.IsNil)
355 defer tree1.db.Close() //nolint:errcheck
356
357 database2, err := db.NewBadgerDB(c.TempDir())
358 c.Assert(err, qt.IsNil)
359 tree2, err := NewTree(database2, 100, HashFunctionBlake2b)
360 c.Assert(err, qt.IsNil)
361 defer tree2.db.Close() //nolint:errcheck
362
363 var keys, values [][]byte
364 for i := 0; i < nLeafs; i++ {
365 keys = append(keys, randomBytes(32))
366 values = append(values, randomBytes(32))
367 }
368
369 for i := 0; i < len(keys); i++ {
370 if err := tree1.Add(keys[i], values[i]); err != nil {
371 t.Fatal(err)
372 }
373 }
374
375 indexes, err := tree2.AddBatch(keys, values)
376 c.Assert(err, qt.IsNil)
377 c.Check(len(indexes), qt.Equals, 0)
378 // check that both trees roots are equal
379 checkRoots(c, tree1, tree2)
380}
381
382func TestAddBatchTreeNotEmptyFewLeafs(t *testing.T) {
383 c := qt.New(t)
384
385 nLeafs := 1024
386 initialNLeafs := 99
387
388 tree1, tree2 := testInit(c, initialNLeafs)
389 tree2.dbgInit()
390
391 bLen := tree1.HashFunction().Len()
392 start := time.Now()
393 for i := initialNLeafs; i < nLeafs; i++ {
394 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
395 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
396 if err := tree1.Add(k, v); err != nil {
397 t.Fatal(err)
398 }
399 }
400 time1 := time.Since(start)
401
402 // prepare the key-values to be added
403 var keys, values [][]byte
404 for i := initialNLeafs; i < nLeafs; i++ {
405 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
406 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
407 keys = append(keys, k)
408 values = append(values, v)
409 }
410 start = time.Now()
411 indexes, err := tree2.AddBatch(keys, values)
412 c.Assert(err, qt.IsNil)
413 time2 := time.Since(start)
414 if debug {
415 debugTime("Case tree not empty w/ few leafs, AddBatch", time1, time2)
416 printTestContext(" ", nLeafs, "Poseidon", "memory")
417 tree2.dbg.print(" ")
418 }
419 c.Check(len(indexes), qt.Equals, 0)
420
421 // check that both trees roots are equal
422 checkRoots(c, tree1, tree2)
423}
424
425func TestAddBatchTreeNotEmptyEnoughLeafs(t *testing.T) {
426 c := qt.New(t)
427
428 nLeafs := 1024
429 initialNLeafs := 500
430
431 tree1, tree2 := testInit(c, initialNLeafs)
432 tree2.dbgInit()
433
434 bLen := tree1.HashFunction().Len()
435 start := time.Now()
436 for i := initialNLeafs; i < nLeafs; i++ {
437 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
438 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
439 if err := tree1.Add(k, v); err != nil {
440 t.Fatal(err)
441 }
442 }
443 time1 := time.Since(start)
444
445 // prepare the key-values to be added
446 var keys, values [][]byte
447 for i := initialNLeafs; i < nLeafs; i++ {
448 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
449 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
450 keys = append(keys, k)
451 values = append(values, v)
452 }
453 start = time.Now()
454 indexes, err := tree2.AddBatch(keys, values)
455 c.Assert(err, qt.IsNil)
456 time2 := time.Since(start)
457 if debug {
458 debugTime("Case tree not empty w/ enough leafs, AddBatch", time1, time2)
459 printTestContext(" ", nLeafs, "Poseidon", "memory")
460 tree2.dbg.print(" ")
461 }
462 c.Check(len(indexes), qt.Equals, 0)
463 // check that both trees roots are equal
464 checkRoots(c, tree1, tree2)
465}
466
467func TestAddBatchTreeEmptyRepeatedLeafs(t *testing.T) {
468 c := qt.New(t)
469
470 nLeafs := 1024
471 nRepeatedKeys := 99
472
473 tree1, tree2 := testInit(c, 0)
474
475 bLen := tree1.HashFunction().Len()
476 // prepare the key-values to be added
477 var keys, values [][]byte
478 for i := 0; i < nLeafs; i++ {
479 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
480 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
481 keys = append(keys, k)
482 values = append(values, v)
483 }
484 // add repeated key-values
485 for i := 0; i < nRepeatedKeys; i++ {
486 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
487 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
488 keys = append(keys, k)
489 values = append(values, v)
490 }
491
492 // add the non-repeated key-values in tree1 with .Add loop
493 for i := 0; i < nLeafs; i++ {
494 if err := tree1.Add(keys[i], values[i]); err != nil {
495 t.Fatal(err)
496 }
497 }
498
499 indexes, err := tree2.AddBatch(keys, values)
500 c.Assert(err, qt.IsNil)
501 c.Check(len(indexes), qt.Equals, nRepeatedKeys)
502 // check that both trees roots are equal
503 checkRoots(c, tree1, tree2)
504}
505
506func TestAddBatchTreeNotEmptyFewLeafsRepeatedLeafs(t *testing.T) {
507 c := qt.New(t)
508
509 nLeafs := 1024
510 initialNLeafs := 99
511
512 tree1, tree2 := testInit(c, initialNLeafs)
513
514 bLen := tree1.HashFunction().Len()
515 // prepare the key-values to be added
516 var keys, values [][]byte
517 for i := 0; i < nLeafs; i++ {
518 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
519 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
520 keys = append(keys, k)
521 values = append(values, v)
522 }
523
524 // add the keys that will be existing when AddBatch is called
525 for i := initialNLeafs; i < nLeafs; i++ {
526 if err := tree1.Add(keys[i], values[i]); err != nil {
527 t.Fatal(err)
528 }
529 }
530
531 indexes, err := tree2.AddBatch(keys, values)
532 c.Assert(err, qt.IsNil)
533 c.Check(len(indexes), qt.Equals, initialNLeafs)
534 // check that both trees roots are equal
535 checkRoots(c, tree1, tree2)
536}
537
538func TestSplitInBuckets(t *testing.T) {
539 c := qt.New(t)
540
541 bLen := HashFunctionPoseidon.Len()
542 nLeafs := 16
543 kvs := make([]kv, nLeafs)
544 for i := 0; i < nLeafs; i++ {
545 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
546 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
547 keyPath := make([]byte, 32)
548 copy(keyPath[:], k)
549 kvs[i].pos = i
550 kvs[i].keyPath = k
551 kvs[i].k = k
552 kvs[i].v = v
553 }
554
555 // check keyToBucket results for 4 buckets & 8 keys
556 c.Assert(keyToBucket(kvs[0].k, 4), qt.Equals, 0)
557 c.Assert(keyToBucket(kvs[1].k, 4), qt.Equals, 2)
558 c.Assert(keyToBucket(kvs[2].k, 4), qt.Equals, 1)
559 c.Assert(keyToBucket(kvs[3].k, 4), qt.Equals, 3)
560 c.Assert(keyToBucket(kvs[4].k, 4), qt.Equals, 0)
561 c.Assert(keyToBucket(kvs[5].k, 4), qt.Equals, 2)
562 c.Assert(keyToBucket(kvs[6].k, 4), qt.Equals, 1)
563 c.Assert(keyToBucket(kvs[7].k, 4), qt.Equals, 3)
564
565 // check keyToBucket results for 8 buckets & 8 keys
566 c.Assert(keyToBucket(kvs[0].k, 8), qt.Equals, 0)
567 c.Assert(keyToBucket(kvs[1].k, 8), qt.Equals, 4)
568 c.Assert(keyToBucket(kvs[2].k, 8), qt.Equals, 2)
569 c.Assert(keyToBucket(kvs[3].k, 8), qt.Equals, 6)
570 c.Assert(keyToBucket(kvs[4].k, 8), qt.Equals, 1)
571 c.Assert(keyToBucket(kvs[5].k, 8), qt.Equals, 5)
572 c.Assert(keyToBucket(kvs[6].k, 8), qt.Equals, 3)
573 c.Assert(keyToBucket(kvs[7].k, 8), qt.Equals, 7)
574
575 buckets := splitInBuckets(kvs, 4)
576
577 expected := [][]string{
578 {
579 "00000000", // bucket 0
580 "08000000",
581 "04000000",
582 "0c000000",
583 },
584 {
585 "02000000", // bucket 1
586 "0a000000",
587 "06000000",
588 "0e000000",
589 },
590 {
591 "01000000", // bucket 2
592 "09000000",
593 "05000000",
594 "0d000000",
595 },
596 {
597 "03000000", // bucket 3
598 "0b000000",
599 "07000000",
600 "0f000000",
601 },
602 }
603
604 for i := 0; i < len(buckets); i++ {
605 sortKvs(buckets[i])
606 c.Assert(len(buckets[i]), qt.Equals, len(expected[i]))
607 for j := 0; j < len(buckets[i]); j++ {
608 c.Check(hex.EncodeToString(buckets[i][j].k[:4]),
609 qt.Equals, expected[i][j])
610 }
611 }
612}
613
614// compareBytes compares byte slices where the bytes are compared from left to
615// right and each byte is compared by bit from right to left
616func compareBytes(a, b []byte) bool {
617 // WIP
618 for i := 0; i < len(a); i++ {
619 for j := 0; j < 8; j++ {
620 aBit := a[i] & (1 << j)
621 bBit := b[i] & (1 << j)
622 if aBit > bBit {
623 return false
624 } else if aBit < bBit {
625 return true
626 }
627 }
628 }
629 return false
630}
631
632// sortKvs sorts the kv by path
633func sortKvs(kvs []kv) {
634 sort.Slice(kvs, func(i, j int) bool {
635 return compareBytes(kvs[i].keyPath, kvs[j].keyPath)
636 })
637}
638
639func TestAddBatchTreeNotEmpty(t *testing.T) {
640 c := qt.New(t)
641
642 nLeafs := 4096
643 initialNLeafs := 900
644
645 tree1, tree2 := testInit(c, initialNLeafs)
646 tree2.dbgInit()
647
648 bLen := tree1.HashFunction().Len()
649 start := time.Now()
650 for i := initialNLeafs; i < nLeafs; i++ {
651 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
652 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
653 if err := tree1.Add(k, v); err != nil {
654 t.Fatal(err)
655 }
656 }
657 time1 := time.Since(start)
658
659 // prepare the key-values to be added
660 var keys, values [][]byte
661 for i := initialNLeafs; i < nLeafs; i++ {
662 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
663 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
664 keys = append(keys, k)
665 values = append(values, v)
666 }
667 start = time.Now()
668 indexes, err := tree2.AddBatch(keys, values)
669 c.Assert(err, qt.IsNil)
670 time2 := time.Since(start)
671 if debug {
672 debugTime("Case tree not empty, AddBatch", time1, time2)
673 printTestContext(" ", nLeafs, "Poseidon", "memory")
674 tree2.dbg.print(" ")
675 }
676 c.Check(len(indexes), qt.Equals, 0)
677
678 // check that both trees roots are equal
679 checkRoots(c, tree1, tree2)
680}
681
682func TestAddBatchNotEmptyUnbalanced(t *testing.T) {
683 c := qt.New(t)
684
685 nLeafs := 4096
686 initialNLeafs := 900
687
688 tree1, _ := testInit(c, initialNLeafs)
689 bLen := tree1.HashFunction().Len()
690
691 start := time.Now()
692 for i := initialNLeafs; i < nLeafs; i++ {
693 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
694 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
695 if err := tree1.Add(k, v); err != nil {
696 t.Fatal(err)
697 }
698 }
699 time1 := time.Since(start)
700
701 database2, err := db.NewBadgerDB(c.TempDir())
702 c.Assert(err, qt.IsNil)
703 tree2, err := NewTree(database2, 100, HashFunctionPoseidon)
704 c.Assert(err, qt.IsNil)
705 defer tree2.db.Close() //nolint:errcheck
706 tree2.dbgInit()
707
708 var keys, values [][]byte
709 // add the initial leafs to fill a bit the tree before calling the
710 // AddBatch method
711 for i := 0; i < initialNLeafs; i++ {
712 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
713 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
714 // use only the keys of one bucket, store the not used ones for
715 // later
716 if i%4 != 0 {
717 keys = append(keys, k)
718 values = append(values, v)
719 continue
720 }
721 if err := tree2.Add(k, v); err != nil {
722 t.Fatal(err)
723 }
724 }
725
726 for i := initialNLeafs; i < nLeafs; i++ {
727 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
728 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
729 keys = append(keys, k)
730 values = append(values, v)
731 }
732 start = time.Now()
733 indexes, err := tree2.AddBatch(keys, values)
734 c.Assert(err, qt.IsNil)
735 time2 := time.Since(start)
736 if debug {
737 debugTime("Case tree not empty & unbalanced, AddBatch", time1, time2)
738 printTestContext(" ", nLeafs, "Poseidon", "memory")
739 tree2.dbg.print(" ")
740 }
741 c.Check(len(indexes), qt.Equals, 0)
742
743 // check that both trees roots are equal
744 checkRoots(c, tree1, tree2)
745}
746
747func TestFlp2(t *testing.T) {
748 c := qt.New(t)
749 c.Assert(flp2(31), qt.Equals, 16)
750 c.Assert(flp2(32), qt.Equals, 32)
751 c.Assert(flp2(33), qt.Equals, 32)
752 c.Assert(flp2(63), qt.Equals, 32)
753 c.Assert(flp2(64), qt.Equals, 64)
754 c.Assert(flp2(9000), qt.Equals, 8192)
755}
756
757func TestAddBatchBench(t *testing.T) {
758 nLeafs := 50_000
759 printTestContext("TestAddBatchBench: ", nLeafs, "Blake2b", "badgerdb")
760
761 // prepare inputs
762 var ks, vs [][]byte
763 for i := 0; i < nLeafs; i++ {
764 k := randomBytes(32)
765 v := randomBytes(32)
766 ks = append(ks, k)
767 vs = append(vs, v)
768 }
769
770 benchAdd(t, ks, vs)
771
772 benchAddBatch(t, ks, vs)
773}
774
775func benchAdd(t *testing.T, ks, vs [][]byte) {
776 c := qt.New(t)
777
778 database, err := db.NewBadgerDB(c.TempDir())
779 c.Assert(err, qt.IsNil)
780 tree, err := NewTree(database, 140, HashFunctionBlake2b)
781 c.Assert(err, qt.IsNil)
782 defer tree.db.Close() //nolint:errcheck
783
784 start := time.Now()
785 for i := 0; i < len(ks); i++ {
786 err = tree.Add(ks[i], vs[i])
787 c.Assert(err, qt.IsNil)
788 }
789 if debug {
790 printRes(" Add loop", time.Since(start))
791 tree.dbg.print(" ")
792 }
793}
794
795func benchAddBatch(t *testing.T, ks, vs [][]byte) {
796 c := qt.New(t)
797
798 database, err := db.NewBadgerDB(c.TempDir())
799 c.Assert(err, qt.IsNil)
800 tree, err := NewTree(database, 140, HashFunctionBlake2b)
801 c.Assert(err, qt.IsNil)
802 defer tree.db.Close() //nolint:errcheck
803
804 tree.dbgInit()
805
806 start := time.Now()
807 invalids, err := tree.AddBatch(ks, vs)
808 if debug {
809 printRes(" AddBatch", time.Since(start))
810 tree.dbg.print(" ")
811 }
812 c.Assert(err, qt.IsNil)
813 c.Assert(len(invalids), qt.Equals, 0)
814}
815
816func TestDbgStats(t *testing.T) {
817 c := qt.New(t)
818
819 nLeafs := 10_000
820
821 // prepare inputs
822 var ks, vs [][]byte
823 for i := 0; i < nLeafs; i++ {
824 k := randomBytes(32)
825 v := randomBytes(32)
826 ks = append(ks, k)
827 vs = append(vs, v)
828 }
829
830 // 1
831 database1, err := db.NewBadgerDB(c.TempDir())
832 c.Assert(err, qt.IsNil)
833 tree1, err := NewTree(database1, 100, HashFunctionBlake2b)
834 c.Assert(err, qt.IsNil)
835 defer tree1.db.Close() //nolint:errcheck
836
837 tree1.dbgInit()
838
839 for i := 0; i < len(ks); i++ {
840 err = tree1.Add(ks[i], vs[i])
841 c.Assert(err, qt.IsNil)
842 }
843
844 // 2
845 database2, err := db.NewBadgerDB(c.TempDir())
846 c.Assert(err, qt.IsNil)
847 tree2, err := NewTree(database2, 100, HashFunctionBlake2b)
848 c.Assert(err, qt.IsNil)
849 defer tree2.db.Close() //nolint:errcheck
850
851 tree2.dbgInit()
852
853 invalids, err := tree2.AddBatch(ks, vs)
854 c.Assert(err, qt.IsNil)
855 c.Assert(len(invalids), qt.Equals, 0)
856
857 // 3
858 database3, err := db.NewBadgerDB(c.TempDir())
859 c.Assert(err, qt.IsNil)
860 tree3, err := NewTree(database3, 100, HashFunctionBlake2b)
861 c.Assert(err, qt.IsNil)
862 defer tree3.db.Close() //nolint:errcheck
863
864 tree3.dbgInit()
865
866 // add few key-values
867 // invalids, err = tree3.AddBatch(ks[:], vs[:])
868 invalids, err = tree3.AddBatch(ks[:1000], vs[:1000])
869 c.Assert(err, qt.IsNil)
870 c.Assert(len(invalids), qt.Equals, 0)
871
872 // add the rest of key-values
873 invalids, err = tree3.AddBatch(ks[1000:], vs[1000:])
874 c.Assert(err, qt.IsNil)
875 c.Assert(len(invalids), qt.Equals, 0)
876
877 checkRoots(c, tree1, tree2)
878 checkRoots(c, tree1, tree3)
879
880 if debug {
881 fmt.Println("TestDbgStats")
882 tree1.dbg.print(" add in loop in emptyTree ")
883 tree2.dbg.print(" addbatch caseEmptyTree ")
884 tree3.dbg.print(" addbatch caseNotEmptyTree ")
885 }
886}
887
888func TestLoadVT(t *testing.T) {
889 c := qt.New(t)
890
891 nLeafs := 1024
892
893 database, err := db.NewBadgerDB(c.TempDir())
894 c.Assert(err, qt.IsNil)
895 tree, err := NewTree(database, 100, HashFunctionPoseidon)
896 c.Assert(err, qt.IsNil)
897 defer tree.db.Close() //nolint:errcheck
898
899 var keys, values [][]byte
900 for i := 0; i < nLeafs; i++ {
901 k := randomBytes(31)
902 v := randomBytes(31)
903 keys = append(keys, k)
904 values = append(values, v)
905 }
906 indexes, err := tree.AddBatch(keys, values)
907 c.Assert(err, qt.IsNil)
908 c.Check(len(indexes), qt.Equals, 0)
909
910 vt, err := tree.loadVT()
911 c.Assert(err, qt.IsNil)
912 _, err = vt.computeHashes()
913 c.Assert(err, qt.IsNil)
914
915 // check that tree & vt roots are equal
916 c.Check(tree.Root(), qt.DeepEquals, vt.root.h)
917}
918
919// TODO test adding batch with multiple invalid keys
920// TODO for tests of AddBatch, if the root does not match the Add root, bulk
921// all the leafs of both trees into a log file to later be able to debug and
922// recreate the case