01

默克爾樹的概念

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

02

默克爾樹的結構

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

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

03

默克爾樹的作用

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

04

默克爾樹的應用

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

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

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

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

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

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

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

Cellular IoT Wiki初心：

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

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

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

連接我們，和10000+物聯(lián)網開發(fā)者一起 降低技術和成本門檻

讓蜂窩物聯(lián)網應用更簡單~~

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

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

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

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

Hey 物聯(lián)網從業(yè)者，

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

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

及時獲得最新物聯(lián)網應用技術沉淀發(fā)布

審核編輯 黃宇