merkle

README

go-merkle

A fixed Merkle Tree implementation in Go.

This fork was created to add generating proofs to the library.

Example Use

package main

import (
    "crypto/sha256"
    "io/ioutil"
    "fmt"

    "github.com/contextart/go-merkle"
)

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()
    // 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.NewTreeWithOpts(TreeOptions{EnableHashSorting: true})
    err = tree.Generate(blocks, sha256.New())
    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))
}

Documentation

Overview

Package merkle is a fixed merkle tree implementation

Example (Complete)

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

treeOptions := TreeOptions{
	EnableHashSorting: false,
	DisableHashLeaves: false,
}

tree := NewTreeWithOpts(treeOptions)
err := tree.Generate(items, md5.New())
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

• func CalculateHeightAndNodeCount(leaves uint64) (height, nodeCount uint64)
• type Node
  • func NewNode(h hash.Hash, block []byte) (*Node, error)
• type Tree
  • func NewTree() Tree
  • func NewTreeWithOpts(options TreeOptions) Tree
  • func (tree *Tree) Generate(blocks [][]byte, hashf hash.Hash) error
  • func (tree *Tree) GetNodesAtHeight(h uint64) []*Node
  • func (tree *Tree) GetPathToRootFromNode(node *Node) ([][]byte, error)
  • func (tree *Tree) GetProofForLeafHash(leafHash []byte) ([][]byte, error)
  • func (tree *Tree) Height() uint64
  • func (tree *Tree) Leaves() []*Node
  • func (tree *Tree) Root() *Node
• type TreeOptions

Examples

• Package (Complete)

Functions

func CalculateHeightAndNodeCount

func CalculateHeightAndNodeCount(leaves uint64) (height, nodeCount uint64)

CalculateHeightAndNodeCount returns the height and number of nodes in an unbalanced binary tree given number of leaves

Types

type Node

type Node struct {
	Hash   []byte
	Left   *Node
	Right  *Node
	Parent *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 Tree

type Tree struct {
	// All nodes, linear
	Nodes []*Node
	// Points to each level in the node. The first level contains the root node
	Levels [][]*Node
	// Any particular behavior changing option
	Options TreeOptions
}

Tree contains all nodes

func NewTree

func NewTree() Tree

NewTree creates a Tree with the default options

func NewTreeWithOpts

func NewTreeWithOpts(options TreeOptions) Tree

NewTreeWithOpts creates a Tree with custom options

func (*Tree) Generate

func (tree *Tree) Generate(blocks [][]byte, hashf hash.Hash) error

Generate generates the tree nodes

func (*Tree) GetNodesAtHeight

func (tree *Tree) GetNodesAtHeight(h uint64) []*Node

GetNodesAtHeight returns all nodes at a given height, where height 1 returns a 1-element slice containing the root node, and a height of tree.Height() returns the leaves

func (*Tree) GetPathToRootFromNode

func (tree *Tree) GetPathToRootFromNode(node *Node) ([][]byte, error)

func (*Tree) GetProofForLeafHash

func (tree *Tree) GetProofForLeafHash(leafHash []byte) ([][]byte, error)

func (*Tree) Height

func (tree *Tree) Height() uint64

Height returns the height of this tree

func (*Tree) Leaves

func (tree *Tree) Leaves() []*Node

Leaves returns a slice of the leaf nodes in the tree, if available, else nil

func (*Tree) Root

func (tree *Tree) Root() *Node

Root returns the root node of the tree, if available, else nil

type TreeOptions

type TreeOptions struct {
	// EnableHashSorting modifies the tree's hash behavior to sort the hashes before concatenating them
	// to calculate the parent hash. This removes the capability of proving the position in the tree but
	// simplifies the proof format by removing the need to specify left/right.
	EnableHashSorting bool

	// DisableHashLeaves determines whether leaf nodes should be hashed or not. By doing disabling this behavior,
	// you can use a different hash function for leaves or generate a tree that contains already hashed
	// values. If this is disabled, a length of 32 bytes is enforced for all leaves.
	DisableHashLeaves bool

	// DoubleOddNodes repeats trailing nodes so they become their own
	// left/right pair and are hashed together. The default behavior is to
	// use a null hash as the missing pair.
	DoubleOddNodes bool
}

TreeOptions configures tree behavior