公眾號回復「1」，拉你進區塊鏈技術討論微信群

作者：佚名

文章來源：區塊鏈社區HiBlock

內容來源：Vitalik Buterin博客、CSDN-星空專欄、陳建慧程序人生，公眾號-Astar區塊鏈實驗室、幣姥爺日記

本文約6500字+，閱讀（觀看）需要38分鐘

1Merkle tree

梅克爾樹，又叫哈希樹，顧名思義，就是存儲hash值的一棵樹。是一種二叉樹，由一個根節點、一組中間節點和一組葉節點組成。最下面的葉節點包含存儲數據或其哈希值，每個中間節點是它的兩個孩子節點內容的哈希值，根節點也是由它的兩個子節點內容的哈希值組成。

比特幣的一個重要特性，這區塊是存在一個多級數據結構中的 。一個區塊的「哈希值」實際上只是 這個區塊的頭信息的哈希值，一個大約 200 個位元組的數據，其中包含了時間戳，隨機數，上一個區 塊的哈希和一個存儲了這個區塊中所有交易的稱之為默克爾樹的數據結構的根哈希。

2梅克爾樹的結構和特徵

如圖，我們來看梅克爾樹的數據結構，所有的數據區塊兩兩分組（如圖的最底層），指向這些數據的哈希指針被儲存在上一層的父節點（parent node）中。

而這些父節點再次被兩兩分組，並且指向父節點的指針被儲存在上一層的父節點中，一直持續這個過程，直到我們得到一個單一的區塊，即樹根節點。

根據梅克爾樹的數據結構，我們可以清楚的了解到，只要我們記住最前面的樹根節點的哈希指針，我們就可以根據哈希指針回溯到表中的任意位置，這讓我們能保證表中的數據不被篡改。

如果有人篡改了梅克爾樹底部的一些數據區塊，會導致上一層的哈希指針不匹配，那麼他不得不一直篡改上一層的哈希指針，直到數的頂端，而此刻，篡改即將終止，因為我們存儲了樹根節點的哈希指針。

因此，只要我們記住樹根頂部的哈希指針，任何企圖篡改數據的行為都會被檢測到，這讓數據篡改變得不可能實現。

梅克爾樹的特點：

MT是一種樹，大多數是二叉樹，也可以多叉樹，無論是幾叉樹，它都具有樹結構的所有特點；

Merkle Tree的葉子節點的value是數據集合的單元數據或者單元數據HASH。

非葉子節點的value是根據它下面所有的葉子節點值，然後按照Hash演算法計算而得出的。

通常，加密的hash方法像SHA-2和MD5用來做hash。但如果僅僅防止數據不是蓄意的損壞或篡改，可以改用一些安全性低但效率高的校驗和演算法，如CRC。

Second Preimage Attack: Merkle tree的樹根並不表示樹的深度，這可能會導致second-preimage attack，即攻擊者創建一個具有相同Merkle樹根的虛假文檔。一個簡單的解決方法在Certificate Transparency中定義：當計算葉節點的hash時，在hash數據前加0x00。當計算內部節點是，在前面加0x01。另外一些實現限制hash tree的根，通過在hash值前面加深度前綴。因此，前綴每一步會減少，只有當到達葉子時前綴依然為正，提取的hash鏈才被定義為有效。

3梅克爾樹的形式

1

二進位梅克爾樹

梅克爾樹最為常見和最簡單的形式，是二進位梅克爾樹（ binary Mekle tree），其中一bucket單位的數據塊總是包含了兩個相鄰的塊或哈希，它的描述如下：

那麼，這種奇怪的哈希演算法有什麼好處么？為什麼不直接將這些數據塊串接成一個單獨的大塊，用常規的哈希演算法進行呢？答案在於，它允許了一個整齊的機制，我們稱之為梅克爾證明（Merkle proofs）：

