arbo

package module
v0.0.0-...-f2d5037 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jun 4, 2021 License: GPL-3.0 Imports: 13 Imported by: 0

README

arbo GoDoc Go Report Card Test

arbo: tree in Esperanto.

MerkleTree implementation in Go. Compatible with the circomlib implementation of the MerkleTree, following the specification from https://docs.iden3.io/publications/pdfs/Merkle-Tree.pdf and https://eprint.iacr.org/2018/955.

Allows to define which hash function to use. So for example, when working with zkSnarks the Poseidon hash function can be used, but when not, it can be used the Blake2b hash function, which has much faster computation time.

Usage

// create new database
database, err := db.NewBadgerDB(c.TempDir())

// create new Tree with maxLevels=100 and Blake2b hash function
tree, err := arbo.NewTree(database, 100, arbo.HashFunctionBlake2b)


key := []byte("hello")
value := []byte("world")
err = tree.Add(key, value)


// There are cases where multiple key-values (leafs) are going to be added to a
// Tree, for these cases is more effitient to use:
invalids, err := tree.AddBatch(keys, values)

// generate the merkle proof of a leaf by it's key
value, siblings, err := tree.GenProof(key)

// verify the proof
verified, err := arbo.CheckProof(tree.hashFunction, key, value, tree.Root(), siblings)
if !verified {
	fmt.Println("proof could not be verified")
}

// get the value of a leaf assigned to a key
gettedKey, gettedValue, err := tree.Get(key)

// update the value of a leaf assigned to a key
err = tree.Update(key, value)

// dump the tree (the leafs)
dump, err := tree.Dump(nil) // instead of nil, a root to start from can be used

// import the dump into a tree
err = tree.ImportDump(dump)

// print graphviz diagram of the tree
err = tree.PrintGraphviz(nil) // instead of nil, a root to start from can be used
Usage with SNARKs compatibility

Arbo is designed to be compatible with circom merkle tree's snark-friendly merkletree. The only change needed is the hash function used for the Tree, for example using the Poseidon hash function:

tree, err := arbo.NewTree(database, 100, arbo.HashFunctionPoseidon)

Be aware of the characteristics of this kind of hashes, such as using values inside the finite field used by the hash, and also the computation time.

The interface of arbo uses byte arrays, and for the case of these kind of hashes (that usually work directly with finite field elements), arbo expects those values to be represented by little-endian byte arrays. There is a helper method to convert a *big.Int to []byte using little-endian:

bLen := tree.HashFunction().Len()
kBigInt := big.NewInt(100)

// convert *big.Int to byte array
kBytes := arbo.BigIntToBytes(bLen, kBigInt)

// convert byte array to *big.Int
kBigInt2 := arbo.BytesToBigInt(kBytes)

Documentation

Overview

Package arbo implements a Merkle Tree compatible with the circomlib implementation of the MerkleTree, following the specification from https://docs.iden3.io/publications/pdfs/Merkle-Tree.pdf and https://eprint.iacr.org/2018/955.

Allows to define which hash function to use. So for example, when working with zkSnarks the Poseidon hash function can be used, but when not, it can be used the Blake2b hash function, which has much faster computation time.

Package arbo > vt.go implements the Virtual Tree, which computes a tree without computing any hash. With the idea of once all the leafs are placed in their positions, the hashes can be computed, avoiding computing a node hash more than one time.

Index

Constants

View Source 
const (
	// PrefixValueLen defines the bytes-prefix length used for the Value
	// bytes representation stored in the db
	PrefixValueLen = 2

	// PrefixValueEmpty is used for the first byte of a Value to indicate
	// that is an Empty value
	PrefixValueEmpty = 0
	// PrefixValueLeaf is used for the first byte of a Value to indicate
	// that is a Leaf value
	PrefixValueLeaf = 1
	// PrefixValueIntermediate is used for the first byte of a Value to
	// indicate that is a Intermediate value
	PrefixValueIntermediate = 2
)

Variables

