以太坊（Ethereum）是目前最被接受的區(qū)塊鏈，而默克爾基數(shù)樹（Merkle Patricia Tree，MPT）是以太坊中非常重要的數(shù)據(jù)結(jié)構(gòu)，用于存儲賬戶的狀態(tài)信息、區(qū)塊鏈中的交易信息以及交易收據(jù)信息。

當生成樹形結(jié)構(gòu)之后，將樹的根（root）記錄于區(qū)塊鏈中，既便于查找又節(jié)約鏈上空間。

在以太坊的區(qū)塊頭（block head）中記錄了三個 MPT 樹的根，分別是：

• 狀態(tài)樹（state trie），記錄此區(qū)塊生成時所有賬戶的狀態(tài)信息（如：余額）
• 交易樹（tx trie），記錄此區(qū)塊中打包記錄的所有交易信息
• 收據(jù)樹（receipt trie），記錄此區(qū)塊中每筆交易帶來的狀態(tài)變化的中間狀態(tài)以及日志信息

如下圖所示的兩個區(qū)塊頭中，state root、tx root 和 receipt root 分別存儲了這三棵樹的根，第二個區(qū)塊顯示了當賬戶 175 的數(shù)據(jù)變更時(27 -> 45)，只需要關(guān)注跟這個賬戶相關(guān)的樹的分支，在生成新的樹形結(jié)構(gòu)之后將樹的 root 存儲到區(qū)塊頭，同時老的區(qū)塊中的數(shù)據(jù)仍然可以正常訪問。

mpt.png

以太坊使用的 Merkle Patricia Trie（MPT），源自于 Trie 結(jié)構(gòu)，又分別繼承了 Patricia Trie 和 Merkle Tree 的優(yōu)點。

Trie 樹

Trie，又稱為字典樹或者前綴樹 (prefix tree)，是一種有序樹，用于保存關(guān)聯(lián)數(shù)組，其中的 key 通常是字符串。與二叉查找樹不同：

• key 不是直接保存在節(jié)點中，而是由節(jié)點在 Trie 中的位置決定（下圖中標注出完整的單詞，只是為了演示 Trie 的原理）；
• 一個節(jié)點的所有子孫都有相同的前綴（key），而根節(jié)點 key 為空；
• 待存儲的數(shù)據(jù)只存于葉節(jié)點和部分內(nèi)部節(jié)點中，非葉節(jié)點幫助形成葉子節(jié)點 key 的前綴。

下圖展示了一個簡單的 Trie 結(jié)構(gòu)：

Trie

Patricia Trie 基數(shù)樹

Patricia trie 基數(shù)樹，或稱 crit bit tree 壓縮前綴樹，是一種更節(jié)省空間的 Trie。Patricia Trie 里如果父節(jié)點只有一個子節(jié)點，那么這個父節(jié)點將與其子節(jié)點合并。

這樣可以縮短 Trie 中不必要的深度，大大加快搜索節(jié)點速度。

patricia.png

Merkle Tree 默克爾樹

Merkle Tree 默克爾樹，通常也被稱作 Hash Tree，顧名思義，就是存儲 hash 值的一棵樹。Merkle 樹的葉子是數(shù)據(jù)塊(例如，文件或者文件的集合)的 hash 值。非葉節(jié)點是其對應(yīng)子節(jié)點串聯(lián)字符串的 hash。

hash 哈希，簡單的說就是一種將任意長度的數(shù)據(jù)壓縮到某一固定長度數(shù)據(jù)的方式。

要了解 Merkle Tree 就要先從 Hash List說起：

在 P2P 網(wǎng)絡(luò)中作數(shù)據(jù)傳輸?shù)臅r候，會同時從多個機器上下載數(shù)據(jù)。為了校驗數(shù)據(jù)的完整性，把大的文件分割成小的數(shù)據(jù)塊。這樣的好處是，如果小塊數(shù)據(jù)在傳輸過程中損壞了，那么只要重新下載這一快數(shù)據(jù)就行了，不用重新下載整個文件。

怎么確定小的數(shù)據(jù)塊沒有損壞？

只需要為每個數(shù)據(jù)塊做 hash。在下載到真正數(shù)據(jù)之前，會先下載一個 hash 列表。那么問題又來了，怎么確定這個 hash 列表本事是正確的呢？

答案是把每個小塊數(shù)據(jù)的 hash 值拼到一起，然后對這個長字符串在作一次 hash 運算，這樣就得到 hash 列表的根 hash（Top Hash or Root Hash）。下載數(shù)據(jù)的時候，首先從可信的數(shù)據(jù)源得到正確的根 hash，就可以用它來校驗 hash 列表了，然后通過校驗后的 hash 列表校驗數(shù)據(jù)塊。

哈希.png

Hash List 可以看作一種特殊的 Merkle Tree，即樹高為 2 的多叉 Merkle Tree。

在最底層，和 Hash List 一樣，我們把數(shù)據(jù)分成小的數(shù)據(jù)塊，有相應(yīng)地 hash 和它對應(yīng)。但是往上走，并不是直接去運算根 hash，而是把相鄰的兩個 hash 合并成一個字符串，然后運算這個字符串的 hash，這樣每兩個 hash 就得到了一個父 hash。于是往上推，最終必然形成一棵樹，得到根 hash，我們把它叫做 Merkle Root。

merkle.png

在 p2p 網(wǎng)絡(luò)下載網(wǎng)絡(luò)之前，先從可信的源獲得文件的 Merkle Tree 的 root。一旦獲得了 root ，就可以從其他從不可信的源獲取 Merkle tree。通過可信的樹根來檢查接受到的 Merkle Tree。如果 Merkle Tree 是損壞的或者虛假的，就從其他源獲得另一個 Merkle Tree，直到獲得一個與可信樹根匹配的 MerkleTree。

Merkle Tree 和 Hash List 的主要區(qū)別是：可以直接下載并立即驗證 Merkle Tree 的一個分支。

因為可以將文件切分成小的數(shù)據(jù)塊，這樣如果有一塊數(shù)據(jù)損壞，僅僅重新下載這個數(shù)據(jù)塊就行了。如果文件非常大，那么 Merkle tree 和 Hash List 都很大，但是 Merkle Tree 可以一次下載一個分支，然后立即驗證這個分支，如果分支驗證通過，就可以下載數(shù)據(jù)了。而 Hash list 只有下載整個 hash list 才能驗證。

Merkle Patricia Trie(MPT) 默克爾基數(shù)樹

顧名思義，MPT（Merkle Patricia Trie）就是 Merkle Tree 和 Patricia Trie 這兩者混合后的產(chǎn)物。

但 MPT 到底是什么結(jié)構(gòu)，憑空想象還是很難以理解，那就以下圖的簡化示例加以說明：

16進制前綴編碼.png

圖中右上角顯示的是四個賬戶地址及其余額，這也是一個簡化版的世界狀態(tài)：

以地址作為 key，以余額作為要存儲的 value，生成了一個 Patricia Trie（具體生成的細節(jié)后面會描述）；然后自底向上的遍歷過程中，不斷向上生成 hash，最后得到根節(jié)點的 root hash（體現(xiàn)了 Merkle Tree 的特點），即獲得了 state root。

這就是 MPT 的大概視圖，有了這個概念后才能具象化的理解 MPT 是如何結(jié)合 Merkle Tree 和 Patricia Trie 的；并更好的理解 Patricia Trie 的生成細節(jié)。

MPT 節(jié)點類型

在生成的 Patricia Trie 中可以看到存在三種類型的節(jié)點：

• Leaf（葉節(jié)點）：沒有子節(jié)點，表示為 [key, value] 鍵值對，從 root 到此節(jié)點的 key 的累加值表示完整 key 值（完整地址），value 用于存儲上面賬戶地址中實際的余額
• Extertion（擴展節(jié)點）：擁有一個分支節(jié)點作為子節(jié)點，表示為 [key, value] 鍵值對，key 值表示至少有兩個 key 的分支共享從 root 到此節(jié)點的 key 的累加值（地址的前一部分），只用于指向分支節(jié)點，不存儲實際值
• Branch（分支節(jié)點）：有 17 個子項的數(shù)據(jù)結(jié)構(gòu)，其中前 16 項對應(yīng) 16 進制的 0-F，表示從 root 到此節(jié)點的 key 的累加值產(chǎn)生了分叉，分叉值恰好分別對應(yīng) 0-F 的匹配項。若恰好有一個 key 值結(jié)束于此，則第 17 項存儲對應(yīng)的 value

通過這些節(jié)點類型，可以將上面的四個賬戶地址及其余額表示為 Patricia Trie。

基于以上內(nèi)容，大概的 MPT 內(nèi)容都已經(jīng)出來了，但是與圖中還有一些細小的不一致，這就引出了下面的內(nèi)容。

Hex-Prefix Encoding 16進制前綴編碼

Hex-Prefix Encoding (16進制前綴編碼)，是一種將任意長度的 nibble（4 位為一個 nibble，也可稱為半字節(jié)）編碼成 byte 數(shù)組的方法，也就是將最小粒度為 4 位的數(shù)組編碼成最小粒度為 8 位的數(shù)組。

為什么要進行編碼？

在以太坊協(xié)議中，不管是地址還是 hash，都是一個 16 進制串，如0x5b3edbcf7d0a97e95e57a4554a29ea66601b71ad，數(shù)據(jù)最小的表示單位為一個 16 進制數(shù)，如 0-F。

但在編程實現(xiàn)中，數(shù)據(jù)的最小表示單位往往是 byte（8 位，2 個 16 進制數(shù)），這樣在用 byte 來表示一串奇數(shù)長度的 16 進制串時會出現(xiàn)問題，如5b3和5b30，直接轉(zhuǎn)成 byte 都是5b30。

還有一種簡單直觀的轉(zhuǎn)換方式，5b3 -> 050b03，這種方式雖然簡單，但是數(shù)據(jù)量會翻倍，不利于大量 hash 的計算，同時也會增加 trie 的大小，降低同步性能。

而這個問題的解決方式就是 16 進制前綴編碼。具體的編碼參考下表：

在原始數(shù)據(jù)前增加一個 nibble，根據(jù)奇偶性（原始數(shù)據(jù)的 nibble 數(shù)量）和終止符的狀態(tài)（葉節(jié)點還是擴展節(jié)點）進行編碼：

• 最低位表示奇偶性：奇數(shù)為 1，偶數(shù)為 0
• 第二低位編碼終止符狀態(tài)：葉節(jié)點為 1，擴展節(jié)點為 0
• 如果原始數(shù)據(jù) nibble 數(shù)量為偶數(shù)，則增加一個值為 0 的 nibble 來保持整體的偶特性

總結(jié)

將以上這些綜合起來，就完成了以太坊上 Merkle Patricia Trie（默克爾基數(shù)樹）的構(gòu)造。