merkle

package
v1.2.1 Latest Latest
Warning

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

 Go to latest Published: Aug 16, 2018 License: Apache-2.0 Imports: 15 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, error)

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) VerifiedPrefixHashFromInclusionProof added in v1.1.1 

func (v LogVerifier) VerifiedPrefixHashFromInclusionProof(
	subSize, size int64,
	proof [][]byte, root []byte, leafHash []byte,
) ([]byte, error)

VerifiedPrefixHashFromInclusionProof calculates a root hash over leaves [0..subSize), based on the inclusion |proof| and |leafHash| for a leaf at index |subSize-1| in a tree of the specified |size| with the passed in |root| hash. Returns an error if the |proof| verification fails. The resulting smaller tree's root hash is trusted iff the bigger tree's |root| hash is trusted.

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 tree sizes. Accepts 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, runTX runTXFunc) (*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

Source Files

View all Source files

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
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.