trie

package
v0.0.0-...-e4e12f0 Latest Latest
Warning

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

 Go to latest Published: Aug 12, 2022 License: LGPL-3.0 Imports: 12 Imported by: 0

README

based on github.com/ethereum/go-ethereum/trie v1.7.3 tag

Documentation

Overview

Package trie implements Merkle Patricia Tries.

Index

Constants

This section is empty.

Variables

View Source 
var NonCryptoNodeHash = workshare.BytesToBytes32(bytes.Repeat([]byte{0xff}, 32))

Functions

func DeriveRoot 

func DeriveRoot(list DerivableList) workshare.Bytes32

func VerifyNodeHash 

func VerifyNodeHash(blob, expectedHash []byte) (bool, error)

VerifyNodeHash verifies the hash of the node blob (trailing excluded).

func VerifyProof 

func VerifyProof(rootHash workshare.Bytes32, key []byte, proofDb DatabaseReader) (value []byte, err error, nodes int)

VerifyProof checks merkle proofs. The given proof must contain the value for key in a trie with the given root hash. VerifyProof returns an error if the proof contains invalid trie nodes or the wrong value.

Types

type Database 

type Database interface {
	DatabaseReader
	DatabaseWriter
}

Database must be implemented by backing stores for the trie.

type DatabaseKeyEncoder 

type DatabaseKeyEncoder interface {
	Encode(hash []byte, seq uint64, path []byte) []byte
}

DatabaseKeyEncoder defines the method how to produce database key. If the database implements this interface, everytime before save the node, Encode is called and its return-value will be the saving key instead of node hash.

type DatabaseReader 

type DatabaseReader interface {
	Get(key []byte) (value []byte, err error)
}

DatabaseReader wraps the Get method of a backing store for the trie.

type DatabaseReaderTo 

type DatabaseReaderTo interface {
	// GetTo gets value for the given key and append to dst.
	GetTo(key, dst []byte) (value []byte, err error)
}

DatabaseReaderTo wraps the GetTo method of backing store for the trie. The purpose of this interface is to reuse read buffer and avoid allocs. If the database implements this interface, DatabaseReader.Get will not be called when resolving nodes.

type DatabaseWriter 

type DatabaseWriter interface {
	// Put stores the mapping key->value in the database.
	// Implementations must not hold onto the value bytes, the trie
	// will reuse the slice across calls to Put.
	Put(key, value []byte) error
}

DatabaseWriter wraps the Put method of a backing store for the trie.

type DerivableList 

type DerivableList interface {
	Len() int
	GetRlp(i int) []byte
}

type ExtendedTrie 

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

ExtendedTrie is an extended Merkle Patricia Trie which supports nodes sequence number and leaf metadata.

func NewExtended 

func NewExtended(root workshare.Bytes32, seq uint64, db Database, nonCrypto bool) *ExtendedTrie

NewExtended creates an extended trie.

func NewExtendedCached 

func NewExtendedCached(rootNode Node, db Database, nonCrypto bool) *ExtendedTrie

NewExtendedCached creates an extended trie with the given root node.

func (*ExtendedTrie) CacheTTL 

func (e *ExtendedTrie) CacheTTL() uint16

CacheTTL returns the life time of a cached node.

func (*ExtendedTrie) Commit 

func (e *ExtendedTrie) Commit(seq uint64) (root workshare.Bytes32, err error)

Commit writes all nodes with the given sequence number to the trie's database.

Committing flushes nodes from memory. Subsequent Get calls will load nodes from the database.

func (*ExtendedTrie) CommitTo 

func (e *ExtendedTrie) CommitTo(db DatabaseWriter, seq uint64) (root workshare.Bytes32, err error)

CommitTo writes all nodes with the given sequence number to the given database.

Committing flushes nodes from memory. Subsequent Get calls will load nodes from the trie's database. Calling code must ensure that the changes made to db are written back to the trie's attached database before using the trie.

func (*ExtendedTrie) Get 

func (e *ExtendedTrie) Get(key []byte) (val, meta []byte, err error)

Get returns the value and metadata for key stored in the trie. The value and meta bytes must not be modified by the caller. If a node was not found in the database, a MissingNodeError is returned.

func (*ExtendedTrie) Hash 

func (e *ExtendedTrie) Hash() workshare.Bytes32

Hash returns the root hash of the trie. It does not write to the database and can be used even if the trie doesn't have one.

