有意思的數(shù)據(jù)結(jié)構(gòu)默克樹 Merkle tree應(yīng)用介紹

更新時間：2022年09月28日 14:22:05 作者：spider集控團隊

這篇文章主要為大家介紹了有意思的數(shù)據(jù)結(jié)構(gòu)默克樹 Merkle tree應(yīng)用介紹，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

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

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

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

長什么樣子？

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

Hash鏈表

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

防篡改

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

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

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

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

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

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

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

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

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

1.我們首先要向信任節(jié)點獲取藍(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，等于說明存在。

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

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

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

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

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

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

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

是否可以嘗試如下步驟：

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

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

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

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

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