Ethereum Merkle Patricia Trie Explained

Ethereum Merkle Patricia Trie Explained

Nam

Nam Hoang / Sep 24, 2021

27 min read

Course Sections

Giới thiệu

Merkle Patricia Trie là một trong những cấu trúc dữ liệu then chốt cho lớp lưu trữ (storage layer) của Ethereum. Tôi muốn hiểu chính xác cách nó hoạt động. Vì vậy, tôi đã thực hiện một nghiên cứu sâu về tất cả các tài liệu mình có thể tìm thấy và tự mình triển khai thuật toán này.
Trong bài viết này, tôi sẽ chia sẻ những gì mình đã học được. Giải thích chính xác cách Merkle Patricia Trie hoạt động và cho bạn thấy một bản demo về cách một merkle proof được tạo ra và xác thực.
Mã nguồn của thuật toán và các ví dụ được sử dụng trong bài viết này đều là mã nguồn mở.

https://github.com/zhangchiqing/merkle-patricia-trie

Được rồi, hãy bắt đầu thôi.

Một cấu trúc key-value mapping cơ bản

Về bản chất, Merkle Patricia Trie của Ethereum là một cấu trúc key-value mapping cung cấp các phương thức tiêu chuẩn sau:

type Trie interface {
  // các phương thức như một key-value mapping cơ bản
  Get(key []byte) ([]byte, bool) {
  Put(key []byte, value []byte)
  Del(key []byte, value []byte) bool
}

Một bản triển khai của giao diện Trie trên nên vượt qua được các trường hợp kiểm thử (test cases) sau:

func TestGetPut(t *testing.T) {
	t.Run("nên không nhận được gì nếu key không tồn tại", func(t *testing.T) {
		trie := NewTrie()
		_, found := trie.Get([]byte("notexist"))
		require.Equal(t, false, found)
	})

	t.Run("nên nhận được giá trị nếu key tồn tại", 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("nên nhận được giá trị đã cập nhật", 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"))
	})
}

(Các test cases trong hướng dẫn này đã được bao gồm trong repo và đã vượt qua kiểm tra.)

Xác minh tính toàn vẹn dữ liệu

Merkle Patricia Trie có gì khác biệt so với một cấu trúc mapping thông thường?
Cụ thể, Merkle Patricia Trie cho phép chúng ta xác minh tính toàn vẹn dữ liệu (data integrity). (Trong phần còn lại của hướng dẫn này, chúng ta sẽ gọi nó là trie cho đơn giản).
Người ta có thể tính toán Merkle Root Hash của trie bằng hàm Hash, sao cho nếu bất kỳ cặp key-value nào được cập nhật, merkle root hash của trie sẽ thay đổi; nếu hai Trie có các cặp key-value giống hệt nhau, chúng phải có cùng một merkle root hash.

type Trie interface {
  // tính toán merkle root hash để xác minh tính toàn vẹn dữ liệu
  Hash() []byte
}

Hãy giải thích hành vi này bằng một số test cases:

// xác minh tính toàn vẹn dữ liệu
func TestDataIntegrity(t *testing.T) {
	t.Run("nên nhận được một mã hash khác nếu một cặp key-value mới được thêm vào hoặc cập nhật", 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("nên nhận được cùng một mã hash nếu hai trie có các cặp key-value giống hệt nhau", 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())
	})
}

Xác minh sự tồn tại của một cặp key-value

Đúng vậy, trie có thể xác minh tính toàn vẹn dữ liệu, nhưng tại sao không đơn giản là so sánh mã hash bằng cách băm toàn bộ danh sách các cặp key-value, tại sao phải phiền phức tạo ra cấu trúc dữ liệu trie?
Đó là bởi vì trie cũng cho phép chúng ta xác minh sự tồn tại (inclusion) của một cặp key-value mà không cần truy cập vào toàn bộ các cặp key-value.
Điều đó có nghĩa là trie có thể cung cấp một bằng chứng (proof) để chứng minh rằng một cặp key-value nhất định được bao gồm trong một cấu trúc key-value mapping tạo ra một merkle root hash nhất định.

type Proof interface {}

