package merkle

import "github.com/google/trillian/merkle"

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, get SparseGetNodeFunc, set SparseSetNodeFunc) ([]byte, error)
• func (s *HStar2) HStar2Root(depth int, values []*HStar2LeafHash) ([]byte, error)
• func (s *HStar2) Prefetch(prefix []byte, subtreeDepth int, values []*HStar2LeafHash, visit PrefetchNodeVisitor) 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 SparseSetNodeFunc

Variables ¶

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 SparseSetNodeFunc ¶

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

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

Source Files ¶

doc.go hstar2.go log_proofs.go log_verifier.go

Directories ¶