trie

package

v0.11.7 Latest Latest Go to latest Published: Apr 26, 2024 License: Apache-2.0 Imports: 10 Imported by: 0

Details

Valid go.mod file

The Go module system was introduced in Go 1.11 and is the official dependency management solution for Go.
Redistributable license

Redistributable licenses place minimal restrictions on how software can be used, modified, and redistributed.
Tagged version

Modules with tagged versions give importers more predictable builds.
Stable version

When a project reaches major version v1 it is considered stable.
Learn more about best practices

Repository

github.com/NethermindEth/juno

Links

Open Source Insights

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
type NewTrieFunc
type Node
type Storage
- func NewStorage(txn db.Transaction, prefix []byte) *Storage
type Trie
- func NewTriePedersen(storage *Storage, height uint8) (*Trie, error)
- func NewTriePoseidon(storage *Storage, height uint8) (*Trie, error)

Constants ¶

This section is empty.

Variables ¶

This section is empty.

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 ¶ added in v0.6.0

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

func NewKey ¶ added in v0.6.0

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

func (*Key) DeleteLSB ¶ added in v0.6.0

func (k *Key) DeleteLSB(n uint8)

DeleteLSB right shifts and shortens the key

func (*Key) EncodedLen ¶ added in v0.6.0

func (k *Key) EncodedLen() uint

func (*Key) Equal ¶ added in v0.6.0

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

func (*Key) Felt ¶ added in v0.6.0

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

func (*Key) Len ¶ added in v0.6.0

func (k *Key) Len() uint8

func (*Key) String ¶ added in v0.6.0

func (k *Key) String() string

func (*Key) Test ¶ added in v0.6.0

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

func (*Key) Truncate ¶ added in v0.6.0

func (k *Key) Truncate(length uint8)

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

func (*Key) UnmarshalBinary ¶ added in v0.6.0

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

func (*Key) WriteTo ¶ added in v0.6.0

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

type NewTrieFunc ¶ added in v0.2.1

type NewTrieFunc func(*Storage, 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 ¶ added in v0.4.0

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

UnmarshalBinary deserializes a Node from a byte array

func (*Node) WriteTo ¶ added in v0.4.0

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

type Storage ¶

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

TransactionStorage is a database transaction on a trie.

func NewStorage ¶ added in v0.11.6

func NewStorage(txn db.Transaction, prefix []byte) *Storage

func (*Storage) Delete ¶

func (t *Storage) Delete(key *Key) error

func (*Storage) DeleteRootKey ¶ added in v0.4.0

func (t *Storage) DeleteRootKey() error

func (*Storage) Get ¶

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

func (*Storage) Put ¶

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

func (*Storage) PutRootKey ¶ added in v0.4.0

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

func (*Storage) RootKey ¶ added in v0.4.0

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

func (*Storage) SyncedStorage ¶ added in v0.11.6

func (t *Storage) SyncedStorage() *Storage

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 ¶ added in v0.2.1

func NewTriePedersen(storage *Storage, height uint8) (*Trie, error)

func NewTriePoseidon ¶ added in v0.2.1

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

func (*Trie) Commit ¶ added in v0.4.0

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

Source Files ¶

View all Source files

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL