Merkle 樹是使得區塊鏈成爲可能的基本組成部分。雖然從理論上講，打造沒有 Merkle 樹的區塊鏈是可能的，簡單地通過創建直接包含每個交易的巨大區塊頭就可以，但是這樣做會帶來巨大的可擴展性的挑戰，可以說，在很長的時間內除了最強大的計算機之外，其他任何人都無法可靠的使用區塊鏈。藉助 Merkle 樹，可以構建在所有計算機和筆記本電腦上運行的以太坊節點，這些節點可以是大型和小型智能手機，甚至是物聯網設備，例如將由 Slock.it 生產的設備。那麼這些 Merkle 樹究竟是如何工作的，他們現在和將來會提供什麼樣的價值？

首先，基礎知識。就一般意義上說。Merkle 樹是一種將大量「數據塊」散列在一起的方式，這種方式依賴於將大量的數據拆分成桶，其中每個桶只包含幾個塊，然後獲得每個桶的散列，並重復相同的過程，直到剩餘的散列總數變成一個：根散列。

Merkle 樹最常見和最簡單的形式是二分 Merkle 樹，其中一個桶總是由兩個相鄰的塊或散列組成 ; 它可以描述如下：

那麼這種奇怪的哈希算法有什麼好處呢？ 爲什麼不把所有塊連接在一起成爲一個大塊，並使用常規的哈希算法呢？答案是它允許一個稱爲 Merkle 證明的巧妙機制存在：

Merkle 證明由一個塊（樹的根散列）和由沿着從塊到根的路徑上的所有散列組成的「分支」組成。瞭解此證明的人可以驗證散列，至少對於那個分支來說，在樹上是一直保持一致，因此給定的塊實際上在樹中的那個位置。該應用很簡單：假設有一個大型數據庫，並且數據庫的全部內容都存儲在 Merkle 樹中，其中 Merkle 樹的根是公衆已知和可信的（例如，它是由足夠的受信任方進行數字簽名的，或者有很多工作證明）。然後，想要在數據庫上執行鍵值查詢（例如「告訴我位置 85273 中的對象」）的用戶可以要求 Merkle 證明，並且在收到證明後驗證它是正確的，因此實際收到的值是在具有該特定根的數據庫中的 85273 處。它允許了一種驗證少量數據機制的存在，例如 hash，被擴展用來對可能無限大小的大型數據庫進行身份驗證。

比特幣中的默克爾證明

正如中本聰在 2009 年所描述和創建的那樣，Merkle 證明的原始應用是在比特幣中。比特幣區塊鏈使用 Merkle 證明來存儲每個區塊的交易：

默克爾數證明提供的好處是中本聰描述的「簡化支付驗證」的概念：不必下載每筆交易和每個塊，「輕客戶端」只需下載區塊頭鏈，80 個字節的數據區塊只包含五樣東西：

  • 前一個區塊頭的 hash 值
  • 時間戳
  • 挖礦難度值
  • 工作量證明隨機數
  • 這個區塊包含的所有交易的默克爾樹的根哈希值

如果輕客戶端想要確定一個交易的狀態，它可以簡單地要求一個 Merkle 證明，證明一個特定的交易在 Merkle 樹中，該 Merkle 樹的根在主鏈的區塊頭中。

這讓我們相當喫驚，但比特幣風格的輕客戶端確實有其侷限性。一個特別的限制是，儘管它們可以證明交易被包含了，但它們不能證明關於當前狀態的任何信息（例如數字資產持有，名稱註冊，金融合同狀態等）。 你現在有多少比特幣？比特幣輕客戶端可以使用涉及查詢多個節點的協議，並相信至少其中一個節點會通過您的地址通知您任何特定的交易支出，這會讓您對該用例感到滿意，但對於其他更復雜的應用，這還遠遠不夠；交易影響的確切性質取決於先前幾筆交易的效果，而這些交易本身依賴於以前的交易，因此最終您必須驗證整個交易鏈中的每筆交易。爲了解決這個問題，以太坊將 Merkle 樹的概念進一步拓展。

以太坊中的默克爾證明

每個以太坊中的區塊頭包含的不僅只是一個默克爾樹的數據結構，而且還分別向三個默克爾數據庫結構提供不同的對象：

  1. 交易
  2. 收據（本質上，每片數據展示了每筆交易的結果）
  3. 狀態

