merkle

package
v1.0.1 Latest Latest
Warning

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

Go to latest
Published: Sep 20, 2017 License: Apache-2.0 Imports: 13 Imported by: 0

Documentation

Overview

Package merkle provides Merkle tree manipulation functions.

Index

Constants

This section is empty.

Variables

View Source
var (
	// ErrNoSuchRevision is returned when a request is made for information about
	// a tree revision which does not exist.
	ErrNoSuchRevision = errors.New("no such revision")
)
View Source
var (
	// ErrSubtreeOverrun indicates that a subtree exceeds the maximum tree depth.
	ErrSubtreeOverrun = errors.New("subtree with prefix exceeds maximum tree size")
)

Functions

func VerifyMapInclusionProof

func VerifyMapInclusionProof(treeID int64, index, leaf, expectedRoot []byte, proof [][]byte, h hashers.MapHasher) error

VerifyMapInclusionProof verifies that the passed in expectedRoot can be reconstructed correctly given the other parameters.

The process is essentially the same as the inclusion proof checking for append-only logs, but adds support for nil/"default" proof nodes.

Returns nil on a successful verification, and an error otherwise.

Types

type ByIndex

type ByIndex struct{ Leaves }

ByIndex implements sort.Interface by providing Less and using Len and Swap methods from the embedded Leaves value.

func (ByIndex) Less

func (s ByIndex) Less(i, j int) bool

Less returns true if i.Index < j.Index

type CompactMerkleTree

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

CompactMerkleTree is a compact Merkle tree representation. Uses log(n) nodes to represent the current on-disk tree.

func NewCompactMerkleTree

func NewCompactMerkleTree(hasher hashers.LogHasher) *CompactMerkleTree

NewCompactMerkleTree creates a new CompactMerkleTree with size zero. This always succeeds.

func NewCompactMerkleTreeWithState

func NewCompactMerkleTreeWithState(hasher hashers.LogHasher, size int64, f GetNodeFunc, expectedRoot []byte) (*CompactMerkleTree, error)

NewCompactMerkleTreeWithState creates a new CompactMerkleTree for the passed in |size|. This can fail if the nodes required to recreate the tree state cannot be fetched or the calculated root hash after population does not match the value we expect. |f| will be called a number of times with the co-ordinates of internal MerkleTree nodes whose hash values are required to initialize the internal state of the CompactMerkleTree. |expectedRoot| is the known-good tree root of the tree at |size|, and is used to verify the correct initial state of the CompactMerkleTree after initialisation.

func (*CompactMerkleTree) AddLeaf

func (c *CompactMerkleTree) AddLeaf(data []byte, f setNodeFunc) (int64, []byte, error)

AddLeaf calculates the leafhash of |data| and appends it to the tree. |f| is a callback which will be called multiple times with the full MerkleTree coordinates of nodes whose hash should be updated.

func (*CompactMerkleTree) AddLeafHash

func (c *CompactMerkleTree) AddLeafHash(leafHash []byte, f setNodeFunc) (int64, error)

AddLeafHash adds the specified |leafHash| to the tree. |f| is a callback which will be called multiple times with the full MerkleTree coordinates of nodes whose hash should be updated.

func (CompactMerkleTree) CurrentRoot

func (c CompactMerkleTree) CurrentRoot() []byte

CurrentRoot returns the current root hash.

func (CompactMerkleTree) Depth

func (c CompactMerkleTree) Depth() int

Depth returns the number of levels in the tree.

func (CompactMerkleTree) DumpNodes

func (c CompactMerkleTree) DumpNodes()

DumpNodes logs the internal state of the CompactMerkleTree, and is used for debugging.

func (CompactMerkleTree) Hashes

func (c CompactMerkleTree) Hashes() [][]byte

Hashes returns a copy of the set of node hashes that comprise the compact representation of the tree.

func (CompactMerkleTree) Size

func (c CompactMerkleTree) Size() int64

Size returns the current size of the tree, that is, the number of leaves ever added to the tree.

type GetNodeFunc

type GetNodeFunc func(depth int, index int64) ([]byte, error)

GetNodeFunc is a function prototype which can look up particular nodes within a non-compact Merkle tree. Used by the CompactMerkleTree to populate itself with correct state when starting up with a non-empty tree.

type HStar2

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

HStar2 is a recursive implementation for calculating the root hash of a sparse Merkle tree.

