2.2 默克爾樹

默克爾樹是由Ralph Merkle于1979年提出的，它有如下兩個特征。

（1）默克爾樹的葉子節點值是數據的哈希值，比特幣使用了SHA-256。

（2）非葉子節點的值是對所有葉子節點進行加密哈希運算得出的。

默克爾樹可以是多叉樹也可以是二叉樹，如圖2.1所示。

創建默克爾樹的流程如下。

（1）根據d₁～d₄生成第一級葉子節點V₁～V₄。

（2）根據V₁和V₂生成節點V₅，根據V₃和V₄生成節點V₆。

（3）最后根據V₅和V₆生成根節點V₇。

從創建流程可以看出，默克爾樹的樹高度是log ₂n+1，其中 n 是數據數量。圖2.1所示的默克爾樹層數是log₂ 4+1=3。

使用默克爾樹的好處是什么呢？

首先，驗證簡單。如果我們需要驗證d₂，那么我們需要用到V₁和V₆，即通過d₂運算出葉子節點V₂，用V₁和V₂運算出節點V₅，再用節點V₅和V₆運算出根節點V₇，如圖2.2所示。這樣不需要傳輸所有的數據就可以完成驗證，大大減少了驗證的時間并簡化了數據傳輸流程，特別是對于區塊鏈數據集而言，數據集越大，使用默克爾樹帶來的驗證效率的提升越明顯。

其次，默克爾樹還有一個重要特性，就是能夠快速定位到差異數據節點。舉個例子，給定默克爾樹另外一個值V₈，如果V₈和V₇的兩棵樹因d₃的不同而產生了差異，那么默克爾樹如何通過對比兩棵樹來找到不一樣的數據d₃呢？默克爾樹查找差異節點的過程如圖2.3所示。

（1）根據V₇，比較節點V₅和V₆，發現V₅相同，V₆不同。

（2）根據V₆，比較葉子節點V₃和V₄，發現V₄相同，V₃不同，因此判斷d₃異常。

默克爾樹通過比較查詢得到的最差時間復雜度是O（log₂n），即樹高度減1。我們知道時間復雜度有O（1）＜O（log₂n）＜O（n）＜O（n² ），對數時間復雜度O（log₂n）比線性的O（n）更優，特別是在數據規模較大的時候。我們以比特幣為例進行說明：如果每個交易為300Byte，使用的算法是SHA-256，哈希值為32Byte，那么隨著區塊鏈交易的增多，區塊大小為線性增長，但是哈希比較次數和默克爾樹路徑占用的存儲空間都增長得非常緩慢，如表2.1所示。

擁有這些特性的默克爾樹還可以應用于大數據的快速比對，無論數據量多大，我們可以通過對比默克爾樹的根哈希值來快速判斷數據是否一致。例如，在下載電影種子哈希比對場景中，一般我們先下載后綴為.torrent 的電影種子，再通過各種下載工具進行下載。.torrent文件是BitTorrent常見的后綴文件，BitTorrent是點對點文件傳輸協議（Peer to Peer File Sharing，P2P），作用于互聯網的文件傳輸和數據分發。BitTorrent中的節點會將文件劃分為多個數據塊，每個數據塊的大小一般是2的冪，數據大小范圍是32KB～16MB，目前我們使用SHA-1（未來遷移到SHA-256）來為每個數據塊生成哈希值，然后記錄到.torrent文件中的info數據結構的pieces字段中，一般格式如下所示：

普通的.torrent文件通過使用哈希列表（Hash List）來存儲pieces，但是在大文件中 SHA-1 的大小是160bit，即1個哈希值占用20Byte 的存儲空間，當數據塊過大時，哈希列表雖然小，卻會影響P2P的數據交換效率。反之，若數據塊過小，則哈希列表會過大，這會導致.torrent 種子的體積過大。為了平衡數據塊的體積問題，人們引入了新的默克爾樹可選擴展字段，在原格式的基礎上增加了root hash字段，該字段存儲的是默克爾樹的根哈希值，而不是完整的默克爾樹。

當發起網絡下載的時候，我們可從網絡上下載默克爾樹，并與root hash進行比較，以確保下載的正確性。同時，因為默克爾樹只需要下載分支就可以校驗數據，所以不需要完整地下載默克爾樹，只需要下載一部分就可以校驗數據的正確性。與哈希列表相比，這種方法的優勢還是很明顯的。