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

这篇文章主要介绍了以太坊 Merkle Patricia Trie 是如何工作的 ,文中通过代码以及文档配合进行讲解,很详细,它对在座的每个人的研究和工作具有很经典的参考价值。 如果需要,让我们与区块链资料网一起学习。

https://www.interchains.cc/25132.html

以太坊 Merkle Patricia Trie 是如何工作的是很好的区块链资料,他说明了区块链当中的经典原理,可以给我们提供资料,以太坊 Merkle Patricia Trie 是如何工作的学习起来其实是很简单的,

不多的几个较为抽象的概念也很容易理解,之所以很多人感觉以太坊 Merkle Patricia Trie 是如何工作的比较复杂,一方面是因为大多数的文档没有做到由浅入深地讲解,概念上没有注意先后顺序,给读者的理解带来困难

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

解释 Merkle Patricia Trie 究竟是如何工作的,并展示一个 Merkle 证明生成和验证的demo。

  • 来源:https://medium.com/@chiqing/merkle-patricia-tri-explained-ae3ac6a7e123
  • 译文出自:登链翻译计划
  • 译者:aisiji
  • 校对:Tiny 熊
  • 本文永久链接:learnblockchain.cn/article…

介绍

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

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

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

好了,我们开始吧。

一个基本的键-值映射

以太坊eth的 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"))     }) }

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

验证数据的完整性

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)

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

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

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

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

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 根哈希值呢?

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

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

验证实现

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

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

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

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

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

由于块10467135的交易根是[0xbb345e208bda953c908027a45aa443d6cab6b8d2fd64e83ec52f1008ddeafa58](https://api.etherscan.io/api?module=proxy&action=eth_getBlockByNumber&tag=0x9fb73f&boolean=true&apikey=YourApiKeyToken)。我可以创建一个测试案例,将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为例,来说明一个Transaction Trie是如何建立的,以及它是如何存储的。

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

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

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

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

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

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

Empty Trie

trie 结构只包含一个根字段,指向一个根节点。而节点类型是一个接口,它可以是4种类型的节点之一。

type Trie struct {     root Node }

当一个 trie 被创建时,根节点指向一个 EmptyNode。

<a href=以太坊eth Merkle Patricia Trie 是如何工作的” />

添加第一笔交易

当添加第一个交易的键值对时,一个叶节点(LeafNode)被创建,交易数据存储在其中。根节点被更新以指向该叶节点(LeafNode)。

<a href=以太坊eth Merkle Patricia Trie 是如何工作的” />

添加第二笔交易

当添加第2个交易时,根部的叶节点(LeafNode) 将变成一个分支节点(BranchNode),有两个分支指向2个叶节点(LeafNode) 。左边的叶节点(LeafNode) 持有剩余的 nibbles(nibbles是一个单一的十六进制字符)-1,以及第2个交易的值。

而现在根节点正指向新的分支节点(BranchNode)。

<a href=以太坊eth Merkle Patricia Trie 是如何工作的” />

<a href=以太坊eth Merkle Patricia Trie 是如何工作的” />

添加第三笔交易

添加第3个交易将使左侧的叶节点(LeafNode) 变成一个分支节点(BranchNode) ,与添加第2个交易的过程类似。虽然根节点没有改变,但它的根哈希值已经改变了,因为它的0分支指向了不同的节点,有不同的哈希值。

<a href=以太坊eth Merkle Patricia Trie 是如何工作的” />

<a href=以太坊eth Merkle Patricia Trie 是如何工作的” />

添加第四笔交易

添加最后一个交易与添加第三个交易类似。现在我们可以验证根哈希值是否与区块中包含的 transactionRoot 相同。

<a href=以太坊eth Merkle Patricia Trie 是如何工作的” />

<a href=以太坊eth Merkle Patricia Trie 是如何工作的” />

获得第三笔交易的默克尔证明

第3笔交易的 Merkle 证明只是通往存储第3笔交易值的叶节点(LeafNode) 的路径。在验证证明时,可以从根哈希值开始,解码 Node,匹配 nibbles ,然后重复,直到找到匹配所有剩余 nibbles 的 Node。如果找到了,那么这个值就是与密钥配对的那个值;如果没有找到,那么 Merkle 证明就无效了。

更新 trie 的规则

在上面的例子中,我们已经建立了一个有3种类型节点的trie。空节点、叶节点和分支节点。然而,我们没有机会使用扩展节点(ExtensionNode) 。请找到其他使用 ExtensionNode 的测试案例。

一般来说,该规则是:

  • 当停在一个空节点时,用一个新的叶子节点替换它的剩余路径。
  • 当停在一个叶节点(LeafNode) 时,将其转换为一个 ExtensionNode 并添加一个新的分支和一个新的叶节点(LeafNode) 。
  • 当停在一个扩展节点时,将其转换为另一个具有较短路径的扩展节点,并创建一个新的分支节点指向该扩展节点。

有相当多的细节,如果你有兴趣,你可以阅读源代码。

摘要

Merkle Patricia Trie 是一个存储键值对的数据结构,就像一个地图。除此之外,它还允许我们验证数据的完整性和键值对的包容性。


本翻译由 Cell Network 赞助支持。

  • 发表于 2021-06-28 10:56
  • 阅读 ( 428 )
  • 学分 ( 90 )
  • 分类:以太坊eth

部分转自网络,侵权联系删除www.interchains.cchttps://www.interchains.cc/25132.html

区块链毕设网(www.interchains.cc)全网最靠谱的原创区块链毕设代做网站 部分资料来自网络,侵权联系删除! 最全最大的区块链源码站 ! QQ3039046426
区块链知识分享网, 以太坊dapp资源网, 区块链教程, fabric教程下载, 区块链书籍下载, 区块链资料下载, 区块链视频教程下载, 区块链基础教程, 区块链入门教程, 区块链资源 » 以太坊 Merkle Patricia Trie 是如何工作的

提供最优质的资源集合

立即查看 了解详情