merkle

package
v1.3.10 Latest Latest
Warning

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

 Go to latest Published: Jul 2, 2020 License: Apache-2.0 Imports: 16 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 Rehash added in v1.3.10 

func Rehash(h [][]byte, nf []NodeFetch, hc func(left, right []byte) []byte) ([][]byte, error)

Rehash computes the proof based on the slice of NodeFetch structs, and the corresponding hashes of these nodes. The slices must be of the same length. The hc parameter computes node's hash based on hashes of its children.

Warning: The passed-in slice of hashes can be modified in-place.

func VerifyMapInclusionProof 

func VerifyMapInclusionProof(treeID int64, leaf *trillian.MapLeaf, 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 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.

func (*HStar2) Prefetch added in v1.3.4 

func (s *HStar2) Prefetch(prefix []byte, subtreeDepth int, values []*HStar2LeafHash, visit PrefetchNodeVisitor) error

Prefetch does a dry run of HStar2 algorithm, and reports all Merkle tree nodes that it needs through the passed-in visit function.

This function can be useful, for example, if the caller prefers to collect the node IDs and read them from storage in one batch. Then they can run HStar2Nodes in such a way that it reads from the prefetched set.

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 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, or nil if it doesn't exist.

func (*InMemoryMerkleTree) LevelCount 

func (mt *InMemoryMerkleTree) LevelCount() int64

LevelCount returns the number of levels in the 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, snapshot1 >= 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 {
	ID     compact.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) ([]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 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.

Use Rehash function to compose the proof after the node hashes are fetched.

func CalcInclusionProofNodeAddresses 

func CalcInclusionProofNodeAddresses(snapshot, index, treeSize int64) ([]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).

Use Rehash function to compose the proof after the node hashes are fetched.

type PrefetchNodeVisitor added in v1.3.4 

type PrefetchNodeVisitor func(depth int, index *big.Int)

PrefetchNodeVisitor reports coordinates of a Merkle tree node to prefetch.

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) BatchInclusionProof added in v1.3.0 

func (s SparseMerkleTreeReader) BatchInclusionProof(ctx context.Context, rev int64, indices [][]byte) (map[string][][]byte, error)

BatchInclusionProof returns an inclusion (or non-inclusion) proof for each of the specified keys at the specified revision. The return value is a map of the string form of the key to the inclusion proof for that key.

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.

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 TXRunner added in v1.3.0 

type TXRunner interface {
	// RunTX executes f and supplies a transaction object to operate on.
	RunTX(ctx context.Context, f func(context.Context, storage.MapTreeTX) error) error
}

TXRunner supplies the RunTX function. TXRunner can be passed as the last argument to MapStorage.ReadWriteTransaction.

TODO(pavelkalinnikov): This interface violates layering, because it assumes existence of transactions. It must be part of the storage package.

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 compact provides compact Merkle tree data structures.
 Package compact provides compact Merkle tree data structures.
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 rfc6962 provides hashing functionality according to RFC6962.
 Package rfc6962 provides hashing functionality according to RFC6962.
Package smt contains the implementation of the sparse Merkle tree logic.
 Package smt contains the implementation of the sparse Merkle tree logic.
Package testonly contains code and data for testing Merkle trees.
 Package testonly contains code and data for testing Merkle trees.

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.