gomerkletree

README

go-merkletree

Golang's implementation of Incremental Binary Merkletree. To learn what is it, please visit Semaphore doc page: incremental Merkle tree.

Also, Semaphore is a good example of Merkletree usage.

Importing

In order to use it in your Go's project, import it using:

go get -u github.com/jeffprestes/gomerkletree

Usage

Look for the examples at merkletree_test.go file

Testing

To test run:

   go test ./ -v 

Documentation

Index

• Variables
• func BigIntFromString(str string) (newint *big.Int)
• func CreateBlakeHash(byteStr []byte) []byte
• func EncodeToBigInt(data []byte) (encodedData *big.Int)
• func HashCalculator(a, b *big.Int) (hash *big.Int)
• func IsRootMatch(str, treeRoot string) bool
• type DatabaseLeaf
  • func NewDatabaseLeaf(index uint64, leafData []byte, leafEncoded *big.Int) (obj DatabaseLeaf)
• type MerkleStructure
  • func NewMerkletree(depth int, zero *big.Int, printLog bool) (tree MerkleStructure)
  • func (tree *MerkleStructure) ComputeEmptyNodes()
  • func (tree *MerkleStructure) FindItem(leafData []byte) (index uint64)
  • func (tree *MerkleStructure) GenerateProof(index uint64) (path []uint8, siblings []*big.Int, root *big.Int, err error)
  • func (tree *MerkleStructure) InsertLeaf(leafData []byte) (leafDb DatabaseLeaf)
  • func (tree *MerkleStructure) ToString() (stats string)
  • func (tree *MerkleStructure) UpdateLeaf(leafData []byte, index uint64, path []uint8, siblings []*big.Int) (leafDb DatabaseLeaf)
  • func (tree *MerkleStructure) VerifyProof(leafData []byte, path []uint8, siblings []*big.Int, root *big.Int) (bool, *big.Int, *big.Int)

Variables

var HugeData = []byte("0x61089b610026600b82828239805160001a60731461001957fe5b30600052607381538281f3fe730000000000000000000000000000000000000000301460806040526004361061004b5760003560e01c806304433bbc14610050578063534e785c14610081578063f21de1e8146100be575b600080fd5b61006a60048036038101906100659190610541565b6100dd565b6040516100789291906106a6565b60405180910390f35b81801561008d57600080fd5b506100a860048036038101906100a39190610586565b6101ee565b6040516100b5919061068b565b60405180910390f35b6100c66103ea565b6040516100d49291906106a6565b60405180910390f35b6000806000806100eb6103ea565b9150915081610102576000809350935050506101e7565b600081905060008173ffffffffffffffffffffffffffffffffffffffff1663a667817789896040518363ffffffff1660e01b81526004016101449291906106f8565b60206040518083038186803b15801561015c57600080fd5b505afa158015610170573d6000803e3d6000fd5b505050506040513d601f19601f8201168201806040525081019061019491906104ef565b9050600073ffffffffffffffffffffffffffffffffffffffff168173ffffffffffffffffffffffffffffffffffffffff1614156101db5760008095509550505050506101e7565b60018195509550505050505b9250929050565b60008060006101fb6103ea565b915091508161020f576000925050506103e4565b7f885cb69240a935d632d79c317109709ecfa91a80626ff3989d68f67f5b1dd12d60001c73ffffffffffffffffffffffffffffffffffffffff16637fb5297f6040518163ffffffff1660e01b8152600401600060405180830381600087803b15801561027a57600080fd5b505af115801561028e573d6000803e3d6000fd5b50505050600081905060006002876040516102a99190610674565b602060405180830381855afa1580156102c6573d6000803e3d6000fd5b5050506040513d601f19601f820116820180604052508101906102e99190610518565b90508173ffffffffffffffffffffffffffffffffffffffff16635188f99682886040518363ffffffff1660e01b81526004016103269291906106cf565b600060405180830381600087803b15801561034057600080fd5b505af1158015610354573d6000803e3d6000fd5b505050507f885cb69240a935d632d79c317109709ecfa91a80626ff3989d68f67f5b1dd12d60001c73ffffffffffffffffffffffffffffffffffffffff166376eadd366040518163ffffffff1660e01b8152600401600060405180830381600087803b1580156103c357600080fd5b505af11580156103d7573d6000803e3d6000fd5b5050505060019450505050505b92915050565b60008060007370607478afc46410fd4401f3847a4848e661e457905060018192509250509091565b60008135905061042181610837565b92915050565b60008151905061043681610837565b92915050565b60008151905061044b8161084e565b92915050565b60008083601f84011261046357600080fd5b8235905067ffffffffffffffff81111561047c57600080fd5b60208301915083600182028301111561049457600080fd5b9250929050565b600082601f8301126104ac57600080fd5b81356104bf6104ba82610749565b61071c565b915080825260208301602083018583830111156104db57600080fd5b6104e68382846107e4565b50505092915050565b60006020828403121561050157600080fd5b600061050f84828501610427565b91505092915050565b60006020828403121561052a57600080fd5b60006105388482850161043c565b91505092915050565b6000806020838503121561055457600080fd5b600083013567ffffffffffffffff81111561056e57600080fd5b61057a85828601610451565b92509250509250929050565b6000806040838503121561059957600080fd5b600083013567ffffffffffffffff8111156105b357600080fd5b6105bf8582860161049b565b92505060206105d085828601610412565b9150509250929050565b6105e38161079c565b82525050565b6105f28161079c565b82525050565b610601816107ae565b82525050565b610610816107ba565b82525050565b600061062182610775565b61062b8185610780565b935061063b8185602086016107f3565b80840191505092915050565b6000610653838561078b565b93506106608385846107e4565b61066983610826565b840190509392505050565b60006106808284610616565b915081905092915050565b60006020820190506106a060008301846105f8565b92915050565b60006040820190506106bb60008301856105f8565b6106c860208301846105e9565b9392505050565b60006040820190506106e46000830185610607565b6106f160208301846105da565b9392505050565b60006020820190508181036000830152610713818486610647565b90509392505050565b6000604051905081810181811067ffffffffffffffff8211171561073f57600080fd5b8060405250919050565b600067ffffffffffffffff82111561076057600080fd5b601f19601f8301169050602081019050919050565b600081519050919050565b600081905092915050565b600082825260208201905092915050565b60006107a7826107c4565b9050919050565b60008115159050919050565b6000819050919050565b600073ffffffffffffffffffffffffffffffffffffffff82169050919050565b82818337600083830152505050565b60005b838110156108115780820151818401526020810190506107f6565b83811115610820576000848401525b50505050565b6000601f19601f8301169050919050565b6108408161079c565b811461084b57600080fd5b50565b610857816107ba565b811461086257600080fd5b5056fea2646970667358221220a7451184daf9cf1afbba15395390a96db3af3bb092cc89446dc6d110c51125bc64736f6c634300060c0033")

