今天為啥又聊 Merkle Tree 呢洋幻？ 我們地球上大部分人應(yīng)該連它的名字都沒(méi)有聽(tīng)過(guò)元莫，而且說(shuō)實(shí)話它也是個(gè)比較傳統(tǒng)的概念了扳剿。Merkle Tree 是由計(jì)算機(jī)科學(xué)家 Ralph Merkle 在很多年前提出的宪郊，并以他本人的名字來(lái)命名。不過(guò)享完，Merkle Tree 確實(shí)涉及到了很多有意思的實(shí)際應(yīng)用灼芭。最近幾年才有的一個(gè)例子是有额，比特幣錢包服務(wù)用 Merkle Tree 的機(jī)制來(lái)作”百分百準(zhǔn)備金證明“ （ http://blog.bifubao.com/2014/03/16/proof-of-reserves/ ）般又。不過(guò)今天，我們還是從數(shù)據(jù)的“完整性校驗(yàn)”這個(gè)角度來(lái)聊 Merkle Tree巍佑。 Git 版本控制系統(tǒng)茴迁，ZFS 文件系統(tǒng)以及我們自己下載電影常用的點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò) BT 下載，都是通過(guò) Merkle Tree 來(lái)進(jìn)行完整性校驗(yàn)的萤衰。順便說(shuō)一句堕义，所謂的完整性校驗(yàn)，就是檢查一下數(shù)據(jù)有沒(méi)有損壞脆栋。

先說(shuō)哈希( Hash )

其實(shí)要實(shí)現(xiàn)完整性校驗(yàn)倦卖，最簡(jiǎn)單的方法就是對(duì)要校驗(yàn)的整個(gè)的數(shù)據(jù)文件做個(gè)哈希運(yùn)算，把得到的哈希值公布在網(wǎng)上椿争，這樣我們把數(shù)據(jù)下載到手之后怕膛，再次運(yùn)算一下哈希值，如果運(yùn)算結(jié)果相等秦踪，就表示我們下載過(guò)程中文件沒(méi)有任何的損壞褐捻。因?yàn)楣５淖畲筇攸c(diǎn)是掸茅，如果你的輸入數(shù)據(jù)，稍微變了一點(diǎn)點(diǎn)柠逞，那么經(jīng)過(guò)哈希運(yùn)算昧狮，你得到的哈希值將會(huì)變得面目全非。這樣做的一個(gè)目的是可以防止有人根據(jù)哈希值反推出原始輸入數(shù)據(jù)的一些特征板壮。

如果我們從一個(gè)穩(wěn)定的服務(wù)器上進(jìn)行下載逗鸣，那么采用單個(gè)哈希來(lái)進(jìn)行校驗(yàn)的形式是可以接受的。

再說(shuō)哈希列表（ Hash List ）

但是在點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)中作數(shù)據(jù)傳輸?shù)臅r(shí)候绰精，我們會(huì)從同時(shí)從多個(gè)機(jī)器上下載數(shù)據(jù)慕购，而且其中很多機(jī)器可以認(rèn)為是不穩(wěn)定或者是不可信的，這時(shí)需要有更加巧妙的做法茬底。實(shí)際中沪悲，點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)在傳輸數(shù)據(jù)的時(shí)候，其實(shí)都是把比較大的一個(gè)文件阱表，切成小的數(shù)據(jù)塊殿如。這樣的好處是，如果有一個(gè)小塊數(shù)據(jù)在傳輸過(guò)程中損壞了最爬，那我只要重新下載這一個(gè)數(shù)據(jù)塊就行了涉馁，不用重新下載整個(gè)文件。當(dāng)然這就要求每個(gè)數(shù)據(jù)塊都擁有自己的哈希值爱致。BT 下載的時(shí)候烤送，在下載真正的數(shù)據(jù)之前，我們會(huì)先下載一個(gè)哈希列表的糠悯。這時(shí)有一個(gè)問(wèn)題就出現(xiàn)了帮坚，那么多的哈希，我們?cè)趺幢ＷC它們本身都是正確地呢互艾？

答案是我們需要一個(gè)根哈希试和。把每個(gè)小塊的哈希值拼到一起，然后對(duì)整個(gè)這個(gè)長(zhǎng)長(zhǎng)的字符串再做一次哈希運(yùn)算纫普，最終的結(jié)果就是哈希列表的根哈希阅悍。于是，如果我們能夠保證從一個(gè)絕對(duì)可信的網(wǎng)站昨稼，或者從我們的朋友手里拿到一個(gè)正確的根哈希节视，就可以用它來(lái)校驗(yàn)哈希列表中的每一
個(gè)哈希都是正確的，進(jìn)而可以保證下載的每一個(gè)數(shù)據(jù)塊的正確性了假栓。

這種方式挺好寻行，但是實(shí)際的應(yīng)用中，其實(shí)還是有著它的不足之處的但指，這就是為什么 Merkle 教授要發(fā)明 Merkle Tree 了寡痰。

最后是 Merkle Tree

先看它的結(jié)構(gòu)抗楔。在最底層，和哈希列表一樣拦坠，我們把數(shù)據(jù)分成小的數(shù)據(jù)塊连躏，有相應(yīng)地哈希和它對(duì)應(yīng)。但是往上走贞滨，并不是直接去運(yùn)算根哈希入热，而是把相鄰的兩個(gè)哈希合并成一個(gè)字符串，然后運(yùn)算這個(gè)字符串的哈希晓铆，這樣每?jī)蓚€(gè)哈希就結(jié)婚生子勺良，得到了一個(gè)”子哈希“骄噪。如果最底層的哈仙欣В總數(shù)是單數(shù)，那到最后必然出現(xiàn)一個(gè)單身哈希链蕊，這種情況就直接對(duì)它進(jìn)行哈希運(yùn)算事甜，所以也能得到它的子哈希。于是往上推滔韵，依然是一樣的方式逻谦，可以得到數(shù)目更少的新一級(jí)哈希，最終必然形成一棵倒掛的樹(shù)陪蜻，到了樹(shù)根的這個(gè)位置邦马，這一代就剩下一個(gè)根哈希了，我們把它叫做 Merkle root.

再說(shuō)它的優(yōu)點(diǎn)宴卖。相對(duì)于 Hash List滋将，Merkle Tree 的明顯的一個(gè)好處是可以單獨(dú)拿出一個(gè)分支來(lái)（作為一個(gè)小樹(shù)）對(duì)部分?jǐn)?shù)據(jù)進(jìn)行校驗(yàn)，這個(gè)很多使用場(chǎng)合就帶來(lái)了哈希列表所不能比擬的方便和高效嘱腥。

好耕渴，這一期就說(shuō)這么多，大家現(xiàn)在概念上有個(gè)認(rèn)識(shí)齿兔，后面我們會(huì)有專門的文章講 Merkle Tree 實(shí)用的例子。

參考資料

• https://www.youtube.com/watch?v=Js535LqapFE#t=238
  給出了 Merkle Tree 相對(duì)于 Hash List 的優(yōu)勢(shì)础米。
• http://en.wikipedia.org/wiki/Merkle_tree