一種有意思的數據結構-默克樹（Merkle tree）

默克樹（Merkle tree）又叫hash樹。程序員可以說自己不知道默克樹，但是不能保證自己一定沒有用過，因為git存儲我們每一個版本代碼和提交記錄關系的數據結構就是默克樹。

其在區塊鏈技術中起著十分重要的作用，本文會介紹這種數據結構，并舉例兩個常見的應用場景（可能不夠嚴謹）。

長什么樣子？

下圖是一個簡單的默克樹，可以看到除最底層的數據外，其他節點都是左右兩個子節點的hash值組成。（注：紅線代表左右順序）

Hash鏈表

鏈表的定義就是當前節點指向下一個節點，傳統鏈表是使用地址作為指向，但是區塊鏈中的鏈表和默克樹一樣，使用上一個節點的hash值作為指向，如圖：

防篡改

這兩種數據結構天生就具備防篡改的特性，我們看他們在區塊鏈中的形態：

假設我們更改了左邊虛框內那一批已經存在的交易數據，例如data1，那區塊1的默克樹root值就一定會改變，區塊1的hash值也一定會變，這種變化會產生新的鏈，當發現這條新鏈在區塊1后的所有區塊值與各個節點原本記錄的值不一致，就會認為有人修改了鏈上的舊數據。

而且我們使用的是hash值作為指向，只要大家手上的最后一個值沒問題，在回溯時必然無法回溯到被篡改的數據，甚至回溯對比后還可以知道哪里發生了篡改。

既然無法指向我們篡改的數據，那我們把后面的所有區塊以及其數據也篡改了行不行？可以的，但是區塊有無數個，而且并不是簡單的遍歷修改本地數據就ok了，還需要所有節點的共識，你能黑光所有的節點，讓他們都直接放棄手中的數據，認可你這新的鏈嗎？

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

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

判斷某個交易是否被記錄（是否存在）

你怎么保證你手中的數據和鏈上一致？怎么證明你的數據在鏈上呢？

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

1.我們首先要向信任節點獲取藍色框和黃色框的值。

2.這里假設我們判斷data1數據，算出我們要判斷的數據的記為A，A與B進行hash,得到C

3.將C與D進行hash，得到E

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

常見應用 - 1 git

我們切換commit時，git是怎么實現不同commit文件數量和文件內容的切換的？

git會記錄所有版本的文件，例如文件a在第一個commit中內容是1，第二次commit中內容是2，此時git本地倉庫中會分別有：內容為1的文件a，內容為2的文件a。

git中每一個commit就相當于一個區塊，這個區塊有對應的默克樹，而默克樹中的hash值又指向了對應的文件，所以切換一個commit其實就相當于將當前區塊切換，如下圖：

注：將工作區的文件改成本地倉庫的某個版本的文件是index區負責的，這里就不細講了。

常見應用 - 2 分布式數據存儲的數據校驗

我們將成千上萬個文件存在互聯網上的任意服務器，任何一個能上網的終端，都可以作為我們的存儲器，注：假設我們為了保證性能，不通過中介服務器，直接p2p連接，并且不校驗這些存儲器的身份。那如何保證我們從這些不受信任的存儲器中下載的數據，是我們存入時的樣子（沒有被篡改）？

是否可以嘗試如下步驟：

0.這些任意的服務器都要擁有其存儲文件的默克樹。

1.終端下載這個服務器中存儲的默克樹，向值得信任的服務器取得這個默克樹對應區塊的值，計算并判斷默克樹頂部的hash值是否等于區塊記錄的值，等于說明這個服務器記錄的默克樹沒有問題。

下面兩步任選一個都能確認文件沒被篡改。

2.使用時判斷這個文件內容是否有被這個默克樹記錄。

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

小結

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

也可以看：密碼學基礎.md