01

默克爾樹的概念

默克爾樹(Merkle Tree)是一種特殊的二叉樹，它的每個節點都存儲了一個數據塊的哈希值。哈希值是一種可以將任意長度的數據轉換為固定長度的字符串的算法，它具有唯一性和不可逆性的特點，即不同的數據塊會產生不同的哈希值，而相同的數據塊會產生相同的哈希值，且無法從哈希值還原出原始數據。默克爾樹的葉子節點存儲了數據塊本身的哈希值，而非葉子節點存儲了其子節點哈希值的組合的哈希值。這樣，默克爾樹的根節點就包含了所有數據塊的哈希信息，可以用來代表整棵樹的唯一標識。

02

默克爾樹的結構

默克爾樹是一種完全二叉樹，即每個非葉子節點都有兩個子節點，如果數據塊的數量不是2的整數次冪，那么就需要復制最后一個數據塊來補齊。例如，如果有5個數據塊，那么就需要復制第5個數據塊來構成6個數據塊，然后再復制第6個數據塊來構成8個數據塊。這樣，就可以形成一個4層的完全二叉樹.

如下圖所示： 在這個例子中，A、B、C、D、E、F、G、H是8個數據塊，它們經過哈希函數H得到8個哈希值H(A)、H(B)、H(C)、H(D)、H(E)、H(F)、H(G)、H(H)，這些哈希值作為葉子節點。然后，葉子節點兩兩組合，得到4個中間節點H(H(A)+H(B))、H(H(C)+H(D))、H(H(E)+H(F))、H(H(G)+H(H))，其中+表示字符串連接。再然后，中間節點兩兩組合，得到2個中間節點H(H(H(A)+H(B))+H(H(C)+H(D)))和H(H(H(E)+H(F))+H(H(G)+H(H)))。最后，這兩個中間節點組合得到根節點H(H(H(H(A)+H(B))+H(H(C)+H(D)))+H(H(H(E)+H(F))+H(H(G)+H(H))))。這個根節點就是默克爾根(Merkle Root)，它包含了所有數據塊的哈希信息。

03

默克爾樹的作用

默克爾樹有以下幾個作用： 1.數據完整性驗證：通過比較兩棵默克爾樹的根節點是否相同，可以快速判斷兩份數據是否完全一致。如果根節點不同，則說明至少有一個數據塊發生了變化；如果根節點相同，則說明所有數據塊都沒有變化。這樣可以節省大量的比較時間和空間。 2.數據安全性保護：由于哈希函數的不可逆性，即使知道了默克爾根和部分數據塊，也無法還原出其他數據塊的內容。這樣可以保護數據的隱私和安全。 3.數據有效性證明：通過提供某個數據塊及其對應的默克爾路徑(Merkle Path)，即從該數據塊到根節點經過的所有節點的哈希值，可以證明該數據塊確實存在于某棵默克爾樹中。這樣可以避免傳輸整棵默克爾樹，只需要傳輸默克爾根和默克爾路徑即可。

04

默克爾樹的應用

默克爾樹廣泛應用于文件系統和P2P網絡中，例如：

1.Git：Git是一種分布式版本控制系統，它使用默克爾樹來存儲和管理文件的歷史版本。每個文件都有一個哈希值，每個目錄也有一個哈希值，這些哈希值構成了一棵默克爾樹。每次提交(commit)都會生成一個新的默克爾根，作為該提交的唯一標識。這樣，可以快速比較不同提交之間的差異，以及驗證文件的完整性和有效性。

2.BitTorrent：BitTorrent是一種P2P文件共享協議，它使用默克爾樹來分割和校驗大文件。每個文件被切分成多個數據塊，每個數據塊有一個哈希值，這些哈希值構成了一棵默克爾樹。每個文件的元數據(metadata)中包含了該文件的默克爾根和數據塊的大小。這樣，可以在下載過程中驗證數據塊的完整性和有效性，以及恢復損壞的數據塊。

3.Bitcoin：Bitcoin是一種去中心化的數字貨幣系統，它使用默克爾樹來存儲和驗證交易記錄。每個交易都有一個哈希值，這些哈希值構成了一棵默克爾樹。每個區塊(block)中包含了該區塊的默克爾根和交易數量。這樣，可以在不傳輸整個區塊的情況下，證明某個交易是否存在于某個區塊中，以及驗證區塊的完整性和有效性。 默克爾樹是一種特殊的二叉樹，它的每個節點都存儲了一個數據塊的哈希值。

本文章源自奇跡物聯開源的物聯網應用知識庫Cellular IoT Wiki，更多技術干貨歡迎關注收藏Wiki：Cellular IoT Wiki 知識庫（https://rckrv97mzx.feishu.cn/wiki/wikcnBvAC9WOkEYG5CLqGwm6PHf）

歡迎同學們走進AmazIOT知識庫的世界！

這里是為物聯網人構建的技術應用百科，以便幫助你更快更簡單的開發物聯網產品。

Cellular IoT Wiki初心：

在我們長期投身于蜂窩物聯網 ODM/OEM 解決方案的實踐過程中，一直被物聯網技術碎片化與產業資源碎片化的問題所困擾。從產品定義、芯片選型，到軟硬件研發和測試，物聯網技術的碎片化以及產業資源的碎片化，始終對團隊的產品開發交付質量和效率形成制約。為了減少因物聯網碎片化而帶來的重復開發工作，我們著手對物聯網開發中高頻應用的技術知識進行沉淀管理，并基于 Bloom OS 搭建了不同平臺的 RTOS 應用生態。后來我們發現，很多物聯網產品開發團隊都面臨著相似的困擾，于是，我們決定向全體物聯網行業開發者開放奇跡物聯內部沉淀的應用技術知識庫 Wiki，期望能為更多物聯網產品開發者減輕一些重復造輪子的負擔。

Cellular IoT Wiki沉淀的技術內容方向如下：

奇跡物聯的業務服務范圍：基于自研的NB-IoT、Cat1、Cat4等物聯網模組，為客戶物聯網ODM/OEM解決方案服務。我們的研發技術中心在石家莊，PCBA生產基地分布在深圳、石家莊、北京三個工廠，滿足不同區域&不同量產規模&不同產品開發階段的生產制造任務。跟傳統PCBA工廠最大的區別是我們只服務物聯網行業客戶。

連接我們，和10000+物聯網開發者一起 降低技術和成本門檻

讓蜂窩物聯網應用更簡單~~

哈哈你終于滑到最重要的模塊了，

千萬不！要！劃！走！忍住沖動！~

歡迎加入飛書“開源技術交流群”，隨時找到我們哦~

點擊鏈接如何加入奇跡物聯技術話題群（https://rckrv97mzx.feishu.cn/docx/Xskpd1cFQo7hu9x5EuicbsjTnTf）可以獲取加入技術話題群攻略

Hey 物聯網從業者，

你是否有了解過奇跡物聯的官方公眾號“eSIM物聯工場”呢？

這里是奇跡物聯的物聯網應用技術開源wiki主陣地，歡迎關注公眾號，不迷路～

及時獲得最新物聯網應用技術沉淀發布

審核編輯 黃宇