Merkle Tree（默克爾樹）算法解析

Merkle Trees 以計算機科學家 Ralph Merkle 的名字命名，他是與 Merkle Trees 一起發明了公鑰密碼學和密碼散列的教授。Merkle Tree，通常也被稱作Hash Tree，顧名思義，就是存儲hash值的一棵樹。Merkle樹的葉子是數據塊(例如，文件或者文件的集合)的hash值。非葉節點是其對應子節點串聯字符串的hash。

01

Merkle Tree概念

1、Hash

Hash是一個把任意長度的數據映射成固定長度數據的函數。例如，對於數據完整性校驗，最簡單的方法是對整個數據做Hash運算得到固定長度的Hash值，然後把得到的Hash值公布在網上，這樣用戶下載到數據之後，對數據再次進行Hash運算，比較運算結果和網上公布的Hash值進行比較，如果兩個Hash值相等，說明下載的數據沒有損壞。可以這樣做是因為輸入數據的稍微改變就會引起Hash運算結果的面目全非，而且根據Hash值反推原始輸入數據的特徵是困難的。           

如果從一個穩定的服務器進行下載，採用單一Hash是可取的。但如果數據源不穩定，一旦數據損壞，就需要重新下載，這種下載的效率是很低的。

2、Hash List

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

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

3、 Merkle Tree

Merkle Tree可以看做Hash List的泛化（Hash List可以看作一種特殊的Merkle Tree，即樹高為2的多叉Merkle Tree）。

在最底層，和哈希列表一樣，我們把數據分成小的數據塊，有相應的哈希和它對應。但是往上走，並不是直接去運算根哈希，而是把相鄰的兩個哈希合並成一個字符串，然後運算這個字符串的哈希，這樣每兩個哈希就結婚生子，得到了一個”子哈希“。如果最底層的哈希總數是單數，那到最後必然出現一個單身哈希，這種情況就直接對它進行哈希運算，所以也能得到它的子哈希。於是往上推，依然是一樣的方式，可以得到數目更少的新一級哈希，最終必然形成一棵倒掛的樹，到了樹根的這個位置，這一代就剩下一個根哈希了，我們把它叫做 Merkle Root[3]。

在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才能驗證。

02

Merkle Tree的特點

Merkle Tree的特點主要包括如下方面：1、Merkle Tree是一種樹，大多數是二叉樹，也可以多叉樹，無論是幾叉樹，它都具有樹結構的所有特點；2、Merkle Tree的葉子節點的value是數據集合的單元數據或者單元數據HASH。3、非葉子節點的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鏈才被定義為有效。

03

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文件分分析通信協議。

要進下載必須從中心索引服務器獲取一個擴展名為torrent的索引文件（即大家所說的種子），torrent文件包含了要共享文件的信息，包括文件名，大小，文件的Hash信息和一個指向Tracker的URL[8]。Torrent文件中的Hash信息是每一塊要下載的文件內容的加密摘要，這些摘要也可運行在下載的時候進行驗證。

大的torrent文件是Web服務器的瓶頸，而且也不能直接被包含在RSS或gossiped around(用流言傳播協議進行傳播)。一個相關的問題是大數據塊的使用，因為為了保持torrent文件的非常小，那么數據塊Hash的數量也得很小，這就意味着每個數據塊相對較大。大數據塊影響節點之間進行交易的效率，因為只有當大數據塊全部下載下來並校驗通過後，才能與其他節點進行交易。

就解決上面兩個問題是用一個簡單的Merkle Tree代替Hash List。設計一個層數足夠多的二叉樹，葉節點是數據塊的Hash，不足的葉節點用0來代替。上層的節點是其對應孩子節點串聯的hash。Hash算法和普通torrent一樣採用SHA1。其數據傳輸過程和第一節中描述的類似。

3、Trusted Computing

可信計算是可信計算組為分布式計算環境中參與節點的計算平臺提供端點可信性而提出的。可信計算技術在計算平臺的硬件層引入可信平臺模塊(Trusted Platform，TPM)，實際上為計算平臺提供了基於硬件的可信根(Root of trust，RoT)。

從可信根出發，使用信任鏈傳遞機制，可信計算技術可對本地平臺的硬件及軟件實施逐層的完整性度量，並將度量結果可靠地保存在TPM的平臺配置寄存器(Platform configuration register，PCR)中，此後遠程計算平臺可通過遠程驗證機制(Remote Attestation)比對本地PCR中度量結果，從而驗證本地計算平臺的可信性。可信計算技術讓分布式應用的參與節點擺脫了對中心服務器的依賴，而直接通過用戶機器上的TPM芯片來建立信任，使得創建擴展性更好、可靠性更高、可用性更強的安全分布式應用成為可能。可信計算技術的核心機制是遠程驗證(remote attestation),分布式應用的參與結點正是通過遠程驗證機制來建立互信,從而保障應用的安全。

