trie

Documentation

Overview

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

Index

• func RunOnTempTrie(height uint8, do func(*Trie) error) error
• type Key
  • func NewKey(length uint8, keyBytes []byte) Key
  • func (k *Key) DeleteLSB(n uint8)
  • func (k *Key) EncodedLen() uint
  • func (k *Key) Equal(other *Key) bool
  • func (k *Key) Felt() felt.Felt
  • func (k *Key) Len() uint8
  • func (k *Key) String() string
  • func (k *Key) Test(bit uint8) bool
  • func (k *Key) Truncate(length uint8)
  • func (k *Key) UnmarshalBinary(data []byte) error
  • func (k *Key) WriteTo(buf *bytes.Buffer) (int64, error)
• type NewTrieFunc
• type Node
  • func (n *Node) Hash(path *Key, hashFunc hashFunc) *felt.Felt
  • func (n *Node) UnmarshalBinary(data []byte) error
  • func (n *Node) WriteTo(buf *bytes.Buffer) (int64, error)
• type TransactionStorage
  • func NewTransactionStorage(txn db.Transaction, prefix []byte) *TransactionStorage
  • func (t *TransactionStorage) Delete(key *Key) error
  • func (t *TransactionStorage) DeleteRootKey() error
  • func (t *TransactionStorage) Get(key *Key) (*Node, error)
  • func (t *TransactionStorage) Put(key *Key, value *Node) error
  • func (t *TransactionStorage) PutRootKey(newRootKey *Key) error
  • func (t *TransactionStorage) RootKey() (*Key, error)
  • func (t *TransactionStorage) SyncedStorage() *TransactionStorage
• type Trie
  • func NewTriePedersen(storage *TransactionStorage, height uint8) (*Trie, error)
  • func NewTriePoseidon(storage *TransactionStorage, height uint8) (*Trie, error)
  • func (t *Trie) Commit() 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() *Key

Functions

func RunOnTempTrie

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

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

Types

type Key

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

func NewKey

func NewKey(length uint8, keyBytes []byte) Key

func (*Key) DeleteLSB

func (k *Key) DeleteLSB(n uint8)

DeleteLSB right shifts and shortens the key

func (*Key) EncodedLen

func (k *Key) EncodedLen() uint

func (*Key) Equal

func (k *Key) Equal(other *Key) bool

func (*Key) Felt

func (k *Key) Felt() felt.Felt

func (*Key) Len

func (k *Key) Len() uint8

func (*Key) String

func (k *Key) String() string

func (*Key) Test

func (k *Key) Test(bit uint8) bool

func (*Key) Truncate

func (k *Key) Truncate(length uint8)

Truncate truncates key to `length` bits by clearing the remaining upper bits

func (*Key) UnmarshalBinary

func (k *Key) UnmarshalBinary(data []byte) error

func (*Key) WriteTo

func (k *Key) WriteTo(buf *bytes.Buffer) (int64, error)

type NewTrieFunc

type NewTrieFunc func(*TransactionStorage, uint8) (*Trie, error)

type Node

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

A Node represents a node in the Trie

func (*Node) Hash

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

Hash calculates the hash of a Node

func (*Node) UnmarshalBinary

func (n *Node) UnmarshalBinary(data []byte) error

UnmarshalBinary deserializes a Node from a byte array

func (*Node) WriteTo

func (n *Node) WriteTo(buf *bytes.Buffer) (int64, error)

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

func (*TransactionStorage) DeleteRootKey

func (t *TransactionStorage) DeleteRootKey() error

func (*TransactionStorage) Get

func (t *TransactionStorage) Get(key *Key) (*Node, error)

func (*TransactionStorage) Put

func (t *TransactionStorage) Put(key *Key, value *Node) error

func (*TransactionStorage) PutRootKey

func (t *TransactionStorage) PutRootKey(newRootKey *Key) error

func (*TransactionStorage) RootKey

func (t *TransactionStorage) RootKey() (*Key, error)

func (*TransactionStorage) SyncedStorage

func (t *TransactionStorage) SyncedStorage() *TransactionStorage

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 *TransactionStorage, height uint8) (*Trie, error)

func NewTriePoseidon

func NewTriePoseidon(storage *TransactionStorage, height uint8) (*Trie, error)

func (*Trie) Commit

func (t *Trie) Commit() error

Commit forces root calculation

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() *Key

RootKey returns db key of the Trie root node