proof

Documentation

Overview

Package proof contains helpers for constructing log Merkle tree proofs.

Index

• func RootFromInclusionProof(hasher merkle.LogHasher, index, size uint64, leafHash []byte, proof [][]byte) ([]byte, error)
• func VerifyConsistency(hasher merkle.LogHasher, size1, size2 uint64, proof [][]byte, ...) error
• func VerifyInclusion(hasher merkle.LogHasher, index, size uint64, leafHash []byte, proof [][]byte, ...) error
• type Nodes
  • func Consistency(size1, size2 uint64) (Nodes, error)
  • func Inclusion(index, size uint64) (Nodes, error)
  • func (n Nodes) Ephem() (compact.NodeID, int, int)
  • func (n Nodes) Rehash(h [][]byte, hc func(left, right []byte) []byte) ([][]byte, error)
• type RootMismatchError
  • func (e RootMismatchError) Error() string

Functions

func RootFromInclusionProof

func RootFromInclusionProof(hasher merkle.LogHasher, index, size uint64, leafHash []byte, proof [][]byte) ([]byte, error)

RootFromInclusionProof calculates the expected root hash for a tree of the given size, provided a leaf index and hash with the corresponding inclusion proof. Requires 0 <= index < size.

func VerifyConsistency

func VerifyConsistency(hasher merkle.LogHasher, size1, size2 uint64, proof [][]byte, root1, root2 []byte) error

VerifyConsistency checks that the passed-in consistency proof is valid between the passed in tree sizes, with respect to the corresponding root hashes. Requires 0 <= size1 <= size2.

func VerifyInclusion

func VerifyInclusion(hasher merkle.LogHasher, index, size uint64, leafHash []byte, proof [][]byte, root []byte) error

VerifyInclusion verifies the correctness of the inclusion proof for the leaf with the specified hash and index, relatively to the tree of the given size and root hash. Requires 0 <= index < size.

Types

type Nodes

type Nodes struct {
	// IDs contains the IDs of non-ephemeral nodes sufficient to build the proof.
	// If an ephemeral node is needed for a proof, it can be recomputed based on
	// a subset of nodes in this list.
	IDs []compact.NodeID
	// contains filtered or unexported fields
}

Nodes contains information on how to construct a log Merkle tree proof. It supports any proof that has at most one ephemeral node, such as inclusion and consistency proofs defined in RFC 6962.

func Consistency

func Consistency(size1, size2 uint64) (Nodes, error)

Consistency returns the information on how to fetch and construct a consistency proof between the two given tree sizes of a log Merkle tree. It requires 0 <= size1 <= size2.

func Inclusion

func Inclusion(index, size uint64) (Nodes, error)

Inclusion returns the information on how to fetch and construct an inclusion proof for the given leaf index in a log Merkle tree of the given size. It requires 0 <= index < size.

func (Nodes) Ephem

func (n Nodes) Ephem() (compact.NodeID, int, int)

Ephem returns the ephemeral node, and indices begin and end, such that IDs[begin:end] slice contains the child nodes of the ephemeral node.

The list is empty iff there are no ephemeral nodes in the proof. Some examples of when this can happen: a proof in a perfect tree; an inclusion proof for a leaf in a perfect subtree at the right edge of the tree.

func (Nodes) Rehash

func (n Nodes) Rehash(h [][]byte, hc func(left, right []byte) []byte) ([][]byte, error)

Rehash computes the proof based on the slice of node hashes corresponding to their IDs in the n.IDs field. The slices must be of the same length. The hc parameter computes a node's hash based on hashes of its children.

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

type RootMismatchError

type RootMismatchError struct {
	ExpectedRoot   []byte
	CalculatedRoot []byte
}

RootMismatchError occurs when an inclusion proof fails.

func (RootMismatchError) Error

func (e RootMismatchError) Error() string