trie

package
v0.0.0-...-de85661 Latest Latest
Warning

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

 Go to latest Published: Aug 3, 2022 License: Unlicense Imports: 19 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source 
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.

View Source 
var ErrCommitDisabled = errors.New("no database for committing")
View Source 
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 VerifyProof 

func VerifyProof(rootHash entity.Hash, key []byte, proofDb typedb.KeyValueReader) (value []byte, err error)

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.

func VerifyRangeProof 

func VerifyRangeProof(rootHash entity.Hash, firstKey []byte, lastKey []byte, keys [][]byte, values [][]byte, proof typedb.KeyValueReader) (bool, error)

VerifyRangeProof checks whether the given leaf nodes and edge proof can prove the given trie leaves range is matched with the specific root. Besides, the range should be consecutive (no gap inside) and monotonic increasing.

Note the given proof actually contains two edge proofs. Both of them can be non-existent proofs. For example the first proof is for a non-existent key 0x03, the last proof is for a non-existent key 0x10. The given batch leaves are [0x04, 0x05, .. 0x09]. It's still feasible to prove the given batch is valid.

The firstKey is paired with firstProof, not necessarily the same as keys[0] (unless firstProof is an existent proof). Similarly, lastKey and lastProof are paired.

Expect the normal case, this function can also be used to verify the following range proofs:

  • All elements proof. In this case the proof can be nil, but the range should be all the leaves in the trie.
  • One element proof. In this case no matter the edge proof is a non-existent proof or not, we can always verify the correctness of the proof.
  • Zero element proof. In this case a single non-existent proof is enough to prove. Besides, if there are still some other leaves available on the right side, then an error will be returned.

Except returning the error to indicate the proof is valid or not, the function will also return a flag to indicate whether there exists more accounts/slots in the trie.

Note: This method does not verify that the proof is of minimal form. If the input proofs are 'bloated' with neighbour leaves or random data, aside from the 'useful' data, then the proof will still be accepted.

Types

type Config 

type Config struct {
	Cache     int    // 用于在内存中缓存trie节点的内存余量（MB）
	Journal   string // 节点重新启动后的清除缓存日志
	Preimages bool   // 标记是否记录trie键的前图像
}

Config定义数据库的所有必要选项。

type LeafCallback 

type LeafCallback func(paths [][]byte, hexpath []byte, leaf []byte, parent entity.Hash) error

LeafCallback 是当trie操作到达叶节点时调用的回调类型。 路径是一个路径元组，用于标识单个trie（帐户）或分层trie（帐户->存储）中的特定trie节点。元组中的每个路径都是原始格式（32字节）。 hexpath是标识trie节点的复合hexary路径。如果trie节点位于分层trie中，则所有密钥字节都将转换为六进制半字节，并与父路径合成。 状态同步和提交使用它来处理帐户和存储尝试之间的外部引用。在状态修复中，它还用于提取具有相应路径的原始状态（叶节点）。

type MissingNodeError 

type MissingNodeError struct {
	Owner    entity.Hash // trie的所有者（如果是2层trie）
	NodeHash entity.Hash // 缺少节点的哈希
	Path     []byte      // 缺少节点的十六进制编码路径
	// contains filtered or unexported fields
}

如果本地数据库中不存在trie节点，则trie函数（TryGet、TryUpdate、TryDelete）将返回MissingNodeError。它包含检索丢失节点所需的信息。

func (*MissingNodeError) Error 

func (err *MissingNodeError) Error() string

func (*MissingNodeError) Unwrap 

func (err *MissingNodeError) Unwrap() error

Unwrap返回缺少trie节点的具体错误，以便我们在外部进行进一步分析。

type SecureTrie 

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

SecureTrie对于并发使用不安全。

func NewSecure 

func NewSecure(owner entity.Hash, root entity.Hash, db *TrieDatabase) (*SecureTrie, error)

NewSecure使用备份数据库中的现有根节点和内存节点池中的可选中间节点创建一个trie。 如果root是空字符串的零哈希或sha3哈希，则trie最初为空。 否则，如果db为nil，New将死机，如果找不到根节点，则返回MissingNodeError。 访问trie会根据需要从数据库或节点池加载节点。加载的节点将一直保留到其“缓存生成”过期。 每次调用提交都会创建一个新的缓存生成。cachelimit设置要保留的过去缓存生成数。