一個梅克爾證明包含了一個數據塊，這顆梅克爾樹的根哈希，以及包含了所有沿數據塊到根路徑哈希的「分支」。有人認為，這種證明可以驗證哈希的過程，至少是對分支而言。應用也很簡單：假設有一個大資料庫，而該資料庫的全部內容都存儲在梅克爾樹中，並且這顆梅克爾樹的根是公開並且可信的（例如，它是由足夠多個受信方進行數字簽名過的，或者它有很多的工作量證明）。那麼，假如一位用戶想在資料庫中進行一次鍵值查找（比如：「請告訴我，位置在85273的對象」），那他就可以詢問梅克爾證明，並接受到一個正確的驗證證明，他收到的值，實際上是資料庫在85273位置的特定根。它允許了一種機制，既可以驗證少量的數據，例如一個哈希，也可以驗證大型的資料庫（可能擴至無限）。

比特幣系統的梅克爾證明

梅克爾證據的原始應用是比特幣系統（Bitcoin），它是由中本聰（Satoshi Nakamoto）在2009年描述並且創造的。比特幣區塊鏈使用了梅克爾證明，為的是將交易存儲在每一個區塊中：

而這樣做的好處，也就是中本聰描述到的「簡化支付驗證」（SPV）的概念:而不是下載每一筆交易以及每一個區塊，一個「輕客戶端」（light client）可以僅下載鏈的區塊頭，每個區塊中僅包含五項內容，數據塊大小為80位元組：

上一區塊頭的哈希值

時間戳

挖礦難度值

工作量證明隨機數（nonce）

包含該區塊交易的梅克爾樹的根哈希

如果一個輕客戶端希望確定一筆交易的狀態，它可以簡單地要求一個梅克爾證明，顯示出一個在梅克爾樹特定的交易，其根是在主鏈（main chain，非分叉鏈）上的區塊頭。

它會讓我們走得很遠，但比特幣的輕客戶確實有其局限性。一個特別的限制是，它們雖然可以證明包含的交易，但無法證明任何當前的狀態（例如：數字資產的持有，名稱註冊，金融合約的狀態等）。你現在擁有了多少個比特幣？一個比特幣輕客戶端，可以使用一種協議，它涉及查詢多個節點，並相信其中至少會有一個節點會通知你，關於你的地址中任何特定的交易支出，而這可以讓你實現更多的應用。但對於其他更為複雜的應用而言，這些遠遠是不夠的。一筆交易影響的確切性質（precise nature），可以取決於此前的幾筆交易，而這些交易本身則依賴於更為前面的交易，所以最終你可以驗證整個鏈上的每一筆交易。為了解決這個問題，以太坊的梅克爾樹的概念，會更進一步。

以太坊的梅克爾證明

以太坊的每一個區塊頭，並非只包含一顆梅克爾樹，而是包含了三顆梅克爾樹，分別對應了三種對象：

交易（Transactions）

收據（Receipts，基本上，它是展示每一筆交易影響的數據條）

狀態（State）

這使得一個非常先進的輕客戶端協議成為了可能，它允許輕客戶端輕鬆地進行並核實以下類型的查詢答案：

這筆交易被包含在特定的區塊中了么？

告訴我這個地址在過去30天中，發出X類型事件的所有實例（例如，一個眾籌合約完成了它的目標）

目前我的賬戶餘額是多少？

這個賬戶是否存在？

假裝在這個合約中運行這筆交易，它的輸出會是什麼？

第一種是由交易樹（transaction tree）來處理的；第三和第四種則是由狀態樹（state tree）負責處理，第二種則由收據樹（receipt tree）處理。計算前四個查詢任務是相當簡單的。伺服器簡單地找到對象，獲取梅克爾分支，並通過分支來回復輕客戶端。

第五種查詢任務同樣也是由狀態樹處理，但它的計算方式會比較複雜。這裡，我們需要構建下我們稱之為梅克爾狀態轉變的證明（Merkle state transition proof）。從本質上來講，這樣的證明也就是在說「如果你在根S的狀態樹上運行交易T，其結果狀態樹將是根為S"，log為L，輸出為O」 （「輸出」作為存在於以太坊的一種概念，因為每一筆交易都是一個函數調用，它在理論上並不是必要的）。

