merkle

README

NOTE

This implementation is forked from cbergoon's implementation. I claim no authorship over this code apart from some minor modifications.

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.

Documentation

Index

• func GetBinaryMerkleRoot(level []common.Hash) common.Hash
• func GetMerkleProof(leafLevel []common.Hash, index int) []common.Hash
• type Content
• type DerivableList
• type MerkleTree
  • func NewTree(contents []Content) (*MerkleTree, error)
  • func (m *MerkleTree) MerkleRoot() common.Hash
  • func (m *MerkleTree) RebuildTree() error
  • func (m *MerkleTree) RebuildTreeWith(cs []Content) error
  • func (m *MerkleTree) String() string
  • func (m *MerkleTree) VerifyContent(expectedMerkleRoot []byte, content Content) bool
  • func (m *MerkleTree) VerifyTree() bool

Functions

func GetBinaryMerkleRoot

func GetBinaryMerkleRoot(level []common.Hash) common.Hash

func GetMerkleProof

func GetMerkleProof(leafLevel []common.Hash, index int) []common.Hash

Types

type Content

type Content interface {
	CalculateHash() common.Hash
	Equals(other Content) bool
}

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 DerivableList

type DerivableList interface {
	Len() int
	GetRlp(i int) []byte
}

type MerkleTree

type MerkleTree struct {
	Root *node

	Leaves []*node
	// contains filtered or unexported fields
}

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. Note, it is not thread safe

func NewTree

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

NewTree creates a new Merkle Tree using the specified contents.

func (*MerkleTree) MerkleRoot

func (m *MerkleTree) MerkleRoot() common.Hash

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

func (*MerkleTree) RebuildTree

func (m *MerkleTree) RebuildTree() error

RebuildTree is a helper function that will rebuild the tree by only reusing the contents held in the leaves.

func (*MerkleTree) RebuildTreeWith

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

RebuildTreeWith replaces the contents of the tree and does a complete rebuilding. while the root of the tree will be replaced, the Merkle tree completely survives. Return an error if the list of contents contains no entries.

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(expectedMerkleRoot []byte, content Content) bool

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

func (*MerkleTree) VerifyTree

func (m *MerkleTree) VerifyTree() bool

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