node

Documentation

Index

• type Node
  • func NewInterimCompactifiedNode(height int, lChild, rChild *Node) *Node
  • func NewInterimNode(height int, lchild, rchild *Node) *Node
  • func NewLeaf(path ledger.Path, payload *ledger.Payload, height int) *Node
  • func NewNode(height int, lchild, rchild *Node, path ledger.Path, payload *ledger.Payload, ...) *Node
  • func (n *Node) AllPayloads() []ledger.Payload
  • func (n *Node) FmtStr(prefix string, subpath string) string
  • func (n *Node) Hash() hash.Hash
  • func (n *Node) Height() int
  • func (n *Node) IsDefaultNode() bool
  • func (n *Node) IsLeaf() bool
  • func (n *Node) LeftChild() *Node
  • func (n *Node) MaxDepth() uint16
  • func (n *Node) Path() *ledger.Path
  • func (n *Node) Payload() *ledger.Payload
  • func (n *Node) RegCount() uint64
  • func (n *Node) RightChild() *Node
  • func (n *Node) VerifyCachedHash() bool

Types

type Node

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

Node defines an Mtrie node

DEFINITIONS:

• HEIGHT of a node v in a tree is the number of edges on the longest downward path between v and a tree leaf.

Conceptually, an MTrie is a sparse Merkle Trie, which has two node types:

• INTERIM node: has at least one child (i.e. lChild or rChild is not nil). Interim nodes do not store a path and have no payload.
• LEAF node: has _no_ children.

Per convention, we also consider nil as a leaf. Formally, nil is the generic representative for any empty (sub)-trie (i.e. a trie without allocated registers).

Nodes are supposed to be treated as _immutable_ data structures. TODO: optimized data structures might be able to reduce memory consumption

func NewInterimCompactifiedNode

func NewInterimCompactifiedNode(height int, lChild, rChild *Node) *Node

NewInterimCompactifiedNode creates a new compactified interim Node. For compactification, we only consider the immediate children. When starting with a maximally pruned trie and creating only InterimCompactifiedNodes during an update, the resulting trie remains maximally pruned. Details on compactification:

• If _both_ immediate children represent completely unallocated sub-tries, then the sub-trie with the new interim node is also completely empty. We return nil.
• If either child is a leaf (i.e. representing a single allocated register) _and_ the other child represents a completely unallocated sub-trie, the new interim node also only holds a single allocated register. In this case, we return a compactified leaf.

UNCHECKED requirement:

• for any child `c` that is non-nil, its height must satisfy: height = c.height + 1

func NewInterimNode

func NewInterimNode(height int, lchild, rchild *Node) *Node

NewInterimNode creates a new interim Node. UNCHECKED requirement:

• for any child `c` that is non-nil, its height must satisfy: height = c.height + 1

func NewLeaf

func NewLeaf(path ledger.Path,
	payload *ledger.Payload,
	height int,
) *Node

NewLeaf creates a compact leaf Node. UNCHECKED requirement: height must be non-negative UNCHECKED requirement: payload is non nil UNCHECKED requirement: payload should be deep copied if received from external sources

func NewNode

func NewNode(height int,
	lchild,
	rchild *Node,
	path ledger.Path,
	payload *ledger.Payload,
	hashValue hash.Hash,
	maxDepth uint16,
	regCount uint64,
) *Node

NewNode creates a new Node. UNCHECKED requirement: combination of values must conform to a valid node type (see documentation of `Node` for details)

func (*Node) AllPayloads

func (n *Node) AllPayloads() []ledger.Payload

AllPayloads returns the payload of this node and all payloads of the subtrie

func (*Node) FmtStr

func (n *Node) FmtStr(prefix string, subpath string) string

FmtStr provides formatted string representation of the Node and sub tree

func (*Node) Hash

func (n *Node) Hash() hash.Hash

Hash returns the Node's hash value. Do NOT MODIFY returned slice!

func (*Node) Height

func (n *Node) Height() int

Height returns the Node's height. Per definition, the height of a node v in a tree is the number of edges on the longest downward path between v and a tree leaf.

func (*Node) IsDefaultNode

func (n *Node) IsDefaultNode() bool

IsDefaultNode returns true iff the sub-trie represented by this root node contains only unallocated registers. This is the case, if the node is nil or the node's hash is equal to the default hash value at the respective height.

func (*Node) IsLeaf

func (n *Node) IsLeaf() bool

IsLeaf returns true if and only if Node is a LEAF.

func (*Node) LeftChild

func (n *Node) LeftChild() *Node

LeftChild returns the the Node's left child. Only INTERIM nodes have children. Do NOT MODIFY returned Node!

func (*Node) MaxDepth

func (n *Node) MaxDepth() uint16

MaxDepth returns the longest path from this node to compacted leafs in the subtree. in contrast to the Height, this value captures compactness of the subtrie.

func (*Node) Path

func (n *Node) Path() *ledger.Path

Path returns a pointer to the Node's register storage path. If the node is not a leaf, the function returns `nil`.

func (*Node) Payload

func (n *Node) Payload() *ledger.Payload

Payload returns the the Node's payload. Do NOT MODIFY returned slices!

func (*Node) RegCount

func (n *Node) RegCount() uint64

RegCount returns number of registers allocated in the subtrie of this node.

func (*Node) RightChild

func (n *Node) RightChild() *Node

RightChild returns the the Node's right child. Only INTERIM nodes have children. Do NOT MODIFY returned Node!

func (*Node) VerifyCachedHash

func (n *Node) VerifyCachedHash() bool

VerifyCachedHash verifies the hash of a node is valid