哈希算法（Hash）

哈希算法也叫散列算法，一般來(lái)說(shuō)滿(mǎn)足這樣的關(guān)系：Func(data)=key，輸入任意長(zhǎng)度的 data，經(jīng)過(guò)哈希算法處理后輸出一個(gè)定長(zhǎng)的數(shù)據(jù) key。同時(shí)這個(gè)過(guò)程是不可逆的，無(wú)法由 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) 而直接進(jìn)行訪(fǎng)問(wèn)的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪(fǎng)問(wèn)記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。給定表 M，存在函數(shù) Func(key)，對(duì)任意給定的關(guān)鍵字值 key，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址，則稱(chēng)表 M 為哈希表，函數(shù) Func(key) 為哈希函數(shù)。
哈希表是一種通過(guò)哈希函數(shù)將特定的鍵映射到特定值的一種數(shù)據(jù)結(jié)構(gòu)，他維護(hù)著 key 和 value 之間的一 一對(duì)應(yīng)關(guān)系。

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)定或者不可信的。為了校驗(yàn)數(shù)據(jù)的完整性，更好的辦法是把大的文件分割成小的數(shù)據(jù)塊（例如，把分割成 64KB 為單位的數(shù)據(jù)塊）。這樣的好處是，如果小塊數(shù)據(jù)在傳輸過(guò)程中損壞了，那么只要重新下載這一快數(shù)據(jù)就行了，不用重新下載整個(gè)文件。

怎么確定小的數(shù)據(jù)塊沒(méi)有損壞哪？只需要為每個(gè)數(shù)據(jù)塊做 Hash。BT下載的時(shí)候，在下載到真正數(shù)據(jù)之前，我們會(huì)先下載一個(gè) Hash 列表。那么問(wèn)題又來(lái)了，怎么確定這個(gè)Hash列表本事是正確的哪？答案是把每個(gè)小塊數(shù)據(jù)的Hash值拼到一起，然后對(duì)這個(gè)長(zhǎng)字符串在作一次Hash運(yùn)算，這樣就得到Hash列表的根Hash(Top Hash or Root Hash)。下載數(shù)據(jù)的時(shí)候，首先從可信的數(shù)據(jù)源得到正確的根Hash，就可以用它來(lái)校驗(yàn)Hash列表了，然后通過(guò)校驗(yàn)后的Hash列表校驗(yàn)數(shù)據(jù)塊。

默克爾樹(shù)（Merkle Tree）

• 二叉樹(shù)：平衡二叉樹(shù)，非平衡二叉樹(shù)

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

• 默克爾樹(shù)

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

在最底層，和哈希列表一樣，我們把數(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[3]。

在 P2P 網(wǎng)絡(luò)下載網(wǎng)絡(luò)之前，先從可信的源獲得文件的 Merkle Tree 樹(shù)根。一旦獲得了樹(shù)根，就可以從其他從不可信的源獲取 Merkle tree。通過(guò)可信的樹(shù)根來(lái)檢查接受到的Merkle Tree。如果 Merkle Tree 是損壞的或者虛假的，就從其他源獲得另一 個(gè)Merkle Tree，直到獲得一個(gè)與可信樹(shù)根匹配的 Merkle Tree。

Merkle Tree 和Hash List 的主要區(qū)別是，可以直接下載并立即驗(yàn)證 Merkle Tree 的一個(gè)分支。因?yàn)榭梢詫⑽募蟹殖尚〉臄?shù)據(jù)塊，這樣如果有一塊數(shù)據(jù)損壞，僅僅重新下載這個(gè)數(shù)據(jù)塊就行了。如果文件非常大，那么 Merkle tree 和 Hash list 都很到，但是 Merkle tree 可以一次下載一個(gè)分支，然后立即驗(yàn)證這個(gè)分支，如果分支驗(yàn)證通過(guò)，就可以下載數(shù)據(jù)了。而Hash list只有下載整個(gè)hash list才能驗(yàn)證。

典型應(yīng)用

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

  為了保持?jǐn)?shù)據(jù)一致，分布系統(tǒng)間數(shù)據(jù)需要同步，如果對(duì)機(jī)器上所有數(shù)據(jù)都進(jìn)行比對(duì)的話(huà)，數(shù)據(jù)傳輸量就會(huì)很大，從而造成“網(wǎng)絡(luò)擁擠”。為了解決這個(gè)問(wèn)題，可以在每臺(tái)機(jī)器上構(gòu)造一棵 Merkle Tree，這樣，在兩臺(tái)機(jī)器間進(jìn)行數(shù)據(jù)比對(duì)時(shí)，從 Merkle Tree 的根節(jié)點(diǎn)開(kāi)始進(jìn)行比對(duì)，如果根節(jié)點(diǎn)一樣，則表示兩個(gè)副本目前是一致的，不再需要任何處理；如果不一樣，則沿著hash值不同的節(jié)點(diǎn)路徑查詢(xún)，很快就能定位到數(shù)據(jù)不一致的葉節(jié)點(diǎn)，只用把不一致的數(shù)據(jù)同步即可，這樣大大節(jié)省了比對(duì)時(shí)間以及數(shù)據(jù)的傳輸量。

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

more..

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

默克爾證明（Merkle Proof）

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