merkletree

README

Merkle Tree in Golang

An implementation of a Merkle Tree written in Go. A Merkle Tree is a hash tree that provides an efficient way to verify the contents of a set data are present and untampered with.

At its core, a Merkle Tree is a list of items representing the data that should be verified. Each of these items is inserted into a leaf node and a tree of hashes is constructed bottom up using a hash of the nodes left and right children's hashes. This means that the root node will effictively be a hash of all other nodes (hashes) in the tree. This property allows the tree to be reproduced and thus verified by on the hash of the root node of the tree. The benefit of the tree structure is verifying any single content entry in the tree will require only nlog2(n) steps in the worst case.

Documentation

See the docs here.

Install

go get github.com/cbergoon/merkletree

Example Usage

Below is an example that makes use of the entire API - its quite small.

package main

import (
  "crypto/sha256"
  "log"

  "github.com/cbergoon/merkletree"
)

//TestContent implements the Content interface provided by merkletree and represents the content stored in the tree.
type TestContent struct {
  x string
}

//CalculateHash hashes the values of a TestContent
func (t TestContent) CalculateHash() ([]byte, error) {
  h := sha256.New()
  if _, err := h.Write([]byte(t.x)); err != nil {
    return nil, err
  }

  return h.Sum(nil), nil
}

//Equals tests for equality of two Contents
func (t TestContent) Equals(other merkletree.Content) (bool, error) {
  return t.x == other.(TestContent).x, nil
}

func main() {
  //Build list of Content to build tree
  var list []merkletree.Content
  list = append(list, TestContent{x: "Hello"})
  list = append(list, TestContent{x: "Hi"})
  list = append(list, TestContent{x: "Hey"})
  list = append(list, TestContent{x: "Hola"})

  //Create a new Merkle Tree from the list of Content
  t, err := merkletree.NewTree(list)
  if err != nil {
    log.Fatal(err)
  }

  //Get the Merkle Root of the tree
  mr := t.MerkleRoot()
  log.Println(mr)

  //Verify the entire tree (hashes for each node) is valid
  vt, err := t.VerifyTree()
  if err != nil {
    log.Fatal(err)
  }
  log.Println("Verify Tree: ", vt)

  //Verify a specific content in in the tree
  vc, err := t.VerifyContent(list[0])
  if err != nil {
    log.Fatal(err)
  }

  log.Println("Verify Content: ", vc)

  //String representation
  log.Println(t)
}

Sample

License

This project is licensed under the MIT License.

Documentation

Overview

Package merkletree implements a Merkle Tree capable of storing arbitrary content.

A Merkle Tree is a hash tree that provides an efficient way to verify the contents of a set data are present and untampered with. At its core, a Merkle Tree is a list of items representing the data that should be verified. Each of these items is inserted into a leaf node and a tree of hashes is constructed bottom up using a hash of the nodes left and right children's hashes. This means that the root node will effictively be a hash of all other nodes (hashes) in the tree. This property allows the tree to be reproduced and thus verified by on the hash of the root node of the tree. The benefit of the tree structure is verifying any single content entry in the tree will require only nlog2(n) steps in the worst case.

Creating a new merkletree requires that the type that the tree will be constructed from implements the Content interface.

type Content interface {
	CalculateHash() []byte
	Equals(other Content) bool
}

A slice of the Content items should be created and then passed to the NewTree method.

t, err := merkle.NewTree(list)

t represents the Merkle Tree and can be verified and manipulated with the API methods described below.

Index

• func DeleteLinks(n *Node)
• func RestoreLinks(n *Node, par *Node, mt *MerkleTree)
• type Content
• type MerkleTree
  • func NewTree(cs []Content) (*MerkleTree, error)
  • func NewTreeWithHashStrategy(cs []Content, hashStrategy func() hash.Hash) (*MerkleTree, error)
  • func (m *MerkleTree) GetMerklePath(content Content) ([][]byte, []int64, error)
  • func (m *MerkleTree) MerkleRoot() []byte
  • func (m *MerkleTree) PrepareForMarshalling()
  • func (m *MerkleTree) RebuildTree() error
  • func (m *MerkleTree) RebuildTreeWith(cs []Content) error
  • func (m *MerkleTree) RestoreAfterMarshalling()
  • func (m *MerkleTree) String() string
  • func (m *MerkleTree) VerifyContent(content Content) (bool, error)
  • func (m *MerkleTree) VerifyTree() (bool, error)
