Documentation
¶
Overview ¶
Package compact provides compact Merkle tree data structures.
Deprecated: This package is superseded by the corresponding functionality in https://github.com/transparency-dev/merkle. It will be removed in future releases of Trillian.
Index ¶
- func Decompose(begin, end uint64) (uint64, uint64)
- type HashFn
- type 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
- type VisitFn
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Decompose ¶
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 NodeID ¶
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 RangeNodes ¶
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 ¶
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 ¶
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) GetRootHash ¶
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.
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.
Source Files