tree

package
v1.3.13 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Feb 16, 2021 License: Apache-2.0 Imports: 11 Imported by: 1

Documentation

Overview

Package tree defines types that help navigating a tree in storage.

Index

Constants

This section is empty.

Variables

View Source
var (
	// EmptySuffix is a reusable suffix of zero bits. To avoid special cases
	// there is a single byte path attached to it and there is no way to create
	// a Suffix with a nil or empty path.
	EmptySuffix = NewSuffix(0, []byte{0})
)

Functions

This section is empty.

Types

type Layout

type Layout struct {

	// Height is the height of the tree. It defines the maximal bit-length of a
	// node ID that the tree can contain.
	Height int
	// contains filtered or unexported fields
}

Layout defines the mapping between tree node IDs and tile IDs.

func NewLayout

func NewLayout(heights []int) *Layout

NewLayout creates a tree layout based on the passed-in strata heights.

func (*Layout) GetTileID

func (l *Layout) GetTileID(id NodeID) TileID

GetTileID returns the ID of the tile that the given node belongs to.

Note that nodes located at strata boundaries normally belong to tiles rooted above them. However, the topmost node (with an empty NodeID) is the root for its own tile since there is nothing above it.

func (*Layout) GetTileRootID added in v1.3.6

func (l *Layout) GetTileRootID(id NodeID2) NodeID2

GetTileRootID returns the ID for the root of the tile that the node with the given ID belongs to.

func (*Layout) Split

func (l *Layout) Split(id NodeID) (TileID, *Suffix)

Split returns the ID of the that the given node belongs to, and the corresponding local address within this tile.

func (*Layout) TileHeight added in v1.3.5

func (l *Layout) TileHeight(rootDepth int) int

TileHeight returns the height of a tile with its root located at the specified depth from the tree root. The result is not defined if rootDepth is not a tile boundary.

TODO(pavelkalinnikov, v2): Use "type-safe" structured argument like NodeID2.

type Node

type Node struct {
	NodeID       NodeID
	Hash         []byte
	NodeRevision int64
}

Node represents a single node in a Merkle tree.

type NodeID

type NodeID struct {
	// Path is effectively a BigEndian bit set, with the MSB of Path[0]
	// identifying the root child, and successive bits identifying the lower
	// level children down to the leaf.
	Path []byte
	// PrefixLenBits is the number of significant bits in Path, which are
	// considered part of this NodeID.
	//
	// e.g. if Path contains two bytes, and PrefixLenBits is 9, then the 8 bits
	// in Path[0] are included, along with the MSB of Path[1]. The remaining
	// 7 bits are not significant.
	PrefixLenBits int
}

NodeID is an identifier of a Merkle tree Node. A default constructed NodeID is an empty ID representing the root of a (sub-)tree. The type is designed to be immutable, so the public fields should not be modified.

Reading paths right to left is the natural order when traversing from leaves towards the root. However, for internal nodes the rightmost bits of the IDs are not aligned on a byte boundary so care must be taken.

NodeIDs as presented to the storage layer will always have a multiple of 8 bits as they identify the root of a 256 element subtree.

Note that some of the APIs count bits with 0 being the rightmost in the entire path array when some of these might not be significant.

See the types.go file that defines this type for more detailed information and docs/storage for how they are used in the on-disk representation of Merkle trees.

TODO(pavelkalinnikov, v2): To be removed in the next major version.

func NewNodeIDForTreeCoords

func NewNodeIDForTreeCoords(depth int64, index int64, maxPathBits int) (NodeID, error)

NewNodeIDForTreeCoords creates a new NodeID for a Tree node with a specified depth and index. This method is used exclusively by the Log, and, since the Log model grows upwards from the leaves, we modify the provided coords accordingly.

depth is the Merkle tree level: 0 = leaves, and increases upwards towards the root.

index is the horizontal index into the tree at level depth, so the returned NodeID will be zero padded on the right by depth places.

