trie树的keys使用三种不同的编码方式进行编码：
- KEYBYTES encoding：只包含实际的key，这种编码方式用于编码大多数API接口
- HEX encoding：这种编码格式每一个字节包含了Key的一个半字节，尾部接上一个可选的’终结符’,'终结符’代表这个节点到底是叶子节点还是扩展节点。十六进制键编码用于加载在内存中的节点，因为它方便访问
- COMPACT encoding：这种编码格式就是源码阅读3里面的紧凑编码/十六进制前缀编码，这种编码格式可以看成是HEX encoding这种编码格式的另外一种版本，可以在存储到数据库的时候节约磁盘空间。
func hexToCompact(hex []byte) []byte {
terminator := byte(0)
//判断十六进制的key是否包含终止符16
if hasTerm(hex) {
terminator = 1
//去除尾部的终止符
hex = hex[:len(hex)-1]
}
//创建缓冲区buf
buf := make([]byte, len(hex)/2+1)
//0010 0000，设置为叶子节点
buf[0] = terminator << 5 // the flag byte
//len(hex)&1，由于1前面都是0，相当于用len（hex）的二进制数值和0001进行与操作，
//这个用于校验hex的长度是否为偶数，真等于1说明为奇数
if len(hex)&1 == 1 {
//0010 0000 | 0001 0000 == 0011 0000
buf[0] |= 1 << 4 // 设置为奇数标志
buf[0] |= hex[0] // hex[0]为压缩路径的第一个路径，将hex[0]拼接到0011 的后面
hex = hex[1:] //hex后移，方便取出下一个元素
}
//解析hex
decodeNibbles(hex, buf[1:])
return buf
}
func compactToHex(compact []byte) []byte {
if len(compact) == 0 {
return compact
}
base := keybytesToHex(compact)
// delete terminator flag
//判断为扩展节点
if base[0] < 2 {
//去除(十进制的16)结束标记，该标记由keybytesToHex带来
base = base[:len(base)-1]
}
// apply odd flag
//base[0]&0001 用来判断是否为奇数，是奇数该运算(&)结果为1，否则为0
chop := 2 - base[0]&1
// 将前缀（0011之类的经过十六进制前缀编码后的数据）移除，后面的就是真正的数据
//HP编码种，奇数个 nibble，前缀是1位，偶数则为两位，具体可见 “Hex序列的压缩编码规则” 那个部分
return base[chop:]
}
hex和keybytes的相互转换：
func keybytesToHex(str []byte) []byte {
l := len(str)*2 + 1
var nibbles = make([]byte, l)
//转换为16进制，和10进制转16进制一样
for i, b := range str {
nibbles[i*2] = b / 16
nibbles[i*2+1] = b % 16
}
nibbles[l-1] = 16
return nibbles
}
// hexToKeybytes 将十六进制转为key字节。这只能用于偶数长度的键。
func hexToKeybytes(hex []byte) []byte {
//判断是否含有终止符（16），有的话去除
if hasTerm(hex) {
hex = hex[:len(hex)-1]
}
//长度为奇数，无法转换
if len(hex)&1 != 0 {
panic("can't convert hex key of odd length")
}
key := make([]byte, len(hex)/2)
//将hex转换后塞到key中
decodeNibbles(hex, key)
return key
}
注：源码中似乎没有COMPACT转keybytes的部分
- keybytes为按完整字节（8bit）存储的正常信息
- hex为按照半字节nibble（4bit）储存信息的格式。供compact使用
- 为了便于作黄皮书中Modified Merkle Patricia Tree的节点的key，编码为偶数字节长度的hex格式。其第一个半字节nibble会在低的2个bit位中，由高到低分别存放t标志与奇数标志。经compact编码的keybytes，在增加了hex的t标志与半字节nibble为偶数个（即完整的字节）的情况下，便于存储
node的结构，可以看到node分为4种类型：
- fullNode对应了黄皮书里面的分支节点
- shortNode对应了黄皮书里面的扩展节点和叶子节点(通过shortNode.Val的类型来判断当前节点是叶子节点(shortNode.Val为valueNode)还是拓展节点(通过shortNode.Val指向下一个node))。
- hashNode用于指向下一个节点
- valueNode存储value
type (
fullNode struct {
Children [17]node // 在MPT数中需要进行编码和解码（需要自己设定编码器和解码器）
flags nodeFlag
}
shortNode struct {
Key []byte
Val node
flags nodeFlag
}
hashNode []byte
valueNode []byte
)
其余部分为对节点的编码、解码、设置cache等
trie.go MPT树 结构定义type Trie struct {
db *Database
root node
unhashed int
}
- trie的结构， root包含了当前的root节点
- db是后端的KV存储，trie的结构最终都是需要通过KV的形式存储到数据库里面去，然后启动的时候是需要从数据库里面加载的。
- unhashed用于跟踪上一个被插入的叶子节点，这个数字不会映射到实际的unhashed nodes
Trie树的初始化调用New函数，函数接受一个hash值和一个Database参数，如果hash值不是空值的话，就说明是从数据库加载一个已经存在的Trie树， 就调用trei.resolveHash方法来加载整颗Trie树，这个方法后续会介绍。 如果root是空，那么就新建一颗Trie树返回。
func New(root common.Hash, db *Database) (*Trie, error) {
if db == nil {
panic("trie.New called without a database")
}
//创建树
trie := &Trie{
db: db,
}
//root非空则从数据库中加载
if root != (common.Hash{}) && root != emptyRoot {
rootnode, err := trie.resolveHash(root[:], nil)
if err != nil {
return nil, err
}
trie.root = rootnode
}
return trie, nil
}
Trie树的插入，这是一个递归调用的方法，从根节点开始，一直往下找，直到找到可以插入的点，进行插入操作。参数node是当前插入的节点， prefix是当前已经处理完的部分key， key是还没有处理玩的部分key, 完整的key = prefix + key。 value是需要插入的值。 返回值bool是操作是否改变了Trie树(dirty)，node是插入完成后的子树的根节点， error是错误信息。
insert使用切面截取后面的部分
func (t *Trie) insert(n node, prefix, key []byte, value node) (bool, node, error) {
//key要求非空
if len(key) == 0 {
if v, ok := n.(valueNode); ok {
return !bytes.Equal(v, value.(valueNode)), value, nil
}
return true, value, nil
}
switch n := n.(type) {
case *shortNode:
matchlen := prefixLen(key, n.Key)
//如果整个键匹配，则保持这个短节点不变
// 并且只更新值。
if matchlen == len(n.Key) {
dirty, nn, err := t.insert(n.Val, append(prefix, key[:matchlen]...), key[matchlen:], value)
if !dirty || err != nil {
return false, n, err
}
//如果没有错误就更新shortNode的值然后返回。
return true, &shortNode{n.Key, nn, t.newFlag()}, nil
}
branch := &fullNode{flags: t.newFlag()}
var err error
//然后再branch节点的Children位置调用t.insert插入剩下的两个short节点。
_, branch.Children[n.Key[matchlen]], err = t.insert(nil, append(prefix, n.Key[:matchlen+1]...), n.Key[matchlen+1:], n.Val)
if err != nil {
return false, nil, err
}
_, branch.Children[key[matchlen]], err = t.insert(nil, append(prefix, key[:matchlen+1]...), key[matchlen+1:], value)
if err != nil {
return false, nil, err
}
// 如果这个shornode出现在索引0处，则用分支替换它。
if matchlen == 0 {
return true, branch, nil
}
// 否则，将其替换为一个通向分支的短节点。
return true, &shortNode{key[:matchlen], branch, t.newFlag()}, nil
case *fullNode:
//如果当前的节点是fullNode(也就是branch节点)，
//那么直接往对应的孩子节点调用insert方法,然后把对应的孩子节点只想新生成的节点。
dirty, nn, err := t.insert(n.Children[key[0]], append(prefix, key[0]), key[1:], value)
if !dirty || err != nil {
return false, n, err
}
n = n.copy()
n.flags = t.newFlag()
n.Children[key[0]] = nn
return true, n, nil
case nil:
return true, &shortNode{key, value, t.newFlag()}, nil
case hashNode:
//如果当前节点是hashNode, hashNode的意思是当前节点还没有加载到内存里面来，
//还是存放在数据库里面，那么首先调用 t.resolveHash(n, prefix)来加载到内存，
//然后对加载出来的节点调用insert方法来进行插入。
rn, err := t.resolveHash(n, prefix)
if err != nil {
return false, nil, err
}
dirty, nn, err := t.insert(rn, prefix, key, value)
if !dirty || err != nil {
return false, rn, err
}
return true, nn, nil
default:
panic(fmt.Sprintf("%T: invalid node: %v", n, n))
}
}
借助pos来递归地寻找合适的key
func (t *Trie) tryGet(origNode node, key []byte, pos int) (value []byte, newnode node, didResolve bool, err error) {
switch n := (origNode).(type) {
case nil:
return nil, nil, false, nil
case valueNode:
return n, n, false, nil
case *shortNode:
if len(key)-pos < len(n.Key) || !bytes.Equal(n.Key, key[pos:pos+len(n.Key)]) {
// key not found in trie
return nil, n, false, nil
}
value, newnode, didResolve, err = t.tryGet(n.Val, key, pos+len(n.Key))
if err == nil && didResolve {
n = n.copy()
n.Val = newnode
}
return value, n, didResolve, err
case *fullNode:
value, newnode, didResolve, err = t.tryGet(n.Children[key[pos]], key, pos+1)
if err == nil && didResolve {
n = n.copy()
n.Children[key[pos]] = newnode
}
return value, n, didResolve, err
case hashNode:
child, err := t.resolveHash(n, key[:pos])
if err != nil {
return nil, n, true, err
}
value, newnode, _, err := t.tryGet(child, key, pos)
return value, newnode, true, err
default:
panic(fmt.Sprintf("%T: invalid node: %v", origNode, origNode))
}
}
go使用切片的截取来进行delete操作，主要是截取前面的部分
func (t *Trie) delete(n node, prefix, key []byte) (bool, node, error) {
switch n := n.(type) {
case *shortNode:
matchlen := prefixLen(key, n.Key)
if matchlen < len(n.Key) {
return false, n, nil // don't replace n on mismatch
}
if matchlen == len(key) {
return true, nil, nil // remove n entirely for
dirty, child, err := t.delete(n.Val, append(prefix, key[:len(n.Key)]...), key[len(n.Key):])
if !dirty || err != nil {
return false, n, err
}
switch child := child.(type) {
case *shortNode:
return true, &shortNode{concat(n.Key, child.Key...), child.Val, t.newFlag()}, nil
default:
return true, &shortNode{n.Key, child, t.newFlag()}, nil
}
case *fullNode:
dirty, nn, err := t.delete(n.Children[key[0]], append(prefix, key[0]), key[1:])
if !dirty || err != nil {
return false, n, err
}
n = n.copy()
n.flags = t.newFlag()
n.Children[key[0]] = nn
if nn != nil {
return true, n, nil
}
pos := -1
for i, cld := range &n.Children {
if cld != nil {
if pos == -1 {
pos = i
} else {
pos = -2
break
}
}
}
if pos >= 0 {
if pos != 16 {
cnode, err := t.resolve(n.Children[pos], prefix)
if err != nil {
return false, nil, err
}
if cnode, ok := cnode.(*shortNode); ok {
k := append([]byte{byte(pos)}, cnode.Key...)
return true, &shortNode{k, cnode.Val, t.newFlag()}, nil
}
}
// Otherwise, n is replaced by a one-nibble short node
// containing the child.
return true, &shortNode{[]byte{byte(pos)}, n.Children[pos], t.newFlag()}, nil
}
// n still contains at least two values and cannot be reduced.
return true, n, nil
case valueNode:
return true, nil, nil
case nil:
return false, nil, nil
case hashNode:
rn, err := t.resolveHash(n, prefix)
if err != nil {
return false, nil, err
}
dirty, nn, err := t.delete(rn, prefix, key)
if !dirty || err != nil {
return false, rn, err
}
return true, nn, nil
default:
panic(fmt.Sprintf("%T: invalid node: %v (%v)", n, n, key))
}
}
proof.go Trie树的默克尔证明
Prove为key构造默克尔证明。结果包含到key处值路径上的所有编码节点。值本身也包含在最后一个节点中，可以通过验证证明来检索。
如果trie不包含key的值，则返回的证明包含该键现有最长前缀的所有节点(至少是根节点)，以证明该键不存在的节点结束。
func (t *Trie) Prove(key []byte, fromLevel uint, proofDb ethdb.KeyValueWriter) error {
// Collect all nodes on the path to key.
key = keybytesToHex(key)
var nodes []node
tn := t.root
//Prove方法，从根节点开始。把经过的节点的hash值一个一个存入到[]byte中。然后返回。
for len(key) > 0 && tn != nil {
//根据tn的类型进行分发
switch n := tn.(type) {
case *shortNode:
if len(key) < len(n.Key) || !bytes.Equal(n.Key, key[:len(n.Key)]) {
// trie中不包含key
tn = nil
} else {
tn = n.Val
key = key[len(n.Key):]
}
nodes = append(nodes, n)
case *fullNode:
tn = n.Children[key[0]]
key = key[1:]
nodes = append(nodes, n)
case hashNode:
var err error
tn, err = t.resolveHash(n, nil)
if err != nil {
log.Error(fmt.Sprintf("Unhandled trie error: %v", err))
return err
}
default:
panic(fmt.Sprintf("%T: invalid node: %v", tn, tn))
}
}
hasher := newHasher(false)
defer returnHasherToPool(hasher)
for i, n := range nodes {
if fromLevel > 0 {
fromLevel--
continue
}
var hn node
n, hn = hasher.proofHash(n)
if hash, ok := hn.(hashNode); ok || i == 0 {
// If the node's database encoding is a hash (or is the
// root node), it becomes a proof element.
enc := nodeToBytes(n)
if !ok {
hash = hasher.hashData(enc)
}
proofDb.Put(hash, enc)
}
}
return nil
}
VerifyProof检查默克尔证明。给定的证明必须包含key在给定的根哈希中的值。如果验证包含无效的trie节点或错误的值，VerifyProof将返回一个错误。
func VerifyProof(rootHash common.Hash, key []byte, proofDb ethdb.KeyValueReader) (value []byte, err error) {
key = keybytesToHex(key)
wantHash := rootHash
for i := 0; ; i++ {
buf, _ := proofDb.Get(wantHash[:])
if buf == nil {
return nil, fmt.Errorf("proof node %d (hash %064x) missing", i, wantHash)
}
n, err := decodeNode(wantHash[:], buf)
if err != nil {
return nil, fmt.Errorf("bad proof node %d: %v", i, err)
}
keyrest, cld := get(n, key, true)
switch cld := cld.(type) {
case nil:
// The trie doesn't contain the key.
return nil, nil
case hashNode:
key = keyrest
copy(wantHash[:], cld)
case valueNode:
return cld, nil
}
}
}
security_trie.go 加密的Trie
为了避免刻意使用很长的key导致访问时间的增加， security_trie包装了一下trie树， 所有的key都转换成keccak256算法计算的hash值。同时在数据库里面存储hash值对应的原始的key。
type SecureTrie struct {
trie Trie//原始的Trie树
hashKeyBuf [common.HashLength]byte//计算hash值的buf
secKeyCache map[string][]byte//记录hash值和对应的key的映射
secKeyCacheOwner *SecureTrie // Pointer to self, replace the key cache on mismatch
}
Commit将所有节点和安全哈希预映像写入到trie的数据库。节点以其sha3哈希值作为密钥存储。提交将从内存中刷新节点。随后的Get调用将从数据库加载节点。
func (t *SecureTrie) Commit(onleaf LeafCallback) (common.Hash, int, error) {
// Write all the pre-images to the actual disk database
if len(t.getSecKeyCache()) > 0 {
if t.trie.db.preimages != nil { // Ugly direct check but avoids the below write lock
t.trie.db.lock.Lock()
for hk, key := range t.secKeyCache {
t.trie.db.insertPreimage(common.BytesToHash([]byte(hk)), key)
}
t.trie.db.lock.Unlock()
}
t.secKeyCache = make(map[string][]byte)
}
// Commit the trie to its intermediate node database
return t.trie.Commit(onleaf)
}
Trie树的使用
Trie树的使用方法 : 首先创建一个空的Trie树，然后插入一些数据，最后调用trie.Hash()方法进行序列化并得到一个hash值(root), 也就是上图中的KEC(c(J,0))或者是TRIE(J)。
func TestInsert(t *testing.T) {
trie := newEmpty()
updateString(trie, "doe", "reindeer")
updateString(trie, "dog", "puppy")
updateString(trie, "dogglesworth", "cat")
exp := common.HexToHash("8aad789dff2f538bca5d8ea56e8abe10f4c7ba3a5dea95fea4cd6e7c3a1168d3")
root := trie.Hash()
if root != exp {
t.Errorf("case 1: exp %x got %x", exp, root)
}
}
这里的hash实际上只是做了类型转换
func (t *Trie) Hash() common.Hash {
hash, cached, _ := t.hashRoot()
t.root = cached
return common.BytesToHash(hash.(hashNode))
}
func BytesToHash(b []byte) Hash {
var h Hash
h.SetBytes(b)
return h
}
