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