merkletree

README

go-merkletree

Optimized MerkleTree implementation in Go.

Compatible with Rust version: https://github.com/arnaucube/merkletree-rs

The MerkleTree is optimized in the design and concepts, to have a faster and lighter MerkleTree, maintaining compatibility with a non optimized MerkleTree. In this way, the MerkleRoot of the optimized MerkleTree will be the same that the MerkleRoot of the non optimized MerkleTree.

This repo is holds the nostalgic (old) version of the MerkleTree implementation that we used in the past in iden3, as now has been substituted by a new specification.

Adding 1000 leafs takes aprox:

• 465.612ms using Keccak256 as hash function
• 317.362ms using SHA256 as hash function

Documentation

Index

• Constants
• Variables
• func BytesToHex(bs []byte) string
• func BytesToUint32(b []byte) uint32
• func CheckProof(root Hash, proof []byte, hi Hash, ht Hash, numLevels int) bool
• func HexToBytes(h string) ([]byte, error)
• func Uint32ToBytes(u uint32) []byte
• type Hash
  • func HashBytes(b []byte) (hash Hash)
  • func (hash Hash) Bytes() []byte
  • func (hash Hash) Hex() string
• type MerkleTree
  • func New(storage *leveldb.DB, numLevels int) (*MerkleTree, error)
  • func (mt *MerkleTree) Add(v Value) error
  • func (mt *MerkleTree) GenerateProof(hi Hash) ([]byte, error)
  • func (mt *MerkleTree) Get(key Hash) (byte, uint32, []byte, error)
  • func (mt *MerkleTree) GetValueInPos(hi Hash) ([]byte, error)
  • func (mt *MerkleTree) Insert(key Hash, nodeType byte, indexLength uint32, nodeBytes []byte) error
  • func (mt *MerkleTree) NumLevels() int
  • func (mt *MerkleTree) PrintFullMT()
  • func (mt *MerkleTree) PrintLevelsMT(maxLevel int)
  • func (mt *MerkleTree) Root() Hash
• type Value

Constants

const (
	// EmptyNodeType indicates the type of an EmptyNodeValue Node
	EmptyNodeType = 00
)

Variables

var (
	// ErrNodeAlreadyExists is an error that indicates that a node already exists in the merkletree database
	ErrNodeAlreadyExists = errors.New("node already exists")

	// EmptyNodeValue is a [32]byte EmptyNodeValue array, all to zero
	EmptyNodeValue = Hash{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
)

Functions

func BytesToHex

func BytesToHex(bs []byte) string

BytesToHex encodes an array of bytes into a string in hex.

func BytesToUint32

func BytesToUint32(b []byte) uint32

BytesToUint32 returns a uint32 from a byte array

func CheckProof

func CheckProof(root Hash, proof []byte, hi Hash, ht Hash, numLevels int) bool

CheckProof validates the Merkle Proof for the leafHash and root

func HexToBytes

func HexToBytes(h string) ([]byte, error)

HexToBytes decodes a hex string into an array of bytes.

func Uint32ToBytes

func Uint32ToBytes(u uint32) []byte

Uint32ToBytes returns a byte array from a uint32

Types

type Hash

type Hash [32]byte

Hash used in this tree, is the [32]byte keccak()

func HashBytes

func HashBytes(b []byte) (hash Hash)

HashBytes performs a Keccak256 hash over the bytes

func (Hash) Bytes

func (hash Hash) Bytes() []byte

Bytes returns a byte array from a Hash

func (Hash) Hex

func (hash Hash) Hex() string

Hex returns a hex string from the Hash type

type MerkleTree

type MerkleTree struct {
	// contains filtered or unexported fields
}

MerkleTree struct with the main elements of the Merkle Tree

func New

func New(storage *leveldb.DB, numLevels int) (*MerkleTree, error)

New generates a new Merkle Tree

func (*MerkleTree) Add

func (mt *MerkleTree) Add(v Value) error

Add adds the leaf to the MT

func (*MerkleTree) GenerateProof

func (mt *MerkleTree) GenerateProof(hi Hash) ([]byte, error)

GenerateProof generates the Merkle Proof from a given leafHash for the current root

func (*MerkleTree) Get

func (mt *MerkleTree) Get(key Hash) (byte, uint32, []byte, error)

func (*MerkleTree) GetValueInPos

func (mt *MerkleTree) GetValueInPos(hi Hash) ([]byte, error)

GetValueInPos returns the merkletree value in the position of the Hash of the Index (Hi)

func (*MerkleTree) Insert

func (mt *MerkleTree) Insert(key Hash, nodeType byte, indexLength uint32, nodeBytes []byte) error

func (*MerkleTree) NumLevels

func (mt *MerkleTree) NumLevels() int

NumLevels returns the merkletree.NumLevels

func (*MerkleTree) PrintFullMT

func (mt *MerkleTree) PrintFullMT()

PrintFullMT prints the tree in the terminal, all the levels with all the nodes

func (*MerkleTree) PrintLevelsMT

func (mt *MerkleTree) PrintLevelsMT(maxLevel int)

PrintLevelsMT prints the tree in the terminal until a specified depth

func (*MerkleTree) Root

func (mt *MerkleTree) Root() Hash

Root returns the merkletree.Root

type Value

type Value interface {
	IndexLength() uint32 // returns the index length value
	Bytes() []byte       // returns the value in byte array representation
}

Value is the interface of a generic leaf, a key value object stored in the leveldb