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