type Trie interface {
  // tạo một merkle proof cho một cặp key-value để xác minh sự tồn tại của cặp key-value đó
  Prove(key []byte) (Proof, bool)
}

// xác minh proof cho key nhất định với merkle root hash nhất định
func VerifyProof(rootHash []byte, key []byte, proof Proof) (value []byte, err error)

Điều này hữu ích trong Ethereum. Ví dụ, hãy tưởng tượng thế giới trạng thái của Ethereum (world state) là một cấu trúc key-value mapping, và các key là địa chỉ của mỗi tài khoản, còn các value là số dư của từng tài khoản.
Là một light client, vốn không có quyền truy cập vào toàn bộ trạng thái blockchain như các full node, mà chỉ có merkle root hash cho một block nhất định, làm thế nào nó có thể tin tưởng vào kết quả số dư tài khoản trả về từ một full node?
Câu trả lời là, một full node có thể cung cấp một merkle proof chứa merkle root hash, account key và giá trị số dư của nó, cũng như các dữ liệu khác. Merkle proof này cho phép một light client tự xác minh tính chính xác mà không cần có quyền truy cập vào toàn bộ trạng thái blockchain.
Hãy giải thích hành vi này bằng các test cases:

func TestProveAndVerifyProof(t *testing.T) {
	t.Run("không nên tạo proof cho key không tồn tại", 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("nên tạo một proof cho một key hiện có, proof có thể được xác minh bằng 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()

		// xác minh proof với root hash, key đang xét và proof của nó
		val, err := VerifyProof(rootHash, key, proof)
		require.NoError(t, err)

		// khi xác minh thành công, nó sẽ trả về giá trị chính xác của key
		require.Equal(t, []byte("hello"), val)
	})

	t.Run("nên thất bại khi xác minh nếu trie đã được cập nhật", func(t *testing.T) {
		tr := NewTrie()
		tr.Put([]byte{1, 2, 3}, []byte("hello"))
		tr.Put([]byte{1, 2, 3, 4, 5}, []byte("world"))

		// hash được lấy trước khi trie được cập nhật
		rootHash := tr.Hash()

		// proof được tạo ra sau khi trie đã được cập nhật
		tr.Put([]byte{5, 6, 7}, []byte("trie"))
		key := []byte{1, 2, 3}
		proof, ok := tr.Prove(key)
		require.True(t, ok)

		// nên thất bại khi xác minh vì merkle root hash không khớp
		_, err := VerifyProof(rootHash, key, proof)
		require.Error(t, err)
	})
}

Một light client có thể yêu cầu merkle root hash của trạng thái trie và sử dụng nó để xác minh số dư tài khoản của mình. Nếu trie được cập nhật, ngay cả khi các cập nhật nằm ở các key khác, thì việc xác minh cũng sẽ thất bại.
Và giờ đây, light client chỉ cần tin tưởng vào merkle root hash, vốn là một mẩu dữ liệu nhỏ, để tự thuyết phục liệu full node có trả về đúng số dư tài khoản của mình hay không.
Được rồi, nhưng tại sao light client nên tin tưởng vào merkle root hash?
Vì cơ chế đồng thuận của Ethereum là Proof of Work, và merkle root hash cho world state được bao gồm trong mỗi block header, công việc tính toán chính là bằng chứng để xác minh/tin tưởng vào merkle root hash.
Thật tuyệt vời khi một mẩu dữ liệu nhỏ như merkle root hash có thể được sử dụng để xác minh trạng thái của một cấu trúc key-value mapping khổng lồ.

Xác minh bản triển khai

Tôi đã giải thích cách merkle patricia trie hoạt động. Repo này cung cấp một bản triển khai đơn giản. Nhưng làm thế nào chúng ta có thể xác minh bản triển khai của mình?
Một cách dễ dàng là xác minh với dữ liệu mạng chính (Ethereum mainnet) và bản triển khai Trie chính thức bằng golang.
Ethereum có 3 loại Merkle Patricia Trie: Transaction Trie, Receipt Trie và State Trie. Trong mỗi block header, nó bao gồm 3 mã merkle root hash: transactionRoot, receiptRoot và stateRoot.
Vì transactionRoot là merkle root hash của tất cả các giao dịch được bao gồm trong block, chúng ta có thể xác minh bản triển khai của mình bằng cách lấy tất cả các giao dịch, sau đó lưu chúng vào trie của mình, tính toán merkle root hash của nó và cuối cùng so sánh nó với transactionRoot trong block header.

