阅读 go-ethereum 源码 - 4

Trie.go (Merkle-patricia-tree )

Merkle Patricia Tree(简称MPT树，实际上是一种trie前缀树)是以太坊中的一种加密认证的数据结构，可以用来存储所有的(key，value)对。

以太坊区块链中的区块由标题，交易列表和叔区块列表组成。区块头中包含交易的根哈希，它用于验证交易列表。在区块头部包括了交易的hash树根，用来校验交易的列表。在p2p网络上传输的交易是一个简单的列表，它们被组装成一个叫做trie树的特殊数据结构，来计算根hash。值得注意的是，除了校验区块外，这个数据结构并不是必须的，一旦区块被验证正确，那么它在技术上是可以忽略的。但是，这意味着交易列表在本地以trie树的形式存储，发送给客户端的时候序列化成列表。客户端接收到交易列表后重新构建交易列表trie树来验证根hash。RLP(Recursive length prefix encoding,递归长度前缀编码)，用来对trie树种所有的条目进行编码。对RLP的介绍和源码实现阅读可参考阅读 go-ethereum 源码 - 2 。

Merkle Patricia Tree的Wiki可在https://github.com/ethereum/wiki/wiki/Patricia-Tree查看。

go-ethereum源码中对MPT数的处理时在文件 **trie.go **中。
进入go-ethereum 源码查看trie.go .

git checkout 9f133a92d0853102863b77dd7c884d1462cf73a4

或通过如下方式在线浏览：

https://github.com/ethereum/go-ethereum/blob/9f133a92d0853102863b77dd7c884d1462cf73a4/trie.go

注意：

在MPT的wiki中制定，树的Merkle部分是一个节点的确定性加密的hash。该hash 为 rlp编码的value值的sha3.

