trie

Documentation

Index

• func EmptyTrieRootHash(keyByteSize int) []byte
• func RootHashToString(rootHash []byte) string
• type MTrie
  • func Load(path string) (*MTrie, error)
  • func NewEmptyMTrie(keyByteSize int) (*MTrie, error)
  • func NewMTrie(root *node.Node) (*MTrie, error)
  • func NewTrieWithUpdatedRegisters(parentTrie *MTrie, updatedRegisterKeys [][]byte, ...) (*MTrie, error)
  • func (mt *MTrie) AllocatedRegCount() uint64
  • func (mt *MTrie) DumpAsJSON(path string) error
  • func (mt *MTrie) Equals(o *MTrie) bool
  • func (mt *MTrie) KeyLength() int
  • func (mt *MTrie) MaxDepth() uint16
  • func (mt *MTrie) RootHash() []byte
  • func (mt *MTrie) RootNode() *node.Node
  • func (mt *MTrie) Store(path string) error
  • func (mt *MTrie) String() string
  • func (mt *MTrie) StringRootHash() string
  • func (mt *MTrie) UnsafeProofs(keys [][]byte, proofs []*proof.Proof) error
  • func (mt *MTrie) UnsafeRead(keys [][]byte) ([][]byte, error)

Functions

func EmptyTrieRootHash

func EmptyTrieRootHash(keyByteSize int) []byte

EmptyTrieRootHash returns the rootHash of an empty Trie for the specified key size bytes

func RootHashToString

func RootHashToString(rootHash []byte) string

Types

type MTrie

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

MTrie is a fully in memory trie with option to persist to disk. Formally, an MTrie represents a perfect, 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 Load

func Load(path string) (*MTrie, error)

Load loads a trie

func NewEmptyMTrie

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

func NewMTrie

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

func NewTrieWithUpdatedRegisters

func NewTrieWithUpdatedRegisters(parentTrie *MTrie, updatedRegisterKeys [][]byte, updatedRegisterValues [][]byte) (*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) DumpAsJSON

func (mt *MTrie) DumpAsJSON(path string) 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) KeyLength

func (mt *MTrie) KeyLength() int

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

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

func (mt *MTrie) Store(path string) error

Store stores the trie key Values to a file

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(keys [][]byte, proofs []*proof.Proof) error

func (*MTrie) UnsafeRead

func (mt *MTrie) UnsafeRead(keys [][]byte) ([][]byte, error)

TODO move consistency checks from Forest into Trie to obtain a safe, self-contained API