merkletree

package module
v1.0.3 Latest Latest
Warning

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

 Go to latest Published: Aug 15, 2023 License: Apache-2.0 Imports: 16 Imported by: 1

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/MetaDataLab/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/MetaDataLab/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.NewTree(merkletree.WithData(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 deprecated 

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.

Deprecated: please use MultiProof.Verify(...)

func VerifyMultiProofUsing deprecated 

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.

Deprecated: please use MultiProof.Verify(...)

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 Export 

type Export struct {
	// if salt is true the data values are salted with their index
	Salt bool `json:"salt"`
	// if sorted is true, the hash values are sorted before hashing branch nodes
	Sorted bool `json:"sorted"`
	// data is the data from which the Merkle tree is created
	Data [][]byte `json:"data"`
	// nodes are the leaf and branch nodes of the Merkle tree
	Nodes [][]byte `json:"nodes"`
	// HashCode specifies the hash type
	HashCode HashCode `json:"hash_code"`
}

Export is the structure for exporting the MerkleTree, the hashtype needs to be specified on load.

func (Export) MarshalEasyJSON 

func (v Export) MarshalEasyJSON(w *jwriter.Writer)

MarshalEasyJSON supports easyjson.Marshaler interface

func (Export) MarshalJSON 

func (v Export) MarshalJSON() ([]byte, error)

MarshalJSON supports json.Marshaler interface

func (*Export) UnmarshalEasyJSON 

func (v *Export) UnmarshalEasyJSON(l *jlexer.Lexer)

UnmarshalEasyJSON supports easyjson.Unmarshaler interface

func (*Export) UnmarshalJSON 

func (v *Export) UnmarshalJSON(data []byte) error

UnmarshalJSON supports json.Unmarshaler interface

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 HashCode 

type HashCode int
const (
	INVALID   HashCode = iota // 0
	BLAKE2B                   // 1
	KECCAK256                 // 2
	SHA256                    // 3
	SHA512                    // 4
)

func GetHashCode 

func GetHashCode(value HashType) (HashCode, error)

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.

func GetHashTypeFromCode 

func GetHashTypeFromCode(code HashCode) (HashType, error)

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/MetaDataLab/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 ImportBinaryMerkleTree 

func ImportBinaryMerkleTree(imp []byte, hash HashType) (*MerkleTree, error)

func ImportBinaryMerkleTreeV2 

func ImportBinaryMerkleTreeV2(imp []byte) (*MerkleTree, error)

func ImportMerkleTree 

func ImportMerkleTree(imp []byte, hash HashType) (*MerkleTree, error)

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. Deprecated: plase use NewTree().

func NewTree 

func NewTree(params ...Parameter) (*MerkleTree, error)

NewTree creates a new merkle tree using the provided information.

func NewTreeWithLeavesHashes 

func NewTreeWithLeavesHashes(leavesNodes [][]byte, hashType HashType) (*MerkleTree, error)

NewTreeWithLeavesHashes creates a new merkle tree using leaves hashes, generating a tree without data.

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, and hashes are sorted if requested. data must contain at least one element for it to be valid. Deprecated: plase use NewTree().

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

func (t *MerkleTree) Export() ([]byte, error)

func (*MerkleTree) ExportBinary 

func (t *MerkleTree) ExportBinary() ([]byte, error)

func (*MerkleTree) ExportBinaryV2 

func (t *MerkleTree) ExportBinaryV2(withdata bool) ([]byte, error)

func (*MerkleTree) GenerateIndexProof 

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

GenerateIndexProof generates the proof for the data of number Index. Height is the height of the pollard to verify the proof. If using the Merkle root to verify this should be 0. If the Index is greater than the data count in the tree this will return an error. If the Index is valid this will return the hashes for each level in the tree and the index of the value in the tree.

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

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

LeavesNodes returns the hashes of the leaves of the tree.

func (MerkleTree) MarshalEasyJSON 

func (v MerkleTree) MarshalEasyJSON(w *jwriter.Writer)

MarshalEasyJSON supports easyjson.Marshaler interface

func (MerkleTree) MarshalJSON 

func (v MerkleTree) MarshalJSON() ([]byte, error)

MarshalJSON supports json.Marshaler interface

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.

func (*MerkleTree) UnmarshalEasyJSON 

func (v *MerkleTree) UnmarshalEasyJSON(l *jlexer.Lexer)

UnmarshalEasyJSON supports easyjson.Unmarshaler interface

func (*MerkleTree) UnmarshalJSON 

func (v *MerkleTree) UnmarshalJSON(data []byte) error

UnmarshalJSON supports json.Unmarshaler 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
	// contains filtered or unexported fields
}

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

func NewMultiProof 

func NewMultiProof(params ...Parameter) (*MultiProof, error)

NewMultiProof creates a new multiproof using the provided information.

func (*MultiProof) Verify 

func (p *MultiProof) Verify(data [][]byte, root []byte) (bool, error)

Verify verifies a multiproof.

type Parameter 

type Parameter interface {
	// contains filtered or unexported methods
}

Parameter is the interface for service parameters.

func WithData 

func WithData(data [][]byte) Parameter

WithData sets the data for the merkle tree.

func WithHashType 

func WithHashType(hash HashType) Parameter

WithHashType sets the hash type for the merkle tree or proof.

func WithHashes 

func WithHashes(hashes map[uint64][]byte) Parameter

WithHashes sets the indexed hashes of values that cannot be calculated from the proof.

func WithIndices 

func WithIndices(indices []uint64) Parameter

WithIndices sets the indices that can be calculated from the proof.

func WithSalt 

func WithSalt(salt bool) Parameter

WithSalt sets the salt for the merkle tree or proof.

func WithSorted 

func WithSorted(sorted bool) Parameter

WithSorted sets the sorted for the merkle tree.

func WithValues 

func WithValues(values uint64) Parameter

WithValues sets the values for the merkle proof.

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.