Merkle Patricia Tree 詳解

1. 前言

1.1 概述

Merkle Patricia Tree（又稱為Merkle Patricia Trie）是一種經過改良的、融合了默克爾樹和字首樹兩種樹結構優點的資料結構，是以太坊中用來組織管理賬戶資料、生成交易集合雜湊的重要資料結構。

MPT樹有以下幾個作用：

儲存任意長度的key-value鍵值對資料；
提供了一種快速計算所維護資料集雜湊標識的機制；
提供了快速狀態回滾的機制；
提供了一種稱為默克爾證明的證明方法，進行輕節點的擴充套件，實現簡單支付驗證；

由於MPT結合了（1）字首樹（2）默克爾樹兩種樹結構的特點與優勢，因此在介紹MPT之前，我們首先簡要地介紹下這兩種樹結構的特點。

1.2 字首樹

字首樹（又稱字典樹），用於儲存關聯陣列，其鍵（key）的內容通常為字串。字首樹節點在樹中的位置是由其鍵的內容所決定的，即字首樹的key值被編碼在根節點到該節點的路徑中。

如下圖所示，圖中共有6個葉子節點，其key的值分別為（1）to（2）tea（3）ted（4）ten（5）A（6）inn。

優勢：

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

但是對於最差的情況（字首為空串），時間效率為O(n)，仍然需要遍歷整棵樹，此時效率與雜湊表相同。

相比於雜湊表，在字首樹不會存在雜湊衝突的問題。

劣勢：

直接查詢效率低下

字首樹的查詢效率是O(m)，m為所查詢節點的key長度，而雜湊表的查詢效率為O(1)。且一次查詢會有m次IO開銷，相比於直接查詢，無論是速率、還是對磁碟的壓力都比較大。

可能會造成空間浪費

當存在一個節點，其key值內容很長（如一串很長的字串），當樹中沒有與他相同字首的分支時，為了儲存該節點，需要建立許多非葉子節點來構建根節點到該節點間的路徑，造成了儲存空間的浪費。

1.3 默克爾樹

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

在比特幣網路中，merkle樹被用來歸納一個區塊中的所有交易，同時生成整個交易集合的數字指紋。此外，由於merkle樹的存在，使得在比特幣這種公鏈的場景下，擴充套件一種“輕節點”實現簡單支付驗證變成可能，關於輕節點的內容，將會下文詳述。

特點

默克爾樹是一種樹，大多數是二叉樹，也可以多叉樹，無論是幾叉樹，它都具有樹結構的所有特點；
默克爾樹葉子節點的value是資料項的內容，或者是資料項的雜湊值；
非葉子節點的value根據其孩子節點的資訊，然後按照Hash演算法計算而得出的；

原理

在比特幣網路中，merkle樹是自底向上構建的。在下圖的例子中，首先將L1-L4四個單後設資料雜湊化，然後將雜湊值儲存至相應的葉子節點。這些節點是Hash0-0, Hash0-1, Hash2-0, Hash2-1

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

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

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

如上圖所示，一棵有著4個葉子節點的樹，計算代表整棵樹的雜湊需要經過7次計算，若採用將這四個葉子節點拼接成一個字串進行計算，僅僅只需要一次雜湊就可以實現，那麼為什麼要採用這種看似奇怪的方式呢？

優勢：

快速重雜湊

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

輕節點擴充套件

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

劣勢：

儲存空間開銷大

2. 術語解釋

在下文中，會有些特定的專業術語，在這裡首先對這些術語給出定義

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

3. 結構設計

在這一章節，將詳細地介紹MPT樹的結構設計，以及採用這種結構設計的用意、最佳化點。

3.1 節點分類

如上文所述，儘管字首樹可以起到維護key-value資料的目的，但是其具有十分明顯的侷限性。無論是查詢操作，還是對資料的增刪改，不僅效率低下，且儲存空間浪費嚴重。故，在以太坊中，為MPT樹新增了幾種不同型別的樹節點，以儘量壓縮整體的樹高、降低操作的複雜度。

MPT樹中，樹節點可以分為以下四類：

空節點
分支節點
葉子節點
擴充套件節點

空節點用來表示空串。

分支節點

分支節點用來表示MPT樹中所有擁有超過1個孩子節點以上的非葉子節點，其定義如下所示：