func (*SecureTrie) Commit 

func (t *SecureTrie) Commit(onleaf LeafCallback) (entity.Hash, int, error)

Commit 将所有节点和安全哈希预映像写入trie的数据库。节点以其sha3哈希作为密钥进行存储。提交会刷新内存中的节点。后续的Get调用将从数据库加载节点。

func (*SecureTrie) Copy 

func (t *SecureTrie) Copy() *SecureTrie

Copy返回SecureTrie的副本。

func (*SecureTrie) GetKey 

func (s *SecureTrie) GetKey(bytes []byte) ([]byte, error)

func (*SecureTrie) Hash 

func (s *SecureTrie) Hash() entity.Hash

func (*SecureTrie) Prove 

func (t *SecureTrie) Prove(key []byte, fromLevel uint, proofDb typedb.KeyValueWriter) 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 (*SecureTrie) TryDelete 

func (s *SecureTrie) TryDelete(key []byte) error

func (*SecureTrie) TryGet 

func (s *SecureTrie) TryGet(key []byte) ([]byte, error)

func (*SecureTrie) TryGetNode 

func (t *SecureTrie) TryGetNode(path []byte) ([]byte, int, error)

TryGetNode尝试通过压缩编码路径检索trie节点。由于路径可能包含奇数个半字节，因此无法使用密钥字节编码。

func (*SecureTrie) TryUpdate 

func (s *SecureTrie) TryUpdate(key, value []byte) error

func (*SecureTrie) TryUpdateAccount 

func (s *SecureTrie) TryUpdateAccount(key []byte, account *entity.StateAccount) error

type StackTrie 

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

StackTrie是一种trie实现，它期望按顺序插入密钥。 一旦确定不再插入子树，它将对其进行哈希运算并释放所使用的内存。

func NewStackTrie 

func NewStackTrie(db typedb.KeyValueWriter) *StackTrie

NewStackTrie分配并初始化空trie。

func NewStackTrieWithOwner 

func NewStackTrieWithOwner(db typedb.KeyValueWriter, owner entity.Hash) *StackTrie

NewStackTrieWithOwner分配并初始化一个空的trie，但带有额外的owner字段。

func (*StackTrie) Commit 

func (st *StackTrie) Commit() (h entity.Hash, err error)

如果entrie trie仍然没有散列，Commit将首先对其进行散列，然后将所有节点提交到相关数据库。 实际上，大多数trie节点可能已经提交。这里的主要目的是提交根节点。需要关联的数据库，否则应禁用整个提交功能。

func (*StackTrie) Hash 

func (st *StackTrie) Hash() (h entity.Hash)

func (*StackTrie) Reset 

func (st *StackTrie) Reset()

func (*StackTrie) TryUpdate 

func (st *StackTrie) TryUpdate(key, value []byte) error

TryUpdate将（键，值）对插入堆栈trie

func (*StackTrie) Update 

func (st *StackTrie) Update(key []byte, value []byte)

type Sync 

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

Sync is the nodeentity 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.

func NewSync 

func NewSync(root entity.Hash, database typedb.KeyValueReader, callback LeafCallback) *Sync

NewSync creates a new trie data download scheduler.

func (*Sync) AddCodeEntry 

func (s *Sync) AddCodeEntry(hash entity.Hash, path []byte, parent entity.Hash)

AddCodeEntry schedules the direct retrieval of a contract code that should not be interpreted as a trie node, but rather accepted and stored into the database as is.

func (*Sync) AddSubTrie 

func (s *Sync) AddSubTrie(root entity.Hash, path []byte, parent entity.Hash, callback LeafCallback)

AddSubTrie registers a new trie to the sync code, rooted at the designated parent.

func (*Sync) Commit 

func (s *Sync) Commit(dbw typedb.Batch) error

Commit flushes the data stored in the internal membatch out to persistent storage, returning any occurred error.

func (*Sync) Missing 

