Documentation
¶
Index ¶
- func EmptyTrieRootHash(pathByteSize int) []byte
- type MTrie
- func (mt *MTrie) AllPayloads() []ledger.Payload
- func (mt *MTrie) AllocatedRegCount() uint64
- func (mt *MTrie) DumpAsJSON(w io.Writer) error
- func (mt *MTrie) Equals(o *MTrie) bool
- func (mt *MTrie) Height() int
- func (mt *MTrie) IsAValidTrie() bool
- func (mt *MTrie) MaxDepth() uint16
- func (mt *MTrie) PathLength() int
- func (mt *MTrie) RootHash() []byte
- func (mt *MTrie) RootNode() *node.Node
- func (mt *MTrie) String() string
- func (mt *MTrie) StringRootHash() string
- func (mt *MTrie) UnsafeProofs(paths []ledger.Path, proofs []*ledger.TrieProof)
- func (mt *MTrie) UnsafeRead(paths []ledger.Path) []*ledger.Payload
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
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 the 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 where not affected by the write operation are shared between the original MTrie (before the register updates) and the updated MTrie (after the register writes).
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 NewEmptyMTrie ¶
NewEmptyMTrie returns an empty Mtrie (root is an empty node)
func NewTrieWithUpdatedRegisters ¶
func NewTrieWithUpdatedRegisters(parentTrie *MTrie, updatedPaths []ledger.Path, updatedPayloads []ledger.Payload) (*MTrie, error)
NewTrieWithUpdatedRegisters constructs a new trie containing all registers from the parent trie. 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 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 `updatedPayloads` are permuted IN-PLACE for optimized processing. TODO: move consistency checks from MForest to here, to make API safe and self-contained
func (*MTrie) AllPayloads ¶ added in v0.12.0
AllPayloads returns all payloads
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 ¶ added in v0.11.0
DumpAsJSON dumps the trie key value pairs to a file having each key value pair as a json row
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) Height ¶ added in v0.16.0
Height returns the height of the trie, which is the height of its root node.
func (*MTrie) IsAValidTrie ¶ added in v0.12.0
IsAValidTrie verifies the content of the trie for potential issues
func (*MTrie) MaxDepth ¶
MaxDepth returns the length of the longest branch from root to leaf. Concurrency safe (as Tries are immutable structures by convention)
func (*MTrie) PathLength ¶
PathLength return the length [in bytes] the trie operates with. Concurrency safe (as Tries are immutable structures by convention)
func (*MTrie) RootHash ¶
RootHash returns the trie's root hash (i.e. the hash of the trie's root node). 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 ¶
StringRootHash returns the trie's string representation. Concurrency safe (as Tries are immutable structures by convention)
func (*MTrie) StringRootHash ¶
StringRootHash returns the trie's Hex-encoded root hash. Concurrency safe (as Tries are immutable structures by convention)
func (*MTrie) UnsafeProofs ¶
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.
func (*MTrie) UnsafeRead ¶
UnsafeRead read payloads for the given paths. UNSAFE: requires _all_ paths to have a length of mt.Height bits. CAUTION: while reading the payloads, `paths` is permuted IN-PLACE for optimized processing. Return:
- `payloads` []*ledger.Payload For each path, the corresponding payload is written into payloads. AFTER the read operation completes, the order of `path` and `payloads` are such that for `path[i]` the corresponding register value is referenced by 0`payloads[i]`.
TODO move consistency checks from Forest into Trie to obtain a safe, self-contained API
Source Files