這一種基於Merkle Tree的遠程驗證機制，其核心是完整性度量值哈希樹。

首先，RAMT 在內核中維護的不再是一張完整性度量值列表(ML),而是一棵完整性度量值哈希樹(integrity measurement hash tree,簡稱IMHT).其中,IMHT的葉子結點存儲的數據對象是待驗證計算平臺上被度量的各種程序的完整性哈希值，而其內部結點則依據Merkle 哈希樹的構建規則由子結點的連接的哈希值動態生成。

其次，為了維護IMHT 葉子結點的完整性，RAMT 需要使用TPM 中的一段存儲器來保存IMHT 可信根哈希的值。

再次，RAMT 的完整性驗證過程基於認證路徑(authentication path)實施.認證路徑是指IMHT 上從待驗證葉子結點到根哈希的路徑。

4、 Merkle DAG

Merkle DAG是IPFS系統的核心概念之一，當然Merkle DAG並不是IPFS團隊發明的，它來來自於Git數據結構，ipfs團隊進行了改造。Merkle DAG的全稱是 Merkle directed acyclic graph（默克有向無環圖）。Merkle DAG跟Merkle tree很相似，它是在Merkle tree基礎上構建的，但又不完全一樣，比如：Merkle DAG不需要進行樹的平衡操作，非葉子節點允許包含數據等。

Merkle DAG擁有如下的功能：

內容尋址：使用多重哈希來唯一識別一個數據塊的內容

防篡改：可以方便的檢查哈希值來確認數據是否被篡改

去重：由於內容相同的數據塊哈希是相同的，可以很容去掉重復的數據，節省存儲空間

IPFS的數據對象格式如下：

Data：非結構的二進制數據，大小小於256kB

Links：一個Link數據結構的數組。IPFS對象通過他們鏈接到其他對象

Link數據結構包含三個域：

Name：Link的名字

Hash：Link鏈接到對象的Hash

Size：Link鏈接到對象的累積大小，包括它的Links

測試指南：

第一步：如果你要測試的話，使用一個超過256k的數據文件比較好，因為ipfs當前的數據分片是 256k大小一個。

第二步：執行ipfs add 命令，添加文件

第三步：使用命令 ipfs -ls -v 來查看文件的分片

如下所示，可以看到文件被分成了15個block。每個block大小時256k（除了最後一個）。

當執行 ipfs add 的時候，文件first.JPG的數據被分成了一個個大小均等的block並且構造一個Merkle DAG把文件數據片組織起來。

可以使用IPFS提供的命令來查看數據塊（block）的信息，數據塊block下面還允許鏈接子數據塊（sub-block，本文的例子中沒有涉及）。

相關的查詢命令如下：

ipfs block stat: 查詢block的數據大小，不包含子塊。

ipfs refs：列出來數據塊的子塊信息

ipfs ls or ipfs object links：顯示所有的子塊和塊的大小

IPFS可以表示Git使用的數據結構，Git commit object。Commit Object主要的特點是他有一個或多個名為’parent0’和‘parent1’等的鏈接（這些鏈接指向前一個版本），以及一個名為object的對象(在Git中成為tree)指向引用這個commit的文件系統結構。

5、BitCoin的Merkle Proof

Merkle Proof最早的應用是Bitcoin，它是由中本聰在2009年描述並創建的。Bitcoin的Blockchain利用Merkle proofs來存儲每個區塊的交易。

而這樣做的好處，也就是中本聰描述到的“簡化支付驗證”（Simplified Payment Verification，SPV）的概念:一個“輕客戶端”（light client）可以僅下載鏈的區塊頭即每個區塊中的80byte的數據塊，僅包含五個元素，而不是下載每一筆交易以及每一個區塊：上一區塊頭的哈希值；時間戳；挖礦難度值；工作量證明隨機數（nonce）；包含該區塊交易的Merkle Tree的根哈希。

如果客戶端想要確認一個交易的狀態，它只需簡單的發起一個Merkle proof請求，這個請求顯示出這個特定的交易在Merkle trees的一個之中，而且這個Merkle Tree的樹根在主鏈的一個區塊頭中。

但是Bitcoin的輕客戶端有它的局限。一個局限是，盡管它可以證明包含的交易，但是它不能進行涉及當前狀態的證明（如數字資產的持有，名稱注冊，金融合約的狀態等）。

Bitcoin如何查詢你當前有多少幣？一個比特幣輕客戶端，可以使用一種協議，它涉及查詢多個節點，並相信其中至少會有一個節點會通知你，關於你的地址中任何特定的交易支出，而這可以讓你實現更多的應用。但對於其他更為復雜的應用而言，這些遠遠是不夠的。一筆交易影響的確切性質（precise nature），可以取決於此前的幾筆交易，而這些交易本身則依賴於更為前面的交易，所以最終你可以驗證整個鏈上的每一筆交易。為了解決這個問題，Ethereum的Merkle Tree的概念，會更進一步。

