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