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