Ví dụ, tôi chọn block 10467135 trên mainnet, và lưu toàn bộ 193 giao dịch vào một file transactions.json.
Vì transaction root của block 10467135 là 0xbb345e208bda953c908027a45aa443d6cab6b8d2fd64e83ec52f1008ddeafa58. Tôi có thể tạo một test case để thêm 193 giao dịch của block 10467135 vào Trie của mình và kiểm tra:

  • Liệu merkle root hash có phải là bb345e208bda953c908027a45aa443d6cab6b8d2fd64e83ec52f1008ddeafa58 hay không.

  • Liệu một merkle proof cho một giao dịch nhất định được tạo ra từ bản triển khai trie của chúng ta có thể được xác minh bởi bản triển khai chính thức hay không.

Nhưng key và value cho danh sách các giao dịch sẽ là gì? Các key là mã hóa RLP của một số nguyên không dấu bắt đầu từ chỉ số 0; các value là mã hóa RLP của các giao dịch tương ứng.
Được rồi, hãy xem các test cases:

import (
	"github.com/ethereum/go-ethereum/common"
	"github.com/ethereum/go-ethereum/core/types"
	"github.com/ethereum/go-ethereum/trie"
)
// sử dụng bản triển khai golang chính thức để kiểm tra xem một proof hợp lệ từ bản triển khai của chúng ta có được chấp nhận hay không
func VerifyProof(rootHash []byte, key []byte, proof Proof) (value []byte, err error) {
	return trie.VerifyProof(common.BytesToHash(rootHash), key, proof)
}
// tải giao dịch từ 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 là mã hóa của chỉ số dưới dạng kiểu số nguyên không dấu
		key, err := rlp.EncodeToBytes(uint(i))
		require.NoError(t, err)
		transaction := FromEthTransaction(tx)
		// value là mã hóa RLP của một giao dịch
		rlp, err := transaction.GetRLP()
		require.NoError(t, err)
		trie.Put(key, rlp)
	}
	// transaction root của 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 nên khớp với transactionRoot của 10467135", func(t *testing.T) {
		// transaction root nên khớp với transactionRoot của block 10467135
		require.Equal(t, transactionRoot, trie.Hash())
	})
	t.Run("một merkle proof cho một giao dịch nhất định có thể được xác minh bởi bản triển khai trie chính thức", 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)
		// xác minh rằng nếu xác minh thành công, nó sẽ trả về giao dịch đã được mã hóa RLP
		rlp, err := FromEthTransaction(txs[30]).GetRLP()
		require.NoError(t, err)
		require.Equal(t, rlp, txRLP)
	})
}

Các test cases trên đã vượt qua, và cho thấy nếu chúng ta thêm tất cả 193 giao dịch của block 10467135 vào trie của mình, thì trie hash sẽ giống với transactionRoot được công bố trong block đó. Và merkle proof cho giao dịch có chỉ số 30, được tạo ra bởi trie của chúng ta, được coi là hợp lệ bởi bản triển khai trie chính thức của golang.

Cấu tạo bên trong Merkle Patricia Trie — Các Trie Node

Bây giờ, hãy cùng xem xét cấu trúc bên trong của trie.

Bên trong, trie có 4 loại node: EmptyNode, LeafNode, BranchNode và ExtensionNode. Mỗi node sẽ được mã hóa và lưu trữ dưới dạng các cặp key-value trong một kho lưu trữ key-value.

Ví dụ, hãy xem xét Block 10593417 trên mainnet để thấy cách một transaction trie được xây dựng và lưu trữ.

Block 10593417 chỉ có 4 giao dịch với transactionRoot hash là: 0xab41f886be23cd786d8a69a72b0f988ea72e0b2e03970d0798f5e03763a442cc. Vì vậy, để lưu trữ 4 giao dịch vào một trie, thực chất chúng ta đang lưu trữ các cặp key-value sau dưới dạng hex-string:

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

