Documentation
¶
Overview ¶
Package trie implements Merkle Patricia Tries.
Index ¶
- Variables
- func CacheMisses() int64
- func CacheUnloads() int64
- func VerifyProof(rootHash common.Hash, key []byte, proofDb DatabaseReader) (value []byte, nodes int, err error)
- type Database
- func (db *Database) Cap(limit common.StorageSize) error
- func (db *Database) Commit(node common.Hash, report bool) error
- func (db *Database) Dereference(root common.Hash)
- func (db *Database) DiskDB() DatabaseReader
- func (db *Database) InsertBlob(hash common.Hash, blob []byte)
- func (db *Database) Node(hash common.Hash) ([]byte, error)
- func (db *Database) Nodes() []common.Hash
- func (db *Database) Reference(child common.Hash, parent common.Hash)
- func (db *Database) Size() (common.StorageSize, common.StorageSize)
- type DatabaseReader
- type Iterator
- type LeafCallback
- type MissingNodeError
- type NodeIterator
- type SecureTrie
- func (t *SecureTrie) Commit(onleaf LeafCallback) (root common.Hash, err error)
- func (t *SecureTrie) Copy() *SecureTrie
- func (t *SecureTrie) Delete(key []byte)
- func (t *SecureTrie) Get(key []byte) []byte
- func (t *SecureTrie) GetKey(shaKey []byte) []byte
- func (t *SecureTrie) Hash() common.Hash
- func (t *SecureTrie) NodeIterator(start []byte) NodeIterator
- func (t *SecureTrie) Prove(key []byte, fromLevel uint, proofDb ethdb.Putter) error
- func (t *SecureTrie) Root() []byte
- func (t *SecureTrie) TryDelete(key []byte) error
- func (t *SecureTrie) TryGet(key []byte) ([]byte, error)
- func (t *SecureTrie) TryUpdate(key, value []byte) error
- func (t *SecureTrie) Update(key, value []byte)
- type Sync
- func (s *Sync) AddRawEntry(hash common.Hash, depth int, parent common.Hash)
- func (s *Sync) AddSubTrie(root common.Hash, depth int, parent common.Hash, callback LeafCallback)
- func (s *Sync) Commit(dbw ethdb.Putter) (int, error)
- func (s *Sync) Missing(max int) []common.Hash
- func (s *Sync) Pending() int
- func (s *Sync) Process(results []SyncResult) (bool, int, error)
- type SyncResult
- type Trie
- func (t *Trie) Commit(onleaf LeafCallback) (root common.Hash, err error)
- func (t *Trie) Delete(key []byte)
- func (t *Trie) Get(key []byte) []byte
- func (t *Trie) Hash() common.Hash
- func (t *Trie) NodeIterator(start []byte) NodeIterator
- func (t *Trie) Prove(key []byte, fromLevel uint, proofDb ethdb.Putter) error
- func (t *Trie) Root() []byte
- func (t *Trie) SetCacheLimit(l uint16)
- func (t *Trie) TryDelete(key []byte) error
- func (t *Trie) TryGet(key []byte) ([]byte, error)
- func (t *Trie) TryUpdate(key, value []byte) error
- func (t *Trie) Update(key, value []byte)
Constants ¶
This section is empty.
Variables ¶
var ErrAlreadyProcessed = errors.New("already processed")
ErrAlreadyProcessed is returned by the trie sync when it's requested to process a node it already processed previously.
var ErrNotRequested = errors.New("not requested")
ErrNotRequested is returned by the trie sync when it's requested to process a node it did not request.
Functions ¶
func CacheMisses ¶
func CacheMisses() int64
CacheMisses retrieves a global counter measuring the number of cache misses the trie had since process startup. This isn't useful for anything apart from trie debugging purposes.
func CacheUnloads ¶
func CacheUnloads() int64
CacheUnloads retrieves a global counter measuring the number of cache unloads the trie did since process startup. This isn't useful for anything apart from trie debugging purposes.
func VerifyProof ¶
func VerifyProof(rootHash common.Hash, key []byte, proofDb DatabaseReader) (value []byte, nodes int, err error)
todo 校验 Prove() 返回的 proofDb 数组 和 key 的关系
以此来得知 key 是否在该 MPT 的路径上 ? 验证proffDb中是否存在满足输入的hash，和对应key的节点，如果满足，则返回rlp解码后的该节点
todo 因为 key 对应的 value 肯定是 valueNode. 所以 证明 某个node是否在 tire上. 只需要早 proof 路径上找到 key 对应的 valueNode 即可
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 struct {
// contains filtered or unexported fields
}
Database is an intermediate write layer between the trie data structures and the disk database. The aim is to accumulate trie writes in-memory and only periodically flush a couple tries to disk, garbage collecting the remainder.
* Database
todo 是在 `trie数据结构` 和 `磁盘数据库` 之间的中间写入层。 目的是在内存中累积trie写操作，并且仅定期刷新一对尝试写入磁盘的内容，垃圾收集剩余的内容。
func NewDatabase ¶
NewDatabase creates a new trie database to store ephemeral trie content before its written out to disk or garbage collected. * 对 db 实例的封装
func (*Database) Cap ¶
func (db *Database) Cap(limit common.StorageSize) error
Cap iteratively flushes old but still referenced trie nodes until the total memory usage goes below the given threshold. * Cap迭代地刷新,旧的但仍然被引用的trie节点，直到总内存使用率低于给定阈值。
func (*Database) Commit ¶
Commit iterates over all the children of a particular node, writes them out to disk, forcefully tearing down all references in both directions. Commit 迭代特定节点的所有子节点，将它们写入磁盘，强行拆除两个方向上的所有引用。
As a side effect, all pre-images accumulated up to this point are also written. 该函数的副作用是：到当前时间点为止 所累积的所有 preimages 中的数据也被一起写入levelDB。 (因为：本身该函数只是 写 db.nodes 中的trie 的所有nodes的)
func (*Database) Dereference ¶
Dereference removes an existing reference from a root node. 删除掉 之前reference 中的 某个 trie root 对应的trie 的所有 node
func (*Database) DiskDB ¶
func (db *Database) DiskDB() DatabaseReader
DiskDB retrieves the persistent storage backing the trie database.
func (*Database) InsertBlob ¶
InsertBlob writes a new reference tracked blob to the memory database if it's yet unknown. This method should only be used for non-trie nodes that require reference counting, since trie nodes are garbage collected directly through their embedded children.
* 如果尚不知道，InsertBlob 会将新的引用跟踪的Blob 写入 内存数据库。 todo 此方法仅应用于需要引用计数的非trie节点， 因为trie节点是直接通过其嵌入式子节点进行gc的。
todo 说白了目前这种只用来存储 code
func (*Database) Node ¶
Node retrieves an encoded cached trie node from memory. If it cannot be found cached, the method queries the persistent database for the content.
func (*Database) Nodes ¶
Nodes retrieves the hashes of all the nodes cached within the memory database. This method is extremely expensive and should only be used to validate internal states in test code.
func (*Database) Reference ¶
Reference adds a new reference from a parent node to a child node. 根据父节点到子节点添加新的 引用
func (*Database) Size ¶
func (db *Database) Size() (common.StorageSize, common.StorageSize)
Size returns the current storage size of the memory cache in front of the persistent database layer.
type DatabaseReader ¶
type DatabaseReader interface {
// Get retrieves the value associated with key from the database.
Get(key []byte) (value []byte, err error)
// Has retrieves whether a key is present in the database.
Has(key []byte) (bool, error)
}
DatabaseReader wraps the Get and Has method of a backing store for the trie.
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
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
type LeafCallback ¶
LeafCallback is a callback type invoked when a trie operation reaches a leaf node. It's used by state sync and commit to allow handling external references between account and storage tries.
type MissingNodeError ¶
type MissingNodeError struct {
NodeHash common.Hash // hash of the missing node
Path []byte // hex-encoded path to the missing node
}
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 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() common.Hash
// 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() common.Hash
// 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 true iff the current node is a leaf node.
Leaf() bool
// 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
// LeafBlob returns the content 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.
LeafBlob() []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 SecureTrie ¶
type SecureTrie struct {
// contains filtered or unexported fields
}
SecureTrie wraps a trie with key hashing. In a secure trie, all access operations hash the key using keccak256. This prevents calling code from creating long chains of nodes that increase the access time.
Contrary to a regular trie, a SecureTrie can only be created with New and must have an attached database. The database also stores the preimage of each key.
SecureTrie is not safe for concurrent use.
func NewSecure ¶
NewSecure creates a trie with an existing root node from a backing database and optional intermediate in-memory node pool.
If root is the zero hash or the sha3 hash of an empty string, the trie is initially empty. Otherwise, New will panic if db is nil and returns MissingNodeError if the root node cannot be found.
Accessing the trie loads nodes from the database or node pool on demand. Loaded nodes are kept around until their 'cache generation' expires. A new cache generation is created by each call to Commit. cachelimit sets the number of past cache generations to keep.
func (*SecureTrie) Commit ¶
func (t *SecureTrie) Commit(onleaf LeafCallback) (root common.Hash, err error)
Commit writes all nodes and the secure hash pre-images to the trie's database. Nodes are stored with their sha3 hash as the key.
Committing flushes nodes from memory. Subsequent Get calls will load nodes from the database.
func (*SecureTrie) Copy ¶
func (t *SecureTrie) Copy() *SecureTrie
Copy returns a copy of SecureTrie.
func (*SecureTrie) Delete ¶
func (t *SecureTrie) Delete(key []byte)
Delete removes any existing value for key from the trie.
func (*SecureTrie) Get ¶
func (t *SecureTrie) 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 (*SecureTrie) GetKey ¶
func (t *SecureTrie) GetKey(shaKey []byte) []byte
GetKey returns the sha3 preimage of a hashed key that was previously used to store a value.
func (*SecureTrie) Hash ¶
func (t *SecureTrie) Hash() common.Hash
Hash returns the root hash of SecureTrie. It does not write to the database and can be used even if the trie doesn't have one.
func (*SecureTrie) NodeIterator ¶
func (t *SecureTrie) NodeIterator(start []byte) NodeIterator
NodeIterator returns an iterator that returns nodes of the underlying trie. Iteration starts at the key after the given start key.
func (*SecureTrie) Prove ¶
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.
* Prove: 构造入参的key的Merkle proof。 结果包含键值上路径上的所有编码节点。 该值本身也包含在最后一个节点中，可以通过验证证明来检索.
如果trie不包含key的值， 则返回的证明将包含key的现有前缀最长的所有节点（至少是根节点）， 并以证明不存在key的节点结尾.
func (*SecureTrie) Root ¶
func (t *SecureTrie) Root() []byte
Root returns the root hash of SecureTrie. Deprecated: use Hash instead.
func (*SecureTrie) TryDelete ¶
func (t *SecureTrie) 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 (*SecureTrie) TryGet ¶
func (t *SecureTrie) 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 (*SecureTrie) TryUpdate ¶
func (t *SecureTrie) 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 (*SecureTrie) Update ¶
func (t *SecureTrie) 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.
type Sync ¶
type Sync struct {
// contains filtered or unexported fields
}
Sync is the main state trie synchronisation scheduler, which provides yet unknown trie hashes to retrieve, accepts node data associated with said hashes and reconstructs the trie step by step until all is done.
* Sync是主要state Trie同步调度程序，它提供尚未取回的Trie Hash以进行检索，接受与所述Hash相关的trie node date并逐步重建Trie直到完成所有步骤。
func NewSync ¶
func NewSync(root common.Hash, database DatabaseReader, callback LeafCallback) *Sync
NewSync creates a new trie data download scheduler.
func (*Sync) AddRawEntry ¶
AddRawEntry schedules the direct retrieval of a state entry that should not be interpreted as a trie node, but rather accepted and stored into the database as is. This method's goal is to support misc state metadata retrievals (e.g. contract code).
func (*Sync) AddSubTrie ¶
AddSubTrie registers a new trie to the sync code, rooted at the designated parent.
func (*Sync) Commit ¶
Commit flushes the data stored in the internal membatch out to persistent storage, returning the number of items written and any occurred error.
Commit 将存储在 membatch (内存缓存中) 中的数据刷新到持久存储中，返回写入的项目数和任何发生的错误。
func (*Sync) Missing ¶
Missing retrieves the known missing nodes from the trie for retrieval.
Missing: 从trie中拉取已知的丢失节点以进行拉取
type SyncResult ¶
type SyncResult struct {
Hash common.Hash // Hash of the originally unknown trie node
Data []byte // Data content of the retrieved node
}
SyncResult is a simple list to return missing nodes along with their request hashes.
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 ¶
New creates a trie with an existing root node from db.
If root is the zero hash or the sha3 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.
* todo 这个方法超级重要
从数据库加载一个已经存在的Trie树， 就调用 `trie.resolveHash()` 方法来加载整颗Trie树
func (*Trie) Commit ¶
func (t *Trie) Commit(onleaf LeafCallback) (root common.Hash, err error)
Commit writes all nodes to the trie's memory database, tracking the internal and external (for account tries) references.
* Commit: 将所有node写入trie的内存数据库，跟踪内部和外部（用于帐户尝试）引用。
func (*Trie) Get ¶
Get returns the value for key stored in the trie. The value bytes must not be modified by the caller.
func (*Trie) Hash ¶
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 ¶
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.
* todo 这个方法一般只有 轻节点用
Prove: 构造入参的key的Merkle proof
proofDb: 用来 接收 证明 路径的 list
todo 根据给定的key，在trie中，将满足key中最大长度前缀的路径上的节点都加入到proofDb 返回（队列中每个元素满足：未编码的hash以及对应rlp编码后的节点）
如果trie不包含key的值， 则返回的证明将包含key的现有前缀最长的所有节点（至少是根节点）， 并以证明不存在key的节点结尾. (这句话的意思是, 只返回了 key前缀匹配到的node, 而后缀没匹配到node)
func (*Trie) SetCacheLimit ¶
SetCacheLimit sets the number of 'cache generations' to keep. A cache generation is created by a call to Commit.
func (*Trie) TryDelete ¶
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 ¶
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.
`TryGet()` 返回存储在trie中的 key 的 value
调用者不得修改值字节
如果在数据库中找不到节点，则返回MissingNodeError
func (*Trie) TryUpdate ¶
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 ¶
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