Merkle Tree

Merkletree usage

Import

Import packages:

import (
  "github.com/iden3/go-iden3/db"
  "github.com/iden3/go-iden3/merkletree"
  "github.com/iden3/go-iden3/core"
  common3 "github.com/iden3/go-iden3/common"
)

New Merkletree

Define new tree:

// first we create the storage, where will be placed the leveldb database
storage, err := db.NewLevelDbStorage("./path", false)
if err!=nil {
  panic(err)
}
// new merkletree of 140 levels of maximum depth using the defined
// storage
mt, err := merkletree.NewMerkleTree(storage, 140)
if err!=nil {
  panic(err)
}
defer mt.Storage().Close()

Add claims

To add claims, first we need to have a claim data struct that fits the Entrier interface:

// Data consists of 4 elements of the mimc7 field.
type Data [4]ElemBytes
// An Entry contains Data where the claim will be serialized.
type Entry struct {
  Data Data
  [...]
}
// Entrier is the interface of a generic claim.
type Entrier interface {
  Entry() *Entry
}

We can use a new struct, or also use one of the already existing in the go-iden3/core/claim.go.

For this example, we will use the core.ClaimAssignName. We add two different claims into the merkletree:

name0 := "alice@iden3.io"
ethAddr0 := common.HexToAddress("0x7b471a1bdbd3b8ac98f3715507449f3a8e1f3b22")
claim0 := core.NewClaimAssignName(name0, ethAddr0)
claimEntry0 := claim0.Entry()

name1 := "bob@iden3.io"
ethAddr1 := common.HexToAddress("0x28f8267fb21e8ce0cdd9888a6e532764eb8d52dd")
claim1 := core.NewClaimAssignName(name1, ethAddr1)
claimEntry1 := claim1.Entry()

Once we have the claim struct that fits the Entrier interface, we can add it to the merkletree:

err = mt.Add(claimEntry0)
if err != nil {
  panic(err)
}
err = mt.Add(claimEntry1)
if err != nil {
  panic(err)
}

Generate merkle proof

Now we can generat the merkle proof of this claim:

mp, err := mt.GenerateProof(claimEntry0.HIndex(), nil)
if err != nil {
  panic(err)
}

// We can display the merkleproof:
fmt.Println("merkle proof: ", mp)
// out:
// merkle proof:  Proof:
//         existence: true
//         depth: 2
//         notempties: 01
//         siblings: 0 a045683a

Generate merkle proof for a specific tree (with specific root)

mp, err := mt.GenerateProof(claimEntry0.HIndex(), specificRoot)
if err != nil {
  panic(err)
}

Check merkle proof

Now from a given merkle proof, we can check that it’s data is consistent:

checked := merkletree.VerifyProof(mt.RootKey(), mp,
                  claimEntry0.HIndex(), claimEntry0.HValue())
// checked == true

Get value in position

We can also get the claim byte data in a certain position of the merkle tree (determined by its Hash Index (HIndex)):

claimDataInPos, err := mt.GetDataByIndex(claimEntry0.HIndex())
if err!=nil{
  panic(err)
}

Proof of non existence

Also, we can generate a Proof of non existence, that is, the merkle proof that a claim is not in the tree. For example, we have this claim2 that is not added in the merkletree:

name2 := "eve@iden3.io"
ethAddr2 := common.HexToAddress("0x29a6a240e2d8f8bf39b5338b9664d414c5d793f4")
claim2 := core.NewClaimAssignName(name2, ethAddr2)
claimEntry2 := claim2.Entry()

Now, we can generate the merkle proof of the data in the position of this claim in the merkletree, and print it to see that it’s a non-existence proof:

mp, err = mt.GenerateProof(claimEntry2.HIndex(), nil)
if err != nil {
  panic(err)
}

// We can display the merkleproof:
fmt.Println("merkle proof: ", mp)
// out:
// merkle proof:  Proof:
//         existence: false
//         depth: 2
//         notempties: 01
//         siblings: 0 a045683a
//         node aux: hi: c641b925, ht: eeae8c7e

In the mp we have the merkleproof that in the position of this claim2 (that is determined by its Hash Index (HIndex)) there is no data stored (so, it’s an NodeTypeEmpty not actually stored in the tree).

We can check this proof by calling the VerifyProof function, and in the parameter where we put the Hash Total (HtTotal) we can actually put anything, because we can proof that anything is not there. We will use the Hash Total of the claim2 for convenience.