func NewHStar2

func NewHStar2(treeID int64, hasher hashers.MapHasher) HStar2

NewHStar2 creates a new HStar2 tree calculator based on the passed in MapHasher.

func (*HStar2) HStar2Nodes

func (s *HStar2) HStar2Nodes(prefix []byte, subtreeDepth int, values []HStar2LeafHash,
	get SparseGetNodeFunc, set SparseSetNodeFunc) ([]byte, error)

HStar2Nodes calculates the root hash of a pre-existing sparse Merkle tree plus the extra values passed in. Get and set are used to fetch and store internal node values. Values must not contain multiple leaves for the same index.

prefix is the location of this subtree within the larger tree. Root is at nil. subtreeDepth is the number of levels in this subtree.

func (*HStar2) HStar2Root

func (s *HStar2) HStar2Root(depth int, values []HStar2LeafHash) ([]byte, error)

HStar2Root calculates the root of a sparse Merkle tree of a given depth which contains the given set of non-null leaves.

type HStar2LeafHash

type HStar2LeafHash struct {
	// TODO(al): remove big.Int
	Index    *big.Int
	LeafHash []byte
}

HStar2LeafHash represents a leaf for the HStar2 sparse Merkle tree implementation.

type HashKeyValue

type HashKeyValue struct {
	// HashedKey is the hash of the key data
	HashedKey []byte

	// HashedValue is the hash of the value data.
	HashedValue []byte
}

HashKeyValue represents a Hash(key)-Hash(value) pair.

type InMemoryMerkleTree

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

InMemoryMerkleTree holds a Merkle Tree in memory as a 2D node array

func NewInMemoryMerkleTree

func NewInMemoryMerkleTree(hasher hashers.LogHasher) *InMemoryMerkleTree

NewInMemoryMerkleTree creates a new empty Merkle Tree using the specified Hasher

func (*InMemoryMerkleTree) AddLeaf

func (mt *InMemoryMerkleTree) AddLeaf(leafData []byte) (int64, TreeEntry)

AddLeaf adds a new leaf to the hash tree. Stores the hash of the leaf data in the tree structure, does not store the data itself.

(We will evaluate the tree lazily, and not update the root here.)

Returns the position of the leaf in the tree. Indexing starts at 1, so position = number of leaves in the tree after this update.

func (*InMemoryMerkleTree) CurrentRoot

func (mt *InMemoryMerkleTree) CurrentRoot() TreeEntry

CurrentRoot set the current root of the tree. Updates the root to reflect the current shape of the tree and returns the tree digest.

Returns the hash of an empty string if the tree has no leaves (and hence, no root).

func (*InMemoryMerkleTree) LeafCount

func (mt *InMemoryMerkleTree) LeafCount() int64

LeafCount returns the number of leaves in the tree.

func (*InMemoryMerkleTree) LeafHash

func (mt *InMemoryMerkleTree) LeafHash(leaf int64) []byte

LeafHash returns the hash of the requested leaf.

func (*InMemoryMerkleTree) LevelCount

func (mt *InMemoryMerkleTree) LevelCount() int64

LevelCount returns the number of levels in the current Merkle tree

func (*InMemoryMerkleTree) NodeCount

func (mt *InMemoryMerkleTree) NodeCount(level int64) int64

NodeCount gets the current node count (of the lazily evaluated tree). Caller is responsible for keeping track of the lazy evaluation status. This will not update the tree.

func (*InMemoryMerkleTree) PathToCurrentRoot

func (mt *InMemoryMerkleTree) PathToCurrentRoot(leaf int64) []TreeEntryDescriptor

PathToCurrentRoot get the Merkle path from leaf to root for a given leaf.

Returns a slice of node hashes, ordered by levels from leaf to root. The first element is the sibling of the leaf hash, and the last element is one below the root. Returns an empty slice if the tree is not large enough or the leaf index is 0.

func (*InMemoryMerkleTree) PathToRootAtSnapshot

func (mt *InMemoryMerkleTree) PathToRootAtSnapshot(leaf int64, snapshot int64) []TreeEntryDescriptor

PathToRootAtSnapshot gets the Merkle path from a leaf to the root for a previous snapshot.

Returns a slice of node hashes, ordered by levels from leaf to root. The first element is the sibling of the leaf hash, and the last element is one below the root. Returns an empty slice if the leaf index is 0, the snapshot requested is in the future or the snapshot tree is not large enough.