The "Merkle" part of the radix trie arises in the fact that a deterministic cryptographic hash of a node is used as the pointer to the node (for every lookup in the key/value DB key == sha3(rlp(value)), rather than some 32-bit or 64-bit memory location as might happen in a more traditional trie implemented in C.

但在go-ethereum的早期代码中，该hash实现为sha256。所以源码中间的计算结果会不同于wiki。在后续的实现中，go-ethereum 将会改为sha3 。

// Wrapper around the regular db "Put" which generates a key and value
func (t *Trie) Put(node interface{}) []byte {
    enc := Encode(node)     //RLP 编码
    sha := Sha256Bin(enc)   //sha256

    t.db.Put([]byte(sha), enc)

    return sha
}

HP编码

在以太坊（ethereum）中，使用了一种特殊的十六进制前缀(hex-prefix, HP)编码，所以在字母表中就有16个字符。这其中的一个字符为一个nibble。

我们用'\x01\x01\x02'做为key，'hello'作为值存入到trie树中。trie树将将创建一个新的叶节点。并将[hash, rlp(node)]存储在数据库中。

" \x01\x01\x02" hp编码为20010102 。 k编码中后6位为010102，开头两位20为HP编码前缀。第一位2是字符串的标志位,用二进制的表示为0b10.

二进制最后一位表示key的长度是否为偶数（0，1，0，1，0，2），设为0
二进制第一位表示是否终止（终止为1）

0b00 + 0b10 = 0b10 = byte(2)

HP编码后需要为偶数，所以2后再补充一字节 0 ，最终变为[2,0,0,1,0,1,0,2]

相关编码解码的实现在源码 encoding.go 中。

MPT中存储内容结构展示

编写一个简单的展示树结构的代码：


func printNode(root string, n []byte, trie *Trie, intent int) {

    tip := ""
    for i := 0; i < intent; i++ {
        tip += " "
    }
    fmt.Printf(tip+"node hash: %s \n", hex.EncodeToString([]byte(root)))
    // Decode it
    currentNode := DecodeNode(n)

    if len(currentNode) == 0 {
        fmt.Printf(tip+"node valu: %v \n", currentNode)

    } else if len(currentNode) == 2 {
        // Decode the key
        k := CompactDecode(currentNode[0])
        v := currentNode[1]

        length := len(k)
        if length == 0 || k[length-1] == 16 {
            //终止
            fmt.Printf(tip+"node valu: %v %v\n", k, v)
        } else {
            //非终止，v = next node hash
            fmt.Printf(tip+"node valu: %v %s\n", k, hex.EncodeToString([]byte(v)))
            n, err := trie.db.Get([]byte(v))

            if nil == err {
                printNode(v, n, trie, intent+1)
            }

        }

    } else if len(currentNode) == 17 {

        fmt.Printf(tip + "node swch:")
        printSwitchNode(currentNode, trie, intent)
    }

}

func printSwitchNode(slice []string, trie *Trie, intent int) {
    fmt.Printf("[")
    for i, val := range slice {
        //fmt.Printf("%q", val)

        if i != len(slice)-1 {
            fmt.Printf("%s", hex.EncodeToString([]byte(val)))
            fmt.Printf(",")
        } else {
            fmt.Printf("%v", val)
        }
    }
    fmt.Printf("]\n")

    for i, val := range slice {
        //fmt.Printf("%q", val)
        if i != len(slice)-1 {
            if val != "" {
                //下个节点hash
                n, err := trie.db.Get([]byte(val))

                if nil == err {
                    printNode(val, n, trie, intent+1)
                }
            }
        }
    }
}

trie.go的单元测试代码写在trie_test.go 中，我们加入一个新的测试用例。

编写一个测试用例：

func TestTrieUpdate2(t *testing.T) {

    db, err := NewMemDatabase()
    trie := NewTrie(db, "")

    if err != nil {
        t.Error("Error starting db")
    }

    //树中加入<64 6f> ‘do' : 'verb'
    trie.Update("do", "verb")
    n, _ := trie.db.Get([]byte(trie.root))
    printNode(trie.root, n, trie, 0)

}

执行测试：

go test -run TestTrieUpdate2

输出为：

node hash: 40974ec0af4f0e1d466b3e0c6eb8e8c6cb99aa2a349c23b268a5cf65b6221782 
node valu: [6 4 6 15 16] verb

树中再次加入：trie.Update("dog", "puppy")

输出:

node hash: f7ea383e3a2acd742393382c3d5836cf7379b45dbfbc35cd7076001d3bdf51b7 
node valu: [6 4 6 15] 80b3283481f857ad774e1d932cad83a9b1433de221ec468a63cae62eda2a7217
 node hash: 80b3283481f857ad774e1d932cad83a9b1433de221ec468a63cae62eda2a7217 
 node swch:[,,,,,,9aa7cda514c3d6a2b65947dd8fa85f244d037f4572bd22984057a3e345597955,,,,,,,,,,verb]
  node hash: 9aa7cda514c3d6a2b65947dd8fa85f244d037f4572bd22984057a3e345597955 
  node valu: [7 16] puppy

加入: trie.Update("doge", "coin")

输出:

node hash: ca34cb14ee0fb6b039e2c26189442b7dd2f2c1cd575cc896ee49e77108e9e6eb 
node valu: [6 4 6 15] 2a937541cb3a17823d0a2f7adf9d8b355a5240ef99046e0d3485076320b41d7a
 node hash: 2a937541cb3a17823d0a2f7adf9d8b355a5240ef99046e0d3485076320b41d7a 
 node swch:[,,,,,,552cf872957cc9cbf82a53e5b89f37f867685d28105acebba60a03ac7f321147,,,,,,,,,,verb]
  node hash: 552cf872957cc9cbf82a53e5b89f37f867685d28105acebba60a03ac7f321147 
  node valu: [7] da821f38c5d331e760a88ae3a14a42c70618463d4509ff0822ad7014e7b388f0
   node hash: da821f38c5d331e760a88ae3a14a42c70618463d4509ff0822ad7014e7b388f0 
   node swch:[,,,,,,31ffd3d3e73ef63a36f6aaf751e53d8171605db7e13b15cf8525df259739d389,,,,,,,,,,puppy]
    node hash: 31ffd3d3e73ef63a36f6aaf751e53d8171605db7e13b15cf8525df259739d389 
    node valu: [5 16] coin

加入: trie.Update("horse", "stallion")

输出:

node hash: 6529010d2a2f633bfe03e7a3a3503e5a5bccd1ca49989ac0fb195fd022c6cc93 
node valu: [6] 81a164dfe985a4a6f330883c8c713ca48f06976779a0f9fcf43cfe2f2d8872a5
 node hash: 81a164dfe985a4a6f330883c8c713ca48f06976779a0f9fcf43cfe2f2d8872a5 
 node swch:[,,,,7e627874d222eb965ce0bfd13ef518392bc1c39020afb48a5024f1693449e6ad,,,,94c7c69112a354b2beba2f82c4e53f18aface66280be4ea1dd3f778a7917a373,,,,,,,,]
  node hash: 7e627874d222eb965ce0bfd13ef518392bc1c39020afb48a5024f1693449e6ad 
  node valu: [6 15] 2a937541cb3a17823d0a2f7adf9d8b355a5240ef99046e0d3485076320b41d7a
   node hash: 2a937541cb3a17823d0a2f7adf9d8b355a5240ef99046e0d3485076320b41d7a 
   node swch:[,,,,,,552cf872957cc9cbf82a53e5b89f37f867685d28105acebba60a03ac7f321147,,,,,,,,,,verb]
    node hash: 552cf872957cc9cbf82a53e5b89f37f867685d28105acebba60a03ac7f321147 
    node valu: [7] da821f38c5d331e760a88ae3a14a42c70618463d4509ff0822ad7014e7b388f0
     node hash: da821f38c5d331e760a88ae3a14a42c70618463d4509ff0822ad7014e7b388f0 
     node swch:[,,,,,,31ffd3d3e73ef63a36f6aaf751e53d8171605db7e13b15cf8525df259739d389,,,,,,,,,,puppy]
      node hash: 31ffd3d3e73ef63a36f6aaf751e53d8171605db7e13b15cf8525df259739d389 
      node valu: [5 16] coin
  node hash: 94c7c69112a354b2beba2f82c4e53f18aface66280be4ea1dd3f778a7917a373 
  node valu: [6 15 7 2 7 3 6 5 16] stallion

简化显示为：

node hash: hash1 
node valu: [6] hash2
 node hash: hash2 
 node swch:[,,,,hash3,,,,hash4,,,,,,,,]
  node hash: hash3 
  node valu: [6 15] hash5
   node hash: hash5 
   node swch:[,,,,,,hash6,,,,,,,,,,verb]
    node hash: hash6 
    node valu: [7] hash7
     node hash: hash7 
     node swch:[,,,,,,hash8,,,,,,,,,,puppy]
      node hash: hash8 
      node valu: [5 16] coin
  node hash: hash4 
  node valu: [6 15 7 2 7 3 6 5 16] stallion

var hashNum int64 = 0
var hashMap = make(map[string]string)

func clearSimpleHash() {
    hashNum = 0
    hashMap = make(map[string]string)
}
func simpleHash(hash string) string {
    if h, ok := hashMap[hash]; ok {
        return h
    }
    hashNum += 1
    nhash := "hash" + strconv.FormatInt(hashNum, 10)
    hashMap[hash] = nhash
    return nhash
}

原文:http://www.cnspirit.com/2018/04/go-ethereum-4.html