Merkle Patricia Trie（翻譯）

2019 年 10 月 7 日
筆記

原文：https://github.com/ethereum/wiki/wiki/Patricia-Tree

改良的 Merkle Patricia Trie 規範（又稱為 Merkle Patricia Tree）

Merkle Patricia Trie（下簡稱 MPT 樹，Trie 又稱前綴樹或字典樹）嘗試提供一種加密認證的數據結構，其可用於存儲任意類型的的鍵值對。本文僅討論鍵值對為字元串的情況（對於其他類型，只需要使用某種序列化方式將其轉換為字元串即可）。這些鍵值對是完全確定的，這意味著兩顆具有相同鍵值對的 Patricia 前綴樹，它們的數據是保證完全一致的，因此也擁有相同的根哈希（root hash）。MPT 樹提供優秀的 O(log(n)) 時間複雜度的插入，查詢和刪除性能。此外 MPT 樹也比一些基於比較的替代方案（如紅黑前綴樹）更好理解和實現。

主要技術指標：Merkle Patricia Trie

但是，radix 樹有一個較大的缺點：存儲效率很低。舉個例子，如果你只存儲一個路徑/值對，而這個路徑長64個字元（32 位元組的半位元組（Hex）表示，正如以太坊的狀態樹一樣），你將需要近 1K 的額外空間，一層一個字元地存儲這個路徑，並在需要刪除它的時候花上整整 64 步。本文的 Patricia 樹正是用來解決這個問題的。

改進

MPT 樹通過提高原本的數據結構的複雜度，來嘗試解決效率問題。MPT 樹的節點可分為 4 種類型：

NULL 空節點，用於表示空字元串
branch 分支節點，具有 17 個項 [v0 ... v15, vt]
leaf 葉子節點，具有 2 個項 [ encodedPath, value ]
extension 擴展節點，具有 2 個項 [ encodedPath, key ]

在使用長為 64 個字元的路徑的情況下，在遍歷前綴樹的前面幾層的節點之後，後面層的節點很大可能都不再是發散的路徑，而是一條單一路徑。如果此時還按照前面的節點一樣配置 index（Hex 字符集，共 16 個），則除了其中 1 個 index 不為空之外（即目標路徑的下一個字元），剩餘 15 個 index都是空的。這樣做顯然是不明智的。所以我們使用擴展節點 [ encodedPath, key ] 來快速處理這種單一路徑。其中，encodePath 包含要跳過的」局部路徑」（partial path，使用了下面提到的緊湊編碼），key 用於下一次的資料庫查詢。

對於用 encodePath 第一個半位元組就可以確定的葉子節點，上面提到的情況同樣存在，且跳過的」局部路徑」即完整路徑的剩餘部分。此時 value 即目標值。

當遍歷半位元組路徑時，我們可能最終得到一個奇數個半位元組的遍歷路徑。但因為所有的數據是以 bytes 格式存儲的，因此不可能區分下面這種情況：半位元組 1，和半位元組 01 （兩者都應該存儲為 <01>）。所以如果要指定奇數長度，則在局部路徑加上前綴標記。

規範：帶可選終結符的十六進位序列的緊湊編碼

上面提到，局部路徑的首位半位元組用於標記一個 2 項節點的屬性：奇數剩餘路徑長度/偶數奇數剩餘路徑長度 和 葉子節點/擴展節點 。定義如下：

1234567	HEX 值位值 \| 節點局部路徑類型路徑長度———————————————————- 0 0000 \| 擴展節點偶數 1 0001 \| 擴展節點奇數 2 0010 \| 終止節點（葉子節點）偶數 3 0011 \| 終止節點（葉子節點）奇數

對於偶數剩餘路徑長度（0 或 2），將始終跟隨另一個「填充」的半位元組 0。

def compact_encode(hexarray): term = 1 if hexarray[-1] == 16 else 0 if term: hexarray = hexarray[:-1] oddlen = len(hexarray) % 2 flags = 2 * term + oddlen if oddlen: hexarray = [flags] + hexarray else: hexarray = [flags] + [0] + hexarray // hexarray now has an even length whose first nibble is the flags. o = '' for i in range(0,len(hexarray),2): o += chr(16 * hexarray[i] + hexarray[i+1]) return o

123456789101112131415	def compact_encode(hexarray): term = 1 if hexarray[-1] == 16 else 0 if term: hexarray = hexarray[:-1] oddlen = len(hexarray) % 2 flags = 2 * term + oddlen if oddlen: hexarray = [flags] + hexarray else: hexarray = [flags] + [0] + hexarray // hexarray now has an even length whose first nibble is the flags. o = '' for i in range(0,len(hexarray),2): o += chr(16 * hexarray[i] + hexarray[i+1]) return o

示例：

> [ 1, 2, 3, 4, 5, …] '11 23 45' > [ 0, 1, 2, 3, 4, 5, …] '00 01 23 45' > [ 0, f, 1, c, b, 8, 10] '20 0f 1c b8' > [ f, 1, c, b, 8, 10] '3f 1c b8'

123456789	> [ 1, 2, 3, 4, 5, …]'11 23 45'> [ 0, 1, 2, 3, 4, 5, …]'00 01 23 45'> [ 0, f, 1, c, b, 8, 10]'20 0f 1c b8'> [ f, 1, c, b, 8, 10]'3f 1c b8'

以下是在 MPT 樹中獲取節點的擴展程式碼：

def get_helper(node,path): if path == []: return node if node = '': return '' curnode = rlp.decode(node if len(node) < 32 else db.get(node)) if len(curnode) == 2: (k2, v2) = curnode k2 = compact_decode(k2) if k2 == path[:len(k2)]: return get_helper(v2, path[len(k2):]) else: return '' elif len(curnode) == 17: return get_helper(curnode[path[0]],path[1:]) def get(node,path): path2 = [] for i in range(len(path)): path2.push(int(ord(path[i]) / 16)) path2.push(ord(path[i]) % 16) path2.push(16) return get_helper(node,path2)

12345678910111213141516171819202122