哈希算法（Hash）

哈希算法也叫散列算法雹嗦，一般來說滿足這樣的關(guān)系：Func(data)=key，輸入任意長度的 data幸斥，經(jīng)過哈希算法處理后輸出一個定長的數(shù)據(jù) key勋篓。同時這個過程是不可逆的，無法由 key 逆推出 data此熬。

• MD5
• SHA：SHA-1庭呜，SHA-224, SHA-256，SHA-384犀忱，SHA-512

注意募谎，哈希表（HashTable）是利用了哈希函數(shù)的一種數(shù)據(jù)結(jié)構(gòu)

散列表（Hash table，也叫哈希表）阴汇，是根據(jù)關(guān)鍵碼值 (key/value) 而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)近哟。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄鲫寄，以加快查找的速度吉执。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表地来。給定表 M戳玫，存在函數(shù) Func(key)，對任意給定的關(guān)鍵字值 key未斑，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址咕宿，則稱表 M 為哈希表，函數(shù) Func(key) 為哈希函數(shù)蜡秽。
哈希表是一種通過哈希函數(shù)將特定的鍵映射到特定值的一種數(shù)據(jù)結(jié)構(gòu)府阀，他維護著 key 和 value 之間的一 一對應(yīng)關(guān)系。

Hash List

在點對點網(wǎng)絡(luò)中作數(shù)據(jù)傳輸?shù)臅r候芽突，會同時從多個機器上下載數(shù)據(jù)试浙，而且很多機器可以認(rèn)為是不穩(wěn)定或者不可信的。為了校驗數(shù)據(jù)的完整性寞蚌，更好的辦法是把大的文件分割成小的數(shù)據(jù)塊（例如田巴，把分割成 64KB 為單位的數(shù)據(jù)塊）钠糊。這樣的好處是，如果小塊數(shù)據(jù)在傳輸過程中損壞了壹哺，那么只要重新下載這一快數(shù)據(jù)就行了抄伍，不用重新下載整個文件。

怎么確定小的數(shù)據(jù)塊沒有損壞哪管宵？只需要為每個數(shù)據(jù)塊做 Hash截珍。BT下載的時候，在下載到真正數(shù)據(jù)之前箩朴，我們會先下載一個 Hash 列表岗喉。那么問題又來了，怎么確定這個Hash列表本事是正確的哪隧饼？答案是把每個小塊數(shù)據(jù)的Hash值拼到一起沈堡，然后對這個長字符串在作一次Hash運算静陈，這樣就得到Hash列表的根Hash(Top Hash or Root Hash)燕雁。下載數(shù)據(jù)的時候，首先從可信的數(shù)據(jù)源得到正確的根Hash鲸拥，就可以用它來校驗Hash列表了拐格，然后通過校驗后的Hash列表校驗數(shù)據(jù)塊。

默克爾樹（Merkle Tree）

• 二叉樹：平衡二叉樹刑赶，非平衡二叉樹

  在計算機科學(xué)中捏浊，二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)，每個節(jié)點代表一條結(jié)構(gòu)化數(shù)據(jù)撞叨。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）金踪。
  二叉樹常被用于實現(xiàn)數(shù)據(jù)快速查詢。二叉樹如下圖所示：
  

• 默克爾樹

默克爾樹（Merkle tree）是一種哈希二叉樹牵敷，1979年由 Ralph Merkle 發(fā)明胡岔。
Merkle Tree可以看做Hash List的泛化（Hash List可以看作一種特殊的Merkle Tree，即樹高為2的多叉Merkle Tree）枷餐。

在最底層靶瘸，和哈希列表一樣，我們把數(shù)據(jù)分成小的數(shù)據(jù)塊毛肋，有相應(yīng)地哈希和它對應(yīng)怨咪。但是往上走，并不是直接去運算根哈希润匙，而是把相鄰的兩個哈希合并成一個字符串诗眨，然后運算這個字符串的哈希，這樣每兩個哈希就結(jié)婚生子孕讳，得到了一個”子哈狭苫埃“肄鸽。如果最底層的哈希總數(shù)是單數(shù)油啤，那到最后必然出現(xiàn)一個單身哈希典徘，這種情況就直接對它進行哈希運算，所以也能得到它的子哈希益咬。于是往上推逮诲，依然是一樣的方式，可以得到數(shù)目更少的新一級哈希幽告，最終必然形成一棵倒掛的樹梅鹦，到了樹根的這個位置，這一代就剩下一個根哈希了冗锁，我們把它叫做 Merkle Root[3]齐唆。