func (*InMemoryMerkleTree) RootAtSnapshot

func (mt *InMemoryMerkleTree) RootAtSnapshot(snapshot int64) TreeEntry

RootAtSnapshot gets the root of the tree for a previous snapshot, where snapshot 0 is an empty tree, snapshot 1 is the tree with 1 leaf, etc.

Returns an empty string if the snapshot requested is in the future (i.e., the tree is not large enough).

func (*InMemoryMerkleTree) SnapshotConsistency

func (mt *InMemoryMerkleTree) SnapshotConsistency(snapshot1 int64, snapshot2 int64) []TreeEntryDescriptor

SnapshotConsistency gets the Merkle consistency proof between two snapshots. Returns a slice of node hashes, ordered according to levels. Returns an empty slice if snapshot1 is 0, snapshot 1 >= snapshot2, or one of the snapshots requested is in the future.

type Leaves

type Leaves []HStar2LeafHash

Leaves is a slice of HStar2LeafHash

func (Leaves) Len

func (s Leaves) Len() int

Len returns the number of leaves.

func (Leaves) Swap

func (s Leaves) Swap(i, j int)

Swap swaps two leaf locations.

type LogVerifier

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

LogVerifier verifies inclusion and consistency proofs for append only logs.

func NewLogVerifier

func NewLogVerifier(hasher hashers.LogHasher) LogVerifier

NewLogVerifier returns a new LogVerifier for a tree.

func (LogVerifier) RootFromInclusionProof

func (v LogVerifier) RootFromInclusionProof(leafIndex, treeSize int64, proof [][]byte, leafHash []byte) ([]byte, error)

RootFromInclusionProof calculates the expected tree root given the proof and leaf. leafIndex starts at 0. treeSize is the number of nodes in the tree. proof is an array of neighbor nodes from the bottom to the root.

func (LogVerifier) VerifyConsistencyProof

func (v LogVerifier) 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. Snapshots are the respective treeSizes. shapshot2 >= snapshot1 >= 0.

func (LogVerifier) VerifyInclusionProof

func (v LogVerifier) VerifyInclusionProof(leafIndex, treeSize int64, proof [][]byte, root []byte, leafHash []byte) error

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

type NodeFetch

type NodeFetch struct {
	NodeID storage.NodeID
	Rehash bool
}

NodeFetch bundles a nodeID with additional information on how to use the node to construct the correct proof.

func CalcConsistencyProofNodeAddresses

func CalcConsistencyProofNodeAddresses(snapshot1, snapshot2, treeSize int64, maxBitLen int) ([]NodeFetch, error)

CalcConsistencyProofNodeAddresses returns the tree node IDs needed to build a consistency proof between two specified tree sizes. snapshot1 and snapshot2 represent the two tree sizes for which consistency should be proved, treeSize is the actual size of the tree at the revision we are using to fetch nodes (this can be > snapshot2). The maxBitLen parameter is copied into all the returned nodeIDs. The caller is responsible for checking that the input tree sizes correspond to valid tree heads. All returned NodeIDs are tree coordinates within the new tree. It is assumed that they will be fetched from storage at a revision corresponding to the STH associated with the treeSize parameter.

func CalcInclusionProofNodeAddresses

func CalcInclusionProofNodeAddresses(snapshot, index, treeSize int64, maxBitLen int) ([]NodeFetch, error)

CalcInclusionProofNodeAddresses returns the tree node IDs needed to build an inclusion proof for a specified leaf and tree size. The snapshot parameter is the tree size being queried for, treeSize is the actual size of the tree at the revision we are using to fetch nodes (this can be > snapshot). The maxBitLen parameter is copied into all the returned nodeIDs.

func (NodeFetch) Equivalent

func (n NodeFetch) Equivalent(other NodeFetch) bool

Equivalent return true iff the other represents the same rehash state and NodeID as the other.

type RootHashMismatchError

type RootHashMismatchError struct {
	ExpectedHash []byte
	ActualHash   []byte
}

RootHashMismatchError indicates a unexpected root hash value.

func (RootHashMismatchError) Error

func (r RootHashMismatchError) Error() string

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 SparseGetNodeFunc

type SparseGetNodeFunc func(depth int, index *big.Int) ([]byte, error)

