结构体数组在Ethereum的世界里，数据的最终存储形式是[(7)

h:=newHasher(t.cachegen,t.cachelimit)

returnh.hash(t.root,db,force:true)

}

hashRoot()函数内部调用Hasher结构体进行折叠操作：

//trie/hasher.go

func(h*hasher)hash(nnode,dbDatabaseWriter,forcebool)(hashnode,cachednode,error)

func(h*hasher)hashChildren(originalnode,dbDatabaseWriter)(hashnode,cachednode,error)

func（h*hasher）store(nnode,dbDatabaseWriter,forcebool)(node,error)

折叠node的入口是hasher.hash()，在执行中，hash()和hashChiildren()相互调用以遍历整个MPT结构，store()对节点作RLP哈希计算。折叠node的基本逻辑是：如果node没有子节点，那么直接返回；如果这个node带有子节点，那么首先将子节点折叠成hashNode。当这个node的子节点全都变成哈希值hashNode之后，再对这个node作RLP+哈希计算，得到它的哈希值，亦即hashNode。

注意到hash()和hashChildren()返回两个node类型对象，第一个@hash是入参n经过折叠的hashNode哈希值，第二个@cached是没有经过折叠的n，并且n的hashNode还被赋值了。

由于Hasher.hash()有一个接口类型的参数，这样在折叠MPT过程中，如果db不为空，就把每次计算hashNode时的哈希值和它对应的节点RLP编码值一起存进里，这也正是Commit()的逻辑。

func(t*Trie)Commit()(roothash,error){

ift.db==nil{…}

returnt.CommitTo(t.db)

}

func(t*Trie)CommitTo(dbDatabaseWriter)(rootcommon.Hash,error){

hash,cached,error:=t.hashRoot(db)

t.root=cached

…

}

回看一下Trie.Hash()，它在调用hashRoot()时，传入的是空值db。只有显式调用Commit()或者CommitTo()才可以提交数据，所以Hash()多次调用也是安全的。

在MPT的查找，插入，删除中，如果遍历过程中遇到一个hashNode，首先需要从里以这个哈希值为k，读取出相匹配的v，然后再将v解码恢复成fullNode或shortNode。在代码中这个过程叫resolve。

//trie/trie.go

func(t*trie)resolve(n,prefix)(node,error){

ifn,ok:=n.(hashNode);ok{

returnresolveHash(n,prefix)

}

returnn,nil

}

func(t*Trie)resolveHash(nhashNode,prefix[]byte)(node,error){

enc,err:=t.db.Get(n)

…

dec:=mustDecodeNode(n,enc,t.cachegen)

returndec,nil

}

这样，涉及到hashNode的所有操作就基本完整了。

MPT中对key的编码

当[k,v]数据插入MPT时，它们的k(key)都必须经过编码。这时对key的编码，要保证原本是[]byte类型的key能够以16进制形式按位进入fullNode.Children[]，因为Children[]数组最多只能容纳16个子节点。相应的，Ethereum代码中在这里定义了一种编码方式叫Hex，将1byte的字符大小限制在4bit(16进制)以内。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-69032-7.html