checked = merkletree.VerifyProof(mt.RootKey(), mp, claimEntry2.HIndex(), claimEntry2.HValue())
// checked == true

Live snapshot of the tree

This option allows to create a read only snapshot of the Merkle Tree, where to perform read actions, while the main tree continues evolving. Basically what it does is to create a new MerkleTree object with the specified Root. Also this Merkle Tree snapshot will not allow to add nodes into it.

snapshot, err := mt.Snapshot(concreteRootKey)
if err!=nil {
    panic(err)
}
// now we can for example, generate proofs for that snapshot of the Merkle Tree
mp, err := snapshot.GenerateProof(claimEntry0.HIndex())
if err != nil {
  panic(err)
}
// and the mp (merkleproof) will be valid for the root of the snapshot

Walk over the Merkle Tree

Walk option allows to iterate through all the branches of a tree with a given RootKey. It allows to give a funcion that will be called inside each node of the tree, returning the a pointer to that Node object.

When calling the Walk function, we can specify a RootKey

We can use a BufferString, that we can use to print to the screen or also into a file all the Leaf nodes:

w := bytes.NewBufferString("")
// mt.Walk(nil, [...] --> as we specify the RootKey as nil, it will use the current mt.RootKey()
err := mt.Walk(nil, func(n *Node) {
    if n.Type == NodeTypeLeaf {
        fmt.Fprintf(w, "node \"%v\"\n", common3.HexEncode(n.Value()))
    }
})
if err != nil {
    panic(err)
}
fmt.Println(w)

Or also we can just print each node inside a switch (also, in this case, we specify a concrete RootKey of the MerkleTree that we want to use):

err := mt.Walk(concreteRootKey, func(n *Node) {
    switch n.Type {
    case NodeTypeEmpty:
        fmt.Println("empty")
    case NodeTypeLeaf:
        fmt.Println("leaf \"%v\"\n", common3.HexEncode(n.Value()))
    case NodeTypeMiddle:
        fmt.Println("node \"%v\"\n", common3.HexEncode(n.Value()))
    default:
        return ErrInvalidNodeFound
    }
})
if err != nil {
    panic(err)
}

Dump all the claims of a MerkleTree

Using this function we can dump all the claims of a MerkleTree, allowing us also to specify a concrete RootKey of the tree that we want to dump. The output generated by this method, can be used from the iden3js library, importing all the dumped claims, allowing to have the same tree from go in javascript.

w := bytes.NewBufferString("")
err := mt.DumpClaims(w, rootKey) // as rootKey we can pass a nil pointer, and it will use the current RootKey
if err!=nil {
    panic(err)
}
fmt.Println(w)

Merkle tree visual representation

Finally, you can get a visual representation of the merkle tree with graphviz, in which only the last bytes of each node key are shown in hexadecimal to make a compact representation. In the following example print the graphviz code for the representation of a merkle tree with 10 claims:

s := bytes.NewBufferString("")
mt2.GraphViz(s, nil)
fmt.Println(s)

GraphViz output code:

digraph hierarchy {
node [fontname=Monospace,fontsize=10,shape=box]
"b0830ca8" -> {"5ae3cb67" "570088ed"}
"5ae3cb67" -> {"6ce2c761" "37b29928"}
"empty0" [style=dashed,label=0];
"6ce2c761" -> {"e82bf1e7" "empty0"}
"e82bf1e7" -> {"6ee500bf" "63289a99"}
"6ee500bf" [style=filled];
"63289a99" [style=filled];
"37b29928" -> {"ef87b970" "8b6e9f1c"}
"ef87b970" -> {"1481190a" "93c79331"}
"1481190a" [style=filled];
"93c79331" [style=filled];
"8b6e9f1c" [style=filled];
"570088ed" -> {"4f3d0101" "8a2524f6"}
"4f3d0101" -> {"74924bbf" "6aa34a3d"}
"74924bbf" [style=filled];
"empty1" [style=dashed,label=0];
"6aa34a3d" -> {"empty1" "69003eca"}
"69003eca" -> {"fac8618d" "43f442c5"}
"fac8618d" [style=filled];
"43f442c5" [style=filled];
"8a2524f6" -> {"3f5e7a5f" "d76c6447"}
"3f5e7a5f" [style=filled];
"d76c6447" [style=filled];
}

The GraphViz visualization looks like this: image0

You can also view the graph using an online graphviz renderer.

Complete example

The complete example can be found in this directory in the file `example.go <https://github.com/iden3/go-iden3/blob/master/merkletreeDoc/example.go>`__.