以太坊 Merkle Patricia Trie 是如何工作的

译文出自：登链翻译计划 [1]

译者：aisiji[2]

校对：Tiny 熊 [3]

介绍

Merkle Patricia Trie 是以太坊存储层的关键数据结构之一。我希望了解它到底是如何工作的，于是遍寻资料进行了深入研究，实现了这个算法。

在这篇博文里，我将分享我所学到的东西。解释 Merkle Patricia Trie 究竟是如何工作的，并展示一个 Merkle 证明生成和验证的 demo。

算法的源代码和本博文中使用的例子都是开源的 : https://github.com/zhangchiqing/merkle-patricia-trie

好了，我们开始吧。

一个基本的键-值映射

以太坊的 Merkle Patricia Trie 本质上是一种键值映射，它提供以下标准方法。

    type Trie interface {        // methods as a basic key-value mapping        Get(key []byte) ([]byte, bool) {        Put(key []byte, value []byte)        Del(key []byte, value []byte) bool      }

上述 Trie 接口的实现应该通过以下测试案例。

    func TestGetPut(t *testing.T) {       t.Run("should get nothing if key does not exist", func(t *testing.T) {        trie := NewTrie()       _, found := trie.Get([]byte("notexist"))        require.Equal(t, false, found)       })       t.Run("should get value if key exist", func(t *testing.T) {        trie := NewTrie()        trie.Put([]byte{1, 2, 3, 4}, []byte("hello"))        val, found := trie.Get([]byte{1, 2, 3, 4})        require.Equal(t, true, found)        require.Equal(t, val, []byte("hello"))       })       t.Run("should get updated value", func(t *testing.T) {        trie := NewTrie()        trie.Put([]byte{1, 2, 3, 4}, []byte("hello"))        trie.Put([]byte{1, 2, 3, 4}, []byte("world"))        val, found := trie.Get([]byte{1, 2, 3, 4})        require.Equal(t, true, found)        require.Equal(t, val, []byte("world"))       })      }

(本教程中的测试案例在代码库 [4] 并已经通过了。)

验证数据的完整性

Merkle patricia trie 与标准映射有什么不同？

Merkle patricia trie 允许我们验证数据的完整性 (在本文的其余部分，为了简单起见，我们将称它为 trie。)

我们可以用 Hash 函数计算 trie 的 Merkle root Hash ，如果任何键值对被更新，trie 的 Merkle root Hash 就会不同；如果两个 Trie 有相同的键值对，它们应该有相同的 Merkle root Hash。

    type Trie interface {        // compute the merkle root hash for verifying data integrity        Hash() []byte      }

让我们用一些测试案例来解释这种行为。

    // 验证数据的完整性      func TestDataIntegrity(t *testing.T) {       t.Run("should get a different hash if a new key-value pair was added or updated", func(t *testing.T) {        trie := NewTrie()        hash0 := trie.Hash()        trie.Put([]byte{1, 2, 3, 4}, []byte("hello"))        hash1 := trie.Hash()        trie.Put([]byte{1, 2}, []byte("world"))        hash2 := trie.Hash()        trie.Put([]byte{1, 2}, []byte("trie"))        hash3 := trie.Hash()        require.NotEqual(t, hash0, hash1)        require.NotEqual(t, hash1, hash2)        require.NotEqual(t, hash2, hash3)       })       t.Run("should get the same hash if two tries have the identicial key-value pairs", func(t *testing.T) {        trie1 := NewTrie()        trie1.Put([]byte{1, 2, 3, 4}, []byte("hello"))        trie1.Put([]byte{1, 2}, []byte("world"))        trie2 := NewTrie()        trie2.Put([]byte{1, 2, 3, 4}, []byte("hello"))        trie2.Put([]byte{1, 2}, []byte("world"))        require.Equal(t, trie1.Hash(), trie2.Hash())       })      }

验证是否包含一个键值对

trie 可以验证数据的完整性，但为什么不简单地通过散列整个键值对列表来比较散列，为什么要费力地创建一个 trie 数据结构？

这是因为 trie 还允许我们在不访问整个键值对的情况下验证键值对的包含情况。

这意味着 trie 可以提供一个证明，以证明某个键值对包含在产生某个 merkle 根散列的键值映射中。

    type Proof interface {}      type Trie interface {        // generate a merkle proof for a key-value pair for verifying the inclusion of the key-value pair        Prove(key []byte) (Proof, bool)      }      // verify the proof for the given key with the given merkle root hash      func VerifyProof(rootHash []byte, key []byte, proof Proof) (value []byte, err error)

这在以太坊中是很有用的。例如，设想以太坊的世界状态是一个键值映射，键是每个账户地址，值是每个账户的余额。

作为一个轻客户端，它不像全节点那样可以访问完整的区块链状态，而只是访问某些区块的 Merkle 根哈希值，它怎么能相信全节点返回的账户余额结果？

答案是，一个完整的节点可以提供一个 merkle 证明，其中包含 merkle 根哈希值、账户密钥及其余额值，以及其他数据。这个 merkle 证明允许轻客户通过自己的方式验证正确性，而不需要访问完整的区块链状态。

让我们用测试案例来解释这种行为。

    func TestProveAndVerifyProof(t *testing.T) {       t.Run("should not generate proof for non-exist key", func(t *testing.T) {        tr := NewTrie()        tr.Put([]byte{1, 2, 3}, []byte("hello"))        tr.Put([]byte{1, 2, 3, 4, 5}, []byte("world"))        notExistKey := []byte{1, 2, 3, 4}       _, ok := tr.Prove(notExistKey)        require.False(t, ok)       })       t.Run("should generate a proof for an existing key, the proof can be verified with the merkle root hash", func(t *testing.T) {        tr := NewTrie()        tr.Put([]byte{1, 2, 3}, []byte("hello"))        tr.Put([]byte{1, 2, 3, 4, 5}, []byte("world"))        key := []byte{1, 2, 3}        proof, ok := tr.Prove(key)        require.True(t, ok)        rootHash := tr.Hash()        // verify the proof with the root hash, the key in question and its proof        val, err := VerifyProof(rootHash, key, proof)        require.NoError(t, err)        // when the verification has passed, it should return the correct value for the key        require.Equal(t, []byte("hello"), val)       })       t.Run("should fail the verification if the trie was updated", func(t *testing.T) {        tr := NewTrie()        tr.Put([]byte{1, 2, 3}, []byte("hello"))        tr.Put([]byte{1, 2, 3, 4, 5}, []byte("world"))        // the hash was taken before the trie was updated        rootHash := tr.Hash()        // the proof was generated after the trie was updated        tr.Put([]byte{5, 6, 7}, []byte("trie"))        key := []byte{1, 2, 3}        proof, ok := tr.Prove(key)        require.True(t, ok)        // should fail the verification since the merkle root hash doesn't match       _, err := VerifyProof(rootHash, key, proof)        require.Error(t, err)       })      }

一个轻量级的客户可以要求得到一个 trie 状态的 merkle root hash，并使用它来验证其账户的余额。如果 trie 被更新了，即使更新的是其他键，验证也会失败。

而现在，轻客户只需要相信 Merkle 根的哈希值，这一小段数据，就可以确定全节点是否为其账户返回了正确的余额。

好吧，但为什么轻客户端要相信 Merkle 根哈希值呢？

由于以太坊的共识机制是工作证明，而世界状态的 merkle 根哈希值包含在每个区块头中，所以计算工作是验证 / 信任 merkle 根哈希值的证明。

一个小小的 Merkle 根的哈希值可以用来验证一个巨大的键值映射的状态，这非常酷。

验证实现

我已经解释了 merkle patricia trie 的工作原理。代码库 [5] 提供了一个简单的实现。但是，怎样才能验证我们的实现呢？

一个简单的方法是用以太坊主网数据和 Trie golang 的官方实现来验证。

以太坊有 3 个 Merkle Patricia Trie：Transaction Trie 、Receipt Trie 和 State Trie。在每个区块头中，它包括 3 个 Merkle 根哈希值： transactionRoot , receiptRoot 和 stateRoot 。

由于 transactionRoot 是区块中所有交易的 Merkle 根哈希值，可以通过获取所有交易来验证我们的实现，然后将它们存储在我们的 trie 中，计算其 Merkle 根哈希值，最后与区块头中的 transactionRoot 进行比较。

例如，我挑选了主网 10467135 区块 [6]，并将所有 193 个交易保存到 transactions.json[7] 文件中。

由于块 10467135 的交易根是 [0xbb345e208bda953c908027a45aa443d6cab6b8d2fd64e83ec52f1008ddeafa58](https://api.etherscan.io/api?module=proxy&action;=eth_getBlockByNumber&tag;=0x9fb73f&boolean;=true&apikey;=YourApiKeyToken "0xbb345e208bda953c908027a45aa443d6cab6b8d2fd64e83ec52f1008ddeafa58") 。我可以创建一个测试案例，将 10467135 区块的 193 个交易添加到我们的 Trie 中并进行检查。

merkle 根哈希值是否为 bb345e208bda953c908027a45aa443d6cab6b8d2fd64e83ec52f1008ddeafa58 。
从我们的 trie 实现中产生的某个交易的 merkle 证明是否能被官方实现所验证。

但交易列表的键和值是什么？键是无符号整数的 RLP 编码，从索引 0 开始；值是相应交易的 RLP 编码。

好的，让我们看看测试案例 :

    import (       "github.com/ethereum/go-ethereum/common"       "github.com/ethereum/go-ethereum/core/types"       "github.com/ethereum/go-ethereum/trie"      )      // use the official golang implementation to check if a valid proof from our implementation can be accepted      func VerifyProof(rootHash []byte, key []byte, proof Proof) (value []byte, err error) {       return trie.VerifyProof(common.BytesToHash(rootHash), key, proof)      }      // load transaction from json      func TransactionJSON(t *testing.T) *types.Transaction {       jsonFile, err := os.Open("transaction.json")       defer jsonFile.Close()       require.NoError(t, err)       byteValue, err := ioutil.ReadAll(jsonFile)       require.NoError(t, err)       var tx types.Transaction       json.Unmarshal(byteValue, &tx;)       return &tx;      }      func TestTransactionRootAndProof(t *testing.T) {       trie := NewTrie()       txs := TransactionsJSON(t)       for i, tx := range txs {        // key is the encoding of the index as the unsigned integer type        key, err := rlp.EncodeToBytes(uint(i))        require.NoError(t, err)        transaction := FromEthTransaction(tx)        // value is the RLP encoding of a transaction        rlp, err := transaction.GetRLP()        require.NoError(t, err)        trie.Put(key, rlp)       }       // the transaction root for block 10467135       // https://api.etherscan.io/api?module=proxy&action;=eth_getBlockByNumber&tag;=0x9fb73f&boolean;=true&apikey;=YourApiKeyToken       transactionRoot, err := hex.DecodeString("bb345e208bda953c908027a45aa443d6cab6b8d2fd64e83ec52f1008ddeafa58")       require.NoError(t, err)       t.Run("merkle root hash should match with 10467135's transactionRoot", func(t *testing.T) {        // transaction root should match with block 10467135's transactionRoot        require.Equal(t, transactionRoot, trie.Hash())       })       t.Run("a merkle proof for a certain transaction can be verified by the offical trie implementation", func(t *testing.T) {        key, err := rlp.EncodeToBytes(uint(30))        require.NoError(t, err)        proof, found := trie.Prove(key)        require.Equal(t, true, found)        txRLP, err := VerifyProof(transactionRoot, key, proof)        require.NoError(t, err)        // verify that if the verification passes, it returns the RLP encoded transaction        rlp, err := FromEthTransaction(txs[30]).GetRLP()        require.NoError(t, err)        require.Equal(t, rlp, txRLP)       })      }

上述测试案例通过了，并且表明如果我们将 10467135 区块的所有 193 个交易加入到 trie 中，那么 trie 的哈希值与该区块中公布的 transactionRoot 相同。而由我们的 trie 生成的索引为 30 的交易的 merkle 证明，被官方的 golang trie 认为是有效的实现。

深入 Merkle Patricia Trie - Trie 节点

现在，让我们来看看 Trie 的内部实现。

在内部，trie 有 4 种类型的节点。空节点 (EmptyNode)、叶节点 (LeafNode)、分支节点 (BranchNode) 和扩展节点 (ExtensionNode)。每个节点将被编码并作为键值对存储在键值存储中。

让我们以主网的区块 10593417[8] 为例，来说明一个 Transaction Trie 是如何建立的，以及它是如何存储的。

Block 10593417[9] 只有 4 个 Root hash 交易。0xab41f886be23cd786d8a69a72b0f988ea72e0b2e03970d0798f5e03763a442cc[10]. 因此，为了将 4 个交易存储到一个 trie ，我们实际上是以十六进制字符串的形式存储以下键值对。

    (80, f8ab81a5852e90edd00083012bc294a3bed4e1c75d00fa6f4e5e6922db7261b5e9acd280b844a9059cbb0000000000000000000000008bda8b9823b8490e8cf220dc7b91d97da1c54e250000000000000000000000000000000000000000000000056bc75e2d6310000026a06c89b57113cf7da8aed7911310e03d49be5e40de0bd73af4c9c54726c478691ba056223f039fab98d47c71f84190cf285ce8fc7d9181d6769387e5efd0a970e2e9)      (01, f8ab81a6852e90edd00083012bc294a3bed4e1c75d00fa6f4e5e6922db7261b5e9acd280b844a9059cbb0000000000000000000000008bda8b9823b8490e8cf220dc7b91d97da1c54e250000000000000000000000000000000000000000000000056bc75e2d6310000026a0d77c66153a661ecc986611dffda129e14528435ed3fd244c3afb0d434e9fd1c1a05ab202908bf6cbc9f57c595e6ef3229bce80a15cdf67487873e57cc7f5ad7c8a)      (02, f86d8229f185199c82cc008252089488e9a2d38e66057e18545ce03b3ae9ce4fc360538702ce7de1537c008025a096e7a1d9683b205f697b4073a3e2f0d0ad42e708f03e899c61ed6a894a7f916aa05da238fbb96d41a4b5ec0338c86cfcb627d0aa8e556f21528e62f31c32f7e672)      (03, f86f826b2585199c82cc0083015f9094e955ede0a3dbf651e2891356ecd0509c1edb8d9c8801051fdc4efdc0008025a02190f26e70a82d7f66354a13cda79b6af1aa808db768a787aeb348d425d7d0b3a06a82bd0518bc9b69dc551e20d772a1b06222edfc5d39b6973e4f4dc46ed8b196)

80 是无符号整数 0 的 RLP 编码结果的十六进制形式： RLP(uint(0)) 。 01 是 RLP(uint(1)) 的结果，以此类推。

密钥 80 的值是第一个交易的 RLP 编码的结果。键值 01 是第二个交易的值，以此类推。

因此，我们将把上述 4 个键值对添加到 trie 中，让我们看看添加每一个键值对时，trie 的内部结构如何变化。

为了更直观，我将用一些图来解释它的工作原理。你也可以通过在测试案例中添加日志来检查每一步的状态。