arbo/README.md
README.mdRaw
1# arbo [](https://godoc.org/github.com/arnaucube/arbo)
2
3> *arbo*: tree in Esperanto.
4
5MerkleTree implementation in Go. Compatible with the circomlib implementation of
6the MerkleTree. Specification: https://docs.iden3.io/publications/pdfs/Merkle-Tree.pdf and https://eprint.iacr.org/2018/955.
7
8Main characteristics of arbo are:
9- Allows to define which hash function to use.
10 - So for example, when working with zkSnarks the [Poseidon hash](https://eprint.iacr.org/2019/458.pdf) function can be used, but when not, it can be used the [Blake2b hash](https://www.blake2.net/blake2.pdf) function, which has much faster computation time.
11 - New hash functions can be plugged by just implementing the interface
12- Parallelizes computation by CPUs
13 - See [AddBatch section](https://github.com/arnaucube/arbo#addbatch)
14
15## AddBatch
16The method `tree.AddBatch` is designed for the cases where there is a big amount of key-values to be added in the tree. It has the following characteristics:
17- Parallelizes by available CPUs
18 - If the tree size is not too big (under the configured threshold):
19 - Makes a copy of the tree in memory (*VirtualTree*)
20 - The *VirtualTree* does not compute any hash, only the relations between the nodes of the tree
21 - This step (computing the *VirtualTree*) is done in parallel in each available CPU until level *log2(nCPU)*
22 - Once the *VirtualTree* is updated with all the new leafs (key-values) in each corresponent position, it *computes all the hashes* of each node until the root
23 - In this way, each node hash is computed only once, while when adding many key-values using `tree.Add` method, most of the intermediate nodes will be recalculated each time that a new leaf is added
24 - This step (*computing all the hashes*) is done in parallel in each available CPU
25 - If the tree size is avobe the configured threshold:
26 - Virtually splits the tree in `n` sub-trees, where `n` is the number of available CPUs
27 - Each CPU adds the corresponent new leaves into each sub-tree (working in a db tx)
28 - Once all sub-trees are updated, puts them together again to compute the new tree root
29
30As result, the method `tree.AddBatch` goes way faster thant looping over `tree.Add`, and can compute the tree with parallelization, so as more available CPUs, faster will do the computation.
31
32As an example, this is the benchmark for adding `10k leaves` (with `4 CPU cores`, `AddBatch` would get faster with more CPUs (powers of 2)):
33```
34Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz with 8GB of RAM
35nCPU: 4, nLeafs: 10_000
36
37Using Poseidon hash function:
38(go) arbo.AddBatch: 436.866007ms
39(go) arbo.Add loop: 5.341122678s
40(go) iden3.Add loop: 8.581494317s
41(js) circomlibjs: 2m09.351s
42```
43And, for example, if instead of using Poseidon hash function we use Blake2b, time is reduced to `80.862805ms`.
44
45## Usage
46
47```go
48// import "github.com/arnaucube/arbo/db"
49// import "github.com/arnaucube/arbo/db/pebbledb"
50// create new database
51database, err := pebbledb.New(db.Options{Path: "./data"})
52
53// create new Tree with maxLevels=100 and Blake2b hash function
54tree, err := arbo.NewTree(arbo.Config{
55 Database: database,
56 MaxLevels: 100,
57 HashFunction: arbo.HashFunctionBlake2b,
58})
59
60key := []byte("hello")
61value := []byte("world")
62// Add a key & value into the merkle tree
63err = tree.Add(key, value)
64
65// There are cases where multiple key-values (leafs) are going to be added to a
66// Tree, for these cases is more efficient to use:
67invalids, err := tree.AddBatch(keys, values)
68
69// generate the merkle proof of a leaf by it's key
70value, siblings, err := tree.GenProof(key)
71
72// verify the proof
73verified, err := arbo.CheckProof(tree.hashFunction, key, value, tree.Root(), siblings)
74if !verified {
75 fmt.Println("proof could not be verified")
76}
77
78// get the value of a leaf assigned to a key
79gettedKey, gettedValue, err := tree.Get(key)
80
81// update the value of a leaf assigned to a key
82err = tree.Update(key, value)
83
84// dump the tree (the leafs)
85dump, err := tree.Dump(nil) // instead of nil, a root to start from can be used
86
87// import the dump into a tree
88err = tree.ImportDump(dump)
89
90// print graphviz diagram of the tree
91err = tree.PrintGraphviz(nil) // instead of nil, a root to start from can be used
92```
93
94### Usage with SNARKs compatibility
95Arbo is designed to be compatible with [circom merkle
96tree](https://github.com/iden3/circomlib/tree/master/circuits/smt)'s
97snark-friendly merkletree.
98The only change needed is the hash function used for the Tree, for example using
99the Poseidon hash function:
100```go
101tree, err := arbo.NewTree(database, 32, arbo.HashFunctionPoseidon)
102```
103Be aware of the characteristics of this kind of hashes, such as using values
104inside the finite field used by the hash, and also the computation time.
105
106The interface of arbo uses byte arrays, and for the case of these kind of hashes
107(that usually work directly with finite field elements), arbo expects those
108values to be represented by little-endian byte arrays. There is a helper method
109to convert a `*big.Int` to `[]byte` using little-endian:
110```go
111bLen := tree.HashFunction().Len()
112kBigInt := big.NewInt(100)
113
114// convert *big.Int to byte array
115kBytes := arbo.BigIntToBytes(bLen, kBigInt)
116
117// convert byte array to *big.Int
118kBigInt2 := arbo.BytesToBigInt(kBytes)
119```
120
121
122# Acknowledgements
123This library was originally implemented at https://github.com/vocdoni/arbo . This fork includes the `db` package from https://github.com/vocdoni/davinci-node/tree/main/db .