merkletree

Documentation

Index

• func BuildReaderProof(r io.Reader, h hash.Hash, segmentSize int, index uint64) (root []byte, proofSet [][]byte, numLeaves uint64, err error)
• func GenerateProofHelper(proofSet [][]byte, proofIndex, numLeaves uint64) []int
• func ReaderRoot(r io.Reader, h hash.Hash, segmentSize int) (root []byte, err error)
• func VerifyProof(h hash.Hash, merkleRoot []byte, proofSet [][]byte, proofIndex uint64, ...) bool
• type SubTree
  • func (t *SubTree) GetHeight() int
  • func (t *SubTree) GetSum() []byte
• type Tree
  • func New(h hash.Hash) *Tree
  • func (t *Tree) GetAllSubTrees() []*SubTree
  • func (t *Tree) Prove() (merkleRoot []byte, proofSet [][]byte, proofIndex uint64, numLeaves uint64)
  • func (t *Tree) Push(data []byte)
  • func (t *Tree) PushSubTree(height int, sum []byte) error
  • func (t *Tree) ReadAll(r io.Reader, segmentSize int) error
  • func (t *Tree) Root() []byte
  • func (t *Tree) SetIndex(i uint64) error

Functions

func BuildReaderProof

func BuildReaderProof(r io.Reader, h hash.Hash, segmentSize int, index uint64) (root []byte, proofSet [][]byte, numLeaves uint64, err error)

BuildReaderProof returns a proof that certain data is in the merkle tree created by the data in the reader. The merkle root, set of proofs, and the number of leaves in the Merkle tree are all returned. All leaves will we 'segmentSize' bytes except the last leaf, which will not be padded out if there are not enough bytes remaining in the reader.

func GenerateProofHelper

func GenerateProofHelper(proofSet [][]byte, proofIndex, numLeaves uint64) []int

GenerateProofHelper generates an array of 1 or 0 telling if during the proof verification the hash to compute is h(sum, proof[i]) or h(proof[i], sum). The size of the resulting slice is len(proofSet)-1. cf gitlab.com/NebulousLabs/merkletree for the algorithm

func ReaderRoot

func ReaderRoot(r io.Reader, h hash.Hash, segmentSize int) (root []byte, err error)

ReaderRoot returns the Merkle root of the data read from the reader, where each leaf is 'segmentSize' long and 'h' is used as the hashing function. All leaves will be 'segmentSize' bytes except the last leaf, which will not be padded out if there are not enough bytes remaining in the reader.

func VerifyProof

func VerifyProof(h hash.Hash, merkleRoot []byte, proofSet [][]byte, proofIndex uint64, numLeaves uint64) bool

VerifyProof takes a Merkle root, a proofSet, and a proofIndex and returns true if the first element of the proof set is a leaf of data in the Merkle root. False is returned if the proof set or Merkle root is nil, and if 'numLeaves' equals 0.

Types

type SubTree

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

A subTree contains the Merkle root of a complete (2^height leaves) subTree of the Tree. 'sum' is the Merkle root of the subTree. If 'next' is not nil, it will be a tree with a higher height.

func (*SubTree) GetHeight

func (t *SubTree) GetHeight() int

func (*SubTree) GetSum

func (t *SubTree) GetSum() []byte

type Tree

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

A Tree takes data as leaves and returns the Merkle root. Each call to 'Push' adds one leaf to the Merkle tree. Calling 'Root' returns the Merkle root. The Tree also constructs proof that a single leaf is a part of the tree. The leaf can be chosen with 'SetIndex'. The memory footprint of Tree grows in O(log(n)) in the number of leaves.

func New

func New(h hash.Hash) *Tree

New creates a new Tree. The provided hash will be used for all hashing operations within the Tree.

func (*Tree) GetAllSubTrees

func (t *Tree) GetAllSubTrees() []*SubTree

func (*Tree) Prove

func (t *Tree) Prove() (merkleRoot []byte, proofSet [][]byte, proofIndex uint64, numLeaves uint64)

Prove creates a proof that the leaf at the established index (established by SetIndex) is an element of the Merkle tree. Prove will return a nil proof set if used incorrectly. Prove does not modify the Tree. Prove can only be called if SetIndex has been called previously.

func (*Tree) Push

func (t *Tree) Push(data []byte)

Push will add data to the set, building out the Merkle tree and Root. The tree does not remember all elements that are added, instead only keeping the log(n) elements that are necessary to build the Merkle root and keeping the log(n) elements necessary to build a proof that a piece of data is in the Merkle tree.

func (*Tree) PushSubTree

func (t *Tree) PushSubTree(height int, sum []byte) error

PushSubTree pushes a cached subtree into the merkle tree. The subtree has to be smaller than the smallest subtree in the merkle tree, it has to be balanced and it can't contain the element that needs to be proven. Since we can't tell if a subTree is balanced, we can't sanity check for unbalanced trees. Therefore an unbalanced tree will cause silent errors, pain and misery for the person who wants to debug the resulting error.

func (*Tree) ReadAll

func (t *Tree) ReadAll(r io.Reader, segmentSize int) error

ReadAll will read segments of size 'segmentSize' and push them into the tree until EOF is reached. Success will return 'err == nil', not 'err == EOF'. No padding is added to the data, so the last element may be smaller than 'segmentSize'.

func (*Tree) Root

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

Root returns the Merkle root of the data that has been pushed.

func (*Tree) SetIndex

func (t *Tree) SetIndex(i uint64) error

SetIndex will tell the Tree to create a storage proof for the leaf at the input index. SetIndex must be called on an empty tree.