README

go-merkle

GoDoc Travis CI

A fixed Merkle Tree implementation in Go

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()
    // 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, 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))
}

Expand ▾ Collapse ▴

Documentation

Overview

    Package merkle is a fixed merkle tree implementation

    Example (Complete)
    Output:
    
    

    Index

    Examples

    Constants

    This section is empty.

    Variables

    This section is empty.

    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
      }

        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) 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

                            Source Files