merkletree

Documentation

Overview

Package merkletree holds code to manipulate Merkle trees.

Index

• Constants
• type FullMerkleTreeInterface
• type HasherFunc
• type MerkleTreeInterface
• type MerkleVerifier
  • func NewMerkleVerifier(h HasherFunc) MerkleVerifier
  • func (m MerkleVerifier) RootFromInclusionProof(leafIndex, treeSize int64, proof [][]byte, leaf []byte) ([]byte, error)
  • func (m MerkleVerifier) RootFromInclusionProofAndHash(leafIndex, treeSize int64, proof [][]byte, leafHash []byte) ([]byte, error)
  • func (m MerkleVerifier) VerifyConsistencyProof(snapshot1, snapshot2 int64, root1, root2 []byte, proof [][]byte) error
  • func (m MerkleVerifier) VerifyInclusionProof(leafIndex, treeSize int64, proof [][]byte, root []byte, leaf []byte) error
  • func (m MerkleVerifier) VerifyInclusionProofByHash(leafIndex, treeSize int64, proof [][]byte, root []byte, leafHash []byte) error
• type RootMismatchError
  • func (e RootMismatchError) Error() string
• type TreeHasher
  • func NewTreeHasher(h HasherFunc) *TreeHasher
  • func (h TreeHasher) HashChildren(left, right []byte) []byte
  • func (h TreeHasher) HashEmpty() []byte
  • func (h TreeHasher) HashLeaf(leaf []byte) []byte

Constants

const (
	// LeafPrefix is the domain separation prefix for leaf hashes.
	LeafPrefix = 0

	// NodePrefix is the domain separation prefix for internal tree nodes.
	NodePrefix = 1
)

Types

type FullMerkleTreeInterface

type FullMerkleTreeInterface interface {
	MerkleTreeInterface

	// RootAtSnapshot returns the root hash at the tree size |snapshot|
	// which must be <= than the current tree size.
	RootAtSnapshot(snapshot uint64) ([]byte, error)

	// PathToCurrentRoot returns the Merkle path (or inclusion proof) from the
	// leaf hash at index |leaf| to the current root.
	PathToCurrentRoot(leaf uint64) ([]byte, error)

	// SnapshotConsistency returns a consistency proof between the two tree
	// sizes specified in |snapshot1| and |snapshot2|.
	SnapshotConsistency(snapshot1, snapshot2 uint64) ([]byte, error)
}

FullMerkleTreeInterface extends MerkleTreeInterface to the full range of operations that only a non-compact tree representation can implement.

type HasherFunc

type HasherFunc func([]byte) []byte

HasherFunc takes a slice of bytes and returns a cryptographic hash of those bytes.

type MerkleTreeInterface

type MerkleTreeInterface interface {
	// LeafCount returns the number of leaves in the tree
	LeafCount() uint64

	// LevelCount returns the number of levels in the tree
	LevelCount() uint64

	// AddLeaf adds the hash of |leaf| to the tree and returns the newly added
	// leaf index
	AddLeaf(leaf []byte) uint64

	// LeafHash returns the hash of the leaf at index |leaf| or a non-nil error.
	LeafHash(leaf uint64) ([]byte, error)

	// CurrentRoot returns the current root hash of the merkle tree.
	CurrentRoot() ([]byte, error)
}

MerkleTreeInterface represents the common interface for basic MerkleTree functions.

type MerkleVerifier

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

MerkleVerifier is a class which knows how to verify merkle inclusion and consistency proofs.

func NewMerkleVerifier

func NewMerkleVerifier(h HasherFunc) MerkleVerifier

NewMerkleVerifier returns a new MerkleVerifier for a tree based on the passed in hasher.

func (MerkleVerifier) RootFromInclusionProof

func (m MerkleVerifier) RootFromInclusionProof(leafIndex, treeSize int64, proof [][]byte, leaf []byte) ([]byte, error)

RootFromInclusionProof calculates the expected tree root given the proof and leaf. leafIndex starts at 0. treeSize starts at 1.

func (MerkleVerifier) RootFromInclusionProofAndHash

func (m MerkleVerifier) RootFromInclusionProofAndHash(leafIndex, treeSize int64, proof [][]byte, leafHash []byte) ([]byte, error)

RootFromInclusionProofAndHash calculates the expected tree root given the proof and leaf hash. leafIndex starts at 0. treeSize starts at 1.

func (MerkleVerifier) VerifyConsistencyProof

func (m MerkleVerifier) VerifyConsistencyProof(snapshot1, snapshot2 int64, root1, root2 []byte, proof [][]byte) error

VerifyConsistencyProof checks that the passed in consistency proof is valid between the passed in tree snapshots.

func (MerkleVerifier) VerifyInclusionProof

func (m MerkleVerifier) VerifyInclusionProof(leafIndex, treeSize int64, proof [][]byte, root []byte, leaf []byte) error

VerifyInclusionProof verifies the correctness of the proof given the passed in information about the tree and leaf.

func (MerkleVerifier) VerifyInclusionProofByHash

func (m MerkleVerifier) VerifyInclusionProofByHash(leafIndex, treeSize int64, proof [][]byte, root []byte, leafHash []byte) error

VerifyInclusionProofByHash verifies the correctness of the proof given tree and leaf hash.

type RootMismatchError

type RootMismatchError struct {
	ExpectedRoot   []byte
	CalculatedRoot []byte
}

RootMismatchError occurs when an inclusion proof fails.

func (RootMismatchError) Error

func (e RootMismatchError) Error() string

type TreeHasher

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

TreeHasher performs the various hashing operations required when manipulating MerkleTrees.

func NewTreeHasher

func NewTreeHasher(h HasherFunc) *TreeHasher

NewTreeHasher returns a new TreeHasher based on the passed in hash.

func (TreeHasher) HashChildren

func (h TreeHasher) HashChildren(left, right []byte) []byte

HashChildren returns the merkle hash of the two passed in children.

func (TreeHasher) HashEmpty

func (h TreeHasher) HashEmpty() []byte

HashEmpty returns the hash of the empty string.

func (TreeHasher) HashLeaf

func (h TreeHasher) HashLeaf(leaf []byte) []byte

HashLeaf returns the hash of the passed in leaf, after applying domain separation.