在 P2P 網(wǎng)絡(luò)下載網(wǎng)絡(luò)之前，先從可信的源獲得文件的 Merkle Tree 樹根冻河。一旦獲得了樹根箍邮，就可以從其他從不可信的源獲取 Merkle tree。通過可信的樹根來檢查接受到的Merkle Tree叨叙。如果 Merkle Tree 是損壞的或者虛假的锭弊，就從其他源獲得另一 個Merkle Tree，直到獲得一個與可信樹根匹配的 Merkle Tree擂错。

Merkle Tree 和Hash List 的主要區(qū)別是味滞，可以直接下載并立即驗證 Merkle Tree 的一個分支。因為可以將文件切分成小的數(shù)據(jù)塊钮呀，這樣如果有一塊數(shù)據(jù)損壞剑鞍，僅僅重新下載這個數(shù)據(jù)塊就行了。如果文件非常大爽醋，那么 Merkle tree 和 Hash list 都很到蚁署，但是 Merkle tree 可以一次下載一個分支，然后立即驗證這個分支子房，如果分支驗證通過形用，就可以下載數(shù)據(jù)了。而Hash list只有下載整個hash list才能驗證证杭。

典型應(yīng)用

• 快速比較大量數(shù)據(jù)：當(dāng)兩個默克爾樹根相同時田度，則意味著所代表的數(shù)據(jù)必然相同（哈希算法決定的）。
• 快速定位修改：例如上例中解愤，如果 D1 中數(shù)據(jù)被修改镇饺，會影響到Hash0-0，Hash0 和 Root送讲。因此奸笤，沿著 Root --> 0 --> 0-0惋啃，可以快速定位到發(fā)生改變的 D1；
• 零知識證明：例如如何證明某個數(shù)據(jù)（D0……D3）中包括給定內(nèi)容 D0监右，很簡單边灭，構(gòu)造一個默克爾樹，公布 N0健盒，N1绒瘦，N4，Root扣癣，D0 擁有者可以很容易檢測 D0 存在惰帽，但不知道其它內(nèi)容。
• 數(shù)據(jù)完整性校驗：git 版本控制系統(tǒng)父虑，ZFS/IPFS 分布式文件系統(tǒng)以及 BT 下載该酗，都是通過 Merkle Tree 來進行完整性校驗的。
• 在分布式存儲系統(tǒng)中的應(yīng)用:

  為了保持?jǐn)?shù)據(jù)一致士嚎，分布系統(tǒng)間數(shù)據(jù)需要同步呜魄，如果對機器上所有數(shù)據(jù)都進行比對的話，數(shù)據(jù)傳輸量就會很大航邢，從而造成“網(wǎng)絡(luò)擁擠”耕赘。為了解決這個問題骄蝇，可以在每臺機器上構(gòu)造一棵 Merkle Tree膳殷，這樣，在兩臺機器間進行數(shù)據(jù)比對時九火，從 Merkle Tree 的根節(jié)點開始進行比對赚窃，如果根節(jié)點一樣，則表示兩個副本目前是一致的岔激，不再需要任何處理勒极；如果不一樣，則沿著hash值不同的節(jié)點路徑查詢虑鼎，很快就能定位到數(shù)據(jù)不一致的葉節(jié)點辱匿，只用把不一致的數(shù)據(jù)同步即可，這樣大大節(jié)省了比對時間以及數(shù)據(jù)的傳輸量炫彩。

相對于 Hash List匾七，MT的明顯的一個好處是可以單獨拿出一個分支來（作為一個小樹）對部分?jǐn)?shù)據(jù)進行校驗，這個很多使用場合就帶來了哈希列表所不能比擬的方便和高效江兢。正是源于這些優(yōu)點昨忆，MT常用于分布式系統(tǒng)或分布式存儲中。

more..

• Merkle Tree 在數(shù)字加密貨幣中首先應(yīng)用于比特幣（BTC）杉允，以太坊（Etherum）采用了改進的 Merkle Patricia Tree (MPT) 邑贴。

默克爾證明（Merkle Proof）

• 比特幣錢包用 Merkle Tree 的機制來作 百分百準(zhǔn)備金證明
• 比特幣SPV中 如何利用默克爾樹證明某個交易是否存在
• EOS.IO 通過默克爾證明 實現(xiàn)區(qū)塊鏈間通信