為了推斷這個證明，伺服器在本地創建了一個假的區塊，將狀態設為 S，並假裝是一個輕客戶端，同時請求這筆交易。也就是說，如果請求這筆交易的過程，需要客戶端確定一個賬戶的餘額，這個輕客戶端會發出一個餘額疑問。如果這個輕客戶端需要檢查存儲在一個特定合約的特定項目，該輕客戶端會對此發出針對查詢。伺服器會正確地「回應」它所有的查詢，但伺服器也會跟蹤它所有發回的數據。然後，伺服器會把綜合數據發送給客戶端。客戶端會進行相同的步驟，但會使用它的資料庫所提供的證明。如果它的結果和伺服器要求的是相同的，那客戶端就接受證明。

2

帕特里夏樹（Patricia Trees）

前面我們提到，最為簡單的一種梅克爾樹是二進位梅克爾樹。然而，以太坊所使用的梅克爾樹則更為複雜，我們稱之為「梅克爾.帕特里夏樹」（Merkle Patricia tree）。

二進位梅克爾樹對於驗證「清單」格式的信息而言，它是非常好的數據結構，本質上來講，它就是一系列前後相連的數據塊。而對於交易樹來說，它們也同樣是不錯的，因為一旦樹已經建立，花多少時間來編輯這顆樹並不重要，樹一旦建立了，它就會永遠存在。

而對狀態樹來說，情況會更複雜些。以太坊中的狀態樹基本上包含了一個鍵值映射，其中的鍵是地址還有各種值，包括賬戶的聲明、餘額、隨機數、代碼以及每一個賬戶的存儲（其中存儲本身就是一顆樹）。例如，摩登測試網路（the Morden testnet ）的創始狀態如下所示：

{"0000000000000000000000000000000000000001": {"balance": "1"},"0000000000000000000000000000000000000002": {"balance": "1"},"0000000000000000000000000000000000000003": {"balance": "1"},"0000000000000000000000000000000000000004": {"balance": "1"},"102e61f5d8f9bc71d0ad4a084df4e65e05ce0e1c": {"balance": "1606938044258990275541962092341162602522202993782792835301376"}}

然而，不同於交易歷史記錄，狀態樹需要經常地進行更新：賬戶餘額和賬戶的隨機數nonce經常會更變，更重要的是，新的賬戶會頻繁地插入，存儲的鍵（ key）也會經常被插入以及刪除。而這樣的數據結構設計，我們可以在一次插入、更新編輯或者刪除操作之後，快速地計算出新的樹根（tree root），而無需重新計算整顆樹。此外，它還有兩個灰常好的次要特性：

樹的深度是有限制的，即使考慮攻擊者會故意地製造一些交易，使得這顆樹儘可能地深。不然，攻擊者可以通過操縱樹的深度，執行拒絕服務攻擊（DOS attack），使得更新變得極其緩慢。

樹的根只取決於數據，和其中的更新順序無關。換個順序進行更新，甚至重新從頭計算樹，並不會改變根。

而帕特里夏樹，簡單地說，或許最接近的解釋是，我們可以同時實現所有的這些特性。其工作原理，最為簡單的解釋是，一個以編碼形式存儲到記錄樹的「路徑」的值。每個節點會有16個子（children），所以路徑是由十六進位編碼來確定的：例如，狗（dog）的鍵的編碼為6 4 6 15 6 7，所以你會從這個根開始，下降到第六個子，然後到第四個，並依次類推，直到你達到終點。在實踐中，當樹稀少時也會有一些額外的優化，我們會使過程更為有效，但這是基本的原則。

4Merkle Tree的操作

1

創建Merckle Tree

加入最底層有9個數據塊。

step1：（紅色線）對數據塊做hash運算，Node0i = hash(Data0i), i=1,2,…,9

step2: （橙色線）相鄰兩個hash塊串聯，然後做hash運算，Node1((i+1)/2) = hash(Node0i+Node0(i+1)), i=1,3,5,7;對於i=9, Node1((i+1)/2) = hash(Node0i)

step3: （黃色線）重複step2

step4：（綠色線）重複step2

step5：（藍色線）重複step2，生成Merkle Tree Root

易得，創建Merkle Tree是O(n)複雜度(這裡指O(n)次hash運算)，n是數據塊的大小。得到Merkle Tree的樹高是log(n)+1。

