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

• aisiji
• 更新于 2021-06-28 10:56
• 阅读 3714

## 介绍

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
}``````

``````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。)

``````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 数据结构？

``````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)``````

``````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)
})
}``````

## 验证实现

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

``````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)
}
func TransactionJSON(t *testing.T) *types.Transaction {
jsonFile, err := os.Open("transaction.json")
defer jsonFile.Close()
require.NoError(t, err)
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)
})
}``````

## 深入 Merkle Patricia Trie - Trie 节点

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

``````(80, f8ab81a5852e90edd00083012bc294a3bed4e1c75d00fa6f4e5e6922db7261b5e9acd280b844a9059cbb0000000000000000000000008bda8b9823b8490e8cf220dc7b91d97da1c54e250000000000000000000000000000000000000000000000056bc75e2d6310000026a06c89b57113cf7da8aed7911310e03d49be5e40de0bd73af4c9c54726c478691ba056223f039fab98d47c71f84190cf285ce8fc7d9181d6769387e5efd0a970e2e9)
(03, f86f826b2585199c82cc0083015f9094e955ede0a3dbf651e2891356ecd0509c1edb8d9c8801051fdc4efdc0008025a02190f26e70a82d7f66354a13cda79b6af1aa808db768a787aeb348d425d7d0b3a06a82bd0518bc9b69dc551e20d772a1b06222edfc5d39b6973e4f4dc46ed8b196)``````

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

## Empty Trie

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

``````type Trie struct {
root Node
}``````

## 更新 trie 的规则

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

## 摘要

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

aisiji