compact

Documentation

Overview

Package compact provides compact Merkle tree data structures.

Index

• func Decompose(begin, end uint64) (uint64, uint64)
• type HashFn
• type NodeID
  • func NewNodeID(level uint, index uint64) NodeID
  • func RangeNodes(begin, end uint64) []NodeID
• type Range
  • func (r *Range) Append(hash []byte, visitor VisitFn) error
  • func (r *Range) AppendRange(other *Range, visitor VisitFn) error
  • func (r *Range) Begin() uint64
  • func (r *Range) End() uint64
  • func (r *Range) Equal(other *Range) bool
  • func (r *Range) GetRootHash(visitor VisitFn) ([]byte, error)
  • func (r *Range) Hashes() [][]byte
• type RangeFactory
  • func (f *RangeFactory) NewEmptyRange(begin uint64) *Range
  • func (f *RangeFactory) NewRange(begin, end uint64, hashes [][]byte) (*Range, error)
• type VisitFn

Functions

func Decompose

func Decompose(begin, end uint64) (uint64, uint64)

Decompose splits the [begin, end) range into a minimal number of sub-ranges, each of which is of the form [m * 2^k, (m+1) * 2^k), i.e. of length 2^k, for some integers m, k >= 0.

The sequence of sizes is returned encoded as bitmasks left and right, where:

• a 1 bit in a bitmask denotes a sub-range of the corresponding size 2^k
• left mask bits in LSB-to-MSB order encode the left part of the sequence
• right mask bits in MSB-to-LSB order encode the right part

The corresponding values of m are not returned (they can be calculated from begin and the sub-range sizes).

For example, (begin, end) values of (0b110, 0b11101) would indicate a sequence of tree sizes: 2,8; 8,4,1.

The output is not specified if begin > end, but the function never panics.

Types

type HashFn

type HashFn func(left, right []byte) []byte

HashFn computes an internal node's hash using the hashes of its child nodes.

type NodeID

type NodeID struct {
	Level uint
	Index uint64
}

NodeID identifies a node of a Merkle tree.

The level is the longest distance from the node down to the leaves, and index is its horizontal position in this level ordered from left to right. Consider an example below where nodes are labeled as [<level> <index>].

        [2 0]
       /     \
    [1 0]     \
    /   \      \
[0 0]  [0 1]  [0 2]

func NewNodeID

func NewNodeID(level uint, index uint64) NodeID

NewNodeID returns a NodeID with the passed in node coordinates.

func RangeNodes

func RangeNodes(begin, end uint64) []NodeID

RangeNodes returns node IDs that comprise the [begin, end) compact range.

type Range

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

Range represents a compact Merkle tree range for leaf indices [begin, end).

It contains the minimal set of perfect subtrees whose leaves comprise this range. The structure is efficiently mergeable with other compact ranges that share one of the endpoints with it.

TODO(pavelkalinnikov): Add document with more details on how it works, and what it can be used for.

func (*Range) Append

func (r *Range) Append(hash []byte, visitor VisitFn) error

Append extends the compact range by appending the passed in hash to it. It uses the tree hasher to calculate hashes of newly created nodes, and reports them through the visitor function (if non-nil).

func (*Range) AppendRange

func (r *Range) AppendRange(other *Range, visitor VisitFn) error

AppendRange extends the compact range by merging in the other compact range from the right. It uses the tree hasher to calculate hashes of newly created nodes, and reports them through the visitor function (if non-nil).

func (*Range) Begin

func (r *Range) Begin() uint64

Begin returns the first index covered by the range (inclusive).

func (*Range) End

func (r *Range) End() uint64

End returns the last index covered by the range (exclusive).

func (*Range) Equal

func (r *Range) Equal(other *Range) bool

Equal compares two Ranges for equality.

func (*Range) GetRootHash

func (r *Range) GetRootHash(visitor VisitFn) ([]byte, error)

GetRootHash returns the root hash of the Merkle tree represented by this compact range. Requires the range to start at index 0. If the range is empty, returns nil.

If visitor is not nil, it is called with all "ephemeral" nodes (i.e. the ones rooting imperfect subtrees) along the right border of the tree.

func (*Range) Hashes

func (r *Range) Hashes() [][]byte

Hashes returns sub-tree hashes corresponding to the minimal set of perfect sub-trees covering the [begin, end) range, ordered left to right.

type RangeFactory

type RangeFactory struct {
	Hash HashFn
}

RangeFactory allows creating compact ranges with the specified hash function, which must not be nil, and must not be changed.

func (*RangeFactory) NewEmptyRange

func (f *RangeFactory) NewEmptyRange(begin uint64) *Range

NewEmptyRange returns a new Range for an empty [begin, begin) range. The value of begin defines where the range will start growing from when entries are appended to it.

func (*RangeFactory) NewRange

func (f *RangeFactory) NewRange(begin, end uint64, hashes [][]byte) (*Range, error)

NewRange creates a Range for [begin, end) with the given set of hashes. The hashes correspond to the roots of the minimal set of perfect sub-trees covering the [begin, end) leaves range, ordered left to right.

type VisitFn

type VisitFn func(id NodeID, hash []byte)

VisitFn visits the node with the specified ID and hash.