func (s *Sync) Missing(max int) (nodes []entity.Hash, paths []SyncPath, codes []entity.Hash)

Missing retrieves the known missing nodes from the trie for retrieval. To aid both eth/6x style fast sync and snap/1x style state sync, the paths of trie nodes are returned too, as well as separate hash list for codes.

func (*Sync) Pending 

func (s *Sync) Pending() int

Pending returns the number of state entries currently pending for download.

func (*Sync) Process 

func (s *Sync) Process(result SyncResult) error

Process injects the received data for requested item. Note it can happpen that the single response commits two pending requests(e.g. there are two requests one for code and one for node but the hash is same). In this case the second response for the same hash will be treated as "non-requested" item or "already-processed" item but there is no downside.

type SyncPath 

type SyncPath [][]byte

SyncPath is a path tuple identifying a particular trie node either in a single trie (account) or a layered trie (account -> storage).

Content wise the tuple either has 1 element if it addresses a node in a single trie or 2 elements if it addresses a node in a stacked trie.

To support aiming arbitrary trie nodes, the path needs to support odd nibble lengths. To avoid transferring expanded hex form over the network, the last part of the tuple (which needs to index into the middle of a trie) is compact encoded. In case of a 2-tuple, the first item is always 32 bytes so that is simple binary encoded.

Examples:

  • Path 0x9 -> {0x19}
  • Path 0x99 -> {0x0099}
  • Path 0x01234567890123456789012345678901012345678901234567890123456789019 -> {0x0123456789012345678901234567890101234567890123456789012345678901, 0x19}
  • Path 0x012345678901234567890123456789010123456789012345678901234567890199 -> {0x0123456789012345678901234567890101234567890123456789012345678901, 0x0099}

func NewSyncPath 

func NewSyncPath(path []byte) SyncPath

NewSyncPath converts an expanded trie path from nibble form into a compact version that can be sent over the network.

type SyncResult 

type SyncResult struct {
	Hash entity.Hash // Hash of the originally unknown trie node
	Data []byte      // Data content of the retrieved node
}

SyncResult is a response with requested data along with it's hash.

type Trie 

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

Trie是Merkle Patricia Trie。零值是没有数据库的空trie。 使用New创建位于数据库顶部的trie。同时使用Trie不安全。

func New 

func New(owner entity.Hash, root entity.Hash, db *TrieDatabase) (*Trie, error)

New使用db中的现有根节点创建trie。 如果root是空字符串的零哈希或sha3哈希，则trie最初为空，不需要数据库。 否则，如果db为nil，New将死机，如果数据库中不存在root，则返回MissingNodeError。 访问trie会根据需要从db加载节点。

func NewEmpty 

func NewEmpty(db *TrieDatabase) *Trie

NewEmpty是创建空树的快捷方式。它主要用于测试。

func NewTrie 

func NewTrie(owner entity.Hash, root entity.Hash, db *TrieDatabase) (*Trie, error)

New使用db中的现有根节点和为存储邻近性分配的所有者创建trie。如果root是空字符串的零散列或sha3散列，则trie最初为空，不需要数据库。 否则，如果db为nil，New将死机，如果数据库中不存在根，则返回MissingNodeError。 访问trie会根据需要从db加载节点。

func (*Trie) Commit 

func (t *Trie) Commit(onleaf LeafCallback) (entity.Hash, int, error)

Commit将所有节点写入trie的内存数据库，跟踪内部和外部（用于帐户尝试）引用。

func (*Trie) Copy 

func (t *Trie) Copy() *Trie

Copy返回Trie的副本。

func (*Trie) Hash 

func (t *Trie) Hash() entity.Hash

哈希返回trie的根哈希。它不会写入数据库，即使trie没有数据库，也可以使用它。

func (*Trie) Prove 

func (t *Trie) Prove(key []byte, fromLevel uint, proofDb typedb.KeyValueWriter) 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) Reset 

func (t *Trie) Reset()

重置将删除引用的根节点并清除所有内部状态。

func (*Trie) TryDelete 

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

TryDelete从trie中删除key的任何现有值。如果在数据库中未找到节点，则返回MissingNodeError。

func (*Trie) TryGet 

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