func NewNodeIDFromBigInt

func NewNodeIDFromBigInt(depth int, index *big.Int, totalDepth int) NodeID

NewNodeIDFromBigInt creates a new node for a given depth and index, where the index can exceed a 64-bit range. The total tree depth must be provided. This occurs in the sparse Merkle tree implementation for maps as the lower levels have up 2^(hash size) entries. For log trees see NewNodeIDForTreeCoords.

func NewNodeIDFromHash

func NewNodeIDFromHash(h []byte) NodeID

NewNodeIDFromHash creates a new NodeID for the given Hash.

func NewNodeIDFromID2

func NewNodeIDFromID2(id NodeID2) NodeID

NewNodeIDFromID2 constructs a NodeID from a NodeID2.

func NewNodeIDFromPrefix

func NewNodeIDFromPrefix(prefix []byte, depth int, index int64, subDepth, totalDepth int) NodeID

NewNodeIDFromPrefix returns a nodeID for a particular node within a subtree. Prefix is the prefix of the subtree. depth is the depth of index from the root of the subtree. index is the horizontal location of the subtree leaf. subDepth is the total number of levels in the subtree. totalDepth is the number of levels in the whole tree.

func NewNodeIDFromPrefixSuffix

func NewNodeIDFromPrefixSuffix(prefix []byte, suffix *Suffix, maxPathBits int) NodeID

NewNodeIDFromPrefixSuffix undoes Split() and returns the NodeID.

func (NodeID) AsKey

func (n NodeID) AsKey() string

AsKey returns a string identifier for this NodeID suitable for short term use e.g. as a Map key. It is more efficient to use this than String() as it's not constrained to return a binary string.

func (NodeID) BigInt

func (n NodeID) BigInt() *big.Int

BigInt returns the big.Int for this node.

func (NodeID) Bit

func (n NodeID) Bit(i int) uint

Bit returns 1 if the zero indexed ith bit from the right (of the whole path array, not just the significant portion) is true, and false otherwise.

func (NodeID) CoordString

func (n NodeID) CoordString() string

CoordString returns a string representation assuming that the NodeID represents a tree coordinate. Using this on a NodeID for a sparse Merkle tree will give incorrect results. Intended for debugging purposes, the format could change.

func (NodeID) Copy

func (n NodeID) Copy() NodeID

Copy returns a duplicate of NodeID.

func (NodeID) Equivalent

func (n NodeID) Equivalent(other NodeID) bool

Equivalent return true iff the other represents the same path prefix as this NodeID.

func (NodeID) MaskLeft

func (n NodeID) MaskLeft(depth int) NodeID

MaskLeft returns a new copy of NodeID with only the left n bits set.

func (NodeID) Neighbor

func (n NodeID) Neighbor(depth int) NodeID

Neighbor returns a new copy of a node, applying a LeftMask operation and with the bit at PrefixLenBits in the copy flipped. In terms of a tree traversal, this is the parent node's other child node in the binary tree (often termed sibling node).

func (NodeID) PathLenBits

func (n NodeID) PathLenBits() int

PathLenBits returns 8 * len(path).

func (NodeID) Prefix

func (n NodeID) Prefix(prefixBytes int) []byte

Prefix returns a copy of NodeID's prefix. This is the same value that would be returned from Split, but without the overhead of calculating the suffix too.

func (NodeID) PrefixAsKey

func (n NodeID) PrefixAsKey(prefixBytes int) string

PrefixAsKey returns a NodeID's prefix in a format suitable for use as a map key. This is the same value that would be returned from Split, but without the overhead of calculating the suffix too.

func (NodeID) Siblings

func (n NodeID) Siblings() []NodeID

Siblings returns the siblings of the given node. In terms of a tree traversal, this returns the Neighbour() of every node (including this one) on the path up to the root. The array is of length PrefixLenBits and is ordered such that the nodes closest to the leaves are earlier in the array. These nodes are the ones that would be required for a Merkle tree inclusion proof for this node.

