trie

package
v0.16.3-patch.3 Latest Latest
Warning

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

Go to latest
Published: May 6, 2021 License: AGPL-3.0 Imports: 11 Imported by: 6

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func EmptyTrieRootHash

func EmptyTrieRootHash(pathByteSize int) []byte

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

func NewEmptyMTrie(pathByteSize int) (*MTrie, error)

NewEmptyMTrie returns an empty Mtrie (root is an empty node)

func NewMTrie

func NewMTrie(root *node.Node) (*MTrie, error)

NewMTrie returns a Mtrie given the root

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

func (mt *MTrie) AllPayloads() []ledger.Payload

AllPayloads returns all payloads

func (*MTrie) AllocatedRegCount

func (mt *MTrie) AllocatedRegCount() uint64

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

func (mt *MTrie) DumpAsJSON(w io.Writer) error

DumpAsJSON dumps the trie key value pairs to a file having each key value pair as a json row

func (*MTrie) Equals

func (mt *MTrie) Equals(o *MTrie) bool

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

func (mt *MTrie) Height() int

Height returns the height of the trie, which is the height of its root node.

func (*MTrie) IsAValidTrie added in v0.12.0

func (mt *MTrie) IsAValidTrie() bool

IsAValidTrie verifies the content of the trie for potential issues

func (*MTrie) MaxDepth

func (mt *MTrie) MaxDepth() uint16

MaxDepth returns the length of the longest branch from root to leaf. Concurrency safe (as Tries are immutable structures by convention)

func (*MTrie) PathLength

func (mt *MTrie) PathLength() int

PathLength return the length [in bytes] the trie operates with. Concurrency safe (as Tries are immutable structures by convention)

func (*MTrie) RootHash

func (mt *MTrie) RootHash() []byte

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

func (mt *MTrie) RootNode() *node.Node

RootNode returns the Trie's root Node Concurrency safe (as Tries are immutable structures by convention)

func (*MTrie) String

func (mt *MTrie) String() string

StringRootHash returns the trie's string representation. Concurrency safe (as Tries are immutable structures by convention)

func (*MTrie) StringRootHash

func (mt *MTrie) StringRootHash() string

StringRootHash returns the trie's Hex-encoded root hash. Concurrency safe (as Tries are immutable structures by convention)

func (*MTrie) UnsafeProofs

func (mt *MTrie) UnsafeProofs(paths []ledger.Path, proofs []*ledger.TrieProof)

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

func (mt *MTrie) UnsafeRead(paths []ledger.Path) []*ledger.Payload

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

Jump to

Keyboard shortcuts

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