package inmemory

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

Package inmemory provides an in-memory MerkleTree implementation. It's a fairly direct port of the C++ Merkle Tree from the CT repo; it has the same API and should have similar performance. It is not part of the Trillian API.

Note: this implementation evaluates the root lazily in the same way as the C++ code so some methods that appear to be accessors can cause mutations to update the structure to the necessary point required to obtain the result.

------------------------------------------------------------------------------------------- IMPORTANT NOTE: This code uses 1-based leaf indexing as this is how the original C++ works. There is scope for confusion if it is mixed with the Trillian specific trees in this package, which index leaves starting from zero. This code is primarily meant for use in cross checks of the new implementation and it is advantageous to be able to compare it directly with the C++ code. -------------------------------------------------------------------------------------------

Index

Types

type MerkleTree 

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

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

func NewMerkleTree 

func NewMerkleTree(hasher hashers.LogHasher) *MerkleTree

NewMerkleTree creates a new empty Merkle Tree using the specified Hasher.

func (*MerkleTree) AddLeaf 

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

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 (*MerkleTree) CurrentRoot 

func (mt *MerkleTree) 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 (*MerkleTree) LeafCount 

func (mt *MerkleTree) LeafCount() int64

LeafCount returns the number of leaves in the tree.

func (*MerkleTree) LeafHash 

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

LeafHash returns the hash of the requested leaf, or nil if it doesn't exist.

func (*MerkleTree) LevelCount 

func (mt *MerkleTree) LevelCount() int64

LevelCount returns the number of levels in the Merkle tree.

func (*MerkleTree) NodeCount 

func (mt *MerkleTree) 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 (*MerkleTree) PathToCurrentRoot 

func (mt *MerkleTree) 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 (*MerkleTree) PathToRootAtSnapshot 

func (mt *MerkleTree) 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 (*MerkleTree) RootAtSnapshot 

func (mt *MerkleTree) 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 (*MerkleTree) SnapshotConsistency 

func (mt *MerkleTree) 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, snapshot1 >= 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

Source Files

merkle_tree.go

Version
v1.4.0
Published
Sep 21, 2021
Platform
js/wasm
Imports
3 packages
Last checked
23 minutes ago –

Tools for package owners.