merkle

README

Files in this package were copied from Google's (Apache-licensed) Trillian package (github.com/google/trillian)
and modified by us to avoid needing to import the entire trillian package

Documentation

Overview

Package merkle provides Merkle tree manipulation functions.

Index

• Constants
• Variables
• func Order(a, b []byte) bool
• func Root(leaves [][]byte) crypto.Digest
• type Hasher
  • func New(h crypto.Hash) *Hasher
  • func (t *Hasher) EmptyRoot() []byte
  • func (t *Hasher) HashChildren(l, r []byte) []byte
  • func (t *Hasher) HashLeaf(leaf []byte) ([]byte, error)
• type InMemoryMerkleTree
  • func NewInMemoryMerkleTree(hasher hashers.LogHasher) *InMemoryMerkleTree
  • func (mt *InMemoryMerkleTree) AddLeaf(leafData []byte) (int64, TreeEntry, error)
  • func (mt *InMemoryMerkleTree) CurrentRoot() TreeEntry
  • func (mt *InMemoryMerkleTree) LeafCount() int64
  • func (mt *InMemoryMerkleTree) LeafHash(leaf int64) []byte
  • func (mt *InMemoryMerkleTree) LevelCount() int64
  • func (mt *InMemoryMerkleTree) NodeCount(level int64) int64
  • func (mt *InMemoryMerkleTree) PathToCurrentRoot(leaf int64) []TreeEntryDescriptor
  • func (mt *InMemoryMerkleTree) PathToRootAtSnapshot(leaf int64, snapshot int64) []TreeEntryDescriptor
  • func (mt *InMemoryMerkleTree) RootAtSnapshot(snapshot int64) TreeEntry
  • func (mt *InMemoryMerkleTree) SnapshotConsistency(snapshot1 int64, snapshot2 int64) []TreeEntryDescriptor
• type TreeEntry
  • func (t TreeEntry) Hash() []byte
  • func (t TreeEntry) HashInto(dest []byte) []byte
• type TreeEntryDescriptor

Constants

const (
	LeafHashPrefix = 0
	NodeHashPrefix = 1
)

Domain separation prefixes

Variables

var DefaultHasher = New(crypto.SHA256) // XXX TODO make SHA512_256 and update test vectors

DefaultHasher is a SHA512-256 based LogHasher.

Functions

func Order

func Order(a, b []byte) bool

Order returns whether one byte slice is greater than another it returns true if a < b

func Root

func Root(leaves [][]byte) crypto.Digest

Root returns the root of a merkle tree with the leaves given as input

Types

type Hasher

type Hasher struct {
	crypto.Hash
}

Hasher implements the RFC6962 tree hashing algorithm but with SHA512-256 instead of SHA256

func New

func New(h crypto.Hash) *Hasher

New creates a new Hashers.LogHasher on the passed in hash function.

func (*Hasher) EmptyRoot

func (t *Hasher) EmptyRoot() []byte

EmptyRoot returns a special case for an empty tree.

func (*Hasher) HashChildren

func (t *Hasher) HashChildren(l, r []byte) []byte

HashChildren returns the inner Merkle tree node hash of the the two child nodes l and r. The hashed structure is NodeHashPrefix||l||r.

func (*Hasher) HashLeaf

func (t *Hasher) HashLeaf(leaf []byte) ([]byte, error)

HashLeaf returns the Merkle tree leaf hash of the data passed in through leaf. The data in leaf is prefixed by the LeafHashPrefix.

type InMemoryMerkleTree

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

InMemoryMerkleTree holds a Merkle Tree in memory as a 2D node array

func NewInMemoryMerkleTree

func NewInMemoryMerkleTree(hasher hashers.LogHasher) *InMemoryMerkleTree

NewInMemoryMerkleTree creates a new empty Merkle Tree using the specified Hasher

func (*InMemoryMerkleTree) AddLeaf

func (mt *InMemoryMerkleTree) AddLeaf(leafData []byte) (int64, TreeEntry, error)

