package merkletree

import "github.com/google/certificate-transparency-go/merkletree"

Package merkletree holds code to manipulate Merkle trees.

Index ¶

• Constants
• type FullMerkleTreeInterface
• type HasherFunc
• type MerkleTreeInterface
• type MerkleVerifier
• func NewMerkleVerifier(h HasherFunc) MerkleVerifier
• func (m MerkleVerifier) RootFromInclusionProof(leafIndex, treeSize int64, proof [][]byte, leaf []byte) ([]byte, error)
• func (m MerkleVerifier) VerifyConsistencyProof(snapshot1, snapshot2 int64, root1, root2 []byte, proof [][]byte) error
• func (m MerkleVerifier) VerifyInclusionProof(leafIndex, treeSize int64, proof [][]byte, root []byte, leaf []byte) error
• type RootMismatchError
• func (e RootMismatchError) Error() string
• type TreeHasher
• func NewTreeHasher(h HasherFunc) *TreeHasher
• func (h TreeHasher) HashChildren(left, right []byte) []byte
• func (h TreeHasher) HashEmpty() []byte
• func (h TreeHasher) HashLeaf(leaf []byte) []byte

Constants ¶

const (
	// LeafPrefix is the domain separation prefix for leaf hashes.
	LeafPrefix = 0

	// NodePrefix is the domain separation prefix for internal tree nodes.
	NodePrefix = 1
)

Types ¶

type FullMerkleTreeInterface ¶

type FullMerkleTreeInterface interface {
	MerkleTreeInterface

	// RootAtSnapshot returns the root hash at the tree size |snapshot|
	// which must be <= than the current tree size.
	RootAtSnapshot(snapshot uint64) ([]byte, error)

	// PathToCurrentRoot returns the Merkle path (or inclusion proof) from the
	// leaf hash at index |leaf| to the current root.
	PathToCurrentRoot(leaf uint64) ([]byte, error)

	// SnapshotConsistency returns a consistency proof between the two tree
	// sizes specified in |snapshot1| and |snapshot2|.
	SnapshotConsistency(snapshot1, snapshot2 uint64) ([]byte, error)
}

FullMerkleTreeInterface extends MerkleTreeInterface to the full range of operations that only a non-compact tree representation can implement.

type HasherFunc ¶

type HasherFunc func([]byte) []byte

HasherFunc takes a slice of bytes and returns a cryptographic hash of those bytes.

type MerkleTreeInterface ¶

type MerkleTreeInterface interface {
	// LeafCount returns the number of leaves in the tree
	LeafCount() uint64

	// LevelCount returns the number of levels in the tree
	LevelCount() uint64

	// AddLeaf adds the hash of |leaf| to the tree and returns the newly added
	// leaf index
	AddLeaf(leaf []byte) uint64

	// LeafHash returns the hash of the leaf at index |leaf| or a non-nil error.
	LeafHash(leaf uint64) ([]byte, error)

	// CurrentRoot returns the current root hash of the merkle tree.
	CurrentRoot() ([]byte, error)
}

MerkleTreeInterface represents the common interface for basic MerkleTree functions.

type MerkleVerifier ¶

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

MerkleVerifier is a class which knows how to verify merkle inclusion and consistency proofs.

func NewMerkleVerifier ¶

func NewMerkleVerifier(h HasherFunc) MerkleVerifier

NewMerkleVerifier returns a new MerkleVerifier for a tree based on the passed in hasher.

func (MerkleVerifier) RootFromInclusionProof ¶

func (m MerkleVerifier) RootFromInclusionProof(leafIndex, treeSize int64, proof [][]byte, leaf []byte) ([]byte, error)

RootFromInclusionProof calculates the expected tree root given the proof and leaf. leafIndex starts at 0. treeSize starts at 1.

func (MerkleVerifier) VerifyConsistencyProof ¶

func (m MerkleVerifier) 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.

func (MerkleVerifier) VerifyInclusionProof ¶

func (m MerkleVerifier) VerifyInclusionProof(leafIndex, treeSize int64, proof [][]byte, root []byte, leaf []byte) error

VerifyInclusionProof verifies the correctness of the proof given the passed in information about the tree and leaf.

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

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

TreeHasher performs the various hashing operations required when manipulating MerkleTrees.

func NewTreeHasher ¶

func NewTreeHasher(h HasherFunc) *TreeHasher

NewTreeHasher returns a new TreeHasher based on the passed in hash.

func (TreeHasher) HashChildren ¶

func (h TreeHasher) HashChildren(left, right []byte) []byte

HashChildren returns the merkle hash of the two passed in children.

func (TreeHasher) HashEmpty ¶

func (h TreeHasher) HashEmpty() []byte

HashEmpty returns the hash of the empty string.

func (TreeHasher) HashLeaf ¶

func (h TreeHasher) HashLeaf(leaf []byte) []byte

HashLeaf returns the hash of the passed in leaf, after applying domain separation.

Source Files ¶

merkle_tree_interface.go merkle_verifier.go tree_hasher.go