SparseGetNodeFunc should return any pre-existing node hash for the node address.

type SparseMerkleTreeReader

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

SparseMerkleTreeReader knows how to read data from a TreeStorage transaction to provide proofs etc.

func NewSparseMerkleTreeReader

func NewSparseMerkleTreeReader(rev int64, h hashers.MapHasher, tx storage.ReadOnlyTreeTX) *SparseMerkleTreeReader

NewSparseMerkleTreeReader returns a new SparseMerkleTreeReader, reading at the specified tree revision, using the passed in MapHasher for calculating and verifying tree hashes read via tx.

func (SparseMerkleTreeReader) InclusionProof

func (s SparseMerkleTreeReader) InclusionProof(ctx context.Context, rev int64, index []byte) ([][]byte, error)

InclusionProof returns an inclusion (or non-inclusion) proof for the specified key at the specified revision. If the revision does not exist it will return ErrNoSuchRevision error.

func (SparseMerkleTreeReader) RootAtRevision

func (s SparseMerkleTreeReader) RootAtRevision(ctx context.Context, rev int64) ([]byte, error)

RootAtRevision returns the sparse Merkle tree root hash at the specified revision, or ErrNoSuchRevision if the requested revision doesn't exist.

type SparseMerkleTreeWriter

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

SparseMerkleTreeWriter knows how to store/update a stored sparse Merkle tree via a TreeStorage transaction.

func NewSparseMerkleTreeWriter

func NewSparseMerkleTreeWriter(ctx context.Context, treeID, rev int64, h hashers.MapHasher, newTX newTXFunc) (*SparseMerkleTreeWriter, error)

NewSparseMerkleTreeWriter returns a new SparseMerkleTreeWriter, which will write data back into the tree at the specified revision, using the passed in MapHasher to calculate/verify tree hashes, storing via tx.

func (*SparseMerkleTreeWriter) CalculateRoot

func (s *SparseMerkleTreeWriter) CalculateRoot() ([]byte, error)

CalculateRoot calculates the new root hash including the newly added leaves.

func (*SparseMerkleTreeWriter) SetLeaves

func (s *SparseMerkleTreeWriter) SetLeaves(ctx context.Context, leaves []HashKeyValue) error

SetLeaves adds a batch of leaves to the in-flight tree update.

type SparseSetNodeFunc

type SparseSetNodeFunc func(depth int, index *big.Int, hash []byte) error

SparseSetNodeFunc should store the passed node hash, associating it with the address.

type Subtree

type Subtree interface {
	// SetLeaf sets a single leaf hash for integration into a sparse Merkle tree.
	SetLeaf(ctx context.Context, index []byte, hash []byte) error

	// CalculateRoot instructs the subtree worker to start calculating the root
	// hash of its tree.  It is an error to call SetLeaf() after calling this
	// method.
	CalculateRoot()

	// RootHash returns the calculated root hash for this subtree, if the root
	// hash has not yet been calculated, this method will block until it is.
	RootHash() ([]byte, error)
}

Subtree is an interface which must be implemented by subtree workers. Currently there's only a locally sharded go-routine based implementation, the the idea is that an RPC based sharding implementation could be created and dropped in.

type TreeEntry

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

TreeEntry is used for nodes in the tree for better readability. Just holds a hash but could be extended

func (TreeEntry) Hash

func (t TreeEntry) Hash() []byte

Hash returns the current hash in a newly created byte slice that the caller owns and may modify.

func (TreeEntry) HashInto

func (t TreeEntry) HashInto(dest []byte) []byte

HashInto returns the current hash in a provided byte slice that the caller may use to make multiple calls to obtain hashes without reallocating memory.

type TreeEntryDescriptor

type TreeEntryDescriptor struct {
	Value  TreeEntry
	XCoord int64 // The horizontal node coordinate
	YCoord int64 // The vertical node coordinate
}

TreeEntryDescriptor wraps a node and is used to describe tree paths, which are useful to have access to when testing the code and examining how it works

Directories

Path Synopsis
Package coniks provides hashing for maps.
Package coniks provides hashing for maps.
Package maphasher provides hashing for maps.
Package maphasher provides hashing for maps.
Package objhasher provides generic object hashing functionality.
Package objhasher provides generic object hashing functionality.
Package rfc6962 provides hashing functionality according to RFC6962.
Package rfc6962 provides hashing functionality according to RFC6962.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL