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## Usage
15
16```go
17// create new database
18database, err := db.NewBadgerDB(c.TempDir())
19
20// create new Tree with maxLevels=100 and Blake2b hash function
21tree, err := arbo.NewTree(database, 100, arbo.HashFunctionBlake2b)
22
23key := []byte("hello")
24value := []byte("world")
25// Add a key & value into the merkle tree
26err = tree.Add(key, value)
27
28// There are cases where multiple key-values (leafs) are going to be added to a
29// Tree, for these cases is more efficient to use:
30invalids, err := tree.AddBatch(keys, values)
31
32// generate the merkle proof of a leaf by it's key
33value, siblings, err := tree.GenProof(key)
34
35// verify the proof
36verified, err := arbo.CheckProof(tree.hashFunction, key, value, tree.Root(), siblings)
37if !verified {
38	fmt.Println("proof could not be verified")
39}
40
41// get the value of a leaf assigned to a key
42gettedKey, gettedValue, err := tree.Get(key)
43
44// update the value of a leaf assigned to a key
45err = tree.Update(key, value)
46
47// dump the tree (the leafs)
48dump, err := tree.Dump(nil) // instead of nil, a root to start from can be used
49
50// import the dump into a tree
51err = tree.ImportDump(dump)
52
53// print graphviz diagram of the tree
54err = tree.PrintGraphviz(nil) // instead of nil, a root to start from can be used
55```
56
57### Usage with SNARKs compatibility
58Arbo is designed to be compatible with [circom merkle
59tree](https://github.com/iden3/circomlib/tree/master/circuits/smt)'s
60snark-friendly merkletree.
61The only change needed is the hash function used for the Tree, for example using
62the Poseidon hash function:
63```go
64tree, err := arbo.NewTree(database, 100, arbo.HashFunctionPoseidon)
65```
66Be aware of the characteristics of this kind of hashes, such as using values
67inside the finite field used by the hash, and also the computation time.
68
69The interface of arbo uses byte arrays, and for the case of these kind of hashes
70(that usually work directly with finite field elements), arbo expects those
71values to be represented by little-endian byte arrays. There is a helper method
72to convert a `*big.Int` to `[]byte` using little-endian:
73```go
74bLen := tree.HashFunction().Len()
75kBigInt := big.NewInt(100)
76
77// convert *big.Int to byte array
78kBytes := arbo.BigIntToBytes(bLen, kBigInt)
79
80// convert byte array to *big.Int
81kBigInt2 := arbo.BytesToBigInt(kBytes)
82```