06.20 區塊鏈中的Merkle Tree

一家運輸公司接到一批貨物有運輸單，貨物量很多，由於不能一次運輸完，於是運輸公司把貨物拆分為小量，採用多次運輸。每一次運輸都會給到對方一個貨物清單，等貨物全部送到的時候，對方拿著送貨清單，清點貨物，檢查貨物是否完成，有沒有存在缺漏遺失的現象。

在網絡傳輸中，需要傳輸大文件的時候，也採用貨物運輸的方式，把文件拆分很多的數據塊各自進行傳輸。那麼傳送數據的“送貨清單”是什麼，這個是哈希值，因為哈希函數可以驗證信息的完整性。

我給你傳輸數據之前，先把數據的哈希結果告訴你，等你收到文件再計算一次哈希然後和收到的哈希比較就知道文件有無損壞。

在傳輸大數據文件的時候需要一份哈希列表，列表中每一項都對應一個數據塊的哈希值，如果只要一部分數據就OK了。可是要去歷遍所有數據塊的哈希，這個成本比較高。那有沒有可能只獲取部分數據的哈希，也能驗證文件的完整性？

這個當然是有的，它就是Merkle tree。

Merkle Tree，通常也被稱作Hash Tree，顧名思義，就是存儲hash值的一棵樹，Merkle樹的葉子是數據塊的hash值，非葉節點是其對應子節點串聯字符串的hash。在區塊鏈中，每一個區塊中都有一個Merkle Tree，用來儲存交易信息，並對交易信息進行完整性驗證。

在點對點網絡中作數據傳輸的時候，會同時從多個機器上下載數據，而且很多機器可以認為是不穩定或者不可信的。為了校驗數據的完整性，更好的辦法是把大的文件分割成小的數據塊（例如，把分割成2K為單位的數據塊）。這樣的好處是，如果小塊數據在傳輸過程中損壞了，那麼只要重新下載這一快數據就行了，不用重新下載整個文件。

怎麼確定小的數據塊沒有損壞呢？

很簡單，只需要為每個數據塊做Hash。BT下載的時候，在下載到真正數據之前，我們會先下載一個Hash列表。那麼問題又來了，怎麼確定這個Hash列表本事是正確的哪？答案是把每個小塊數據的Hash值拼到一起，然後對這個長字符串在作一次Hash運算，這樣就得到Hash列表的根Hash(Top Hash or Root Hash)。下載數據的時候，首先從可信的數據源得到正確的根Hash，就可以用它來校驗Hash列表了，然後通過校驗後的Hash列表校驗數據塊。

但有了Merkle Tree就好辦多了，Merkle Tree可以看做Hash List的泛化（Hash List可以看作一種特殊的Merkle Tree，即樹高為2的多叉Merkle Tree）。在最底層，和哈希列表一樣，我們把數據分成小的數據塊，有相應地哈希和它對應。但是往上走，並不是直接去運算根哈希，而是把相鄰的兩個哈希合併成一個字符串，然後運算這個字符串的哈希，這樣每兩個哈希就結婚生子，得到了一個”子哈希“。

如果最底層的哈希總數是單數，那到最後必然出現一個單身哈希，這種情況就直接對它進行哈希運算，所以也能得到它的子哈希。於是往上推，依然是一樣的方式，可以得到數目更少的新一級哈希，

在p2p網絡下載網絡之前，先從可信的源獲得文件的Merkle Tree樹根，一旦獲得了樹根，就可以從其他從不可信的源獲取Merkle tree。通過可信的樹根來檢查接受到的Merkle Tree，如果Merkle Tree是損壞的或者虛假的，就從其他源獲得另一個Merkle Tree，直到獲得一個與可信樹根匹配的Merkle Tree。

Merkle Tree和Hash List的主要區別是:可以直接下載並立即驗證Merkle Tree的一個分支。因為可以將文件切分成小的數據塊，這樣如果有一塊數據損壞，僅僅重新下載這個數據塊就行了。如果文件非常大，那麼Merkle tree和Hash list都很到，但是Merkle tree可以一次下載一個分支，然後立即驗證這個分支，如果分支驗證通過，就可以下載數據了。而Hash list只有下載整個hash list才能驗證。

那Merkle Tree如何創建呢？

假設一個區塊中，加入最低層有4個數據塊，每個交易數據兩兩配對進行Hash運算，構成Merkle Tree節點，以此推進，進而生成整個Merkle Tree，如下圖：

第1步:（紅色線）對數據塊做Hash運算；

第2步: （黃色線）相鄰兩個Hash值配對，做Hash運算；

第3步：（藍色線）重複第2步，生成Merkle Tree Root。

Merkle Tree的應用

1. 數字簽名

最初Merkle Tree目的是高效的處理Lamport one-time signatures,每一個Lamport key只能被用來簽名一個消息，但是與Merkle tree結合可以來簽名多條Merkle。這種方法成為了一種高效的數字簽名框架，即Merkle Signature Scheme。

2. P2P網絡

在P2P網絡中，Merkle Tree用來確保從其他節點接受的數據塊沒有損壞且沒有被替換，甚至檢查其他節點不會欺騙或者發佈虛假的塊。大家所熟悉的BT下載就是採用了P2P技術來讓客戶端之間進行數據傳輸，一來可以加快數據下載速度，二來減輕下載服務器的負擔。BT即BitTorrent，是一種中心索引式的P2P文件分分析通信協議。

​