trie

Documentation

Index

• func EmptyTrieRootHash() ledger.RootHash
• func SplitPaths(paths []ledger.Path, bitIndex int) int
• type MTrie
  • func NewEmptyMTrie() *MTrie
  • func NewMTrie(root *node.Node, regCount uint64, regSize uint64) (*MTrie, error)
  • func NewTrieWithUpdatedRegisters(parentTrie *MTrie, updatedPaths []ledger.Path, ...) (*MTrie, uint16, error)
  • func (mt *MTrie) AllPayloads() []ledger.Payload
  • func (mt *MTrie) AllocatedRegCount() uint64
  • func (mt *MTrie) AllocatedRegSize() 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) ReadSinglePayload(path ledger.Path) *ledger.Payload
  • func (mt *MTrie) RootHash() ledger.RootHash
  • func (mt *MTrie) RootNode() *node.Node
  • func (mt *MTrie) String() string
  • func (mt *MTrie) UnsafeProofs(paths []ledger.Path) *ledger.TrieBatchProof
  • func (mt *MTrie) UnsafeRead(paths []ledger.Path) []*ledger.Payload
  • func (mt *MTrie) UnsafeValueSizes(paths []ledger.Path) []int

Functions

func EmptyTrieRootHash

func EmptyTrieRootHash() ledger.RootHash

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

func SplitPaths

func SplitPaths(paths []ledger.Path, bitIndex int) int

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

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 NewEmptyMTrie

func NewEmptyMTrie() *MTrie

NewEmptyMTrie returns an empty Mtrie (root is nil)

func NewMTrie

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

NewMTrie returns a Mtrie given the root

func NewTrieWithUpdatedRegisters

func NewTrieWithUpdatedRegisters(
	parentTrie *MTrie,
	updatedPaths []ledger.Path,
	updatedPayloads []ledger.Payload,
	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 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. CAUTION: MTrie expects that for a specific path, the payload's key never changes. TODO: move consistency checks from MForest to here, to make API safe and self-contained

func (*MTrie) AllPayloads

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

func (mt *MTrie) AllocatedRegSize() uint64

AllocatedRegSize returns the size of allocated registers in the trie. Concurrency safe (as Tries are immutable structures by convention)

func (*MTrie) DumpAsJSON

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

func (mt *MTrie) IsAValidTrie() bool

IsAValidTrie verifies the content of the trie for potential issues

func (*MTrie) IsEmpty

func (mt *MTrie) IsEmpty() bool

IsEmpty checks if a trie is empty.

An empty try doesn't mean a trie with no allocated registers.

func (*MTrie) ReadSinglePayload

func (mt *MTrie) ReadSinglePayload(path ledger.Path) *ledger.Payload

ReadSinglePayload reads and returns a payload for a single path.

func (*MTrie) RootHash

func (mt *MTrie) RootHash() ledger.RootHash

RootHash returns the trie's root hash. 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

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.TrieBatchProof

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

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

UnsafeRead reads 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

func (*MTrie) UnsafeValueSizes

func (mt *MTrie) UnsafeValueSizes(paths []ledger.Path) []int

UnsafeValueSizes returns payload value sizes for the given paths. UNSAFE: requires _all_ paths to have a length of mt.Height bits. CAUTION: while getting payload value sizes, `paths` is permuted IN-PLACE for optimized processing. Return:

• `sizes` []int For each path, the corresponding payload value size is written into sizes. AFTER the size operation completes, the order of `path` and `sizes` are such that for `path[i]` the corresponding register value size is referenced by `sizes[i]`.

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