1# arbo [![GoDoc](https://godoc.org/github.com/vocdoni/arbo?status.svg)](https://godoc.org/github.com/vocdoni/arbo) [![Go Report Card](https://goreportcard.com/badge/github.com/vocdoni/arbo)](https://goreportcard.com/report/github.com/vocdoni/arbo) [![Test](https://github.com/vocdoni/arbo/workflows/Test/badge.svg)](https://github.com/vocdoni/arbo/actions?query=workflow%3ATest)
 2
 3> *arbo*: tree in Esperanto.
 4
 5MerkleTree implementation in Go. Compatible with the circomlib implementation of
 6the MerkleTree, following the specification from
 7https://docs.iden3.io/publications/pdfs/Merkle-Tree.pdf and
 8https://eprint.iacr.org/2018/955.
 9
10Allows to define which hash function to use. So for example, when working with
11zkSnarks the Poseidon hash function can be used, but when not, it can be used
12the Blake2b hash function, which has much faster computation time.
13
14## AddBatch
15The 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:
16
17- Makes a copy of the tree in memory (*VirtualTree*)
18- The *VirtualTree* does not compute any hash, only the relations between the nodes of the tree
19	- This step (computing the *VirtualTree*) is done in parallel in each available CPU until level *log2(nCPU)*
20- 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
21	- 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
22	- This step (*computing all the hashes*) is done in parallel in each available CPU
23
24As 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.
25
26## Usage
27
28```go
29// create new database
30database, err := db.NewBadgerDB(c.TempDir())
31
32// create new Tree with maxLevels=100 and Blake2b hash function
33tree, err := arbo.NewTree(database, 100, arbo.HashFunctionBlake2b)
34
35key := []byte("hello")
36value := []byte("world")
37// Add a key & value into the merkle tree
38err = tree.Add(key, value)
39
40// There are cases where multiple key-values (leafs) are going to be added to a
41// Tree, for these cases is more efficient to use:
42invalids, err := tree.AddBatch(keys, values)
43
44// generate the merkle proof of a leaf by it's key
45value, siblings, err := tree.GenProof(key)
46
47// verify the proof
48verified, err := arbo.CheckProof(tree.hashFunction, key, value, tree.Root(), siblings)
49if !verified {
50	fmt.Println("proof could not be verified")
51}
52
53// get the value of a leaf assigned to a key
54gettedKey, gettedValue, err := tree.Get(key)
55
56// update the value of a leaf assigned to a key
57err = tree.Update(key, value)
58
59// dump the tree (the leafs)
60dump, err := tree.Dump(nil) // instead of nil, a root to start from can be used
61
62// import the dump into a tree
63err = tree.ImportDump(dump)
64
65// print graphviz diagram of the tree
66err = tree.PrintGraphviz(nil) // instead of nil, a root to start from can be used
67```
68
69### Usage with SNARKs compatibility
70Arbo is designed to be compatible with [circom merkle
71tree](https://github.com/iden3/circomlib/tree/master/circuits/smt)'s
72snark-friendly merkletree.
73The only change needed is the hash function used for the Tree, for example using
74the Poseidon hash function:
75```go
76tree, err := arbo.NewTree(database, 32, arbo.HashFunctionPoseidon)
77```
78Be aware of the characteristics of this kind of hashes, such as using values
79inside the finite field used by the hash, and also the computation time.
80
81The interface of arbo uses byte arrays, and for the case of these kind of hashes
82(that usually work directly with finite field elements), arbo expects those
83values to be represented by little-endian byte arrays. There is a helper method
84to convert a `*big.Int` to `[]byte` using little-endian:
85```go
86bLen := tree.HashFunction().Len()
87kBigInt := big.NewInt(100)
88
89// convert *big.Int to byte array
90kBytes := arbo.BigIntToBytes(bLen, kBigInt)
91
92// convert byte array to *big.Int
93kBigInt2 := arbo.BytesToBigInt(kBytes)
94```