View Source 
var (
	// TypeHashSha256 represents the label for the HashFunction of Sha256
	TypeHashSha256 = []byte("sha256")
	// TypeHashPoseidon represents the label for the HashFunction of
	// Poseidon
	TypeHashPoseidon = []byte("poseidon")
	// TypeHashBlake2b represents the label for the HashFunction of Blake2b
	TypeHashBlake2b = []byte("blake2b")

	// HashFunctionSha256 contains the HashSha256 struct which implements
	// the HashFunction interface
	HashFunctionSha256 HashSha256
	// HashFunctionPoseidon contains the HashPoseidon struct which implements
	// the HashFunction interface
	HashFunctionPoseidon HashPoseidon
	// HashFunctionBlake2b contains the HashBlake2b struct which implements
	// the HashFunction interface
	HashFunctionBlake2b HashBlake2b
)
View Source 
var (

	// ErrKeyNotFound is used when a key is not found in the db neither in
	// the current db Batch.
	ErrKeyNotFound = fmt.Errorf("key not found")
	// ErrKeyAlreadyExists is used when trying to add a key as leaf to the
	// tree that already exists.
	ErrKeyAlreadyExists = fmt.Errorf("key already exists")
	// ErrInvalidValuePrefix is used when going down into the tree, a value
	// is read from the db and has an unrecognized prefix.
	ErrInvalidValuePrefix = fmt.Errorf("invalid value prefix")
	// ErrDBNoTx is used when trying to use Tree.dbPut but Tree.dbBatch==nil
	ErrDBNoTx = fmt.Errorf("dbPut error: no db Batch")
	// ErrMaxLevel indicates when going down into the tree, the max level is
	// reached
	ErrMaxLevel = fmt.Errorf("max level reached")
	// ErrMaxVirtualLevel indicates when going down into the tree, the max
	// virtual level is reached
	ErrMaxVirtualLevel = fmt.Errorf("max virtual level reached")
)

Functions

func BigIntToBytes 

func BigIntToBytes(blen int, bi *big.Int) []byte

BigIntToBytes converts a *big.Int into a byte array in Little-Endian

func BytesToBigInt 

func BytesToBigInt(b []byte) *big.Int

BytesToBigInt converts a byte array in Little-Endian representation into *big.Int

func CheckProof 

func CheckProof(hashFunc HashFunction, k, v, root, packedSiblings []byte) (bool, error)

CheckProof verifies the given proof. The proof verification depends on the HashFunction passed as parameter.

func PackSiblings 

func PackSiblings(hashFunc HashFunction, siblings [][]byte) []byte

PackSiblings packs the siblings into a byte array. [ 1 byte | L bytes | S * N bytes ] [ bitmap length (L) | bitmap | N non-zero siblings ] Where the bitmap indicates if the sibling is 0 or a value from the siblings array. And S is the size of the output of the hash function used for the Tree.

func ReadIntermediateChilds 

func ReadIntermediateChilds(b []byte) ([]byte, []byte)

ReadIntermediateChilds reads from a byte array the two childs keys

func ReadLeafValue 

func ReadLeafValue(b []byte) ([]byte, []byte)

ReadLeafValue reads from a byte array the leaf key & value

func SwapEndianness 

func SwapEndianness(b []byte) []byte

SwapEndianness swaps the order of the bytes in the byte slice.

func UnpackSiblings 

func UnpackSiblings(hashFunc HashFunction, b []byte) ([][]byte, error)

UnpackSiblings unpacks the siblings from a byte array.

Types

type HashBlake2b 

type HashBlake2b struct{}

HashBlake2b implements the HashFunction interface for the Blake2b hash

func (HashBlake2b) Hash 

func (f HashBlake2b) Hash(b ...[]byte) ([]byte, error)

Hash implements the hash method for the HashFunction HashBlake2b

func (HashBlake2b) Len 

func (f HashBlake2b) Len() int

Len returns the length of the Hash output

func (HashBlake2b) Type 

func (f HashBlake2b) Type() []byte

Type returns the type of HashFunction for the HashBlake2b

type HashFunction 

type HashFunction interface {
	Type() []byte
	Len() int
	Hash(...[]byte) ([]byte, error)
}

HashFunction defines the interface that is expected for a hash function to be used in a generic way in the Tree.

type HashPoseidon 

type HashPoseidon struct{}

HashPoseidon implements the HashFunction interface for the Poseidon hash

func (HashPoseidon) Hash 

func (f HashPoseidon) Hash(b ...[]byte) ([]byte, error)

Hash implements the hash method for the HashFunction HashPoseidon

func (HashPoseidon) Len 

func (f HashPoseidon) Len() int

Len returns the length of the Hash output

