有意思的資料結構默克樹 Merkle tree應用介紹

2022-09-30 14:01:40

一種有意思的資料結構-默克樹（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

以上就是有意思的資料結構默克樹 Merkle tree應用介紹的詳細內容，更多關於資料結構默克樹 Merkle tree的資料請關注it145.com其它相關文章！