2

檢索數據塊

為了更好理解，我們假設有A和B兩台機器，A需要與B相同目錄下有8個文件，文件分別是f1 f2 f3 ….f8。這個時候我們就可以通過Merkle Tree來進行快速比較。假設我們在文件創建的時候每個機器都構建了一個Merkle Tree。具體如下圖:

從上圖可得知，葉子節點node7的value = hash(f1),是f1文件的HASH;而其父親節點node3的value = hash(v7, v8)，也就是其子節點node7 node8的值得HASH。就是這樣表示一個層級運算關係。root節點的value其實是所有葉子節點的value的唯一特徵。

假如A上的文件5與B上的不一樣。我們怎麼通過兩個機器的merkle treee信息找到不相同的文件? 這個比較檢索過程如下:

Step1. 首先比較v0是否相同,如果不同，檢索其孩子node1和node2.

Step2. v1 相同，v2不同。檢索node2的孩子node5 node6;

Step3. v5不同，v6相同，檢索比較node5的孩子node 11 和node 12

Step4. v11不同，v12相同。node 11為葉子節點，獲取其目錄信息。

Step5. 檢索比較完畢。

以上過程的理論複雜度是Log(N)。過程描述圖如下:

從上圖可以得知真箇過程可以很快的找到對應的不相同的文件。

3

更新，插入和刪除

雖然網上有很多關於Merkle Tree的資料，但大部分沒有涉及Merkle Tree的更新、插入和刪除操作，討論Merkle Tree的檢索和遍歷的比較多。我也是非常困惑，一種樹結構的操作肯定不僅包括查找，也包括更新、插入和刪除的啊。後來查到stackexchange上的一個問題，才稍微有點明白。

對於Merkle Tree數據塊的更新操作其實是很簡單的，更新完數據塊，然後接著更新其到樹根路徑上的Hash值就可以了，這樣不會改變Merkle Tree的結構。但是，插入和刪除操作肯定會改變Merkle Tree的結構，如下圖，一種插入操作是這樣的：

插入數據塊0後(考慮數據塊的位置)，Merkle Tree的結構是這樣的：

在考慮一種插入的演算法，滿足下麵條件：

- re-hashing操作的次數控制在log(n)以內

- 數據塊的校驗在log(n)+1以內

- 除非原始樹的n是偶數，插入數據後的樹沒有孤兒，並且如果有孤兒，那麼孤兒是最後一個數據塊

- 數據塊的順序保持一致

- 插入後的Merkle Tree保持平衡

然後上面的插入結果就會變成這樣：

Merkle Tree的插入和刪除操作其實是一個工程上的問題，不同問題會有不同的插入方法。如果要確保樹是平衡的或者是樹高是log(n)的，可以用任何的標準的平衡二叉樹的模式，如AVL樹，紅黑樹，伸展樹，2-3樹等。這些平衡二叉樹的更新模式可以在O(lgn)時間內完成插入操作，並且能保證樹高是O(lgn)的。那麼很容易可以看出更新所有的Merkle Hash可以在O((lgn)2)時間內完成（對於每個節點如要更新從它到樹根O(lgn)個節點，而為了滿足樹高的要求需要更新O(lgn)個節點）。如果仔細分析的話，更新所有的hash實際上可以在O(lgn)時間內完成，因為要改變的所有節點都是相關聯的，即他們要不是都在從某個葉節點到樹根的一條路徑上，或者這種情況相近。

實際上Merkle Tree的結構(是否平衡，樹高限制多少)在大多數應用中並不重要，而且保持數據塊的順序也在大多數應用中也不需要。因此，可以根據具體應用的情況，設計自己的插入和刪除操作。一個通用的Merkle Tree插入刪除操作是沒有意義的。

Merkle Tree目前的應用範圍包括：數字簽名、P2P網路、Trusted Computing、比特幣以太坊的梅克爾證明等。

文章發布只為分享區塊鏈技術內容，版權歸原作者所有，觀點僅代表作者本人，絕不代表區塊鏈兄弟贊同其觀點或證實其描述。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！