package compact
import "github.com/transparency-dev/merkle/compact"
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
- func NewNodeID(level uint, index uint64) NodeID
- func RangeNodes(begin, end uint64, ids []NodeID) []NodeID
- func (id NodeID) Coverage() (uint64, uint64)
- func (id NodeID) Parent() NodeID
- func (id NodeID) Sibling() 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 ¶
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.
func RangeSize ¶
RangeSize returns the number of nodes in the [begin, end) compact range.
Types ¶
type HashFn ¶
HashFn computes an internal node's hash using the hashes of its child nodes.
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 NewNodeID ¶
NewNodeID returns a NodeID with the passed in node coordinates.
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.
func (NodeID) Coverage ¶
Coverage returns the [begin, end) range of leaves covered by the node.
func (NodeID) Parent ¶
Parent returns the ID of the parent node.
func (NodeID) Sibling ¶
Sibling returns the ID of the sibling node.
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) Begin ¶
Begin returns the first index covered by the range (inclusive).
func (*Range) End ¶
End returns the last index covered by the range (exclusive).
func (*Range) Equal ¶
Equal compares two Ranges for equality.
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.
func (*Range) Hashes ¶
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 ¶
VisitFn visits the node with the specified ID and hash.
Source Files ¶
- Version
- v0.0.2 (latest)
- Published
- May 5, 2023
- Platform
- linux/amd64
- Imports
- 4 packages
- Last checked
- 4 days ago –
Tools for package owners.