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:
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.
func RangeSize(begin, end uint64) int
RangeSize returns the number of nodes in the [begin, end) compact range.
HashFn computes an internal node's hash using the hashes of its child nodes.
type HashFn func(left, right []byte) []byte
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.
type NodeID struct {
Level uint
Index uint64
}
func NewNodeID(level uint, index uint64) NodeID
NewNodeID returns a NodeID with the passed in node coordinates.
func RangeNodes(begin, end uint64, ids []NodeID) []NodeID
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.
func (id NodeID) Coverage() (uint64, uint64)
Coverage returns the [begin, end) range of leaves covered by the node.
func (id NodeID) Parent() NodeID
Parent returns the ID of the parent node.
func (id NodeID) Sibling() NodeID
Sibling returns the ID of the sibling node.
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.
type Range struct {
// contains filtered or unexported fields
}
func (r *Range) Append(hash []byte, visitor VisitFn) error
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 (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 (r *Range) Begin() uint64
Begin returns the first index covered by the range (inclusive).
func (r *Range) End() uint64
End returns the last index covered by the range (exclusive).
func (r *Range) Equal(other *Range) bool
Equal compares two Ranges for equality.
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 (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.
RangeFactory allows creating compact ranges with the specified hash function, which must not be nil, and must not be changed.
type RangeFactory struct {
Hash HashFn
}
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 (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.
VisitFn visits the node with the specified ID and hash.
type VisitFn func(id NodeID, hash []byte)