arbo/addbatch_test.go
addbatch_test.goRaw
1package arbo
2
3import (
4 "crypto/rand"
5 "encoding/hex"
6 "fmt"
7 "math/big"
8 "testing"
9 "time"
10
11 qt "github.com/frankban/quicktest"
12 "github.com/iden3/go-merkletree/db/memory"
13)
14
15var debug = true
16
17func debugTime(descr string, time1, time2 time.Duration) {
18 if debug {
19 fmt.Printf("%s was %f times faster than without AddBatch\n",
20 descr, float64(time1)/float64(time2))
21 }
22}
23
24func testInit(c *qt.C, n int) (*Tree, *Tree) {
25 tree1, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
26 c.Assert(err, qt.IsNil)
27 defer tree1.db.Close()
28
29 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
30 c.Assert(err, qt.IsNil)
31 defer tree2.db.Close()
32
33 // add the initial leafs to fill a bit the trees before calling the
34 // AddBatch method
35 for i := 0; i < n; i++ {
36 k := BigIntToBytes(big.NewInt(int64(i)))
37 v := BigIntToBytes(big.NewInt(int64(i * 2)))
38 if err := tree1.Add(k, v); err != nil {
39 c.Fatal(err)
40 }
41 if err := tree2.Add(k, v); err != nil {
42 c.Fatal(err)
43 }
44 }
45 return tree1, tree2
46}
47
48func TestAddBatchCaseA(t *testing.T) {
49 c := qt.New(t)
50
51 nLeafs := 1024
52
53 tree, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
54 c.Assert(err, qt.IsNil)
55 defer tree.db.Close()
56
57 start := time.Now()
58 for i := 0; i < nLeafs; i++ {
59 k := BigIntToBytes(big.NewInt(int64(i)))
60 v := BigIntToBytes(big.NewInt(int64(i * 2)))
61 if err := tree.Add(k, v); err != nil {
62 t.Fatal(err)
63 }
64 }
65 time1 := time.Since(start)
66
67 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
68 c.Assert(err, qt.IsNil)
69 defer tree2.db.Close()
70
71 var keys, values [][]byte
72 for i := 0; i < nLeafs; i++ {
73 k := BigIntToBytes(big.NewInt(int64(i)))
74 v := BigIntToBytes(big.NewInt(int64(i * 2)))
75 keys = append(keys, k)
76 values = append(values, v)
77 }
78 start = time.Now()
79 indexes, err := tree2.AddBatch(keys, values)
80 c.Assert(err, qt.IsNil)
81 time2 := time.Since(start)
82 debugTime("CASE A, AddBatch", time1, time2)
83 c.Check(len(indexes), qt.Equals, 0)
84
85 // check that both trees roots are equal
86 c.Check(tree2.Root(), qt.DeepEquals, tree.Root())
87}
88
89func TestAddBatchCaseANotPowerOf2(t *testing.T) {
90 c := qt.New(t)
91
92 nLeafs := 1027
93
94 tree, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
95 c.Assert(err, qt.IsNil)
96 defer tree.db.Close()
97
98 for i := 0; i < nLeafs; i++ {
99 k := BigIntToBytes(big.NewInt(int64(i)))
100 v := BigIntToBytes(big.NewInt(int64(i * 2)))
101 if err := tree.Add(k, v); err != nil {
102 t.Fatal(err)
103 }
104 }
105
106 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
107 c.Assert(err, qt.IsNil)
108 defer tree2.db.Close()
109
110 var keys, values [][]byte
111 for i := 0; i < nLeafs; i++ {
112 k := BigIntToBytes(big.NewInt(int64(i)))
113 v := BigIntToBytes(big.NewInt(int64(i * 2)))
114 keys = append(keys, k)
115 values = append(values, v)
116 }
117 indexes, err := tree2.AddBatch(keys, values)
118 c.Assert(err, qt.IsNil)
119 c.Check(len(indexes), qt.Equals, 0)
120
121 // check that both trees roots are equal
122 c.Check(tree2.Root(), qt.DeepEquals, tree.Root())
123}
124
125func randomBytes(n int) []byte {
126 b := make([]byte, n)
127 _, err := rand.Read(b)
128 if err != nil {
129 panic(err)
130 }
131 return b
132}
133
134func TestBuildTreeBottomUpSingleThread(t *testing.T) {
135 c := qt.New(t)
136 tree1, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
137 c.Assert(err, qt.IsNil)
138 defer tree1.db.Close()
139
140 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
141 c.Assert(err, qt.IsNil)
142 defer tree2.db.Close()
143
144 testvectorKeys := []string{
145 "1c7c2265e368314ca58ed2e1f33a326f1220e234a566d55c3605439dbe411642",
146 "2c9f0a578afff5bfa4e0992a43066460faaab9e8e500db0b16647c701cdb16bf",
147 "1c45cb31f2fa39ec7b9ebf0fad40e0b8296016b5ce8844ae06ff77226379d9a5",
148 "d8af98bbbb585129798ae54d5eabbc9d0561d583faf1663b3a3724d15bda4ec7",
149 }
150 var keys, values [][]byte
151 for i := 0; i < len(testvectorKeys); i++ {
152 key, err := hex.DecodeString(testvectorKeys[i])
153 c.Assert(err, qt.IsNil)
154 keys = append(keys, key)
155 values = append(values, []byte{0})
156 }
157
158 for i := 0; i < len(keys); i++ {
159 if err := tree1.Add(keys[i], values[i]); err != nil {
160 t.Fatal(err)
161 }
162 }
163
164 kvs, err := tree2.keysValuesToKvs(keys, values)
165 c.Assert(err, qt.IsNil)
166 sortKvs(kvs)
167
168 tree2.tx, err = tree2.db.NewTx()
169 c.Assert(err, qt.IsNil)
170 // indexes, err := tree2.buildTreeBottomUpSingleThread(kvs)
171 indexes, err := tree2.buildTreeBottomUp(4, kvs)
172 c.Assert(err, qt.IsNil)
173 // tree1.PrintGraphviz(nil)
174 // tree2.PrintGraphviz(nil)
175
176 c.Check(len(indexes), qt.Equals, 0)
177
178 // check that both trees roots are equal
179 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
180 // 15b6a23945ae6c81342b7eb14e70fff50812dc8791cb15ec791eb08f91784139
181}
182
183func TestAddBatchCaseATestVector(t *testing.T) {
184 c := qt.New(t)
185 tree1, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
186 c.Assert(err, qt.IsNil)
187 defer tree1.db.Close()
188
189 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
190 c.Assert(err, qt.IsNil)
191 defer tree2.db.Close()
192
193 // leafs in 2nd level subtrees: [ 6, 0, 1, 1]
194 testvectorKeys := []string{
195 "1c7c2265e368314ca58ed2e1f33a326f1220e234a566d55c3605439dbe411642",
196 "2c9f0a578afff5bfa4e0992a43066460faaab9e8e500db0b16647c701cdb16bf",
197 "1c45cb31f2fa39ec7b9ebf0fad40e0b8296016b5ce8844ae06ff77226379d9a5",
198 "d8af98bbbb585129798ae54d5eabbc9d0561d583faf1663b3a3724d15bda4ec7",
199 }
200 var keys, values [][]byte
201 for i := 0; i < len(testvectorKeys); i++ {
202 key, err := hex.DecodeString(testvectorKeys[i])
203 c.Assert(err, qt.IsNil)
204 keys = append(keys, key)
205 values = append(values, []byte{0})
206 }
207
208 for i := 0; i < len(keys); i++ {
209 if err := tree1.Add(keys[i], values[i]); err != nil {
210 t.Fatal(err)
211 }
212 }
213
214 indexes, err := tree2.AddBatch(keys, values)
215 c.Assert(err, qt.IsNil)
216 // tree1.PrintGraphviz(nil)
217 // tree2.PrintGraphviz(nil)
218
219 c.Check(len(indexes), qt.Equals, 0)
220
221 // check that both trees roots are equal
222 // fmt.Println(hex.EncodeToString(tree1.Root()))
223 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
224
225 //////
226
227 // tree1, err = NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
228 // c.Assert(err, qt.IsNil)
229 // defer tree1.db.Close()
230 //
231 // tree2, err = NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
232 // c.Assert(err, qt.IsNil)
233 // defer tree2.db.Close()
234 //
235 // // leafs in 2nd level subtrees: [ 6, 0, 1, 1]
236 // testvectorKeys = []string{
237 // "1c7c2265e368314ca58ed2e1f33a326f1220e234a566d55c3605439dbe411642",
238 // "2c9f0a578afff5bfa4e0992a43066460faaab9e8e500db0b16647c701cdb16bf",
239 // "9cb87ec67e875c61390edcd1ab517f443591047709a4d4e45b0f9ed980857b8e",
240 // "9b4e9e92e974a589f426ceeb4cb291dc24893513fecf8e8460992dcf52621d4d",
241 // "1c45cb31f2fa39ec7b9ebf0fad40e0b8296016b5ce8844ae06ff77226379d9a5",
242 // "d8af98bbbb585129798ae54d5eabbc9d0561d583faf1663b3a3724d15bda4ec7",
243 // "3cd55dbfb8f975f20a0925dfbdabe79fa2d51dd0268afbb8ba6b01de9dfcdd3c",
244 // "5d0a9d6d9f197c091bf054fac9cb60e11ec723d6610ed8578e617b4d46cb43d5",
245 // }
246 // keys = [][]byte{}
247 // values = [][]byte{}
248 // for i := 0; i < len(testvectorKeys); i++ {
249 // key, err := hex.DecodeString(testvectorKeys[i])
250 // c.Assert(err, qt.IsNil)
251 // keys = append(keys, key)
252 // values = append(values, []byte{0})
253 // }
254 //
255 // for i := 0; i < len(keys); i++ {
256 // if err := tree1.Add(keys[i], values[i]); err != nil {
257 // t.Fatal(err)
258 // }
259 // }
260 //
261 // indexes, err = tree2.AddBatch(keys, values)
262 // c.Assert(err, qt.IsNil)
263 // tree1.PrintGraphviz(nil)
264 // tree2.PrintGraphviz(nil)
265 //
266 // c.Check(len(indexes), qt.Equals, 0)
267 //
268 // // check that both trees roots are equal
269 // // c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
270}
271
272func TestAddBatchCaseARandomKeys(t *testing.T) {
273 c := qt.New(t)
274
275 nLeafs := 8
276
277 tree1, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
278 c.Assert(err, qt.IsNil)
279 defer tree1.db.Close()
280
281 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
282 c.Assert(err, qt.IsNil)
283 defer tree2.db.Close()
284
285 var keys, values [][]byte
286 for i := 0; i < nLeafs; i++ {
287 keys = append(keys, randomBytes(32))
288 // values = append(values, randomBytes(32))
289 values = append(values, []byte{0})
290 // fmt.Println("K", hex.EncodeToString(keys[i]))
291 }
292
293 // TMP:
294 keys[0], _ = hex.DecodeString("1c7c2265e368314ca58ed2e1f33a326f1220e234a566d55c3605439dbe411642")
295 keys[1], _ = hex.DecodeString("2c9f0a578afff5bfa4e0992a43066460faaab9e8e500db0b16647c701cdb16bf")
296 keys[2], _ = hex.DecodeString("9cb87ec67e875c61390edcd1ab517f443591047709a4d4e45b0f9ed980857b8e")
297 keys[3], _ = hex.DecodeString("9b4e9e92e974a589f426ceeb4cb291dc24893513fecf8e8460992dcf52621d4d")
298 keys[4], _ = hex.DecodeString("1c45cb31f2fa39ec7b9ebf0fad40e0b8296016b5ce8844ae06ff77226379d9a5")
299 keys[5], _ = hex.DecodeString("d8af98bbbb585129798ae54d5eabbc9d0561d583faf1663b3a3724d15bda4ec7")
300 keys[6], _ = hex.DecodeString("3cd55dbfb8f975f20a0925dfbdabe79fa2d51dd0268afbb8ba6b01de9dfcdd3c")
301 keys[7], _ = hex.DecodeString("5d0a9d6d9f197c091bf054fac9cb60e11ec723d6610ed8578e617b4d46cb43d5")
302
303 for i := 0; i < len(keys); i++ {
304 if err := tree1.Add(keys[i], values[i]); err != nil {
305 t.Fatal(err)
306 }
307 }
308
309 indexes, err := tree2.AddBatch(keys, values)
310 c.Assert(err, qt.IsNil)
311 // tree1.PrintGraphviz(nil)
312 // tree2.PrintGraphviz(nil)
313
314 c.Check(len(indexes), qt.Equals, 0)
315
316 // check that both trees roots are equal
317 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
318}
319
320func TestAddBatchCaseB(t *testing.T) {
321 c := qt.New(t)
322
323 nLeafs := 1024
324 initialNLeafs := 99 // TMP TODO use const minLeafsThreshold-1 once ready
325
326 tree1, tree2 := testInit(c, initialNLeafs)
327
328 start := time.Now()
329 for i := initialNLeafs; i < nLeafs; i++ {
330 k := BigIntToBytes(big.NewInt(int64(i)))
331 v := BigIntToBytes(big.NewInt(int64(i * 2)))
332 if err := tree1.Add(k, v); err != nil {
333 t.Fatal(err)
334 }
335 }
336 time1 := time.Since(start)
337
338 // prepare the key-values to be added
339 var keys, values [][]byte
340 for i := initialNLeafs; i < nLeafs; i++ {
341 k := BigIntToBytes(big.NewInt(int64(i)))
342 v := BigIntToBytes(big.NewInt(int64(i * 2)))
343 keys = append(keys, k)
344 values = append(values, v)
345 }
346 start = time.Now()
347 indexes, err := tree2.AddBatch(keys, values)
348 c.Assert(err, qt.IsNil)
349 time2 := time.Since(start)
350 debugTime("CASE B, AddBatch", time1, time2)
351 c.Check(len(indexes), qt.Equals, 0)
352
353 // check that both trees roots are equal
354 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
355}
356
357func TestAddBatchCaseBRepeatedLeafs(t *testing.T) {
358 c := qt.New(t)
359
360 nLeafs := 1024
361 initialNLeafs := 99 // TMP TODO use const minLeafsThreshold-1 once ready
362
363 tree1, tree2 := testInit(c, initialNLeafs)
364
365 for i := initialNLeafs; i < nLeafs; i++ {
366 k := BigIntToBytes(big.NewInt(int64(i)))
367 v := BigIntToBytes(big.NewInt(int64(i * 2)))
368 if err := tree1.Add(k, v); err != nil {
369 t.Fatal(err)
370 }
371 }
372
373 // prepare the key-values to be added, including already existing keys
374 var keys, values [][]byte
375 for i := 0; i < nLeafs; i++ {
376 k := BigIntToBytes(big.NewInt(int64(i)))
377 v := BigIntToBytes(big.NewInt(int64(i * 2)))
378 keys = append(keys, k)
379 values = append(values, v)
380 }
381 indexes, err := tree2.AddBatch(keys, values)
382 c.Assert(err, qt.IsNil)
383 c.Check(len(indexes), qt.Equals, initialNLeafs)
384
385 // check that both trees roots are equal
386 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
387}
388
389func TestCombineInKVSet(t *testing.T) {
390 c := qt.New(t)
391
392 var a, b, expected []kv
393 for i := 0; i < 10; i++ {
394 k := BigIntToBytes(big.NewInt(int64(i)))
395 kv := kv{k: k}
396 if i < 7 {
397 a = append(a, kv)
398 }
399 if i >= 4 {
400 b = append(b, kv)
401 }
402 expected = append(expected, kv)
403 }
404
405 r, invalids := combineInKVSet(a, b)
406 for i := 0; i < len(r); i++ {
407 c.Assert(r[i].k, qt.DeepEquals, expected[i].k)
408 }
409 c.Assert(len(invalids), qt.Equals, 7-4)
410}
411
412func TestGetKeysAtLevel(t *testing.T) {
413 c := qt.New(t)
414
415 tree, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
416 c.Assert(err, qt.IsNil)
417 defer tree.db.Close()
418
419 for i := 0; i < 32; i++ {
420 k := BigIntToBytes(big.NewInt(int64(i)))
421 v := BigIntToBytes(big.NewInt(int64(i * 2)))
422 if err := tree.Add(k, v); err != nil {
423 t.Fatal(err)
424 }
425 }
426
427 keys, err := tree.getKeysAtLevel(2)
428 c.Assert(err, qt.IsNil)
429 expected := []string{
430 "a5d5f14fce7348e40751496cf25d107d91b0bd043435b9577d778a01f8aa6111",
431 "e9e8dd9b28a7f81d1ff34cb5cefc0146dd848b31031a427b79bdadb62e7f6910",
432 }
433 for i := 0; i < len(keys); i++ {
434 c.Assert(hex.EncodeToString(keys[i]), qt.Equals, expected[i])
435 }
436
437 keys, err = tree.getKeysAtLevel(3)
438 c.Assert(err, qt.IsNil)
439 expected = []string{
440 "9f12c13e52bca96ad4882a26558e48ab67ddd63e062b839207e893d961390f01",
441 "16d246dd6826ec7346c7328f11c4261facf82d4689f33263ff6e207956a77f21",
442 "4a22cc901c6337daa17a431fa20170684b710e5f551509511492ec24e81a8f2f",
443 "470d61abcbd154977bffc9a9ec5a8daff0caabcf2a25e8441f604c79daa0f82d",
444 }
445 for i := 0; i < len(keys); i++ {
446 c.Assert(hex.EncodeToString(keys[i]), qt.Equals, expected[i])
447 }
448
449 keys, err = tree.getKeysAtLevel(4)
450 c.Assert(err, qt.IsNil)
451 expected = []string{
452 "7a5d1c81f7b96318012de3417e53d4f13df5b1337718651cd29d0cb0a66edd20",
453 "3408213e4e844bdf3355eb8781c74e31626812898c2dbe141ed6d2c92256fc1c",
454 "dfd8a4d0b6954a3e9f3892e655b58d456eeedf9367f27dfdd9bc2dd6a5577312",
455 "9e99fbec06fb2a6725997c12c4995f62725eb4cce4808523a5a5e80cca64b007",
456 "0befa1e070231dbf4e8ff841c05878cdec823e0c09594c24910a248b3ff5a628",
457 "b7131b0a15c772a57005a4dc5d0d6dd4b3414f5d9ee7408ce5e86c5ab3520e04",
458 "6d1abe0364077846a56bab1deb1a04883eb796b74fe531a7676a9a370f83ab21",
459 "4270116394bede69cf9cd72069eca018238080380bef5de75be8dcbbe968e105",
460 }
461 for i := 0; i < len(keys); i++ {
462 c.Assert(hex.EncodeToString(keys[i]), qt.Equals, expected[i])
463 }
464}
465
466func TestSplitInBuckets(t *testing.T) {
467 c := qt.New(t)
468
469 nLeafs := 16
470 kvs := make([]kv, nLeafs)
471 for i := 0; i < nLeafs; i++ {
472 k := BigIntToBytes(big.NewInt(int64(i)))
473 v := BigIntToBytes(big.NewInt(int64(i * 2)))
474 keyPath := make([]byte, 32)
475 copy(keyPath[:], k)
476 kvs[i].pos = i
477 kvs[i].keyPath = k
478 kvs[i].k = k
479 kvs[i].v = v
480 }
481
482 // check keyToBucket results for 4 buckets & 8 keys
483 c.Assert(keyToBucket(kvs[0].k, 4), qt.Equals, 0)
484 c.Assert(keyToBucket(kvs[1].k, 4), qt.Equals, 2)
485 c.Assert(keyToBucket(kvs[2].k, 4), qt.Equals, 1)
486 c.Assert(keyToBucket(kvs[3].k, 4), qt.Equals, 3)
487 c.Assert(keyToBucket(kvs[4].k, 4), qt.Equals, 0)
488 c.Assert(keyToBucket(kvs[5].k, 4), qt.Equals, 2)
489 c.Assert(keyToBucket(kvs[6].k, 4), qt.Equals, 1)
490 c.Assert(keyToBucket(kvs[7].k, 4), qt.Equals, 3)
491
492 // check keyToBucket results for 8 buckets & 8 keys
493 c.Assert(keyToBucket(kvs[0].k, 8), qt.Equals, 0)
494 c.Assert(keyToBucket(kvs[1].k, 8), qt.Equals, 4)
495 c.Assert(keyToBucket(kvs[2].k, 8), qt.Equals, 2)
496 c.Assert(keyToBucket(kvs[3].k, 8), qt.Equals, 6)
497 c.Assert(keyToBucket(kvs[4].k, 8), qt.Equals, 1)
498 c.Assert(keyToBucket(kvs[5].k, 8), qt.Equals, 5)
499 c.Assert(keyToBucket(kvs[6].k, 8), qt.Equals, 3)
500 c.Assert(keyToBucket(kvs[7].k, 8), qt.Equals, 7)
501
502 buckets := splitInBuckets(kvs, 4)
503
504 expected := [][]string{
505 {
506 "00000000", // bucket 0
507 "08000000",
508 "04000000",
509 "0c000000",
510 },
511 {
512 "02000000", // bucket 1
513 "0a000000",
514 "06000000",
515 "0e000000",
516 },
517 {
518 "01000000", // bucket 2
519 "09000000",
520 "05000000",
521 "0d000000",
522 },
523 {
524 "03000000", // bucket 3
525 "0b000000",
526 "07000000",
527 "0f000000",
528 },
529 }
530
531 for i := 0; i < len(buckets); i++ {
532 sortKvs(buckets[i])
533 c.Assert(len(buckets[i]), qt.Equals, len(expected[i]))
534 for j := 0; j < len(buckets[i]); j++ {
535 c.Check(hex.EncodeToString(buckets[i][j].k[:4]), qt.Equals, expected[i][j])
536 }
537 }
538}
539
540func TestAddBatchCaseC(t *testing.T) {
541 c := qt.New(t)
542
543 nLeafs := 1024
544 initialNLeafs := 101 // TMP TODO use const minLeafsThreshold+1 once ready
545
546 tree1, tree2 := testInit(c, initialNLeafs)
547
548 start := time.Now()
549 for i := initialNLeafs; i < nLeafs; i++ {
550 k := BigIntToBytes(big.NewInt(int64(i)))
551 v := BigIntToBytes(big.NewInt(int64(i * 2)))
552 if err := tree1.Add(k, v); err != nil {
553 t.Fatal(err)
554 }
555 }
556 time1 := time.Since(start)
557
558 // prepare the key-values to be added
559 var keys, values [][]byte
560 for i := initialNLeafs; i < nLeafs; i++ {
561 k := BigIntToBytes(big.NewInt(int64(i)))
562 v := BigIntToBytes(big.NewInt(int64(i * 2)))
563 keys = append(keys, k)
564 values = append(values, v)
565 }
566 start = time.Now()
567 indexes, err := tree2.AddBatch(keys, values)
568 c.Assert(err, qt.IsNil)
569 time2 := time.Since(start)
570 debugTime("CASE C, AddBatch", time1, time2)
571 c.Check(len(indexes), qt.Equals, 0)
572
573 // check that both trees roots are equal
574 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
575}
576
577func TestAddBatchCaseD(t *testing.T) {
578 c := qt.New(t)
579
580 nLeafs := 4096
581 initialNLeafs := 900
582
583 tree1, tree2 := testInit(c, initialNLeafs)
584
585 start := time.Now()
586 for i := initialNLeafs; i < nLeafs; i++ {
587 k := BigIntToBytes(big.NewInt(int64(i)))
588 v := BigIntToBytes(big.NewInt(int64(i * 2)))
589 if err := tree1.Add(k, v); err != nil {
590 t.Fatal(err)
591 }
592 }
593 time1 := time.Since(start)
594
595 // prepare the key-values to be added
596 var keys, values [][]byte
597 for i := initialNLeafs; i < nLeafs; i++ {
598 k := BigIntToBytes(big.NewInt(int64(i)))
599 v := BigIntToBytes(big.NewInt(int64(i * 2)))
600 keys = append(keys, k)
601 values = append(values, v)
602 }
603 start = time.Now()
604 indexes, err := tree2.AddBatch(keys, values)
605 c.Assert(err, qt.IsNil)
606 time2 := time.Since(start)
607 debugTime("CASE D, AddBatch", time1, time2)
608 c.Check(len(indexes), qt.Equals, 0)
609
610 // check that both trees roots are equal
611 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
612}
613
614func TestAddBatchCaseE(t *testing.T) {
615 c := qt.New(t)
616
617 nLeafs := 4096
618 initialNLeafs := 900
619
620 tree1, _ := testInit(c, initialNLeafs)
621
622 start := time.Now()
623 for i := initialNLeafs; i < nLeafs; i++ {
624 k := BigIntToBytes(big.NewInt(int64(i)))
625 v := BigIntToBytes(big.NewInt(int64(i * 2)))
626 if err := tree1.Add(k, v); err != nil {
627 t.Fatal(err)
628 }
629 }
630 time1 := time.Since(start)
631
632 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
633 c.Assert(err, qt.IsNil)
634 defer tree2.db.Close()
635
636 var keys, values [][]byte
637 // add the initial leafs to fill a bit the tree before calling the
638 // AddBatch method
639 for i := 0; i < initialNLeafs; i++ {
640 k := BigIntToBytes(big.NewInt(int64(i)))
641 v := BigIntToBytes(big.NewInt(int64(i * 2)))
642 // use only the keys of one bucket, store the not used ones for
643 // later
644 if i%4 != 0 {
645 keys = append(keys, k)
646 values = append(values, v)
647 continue
648 }
649 if err := tree2.Add(k, v); err != nil {
650 t.Fatal(err)
651 }
652 }
653
654 for i := initialNLeafs; i < nLeafs; i++ {
655 k := BigIntToBytes(big.NewInt(int64(i)))
656 v := BigIntToBytes(big.NewInt(int64(i * 2)))
657 keys = append(keys, k)
658 values = append(values, v)
659 }
660 start = time.Now()
661 indexes, err := tree2.AddBatch(keys, values)
662 c.Assert(err, qt.IsNil)
663 time2 := time.Since(start)
664 debugTime("CASE E, AddBatch", time1, time2)
665 c.Check(len(indexes), qt.Equals, 0)
666
667 // check that both trees roots are equal
668 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
669}
670
671func TestHighestPowerOfTwo(t *testing.T) {
672 c := qt.New(t)
673 c.Assert(highestPowerOfTwo(31), qt.Equals, 16)
674 c.Assert(highestPowerOfTwo(32), qt.Equals, 32)
675 c.Assert(highestPowerOfTwo(33), qt.Equals, 32)
676 c.Assert(highestPowerOfTwo(63), qt.Equals, 32)
677 c.Assert(highestPowerOfTwo(64), qt.Equals, 64)
678}
679
680// func printLeafs(name string, t *Tree) {
681// w := bytes.NewBufferString("")
682//
683// err := t.Iterate(func(k, v []byte) {
684// if v[0] != PrefixValueLeaf {
685// return
686// }
687// leafK, _ := readLeafValue(v)
688// fmt.Fprintf(w, hex.EncodeToString(leafK[:4])+"\n")
689// })
690// if err != nil {
691// panic(err)
692// }
693// err = ioutil.WriteFile(name, w.Bytes(), 0644)
694// if err != nil {
695// panic(err)
696// }
697//
698// }
699
700// func TestComputeCosts(t *testing.T) {
701// fmt.Println(computeSimpleAddCost(10))
702// fmt.Println(computeBottomUpAddCost(10))
703//
704// fmt.Println(computeSimpleAddCost(1024))
705// fmt.Println(computeBottomUpAddCost(1024))
706// }
707
708// TODO test tree with nLeafs > minLeafsThreshold, but that at level L, there is
709// less keys than nBuckets (so CASE C could be applied if first few leafs are
710// added to balance the tree)
711
712// TODO test adding batch with repeated keys in the batch
713// TODO test adding batch with multiple invalid keys