func (HashPoseidon) Type 

func (f HashPoseidon) Type() []byte

Type returns the type of HashFunction for the HashPoseidon

type HashSha256 

type HashSha256 struct{}

HashSha256 implements the HashFunction interface for the Sha256 hash

func (HashSha256) Hash 

func (f HashSha256) Hash(b ...[]byte) ([]byte, error)

Hash implements the hash method for the HashFunction HashSha256

func (HashSha256) Len 

func (f HashSha256) Len() int

Len returns the length of the Hash output

func (HashSha256) Type 

func (f HashSha256) Type() []byte

Type returns the type of HashFunction for the HashSha256

type Tree 

type Tree struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

Tree defines the struct that implements the MerkleTree functionalities

func NewTree 

func NewTree(database db.Database, maxLevels int, hash HashFunction) (*Tree, error)

NewTree returns a new Tree, if there is a Tree still in the given database, it will load it.

func (*Tree) Add 

func (t *Tree) Add(k, v []byte) error

Add inserts the key-value into the Tree. If the inputs come from a *big.Int, is expected that are represented by a Little-Endian byte array (for circom compatibility).

func (*Tree) AddBatch 

func (t *Tree) AddBatch(keys, values [][]byte) ([]int, error)

AddBatch adds a batch of key-values to the Tree. Returns an array containing the indexes of the keys failed to add.

func (*Tree) Dump 

func (t *Tree) Dump(rootKey []byte) ([]byte, error)

Dump exports all the Tree leafs in a byte array of length: [ N * (2+len(k+v)) ]. Where N is the number of key-values, and for each k+v: [ 1 byte | 1 byte | S bytes | len(v) bytes ] [ len(k) | len(v) | key | value ] Where S is the size of the output of the hash function used for the Tree.

func (*Tree) GenProof 

func (t *Tree) GenProof(k []byte) ([]byte, []byte, error)

GenProof generates a MerkleTree proof for the given key. If the key exists in the Tree, the proof will be of existence, if the key does not exist in the tree, the proof will be of non-existence.

func (*Tree) Get 

func (t *Tree) Get(k []byte) ([]byte, []byte, error)

Get returns the value for a given key

func (*Tree) GetNLeafs 

func (t *Tree) GetNLeafs() (int, error)

GetNLeafs returns the number of Leafs of the Tree.

func (*Tree) Graphviz 

func (t *Tree) Graphviz(w io.Writer, rootKey []byte) error

Graphviz iterates across the full tree to generate a string Graphviz representation of the tree and writes it to w

func (*Tree) GraphvizFirstNLevels 

func (t *Tree) GraphvizFirstNLevels(w io.Writer, rootKey []byte, untilLvl int) error

GraphvizFirstNLevels iterates across the first NLevels of the tree to generate a string Graphviz representation of the first NLevels of the tree and writes it to w

func (*Tree) HashFunction 

func (t *Tree) HashFunction() HashFunction

HashFunction returns Tree.hashFunction

func (*Tree) ImportDump 

func (t *Tree) ImportDump(b []byte) error

ImportDump imports the leafs (that have been exported with the ExportLeafs method) in the Tree.

func (*Tree) Iterate 

func (t *Tree) Iterate(rootKey []byte, f func([]byte, []byte)) error

Iterate iterates through the full Tree, executing the given function on each node of the Tree.

func (*Tree) IterateWithStop 

func (t *Tree) IterateWithStop(rootKey []byte, f func(int, []byte, []byte) bool) error

IterateWithStop does the same than Iterate, but with int for the current level, and a boolean parameter used by the passed function, is to indicate to stop iterating on the branch when the method returns 'true'.

func (*Tree) PrintGraphviz 

func (t *Tree) PrintGraphviz(rootKey []byte) error

PrintGraphviz prints the output of Tree.Graphviz

func (*Tree) PrintGraphvizFirstNLevels 

func (t *Tree) PrintGraphvizFirstNLevels(rootKey []byte, untilLvl int) error

PrintGraphvizFirstNLevels prints the output of Tree.GraphvizFirstNLevels

func (*Tree) Root 

func (t *Tree) Root() []byte

Root returns the root of the Tree

func (*Tree) Update 

func (t *Tree) Update(k, v []byte) error

Update updates the value for a given existing key. If the given key does not exist, returns an error.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.