一種有意思的數(shù)據(jù)結(jié)構(gòu)-默克樹（Merkle tree）

默克樹（Merkle tree）又叫hash樹。程序員可以說(shuō)自己不知道默克樹，但是不能保證自己一定沒(méi)有用過(guò)，因?yàn)間it存儲(chǔ)我們每一個(gè)版本代碼和提交記錄關(guān)系的數(shù)據(jù)結(jié)構(gòu)就是默克樹。

其在區(qū)塊鏈技術(shù)中起著十分重要的作用，本文會(huì)介紹這種數(shù)據(jù)結(jié)構(gòu)，并舉例兩個(gè)常見(jiàn)的應(yīng)用場(chǎng)景（可能不夠嚴(yán)謹(jǐn)）。

長(zhǎng)什么樣子？

下圖是一個(gè)簡(jiǎn)單的默克樹，可以看到除最底層的數(shù)據(jù)外，其他節(jié)點(diǎn)都是左右兩個(gè)子節(jié)點(diǎn)的hash值組成。（注：紅線代表左右順序）

Hash鏈表

鏈表的定義就是當(dāng)前節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)，傳統(tǒng)鏈表是使用地址作為指向，但是區(qū)塊鏈中的鏈表和默克樹一樣，使用上一個(gè)節(jié)點(diǎn)的hash值作為指向，如圖：

防篡改

這兩種數(shù)據(jù)結(jié)構(gòu)天生就具備防篡改的特性，我們看他們?cè)趨^(qū)塊鏈中的形態(tài)：

假設(shè)我們更改了左邊虛框內(nèi)那一批已經(jīng)存在的交易數(shù)據(jù)，例如data1，那區(qū)塊1的默克樹root值就一定會(huì)改變，區(qū)塊1的hash值也一定會(huì)變，這種變化會(huì)產(chǎn)生新的鏈，當(dāng)發(fā)現(xiàn)這條新鏈在區(qū)塊1后的所有區(qū)塊值與各個(gè)節(jié)點(diǎn)原本記錄的值不一致，就會(huì)認(rèn)為有人修改了鏈上的舊數(shù)據(jù)。

而且我們使用的是hash值作為指向，只要大家手上的最后一個(gè)值沒(méi)問(wèn)題，在回溯時(shí)必然無(wú)法回溯到被篡改的數(shù)據(jù)，甚至回溯對(duì)比后還可以知道哪里發(fā)生了篡改。

既然無(wú)法指向我們篡改的數(shù)據(jù)，那我們把后面的所有區(qū)塊以及其數(shù)據(jù)也篡改了行不行？可以的，但是區(qū)塊有無(wú)數(shù)個(gè)，而且并不是簡(jiǎn)單的遍歷修改本地?cái)?shù)據(jù)就ok了，還需要所有節(jié)點(diǎn)的共識(shí)，你能黑光所有的節(jié)點(diǎn)，讓他們都直接放棄手中的數(shù)據(jù)，認(rèn)可你這新的鏈嗎？

所以在對(duì)賬時(shí)，就很容易知道賬目是否正確，由于是直接比較hash值，使用默克樹去判斷內(nèi)容是否被篡改是很快的！

我們看看默克樹在分布式記賬的應(yīng)用中是如何大展身手的！！

判斷某個(gè)交易是否被記錄（是否存在）

你怎么保證你手中的數(shù)據(jù)和鏈上一致？怎么證明你的數(shù)據(jù)在鏈上呢？

例子：你在銀行存了50萬(wàn)，銀行怎么證明它給你存了50萬(wàn)呢？

1.我們首先要向信任節(jié)點(diǎn)獲取藍(lán)色框和黃色框的值。

2.這里假設(shè)我們判斷data1數(shù)據(jù)，算出我們要判斷的數(shù)據(jù)的記為A，A與B進(jìn)行hash,得到C

3.將C與D進(jìn)行hash，得到E

4.判斷E是否等于 F，等于說(shuō)明存在。

常見(jiàn)應(yīng)用 - 1 git

我們切換commit時(shí)，git是怎么實(shí)現(xiàn)不同commit文件數(shù)量和文件內(nèi)容的切換的？

git會(huì)記錄所有版本的文件，例如文件a在第一個(gè)commit中內(nèi)容是1，第二次commit中內(nèi)容是2，此時(shí)git本地倉(cāng)庫(kù)中會(huì)分別有：內(nèi)容為1的文件a，內(nèi)容為2的文件a。

git中每一個(gè)commit就相當(dāng)于一個(gè)區(qū)塊，這個(gè)區(qū)塊有對(duì)應(yīng)的默克樹，而默克樹中的hash值又指向了對(duì)應(yīng)的文件，所以切換一個(gè)commit其實(shí)就相當(dāng)于將當(dāng)前區(qū)塊切換，如下圖：

注：將工作區(qū)的文件改成本地倉(cāng)庫(kù)的某個(gè)版本的文件是index區(qū)負(fù)責(zé)的，這里就不細(xì)講了。

常見(jiàn)應(yīng)用 - 2 分布式數(shù)據(jù)存儲(chǔ)的數(shù)據(jù)校驗(yàn)

我們將成千上萬(wàn)個(gè)文件存在互聯(lián)網(wǎng)上的任意服務(wù)器，任何一個(gè)能上網(wǎng)的終端，都可以作為我們的存儲(chǔ)器，注：假設(shè)我們?yōu)榱吮ＷC性能，不通過(guò)中介服務(wù)器，直接p2p連接，并且不校驗(yàn)這些存儲(chǔ)器的身份。那如何保證我們從這些不受信任的存儲(chǔ)器中下載的數(shù)據(jù)，是我們存入時(shí)的樣子（沒(méi)有被篡改）？

是否可以嘗試如下步驟：

0.這些任意的服務(wù)器都要擁有其存儲(chǔ)文件的默克樹。

1.終端下載這個(gè)服務(wù)器中存儲(chǔ)的默克樹，向值得信任的服務(wù)器取得這個(gè)默克樹對(duì)應(yīng)區(qū)塊的值，計(jì)算并判斷默克樹頂部的hash值是否等于區(qū)塊記錄的值，等于說(shuō)明這個(gè)服務(wù)器記錄的默克樹沒(méi)有問(wèn)題。

下面兩步任選一個(gè)都能確認(rèn)文件沒(méi)被篡改。

2.使用時(shí)判斷這個(gè)文件內(nèi)容是否有被這個(gè)默克樹記錄。

3.判斷所有文件都被這個(gè)默克樹記錄。

小結(jié)

可以看到默克樹的根本在于hash的計(jì)算，是否真的能保證防篡改呢？，如果想進(jìn)一步了解，可以看看密碼學(xué)中有關(guān)于Collision resistance（抗碰撞性）和 Hiding（隱藏性）。

也可以看：密碼學(xué)基礎(chǔ).md