trie

package
v0.12.5 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 2, 2024 License: Apache-2.0 Imports: 10 Imported by: 0

Documentation

Overview

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

Index

Constants

This section is empty.

Variables

View Source 
var (
	ErrUnknownProofNode  = errors.New("unknown proof node")
	ErrChildHashNotFound = errors.New("can't determine the child hash from the parent and child")
)

Functions

func GetBoundaryProofs added in v0.12.0 

func GetBoundaryProofs(leftBoundary, rightBoundary *Key, tri *Trie) ([2][]ProofNode, error)

func RunOnTempTriePedersen added in v0.12.0 

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

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

func RunOnTempTriePoseidon added in v0.12.0 

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

func SplitProofPath added in v0.12.3 

func SplitProofPath(mergedPath []ProofNode, rootHash *felt.Felt, hash hashFunc) ([]ProofNode, []ProofNode, error)

SplitProofPath splits the merged proof path into two paths (left and right), which were merged before it first validates that the merged path is not circular, the split happens at most once and rootHash exists then calls traverseNodes to split the path to left and right paths

func VerifyProof added in v0.11.8 

func VerifyProof(root *felt.Felt, key *Key, value *felt.Felt, proofs []ProofNode, hash hashFunc) bool

verifyProof checks if `leafPath` leads from `root` to `leafHash` along the `proofNodes` https://github.com/eqlabs/pathfinder/blob/main/crates/merkle-tree/src/tree.rs#L2006

func VerifyRangeProof added in v0.12.0 

func VerifyRangeProof(root *felt.Felt, keys, values []*felt.Felt, proofKeys [2]*Key, proofValues [2]*felt.Felt,
	proofs [2][]ProofNode, hash hashFunc,
) (bool, error)

VerifyRangeProof verifies the range proof for the given range of keys. This is achieved by constructing a trie from the boundary proofs, and the supplied key-values. If the root of the reconstructed trie matches the supplied root, then the verification passes. If the trie is constructed incorrectly then the root will have an incorrect key(len,path), and value, and therefore it's hash won't match the expected root. ref: https://github.com/ethereum/go-ethereum/blob/v1.14.3/trie/proof.go#L484

Types

type Binary added in v0.11.8 

type Binary struct {
	LeftHash  *felt.Felt
	RightHash *felt.Felt
}

func (*Binary) Hash added in v0.12.3 

func (b *Binary) Hash(hash hashFunc) *felt.Felt

func (*Binary) Len added in v0.12.3 

func (b *Binary) Len() uint8

func (*Binary) PrettyPrint added in v0.12.3 

func (b *Binary) PrettyPrint()

type Edge added in v0.11.8 

type Edge struct {
	Child *felt.Felt // child hash
	Path  *Key       // path from parent to child
}

func (*Edge) Hash added in v0.12.3 

func (e *Edge) Hash(hash hashFunc) *felt.Felt

func (*Edge) Len added in v0.12.3 

func (e *Edge) Len() uint8

func (*Edge) PrettyPrint added in v0.12.3 

func (e *Edge) PrettyPrint()

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) RemoveLastBit added in v0.11.8 

func (k *Key) RemoveLastBit()

func (*Key) String added in v0.6.0 

func (k *Key) String() string

func (*Key) SubKey added in v0.11.8 

func (k *Key) SubKey(n uint8) (*Key, error)

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
	LeftHash  *felt.Felt
	RightHash *felt.Felt
}

A Node represents a node in the Trie https://docs.starknet.io/architecture-and-concepts/network-architecture/starknet-state/#trie_construction

func (*Node) Hash 

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

Hash calculates the hash of a Node

func (*Node) HashFromParent added in v0.12.0 

func (n *Node) HashFromParent(parnetKey, nodeKey *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 ProofNode added in v0.11.8 

type ProofNode interface {
	Hash(hash hashFunc) *felt.Felt
	Len() uint8
	PrettyPrint()
}

func GetProof added in v0.11.8 

func GetProof(key *Key, tri *Trie) ([]ProofNode, error)

https://github.com/eqlabs/pathfinder/blob/main/crates/merkle-tree/src/tree.rs#L514 GetProof generates a set of proof nodes from the root to the leaf. The proof never contains the leaf node if it is set, as we already know it's hash.

func MergeProofPaths added in v0.12.3 

func MergeProofPaths(leftPath, rightPath []ProofNode, hash hashFunc) ([]ProofNode, *felt.Felt, error)

MergeProofPaths removes duplicates and merges proof paths into a single path merges paths in the specified order [commonNodes..., leftNodes..., rightNodes...] ordering of the merged path is not important since SplitProofPath can discover the left and right paths using the merged path and the rootHash

type Storage 

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

Storage 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 StorageNode added in v0.12.0 

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

storageNode is the on-disk representation of a Node, where key is the storage key and node is the value.

func NewStorageNode added in v0.12.0 

func NewStorageNode(key *Key, node *Node) *StorageNode

func ProofToPath added in v0.12.0 

func ProofToPath(proofNodes []ProofNode, leafKey *Key, hashF hashFunc) ([]StorageNode, error)

ProofToPath returns a set of storage nodes from the root to the end of the proof path. The storage nodes will have the hashes of the children, but only the key of the child along the path outlined by the proof.

func (*StorageNode) Key added in v0.12.0 

func (sn *StorageNode) Key() *Key

func (*StorageNode) Node added in v0.12.0 

func (sn *StorageNode) Node() *Node

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 BuildTrie added in v0.12.0 

func BuildTrie(leftProofPath, rightProofPath []StorageNode, keys, values []*felt.Felt) (*Trie, error)

BuildTrie builds a trie using the proof paths (including inner nodes), and then sets all the keys-values (leaves)

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) GetNodeFromKey added in v0.11.8 

func (t *Trie) GetNodeFromKey(key *Key) (*Node, error)

GetNodeFromKey returns the node for a given 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) PutInner added in v0.12.0 

func (t *Trie) PutInner(key *Key, node *Node) (*felt.Felt, error)

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

func (*Trie) PutWithProof added in v0.12.0 

func (t *Trie) PutWithProof(key, value *felt.Felt, lProofPath, rProofPath []StorageNode) (*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

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.