AddLeaf adds a new leaf to the hash tree. Stores the hash of the leaf data in the tree structure, does not store the data itself.

(We will evaluate the tree lazily, and not update the root here.)

Returns the position of the leaf in the tree. Indexing starts at 1, so position = number of leaves in the tree after this update.

func (*InMemoryMerkleTree) CurrentRoot

func (mt *InMemoryMerkleTree) CurrentRoot() TreeEntry

CurrentRoot set the current root of the tree. Updates the root to reflect the current shape of the tree and returns the tree digest.

Returns the hash of an empty string if the tree has no leaves (and hence, no root).

func (*InMemoryMerkleTree) LeafCount

func (mt *InMemoryMerkleTree) LeafCount() int64

LeafCount returns the number of leaves in the tree.

func (*InMemoryMerkleTree) LeafHash

func (mt *InMemoryMerkleTree) LeafHash(leaf int64) []byte

LeafHash returns the hash of the requested leaf.

func (*InMemoryMerkleTree) LevelCount

func (mt *InMemoryMerkleTree) LevelCount() int64

LevelCount returns the number of levels in the current Merkle tree

func (*InMemoryMerkleTree) NodeCount

func (mt *InMemoryMerkleTree) NodeCount(level int64) int64

NodeCount gets the current node count (of the lazily evaluated tree). Caller is responsible for keeping track of the lazy evaluation status. This will not update the tree.

func (*InMemoryMerkleTree) PathToCurrentRoot

func (mt *InMemoryMerkleTree) PathToCurrentRoot(leaf int64) []TreeEntryDescriptor

PathToCurrentRoot get the Merkle path from leaf to root for a given leaf.

Returns a slice of node hashes, ordered by levels from leaf to root. The first element is the sibling of the leaf hash, and the last element is one below the root. Returns an empty slice if the tree is not large enough or the leaf index is 0.

func (*InMemoryMerkleTree) PathToRootAtSnapshot

func (mt *InMemoryMerkleTree) PathToRootAtSnapshot(leaf int64, snapshot int64) []TreeEntryDescriptor

PathToRootAtSnapshot gets the Merkle path from a leaf to the root for a previous snapshot.

Returns a slice of node hashes, ordered by levels from leaf to root. The first element is the sibling of the leaf hash, and the last element is one below the root. Returns an empty slice if the leaf index is 0, the snapshot requested is in the future or the snapshot tree is not large enough.

func (*InMemoryMerkleTree) RootAtSnapshot

func (mt *InMemoryMerkleTree) RootAtSnapshot(snapshot int64) TreeEntry

RootAtSnapshot gets the root of the tree for a previous snapshot, where snapshot 0 is an empty tree, snapshot 1 is the tree with 1 leaf, etc.

Returns an empty string if the snapshot requested is in the future (i.e., the tree is not large enough).

func (*InMemoryMerkleTree) SnapshotConsistency

func (mt *InMemoryMerkleTree) SnapshotConsistency(snapshot1 int64, snapshot2 int64) []TreeEntryDescriptor

SnapshotConsistency gets the Merkle consistency proof between two snapshots. Returns a slice of node hashes, ordered according to levels. Returns an empty slice if snapshot1 is 0, snapshot 1 >= snapshot2, or one of the snapshots requested is in the future.

type TreeEntry

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

TreeEntry is used for nodes in the tree for better readability. Just holds a hash but could be extended

func (TreeEntry) Hash

func (t TreeEntry) Hash() []byte

Hash returns the current hash in a newly created byte slice that the caller owns and may modify.

func (TreeEntry) HashInto

func (t TreeEntry) HashInto(dest []byte) []byte

HashInto returns the current hash in a provided byte slice that the caller may use to make multiple calls to obtain hashes without reallocating memory.

type TreeEntryDescriptor

type TreeEntryDescriptor struct {
	Value  TreeEntry
	XCoord int64 // The horizontal node coordinate
	YCoord int64 // The vertical node coordinate
}

TreeEntryDescriptor wraps a node and is used to describe tree paths, which are useful to have access to when testing the code and examining how it works