typefullNodestruct{Children[17]node// Actual trie node data to encode/decode (needs custom encoder)flagsnodeFlag}// nodeFlag contains caching-related metadata about a node.typenodeFlagstruct{hashhashNode// cached hash of the node (may be nil)genuint16// cache generation counterdirtybool// whether the node has changes that must be written to the database}

與字首樹相同，MPT同樣是把key-value資料項的key編碼在樹的路徑中，但是key的每一個位元組值的範圍太大（[0-127]），因此在以太坊中，在進行樹操作之前，首先會進行一個key編碼的轉換（下節會詳述），將一個位元組的高低四位內容分拆成兩個位元組儲存。透過編碼轉換，key'的每一位的值範圍都在[0, 15]內。因此，一個分支節點的孩子至多隻有16個。以太坊透過這種方式，減小了每個分支節點的容量，但是在一定程度上增加了樹高。

分支節點的孩子列表中，最後一個元素是用來儲存自身的內容。

此外，每個分支節點會有一個附帶的欄位nodeFlag，記錄了一些輔助資料：

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

葉子節點&&擴充套件節點

葉子節點與擴充套件節點的定義相似，如下所示：

typeshortNodestruct{Key[]byteValnodeflagsnodeFlag}

其中關鍵的欄位為：

Key：用來儲存屬於該節點範圍的key；
Val：用來儲存該節點的內容；

其中Key是MPT樹實現樹高壓縮的關鍵！

如之前所提及的，字首樹中會出現嚴重的儲存空間浪費的情況，如下圖：

圖中右側有一長串節點，這些節點大部分只是充當非葉子節點，用來構建一條路徑，目的只是為了儲存該路徑上的葉子節點。

針對這種情況，MPT樹對此進行了最佳化：當MPT試圖插入一個節點，插入過程中發現目前沒有與該節點Key擁有相同字首的路徑。此時MPT把剩餘的Key儲存在葉子／擴充套件節點的Key欄位中，充當一個”Shortcut“。

例如圖中我們將紅線所圈的節點稱為node1, 將藍線所圈的節點稱為node2。node1與node2共享路徑字首t，但是node1在插入時，樹中沒有與oast有共同字首的路徑，因此node1的key為oast，實現了編碼路徑的壓縮。

這種做法有以下幾點優勢：

提高節點的查詢效率，避免過多的磁碟訪問；
減少儲存空間浪費，避免儲存無用的節點；

此外Val欄位用來儲存葉子／擴充套件節點的內容，對於葉子節點來說，該欄位儲存的是一個資料項的內容；而對於擴充套件節點來說，該欄位可以是以下兩種內容：

Val欄位儲存的是其孩子節點在資料庫中儲存的索引值（其實該索引值也是孩子節點的雜湊值）；
Val欄位儲存的是其孩子節點的引用；

為什麼設計在擴充套件節點的Val欄位有可能儲存一串雜湊值作為孩子節點的索引呢？
在以太坊中，該雜湊代表著另外一個節點在資料庫中索引，即根據這個雜湊值作為資料庫中的索引，可以從資料庫中讀取出另外一個節點的內容。
這種設計的目的是：
（1）當整棵樹被持久化到資料庫中時，保持節點間的關聯關係；
（2）從資料庫中讀取節點時，儘量避免不必要的IO開銷；
在記憶體中，父節點與子節點之間關聯關係可以透過引用、指標等程式設計手段實現，但是當樹節點持久化到資料庫是，父節點中會儲存一個子節點在資料庫中的索引值，以此保持關聯關係。
同樣，從資料庫中讀取節點時，本著最小IO開銷的原則，僅需要讀取那些需要用到的節點資料即可，因此若目前該節點已經包含所需要查詢的資訊時，便無須將其子節點再讀取出來；反之，則根據子節點的雜湊索引遞迴讀取子節點，直至讀取到所需要的資訊。

由於葉子／擴充套件節點共享一套定義，那麼怎麼來區分Val欄位儲存的到底是一個資料項的內容，還是一串雜湊索引呢？在以太坊中，透過在Key中加入特殊的標誌來區分兩種型別的節點。

3.2 key值編碼

在以太坊中，MPT樹的key值共有三種不同的編碼方式，以滿足不同場景的不同需求，在這裡單獨作為一節進行介紹。

三種編碼方式分別為：

Raw編碼（原生的字元）；
Hex編碼（擴充套件的16進位制編碼）；
Hex-Prefix編碼（16進位制字首編碼）；

Raw編碼

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

例如一條key為“cat”，value為“dog”的資料項，其Raw編碼就是['c', 'a', 't']，換成ASCII表示方式就是[63, 61, 74]

Hex編碼

在介紹分支節點的時候，我們介紹了，為了減少分支節點孩子的個數，需要將key的編碼進行轉換，將原key的高低四位分拆成兩個位元組進行儲存。這種轉換後的key的編碼方式，就是Hex編碼。

從Raw編碼向Hex編碼的轉換規則是：

將Raw編碼的每個字元，根據高4位低4位拆成兩個位元組；
若該Key對應的節點儲存的是真實的資料項內容（即該節點是葉子節點），則在末位新增一個ASCII值為16的字元作為終止標誌符；
若該key對應的節點儲存的是另外一個節點的雜湊索引（即該節點是擴充套件節點），則不加任何字元；

key為“cat”, value為“dog”的資料項，其Hex編碼為[3, 15, 3, 13, 4, 10, 16]

Hex編碼用於對記憶體中MPT樹節點key進行編碼

HP編碼

在介紹葉子／擴充套件節點時，我們介紹了這兩種節點定義是共享的，即便持久化到資料庫中，儲存的方式也是一致的。那麼當節點載入到記憶體是，同樣需要透過一種額外的機制來區分節點的型別。於是以太坊就提出了一種HP編碼對儲存在資料庫中的葉子／擴充套件節點的key進行編碼區分。在將這兩類節點持久化到資料庫之前，首先會對該節點的key做編碼方式的轉換，即從Hex編碼轉換成HP編碼。

HP編碼的規則如下：

若原key的末尾位元組的值為16（即該節點是葉子節點），去掉該位元組；
在key之前增加一個半位元組，其中最低位用來編碼原本key長度的奇偶資訊，key長度為奇數，則該位為1；低2位中編碼一個特殊的終止標記符，若該節點為葉子節點，則該位為1；
若原本key的長度為奇數，則在key之前再增加一個值為0x0的半位元組；
將原本key的內容作壓縮，即將兩個字元以高4位低4位進行劃分，儲存在一個位元組中（Hex擴充套件的逆過程）；

若Hex編碼為[3, 15, 3, 13, 4, 10, 16]，則HP編碼的值為[32, 63, 61, 74]

HP編碼用於對資料庫中的樹節點key進行編碼

轉換關係

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

Raw編碼：原生的key編碼，是MPT對外提供介面中使用的編碼方式，當資料項被插入到樹中時，Raw編碼被轉換成Hex編碼；
Hex編碼：16進位制擴充套件編碼，用於對記憶體中樹節點key進行編碼，當樹節點被持久化到資料庫時，Hex編碼被轉換成HP編碼；
HP編碼：16進位制字首編碼，用於對資料庫中樹節點key進行編碼，當樹節點被載入到記憶體時，HP編碼被轉換成Hex編碼；

3.3 安全的MPT

以上介紹的MPT樹，可以用來儲存內容為任何長度的key-value資料項。倘若資料項的key長度沒有限制時，當樹中維護的資料量較大時，仍然會造成整棵樹的深度變得越來越深，會造成以下影響：

查詢一個節點可能會需要許多次IO讀取，效率低下；
系統易遭受Dos攻擊，攻擊者可以透過在合約中儲存特定的資料，“構造”一棵擁有一條很長路徑的樹，然後不斷地呼叫SLOAD指令讀取該樹節點的內容，造成系統執行效率極度下降；
所有的key其實是一種明文的形式進行儲存；

為了解決以上問題，在以太坊中對MPT再進行了一次封裝，對資料項的key進行了一次雜湊計算，因此最終作為引數傳入到MPT介面的資料項其實是(sha3(key), value)

優勢：

傳入MPT介面的key是固定長度的（32位元組），可以避免出現樹中出現長度很長的路徑；

劣勢：

每次樹操作需要增加一次雜湊計算；
需要在資料庫中儲存額外的sha3(key)與key之間的對應關係；

4. 基本操作

介紹完MPT樹的組成結構，在這一章將介紹MPT幾種核心的基本操作。

4.1 Get

一次Get操作的過程為：

將需要查詢Key的Raw編碼轉換成Hex編碼，得到的內容稱之為搜尋路徑；
從根節點開始搜尋與搜尋路徑內容一致的路徑；
1. 若當前節點為葉子節點，儲存的內容是資料項的內容，且搜尋路徑的內容與葉子節點的key一致，則表示找到該節點；反之則表示該節點在樹中不存在。
2. 若當前節點為擴充套件節點，且儲存的內容是雜湊索引，則利用雜湊索引從資料庫中載入該節點，再將搜尋路徑作為引數，對新解析出來的節點遞迴地呼叫查詢函式。
3. 若當前節點為擴充套件節點，儲存的內容是另外一個節點的引用，且當前節點的key是搜尋路徑的字首，則將搜尋路徑減去當前節點的key，將剩餘的搜尋路徑作為引數，對其子節點遞迴地呼叫查詢函式；若當前節點的key不是搜尋路徑的字首，表示該節點在樹中不存在。
4. 若當前節點為分支節點，若搜尋路徑為空，則返回分支節點的儲存內容；反之利用搜尋路徑的第一個位元組選擇分支節點的孩子節點，將剩餘的搜尋路徑作為引數遞迴地呼叫查詢函式。

上圖是一次查詢key為”cat“節點的過程。

將key"cat"轉換成hex編碼[3,15,3,13,4,10,T] （在末尾新增終止符是因為需要查詢一個真實的資料項內容）；
當前節點是根節點，且是擴充套件節點，其key為3,15，則遞迴地對其子節點進行查詢呼叫，剩餘的搜尋路徑為[3,13,4,10,T];
當前節點是分支節點，以搜尋路徑的第一個位元組內容3選擇第4個孩子節點遞迴進行查詢，剩餘的搜尋路徑為[13,4,10,T]；
當前節點是葉子節點，且key與剩餘的搜尋路徑一致，表示找到了該節點，返回Val為“dog”；

4.2 Insert

插入操作也是基於查詢過程完成的，一個插入過程為：

根據4.1中描述的查詢步驟，首先找到與新插入節點擁有最長相同路徑字首的節點，記為Node；
若該Node為分支節點：
1. 剩餘的搜尋路徑不為空，則將新節點作為一個葉子節點插入到對應的孩子列表中；
2. 剩餘的搜尋路徑為空（完全匹配），則將新節點的內容儲存在分支節點的第17個孩子節點項中（Value）；
若該節點為葉子／擴充套件節點：
1. 剩餘的搜尋路徑與當前節點的key一致，則把當前節點Val更新即可；
2. 剩餘的搜尋路徑與當前節點的key不完全一致，則將葉子／擴充套件節點的孩子節點替換成分支節點，將新節點與當前節點key的共同字首作為當前節點的key，將新節點與當前節點的孩子節點作為兩個孩子插入到分支節點的孩子列表中，同時當前節點轉換成了一個擴充套件節點（若新節點與當前節點沒有共同字首，則直接用生成的分支節點替換當前節點）；
若插入成功，則將被修改節點的dirty標誌置為true，hash標誌置空（之前的結果已經不可能用），且將節點的誕生標記更新為現在；

上圖是一次將key為“cau”, value為“dog1”節點插入的過程。

將key"cau"轉換成hex編碼[3,15,3,13,4,11,T] ；
透過查詢演算法，找到左圖藍線圈出的節點node1，且擁有與新插入節點最長的共同字首[3,15,3,13,4]；
新增一個分支節點node2，將node1的val與新節點作為孩子插入到node2的孩子列表中，將node1的val替換成node2；
node1變成了一個擴充套件節點；

4.3 Delete

刪除操作與插入操作類似，都需要藉助查詢過程完成，一次刪除過程為：

根據4.1中描述的查詢步驟，找到與需要插入的節點擁有最長相同路徑字首的節點，記為Node；
若Node為葉子／擴充套件節點：
1. 若剩餘的搜尋路徑與node的Key完全一致，則將整個node刪除；
2. 若剩餘的搜尋路徑與node的key不匹配，則表示需要刪除的節點不存於樹中，刪除失敗；
3. 若node的key是剩餘搜尋路徑的字首，則對該節點的Val做遞迴的刪除呼叫；
若Node為分支節點：
1. 刪除孩子列表中相應下標標誌的節點；
2. 刪除結束，若Node的孩子個數只剩下一個，那麼將分支節點替換成一個葉子／擴充套件節點；
若刪除成功，則將被修改節點的dirty標誌置為true，hash標誌置空（之前的結果已經不可能用），且將節點的誕生標記更新為現在；

上面兩幅圖是一次將key為“cau”, value為“dog1”節點刪除的過程。

將key"cau"轉換成hex編碼[3,15,3,13,4,11,T] ；
透過查詢演算法，找到用叉表示的節點node1，從根節點到node1的路徑與搜尋路徑完全一致；
從node1的父節點中刪除該節點，父節點僅剩一個孩子節點，故將父節點轉換成一個葉子節點；
新生成的葉子節點又與其父節點（擴充套件節點）發生了合併，最終生成了一個葉子節點包含了所有的資訊（圖2）；

4.4 Update

更新操作就是4.2Insert與4.3Delete的結合。當使用者呼叫Update函式時，若value不為空，則隱式地轉為呼叫Insert；若value為空，則隱式地轉為呼叫Delete，故在此不再贅述。

4.5 Commit

Commit函式提供將記憶體中的MPT資料持久化到資料庫的功能。在第一章中我們提到的MPT具有快速計算所維護資料集雜湊標識以快速狀態回滾的能力，也都是在該函式中實現的。

在commit完成後，所有變髒的樹節點會重新進行雜湊計算，並且將新內容寫入資料庫；最終新的根節點雜湊將被作為MPT的最新狀態被返回。

一次MPT樹提交是一個遞迴呼叫的過程，在介紹MPT提交過程之前，我們首先介紹單個節點是如何進行雜湊計算和儲存的。

單節點

首先是對該節點進行髒位的判斷，若當前節點未被修改，則直接返回該節點的雜湊值，呼叫結束（此外，若當前節點既未被修改，同時存在於記憶體的時間又”過長“，則將以該節點為根節點的子樹從記憶體中驅除）；
該節點為髒節點，對該節點進行雜湊重計算。首先是對當前節點的孩子節點進行雜湊計算，對孩子節點的雜湊計算是利用遞迴地對節點進行處理完成。這一步驟的目的是將孩子節點的資訊各自轉換成一個雜湊值進行表示；。
對當前節點進行雜湊計算。雜湊計算利用sha256雜湊演算法對當前節點的RLP編碼進行雜湊計算；
1. 對於分支節點來說，該節點的RLP編碼就是對其孩子列表的內容進行編碼，且在第二步中，所有的孩子節點所有已經被轉換成了一個雜湊值；
2. 對於葉子／擴充套件節點來說，該節點的RLP編碼就是對其Key，Value欄位進行編碼。同樣在第二步中，若Value指代的是另外一個節點的引用，則已經被轉換成了一個雜湊值（在第二步中，Key已經被轉換成了HP編碼）；
將當前節點的資料存入資料庫，儲存的格式為[節點雜湊值，節點的RLP編碼]。
將自身的dirty標誌置為false，並將計算所得的雜湊值進行快取；

MPT樹的提交過程

在理解單節點的提交過程後，MPT樹的提交過程就是以根節點為入口，對根節點進行提交呼叫即可。

上圖展示一棵MPT被持久化的過程：

左下角的葉子節點計算得到雜湊為0xaa，將其存入資料庫中，並在其父節點中用雜湊值進行替換；粉色的擴充套件節點計算得到雜湊為0xcc，在父節點用中0xcc進行替換；遞迴至根節點，計算得到根節點的雜湊為0xee，即整棵樹的雜湊為0xee。

節點過老的判斷依據

判斷一個節點在記憶體中存在時間是否過長的依據是：
該節點未被修改；
當前MPT的計數器減去節點的誕生標誌超過了固定的上限；
每當MPT呼叫一次Commit函式，MPT的計數器發生自增；

實現功能

1.快速計算所維護資料集雜湊標識

這個特點體現在單節點計算的第一步，即在節點雜湊計算之前會對該節點的狀態進行判斷，只有當該節點的內容變髒，才會進行雜湊重計算、資料庫持久化等操作。如此一來，在某一次事務操作中，對整棵MPT樹的部分節點的內容產生了修改，那麼一次雜湊重計算，僅需對這些被修改的節點、以及從這些節點到根節點路徑上的節點進行重計算，便能重新獲得整棵樹的新雜湊。

2.快速狀態回滾

在公鏈的環境下，採用POW演算法是可能會造成分叉而導致區塊鏈狀態進行回滾的。在以太坊中，由於出塊時間短，這種分叉的機率很大，區塊鏈狀態回滾的現象很頻繁。

所謂的狀態回滾指的是：（1）區塊鏈內容發生了重組織，鏈頭髮生切換（2）區塊鏈的世界狀態（賬戶資訊）需要進行回滾，即對之前的操作進行撤銷。

MPT樹就提供了一種機制，可以當區塊碰撞發生了，零延遲地完成世界狀態的回滾。這種優勢的代價就是需要浪費儲存空間去冗餘地儲存每個節點的歷史狀態。

每個節點在資料庫中的儲存都是值驅動的。當一個節點的內容發生了變化，其雜湊相應改變，而MPT將雜湊作為資料庫中的索引，也就實現了對於每一個值，在資料庫中都有一條確定的記錄。而MPT是根據節點雜湊來關聯父子節點的，因此每當一個節點的內容發生變化，最終對於父節點來說，改變的只是一個雜湊索引值；父節點的內容也由此改變，產生了一個新的父節點，遞迴地將這種影響傳遞到根節點。最終，一次改變對應建立了一條從被改節點到根節點的新路徑，而舊節點依然可以根據舊根節點透過舊路徑訪問得到。

示例：

在上圖中，一個節點的內容由27變為45，就對應成建立了一條由藍線圈出的新路徑，透過複用綠線圈出的未修改節點資訊，構造一棵新樹，而舊路徑依舊保留。故透過舊stateRoot，我們依舊能夠查詢到該節點的值為27。

所以，在以太坊中，發生分叉而進行世界狀態回滾時，僅需要用舊的MPT根節點作為入口，即可完成“狀態回滾”。

5. 輕節點擴充套件

接下來來介紹一個默克爾樹，MPT能夠提供的一個重要功能 - 默克爾證明，使用默克爾證明能夠實現輕節點的擴充套件。

5.1 什麼是輕節點

在以太坊或比特幣中，一個參與共識的全節點通常會維護整個區塊鏈的資料，每個區塊中的區塊頭資訊，所有的交易，回執資訊等。由於區塊鏈的不可篡改性，這將導致隨著時間的增加，整個區塊鏈的資料體量會非常龐大。執行在個人PC或者移動終端的可能性顯得微乎其微。為了解決這個問題，一種輕量級的，只儲存區塊頭部資訊的節點被提出。這種節點只需要維護鏈中所有的區塊頭資訊（一個區塊頭的大小通常為幾十個位元組，普通的移動終端裝置完全能夠承受出）。

在公鏈的環境下，僅僅透過本地所維護的區塊頭資訊，輕節點就能夠證明某一筆交易是否存在與區塊鏈中；某一個賬戶是否存在與區塊鏈中，其餘額是多少等功能。

5.2 什麼是默克爾證明

默克爾證明指一個輕節點向一個全節點發起一次證明請求，詢問全節點完整的默克爾樹中，是否存在一個指定的節點；全節點向輕節點返回一個默克爾證明路徑，由輕節點進行計算，驗證存在性。

5.3 默克爾證明過程

如有棵如下圖所示的merkle樹，如果某個輕節點想要驗證9Dog:64這個樹節點是否存在與默克爾樹中，只需要向全節點傳送該請求，全節點會返回一個1FXq:18, ec20,
8f74的一個路徑（默克爾路徑，如圖2黃色框所表示的）。得到路徑之後，輕節點利用9Dog:64與1FXq:18求雜湊，在與ec20求雜湊，最後與8f74求雜湊，得到的結果與本地維護的根雜湊相比，是否相等。

5.4默克爾證明安全性

（1）若全節點返回的是一條惡意的路徑？試圖為一個不存在於區塊鏈中的節點偽造一條合法的merkle路徑，使得最終的計算結果與區塊頭中的默克爾根雜湊相同。

由於雜湊的計算具有不可預測性，使得一個惡意的“全”節點想要為一條不存在的節點偽造一條“偽路徑”使得最終計算的根雜湊與輕節點所維護的根雜湊相同是不可能的。

（2）為什麼不直接向全節點請求該節點是否存在於區塊鏈中？

由於在公鏈的環境中，無法判斷請求的全節點是否為惡意節點，因此直接向某一個或者多個全節點請求得到的結果是無法得到保證的。但是輕節點本地維護的區塊頭資訊，是經過工作量證明驗證的，也就是經過共識一定正確的，若利用全節點提供的默克爾路徑，與代驗證的節點進行雜湊計算，若最終結果與本地維護的區塊頭中根雜湊一致，則能夠證明該節點一定存在於默克爾樹中。

5.5 簡單支付驗證

在以太坊中，利用默克爾證明在輕節點中實現簡單支付驗證，即在無需維護具體交易資訊的前提下，證明某一筆交易是否存在於區塊鏈中。

6.作者

戎佳磊，浙江大學VLIS實驗室在讀研究生。

以太坊愛好者&貢獻者

hyperchain平臺核心開發

[email protected]