func (NodeID) Split

func (n NodeID) Split(prefixBytes, suffixBits int) ([]byte, *Suffix)

Split splits a NodeID into a prefix and a suffix at prefixBytes. The returned prefix is a copy of the underlying bytes.

func (NodeID) String

func (n NodeID) String() string

String returns a string representation of the binary value of the NodeID. The left-most bit is the MSB (i.e. nearer the root of the tree). The length of the returned string will always be the same as the prefix length of the node. For a string ID to use as a map key see AsKey().

func (NodeID) Suffix

func (n NodeID) Suffix(prefixBytes, suffixBits int) *Suffix

Suffix returns a Node's suffix starting at prefixBytes. This is the same Suffix that Split() would return, just without the overhead of also creating the prefix.

func (NodeID) ToNodeID2

func (n NodeID) ToNodeID2() NodeID2

ToNodeID2 converts the ID to NodeID2.

type NodeID2

type NodeID2 struct {
	// contains filtered or unexported fields
}

NodeID2 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.

NodeID2 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 NodeID2 is driven by its use-cases:

  • To make NodeID2 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 NodeID2 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 NodeID2 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.

TODO(pavelkalinnikov, v2): Replace NodeID with this type.

func NewNodeID2

func NewNodeID2(path string, bits uint) NodeID2

NewNodeID2 creates a NodeID2 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 NewNodeID2WithLast added in v1.3.5

func NewNodeID2WithLast(path string, last byte, bits uint8) NodeID2

NewNodeID2WithLast creates a NodeID2 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 (NodeID2) BitLen

func (n NodeID2) BitLen() uint

BitLen returns the length of the NodeID2 in bits.

func (NodeID2) FullBytes

func (n NodeID2) 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 (NodeID2) LastByte

func (n NodeID2) 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 (NodeID2) Prefix

func (n NodeID2) Prefix(bits uint) NodeID2

Prefix returns the prefix of NodeID2 with the given number of bits.

func (NodeID2) Sibling

func (n NodeID2) Sibling() NodeID2

Sibling returns the NodeID2 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 (NodeID2) String

func (n NodeID2) String() string

String returns a human-readable bit string.

type Suffix

type Suffix struct {
	// contains filtered or unexported fields
}

Suffix represents the tail of a NodeID. It is the path within the subtree. The portion of the path that extends beyond the subtree is not part of this suffix. We keep a cache of the Suffix values use by log trees, which will have a depth between 1 and 8 bits. These are reused to avoid constant reallocation and base64 conversion overhead.

TODO(pavelkalinnikov, v2): This type is specific to SubtreeProto. Move it.

func NewSuffix

func NewSuffix(bits uint8, path []byte) *Suffix

NewSuffix creates a new Suffix. The primary use for them is to get their String value to use as a key so we compute that once up front.

TODO(pavelkalinnikov): Mask the last byte of path.

func ParseSuffix

func ParseSuffix(s string) (*Suffix, error)

ParseSuffix converts a suffix string back into a Suffix.

func (Suffix) Bits

func (s Suffix) Bits() uint8

Bits returns the number of significant bits in the Suffix path.

func (Suffix) Path

func (s Suffix) Path() []byte

Path returns a copy of the Suffix path.

func (Suffix) String

func (s Suffix) String() string

String returns a string that represents Suffix. This is a base64 encoding of the following format: [ 1 byte for depth || path bytes ]

type TileID

type TileID struct {
	Root NodeID
}

TileID holds the ID of a tile, which is aligned with the tree layout.

It assumes that strata heights are multiples of 8, and so the byte representation of the TileID matches NodeID.

func (TileID) AsBytes

func (t TileID) AsBytes() []byte

AsBytes returns the ID as a byte slice suitable for passing in to the storage layer. The returned bytes must not be modified.

func (TileID) AsKey

func (t TileID) AsKey() string

AsKey returns the ID as a string suitable for in-memory mapping.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL