## Documentation ¶

### Overview ¶

Package merkletree provides tools for calculating the Merkle root of a dataset, for creating a proof that a piece of data is in a Merkle tree of a given root, and for verifying proofs that a piece of data is in a Merkle tree of a given root. The tree is implemented according to the specification for Merkle trees provided in RFC 6962.

Package merkletree also supports building roots and proofs from cached subroots of the Merkle tree. For example, a large file could be cached by building the Merkle root for each 4MB sector and remembering the Merkle roots of each sector. Using a cached tree, the Merkle root of the whole file can be computed by passing the cached tree each of the roots of the 4MB sector. Building proofs using these cached roots is also supported. A proof must be built within the target sector using a normal Tree, requiring the whole sector to be hashed. The results of that proof can then be passed into the Prove() function of a cached tree, which will create the full proof without needing to hash the entire file. Caching also makes it inexpensive to update the Merkle root of the file after changing or deleting segments of the larger file.

Examples can be found in the README for the package.

### Index ¶

- Constants
- func BuildReaderProof(r io.Reader, h hash.Hash, segmentSize int, index uint64) (root []byte, proofSet [][]byte, numLeaves uint64, err error)
- 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 CachedTree
- type Tree
- 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

### Constants ¶

const ( // DEBUG indicates whether debugging is enabled. When debugging is enabled, // checks are performed on all stateful objects to make sure no supposedly // impossible conditions have occurred. The DEBUG flag is for developers. DEBUG = false )

### Variables ¶

### 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 ReaderRoot ¶

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 CachedTree ¶

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

A CachedTree can be used to build Merkle roots and proofs from the cached Merkle roots of smaller blocks of data. Each CachedTree has a height, meaning every element added to the CachedTree is the root of a full Merkle tree containing 2^height leaves.

#### func NewCachedTree ¶

func NewCachedTree(h hash.Hash, cachedNodeHeight uint64) *CachedTree

NewCachedTree initializes a CachedTree with a hash object, which will be used when hashing the input.

#### func (*CachedTree) Prove ¶

func (ct *CachedTree) Prove(cachedProofSet [][]byte) (merkleRoot []byte, proofSet [][]byte, proofIndex uint64, numLeaves uint64)

Prove will create a proof that the leaf at the indicated index is a part of the data represented by the Merkle root of the Cached Tree. The CachedTree needs the proof set proving that the index is an element of the cached element in order to create a correct proof. After proof is called, the CachedTree is unchanged, and can receive more elements.

#### func (*CachedTree) SetIndex ¶

func (ct *CachedTree) SetIndex(i uint64) error

SetIndex will inform the CachedTree of the index of the leaf for which a storage proof is being created. The index should be the index of the actual leaf, and not the index of the cached element containing the leaf. SetIndex must be called on empty CachedTree.

#### 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 ¶

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

#### func (*Tree) Prove ¶

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 ¶

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 ¶

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 ¶

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'.