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