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