merkletree

package module
v0.0.0-...-7e813ee Latest Latest
Warning

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

 Go to latest Published: Oct 7, 2019 License: MIT Imports: 8 Imported by: 0

README

merkletree

Note: this is a fork/copy of https://gitlab.com/NebulousLabs/merkletree merkletree is a Go package for working with Merkle trees. Specifically, this package is designed to facilitate the generation and verification of "Merkle proofs" — cryptographic proofs that a given subset of data "belongs" to a larger set. BitTorrent, for example, requires downloading many small pieces of a file from many untrusted peers; Merkle proofs allow the downloader to verify that each piece is part of the full file.

When sha256 is used as the hashing algorithm, the implementation matches the merkle tree described in RFC 6962, 'Certificate Transparency'.

Usage

package main

import (
    "crypto/sha256"
    "log"
    "os"

    "gitlab.com/NebulousLabs/merkletree"
)

// All error checking is ignored in the following examples.
func main() {
	// Example 1: Get the merkle root of a file.
	segmentSize := 4096 // bytes per leaf
	file, _ := os.Open("myfile")
	merkleRoot, _ := merkletree.ReaderRoot(file, sha256.New(), segmentSize)

	// Example 2: Build and verify a proof that the element at segment 7 is in
	// the merkle root.
	file.Seek(0, 0) // Offset needs to be set back to 0.
	proofIndex := uint64(7)
	merkleRoot, proof, numLeaves, _ := merkletree.BuildReaderProof(file, sha256.New(), segmentSize, proofIndex)
	verified := VerifyProof(sha256.New(), merkleRoot, proof, proofIndex, numLeaves)

	// Example 3: Using a Tree to build a merkle tree and get a proof for a
	// specific index for non-file objects.
	tree := merkletree.New(sha256.New())
	tree.SetIndex(1)
	tree.Push([]byte("an object - the tree will hash the data after it is pushed"))
	tree.Push([]byte("another object"))
	// The merkle root could be obtained by calling tree.Root(), but will also
	// be provided by tree.Prove()
	merkleRoot, proof, proofIndex, numLeaves := tree.Prove()

	////////////////////////////////////////////////
	/// Remaining examples deal with cached trees //
	////////////////////////////////////////////////

	// Example 4: Creating a cached set of Merkle roots and then using them in
	// a cached tree. The cached tree is height 1, meaning that all elements of
	// the cached tree will be Merkle roots of data with 2 leaves.
	cachedTree := merkletree.NewCachedTree(sha256.New(), 1)
	subtree1 := merkletree.New(sha256.New())
	subtree1.Push([]byte("first leaf, first subtree"))
	subtree1.Push([]byte("second leaf, first subtree"))
	subtree2 := merkletree.New(sha256.New())
	subtree2.Push([]byte("first leaf, second subtree"))
	subtree2.Push([]byte("second leaf, second subtree"))
	// Using the cached tree, build the merkle root of the 4 leaves.
	cachedTree.Push(subtree1.Root())
	cachedTree.Push(subtree2.Root())
	collectiveRoot := cachedTree.Root()

	// Example 5: Modify the data pushed into subtree 2 and create the Merkle
	// root, without needing to rehash the data in any other subtree.
	revisedSubtree2 := merkletree.New(sha256.New())
	revisedSubtree2.Push([]byte("first leaf, second subtree"))
	revisedSubtree2.Push([]byte("second leaf, second subtree, revised"))
	// Using the cached tree, build the merkle root of the 4 leaves - without
	// needing to rehash any of the data in subtree1.
	cachedTree = merkletree.NewCachedTree(sha256.New(), 1)
	cachedTree.Push(subtree1.Root())
	cachedTree.Push(revisedSubtree2.Root())
	revisedRoot := cachedTree.Root()

	// Exapmle 6: Create a proof that leaf 3 (index 2) of the revised root,
	// found in revisedSubtree2 (at index 0 of the revised subtree), is a part of
	// the cached set. This is a two stage process - first we must get a proof
	// that the leaf is a part of revisedSubtree2, and then we must get provide
	// that proof as input to the cached tree prover.
	cachedTree = merkletree.NewCachedTree(sha256.New(), 1)
	cachedTree.SetIndex(2) // leaf at index 2, or the third element which gets inserted.
	revisedSubtree2 = merkletree.New(sha256.New())
	revisedSubtree2.SetIndex(0)
	revisedSubtree2.Push([]byte("first leaf, second subtree"))
	revisedSubtree2.Push([]byte("second leaf, second subtree, revised"))
	_, subtreeProof, _, _ := revisedSubtree2.Prove()
	// Now we can create the full proof for the cached tree, without having to
	// rehash any of the elements from subtree1.
	_, fullProof, _, _ := cachedTree.Prove(subtreeProof)
}

