Documentation
¶
Overview ¶
Package compact provides compact Merkle tree data structures.
Index ¶
- func Decompose(begin, end uint64) (uint64, uint64)
- func RangeSize(begin, end uint64) int
- 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 ID consists of a level and index within this level. Levels are numbered from 0, which corresponds to the tree leaves. Within each level, nodes are numbered with consecutive indices starting from 0.
L4: ┌───────0───────┐ ... L3: ┌───0───┐ ┌───1───┐ ┌─── ... L2: ┌─0─┐ ┌─1─┐ ┌─2─┐ ┌─3─┐ ┌─4─┐ ... L1: ┌0┐ ┌1┐ ┌2┐ ┌3┐ ┌4┐ ┌5┐ ┌6┐ ┌7┐ ┌8┐ ┌9┐ ... L0: 0 1 2 3 4 5 6 7 8 9 ... ... ... ... ... ...
When the tree is not perfect, the nodes that would complement it to perfect are called ephemeral. Algorithms that operate with ephemeral nodes still map them to the same address space.
func RangeNodes ¶
RangeNodes appends the IDs of the nodes that comprise the [begin, end) compact range to the given slice, and returns the new slice. The caller may pre-allocate space with the help of the RangeSize function.
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.
For more details, see https://github.com/transparency-dev/merkle/blob/main/docs/compact_ranges.md.
func (*Range) Append ¶
Append extends the compact range by appending the passed in hash to it. It reports all the added nodes 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