• type Node
  • func (n *Node) String() string

Functions

func DeleteLinks

func DeleteLinks(n *Node)

func RestoreLinks

func RestoreLinks(n *Node, par *Node, mt *MerkleTree)

Types

type Content

type Content interface {
	CalculateHash() ([]byte, error)
	Equals(other Content) (bool, error)
}

Content represents the data that is stored and verified by the tree. A type that implements this interface can be used as an item in the tree.

type MerkleTree

type MerkleTree struct {
	Root               *Node
	MerkleRootInternal []byte
	Leafs              []*Node
	HashStrategy       func() hash.Hash
}

MerkleTree is the container for the tree. It holds a pointer to the root of the tree, a list of pointers to the Leaf nodes, and the merkle root.

func NewTree

func NewTree(cs []Content) (*MerkleTree, error)

NewTree creates a new Merkle Tree using the content cs.

func NewTreeWithHashStrategy

func NewTreeWithHashStrategy(cs []Content, hashStrategy func() hash.Hash) (*MerkleTree, error)

NewTreeWithHashStrategy creates a new Merkle Tree using the content cs using the provided hash strategy. Note that the hash type used in the type that implements the Content interface must match the hash type profided to the tree.

func (*MerkleTree) GetMerklePath

func (m *MerkleTree) GetMerklePath(content Content) ([][]byte, []int64, error)

GetMerklePath: Get Merkle path and indexes(left Leaf or right Leaf)

func (*MerkleTree) MerkleRoot

func (m *MerkleTree) MerkleRoot() []byte

MerkleRoot returns the unverified Merkle Root (hash of the root node) of the tree.

func (*MerkleTree) PrepareForMarshalling

func (m *MerkleTree) PrepareForMarshalling()

func (*MerkleTree) RebuildTree

func (m *MerkleTree) RebuildTree() error

RebuildTree is a helper function that will rebuild the tree reusing only the content that it holds in the leaves.

func (*MerkleTree) RebuildTreeWith

func (m *MerkleTree) RebuildTreeWith(cs []Content) error

RebuildTreeWith replaces the content of the tree and does a complete rebuild; while the root of the tree will be replaced the MerkleTree completely survives this operation. Returns an error if the list of content cs contains no entries.

func (*MerkleTree) RestoreAfterMarshalling

func (m *MerkleTree) RestoreAfterMarshalling()

func (*MerkleTree) String

func (m *MerkleTree) String() string

String returns a string representation of the tree. Only Leaf nodes are included in the output.

func (*MerkleTree) VerifyContent

func (m *MerkleTree) VerifyContent(content Content) (bool, error)

VerifyContent indicates whether a given content is in the tree and the hashes are valid for that content. Returns true if the expected Merkle Root is equivalent to the Merkle root calculated on the critical path for a given content. Returns true if valid and false otherwise.

func (*MerkleTree) VerifyTree

func (m *MerkleTree) VerifyTree() (bool, error)

VerifyTree verify tree validates the hashes at each level of the tree and returns true if the resulting hash at the root of the tree matches the resulting root hash; returns false otherwise.

type Node

type Node struct {
	Tree   *MerkleTree
	Parent *Node
	Left   *Node
	Right  *Node
	Leaf   bool
	Dup    bool
	Hash   []byte
	C      Content
}

Node represents a node, root, or Leaf in the tree. It stores pointers to its immediate relationships, a hash, the content stored if it is a Leaf, and other metadata.

func (*Node) String

func (n *Node) String() string

String returns a string representation of the node.