merkletree

README

go-merkletree

Go implementation of a Merkle tree.

Table of Contents

• Install
• Usage
• Maintainers
• Contribute
• License

Install

go-merkletree is a standard Go module which can be installed with:

go get github.com/wealdtech/go-merkletree

Usage

Example

Maintainers

Jim McDonald: @mcdee.

Contribute

Contributions welcome. Please check out the issues.

License

Apache-2.0 © 2019 Weald Technology Trading Ltd

Documentation

Overview

Package merkletree is an implementation of a Merkle tree (https://en.wikipedia.org/wiki/Merkle_tree). It provides methods to create a tree and generate and verify proofs. The hashing algorithm for the tree is selectable between BLAKE2b and Keccak256, or you can supply your own.

Creating a Merkle tree requires a list of values that are each byte arrays. Once a tree has been created proofs can be generated using the tree's GenerateProof() function.

The package includes a function to verify a generated proof given only the data to prove, proof and the root hash of the relevant Merkle tree. This allows for efficient verification of proofs without requiring the entire Merkle tree to be stored or recreated.

Implementation notes

The tree pads its values to the next highest power of 2; values not supplied are treated as 0. This can be seen graphically by generating a DOT representation of the graph with DOT().

Index

• func VerifyProof(data []byte, proof *Proof, root []byte) (bool, error)
• func VerifyProofUsing(data []byte, proof *Proof, root []byte, hashType HashType, salt []byte) (bool, error)
• type Formatter
• type HashFunc
• type HashType
• type HexFormatter
  • func (f *HexFormatter) Format(data []byte) string
• type MerkleTree
  • func New(data [][]byte) (*MerkleTree, error)
  • func NewUsing(data [][]byte, hash HashType, salt []byte) (*MerkleTree, error)
  • func (t *MerkleTree) DOT(lf Formatter, bf Formatter) string
  • func (t *MerkleTree) GenerateProof(data []byte) (*Proof, error)
  • func (t *MerkleTree) Root() []byte
  • func (t *MerkleTree) String() string
• type Proof
• type StringFormatter
  • func (f *StringFormatter) Format(data []byte) string
• type TruncatedHexFormatter
  • func (f *TruncatedHexFormatter) Format(data []byte) string

Examples

• MerkleTree

Functions

func VerifyProof

func VerifyProof(data []byte, proof *Proof, root []byte) (bool, error)

VerifyProof verifies a Merkle tree proof for a piece of data using the default hash type. The proof and path are as per Merkle tree's GenerateProof(), and root is the root hash of the tree against which the proof is to be verified. Note that this does not require the Merkle tree to verify the proof, only its root; this allows for checking against historical trees without having to instantiate them.

This returns true if the proof is verified, otherwise false.

func VerifyProofUsing

func VerifyProofUsing(data []byte, proof *Proof, root []byte, hashType HashType, salt []byte) (bool, error)

VerifyProofUsing verifies a Merkle tree proof for a piece of data using the provided hash type. The proof and path are as per Merkle tree's GenerateProof(), and root is the root hash of the tree against which the proof is to be verified. Note that this does not require the Merkle tree to verify the proof, only its root; this allows for checking against historical trees without having to instantiate them.

This returns true if the proof is verified, otherwise false.

Types

type Formatter

type Formatter interface {
	// Format
	Format([]byte) string
}

Formatter formats a []byte in to a string. It is used by DOT() to provide users with the required format for the graphical display of their Merkle trees.

type HashFunc

type HashFunc func([]byte) []byte

HashFunc is a hashing function

type HashType

type HashType interface {
	// Hash calculates the hash of a given input
	Hash([]byte) []byte
}

HashType defines the interface that must be supplied by hash functions

type HexFormatter

type HexFormatter struct{}

HexFormatter shows the entire value

func (*HexFormatter) Format

func (f *HexFormatter) Format(data []byte) string

type MerkleTree

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

MerkleTree is the top-level structure for the merkle tree.

Example

Example using the Merkle tree to generate and verify proofs.

package main

import (
	merkletree "github.com/wealdtech/go-merkletree"
)

func main() {
	// Data for the tree
	data := [][]byte{
		[]byte("Foo"),
		[]byte("Bar"),
		[]byte("Baz"),
	}

	// Create the tree
	tree, err := merkletree.New(data)
	if err != nil {
		panic(err)
	}

	// Fetch the root hash of the tree
	root := tree.Root()

	baz := data[2]
	// Generate a proof for 'Baz'
	proof, err := tree.GenerateProof(baz)
	if err != nil {
		panic(err)
	}

	// Verify the proof for 'Baz'
	verified, err := merkletree.VerifyProof(baz, proof, root)
	if err != nil {
		panic(err)
	}
	if !verified {
		panic("failed to verify proof for Baz")
	}
}

func New

func New(data [][]byte) (*MerkleTree, error)

New creates a new Merkle tree using the provided raw data and default hash type. data must contain at least one element for it to be valid.

func NewUsing

func NewUsing(data [][]byte, hash HashType, salt []byte) (*MerkleTree, error)

NewUsing creates a new Merkle tree using the provided raw data and supplied hash type. data must contain at least one element for it to be valid.

func (*MerkleTree) DOT

func (t *MerkleTree) DOT(lf Formatter, bf Formatter) string

DOT creates a DOT representation of the tree. It is generally used for external presentation. This takes two optional formatters for []byte data: the first for leaf data and the second for branches.

func (*MerkleTree) GenerateProof

func (t *MerkleTree) GenerateProof(data []byte) (*Proof, error)

GenerateProof generates the proof for a piece of data. If the data is not present in the tree this will return an error. If the data is present in the tree this will return the hashes for each level in the tree and details of if the hashes returned are the left-hand or right-hand hashes at each level (true if the left-hand, false if the right-hand).

func (*MerkleTree) Root

func (t *MerkleTree) Root() []byte

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

func (*MerkleTree) String

func (t *MerkleTree) String() string

String implements the stringer interface

type Proof

type Proof struct {
	Hashes [][]byte
	Index  uint64
}

Proof is a proof of a Merkle tree

type StringFormatter

type StringFormatter struct{}

StringFormatter shows the entire value as a string

func (*StringFormatter) Format

func (f *StringFormatter) Format(data []byte) string

type TruncatedHexFormatter

type TruncatedHexFormatter struct{}

TruncatedHexFormatter shows only the first and last two bytes of the value

func (*TruncatedHexFormatter) Format

func (f *TruncatedHexFormatter) Format(data []byte) string