80 là dạng hex của các byte từ kết quả của việc mã hóa RLP của số nguyên không dấu 0: RLP(uint(0)). 01 là kết quả của RLP(uint(1)), và cứ thế tiếp tục.
Value cho key 80 là kết quả mã hóa RLP của giao dịch đầu tiên. Value cho key 01 là cho giao dịch thứ hai, và cứ thế tiếp tục.
Vì vậy, chúng ta sẽ thêm 4 cặp key-value trên vào trie, và hãy xem cấu trúc bên trong của trie thay đổi như thế nào khi thêm từng cặp trong số đó.
Để trực quan hơn, tôi sẽ sử dụng một số sơ đồ để giải thích cách nó hoạt động. Bạn cũng có thể kiểm tra trạng thái của từng bước bằng cách thêm log vào các test cases.

Trie Trống (Empty Trie)

Cấu trúc trie chỉ chứa một trường root trỏ đến một root node. Và kiểu Node là một interface, có thể là một trong 4 loại node.

type Trie struct {
	root Node
}

Khi một trie được tạo ra, root node trỏ đến một EmptyNode.

Thêm giao dịch thứ nhất

Khi thêm cặp key-value của giao dịch thứ nhất, một LeafNode được tạo ra với dữ liệu giao dịch được lưu trữ trong đó. Và root node được cập nhật để trỏ đến LeafNode đó.

Thêm giao dịch thứ hai

Khi thêm giao dịch thứ hai, LeafNode tại root sẽ được chuyển thành một BranchNode với hai nhánh trỏ đến 2 LeafNode. LeafNode ở phía bên phải giữ các nibbles còn lại (nibbles là một ký tự hex đơn lẻ) — 1, và giá trị cho giao dịch thứ hai.
Và bây giờ root node đang trỏ đến BranchNode mới.

Thêm giao dịch thứ ba

Thêm giao dịch thứ ba sẽ chuyển LeafNode ở phía bên phải thành một BranchNode, tương tự như quy trình thêm giao dịch thứ hai. Mặc dù root node không thay đổi, nhưng root hash của nó đã bị thay đổi, vì nhánh 0 của nó đang trỏ đến một node khác với các mã hash khác.

Thêm giao dịch thứ tư

Thêm giao dịch cuối cùng cũng tương tự như thêm giao dịch thứ ba. Bây giờ chúng ta có thể xác minh rằng root hash giống hệt với transactionRoot có trong block.

Lấy Merkle Proof cho giao dịch thứ ba

Merkle Proof cho giao dịch thứ ba đơn giản là đường dẫn đến LeafNode lưu trữ giá trị của giao dịch thứ ba. Khi xác minh proof, người ta có thể bắt đầu từ root hash, giải mã Node, khớp các nibbles và lặp lại cho đến khi tìm thấy Node khớp với tất cả các nibbles còn lại. Nếu tìm thấy, thì giá trị đó chính là giá trị đi kèm với key; nếu không tìm thấy, thì merkle proof đó không hợp lệ.

Quy tắc cập nhật trie

Trong ví dụ trên, chúng ta đã xây dựng một trie với 3 loại Node: EmptyNode, LeafNode và BranchNode. Tuy nhiên, chúng ta chưa có cơ hội sử dụng ExtensionNode. Vui lòng tìm các test cases khác có sử dụng ExtensionNode.
Nhìn chung, quy tắc là:

  • Khi dừng lại ở một EmptyNode, thay thế nó bằng một LeafNode mới với đường dẫn còn lại.
  • Khi dừng lại ở một LeafNode, chuyển đổi nó thành một ExtensionNode và thêm một nhánh mới cùng một LeafNode mới.
  • Khi dừng lại ở một ExtensionNode, chuyển đổi nó thành một ExtensionNode khác với đường dẫn ngắn hơn và tạo một BranchNode mới trỏ đến ExtensionNode đó.
    Có khá nhiều chi tiết, nếu bạn quan tâm, bạn có thể đọc mã nguồn.

Tóm tắt

Merkle Patricia Trie là một cấu trúc dữ liệu lưu trữ các cặp key-value, giống như một bản đồ (map). Ngoài ra, nó cũng cho phép chúng ta xác minh tính toàn vẹn dữ liệu và sự tồn tại của một cặp key-value.