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 "go.vocdoni.io/dvote/db/badgerdb"
16 "go.vocdoni.io/dvote/db/pebbledb"
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 database1, err := badgerdb.New(db.Options{Path: c.TempDir()})
43 c.Assert(err, qt.IsNil)
44 tree1, err := NewTree(Config{Database: database1, MaxLevels: 256,
45 HashFunction: HashFunctionPoseidon})
46 c.Assert(err, qt.IsNil)
47
48 database2, err := badgerdb.New(db.Options{Path: c.TempDir()})
49 c.Assert(err, qt.IsNil)
50 tree2, err := NewTree(Config{Database: database2, MaxLevels: 256,
51 HashFunction: HashFunctionPoseidon})
52 c.Assert(err, qt.IsNil)
53
54 bLen := HashFunctionPoseidon.Len()
55 // add the initial leafs to fill a bit the trees before calling the
56 // AddBatch method
57 for i := 0; i < n; i++ {
58 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
59 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
60 if err := tree1.Add(k, v); err != nil {
61 c.Fatal(err)
62 }
63 if err := tree2.Add(k, v); err != nil {
64 c.Fatal(err)
65 }
66 }
67 return tree1, tree2
68}
69
70func TestAddBatchTreeEmpty(t *testing.T) {
71 c := qt.New(t)
72
73 nLeafs := 1024
74
75 database, err := badgerdb.New(db.Options{Path: c.TempDir()})
76 c.Assert(err, qt.IsNil)
77 tree, err := NewTree(Config{database, 256, DefaultThresholdNLeafs,
78 HashFunctionPoseidon})
79 c.Assert(err, qt.IsNil)
80 defer tree.db.Close() //nolint:errcheck
81
82 bLen := 32
83 var keys, values [][]byte
84 for i := 0; i < nLeafs; i++ {
85 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
86 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
87 keys = append(keys, k)
88 values = append(values, v)
89 }
90
91 start := time.Now()
92 for i := 0; i < nLeafs; i++ {
93 if err := tree.Add(keys[i], values[i]); err != nil {
94 t.Fatal(err)
95 }
96 }
97 time1 := time.Since(start)
98
99 database2, err := badgerdb.New(db.Options{Path: c.TempDir()})
100 c.Assert(err, qt.IsNil)
101 tree2, err := NewTree(Config{database2, 256, DefaultThresholdNLeafs,
102 HashFunctionPoseidon})
103 c.Assert(err, qt.IsNil)
104 defer tree2.db.Close() //nolint:errcheck
105 tree2.dbgInit()
106
107 start = time.Now()
108 invalids, err := tree2.AddBatch(keys, values)
109 c.Assert(err, qt.IsNil)
110 time2 := time.Since(start)
111 if debug {
112 debugTime("Case tree empty, AddBatch", time1, time2)
113 printTestContext(" ", nLeafs, "Poseidon", "memory")
114 tree2.dbg.print(" ")
115 }
116 c.Check(len(invalids), qt.Equals, 0)
117
118 // check that both trees roots are equal
119 checkRoots(c, tree, tree2)
120}
121
122func TestAddBatchTreeEmptyNotPowerOf2(t *testing.T) {
123 c := qt.New(t)
124
125 nLeafs := 1027
126
127 database, err := badgerdb.New(db.Options{Path: c.TempDir()})
128 c.Assert(err, qt.IsNil)
129 tree, err := NewTree(Config{database, 256, DefaultThresholdNLeafs,
130 HashFunctionPoseidon})
131 c.Assert(err, qt.IsNil)
132 defer tree.db.Close() //nolint:errcheck
133
134 bLen := 32
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 if err := tree.Add(k, v); err != nil {
139 t.Fatal(err)
140 }
141 }
142
143 database2, err := badgerdb.New(db.Options{Path: c.TempDir()})
144 c.Assert(err, qt.IsNil)
145 tree2, err := NewTree(Config{database2, 256, DefaultThresholdNLeafs,
146 HashFunctionPoseidon})
147 c.Assert(err, qt.IsNil)
148 defer tree2.db.Close() //nolint:errcheck
149
150 var keys, values [][]byte
151 for i := 0; i < nLeafs; i++ {
152 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
153 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
154 keys = append(keys, k)
155 values = append(values, v)
156 }
157 invalids, err := tree2.AddBatch(keys, values)
158 c.Assert(err, qt.IsNil)
159 c.Check(len(invalids), qt.Equals, 0)
160
161 // check that both trees roots are equal
162 checkRoots(c, tree, tree2)
163}
164
165func randomBytes(n int) []byte {
166 b := make([]byte, n)
167 _, err := rand.Read(b)
168 if err != nil {
169 panic(err)
170 }
171 return b
172}
173
174func TestAddBatchTestVector1(t *testing.T) {
175 c := qt.New(t)
176 database1, err := badgerdb.New(db.Options{Path: c.TempDir()})
177 c.Assert(err, qt.IsNil)
178 tree1, err := NewTree(Config{database1, 256, DefaultThresholdNLeafs,
179 HashFunctionBlake2b})
180 c.Assert(err, qt.IsNil)
181 defer tree1.db.Close() //nolint:errcheck
182
183 database2, err := badgerdb.New(db.Options{Path: c.TempDir()})
184 c.Assert(err, qt.IsNil)
185 tree2, err := NewTree(Config{database2, 256, DefaultThresholdNLeafs,
186 HashFunctionBlake2b})
187 c.Assert(err, qt.IsNil)
188 defer tree2.db.Close() //nolint:errcheck
189
190 // leafs in 2nd level subtrees: [ 6, 0, 1, 1]
191 testvectorKeys := []string{
192 "1c7c2265e368314ca58ed2e1f33a326f1220e234a566d55c3605439dbe411642",
193 "2c9f0a578afff5bfa4e0992a43066460faaab9e8e500db0b16647c701cdb16bf",
194 "1c45cb31f2fa39ec7b9ebf0fad40e0b8296016b5ce8844ae06ff77226379d9a5",
195 "d8af98bbbb585129798ae54d5eabbc9d0561d583faf1663b3a3724d15bda4ec7",
196 }
197 var keys, values [][]byte
198 for i := 0; i < len(testvectorKeys); i++ {
199 key, err := hex.DecodeString(testvectorKeys[i])
200 c.Assert(err, qt.IsNil)
201 keys = append(keys, key)
202 values = append(values, []byte{0})
203 }
204
205 for i := 0; i < len(keys); i++ {
206 if err := tree1.Add(keys[i], values[i]); err != nil {
207 t.Fatal(err)
208 }
209 }
210
211 invalids, err := tree2.AddBatch(keys, values)
212 c.Assert(err, qt.IsNil)
213 c.Check(len(invalids), qt.Equals, 0)
214 // check that both trees roots are equal
215 checkRoots(c, tree1, tree2)
216
217 // 2nd test vectors
218 database1, err = badgerdb.New(db.Options{Path: c.TempDir()})
219 c.Assert(err, qt.IsNil)
220 tree1, err = NewTree(Config{database1, 256, DefaultThresholdNLeafs,
221 HashFunctionBlake2b})
222 c.Assert(err, qt.IsNil)
223 defer tree1.db.Close() //nolint:errcheck
224
225 database2, err = badgerdb.New(db.Options{Path: c.TempDir()})
226 c.Assert(err, qt.IsNil)
227 tree2, err = NewTree(Config{database2, 256, DefaultThresholdNLeafs,
228 HashFunctionBlake2b})
229 c.Assert(err, qt.IsNil)
230 defer tree2.db.Close() //nolint:errcheck
231
232 testvectorKeys = []string{
233 "1c7c2265e368314ca58ed2e1f33a326f1220e234a566d55c3605439dbe411642",
234 "2c9f0a578afff5bfa4e0992a43066460faaab9e8e500db0b16647c701cdb16bf",
235 "9cb87ec67e875c61390edcd1ab517f443591047709a4d4e45b0f9ed980857b8e",
236 "9b4e9e92e974a589f426ceeb4cb291dc24893513fecf8e8460992dcf52621d4d",
237 "1c45cb31f2fa39ec7b9ebf0fad40e0b8296016b5ce8844ae06ff77226379d9a5",
238 "d8af98bbbb585129798ae54d5eabbc9d0561d583faf1663b3a3724d15bda4ec7",
239 "3cd55dbfb8f975f20a0925dfbdabe79fa2d51dd0268afbb8ba6b01de9dfcdd3c",
240 "5d0a9d6d9f197c091bf054fac9cb60e11ec723d6610ed8578e617b4d46cb43d5",
241 }
242 keys = [][]byte{}
243 values = [][]byte{}
244 for i := 0; i < len(testvectorKeys); i++ {
245 key, err := hex.DecodeString(testvectorKeys[i])
246 c.Assert(err, qt.IsNil)
247 keys = append(keys, key)
248 values = append(values, []byte{0})
249 }
250
251 for i := 0; i < len(keys); i++ {
252 if err := tree1.Add(keys[i], values[i]); err != nil {
253 t.Fatal(err)
254 }
255 }
256
257 invalids, err = tree2.AddBatch(keys, values)
258 c.Assert(err, qt.IsNil)
259 c.Check(len(invalids), qt.Equals, 0)
260 // check that both trees roots are equal
261 checkRoots(c, tree1, tree2)
262}
263
264func TestAddBatchTestVector2(t *testing.T) {
265 // test vector with unbalanced tree
266 c := qt.New(t)
267
268 database, err := badgerdb.New(db.Options{Path: c.TempDir()})
269 c.Assert(err, qt.IsNil)
270 tree1, err := NewTree(Config{database, 256, DefaultThresholdNLeafs,
271 HashFunctionPoseidon})
272 c.Assert(err, qt.IsNil)
273 defer tree1.db.Close() //nolint:errcheck
274
275 database2, err := badgerdb.New(db.Options{Path: c.TempDir()})
276 c.Assert(err, qt.IsNil)
277 tree2, err := NewTree(Config{database2, 256, DefaultThresholdNLeafs,
278 HashFunctionPoseidon})
279 c.Assert(err, qt.IsNil)
280 defer tree2.db.Close() //nolint:errcheck
281
282 bLen := tree1.HashFunction().Len()
283 var keys, values [][]byte
284 // 1
285 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(1))))
286 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(1))))
287 // 2
288 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(2))))
289 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(2))))
290 // 3
291 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(3))))
292 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(3))))
293 // 5
294 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(5))))
295 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(5))))
296
297 for i := 0; i < len(keys); i++ {
298 if err := tree1.Add(keys[i], values[i]); err != nil {
299 t.Fatal(err)
300 }
301 }
302
303 invalids, err := tree2.AddBatch(keys, values)
304 c.Assert(err, qt.IsNil)
305 c.Check(len(invalids), qt.Equals, 0)
306
307 // check that both trees roots are equal
308 checkRoots(c, tree1, tree2)
309}
310
311func TestAddBatchTestVector3(t *testing.T) {
312 // test vector with unbalanced tree
313 c := qt.New(t)
314
315 database, err := badgerdb.New(db.Options{Path: c.TempDir()})
316 c.Assert(err, qt.IsNil)
317 tree1, err := NewTree(Config{database, 256, DefaultThresholdNLeafs,
318 HashFunctionPoseidon})
319 c.Assert(err, qt.IsNil)
320 defer tree1.db.Close() //nolint:errcheck
321
322 database2, err := badgerdb.New(db.Options{Path: c.TempDir()})
323 c.Assert(err, qt.IsNil)
324 tree2, err := NewTree(Config{database2, 256, DefaultThresholdNLeafs,
325 HashFunctionPoseidon})
326 c.Assert(err, qt.IsNil)
327 defer tree2.db.Close() //nolint:errcheck
328
329 bLen := tree1.HashFunction().Len()
330 var keys, values [][]byte
331 // 0
332 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(0))))
333 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(0))))
334 // 3
335 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(3))))
336 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(3))))
337 // 7
338 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(7))))
339 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(7))))
340 // 135
341 keys = append(keys, BigIntToBytes(bLen, big.NewInt(int64(135))))
342 values = append(values, BigIntToBytes(bLen, big.NewInt(int64(135))))
343
344 for i := 0; i < len(keys); i++ {
345 if err := tree1.Add(keys[i], values[i]); err != nil {
346 t.Fatal(err)
347 }
348 }
349
350 invalids, err := tree2.AddBatch(keys, values)
351 c.Assert(err, qt.IsNil)
352 c.Check(len(invalids), qt.Equals, 0)
353
354 // check that both trees roots are equal
355 checkRoots(c, tree1, tree2)
356 //
357 // tree1.PrintGraphvizFirstNLevels(nil, 100)
358 // tree2.PrintGraphvizFirstNLevels(nil, 100)
359}
360
361func TestAddBatchTreeEmptyRandomKeys(t *testing.T) {
362 c := qt.New(t)
363
364 nLeafs := 8
365
366 database1, err := badgerdb.New(db.Options{Path: c.TempDir()})
367 c.Assert(err, qt.IsNil)
368 tree1, err := NewTree(Config{database1, 256, DefaultThresholdNLeafs,
369 HashFunctionBlake2b})
370 c.Assert(err, qt.IsNil)
371 defer tree1.db.Close() //nolint:errcheck
372
373 database2, err := badgerdb.New(db.Options{Path: c.TempDir()})
374 c.Assert(err, qt.IsNil)
375 tree2, err := NewTree(Config{database2, 256, DefaultThresholdNLeafs,
376 HashFunctionBlake2b})
377 c.Assert(err, qt.IsNil)
378 defer tree2.db.Close() //nolint:errcheck
379
380 var keys, values [][]byte
381 for i := 0; i < nLeafs; i++ {
382 keys = append(keys, randomBytes(32))
383 values = append(values, randomBytes(32))
384 }
385
386 for i := 0; i < len(keys); i++ {
387 if err := tree1.Add(keys[i], values[i]); err != nil {
388 t.Fatal(err)
389 }
390 }
391
392 invalids, err := tree2.AddBatch(keys, values)
393 c.Assert(err, qt.IsNil)
394 c.Check(len(invalids), qt.Equals, 0)
395 // check that both trees roots are equal
396 checkRoots(c, tree1, tree2)
397}
398
399func TestAddBatchTreeNotEmptyFewLeafs(t *testing.T) {
400 c := qt.New(t)
401
402 nLeafs := 1024
403 initialNLeafs := 99
404
405 tree1, tree2 := testInit(c, initialNLeafs)
406 tree2.dbgInit()
407
408 bLen := tree1.HashFunction().Len()
409 start := time.Now()
410 for i := initialNLeafs; i < nLeafs; i++ {
411 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
412 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
413 if err := tree1.Add(k, v); err != nil {
414 t.Fatal(err)
415 }
416 }
417 time1 := time.Since(start)
418
419 // prepare the key-values to be added
420 var keys, values [][]byte
421 for i := initialNLeafs; i < nLeafs; i++ {
422 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
423 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
424 keys = append(keys, k)
425 values = append(values, v)
426 }
427 start = time.Now()
428 invalids, err := tree2.AddBatch(keys, values)
429 c.Assert(err, qt.IsNil)
430 time2 := time.Since(start)
431 if debug {
432 debugTime("Case tree not empty w/ few leafs, AddBatch", time1, time2)
433 printTestContext(" ", nLeafs, "Poseidon", "memory")
434 tree2.dbg.print(" ")
435 }
436 c.Check(len(invalids), qt.Equals, 0)
437
438 // check that both trees roots are equal
439 checkRoots(c, tree1, tree2)
440}
441
442func TestAddBatchTreeNotEmptyEnoughLeafs(t *testing.T) {
443 c := qt.New(t)
444
445 nLeafs := 1024
446 initialNLeafs := 500
447
448 tree1, tree2 := testInit(c, initialNLeafs)
449 tree2.dbgInit()
450
451 bLen := tree1.HashFunction().Len()
452 start := time.Now()
453 for i := initialNLeafs; i < nLeafs; i++ {
454 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
455 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
456 if err := tree1.Add(k, v); err != nil {
457 t.Fatal(err)
458 }
459 }
460 time1 := time.Since(start)
461
462 // prepare the key-values to be added
463 var keys, values [][]byte
464 for i := initialNLeafs; i < nLeafs; i++ {
465 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
466 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
467 keys = append(keys, k)
468 values = append(values, v)
469 }
470 start = time.Now()
471 invalids, err := tree2.AddBatch(keys, values)
472 c.Assert(err, qt.IsNil)
473 time2 := time.Since(start)
474 if debug {
475 debugTime("Case tree not empty w/ enough leafs, AddBatch", time1, time2)
476 printTestContext(" ", nLeafs, "Poseidon", "memory")
477 tree2.dbg.print(" ")
478 }
479 c.Check(len(invalids), qt.Equals, 0)
480 // check that both trees roots are equal
481 checkRoots(c, tree1, tree2)
482}
483
484func TestAddBatchTreeEmptyRepeatedLeafs(t *testing.T) {
485 c := qt.New(t)
486
487 nLeafs := 1024
488 nRepeatedKeys := 99
489
490 tree1, tree2 := testInit(c, 0)
491
492 bLen := tree1.HashFunction().Len()
493 // prepare the key-values to be added
494 var keys, values [][]byte
495 for i := 0; i < nLeafs; i++ {
496 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
497 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
498 keys = append(keys, k)
499 values = append(values, v)
500 }
501 // add repeated key-values
502 for i := 0; i < nRepeatedKeys; i++ {
503 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
504 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
505 keys = append(keys, k)
506 values = append(values, v)
507 }
508
509 // add the non-repeated key-values in tree1 with .Add loop
510 for i := 0; i < nLeafs; i++ {
511 if err := tree1.Add(keys[i], values[i]); err != nil {
512 t.Fatal(err)
513 }
514 }
515
516 invalids, err := tree2.AddBatch(keys, values)
517 c.Assert(err, qt.IsNil)
518 c.Check(len(invalids), qt.Equals, nRepeatedKeys)
519 // check that both trees roots are equal
520 checkRoots(c, tree1, tree2)
521}
522
523func TestAddBatchTreeNotEmptyFewLeafsRepeatedLeafs(t *testing.T) {
524 c := qt.New(t)
525
526 nLeafs := 1024
527 initialNLeafs := 99
528
529 tree1, tree2 := testInit(c, initialNLeafs)
530
531 bLen := tree1.HashFunction().Len()
532 // prepare the key-values to be added
533 var keys, values [][]byte
534 for i := 0; i < nLeafs; i++ {
535 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
536 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
537 keys = append(keys, k)
538 values = append(values, v)
539 }
540
541 // add the keys that will be existing when AddBatch is called
542 for i := initialNLeafs; i < nLeafs; i++ {
543 if err := tree1.Add(keys[i], values[i]); err != nil {
544 t.Fatal(err)
545 }
546 }
547
548 invalids, err := tree2.AddBatch(keys, values)
549 c.Assert(err, qt.IsNil)
550 c.Assert(len(invalids), qt.Equals, initialNLeafs)
551 // check that both trees roots are equal
552 checkRoots(c, tree1, tree2)
553}
554
555func TestSplitInBuckets(t *testing.T) {
556 c := qt.New(t)
557
558 bLen := HashFunctionPoseidon.Len()
559 nLeafs := 16
560 kvs := make([]kv, nLeafs)
561 for i := 0; i < nLeafs; i++ {
562 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
563 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
564 keyPath := make([]byte, 32)
565 copy(keyPath[:], k)
566 kvs[i].pos = i
567 kvs[i].keyPath = k
568 kvs[i].k = k
569 kvs[i].v = v
570 }
571
572 // check keyToBucket results for 4 buckets & 8 keys
573 c.Assert(keyToBucket(kvs[0].k, 4), qt.Equals, 0)
574 c.Assert(keyToBucket(kvs[1].k, 4), qt.Equals, 2)
575 c.Assert(keyToBucket(kvs[2].k, 4), qt.Equals, 1)
576 c.Assert(keyToBucket(kvs[3].k, 4), qt.Equals, 3)
577 c.Assert(keyToBucket(kvs[4].k, 4), qt.Equals, 0)
578 c.Assert(keyToBucket(kvs[5].k, 4), qt.Equals, 2)
579 c.Assert(keyToBucket(kvs[6].k, 4), qt.Equals, 1)
580 c.Assert(keyToBucket(kvs[7].k, 4), qt.Equals, 3)
581
582 // check keyToBucket results for 8 buckets & 8 keys
583 c.Assert(keyToBucket(kvs[0].k, 8), qt.Equals, 0)
584 c.Assert(keyToBucket(kvs[1].k, 8), qt.Equals, 4)
585 c.Assert(keyToBucket(kvs[2].k, 8), qt.Equals, 2)
586 c.Assert(keyToBucket(kvs[3].k, 8), qt.Equals, 6)
587 c.Assert(keyToBucket(kvs[4].k, 8), qt.Equals, 1)
588 c.Assert(keyToBucket(kvs[5].k, 8), qt.Equals, 5)
589 c.Assert(keyToBucket(kvs[6].k, 8), qt.Equals, 3)
590 c.Assert(keyToBucket(kvs[7].k, 8), qt.Equals, 7)
591
592 buckets := splitInBuckets(kvs, 4)
593
594 expected := [][]string{
595 {
596 "00000000", // bucket 0
597 "08000000",
598 "04000000",
599 "0c000000",
600 },
601 {
602 "02000000", // bucket 1
603 "0a000000",
604 "06000000",
605 "0e000000",
606 },
607 {
608 "01000000", // bucket 2
609 "09000000",
610 "05000000",
611 "0d000000",
612 },
613 {
614 "03000000", // bucket 3
615 "0b000000",
616 "07000000",
617 "0f000000",
618 },
619 }
620
621 for i := 0; i < len(buckets); i++ {
622 sortKvs(buckets[i])
623 c.Assert(len(buckets[i]), qt.Equals, len(expected[i]))
624 for j := 0; j < len(buckets[i]); j++ {
625 c.Check(hex.EncodeToString(buckets[i][j].k[:4]),
626 qt.Equals, expected[i][j])
627 }
628 }
629}
630
631// compareBytes compares byte slices where the bytes are compared from left to
632// right and each byte is compared by bit from right to left
633func compareBytes(a, b []byte) bool {
634 // WIP
635 for i := 0; i < len(a); i++ {
636 for j := 0; j < 8; j++ {
637 aBit := a[i] & (1 << j)
638 bBit := b[i] & (1 << j)
639 if aBit > bBit {
640 return false
641 } else if aBit < bBit {
642 return true
643 }
644 }
645 }
646 return false
647}
648
649// sortKvs sorts the kv by path
650func sortKvs(kvs []kv) {
651 sort.Slice(kvs, func(i, j int) bool {
652 return compareBytes(kvs[i].keyPath, kvs[j].keyPath)
653 })
654}
655
656func TestAddBatchTreeNotEmpty(t *testing.T) {
657 c := qt.New(t)
658
659 nLeafs := 4096
660 initialNLeafs := 900
661
662 tree1, tree2 := testInit(c, initialNLeafs)
663 tree2.dbgInit()
664
665 bLen := tree1.HashFunction().Len()
666 start := time.Now()
667 for i := initialNLeafs; i < nLeafs; i++ {
668 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
669 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
670 if err := tree1.Add(k, v); err != nil {
671 t.Fatal(err)
672 }
673 }
674 time1 := time.Since(start)
675
676 // prepare the key-values to be added
677 var keys, values [][]byte
678 for i := initialNLeafs; i < nLeafs; i++ {
679 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
680 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
681 keys = append(keys, k)
682 values = append(values, v)
683 }
684 start = time.Now()
685 invalids, err := tree2.AddBatch(keys, values)
686 c.Assert(err, qt.IsNil)
687 time2 := time.Since(start)
688 if debug {
689 debugTime("Case tree not empty, AddBatch", time1, time2)
690 printTestContext(" ", nLeafs, "Poseidon", "memory")
691 tree2.dbg.print(" ")
692 }
693 c.Check(len(invalids), qt.Equals, 0)
694
695 // check that both trees roots are equal
696 checkRoots(c, tree1, tree2)
697}
698
699func TestAddBatchNotEmptyUnbalanced(t *testing.T) {
700 c := qt.New(t)
701
702 nLeafs := 4096
703 initialNLeafs := 900
704
705 tree1, _ := testInit(c, initialNLeafs)
706 bLen := tree1.HashFunction().Len()
707
708 start := time.Now()
709 for i := initialNLeafs; i < nLeafs; i++ {
710 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
711 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
712 if err := tree1.Add(k, v); err != nil {
713 t.Fatal(err)
714 }
715 }
716 time1 := time.Since(start)
717
718 database2, err := badgerdb.New(db.Options{Path: c.TempDir()})
719 c.Assert(err, qt.IsNil)
720 tree2, err := NewTree(Config{database2, 256, DefaultThresholdNLeafs,
721 HashFunctionPoseidon})
722 c.Assert(err, qt.IsNil)
723 defer tree2.db.Close() //nolint:errcheck
724 tree2.dbgInit()
725
726 var keys, values [][]byte
727 // add the initial leafs to fill a bit the tree before calling the
728 // AddBatch method
729 for i := 0; i < initialNLeafs; i++ {
730 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
731 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
732 // use only the keys of one bucket, store the not used ones for
733 // later
734 if i%4 != 0 {
735 keys = append(keys, k)
736 values = append(values, v)
737 continue
738 }
739 if err := tree2.Add(k, v); err != nil {
740 t.Fatal(err)
741 }
742 }
743
744 for i := initialNLeafs; i < nLeafs; i++ {
745 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
746 v := BigIntToBytes(bLen, big.NewInt(int64(i*2)))
747 keys = append(keys, k)
748 values = append(values, v)
749 }
750 start = time.Now()
751 invalids, err := tree2.AddBatch(keys, values)
752 c.Assert(err, qt.IsNil)
753 time2 := time.Since(start)
754 if debug {
755 debugTime("Case tree not empty & unbalanced, AddBatch", time1, time2)
756 printTestContext(" ", nLeafs, "Poseidon", "memory")
757 tree2.dbg.print(" ")
758 }
759 c.Check(len(invalids), qt.Equals, 0)
760
761 // check that both trees roots are equal
762 checkRoots(c, tree1, tree2)
763}
764
765func TestFlp2(t *testing.T) {
766 c := qt.New(t)
767 c.Assert(flp2(31), qt.Equals, 16)
768 c.Assert(flp2(32), qt.Equals, 32)
769 c.Assert(flp2(33), qt.Equals, 32)
770 c.Assert(flp2(63), qt.Equals, 32)
771 c.Assert(flp2(64), qt.Equals, 64)
772 c.Assert(flp2(9000), qt.Equals, 8192)
773}
774
775func TestAddBatchBench(t *testing.T) {
776 nLeafs := 50_000
777 printTestContext("TestAddBatchBench: ", nLeafs, "Blake2b", "badgerdb")
778
779 // prepare inputs
780 var ks, vs [][]byte
781 for i := 0; i < nLeafs; i++ {
782 k := randomBytes(32)
783 v := randomBytes(32)
784 ks = append(ks, k)
785 vs = append(vs, v)
786 }
787
788 benchAdd(t, ks, vs)
789
790 benchAddBatch(t, ks, vs)
791}
792
793func benchAdd(t *testing.T, ks, vs [][]byte) {
794 c := qt.New(t)
795
796 database, err := badgerdb.New(db.Options{Path: c.TempDir()})
797 c.Assert(err, qt.IsNil)
798 tree, err := NewTree(Config{database, 256, DefaultThresholdNLeafs,
799 HashFunctionBlake2b})
800 c.Assert(err, qt.IsNil)
801 defer tree.db.Close() //nolint:errcheck
802
803 start := time.Now()
804 for i := 0; i < len(ks); i++ {
805 err = tree.Add(ks[i], vs[i])
806 c.Assert(err, qt.IsNil)
807 }
808 if debug {
809 printRes(" Add loop", time.Since(start))
810 tree.dbg.print(" ")
811 }
812}
813
814func benchAddBatch(t *testing.T, ks, vs [][]byte) {
815 c := qt.New(t)
816
817 database, err := badgerdb.New(db.Options{Path: c.TempDir()})
818 c.Assert(err, qt.IsNil)
819 tree, err := NewTree(Config{database, 256, DefaultThresholdNLeafs,
820 HashFunctionBlake2b})
821 c.Assert(err, qt.IsNil)
822 defer tree.db.Close() //nolint:errcheck
823
824 tree.dbgInit()
825
826 start := time.Now()
827 invalids, err := tree.AddBatch(ks, vs)
828 if debug {
829 printRes(" AddBatch", time.Since(start))
830 tree.dbg.print(" ")
831 }
832 c.Assert(err, qt.IsNil)
833 c.Assert(len(invalids), qt.Equals, 0)
834}
835
836func TestDbgStats(t *testing.T) {
837 c := qt.New(t)
838
839 nLeafs := 10_000
840
841 // prepare inputs
842 var ks, vs [][]byte
843 for i := 0; i < nLeafs; i++ {
844 k := randomBytes(32)
845 v := randomBytes(32)
846 ks = append(ks, k)
847 vs = append(vs, v)
848 }
849
850 // 1
851 database1, err := badgerdb.New(db.Options{Path: c.TempDir()})
852 c.Assert(err, qt.IsNil)
853 tree1, err := NewTree(Config{database1, 256, DefaultThresholdNLeafs,
854 HashFunctionBlake2b})
855 c.Assert(err, qt.IsNil)
856 defer tree1.db.Close() //nolint:errcheck
857
858 tree1.dbgInit()
859
860 for i := 0; i < len(ks); i++ {
861 err = tree1.Add(ks[i], vs[i])
862 c.Assert(err, qt.IsNil)
863 }
864
865 // 2
866 database2, err := badgerdb.New(db.Options{Path: c.TempDir()})
867 c.Assert(err, qt.IsNil)
868 tree2, err := NewTree(Config{database2, 256, DefaultThresholdNLeafs,
869 HashFunctionBlake2b})
870 c.Assert(err, qt.IsNil)
871 defer tree2.db.Close() //nolint:errcheck
872
873 tree2.dbgInit()
874
875 invalids, err := tree2.AddBatch(ks, vs)
876 c.Assert(err, qt.IsNil)
877 c.Assert(len(invalids), qt.Equals, 0)
878
879 // 3
880 database3, err := badgerdb.New(db.Options{Path: c.TempDir()})
881 c.Assert(err, qt.IsNil)
882 tree3, err := NewTree(Config{database3, 256, DefaultThresholdNLeafs,
883 HashFunctionBlake2b})
884 c.Assert(err, qt.IsNil)
885 defer tree3.db.Close() //nolint:errcheck
886
887 tree3.dbgInit()
888
889 // add few key-values
890 // invalids, err = tree3.AddBatch(ks[:], vs[:])
891 invalids, err = tree3.AddBatch(ks[:1000], vs[:1000])
892 c.Assert(err, qt.IsNil)
893 c.Assert(len(invalids), qt.Equals, 0)
894
895 // add the rest of key-values
896 invalids, err = tree3.AddBatch(ks[1000:], vs[1000:])
897 c.Assert(err, qt.IsNil)
898 c.Assert(len(invalids), qt.Equals, 0)
899
900 checkRoots(c, tree1, tree2)
901 checkRoots(c, tree1, tree3)
902
903 if debug {
904 fmt.Println("TestDbgStats")
905 tree1.dbg.print(" add in loop in emptyTree ")
906 tree2.dbg.print(" addbatch caseEmptyTree ")
907 tree3.dbg.print(" addbatch caseNotEmptyTree ")
908 }
909}
910
911func TestLoadVT(t *testing.T) {
912 c := qt.New(t)
913
914 nLeafs := 1024
915
916 database, err := badgerdb.New(db.Options{Path: c.TempDir()})
917 c.Assert(err, qt.IsNil)
918 tree, err := NewTree(Config{database, 256, DefaultThresholdNLeafs,
919 HashFunctionPoseidon})
920 c.Assert(err, qt.IsNil)
921 defer tree.db.Close() //nolint:errcheck
922
923 var keys, values [][]byte
924 for i := 0; i < nLeafs; i++ {
925 k := randomBytes(31)
926 v := randomBytes(31)
927 keys = append(keys, k)
928 values = append(values, v)
929 }
930 invalids, err := tree.AddBatch(keys, values)
931 c.Assert(err, qt.IsNil)
932 c.Check(len(invalids), qt.Equals, 0)
933
934 rTx := tree.db.ReadTx()
935 defer rTx.Discard()
936 vt, err := tree.loadVT(rTx)
937 c.Assert(err, qt.IsNil)
938 _, err = vt.computeHashes()
939 c.Assert(err, qt.IsNil)
940
941 // check that tree & vt roots are equal
942 root, err := tree.Root()
943 c.Assert(err, qt.IsNil)
944 c.Check(root, qt.DeepEquals, vt.root.h)
945}
946
947// TestAddKeysWithEmptyValues calls AddBatch giving an array of empty values
948func TestAddKeysWithEmptyValues(t *testing.T) {
949 c := qt.New(t)
950
951 nLeafs := 1024
952
953 database, err := badgerdb.New(db.Options{Path: c.TempDir()})
954 c.Assert(err, qt.IsNil)
955 tree, err := NewTree(Config{database, 256, DefaultThresholdNLeafs,
956 HashFunctionPoseidon})
957 c.Assert(err, qt.IsNil)
958 defer tree.db.Close() //nolint:errcheck
959
960 bLen := 32
961 var keys, values [][]byte
962 for i := 0; i < nLeafs; i++ {
963 k := BigIntToBytes(bLen, big.NewInt(int64(i)))
964 v := []byte{}
965 keys = append(keys, k)
966 values = append(values, v)
967 }
968
969 for i := 0; i < nLeafs; i++ {
970 if err := tree.Add(keys[i], values[i]); err != nil {
971 t.Fatal(err)
972 }
973 }
974
975 database2, err := badgerdb.New(db.Options{Path: c.TempDir()})
976 c.Assert(err, qt.IsNil)
977 tree2, err := NewTree(Config{database2, 256, DefaultThresholdNLeafs,
978 HashFunctionPoseidon})
979 c.Assert(err, qt.IsNil)
980 defer tree2.db.Close() //nolint:errcheck
981 tree2.dbgInit()
982
983 invalids, err := tree2.AddBatch(keys, values)
984 c.Assert(err, qt.IsNil)
985 c.Check(len(invalids), qt.Equals, 0)
986 // check that both trees roots are equal
987 checkRoots(c, tree, tree2)
988
989 // use tree3 to add nil value array
990 database3, err := badgerdb.New(db.Options{Path: c.TempDir()})
991 c.Assert(err, qt.IsNil)
992 tree3, err := NewTree(Config{database3, 256, DefaultThresholdNLeafs,
993 HashFunctionPoseidon})
994 c.Assert(err, qt.IsNil)
995 defer tree3.db.Close() //nolint:errcheck
996
997 invalids, err = tree3.AddBatch(keys, nil)
998 c.Assert(err, qt.IsNil)
999 c.Check(len(invalids), qt.Equals, 0)
1000 checkRoots(c, tree, tree3)
1001
1002 kAux, proofV, siblings, existence, err := tree2.GenProof(keys[9])
1003 c.Assert(err, qt.IsNil)
1004 c.Assert(proofV, qt.DeepEquals, values[9])
1005 c.Assert(keys[9], qt.DeepEquals, kAux)
1006 c.Assert(existence, qt.IsTrue)
1007
1008 // check with empty array
1009 root, err := tree.Root()
1010 c.Assert(err, qt.IsNil)
1011 verif, err := CheckProof(tree.hashFunction, keys[9], []byte{}, root, siblings)
1012 c.Assert(err, qt.IsNil)
1013 c.Check(verif, qt.IsTrue)
1014
1015 // check with array with only 1 zero
1016 verif, err = CheckProof(tree.hashFunction, keys[9], []byte{0}, root, siblings)
1017 c.Assert(err, qt.IsNil)
1018 c.Check(verif, qt.IsTrue)
1019
1020 // check with array with 32 zeroes
1021 e32 := []byte{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1022 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
1023 c.Assert(len(e32), qt.Equals, 32)
1024 verif, err = CheckProof(tree.hashFunction, keys[9], e32, root, siblings)
1025 c.Assert(err, qt.IsNil)
1026 c.Check(verif, qt.IsTrue)
1027
1028 // check with array with value!=0 returns false at verification
1029 verif, err = CheckProof(tree.hashFunction, keys[9], []byte{0, 1}, root, siblings)
1030 c.Assert(err, qt.IsNil)
1031 c.Check(verif, qt.IsFalse)
1032}
1033
1034func TestAddBatchThresholdInDisk(t *testing.T) {
1035 c := qt.New(t)
1036
1037 // customize thresholdNLeafs for the test
1038 testThresholdNLeafs := 1024
1039
1040 database1, err := badgerdb.New(db.Options{Path: c.TempDir()})
1041 c.Assert(err, qt.IsNil)
1042 tree1, err := NewTree(Config{database1, 256, testThresholdNLeafs,
1043 HashFunctionBlake2b})
1044 c.Assert(err, qt.IsNil)
1045 defer tree1.db.Close() //nolint:errcheck
1046
1047 database2, err := pebbledb.New(db.Options{Path: c.TempDir()})
1048 c.Assert(err, qt.IsNil)
1049 tree2, err := NewTree(Config{database2, 256, testThresholdNLeafs,
1050 HashFunctionBlake2b})
1051 c.Assert(err, qt.IsNil)
1052 defer tree2.db.Close() //nolint:errcheck
1053
1054 database3, err := pebbledb.New(db.Options{Path: c.TempDir()})
1055 c.Assert(err, qt.IsNil)
1056 tree3, err := NewTree(Config{database3, 256, testThresholdNLeafs,
1057 HashFunctionBlake2b})
1058 c.Assert(err, qt.IsNil)
1059 defer tree3.db.Close() //nolint:errcheck
1060
1061 var keys, values [][]byte
1062 for i := 0; i < 3*testThresholdNLeafs; i++ {
1063 k := randomBytes(32)
1064 v := randomBytes(32)
1065 if err := tree1.Add(k, v); err != nil {
1066 t.Fatal(err)
1067 }
1068 if i < testThresholdNLeafs+1 {
1069 if err := tree2.Add(k, v); err != nil {
1070 t.Fatal(err)
1071 }
1072 }
1073 // store for later addition through AddBatch
1074 keys = append(keys, k)
1075 values = append(values, v)
1076 }
1077
1078 invalids, err := tree2.AddBatch(keys[testThresholdNLeafs+1:], values[testThresholdNLeafs+1:])
1079 c.Assert(err, qt.IsNil)
1080 c.Check(len(invalids), qt.Equals, 0)
1081 // check that both trees roots are equal
1082 checkRoots(c, tree1, tree2)
1083
1084 // call directly the tree3.addBatchInDisk to ensure that is tested
1085 wTx := tree3.db.WriteTx()
1086 defer wTx.Discard()
1087 invalids, err = tree3.addBatchInDisk(wTx, keys, values)
1088 c.Assert(err, qt.IsNil)
1089 err = wTx.Commit()
1090 c.Assert(err, qt.IsNil)
1091 c.Check(len(invalids), qt.Equals, 0)
1092 // check that both trees roots are equal
1093 checkRoots(c, tree1, tree3)
1094}
1095
1096// TODO test adding batch with multiple invalid keys
1097// TODO for tests of AddBatch, if the root does not match the Add root, bulk
1098// all the leafs of both trees into a log file to later be able to debug and
1099// recreate the case