For more extensive documentation, refer to the godoc.

Notes

This implementation does not retain the entire Merkle tree in memory. Rather, as each new leaf is added to the tree, is it pushed onto a stack as a "subtree of depth 1." If the next element on the stack also has depth 1, the two are combined into a "subtree of depth 2." This process continues until no adjacent elements on the stack have the same depth. (For a nice visual representation of this, play a round of 2048.) This gives a space complexity of O(log(n)), making this implementation suitable for generating Merkle proofs on very large files. (It is not as suitable for generating "batches" of many Merkle proofs on the same file.)

Different Merkle tree implementations handle "orphan" leaves in different ways. Our trees conform to the diagrams below; orphan leaves are not duplicated or hashed multiple times.

     ┌───┴──┐       ┌────┴───┐         ┌─────┴─────┐
  ┌──┴──┐   │    ┌──┴──┐     │      ┌──┴──┐     ┌──┴──┐
┌─┴─┐ ┌─┴─┐ │  ┌─┴─┐ ┌─┴─┐ ┌─┴─┐  ┌─┴─┐ ┌─┴─┐ ┌─┴─┐   │
   (5-leaf)         (6-leaf)             (7-leaf)

When using the Reader functions (ReaderRoot and BuildReaderProof), the last segment will not be padded if there are not 'segmentSize' bytes remaining.

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

View Source 
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

This section is empty.

Functions

func BuildDiffProof 

func BuildDiffProof(ranges []LeafRange, h SubtreeHasher, numLeaves uint64) (proof [][]byte, err error)

BuildDiffProof constructs a Merkle diff for the specified leaf ranges, using the provided SubtreeHasher. The ranges must be sorted and non-overlapping.

func BuildMultiRangeProof 

func BuildMultiRangeProof(ranges []LeafRange, h SubtreeHasher) (proof [][]byte, err error)

BuildMultiRangeProof constructs a proof for the specified leaf ranges, using the provided SubtreeHasher. The ranges must be sorted and non-overlapping.

func BuildRangeProof 

func BuildRangeProof(proofStart, proofEnd int, h SubtreeHasher) (proof [][]byte, err error)

BuildRangeProof constructs a proof for the leaf range [proofStart, proofEnd) using the provided SubtreeHasher.

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 CompressLeafHashes 

func CompressLeafHashes(ranges []LeafRange, h SubtreeHasher) (compressed [][]byte, err error)

CompressLeafHashes takes the ranges of modified leaves as an input together with a SubtreeHasher which can produce all modified leaf hashes to compress the leaf hashes into subtrees where possible. These compressed leaf hashes can be used as the 'rangeHashes' input to VerifyDiffProof.

func ConvertRangeProofToSingleProof 

func ConvertRangeProofToSingleProof(proof [][]byte, proofIndex int) [][]byte

ConvertRangeProofToSingleProof converts a single-leaf range proof to the equivalent proof produced by (*Tree).Prove. proofIndex must be >= 0.

func ConvertSingleProofToRangeProof 

func ConvertSingleProofToRangeProof(proof [][]byte, proofIndex int) [][]byte

ConvertSingleProofToRangeProof converts a proof produced by (*Tree).Prove to a single-leaf range proof. proofIndex must be >= 0.

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 VerifyDiffProof 

func VerifyDiffProof(rangeHashes [][]byte, numLeaves uint64, h hash.Hash, ranges []LeafRange, proof [][]byte, root []byte) (bool, error)

VerifyDiffProof verifies a proof produced by BuildDiffProof using subtree hashes produced by sh, which must contain the concatenation of the subtree hashes within the proof ranges.

func VerifyMultiRangeProof 

func VerifyMultiRangeProof(lh LeafHasher, h hash.Hash, ranges []LeafRange, proof [][]byte, root []byte) (bool, error)

VerifyMultiRangeProof verifies a proof produced by BuildMultiRangeProof using leaf hashes produced by lh, which must contain the concatenation of the leaf hashes within the proof ranges.

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.

func VerifyRangeProof 

func VerifyRangeProof(lh LeafHasher, h hash.Hash, proofStart, proofEnd int, proof [][]byte, root []byte) (bool, error)

VerifyRangeProof verifies a proof produced by BuildRangeProof using leaf hashes produced by lh, which must contain only the leaf hashes within the proof range.

Types

type CachedLeafHasher 

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

CachedLeafHasher implements the LeafHasher interface by returning precomputed leaf hashes.

func NewCachedLeafHasher 

func NewCachedLeafHasher(leafHashes [][]byte) *CachedLeafHasher