Functions

func BigIntFromString

func BigIntFromString(str string) (newint *big.Int)

func CreateBlakeHash

func CreateBlakeHash(byteStr []byte) []byte

func EncodeToBigInt

func EncodeToBigInt(data []byte) (encodedData *big.Int)

func HashCalculator

func HashCalculator(a, b *big.Int) (hash *big.Int)

HashCalculator optmistc poseidon hash calculator.

func IsRootMatch

func IsRootMatch(str, treeRoot string) bool

Types

type DatabaseLeaf

type DatabaseLeaf struct {
	gorm.Model
	LeafIndex   uint64 `gorm:"index:idx_leaf_index,unique"`
	LeafData    []byte
	LeafEncoded *big.Int
}

func NewDatabaseLeaf

func NewDatabaseLeaf(index uint64, leafData []byte, leafEncoded *big.Int) (obj DatabaseLeaf)

type MerkleStructure

type MerkleStructure struct {
	Depth         int
	Root          *big.Int
	LastLeafIndex uint64 // index of the leaf in its original array or list before being
	LastLeaf      *big.Int
	Zero          *big.Int
	Siblings      []*big.Int
	// FilledNodes: Last value filled in a layer of the tree
	// see: https://github.com/privacy-scaling-explorations/zk-kit/blob/f9b209d6006fd454fc464bbd7e1ad3cfab6389d0/packages/incremental-merkle-tree.sol/contracts/IncrementalBinaryTree.sol#L14
	FilledNodes []*big.Int
	EmptyNodes  []*big.Int
	Leaves      map[uint64]*big.Int
	PrintLog    bool
}

func NewMerkletree

func NewMerkletree(depth int, zero *big.Int, printLog bool) (tree MerkleStructure)

func (*MerkleStructure) ComputeEmptyNodes

func (tree *MerkleStructure) ComputeEmptyNodes()

func (*MerkleStructure) FindItem

func (tree *MerkleStructure) FindItem(leafData []byte) (index uint64)

TODO: Implement find element method https://pkg.go.dev/slices@master#example-BinarySearch

func (*MerkleStructure) GenerateProof

func (tree *MerkleStructure) GenerateProof(index uint64) (path []uint8, siblings []*big.Int, root *big.Int, err error)

func (*MerkleStructure) InsertLeaf

func (tree *MerkleStructure) InsertLeaf(leafData []byte) (leafDb DatabaseLeaf)

func (*MerkleStructure) ToString

func (tree *MerkleStructure) ToString() (stats string)

func (*MerkleStructure) UpdateLeaf

func (tree *MerkleStructure) UpdateLeaf(leafData []byte, index uint64, path []uint8, siblings []*big.Int) (leafDb DatabaseLeaf)

TODO: Implement UpdateLeaf https://github.com/privacy-scaling-explorations/zk-kit/blob/f9b209d6006fd454fc464bbd7e1ad3cfab6389d0/packages/incremental-merkle-tree.sol/contracts/IncrementalBinaryTree.sol#L171

func (*MerkleStructure) VerifyProof

func (tree *MerkleStructure) VerifyProof(leafData []byte, path []uint8, siblings []*big.Int, root *big.Int) (bool, *big.Int, *big.Int)