什么是merkle tree

假設(shè)你已經(jīng)知道了什么是哈希算法以及哈希是用來干啥的。

網(wǎng)絡(luò)傳輸數(shù)據(jù)的時候，A收到B的傳過來的文件，需要確認收到的文件有沒有損壞。如何解決？

有一種方法是B在傳文件之前先把文件的hash結(jié)果給A，A收到文件再計算一次哈希然后和收到的哈希比較就知道文件有無損壞。

但是當文件很大的時候，往往需要把文件拆分很多的數(shù)據(jù)塊各自傳輸，這個時候就需要知道每個數(shù)據(jù)塊的哈希值。怎么辦呢？

這種情況，可以在下載數(shù)據(jù)之前先下載一份哈希列表(hash list)，這個列表每一項對應(yīng)一個數(shù)據(jù)塊的哈希值。對這個hash list拼接后可以計算一個根hash。實際應(yīng)用中，我們只要確保從一個可信的渠道獲取正確的根hash，就可以確保下載正確的文件。

似乎很完美了。但是還不夠好！

上面基于hash list的方案這樣一個問題：

有些時候我們獲取(遍歷)所有數(shù)據(jù)塊的hash list代價比較大，只能獲取部分節(jié)點的哈希。

有沒有一種方法可以通過部分hash就能校驗整個文件的完整性呢？

答案是肯定的，merkle tree能做到。它長這樣子:

image

特點如下:

1、數(shù)據(jù)結(jié)構(gòu)是一個樹，可以是二叉樹，也可以是多叉樹（本BLOG以二叉樹來分析）

2、Merkle Tree的葉子節(jié)點的value是數(shù)據(jù)集合的單元數(shù)據(jù)或者單元數(shù)據(jù)HASH。

3、Merke Tree非葉子節(jié)點value是其所有子節(jié)點value的HASH值。

很明顯，這種結(jié)構(gòu)跟hash list相比較，根哈希不是用所有的數(shù)據(jù)塊哈希拼接起來計算的，而是通過一個層級的關(guān)系計算出來的。

在上圖中，葉子節(jié)點node7的value（v7) = hash(f1),是f1文件的HASH;而其父親節(jié)點node3的value = hash(v7, v8)，也就是其子節(jié)點node7 node8的值得HASH

其它應(yīng)用場景

文件下載

假設(shè)我有兩臺機器，A和B，有一個文件從A傳輸?shù)紹。B首先獲取可信的文件merkle tree，當文件下載完畢后，B通過自己構(gòu)建的merkle tree根節(jié)點和獲取的根節(jié)點比較，如果不一致,通過這種二叉樹的結(jié)構(gòu)可以在log(N)的復(fù)雜度快速定位到出錯的數(shù)據(jù)塊。

副本同步

一個集群里的所有機器，需要保持數(shù)據(jù)的同步，如果數(shù)據(jù)不一致，需要快速的定位到不一致的節(jié)點。

可以在每臺機器上針對每個區(qū)間里的數(shù)據(jù)構(gòu)造一棵Merkle Tree，這樣，在兩臺機器間進行數(shù)據(jù)比對時，從Merkle Tree的根節(jié)點開始進行比對，如果根節(jié)點一樣，則表示兩個副本目前是一致的，不再需要任何處理；如果不一樣，則遍歷Merkle Tree，定位到不一致的節(jié)點也非?？焖?/p>

merkle tree應(yīng)用在區(qū)塊鏈上

下面是本文的重點。

比特幣系統(tǒng)的區(qū)塊鏈中，每個區(qū)塊都有一個merkle tree。

image

可以看到merkle root哈希值存在每一個區(qū)塊的頭部，通過這個root值連接著區(qū)塊體，而區(qū)塊體內(nèi)就是包含著大量的交易。每個交易就相當于前面提到的數(shù)據(jù)塊，交易本身有都有自己的哈希值來唯一標識自己。

什么是SPV

為了更好的解釋，這里先插播一個概念，SPV。也就是中本聰描述到的“簡化支付驗證” 正是有了SPV，才讓區(qū)塊鏈和比特幣更加廣泛的被傳播。

我們大部分人在電腦安裝的比特幣錢包都是輕量級(非全節(jié)點)的，也就是本地并沒有所有的區(qū)塊數(shù)據(jù)(上百G)。理論上來說，要驗證一筆交易，錢包需要遍歷所有的區(qū)塊找到和該筆交易相關(guān)的所有交易進行逐個驗證才是可靠的。

但是輕量級的錢包沒有完整的數(shù)據(jù)，如何驗證一筆支付的合法性呢?

merkle tree就起到了關(guān)鍵的作用。

當然SPV有它的局限性(這個有空再寫文章細講)。

這里是分割點

比特幣系統(tǒng)是如何驗證一筆交易的合法性呢？

首先區(qū)塊鏈中每個區(qū)塊中的merkle tree的根哈希都是公開可信的。假設(shè)現(xiàn)在alice轉(zhuǎn)賬給bob一個比特幣，比特幣錢包需要確認這筆交易是否被包含在了區(qū)塊鏈中。

image

入上圖所示，
假設(shè)我們要判斷HK代表的交易是否存在，只需要生成一個僅有 4 個哈希值長度的 Merkle 路徑，來證明區(qū)塊中存該筆交易。該路徑有 4 個哈希值（在圖中由藍色標注）HL、HIJ、HMNOP 和 HABCDEFGH。

由這 4 個
哈希值產(chǎn)生的認證路徑， 再通過計算另外四對哈希值 HKL、 HIJKL、 HIJKLMNOP
和 Merkle 樹根（在圖中由虛線標注），任何節(jié)點都能證明 HK（在圖中由綠色
標注）包含在 Merkle 根中。

具體認證路徑的生成，主要是通過遍歷。有專門的算法，有興趣的可以自行搜索相關(guān)的論文

參考

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

[2] <<精通比特幣>>