merkle

Documentation

Overview

Package merkle provides Merkle tree manipulation functions.

Index

• Variables
• func Rehash(h [][]byte, nf []NodeFetch, hc func(left, right []byte) []byte) ([][]byte, error)
• type ByIndex
  • func (s ByIndex) Less(i, j int) bool
• type HStar2
  • func NewHStar2(treeID int64, hasher hashers.MapHasher) HStar2
  • func (s *HStar2) HStar2Nodes(prefix []byte, subtreeDepth int, values []*HStar2LeafHash, ...) ([]byte, error)
  • func (s *HStar2) HStar2Root(depth int, values []*HStar2LeafHash) ([]byte, error)
  • func (s *HStar2) Prefetch(prefix []byte, subtreeDepth int, values []*HStar2LeafHash, ...) error
• type HStar2LeafHash
• type Leaves
  • func (s Leaves) Len() int
  • func (s Leaves) Swap(i, j int)
• type LogVerifier
  • func NewLogVerifier(hasher hashers.LogHasher) LogVerifier
• type NodeFetch
  • func CalcConsistencyProofNodeAddresses(snapshot1, snapshot2, treeSize int64) ([]NodeFetch, error)
  • func CalcInclusionProofNodeAddresses(snapshot, index, treeSize int64) ([]NodeFetch, error)
• type PrefetchNodeVisitor
• type RootMismatchError
• type SparseGetNodeFunc
• type SparseMerkleTreeReader
  • func NewSparseMerkleTreeReader(rev int64, h hashers.MapHasher, tx storage.ReadOnlyTreeTX) *SparseMerkleTreeReader
  • func (s SparseMerkleTreeReader) BatchInclusionProof(ctx context.Context, rev int64, indices [][]byte) (map[string][][]byte, error)
  • func (s SparseMerkleTreeReader) InclusionProof(ctx context.Context, rev int64, index []byte) ([][]byte, error)
• type SparseSetNodeFunc
• type TXRunner

Variables

var ErrNoSuchRevision = errors.New("no such revision")

ErrNoSuchRevision is returned when a request is made for information about a tree revision which does not exist.

var (
	// ErrSubtreeOverrun indicates that a subtree exceeds the maximum tree depth.
	ErrSubtreeOverrun = errors.New("subtree with prefix exceeds maximum tree size")
)

Functions

func Rehash

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.

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

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 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 = logverifier.LogVerifier

LogVerifier verifies inclusion and consistency proofs for append only logs.

Deprecated: moved to github.com/google/trillian/merkle/logverifier package

func NewLogVerifier

func NewLogVerifier(hasher hashers.LogHasher) LogVerifier

NewLogVerifier returns a new LogVerifier for a tree.

Deprecated: moved to github.com/google/trillian/merkle/logverifier package

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

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

PrefetchNodeVisitor reports coordinates of a Merkle tree node to prefetch.

type RootMismatchError

type RootMismatchError = logverifier.RootMismatchError

RootMismatchError occurs when an inclusion proof fails.

Deprecated: moved to github.com/google/trillian/merkle/logverifier package

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

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

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.