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