func (*ExtendedTrie) IsNonCrypto 

func (e *ExtendedTrie) IsNonCrypto() bool

IsNonCrypto returns whether the trie is a non-crypto trie.

func (*ExtendedTrie) NodeIterator 

func (e *ExtendedTrie) NodeIterator(start []byte, filter func(seq uint64) bool) NodeIterator

NodeIterator returns an iterator that returns nodes of the trie. Iteration starts at the key after the given start key. It filters out nodes satisfy the filter.

func (*ExtendedTrie) RootNode 

func (e *ExtendedTrie) RootNode() Node

RootNode returns the current root node.

func (*ExtendedTrie) SetCacheTTL 

func (e *ExtendedTrie) SetCacheTTL(ttl uint16)

SetCacheTTL sets life time of a cached node.

func (*ExtendedTrie) SetRootNode 

func (e *ExtendedTrie) SetRootNode(root Node)

SetRootNode replace the root node with the given one.

func (*ExtendedTrie) Update 

func (e *ExtendedTrie) Update(key, value, meta []byte) error

Update associates key with value and metadata in the trie. Subsequent calls to Get will return value. If value has length zero, any existing value is deleted from the trie and calls to Get will return nil.

The value and meta bytes must not be modified by the caller while they are stored in the trie.

If a node was not found in the database, a MissingNodeError is returned.

type Iterator 

type Iterator struct {
	Key   []byte // Current data key on which the iterator is positioned on
	Value []byte // Current data value on which the iterator is positioned on
	Meta  []byte // Current metadata on which the iterator is positioned on
	Err   error
	// contains filtered or unexported fields
}

Iterator is a key-value trie iterator that traverses a Trie.

func NewIterator 

func NewIterator(it NodeIterator) *Iterator

NewIterator creates a new key-value iterator from a node iterator. Note that the value returned by the iterator is raw. If the content is encoded (e.g. storage value is RLP-encoded), it's caller's duty to decode it.

func (*Iterator) Next 

func (it *Iterator) Next() bool

Next moves the iterator forward one key-value entry.

func (*Iterator) Prove 

func (it *Iterator) Prove() [][]byte

Prove generates the Merkle proof for the leaf node the iterator is currently positioned on.

type Leaf 

type Leaf struct {
	Value []byte
	Meta  []byte
}

Leaf presents the leaf node.

type MissingNodeError 

type MissingNodeError struct {
	NodeHash *hashNode // hash of the missing node
	Path     []byte    // hex-encoded path to the missing node
	Err      error     // the actual error
}

MissingNodeError is returned by the trie functions (TryGet, TryUpdate, TryDelete) in the case where a trie node is not present in the local database. It contains information necessary for retrieving the missing node.

func (*MissingNodeError) Error 

func (err *MissingNodeError) Error() string

type Node 

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

Node contains the internal node object.

func (Node) Dirty 

func (n Node) Dirty() bool

Dirty returns if the node is dirty.

func (Node) Hash 

func (n Node) Hash() (hash workshare.Bytes32)

Hash returns the hash of the node. It returns zero hash in case of embedded or not computed.

func (Node) SeqNum 

func (n Node) SeqNum() uint64

SeqNum returns the node's sequence number. 0 is returned if the node is dirty.

type NodeIterator 

type NodeIterator interface {
	// Next moves the iterator to the next node. If the parameter is false, any child
	// nodes will be skipped.
	Next(bool) bool

	// Error returns the error status of the iterator.
	Error() error

	// Hash returns the hash of the current node.
	Hash() workshare.Bytes32

	// Node calls the handler with the blob of the current node if any.
	Node(handler func(blob []byte) error) error

	// SeqNum returns the sequence number of the current node.
	SeqNum() uint64

	// Parent returns the hash of the parent of the current node. The hash may be the one
	// grandparent if the immediate parent is an internal node with no hash.
	Parent() workshare.Bytes32

	// Path returns the hex-encoded path to the current node.
	// Callers must not retain references to the return value after calling Next.
	// For leaf nodes, the last element of the path is the 'terminator symbol' 0x10.
	Path() []byte

	// Leaf returns the leaf node if the current node is a leaf node, or nil returned.
	Leaf() *Leaf

	// LeafKey returns the key of the leaf. The method panics if the iterator is not
	// positioned at a leaf. Callers must not retain references to the value after
	// calling Next.
	LeafKey() []byte

	// LeafProof returns the Merkle proof of the leaf. The method panics if the
	// iterator is not positioned at a leaf. Callers must not retain references
	// to the value after calling Next.
	LeafProof() [][]byte
}

