trie

Documentation

Index

• func EmptyTrieRootHash(pathByteSize int) []byte
• type MTrie
  • func NewEmptyMTrie(pathByteSize int) (*MTrie, error)
  • func NewMTrie(root *node.Node) (*MTrie, error)
  • func NewTrieWithUpdatedRegisters(parentTrie *MTrie, updatedPaths []ledger.Path, ...) (*MTrie, error)
  • func (mt *MTrie) AllocatedRegCount() uint64
  • func (mt *MTrie) Equals(o *MTrie) 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) error
  • func (mt *MTrie) UnsafeRead(paths []ledger.Path) ([]*ledger.Payload, error)

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 heights 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

TODO: move consistency checks from MForest to here, to make API is safe and self-contained

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) 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) 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) error

UnsafeProofs provides proofs for the given paths, this is called unsafe as it requires the input paths to be sorted in advance.

func (*MTrie) UnsafeRead

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

UnsafeRead read payloads for the given paths. It is called unsafe as it requires the paths to be sorted TODO move consistency checks from Forrest into Trie to obtain a safe, self-contained API