梅克爾樹(Merkle trees)是區塊鏈的基本組成部分。雖說從理論上來講，沒有梅克爾樹的區塊鏈當然也是可能的，你只需建立直接包含每一筆交易的巨大區塊頭(block header)就可以實現，但這樣做無疑會帶來可擴充套件性方面的挑戰，從長遠發展來看，可能最後將只有那些最強大的計算機，才可以執行這些無需受信的區塊鏈。 正是因為有了梅克爾樹，以太坊節點才可以建立執行在所有的計算機、筆記本、智慧手機，甚至是那些由Slock.it生產的物聯網裝置之上。那麼，究竟梅克爾樹是如何工作的呢，它們又能夠提供些什麼價值呢，現在以及未來的?
首先，咱們先來講點基礎知識。梅克爾樹，一般意義上來講，它是雜湊大量聚集資料“塊”(chunk)的一種方式，它依賴於將這些資料“塊”分裂成較小單位(bucket)的資料塊，每一個bucket塊僅包含幾個資料“塊”，然後取每個bucket單位資料塊再次進行雜湊，重複同樣的過程，直至剩餘的雜湊總數僅變為1:即根雜湊(root hash)。
梅克爾樹最為常見和最簡單的形式，是二進位制梅克爾樹( 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，並假裝是一個輕客戶端，同時請求這筆交易。也就是說，如果請求這筆交易的過程，需要客戶端確定一個賬戶的餘額，這個輕客戶端會發出一個餘額疑問。如果這個輕客戶端需要檢查儲存在一個特定合約的特定專案，該輕客戶端會對此發出針對查詢。伺服器會正確地“迴應”它所有的查詢，但伺服器也會跟蹤它所有發回的資料。然後，伺服器會把綜合資料傳送給客戶端。客戶端會進行相同的步驟，但會使用它的資料庫所提供的證明。如果它的結果和伺服器要求的是相同的，那客戶端就接受證明。
帕特里夏樹(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，所以你會從這個根開始，下降到第六個子，然後到第四個，並依次類推，直到你達到終點。在實踐中，當樹稀少時也會有一些額外的最佳化，我們會使過程更為有效，但這是基本的原則。
梅克爾樹(Merkle trees)是區塊鏈的基本組成部分。雖說從理論上來講，沒有梅克爾樹的區塊鏈當然也是可能的，你只需建立直接包含每一筆交易的巨大區塊頭(block header)就可以實現，但這樣做無疑會帶來可擴充套件性方面的挑戰，從長遠發展來看，可能最後將只有那些最強大的計算機，才可以執行這些無需受信的區塊鏈。 正是因為有了梅克爾樹，以太坊節點才可以建立執行在所有的計算機、筆記本、智慧手機，甚至是那些由Slock.it生產的物聯網裝置之上。那麼，究竟梅克爾樹是如何工作的呢，它們又能夠提供些什麼價值呢，現在以及未來的?
首先，咱們先來講點基礎知識。梅克爾樹，一般意義上來講，它是雜湊大量聚集資料“塊”(chunk)的一種方式，它依賴於將這些資料“塊”分裂成較小單位(bucket)的資料塊，每一個bucket塊僅包含幾個資料“塊”，然後取每個bucket單位資料塊再次進行雜湊，重複同樣的過程，直至剩餘的雜湊總數僅變為1:即根雜湊(root hash)。
梅克爾樹最為常見和最簡單的形式，是二進位制梅克爾樹( 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，並假裝是一個輕客戶端，同時請求這筆交易。也就是說，如果請求這筆交易的過程，需要客戶端確定一個賬戶的餘額，這個輕客戶端會發出一個餘額疑問。如果這個輕客戶端需要檢查儲存在一個特定合約的特定專案，該輕客戶端會對此發出針對查詢。伺服器會正確地“迴應”它所有的查詢，但伺服器也會跟蹤它所有發回的資料。然後，伺服器會把綜合資料傳送給客戶端。客戶端會進行相同的步驟，但會使用它的資料庫所提供的證明。如果它的結果和伺服器要求的是相同的，那客戶端就接受證明。
帕特里夏樹(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，所以你會從這個根開始，下降到第六個子，然後到第四個，並依次類推，直到你達到終點。在實踐中，當樹稀少時也會有一些額外的最佳化，我們會使過程更為有效，但這是基本的原則。