NodeIterator is an iterator to traverse the trie pre-order.

func NewDifferenceIterator 

func NewDifferenceIterator(a, b NodeIterator) (NodeIterator, *int)

NewDifferenceIterator constructs a NodeIterator that iterates over elements in b that are not in a. Returns the iterator, and a pointer to an integer recording the number of nodes seen.

func NewUnionIterator 

func NewUnionIterator(iters []NodeIterator) (NodeIterator, *int)

NewUnionIterator constructs a NodeIterator that iterates over elements in the union of the provided NodeIterators. Returns the iterator, and a pointer to an integer recording the number of nodes visited.

type Trie 

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

Trie is a Merkle Patricia Trie. The zero value is an empty trie with no database. Use New to create a trie that sits on top of a database.

Trie is not safe for concurrent use.

func New 

func New(root workshare.Bytes32, db Database) (*Trie, error)

New creates a trie with an existing root node from db.

If root is the zero hash or the blake2b hash of an empty string, the trie is initially empty and does not require a database. Otherwise, New will panic if db is nil and returns a MissingNodeError if root does not exist in the database. Accessing the trie loads nodes from db on demand.

func (*Trie) Commit 

func (t *Trie) Commit() (root workshare.Bytes32, err error)

Commit writes all nodes to the trie's database. Nodes are stored with their blake2b hash as the key.

Committing flushes nodes from memory. Subsequent Get calls will load nodes from the database.

func (*Trie) CommitTo 

func (t *Trie) CommitTo(db DatabaseWriter) (root workshare.Bytes32, err error)

CommitTo writes all nodes to the given database. Nodes are stored with their blake2b hash as the key.

Committing flushes nodes from memory. Subsequent Get calls will load nodes from the trie's database. Calling code must ensure that the changes made to db are written back to the trie's attached database before using the trie.

func (*Trie) Delete 

func (t *Trie) Delete(key []byte)

Delete removes any existing value for key from the trie.

func (*Trie) Get 

func (t *Trie) Get(key []byte) []byte

Get returns the value for key stored in the trie. The value bytes must not be modified by the caller.

func (*Trie) Hash 

func (t *Trie) Hash() workshare.Bytes32

Hash returns the root hash of the trie. It does not write to the database and can be used even if the trie doesn't have one.

func (*Trie) NodeIterator 

func (t *Trie) NodeIterator(start []byte) NodeIterator

NodeIterator returns an iterator that returns nodes of the trie. Iteration starts at the key after the given start key.

func (*Trie) Prove 

func (t *Trie) Prove(key []byte, fromLevel uint, proofDb DatabaseWriter) error

Prove constructs a merkle proof for key. The result contains all encoded nodes on the path to the value at key. The value itself is also included in the last node and can be retrieved by verifying the proof.

If the trie does not contain a value for key, the returned proof contains all nodes of the longest existing prefix of the key (at least the root node), ending with the node that proves the absence of the key.

func (*Trie) Root 

func (t *Trie) Root() []byte

Root returns the root hash of the trie. Deprecated: use Hash instead.

func (*Trie) TryDelete 

func (t *Trie) TryDelete(key []byte) error

TryDelete removes any existing value for key from the trie. If a node was not found in the database, a MissingNodeError is returned.

func (*Trie) TryGet 

func (t *Trie) TryGet(key []byte) ([]byte, error)

TryGet returns the value for key stored in the trie. The value bytes must not be modified by the caller. If a node was not found in the database, a MissingNodeError is returned.

func (*Trie) TryUpdate 

func (t *Trie) TryUpdate(key, value []byte) error

TryUpdate associates key with value in the trie. Subsequent calls to Get will return value. If value has length zero, any existing value is deleted from the trie and calls to Get will return nil.

The value bytes must not be modified by the caller while they are stored in the trie.

If a node was not found in the database, a MissingNodeError is returned.

func (*Trie) Update 

func (t *Trie) Update(key, value []byte)

Update associates key with value in the trie. Subsequent calls to Get will return value. If value has length zero, any existing value is deleted from the trie and calls to Get will return nil.

The value bytes must not be modified by the caller while they are stored in the trie.

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.