trie

Documentation

Overview

Package trie implements a dense Merkle Patricia Trie. See the documentation on Trie for details.

Index

• func RunOnTempTrie(height uint, do func(*Trie) error) error
• type NewTrieFunc
• type Node
  • func (n *Node) Hash(path *bitset.BitSet, hashFunc hashFunc) *felt.Felt
• type Storage
• type TransactionStorage
  • func NewTransactionStorage(txn db.Transaction, prefix []byte) *TransactionStorage
  • func (t *TransactionStorage) Delete(key *bitset.BitSet) error
  • func (t *TransactionStorage) Get(key *bitset.BitSet) (*Node, error)
  • func (t *TransactionStorage) Put(key *bitset.BitSet, value *Node) error
• type Trie
  • func NewTriePedersen(storage Storage, height uint, rootKey *bitset.BitSet) (*Trie, error)
  • func NewTriePoseidon(storage Storage, height uint, rootKey *bitset.BitSet) (*Trie, error)
  • func (t *Trie) Dump()
  • func (t *Trie) Get(key *felt.Felt) (*felt.Felt, error)
  • func (t *Trie) Put(key, value *felt.Felt) (*felt.Felt, error)
  • func (t *Trie) Root() (*felt.Felt, error)
  • func (t *Trie) RootKey() *bitset.BitSet

Functions

func RunOnTempTrie

func RunOnTempTrie(height uint, do func(*Trie) error) error

RunOnTempTrie creates an in-memory Trie of height `height` and runs `do` on that Trie

Types

type NewTrieFunc

type NewTrieFunc func(Storage, uint, *bitset.BitSet) (*Trie, error)

type Node

type Node struct {
	Value *felt.Felt
	Left  *bitset.BitSet
	Right *bitset.BitSet
}

A Node represents a node in the Trie

func (*Node) Hash

func (n *Node) Hash(path *bitset.BitSet, hashFunc hashFunc) *felt.Felt

Hash calculates the hash of a Node

type Storage

type Storage interface {
	Put(key *bitset.BitSet, value *Node) error
	Get(key *bitset.BitSet) (*Node, error)
	Delete(key *bitset.BitSet) error
}

Storage is the Persistent storage for the Trie

type TransactionStorage

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

TransactionStorage is a database transaction on a trie.

func NewTransactionStorage

func NewTransactionStorage(txn db.Transaction, prefix []byte) *TransactionStorage

func (*TransactionStorage) Delete

func (t *TransactionStorage) Delete(key *bitset.BitSet) error

func (*TransactionStorage) Get

func (t *TransactionStorage) Get(key *bitset.BitSet) (*Node, error)

func (*TransactionStorage) Put

func (t *TransactionStorage) Put(key *bitset.BitSet, value *Node) error

type Trie

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

Trie is a dense Merkle Patricia Trie (i.e., all internal nodes have two children).

This implementation allows for a "flat" storage by keying nodes on their path rather than their hash, resulting in O(1) accesses and O(log n) insertions.

The state trie specification describes a sparse Merkle Trie. Note that this dense implementation results in an equivalent commitment.

Terminology:

• path: represents the path as defined in the specification. Together with len, represents a relative path from the current node to the node's nearest non-empty child.
• len: represents the len as defined in the specification. The number of bits to take from the fixed-length path to reach the nearest non-empty child.
• key: represents the storage key for trie [Node]s. It is the full path to the node from the root.

func NewTriePedersen

func NewTriePedersen(storage Storage, height uint, rootKey *bitset.BitSet) (*Trie, error)

func NewTriePoseidon

func NewTriePoseidon(storage Storage, height uint, rootKey *bitset.BitSet) (*Trie, error)

func (*Trie) Dump

func (t *Trie) Dump()

func (*Trie) Get

func (t *Trie) Get(key *felt.Felt) (*felt.Felt, error)

Get the corresponding `value` for a `key`

func (*Trie) Put

func (t *Trie) Put(key, value *felt.Felt) (*felt.Felt, error)

Put updates the corresponding `value` for a `key`

func (*Trie) Root

func (t *Trie) Root() (*felt.Felt, error)

Root returns the commitment of a Trie

func (*Trie) RootKey

func (t *Trie) RootKey() *bitset.BitSet

RootKey returns db key of the Trie root node