本文主要介紹了默克爾樹的基礎資料結構，以及默克爾樹相關的應用延伸的起點。
默克爾樹簡介
（正常區塊鏈中的默克爾樹）
本文主要介紹了默克爾樹的基礎資料結構，以及默克爾樹相關的應用延伸的起點。
在Coursera平臺的比特幣和加密貨幣技術課程中，作者學習瞭如何使用基於雜湊的資料結構來驗證P2P網路系統中資料完整性的基礎知識。該課程中提到的核心資料結構之一是默克爾樹，它存在於比特幣區塊鏈中，以一種非常有效地節省空間和時間的方式，來幫助驗證交易的存在(本文後面會詳細介紹!)。作者深入研究了默克爾樹，意識到這個資料結構實際上是多麼豐富的，所以決定寫一篇默克爾樹學習筆記。
默克爾樹解說
默克爾樹構建完成後，看起來是這樣：
（這是一個基本的默克爾樹結構，中間節點可縮寫為H（ab）和H（cd），如果沒有縮寫的話，根雜湊也可以為H（H（H（a）+ H（b）） + H（H（c）+ H（d））））
a、b、c、d是一些資料元素（檔案，公鑰、私鑰，JSON等），H是雜湊函式。如果你不是很瞭解雜湊函式，可以把它理解為資料塊的“資料指紋”，Hash是一個把任意長度的資料對映成固定長度資料的函式，而根據Hash值反推原始輸入資料的特徵是幾乎不可能的。每個節點都是透過雜湊運算父節點得到的，默克爾樹的常見結構是二叉樹，但也有非二叉樹結構的，比如以太坊平上默克爾樹。本文只討論這種最常見的二叉樹結構。
自下而上透過雜湊運算相同高度的節點，直至生成默克爾樹根節點。在生成默克爾樹的時候，如果存在單個葉子節點無法匹配成對，就需要特殊處理這個情況，除此之外，樹的構造非常簡單。
默克爾樹構建完成後，就可以在O(log n)時間內使用根雜湊對葉子進行驗證（這也稱為默克爾樹證明），驗證工作是透過重新建立包含從根到被驗證的資料段進行的。在上面的例子中，如果想要驗證c（假設我們有根雜湊值），那麼就需要得到H（d）和H（H（a）+ H（b））。資料c雜湊後得到H（c），再將H（c）與H（d）進行雜湊運算，然後將H（cd）與H（ab）在進行雜湊運算，得到一個最後的雜湊值，如果這個雜湊值與根雜湊相同，則說明c確實是默克爾樹中資料的一部分。
在BT下載等情況下，是由另一方提供資料c， H（d）和H（H（a）+ H（b））的，如果你擔心這種方法的安全性，請記住在一個雜湊函式上不可能找到e值使得H（E）= H（C）。這意味著只要根雜湊是正確的，其他人很難作假他們提供的資料。
輸出某些資料的驗證路徑和重新建立通向默克爾樹根的分支一樣簡單。在數字簽名方案中使用默克爾樹時，驗證整個默克爾樹及其各個葉子節點自身的資料就很重要，並且這實際上是可以在O(log n)時間內完成。有一些更高階（但很複雜）的演算法是可以完成這一輸出過程的。
默克爾樹的執行方法
下圖是完整版本的程式碼，作者將會在這裡解釋建立和驗證默克爾樹的方法。注意build_tree（建立默克爾樹）和_audit（驗證）方法都是來自較大類的例項方法。
構建樹的方法是將葉子新增到堆疊中，並檢查堆疊中的前兩個節點是否具有相同的高度。當高度相同時，節點有一個“子值”(兩個節點雜湊值相連後的再次雜湊值)，當高度不同時，一個新節點會追加到堆疊中。當最後兩個節點高度不同時，需要處理這種邊緣情況。
上面的方法在單節點情況下會失敗，因為不滿足任何條件，所以有一個小方法來處理完整性。
上圖是本文要解釋的驗證過程。公開驗證方法會檢查一些先決條件，這就是為什麼大部分邏輯放在這個私人版本中的原因。
默克爾樹的應用
默克爾樹在區塊鏈中應用，近年來引起了人們的廣泛關注。在許多P2P網路系統中(不僅僅是區塊鏈)，個人需要能夠從不受信任的一方獲取資料，並證明對方傳送給他們的內容是他們想要的真實內容。BT檔案(種子檔案)就是一個例子：當你下載一個BT檔案時，你會收到別人在網上“播種”的BT檔案，但是你怎麼能確定這些檔案真的，是你要下載的內容，而不是垃圾或惡意軟體呢?默克爾樹可以對從對方接收到的資料進行身份驗證，以解決這個信任問題。
類似的問題也適用於像比特幣和以太坊這樣的加密貨幣：如果有人聲稱另一個同行在交易中向他們支付了費用，那麼網路上的一個節點如何驗證交易是否真的發生了呢?一種方法是，節點可以儲存曾經發生過的完整交易歷史記錄，但是，就節點的時間和空間成本而言，這是不現實的。默克爾樹提供了一種解決方案，可以為網路上的節點節省時間和空間。透過每個區塊中的交易資料建立默克爾樹，可以在O(log n)時間（而不是線性時間）內審計交易。此外，它為一些比特幣客戶端提供了新的解決方案，可以節省空間，只儲存默克爾樹根，不需要儲存歷史每一筆交易，這創造了巨大的價值!
除了區塊鏈和BT下載，默克爾樹還能在任何需要有效檢測不一致性的系統中被應用:
證書頒發機構(CAs)使用默克爾樹作為證書透明性的一種方法。在這裡，公鑰私鑰對被視為默克爾樹的葉子。這是CAs用來防止某個CA可能耍無賴並試圖在某個領域的所有者不知道證書的情況下對該領域的證書進行認證的一種機制。
高度可伸縮的資料庫，如Apache Cassandra和Dynamo DB，處理網路上覆制資料庫的故障。這個過程被稱為“反熵”，Apache Cassandra部落格和Amazon Dynamo DB論文對其進行了較為深入的描述。
RSA的數字簽名替代品，在這種情況下，默克爾樹的根充當公鑰，單個節點用作一次性簽名。最近，人們做了更多的工作來推進這種技術，因為理論上它可以抵抗量子計算攻擊(和RSA不一樣，默克爾樹為當今大多數公鑰密碼術提供了支援)。
默克爾樹的應用確實很多，在任何特定領域的默克爾樹應用都是需要長篇大論來論述的，在這裡我們只做簡單的介紹。
原文：https://hackernoon.com/merkle-tree-introduction-4c44250e2da7