6、Ethereum的Merkle Proof

每個以太坊區塊頭不是包括一個Merkle樹，而是為三種對象設計的三棵樹：交易Transaction；收據Receipts(本質上是顯示每個交易影響的多塊數據)；狀態State。

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

這筆交易被包含在特定的區塊中了么？告訴我這個地址在過去30天中，發出X類型事件的所有實例（例如，一個衆籌合約完成了它的目標）。目前我的账戶余額是多少？這個账戶是否存在？假如在這個合約中運行這筆交易，它的輸出會是什么？

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

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

為了推斷這個證明，服務器在本地創建了一個假的區塊，將狀態設為 S，並在請求這筆交易時假裝是一個輕客戶端。也就是說，如果請求這筆交易的過程，需要客戶端確定一個账戶的余額，這個輕客戶端(由服務器模擬的)會發出一個余額查詢請求。如果需要輕客戶端在特點某個合約的存儲中查詢特定的條目，這個輕客戶端就會發出這樣的請求。也就是說服務器(通過模擬一個輕客戶端)正確回應所有自己的請求，但服務器也會跟蹤它所有發回的數據。

然後，服務器從上述的這些請求中把數據合並並把數據以一個證明的方式發送給客戶端。客戶端會進行相同的步驟，但會將服務器提供的證明作為一個數據庫來使用。如果客戶端進行步驟的結果和服務器提供的是一樣的話，客戶端就接受這個證明。       

7、MPT(Merkle Patricia Trees)

前面我們提到，最為簡單的一種Merkle Tree大多數情況下都是一棵二叉樹。然而，Ethereum所使用的Merkle Tree則更為復雜，我們稱之為“梅克爾.帕特裏夏樹”（Merkle Patricia tree）。

對於驗證屬於list格式（本質上來講，它就是一系列前後相連的數據塊）的信息而言，二叉Merkle Tree是非常好的數據結構。對於交易樹來說，它們也同樣是不錯的，因為一旦樹已經建立，花多少時間來編輯這棵樹並不重要，樹一旦建立了，它就會永遠存在並且不會改變。

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

然而，不同於交易歷史記錄，狀態樹需要經常地進行更新：账戶余額和账戶的隨機數nonce經常會更變，更重要的是，新的账戶會頻繁地插入，存儲的鍵（ key）也會經常被插入以及刪除。我們需要這樣的數據結構，它能在一次插入、更新、刪除操作後快速計算到樹根，而不需要重新計算整個樹的Hash。這種數據結構同樣得包括兩個非常好的第二特徵：

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

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

MPT是最接近同時滿足上面的性質的的數據結構。MPT的工作原理的最簡單的解釋是，值通過鍵來存儲，鍵被編碼到搜索樹必須要經過的路徑中。每個節點有16個孩子，因此路徑由16進制的編碼決定：例如，鍵‘dog’的16進制編碼是6 4 6 15 6 7，所以從root开始到第六個分支，然後到第四個，再到第六個，再到第十五個，這樣依次進行到達樹的葉子。

在實踐中，當樹稀少時也會有一些額外的優化，我們會使過程更為有效，但這是基本的原則。

8、其他應用

用到Merkle Tree的應用還有很多，比如Git，Amazon Dynamo，Apache Wave Protocol，Tahoe-LAFS backup system，Certificate Transparency framework，NoSQL systems like Apache Cassadra and Riak等

【參考文獻】

[1] https://en.wikipedia.org/wiki/Merkle_tree

[2] https://en.wikipedia.org/wiki/Hash_function#Hash_function_algorithms

[3] http://www.jianshu.com/p/458e5890662f

[4] http://blog.csdn.net/xtu_xiaoxin/article/details/8148237

[5] http://blog.csdn.net/yuanrxdu/article/details/22474697?utm_source=tuicool&utm_medium=referral

[6] http://crypto.stackexchange.com/questions/22669/merkle-hash-tree-updates

[7] https://en.wikipedia.org/wiki/BitTorrent

[8] 梁成仁, 李健勇, 黃道穎, 等. 基於 Merkle 樹的 BT 系統 torrent 文件優化策略[J]. 計算機工程, 2008, 34(3): 85-87.

[9] http://bittorrent.org/beps/bep_0030.html

[10] 徐梓耀, 賀也平, 鄧靈莉. 一種保護隱私的高效遠程驗證機制[J]. Journal of Software, 2011, 22(2).

[11] http://whatdoesthequantsay.com/2015/09/13/ipfs-introduction-by-example/

[12] https://www.weusecoins.com/what-is-a-merkle-tree/

[13] http://www.8btc.com/merkling-in-ethereum

[14]http://www.cnblogs.com/fengzhiwu/p/5524324.html

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播信息之目的，不構成任何投資建議，如有侵權行為，請第一時間聯絡我們修改或刪除，多謝。