package module
Version: v0.0.0-...-9c1f4b0 Latest Latest

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

Go to latest
Published: Jul 7, 2019 License: GPL-3.0 Imports: 9 Imported by: 0


go-merkletree Go Report Card Build Status GoDoc

Optimized MerkleTree implementation in Go.

Compatible with Rust version:

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




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


View Source
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}


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


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

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL