本文參考：

Patricia Tree - ethereum/wiki

Data structure in Ethereum | Episode 1+: Compact (Hex-prefix) encoding.

Data structure in Ethereum | Episode 3: Patricia trie.

以太坊中的Merkle Patricia Tree

乾貨 | Merkle Patricia Tree 詳解

以太坊MPT原理，你最值得看的一篇

1. 概述

Merkle Patricia Tree（又稱為Merkle Patricia Trie）是一種經過改良的、融合了Merkle tree和前綴樹兩種樹結構優點的數據結構，是以太坊中用來組織管理賬戶數據、生成交易集合哈希的重要數據結構。

MPT樹有以下幾個作用：

  • 存儲任意長度的key-value鍵值對數據，符合以太坊的state模型；
  • 提供了一種快速計算所維護數據集哈希標識的機制；
  • 提供了快速狀態回滾的機制；
  • 提供了一種稱為默克爾證明的證明方法，進行輕節點的擴展，實現簡單支付驗證；

由於MPT結合了Radix trie和Merkle兩種樹結構的特點與優勢 ，因此在介紹MPT之前，我們首先簡要地介紹下這兩種樹結構的特點。

2. Radix trie

Trie樹，又稱前綴樹或字典樹，是一種有序樹，用於保存關聯數組。其中的鍵通常是字元串。與二叉查找樹不同，鍵不是直接保存在節點中，而是由節點在樹中的位置決定 。一個節點的所有子孫都有相同的前綴，也就是這個節點對應的字元串，而 根節點對應空字元串。

一般情況下，不是所有的節點都有對應的值，只有葉子節點和部分內部節點所對應的鍵纔有相關的值。實際上trie每個節點是一個確定長度的數組，數組中每個節點的值是一個指向子節點的指針，最後有個標誌域，標識這個位置為止是否是一個完整的字元串.

常見的用來存英文單詞的trie每個節點是一個長度為27的指針數組，index0-25代表a-z字元，26為標誌域。如圖：

優勢：

相比於哈希表，使用前綴樹來進行查詢擁有共同前綴key的數據時十分高效，例如在字典中查找前綴為pre的單詞，對於哈希表來說，需要遍歷整個表，時間效率為O(n)，然而對於前綴樹來說，只需要在樹中找到前綴為pre的節點，且遍歷以這個節點為根節點的子樹即可。

但是對於最差的情況（前綴為空串)，時間效率為O(n),仍然需要遍歷整棵樹，此時效率與哈希表相同。

相比於哈希表，在前綴樹不會存在哈希衝突的問題。

劣勢：

  • 直接查找效率低下 前綴樹的查找效率是O(m)，m為所查找節點的key長度，而哈希表的查找效率為O(1)。且一次查找會有m次IO開銷，相比於直接查找，無論是速率、還是對磁碟的壓力都比較大。
  • 可能會造成空間浪費 當存在一個節點，其key值內容很長（如一串很長的字元串），當樹中沒有與他相同前綴的分支時，為了存儲該節點，需要創建許多非葉子節點來構建根節點到該節點間的路徑，造成了存儲空間的浪費。

3. Patricia trie

他是一種更節省空間的Trie。對於基數樹的每個節點，如果該節點是唯一的兒子的話，就和父節點合併。

4. Merkle tree

Merkle樹是由計算機科學家 Ralph Merkle 在很多年前提出的，並以他本人的名字來命名,由於在Bitcoin網路中用到了這種數據結構來進行數據正確性的驗證，在這裡簡要地介紹一下merkle樹的特點及原理。

在Bitcoin網路中，merkle樹被用來歸納一個區塊中的所有交易，同時生成整個交易集合的數字指紋。此外，由於merkle樹的存在，使得在Bitcoin這種公鏈的場景下，擴展一種「輕節點」實現簡單支付驗證變成可能。

特點

  • Merkle tree是一種樹，大多數是二叉樹，也可以多叉樹，無論是幾叉樹，它都具有樹結構的所有特點；
  • Merkle tree葉子節點的value是數據項的內容，或者是數據項的哈希值；
  • 非葉子節點的value根據其孩子節點的信息，然後按照Hash演算法計算而得出的；

將相鄰兩個節點的哈希值合併成一個字元串，然後計算這個字元串的哈希，得到的就是這兩個節點的父節點的哈希值。

如果該層的樹節點個數是單數，那麼對於最後剩下的樹節點，這種情況就直接對它進行哈希運算，其父節點的哈希就是其哈希值的哈希值（對於單數個葉子節點，有著不同的處理方法，也可以採用複製最後一個葉子節點湊齊偶數個葉子節點的方式）。循環重複上述計算過程，最後計算得到最後一個節點的哈希值，將該節點的哈希值作為整棵樹的哈希。

若兩棵樹的根哈希一致，則這兩棵樹的結構、節點的內容必然相同。

優勢

  • 快速重哈希

Merkle tree的特點之一就是當樹節點內容發生變化時，能夠在前一次哈希計算的基礎上，僅僅將被修改的樹節點進行哈希重計算，便能得到一個新的根哈希用來代表整棵樹的狀態。

  • 輕節點擴展

採用Merkle tree，可以在公鏈環境下擴展一種「輕節點」。輕節點的特點是對於每個區塊，僅僅需要存儲約80個位元組大小的區塊頭數據，而不存儲交易列表，回執列表等數據。然而通過輕節點，可以實現在非信任的公鏈環境中驗證某一筆交易是否被收錄在區塊鏈賬本的功能。這使得像比特幣，以太坊這樣的區塊鏈能夠運行在個人PC，智能手機等擁有小存儲容量的終端上。

對於輕節點來說，驗證一條交易只需要驗證包含該交易的路徑即可，並不需要把所有交易的Hash全部重新算一遍。

劣勢

  • 存儲空間開銷大

5. MPT(Merkle Patricia Trees)

概念

在深入MPT數據結構之前，我們先了解一下如下概念：

  • 世界狀態：在以太坊中，所有賬戶（包括合約賬戶、普通賬戶）的狀態數據統稱為世界狀態；
  • 輕節點：指只存儲區塊頭數據的區塊鏈節點；
  • 區塊鏈分叉：指向同一個父塊的2個區塊被同時生成的情況，某些部分的礦工看到其中一個區塊，其他的礦工則看到另外一個區塊。這導致2種區塊鏈同時增長；
  • 區塊頭：指以太坊區塊結構體的一部分，用於存儲該區塊的頭部信息，如父區塊哈希、世界狀態哈希、交易回執集合哈希等。區塊頭僅存儲一些「固定」長度的哈希欄位；

MPT樹中的節點

  • 空節點(NULL) - represented as the empty string

簡單的表示空，在代碼中是一個空串。

  • 葉子節點(leaf) - a 2-item node [ encodedPath, value ]

表示為 [key,value]的一個鍵值對，其中key是key的一種特殊十六進位編碼(MP編碼)， value是value的RLP編碼。

  • 分支節點(branch) - a 17-item node [ v0 … v15, vt ]

因為MPT樹中的key被編碼成一種特殊的16進位的表示，再加上最後的value，所以分支節點是一個 長度為17的list ** ** ， 前16個元素對應著key中的16個可能的十六進位字元 ， 如果有一個[key,value]對在這個分支節點終止，最後一個元素代表一個值 ，即分支節點既可以搜索路徑的終止也可以是路徑的中間節點。

  • 擴展節點(extension) - a 2-item node [ encodedPath, key ]

也是[key，value]的一個鍵值對 ，但是這裡的 value是其他節點的hash值 ，這個 hash可以被用來查詢資料庫中的節點。也就是說通過hash鏈接到其他節點。

因此，有兩種[key,value]節點(葉節點和擴展節點):

以太坊中對Key的編碼

在以太坊中，MPT樹的key值共有三種不同的編碼方式，以滿足不同場景的不同需求。

三種編碼方式分別為：

  • 1.Raw編碼（原生的字元）；
  • 2.Hex編碼（擴展的16進位編碼）；
  • 3.Hex-Prefix編碼（16進位前綴編碼）；

Raw編碼

Raw編碼就是原生的key值，不做任何改變。這種編碼方式的key，是MPT對外提供介面的默認編碼方式。

例如一條key為「cat」，value為「dog」的數據項，其key的Raw編碼就是[『c』, 『a』, 『t』]，換成ASCII表示方式就是[63, 61, 74]（Hex）

Hex編碼

Hex編碼就是把一個8位的位元組數據用兩個十六進位數展示出來，編碼時，將8位二進位碼重新分組成兩個4位的位元組，其中一個位元組的低4位是原位元組的高四位，另一個位元組的低4位是原數據的低4位，高4位都補0，然後輸出這兩個位元組對應十六進位數字作為編碼。Hex編碼後的長度是源數據的2倍。

Exp：

ASCII碼：A (65) 二進位碼：0100_0001 重新分組：0000_0100 0000_0001 十六進位： 4 1 Hex編碼：41

若該Key對應的節點存儲的是真實的數據項內容（即該節點是葉子節點），則在末位添加一個ASCII值為16的字元作為terminator；

若該key對應的節點存儲的是另外一個節點的哈希索引（即該節點是擴展節點），則不加任何字元；

[『c』,』a』,』t』] -> [6,3,6,1,7,4,16]

HP編碼

目的：

  • 區分leaf和extension
  • 把奇數路徑變成偶數路徑

步驟：

  • 如果有terminator（16）那麼就去掉terminator。
  • 根據表格給key加上prefix

node type path length | prefix hexchar
--------------------------------------------------
extension even | 0000 0x0
extension odd | 0001 0x1
leaf even | 0010 0x2
leaf odd | 0011 0x3

如果prefix是0x0或者0x2，加一個padding nibble 0 在prefix後面，所以最終應該是 0x00 和 0x20。原因是為了保證key（path）的長度為偶數。

例子： 末尾的字元「16」說明該節點為葉子結點，並且加上了0x20

[ 0, f, 1, c, b, 8, 16] -> 20 0f 1c b8

編碼轉換關係

以上三種編碼方式的轉換關係為：

  • Raw編碼：原生的key編碼，是MPT對外提供介面中使用的編碼方式，當數據項被插入到樹中時，Raw編碼被轉換成Hex編碼；
  • Hex編碼：16進位擴展編碼，用於對內存中樹節點key進行編碼，當樹節點被持久化到資料庫時，Hex編碼被轉換成HP編碼；
  • HP編碼：16進位前綴編碼，用於對資料庫中樹節點key進行編碼，當樹節點被載入到內存時，HP編碼被轉換成Hex編碼；

MPT的結構

MPT樹的特點如下:

  • 葉子節點和分支節點可以保存value, 擴展節點保存key；
  • 沒有公共的key就成為2個葉子節點；key1=[1,2,3] key2=[2,2,3]
  • 有公共的key需要提取為一個擴展節點；key1=[1,2,3] key2=[1,3,3] => ex-node=[1],下一級分支node的key
  • 如果公共的key也是一個完整的key，數據保存到下一級的分支節點中；key1=[1,2] key2=[1,2,3] =>ex-node=[1,2],下一級分支node的key; 下一級分支=[3],上一級key對應的value

簡單的結構如下圖：

我們將存入如下state數據:

key | values
----------------------
a711355 | 45.0 ETH
a77d337 | 1.00 WEI
a7f9365 | 1.1 ETH
a77d397 | 0.12 ETH

插入第一個<a711355, 45>，由於只有一個key,直接用leaf node既可表示

接著插入a77d337,由於和a711355共享前綴』a7』,因而可以創建』a7』擴展節點。

接著插入a7f9365,也是共享』a7』,只需新增一個leaf node.

最後插入a77d397,這個key和a77d337共享』a7』+』d3』,因而再需要創建一個』d3』擴展節點

將葉子節點和最後的short node合併到一個節點了，事實上源碼實現需要再深一層，最後一層的葉子節點只有數據

// nodeFlag contains caching-related metadata about a node.
type nodeFlag struct {
hash hashNode // cached hash of the node (may be nil)
gen uint16 // cache generation counter
dirty bool // whether the node has changes that must be written to the database
}

MPT節點有個flag字，nodeFlag，記錄了一些輔助數據：

  • 節點哈希：若該欄位不為空，則當需要進行哈希計算時，可以跳過計算過程而直接使用上次計算的結果（當節點變髒時，該欄位被置空）；
  • 誕生標誌：當該節點第一次被載入內存中（或被修改時），會被賦予一個計數值作為誕生標誌，該標誌會被作為節點驅除的依據，清除內存中「太老」的未被修改的節點，防止佔用的內存空間過多；
  • 臟標誌：當一個節點被修改時，該標誌位被置為1；

flag.hash會保存該節點採用merkle tree類似演算法生成的hash。同時會將hash和源數據以<hash, node.rlp.rawdata>方式保存在leveldb資料庫中。這樣後面通過hash就可以反推出節點數據。具體結構如下(藍色的hash部分就是flag.hash欄位)

核心思想

hash可以還原出節點上的數據，這樣只需要保存一個root(hash)，即可還原出完整的樹結構，同時還可以按需展開節點數據，比如如果只需要訪問<a771355, 45>這個數據，只需展開h00, h10, h20, h30這四個hash對應的節點

希望能和對區塊鏈感興趣的朋友多多交流，我的blog地址：

區塊鏈可拓展技術：側鏈(Sidechain)?

dinghaoli.github.io圖標
推薦閱讀：
相關文章