NewCachedLeafHasher creates a CachedLeafHasher from a set of precomputed leaf hashes.

func (*CachedLeafHasher) NextLeafHash 

func (clh *CachedLeafHasher) NextLeafHash() ([]byte, error)

NextLeafHash implements LeafHasher.

type CachedSubtreeHasher 

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

CachedSubtreeHasher implements SubtreeHasher using a set of precomputed leaf hashes.

func NewCachedSubtreeHasher 

func NewCachedSubtreeHasher(leafHashes [][]byte, h hash.Hash) *CachedSubtreeHasher

NewCachedSubtreeHasher creates a CachedSubtreeHasher using the specified leaf hashes and hash function.

func (*CachedSubtreeHasher) NextSubtreeRoot 

func (csh *CachedSubtreeHasher) NextSubtreeRoot(subtreeSize int) ([]byte, error)

NextSubtreeRoot implements SubtreeHasher.

func (*CachedSubtreeHasher) Skip 

func (csh *CachedSubtreeHasher) Skip(n int) error

Skip implements SubtreeHasher.

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 LeafHasher 

type LeafHasher interface {
	NextLeafHash() ([]byte, error)
}

A LeafHasher returns the leaves of a Merkle tree in sequential order. When no more leaves are available, NextLeafHash must return io.EOF.

type LeafRange 

type LeafRange struct {
	Start uint64
	End   uint64
}

A LeafRange represents the contiguous set of leaves [Start,End).

type MixedSubtreeHasher 

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

MixedSubtreeHasher implements SubtreeHasher by using cached subtree hashes when possible and otherwise reading leaf hashes from the underlying stream.

func NewMixedSubtreeHasher 

func NewMixedSubtreeHasher(nodeHashes [][]byte, leafReader io.Reader, leavesPerNode int, leafSize int, h hash.Hash) *MixedSubtreeHasher

NewMixedSubtreeHasher returns a new MixedSubtreeHasher that hashes nodeHashes which are already computed hashes of leavesPerNode leaves and also reads individual leaves from leafReader. The behavior of this implementation is greedy in regards to using the cached nodeHashes. A nodeHash will be consumed as soon as NextSubtreeRoot or Skip are called with a size greater than or equal to leavesPerNode.

func (*MixedSubtreeHasher) NextSubtreeRoot 

func (msh *MixedSubtreeHasher) NextSubtreeRoot(subtreeSize int) ([]byte, error)

NextSubtreeRoot implements SubtreeHasher.

func (*MixedSubtreeHasher) Skip 

func (msh *MixedSubtreeHasher) Skip(n int) error

Skip implements SubtreeHasher.

type ReaderLeafHasher 

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

ReaderLeafHasher implements the LeafHasher interface by reading leaf data from the underlying stream.

func NewReaderLeafHasher 

func NewReaderLeafHasher(r io.Reader, h hash.Hash, leafSize int) *ReaderLeafHasher

NewReaderLeafHasher creates a ReaderLeafHasher with the specified stream, hash, and leaf size.

func (*ReaderLeafHasher) NextLeafHash 

func (rlh *ReaderLeafHasher) NextLeafHash() ([]byte, error)

NextLeafHash implements LeafHasher.

type ReaderSubtreeHasher 

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

ReaderSubtreeHasher implements SubtreeHasher by reading leaf data from an underlying stream.

func NewReaderSubtreeHasher 

func NewReaderSubtreeHasher(r io.Reader, leafSize int, h hash.Hash) *ReaderSubtreeHasher

NewReaderSubtreeHasher returns a new ReaderSubtreeHasher that reads leaf data from r.

func (*ReaderSubtreeHasher) NextSubtreeRoot 

func (rsh *ReaderSubtreeHasher) NextSubtreeRoot(subtreeSize int) ([]byte, error)

NextSubtreeRoot implements SubtreeHasher.

func (*ReaderSubtreeHasher) Skip 

func (rsh *ReaderSubtreeHasher) Skip(n int) (err error)

Skip implements SubtreeHasher.

type SubtreeHasher 

type SubtreeHasher interface {
	// NextSubtreeRoot returns the root of the next n leaves. If fewer than n
	// leaves are left in the tree, NextSubtreeRoot returns the root of those
	// leaves and nil. If no leaves are left, NextSubtreeRoot returns io.EOF.
	NextSubtreeRoot(n int) ([]byte, error)
	// Skip skips the next n leaves. If fewer than n leaves are left in the
	// tree, Skip returns io.ErrUnexpectedEOF. If exactly n leaves are left,
	// Skip returns nil (not io.EOF).
	Skip(n int) error
}

A SubtreeHasher calculates subtree roots in sequential order, for use with BuildRangeProof.

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

Source Files

View all Source files

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.