TryGet返回存储在trie中的键的值。调用者不得修改值字节。如果在数据库中找不到节点，则返回MissingNodeError。

func (*Trie) TryGetNode 

func (t *Trie) TryGetNode(path []byte) ([]byte, int, error)

TryGetNode尝试通过压缩编码路径检索trie节点。由于路径可能包含奇数个半字节，因此无法使用密钥字节编码。

func (*Trie) TryUpdate 

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

TryUpdate将键与trie中的值相关联。对Get的后续调用将返回值。 如果值的长度为零，则会从trie中删除任何现有值，并且对Get的调用将返回nil。 值字节存储在trie中时，调用者不得修改它们。如果在数据库中找不到节点，则返回MissingNodeError。

func (*Trie) Update 

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

更新将键与trie中的值相关联。对Get的后续调用将返回值。 如果值的长度为零，则从trie中删除任何现有值，并且对Get的调用将返回nil。 值字节存储在trie中时，调用者不得修改它们。

type TrieDatabase 

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

数据库是trie数据结构和磁盘数据库之间的中间写入层。 其目的是在内存中累积trie写操作，并且只定期刷新几次磁盘尝试，对剩余的进行垃圾收集。 注意，trie数据库在其突变中**不是**线程安全的，但在提供单独、独立的节点访问时**是**线程安全的。 这种拆分设计的基本原理是，即使在trie执行昂贵的垃圾收集时，也可以提供对RPC处理程序和同步服务器的读取访问。

func NewTrieDatabase 

func NewTrieDatabase(diskdb typedb.KeyValueStore) *TrieDatabase

NewDatabase创建一个新的trie数据库来存储临时trie内容，然后再将其写入磁盘或进行垃圾回收。 没有创建读缓存，因此所有数据检索都将命中底层磁盘数据库。

func TrieNewDatabaseWithConfig 

func TrieNewDatabaseWithConfig(diskdb typedb.KeyValueStore, config *Config) *TrieDatabase

NewDatabaseWithConfig创建一个新的trie数据库来存储临时trie内容，然后再将其写入磁盘或进行垃圾回收。 它还充当从磁盘加载的节点的读缓存。

func (*TrieDatabase) Cap 

func (db *TrieDatabase) Cap(limit utils.StorageSize) error

Cap迭代刷新旧但仍引用的trie节点，直到总内存使用量低于给定阈值。 注意，该方法是一个非同步的变异器。将其与其他变异子同时调用是不安全的。

func (*TrieDatabase) Commit 

func (db *TrieDatabase) Commit(node entity.Hash, report bool, callback func(entity.Hash)) error

Commit对特定节点的所有子节点进行迭代，并将其写入磁盘，强制从两个方向删除所有引用。 作为一种副作用，也会写入到目前为止积累的所有预图像。 注意，这个方法是一个非同步的变异器。将其与其他突变同时调用是不安全的。

func (*TrieDatabase) Dereference 

func (db *TrieDatabase) Dereference(root entity.Hash)

取消引用从根节点删除现有引用。

func (*TrieDatabase) DiskDB 

func (db *TrieDatabase) DiskDB() typedb.KeyValueStore

DiskDB 检索支持trie数据库的持久存储。

func (*TrieDatabase) Node 

func (db *TrieDatabase) Node(hash entity.Hash) ([]byte, error)

节点从内存中检索编码的缓存trie节点。如果找不到缓存，该方法将查询持久数据库中的内容。

func (*TrieDatabase) Reference 

func (db *TrieDatabase) Reference(child entity.Hash, parent entity.Hash)

引用将新引用从父节点添加到子节点。 此函数用于在内部trie节点和外部节点（例如存储trie根）之间添加引用，所有内部trie节点由数据库本身一起引用。

func (*TrieDatabase) SaveCache 

func (db *TrieDatabase) SaveCache(dir string) error

SaveCache使用所有可用的CPU核将快速缓存数据自动保存到给定的目录。

func (*TrieDatabase) Size 

func (db *TrieDatabase) Size() (utils.StorageSize, utils.StorageSize)

Size返回持久数据库层前面的内存缓存的当前存储大小。

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.