merkle

Documentation

Overview

package merkle provides hashing operations that can be used to verify a Sigsum log's Merkle tree. The exact hash strategy is defined in RFC 6962.

Index

• func HashEmptyTree() crypto.Hash
• func HashInteriorNode(left, right *crypto.Hash) crypto.Hash
• func HashLeafNode(leaf []byte) crypto.Hash
• func VerifyConsistency(oldSize, newSize uint64, oldRoot, newRoot *crypto.Hash, path []crypto.Hash) error
• func VerifyInclusion(leaf *crypto.Hash, index, size uint64, root *crypto.Hash, path []crypto.Hash) error
• func VerifyInclusionBatch(leaves []crypto.Hash, fn, size uint64, root *crypto.Hash, ...) error
• func VerifyInclusionTail(leaves []crypto.Hash, fn uint64, root *crypto.Hash, path []crypto.Hash) error
• type Prefix
• type Tree
  • func NewTree() Tree
  • func (t *Tree) AddLeafHash(leafHash *crypto.Hash) bool
  • func (t *Tree) GetLeafIndex(leafHash *crypto.Hash) (uint64, error)
  • func (t *Tree) GetRootHash() crypto.Hash
  • func (t *Tree) ProveConsistency(m, n uint64) ([]crypto.Hash, error)
  • func (t *Tree) ProveInclusion(index, size uint64) ([]crypto.Hash, error)
  • func (t *Tree) Size() uint64

Functions

func HashEmptyTree

func HashEmptyTree() crypto.Hash

func HashInteriorNode

func HashInteriorNode(left, right *crypto.Hash) crypto.Hash

func HashLeafNode

func HashLeafNode(leaf []byte) crypto.Hash

func VerifyConsistency

func VerifyConsistency(oldSize, newSize uint64, oldRoot, newRoot *crypto.Hash, path []crypto.Hash) error

VerifyConsistency verifies that a Merkle tree is consistent. The algorithm used is in RFC 9162, §2.1.4.2. It is the same proof technique as RFC 6962.

func VerifyInclusion

func VerifyInclusion(leaf *crypto.Hash, index, size uint64, root *crypto.Hash, path []crypto.Hash) error

VerifyInclusion verifies that something is in a Merkle tree. The algorithm used is equivalent to the one in in RFC 9162, §2.1.3.2. Note that with index == 0, size == 1, the empty path is considered a valid inclusion proof, and inclusion means that *leaf == *root.

func VerifyInclusionBatch

func VerifyInclusionBatch(leaves []crypto.Hash, fn, size uint64, root *crypto.Hash, startPath []crypto.Hash, endPath []crypto.Hash) error

VerifyBatchInclusion verifies a consecutive sequence of leaves are included in a Merkle tree. The algorithm is an extension of the inclusion proof in RFC 9162, §2.1.3.2, using inclusion proofs for the first and last (inclusive) leaves in the sequence.

func VerifyInclusionTail

func VerifyInclusionTail(leaves []crypto.Hash, fn uint64, root *crypto.Hash, path []crypto.Hash) error

Verifies inclusion of all the leaves, to a root hash corresponding to size index + len(leaves).

Types

type Prefix

type Prefix uint8

const (
	PrefixLeafNode Prefix = iota
	PrefixInteriorNode
)

type Tree

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

Represents a tree of leaf hashes. Not concurrency safe; needs external synchronization.

func NewTree

func NewTree() Tree

func (*Tree) AddLeafHash

func (t *Tree) AddLeafHash(leafHash *crypto.Hash) bool

Returns true if added, false for duplicates.

func (*Tree) GetLeafIndex

func (t *Tree) GetLeafIndex(leafHash *crypto.Hash) (uint64, error)

func (*Tree) GetRootHash

func (t *Tree) GetRootHash() crypto.Hash

func (*Tree) ProveConsistency

func (t *Tree) ProveConsistency(m, n uint64) ([]crypto.Hash, error)

func (*Tree) ProveInclusion

func (t *Tree) ProveInclusion(index, size uint64) ([]crypto.Hash, error)

func (*Tree) Size

func (t *Tree) Size() uint64