Documentation
¶
Index ¶
- func EmptyTrieRootHash() ledger.RootHash
- func SplitPaths(paths []ledger.Path, bitIndex int) int
- func TraverseNodes(trie *MTrie, processNode func(*Node) error) error
- type MTrie
- func (mt *MTrie) AllLeafHashes() []*hash.Hash
- func (mt *MTrie) AllocatedRegCount() uint64
- func (mt *MTrie) DumpAsJSON(w io.Writer) error
- func (mt *MTrie) Equals(o *MTrie) bool
- func (mt *MTrie) IsAValidTrie() bool
- func (mt *MTrie) IsEmpty() bool
- func (mt *MTrie) ReadSingleLeafHash(path ledger.Path) *hash.Hash
- func (mt *MTrie) RootHash() ledger.RootHash
- func (mt *MTrie) RootNode() *Node
- func (mt *MTrie) String() string
- func (mt *MTrie) UnsafeProofs(paths []ledger.Path) *ledger.PayloadlessTrieBatchProof
- func (mt *MTrie) UnsafeRead(paths []ledger.Path) []*hash.Hash
- type Node
- func NewInterimCompactifiedNode(height int, lChild, rChild *Node) *Node
- func NewInterimNode(height int, lChild, rChild *Node) *Node
- func NewLeaf(path ledger.Path, value []byte, height int) *Node
- func NewNode(height int, lchild, rchild *Node, path ledger.Path, leafHash *hash.Hash, ...) *Node
- func NewRelevelledLeaf(leaf *Node, relevellingHeight int) *Node
- func (n *Node) AllLeafHashes() []*hash.Hash
- func (n *Node) FmtStr(prefix string, subpath string) string
- func (n *Node) Hash() hash.Hash
- func (n *Node) Height() int
- func (n *Node) IsAllocatedRegisterLeaf() bool
- func (n *Node) IsDefaultNode() bool
- func (n *Node) IsLeaf() bool
- func (n *Node) LeafHash() *hash.Hash
- func (n *Node) LeftChild() *Node
- func (n *Node) Path() *ledger.Path
- func (n *Node) RightChild() *Node
- func (n *Node) VerifyCachedHash() bool
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func EmptyTrieRootHash ¶
EmptyTrieRootHash returns the rootHash of an empty Trie for the specified path size bytes
func SplitPaths ¶
SplitPaths permutes the input paths to be partitioned into 2 parts. The first part contains paths with a zero bit at the input bitIndex, the second part contains paths with a one at the bitIndex. The index of partition is returned.
This would be the partition step of an ascending quick sort of paths (lexicographic order) with the pivot being the path with all zeros and 1 at bitIndex. The comparison of paths is only based on the bit at bitIndex, the function therefore assumes all paths have equal bits from 0 to bitIndex-1
Types ¶
type MTrie ¶
type MTrie struct {
// contains filtered or unexported fields
}
MTrie represents a perfect in-memory full binary Merkle tree with uniform height. For a detailed description of the storage model, please consult `mtrie/README.md`
A MTrie is a thin wrapper around a trie's root Node. An MTrie implements the logic for forming MTrie-graphs from the elementary nodes. Specifically:
- how Nodes (graph vertices) form a Trie,
- how register values are read from the trie,
- how Merkle proofs are generated from a trie, and
- how a new Trie with updated values is generated.
`MTrie`s are _immutable_ data structures. Updating register values is implemented through copy-on-write, which creates a new `MTrie`. For minimal memory consumption, all sub-tries that were not affected by the write operation are shared between the original MTrie (before the register updates) and the updated MTrie (after the register writes).
MTrie expects that for a specific path, the register's key never changes.
DEFINITIONS and CONVENTIONS:
- HEIGHT of a node v in a tree is the number of edges on the longest downward path between v and a tree leaf. The height of a tree is the height of its root. The height of a Trie is always the height of the fully-expanded tree.
func NewMTrie ¶
NewMTrie returns a Mtrie given the root.
No error returns are expected during normal operation.
func NewTrieWithUpdatedRegisters ¶
func NewTrieWithUpdatedRegisters( parentTrie *MTrie, updatedPaths []ledger.Path, updatedValues [][]byte, prune bool, ) (*MTrie, uint16, error)
NewTrieWithUpdatedRegisters constructs a new trie containing all registers from the parent trie, and returns:
- updated trie
- max depth touched during update (this isn't affected by prune flag)
- error
The key-value pairs specify the registers whose values are supposed to hold updated values compared to the parent trie. Constructing the new trie is done in a COPY-ON-WRITE manner:
- The original trie remains unchanged.
- subtries that remain unchanged are referenced from the parent trie instead of copied.
UNSAFE: method requires the following conditions to be satisfied:
- keys are NOT duplicated
- requires _all_ paths to have a length of mt.Height bits.
CAUTION: `updatedPaths` and `updatedValues` are permuted IN-PLACE for optimized processing. CAUTION: MTrie expects that for a specific path, the value's key never changes. TODO: move consistency checks from MForest to here, to make API safe and self-contained
func (*MTrie) AllLeafHashes ¶
AllLeafHashes returns all leaf hashes stored in the trie. Empty leaves (unallocated registers) are skipped.
CAUTION: each returned pointer aliases the corresponding trie node's internal leaf hash. Tries are immutable and shared copy-on-write across trie versions, so the caller MUST NOT modify any pointee; doing so would corrupt that node's cached hash. Callers needing mutable hashes must copy them. Do NOT MODIFY the returned hashes!
func (*MTrie) AllocatedRegCount ¶
AllocatedRegCount returns the number of allocated registers in the trie. Concurrency safe (as Tries are immutable structures by convention)
func (*MTrie) DumpAsJSON ¶
DumpAsJSON dumps the trie leaf entries to a writer having each leaf as a json row. Each entry contains the leaf's path and its stored leaf hash.
func (*MTrie) Equals ¶
Equals compares two tries for equality. Tries are equal iff they store the same data (i.e. root hash matches) and their number and height are identical
func (*MTrie) IsAValidTrie ¶
IsAValidTrie verifies the content of the trie for potential issues
func (*MTrie) IsEmpty ¶
IsEmpty checks if a trie is empty.
An empty trie (root is nil) is not the same as a trie whose registers are all unallocated.
func (*MTrie) ReadSingleLeafHash ¶
ReadSingleLeafHash reads and returns the leaf hash for a single path. Returns nil if no leaf exists at the given path or if the leaf represents an unallocated register.
CAUTION: the returned pointer aliases the trie node's internal leaf hash. Tries are immutable and shared copy-on-write across trie versions, so the caller MUST NOT modify the pointee; doing so would corrupt the node's cached hash. Callers needing a mutable hash must copy it (see the Forest layer, which returns a defensive copy). Do NOT MODIFY the returned hash!
func (*MTrie) RootHash ¶
RootHash returns the trie's root hash. Concurrency safe (as Tries are immutable structures by convention)
func (*MTrie) RootNode ¶
RootNode returns the Trie's root Node Concurrency safe (as Tries are immutable structures by convention)
func (*MTrie) String ¶
String returns the trie's string representation. Concurrency safe (as Tries are immutable structures by convention)
func (*MTrie) UnsafeProofs ¶
func (mt *MTrie) UnsafeProofs(paths []ledger.Path) *ledger.PayloadlessTrieBatchProof
UnsafeProofs provides proofs for the given paths.
CAUTION: while updating, `paths` and `proofs` are permuted IN-PLACE for optimized processing. UNSAFE: requires _all_ paths to have a length of mt.Height bits. Paths in the input query don't have to be deduplicated, though deduplication would result in allocating less dynamic memory to store the proofs.
func (*MTrie) UnsafeRead ¶
UnsafeRead reads leaf hashes for the given paths. UNSAFE: requires _all_ paths to have a length of mt.Height bits. CAUTION: while reading the leaf hashes, `paths` is permuted IN-PLACE for optimized processing. Return:
- `leafHashes` []*hash.Hash For each path, the corresponding leaf hash is written into leafHashes. AFTER the read operation completes, the order of `path` and `leafHashes` are such that for `path[i]` the corresponding leaf hash is referenced by `leafHashes[i]`. A nil entry indicates that no leaf exists at that path or the leaf represents an unallocated register.
TODO move consistency checks from Forest into Trie to obtain a safe, self-contained API
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
Node defines a payloadless Mtrie node.
Unlike the regular mtrie Node which stores full payloads, a payloadless Node stores only the leaf hash for leaf nodes. This enables significant memory savings while preserving the same root hash as a full trie.
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 (in a hypothetical, fully expanded (perfect) tree, i.e. without compactification or nil-pruning).
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 leafHash.
- LEAF node: has _no_ children. It represents a single register, storing a path and the ability to provide the hash commitment of the register's content. Nodes at height 𝒽 = 0 are always leaves. Nodes with 𝒽 > 0 are either leaves or interim nodes. A leaf at height 𝒽 represents a height-𝒽 subtree that holds a single allocated register. Because such a subtree contains no branches, it is collapsed into one node — a COMPACTIFIED LEAF (per mtrie/README.md the term spans all heights 𝒽 ≥ 0). Compactification is optional and always root-hash-preserving. See documentation of `Node.leafHash` and `Node.hashValue` for storage and hashing details.
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 ¶
NewInterimCompactifiedNode creates a new interim Node - compactified if possible. 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 ¶
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 ¶
NewLeaf constructs the leaf Node 𝓃 representing the single register (path, value) at the given height 𝒽. By construction, 𝓃.Hash() equals the hash that the height-𝒽 subtree containing the register would have in the fully-expanded trie. In other words, tries built from these constructors share the same root hash as a fully-expanded trie. That subtree hash is computed by compactification: the recursive application of hashing (see mtrie/README.md for details). It starts from the register's height-0 leaf hash and hashes upward 𝒽 levels, combining at each level with the default hash of the empty sibling subtree.
A `nil` or empty `value` denotes an unallocated register; the result is the default node for the given height (hash is DefaultHashForHeight(height) independent of path; see newDefaultLeaf for details).
It is safe for `path` or `value` to be mutated after the call to `NewLeaf` returns.
UNCHECKED requirement: height must be non-negative.
func NewNode ¶
func NewNode(height int, lchild, rchild *Node, path ledger.Path, leafHash *hash.Hash, hashValue hash.Hash, ) *Node
NewNode creates a new Node. CAUTION: INSECURE! Only intended to reconstruct Nodes from their serialization! UNCHECKED requirement: combination of values must conform to a valid node type (see documentation of `Node` for details)
func NewRelevelledLeaf ¶
NewRelevelledLeaf creates a new compactified leaf 𝓁' for the same register (path, value) as the input leaf 𝓁, re-levelled to height `relevellingHeight`. This is needed when a register r is allocated or removed in the neighbourhood of 𝓁, changing the height at which 𝓁 can be compactified. Example:
trie without r trie with r
parent parent
╱ ╲ ╱ ╲
𝓁 △ ◀──▶ ◯ △ height 𝒽
┊ ╱ ╲
┊ 𝓁' 𝓃 height 𝒽-1
┊ ┊
• • height 0 (fully-expanded perfect trie)
parent : genuine branch at height 𝒽+1; its other child △ is a non-empty sibling subtree
(the reason 𝓁 sits at height 𝒽, not higher). Unchanged by allocating r.
◯ : interim node materialized at 𝓁's former position ( height-𝒽 ).
𝓁, 𝓁' : the SAME register (path, value); 𝓁' is 𝓁 re-levelled to a lower height 𝒽' (𝒽-1 shown).
𝓃 : compactified leaf representing register r.
• : the register's actual leaf at height 0 in the fully-expanded (perfect) trie.
dotted : single-child perfect-trie path (┊) that compactification collapses into one node.
Implementation correctly handles leaves that represent either allocated or unallocated registers. For an unallocated register represented by an explicit default leaf (which carries the register's path), a new default leaf at `relevellingHeight` is created; this is useful for our shortcut for non-inclusion proofs utilizing explicitly represented default leaf nodes. A `nil` input yields a `nil` result.
UNCHECKED requirement: `leaf.IsLeaf()` must be true
func (*Node) AllLeafHashes ¶
AllLeafHashes returns the leaf hash of this node and all leaf hashes of the subtrie. Empty leaves (unallocated registers) are skipped.
func (*Node) Hash ¶
Hash returns the Node's cached hash value, which is a fixed-size array, so the returned value is a copy; mutating it does not affect the Node.
func (*Node) Height ¶
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) IsAllocatedRegisterLeaf ¶
IsAllocatedRegisterLeaf reports whether this node is a leaf representing an allocated register (equivalently, a non-default compactified leaf, at any height 𝒽 ≥ 0). It is a computationally very lightweight check intended to be run on leaf nodes, optimized for minimal computational cost rather than universal applicability.
On leaves it coincides with the negation of `IsDefaultNode`:
𝓃.IsAllocatedRegisterLeaf() = ¬ 𝓃.IsDefaultNode() for any node 𝓃 with 𝓃.IsLeaf() == true
CAUTION:
- For non-leaf nodes, this function always returns false. We do *not* check whether the node could be compactified into a non-default leaf. This is a deliberate trade-off for minimal computational cost.
- A false result therefore does NOT imply the sub-trie is empty/default: any interim node returns false regardless of the subtree beneath it. To test whether a sub-trie is empty/default, use the universally-applicable `IsDefaultNode`.
func (*Node) IsDefaultNode ¶
IsDefaultNode returns true iff the sub-trie represented by this root node contains only unallocated registers. This is the case, if and only if the node is nil or the node's hash is equal to the default hash value at the respective height.
This function is universally applicable, irrespective of compactification, nil-pruning, or whether the node is a leaf or an interim node.
func (*Node) LeafHash ¶
LeafHash returns the Node's leaf hash HashLeaf(path, value). Returns nil for interim nodes and for leaves that represent unallocated registers. Do NOT MODIFY returned hash!
func (*Node) LeftChild ¶
LeftChild returns the Node's left child. Only INTERIM nodes have children. Do NOT MODIFY returned Node!
func (*Node) 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) RightChild ¶
RightChild returns the Node's right child. Only INTERIM nodes have children. Do NOT MODIFY returned Node!
func (*Node) VerifyCachedHash ¶
VerifyCachedHash verifies that every node in the subtree rooted at this node has a cached `hashValue` matching its freshly recomputed hash. CAUTION: this recomputes the hash of every node in the subtree and is therefore very expensive on large tries.
Source Files