這允許一個非常先進的輕客戶端協議，它將使得輕客戶容易地創建並獲得針對多種查詢的可驗證答案：

  • 這個交易在特定的區塊中嗎？
  • 告訴我過去 30 天內由此地址發佈的所有 X 類型事件的實例（例如，衆籌合同達成目標）
  • 我的當前賬戶的餘額是多少？
  • 這個賬戶存在嗎？
  • 假設在這個合約上運行這個交易。輸出會是什麼？

第一個由交易樹處理 ; 第三個和第四個由狀態樹處理，第二個由收據樹處理。 前四項計算相當簡單；服務器只需找到對象，就可以獲取 Merkle 分支（從對象到樹根的散列列表）並將分支回覆給輕客戶端。

第五個也是由狀態樹處理的，但它的計算方式更復雜。 在這裏，我們需要構建可稱爲 Merkle 狀態轉移證明的東西。從本質上講，它是一個證明，它使得聲明「如果你在具有根 S 的狀態下運行交易 T，結果將是一個具有根 S\’ 的狀態，並且具有日誌 L 和輸出 O」（在以太坊中，「輸出」作爲概念而存在，是因爲每個交易都是一個函數調用 ; 這在理論上是不必要的）。

爲了計算證明，服務器在本地創建一個假塊，將狀態設置爲 S，並在應用交易時假裝成爲輕客戶端。也就是說，如果應用交易的過程要求客戶確定帳戶的餘額，輕客戶端會進行餘額查詢。 如果輕客戶端需要檢查特定合同存儲中的特定條目，則輕客戶端爲此進行查詢，等等。服務器正確迴應所有自己的查詢，但會跟蹤它返回的所有數據。 然後服務器向客戶端發送來自所有這些請求的組合數據作爲證據。然後客戶端執行完全相同的程序，但是使用查詢反饋所提供的證據作爲其數據庫 ; 如果其結果與服務器聲明的結果相同，則客戶端接受該證明。

Patricia 樹

上面提到，最簡單的默克爾樹是二分默克爾樹 ; 然而，以太坊使用的樹更復雜 – 這就是你在我們的文檔中所聽說的「Merkle Patricia 樹」。本文不會詳細說明 ; 但是我會討論基本的原理，這篇文章和還有這一篇對此進行了最好的解釋。

二分 Merkle 樹是用於驗證處於「列表」格式的信息的非常好的數據結構 ; 從本質上講，是一系列的大塊數據，一個跟着一個。對於交易樹，它們也是很好的，因爲樹一旦被創建，然後就永久凍結，所以樹被創建後，編輯樹需要多少時間並不重要。

但是，對於狀態樹，情況更爲複雜。以太坊的狀態基本上由一個鍵值映射組成，其中鍵是地址，值是賬戶聲明，列出了每個賬戶的餘額，隨機數，代碼和每個賬戶的存儲（這裏存儲本身也是樹）。例如，Morden testnet 創始狀態如下所示：

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

但是，與交易歷史（固化）不同的是，狀態需要頻繁更新：帳戶的餘額和隨機數經常更改，而且新帳戶頻繁插入，並且存儲中的鍵經常被插入和刪除。因此需要一種可以在插入，更新編輯或刪除操作後快速計算新的樹根的數據結構，而無需重新計算整個樹。 還有兩個非常理想的次要屬性：

  • 樹的深度是有限的，即使攻擊者故意製作交易以使樹儘可能深對此也不會有影響。 否則，攻擊者可以通過操縱樹來執行拒絕服務攻擊，使得每個更新變得非常緩慢。
  • 樹的根僅取決於數據，而不取決於更新的順序。 以不同的順序進行更新，甚至從頭開始重新計算樹都不改變樹的根。

簡而言之，Patricia 樹可能是我們可以同時實現所有這些特性中最接近的解決方案。關於它如何工作的最簡單的解釋是，存儲值的關鍵字被編碼到必須記錄下的樹的「路徑」中。每個節點有 16 個子節點，所以路徑是由十六進制編碼決定的：例如，編碼的密鑰狗十六進制是 6 4 6 15 6 7，所以你可以從根開始，沿着第六個子節點，然後是第四個子節點，然後，直到你到達最後。在實踐中，當樹很稀疏時，我們可以做一些額外的優化來使過程更加高效，但這是基本原則。 上面提到的兩篇文章更詳細地描述了所有的特徵。