Documentation
¶
Overview ¶
Package node implements a sparse Merkle tree node.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ID ¶
type ID struct {
// contains filtered or unexported fields
}
ID identifies a node of a Merkle tree. It is a bit string that counts the node down from the tree root, i.e. 0 and 1 bits represent going to the left or right child correspondingly.
ID is immutable, comparable, and can be used as a Golang map key. It also incurs zero memory allocations in transforming methods like Prefix and Sibling.
The internal structure of ID is driven by its use-cases:
- To make ID objects immutable and comparable, the Golang string type is used for storing the bit string bytes.
- To make Sibling and Prefix operations fast, the last byte is stored separately from the rest of the bytes, so that it can be "amended".
- To make ID objects comparable, there is only one (canonical) way to encode an ID. For example, if the last byte is used partially, its unused bits are always unset. See invariants next to field definitions below.
Constructors and methods of ID make sure its invariants are always met.
For example, an 11-bit node ID [1010,1111,001] is structured as follows: - path string contains 1 byte, which is [1010,1111]. - last byte is [0010,0000]. Note the unset lower 5 bits. - bits is 3, so effectively only the upper 3 bits [001] of last are used.
func NewID ¶
NewID creates a node ID from the given path bytes truncated to the specified number of bits if necessary. Panics if the number of bits is more than the byte string contains.
func NewIDWithLast ¶
NewIDWithLast creates a node ID from the given path bytes and the additional last byte, of which only the specified number of most significant bits is used. The number of bits must be between 1 and 8, and can be 0 only if the path bytes string is empty; otherwise the function panics.
func (ID) FullBytes ¶
FullBytes returns the ID bytes that are complete. Note that there might still be up to 8 extra bits, which can be obtained with the LastByte method.
func (ID) LastByte ¶
LastByte returns the terminating byte of the ID, with the number of upper bits that it uses (between 1 and 8, and 0 if the ID is empty). The remaining unused lower bits are always unset.
Source Files