merkletree

package module
v1.0.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 29, 2022 License: Apache-2.0 Imports: 7 Imported by: 0

README

go-merkletree

Tag License GoDoc Travis CI codecov.io Go Report Card

Go implementation of a Merkle tree.

Table of Contents

Install

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

go get github.com/wealdtech/go-merkletree

Usage

go-merkletree generates Merkle trees from an array of []byte values and uses them to generate proofs. Proofs can be verified, and graphs generated

This package uses pollards and sparese multiproofs for efficient generation of multiple proofs against the same tree; see the articles Understanding Merkle pollards and Understanding sparse Merkle multiproofs for details.

This package can generate visualisations (in DOT format) for trees and proofs. Below is a tree visualisation:

Merkle tree

and below is a proof visualisation with the value being proved in red, the intermediate branches in green and the root in blue:

Merkle proof

Example
package main

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

// Example using the Merkle tree to generate and verify proofs.
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, 0)
	if err != nil {
		panic(err)
	}

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

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.

This implementation includes advanced features salting and pollarding. Salting is the act of adding a piece of data to each value in the Merkle tree as it is initially hashed to form the leaves, which helps avoid rainbow table attacks on leaf hashes presented as part of proofs. Pollarding is the act of providing the root plus all branches to a certain height which can be used to reduce the size of proofs. This is useful when multiple proofs are presented against the same tree as it can reduce the overall size.

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 VerifyProof() to verify a generated proof given only the data to prove, proof and the pollard 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 null with a value hash of 0. This can be seen graphically by generating a DOT representation of the graph with DOT().

If salting is enabled it appends an 4-byte value to each piece of data. The value is the binary representation of the index in big-endian form. Note that if there are more than 2^32 values in the tree the salt will wrap, being modulo 2^32

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.

This implementation includes advanced features salting and pollarding. Salting is the act of adding a piece of data to each value in the Merkle tree as it is initially hashed to form the leaves, which helps avoid rainbow table attacks on leaf hashes presented as part of proofs. Pollarding is the act of providing the root plus all branches to a certain height which can be used to reduce the size of proofs. This is useful when multiple proofs are presented against the same tree as it can reduce the overall size.

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 VerifyProof() to verify a generated proof given only the data to prove, proof and the pollard 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 null with a value hash of 0. This can be seen graphically by generating a DOT representation of the graph with DOT().

If salting is enabled it appends an 4-byte value to each piece of data. The value is the binary representation of the index in big-endian form. Note that if there are more than 2^32 values in the tree the salt will wrap, being modulo 2^32

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func VerifyMultiProof 

func VerifyMultiProof(data [][]byte, salt bool, proof *MultiProof, root []byte) (bool, error)

VerifyMultiProof verifies multiple Merkle tree proofs for pieces 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 VerifyMultiProofUsing 

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

VerifyMultiProofUsing verifies multiple Merkle tree proofs for pieces of data using the provided hash type. The proof and is 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 VerifyPollard 

func VerifyPollard(pollard [][]byte) bool

VerifyPollard ensures that the branches in the pollard match up with the root using the default hash type.

func VerifyPollardUsing 

func VerifyPollardUsing(pollard [][]byte, hashType HashType) bool

VerifyPollardUsing ensures that the branches in the pollard match up with the root using the supplied hash type.

func VerifyProof 

func VerifyProof(data []byte, salt bool, proof *Proof, pollard [][]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, salt bool, proof *Proof, pollard [][]byte, hashType HashType) (bool, error)

VerifyProofUsing verifies a Merkle tree proof for a piece of data using the provided hash type. The proof and is 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

	// HashLength provides the length of the hash
	HashLength() int
}

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

Format formats a value as a full hex string

type MerkleTree 

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

MerkleTree is the structure for the Merkle tree.

Example

Example using the Merkle tree to generate and verify proofs. 

package main

import (
	"fmt"

	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, 0)
	if err != nil {
		panic(err)
	}

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

	fmt.Printf("%x\n", root)
}

Output:

2c95331b1a38dba3600391a3e864f9418a271388936e54edecd916824bb54203

func New 

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

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

func NewUsing 

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

NewUsing creates a new Merkle tree using the provided raw data and supplied hash type. Salting is used if requested. 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) DOTMultiProof 

func (t *MerkleTree) DOTMultiProof(multiProof *MultiProof, lf Formatter, bf Formatter) string

DOTMultiProof creates a DOT representation of the tree with highlights for a multiproof. 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) DOTProof 

func (t *MerkleTree) DOTProof(proof *Proof, lf Formatter, bf Formatter) string

DOTProof creates a DOT representation of the tree with highlights for a proof. 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) GenerateMultiProof 

func (t *MerkleTree) GenerateMultiProof(data [][]byte) (*MultiProof, error)

GenerateMultiProof generates the proof for multiple pieces of data.

func (*MerkleTree) GenerateProof 

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

GenerateProof generates the proof for a piece of data. Height is the height of the pollard to verify the proof. If using the Merkle root to verify this should be 0. 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 the index of the value in the tree

func (*MerkleTree) GenerateProofUsingIndex 

func (t *MerkleTree) GenerateProofUsingIndex(index uint64, height int) (*Proof, error)

GenerateProof generates the proof for a piece of data. Height is the height of the pollard to verify the proof. If using the Merkle root to verify this should be 0. Index should be the leaf node index to generate proof for. This will return the hashes for each level in the tree and the index of the value in the tree

func (*MerkleTree) Pollard 

func (t *MerkleTree) Pollard(height int) [][]byte

Pollard returns the Merkle root plus branches to a certain height. Height 0 will return just the root, height 1 the root plus the two branches directly above it, height 2 the root, two branches directly above it and four branches directly above them, etc.

func (*MerkleTree) Root 

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

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

func (*MerkleTree) Salt 

func (t *MerkleTree) Salt() bool

Salt returns the true if the values in this Merkle tree are salted.

func (*MerkleTree) String 

func (t *MerkleTree) String() string

String implements the stringer interface

type MultiProof 

type MultiProof struct {
	// Values is the number of values in the Merkle tree
	Values uint64
	// Hashes are indexed hashes of values that cannot be calculated from the index data
	Hashes map[uint64][]byte
	// Indices are the indices of the data that can be proved with the hashes
	Indices []uint64
}

MultiProof is a single structure containing multiple proofs of a Merkle tree.

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

Format formats a value as a UTF-8 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

Format formats a value as truncated hex, showing the first and last four characers of the hex string.

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.