merkle

README

go-merkle

This library implements a standard Merkle Tree in Go and also provides a sparse Merkle tree implementation. The SMT implementaiton only allows full leaves on the left and will arrange all empty leaves in rightmost positions. The total leaf count must be a power of 2.

Example Use

package main

import (
    "crypto/md5"
    "fmt"
    "github.com/xsleonard/go-merkle"
    "io/ioutil"
)

func splitData(data []byte, size int) [][]byte {
    /* Splits data into an array of slices of len(size) */
    count := len(data) / size
    blocks := make([][]byte, 0, count)
    for i := 0; i < count; i++ {
        block := data[i*size : (i+1)*size]
        blocks = append(blocks, block)
    }
    if len(data)%size != 0 {
        blocks = append(blocks, data[len(blocks)*size:])
    }
    return blocks
}

func main() {
    // Grab some data to make the tree out of, and partition
    data, err := ioutil.ReadFile("testdata") // assume testdata exists
    if err != nil {
        fmt.Println(err)
        return
    }
    blocks := splitData(data, 32)

    // Create & generate the tree
    tree := merkle.NewTree(md5.New())
    // Create & generate the tree with sorted hashes
    // A tree with pair wise sorted hashes allows for a representation of proofs which are more space efficient
    // tree := merkle.NewTreeWithHashSortingEnable(md5.New())
    err = tree.Generate(blocks, 0)
    if err != nil {
        fmt.Println(err)
        return
    }

    proof, err := tree.GetMerkleProof(0)
        if err != nil {
        fmt.Println(err)
        return
    }

    fmt.Printf("Root Hash: %v\n", tree.RootHash())
    fmt.Prinff("Proof of first leaf: %v\n", proof)


    // Create & generate sparse tree
    hashFunc := md5.New()
    _, err := hashFunc.Write([]byte{})
    if err != nil {
        fmt.Println(err)
        return
    }
    emptyLeafHash := h.Sum(nil)
    tree := merkle.NewSMT(emptyLeafHash, md5.New())

    err = tree.Generate(blocks, 64)
    if err != nil {
        fmt.Println(err)
        return
    }

    proof, err := tree.GetMerkleProof(0)
        if err != nil {
        fmt.Println(err)
        return
    }

    fmt.Printf("Root Hash: %v\n", tree.RootHash())
    fmt.Prinff("Proof of first leaf: %v\n", proof)
}

Documentation

Overview

Package merkle is a fixed merkle tree implementation

Example (Complete)

items := [][]byte{[]byte("alpha"), []byte("beta"), []byte("gamma"), []byte("delta"), []byte("epsilon")}

tree := NewTree(md5.New())
err := tree.generate(items)
if err != nil {
	fmt.Println(err)
	return
}

fmt.Printf("Height: %d\n", tree.height())
fmt.Printf("Root: %v\n", tree.root())
fmt.Printf("N Leaves: %v\n", len(tree.leaves()))
fmt.Printf("Height 2: %v\n", tree.getNodesAtHeight(2))

Index

• type Hash
• type MerkleTree
• type Node
  • func NewNode(h hash.Hash, block []byte) (Node, error)
• type ProofNode
• type SMT
  • func NewSMT(emptyHash Hash, hashFunc hash.Hash) *SMT
  • func (self *SMT) Generate(leaves [][]byte, totalSize int) error
  • func (self *SMT) GetMerkleProof(leafNo uint) ([]ProofNode, error)
  • func (self *SMT) RootHash() []byte
• type Tree
  • func NewTree(hashFunc hash.Hash) *Tree
  • func NewTreeWithHashSortingEnable(hashFunc hash.Hash) *Tree
  • func (self *Tree) Generate(blocks [][]byte, totalLeavesSize int) error
  • func (self *Tree) GetMerkleProof(leafIndex uint) ([]ProofNode, error)
  • func (self *Tree) RootHash() []byte

Examples

• Package (Complete)

Types

type Hash

type Hash []byte

type MerkleTree

type MerkleTree interface {
	Generate(leaves [][]byte, totalLeavesSize int) error
	RootHash() []byte
	GetMerkleProof(leafIndex uint) ([]ProofNode, error)
}

type Node

type Node struct {
	Hash  []byte
	Left  *Node
	Right *Node
}

Node in the merkle tree

func NewNode

func NewNode(h hash.Hash, block []byte) (Node, error)

NewNode creates a node given a hash function and data to hash. If the hash function is nil, the data will be added without being hashed.

type ProofNode

type ProofNode struct {
	Left bool
	Hash []byte
}

type SMT

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

A Sparse Merkle Tree which support all empty leaves lies in right

func NewSMT

func NewSMT(emptyHash Hash, hashFunc hash.Hash) *SMT

func (*SMT) Generate

func (self *SMT) Generate(leaves [][]byte, totalSize int) error

func (*SMT) GetMerkleProof

func (self *SMT) GetMerkleProof(leafNo uint) ([]ProofNode, error)

Leaf mumber begins with 0

func (*SMT) RootHash

func (self *SMT) RootHash() []byte

type Tree

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

Tree contains all nodes

func NewTree

func NewTree(hashFunc hash.Hash) *Tree

func NewTreeWithHashSortingEnable

func NewTreeWithHashSortingEnable(hashFunc hash.Hash) *Tree

func (*Tree) Generate

func (self *Tree) Generate(blocks [][]byte, totalLeavesSize int) error

Generates the tree nodes by using different hash funtions between internal and leaf node

func (*Tree) GetMerkleProof

func (self *Tree) GetMerkleProof(leafIndex uint) ([]ProofNode, error)

func (*Tree) RootHash

func (self *Tree) RootHash() []byte