package node

import "github.com/google/trillian/merkle/smt/node"

Package node implements a sparse Merkle tree node.

Index ¶

• type ID
• func NewID(path string, bits uint) ID
• func NewIDWithLast(path string, last byte, bits uint8) ID
• func (n ID) BitLen() uint
• func (n ID) FullBytes() string
• func (n ID) LastByte() (byte, uint8)
• func (n ID) Prefix(bits uint) ID
• func (n ID) Sibling() ID
• func (n ID) String() string

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 ¶

func NewID(path string, bits uint) ID

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 ¶

func NewIDWithLast(path string, last byte, bits uint8) ID

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) BitLen ¶

func (n ID) BitLen() uint

BitLen returns the length of the ID in bits.

func (ID) FullBytes ¶

func (n ID) FullBytes() string

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 ¶

func (n ID) LastByte() (byte, uint8)

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.

func (ID) Prefix ¶

func (n ID) Prefix(bits uint) ID

Prefix returns the prefix of the node ID with the given number of bits.

func (ID) Sibling ¶

func (n ID) Sibling() ID

Sibling returns the ID of the nodes's sibling in a binary tree, i.e. the ID of the parent node's other child. If the node is the root then the returned ID is the same.

func (ID) String ¶

func (n ID) String() string

String returns a human-readable bit string.

Source Files ¶

id.go