什么是默克爾樹(Merkle Tree)？如何計(jì)算默克爾根?

01

默克爾樹的概念

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

02

默克爾樹的結(jié)構(gòu)

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

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

03

默克爾樹的作用

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

04

默克爾樹的應(yīng)用

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

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

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

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

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

歡迎同學(xué)們走進(jìn)AmazIOT知識(shí)庫的世界！

這里是為物聯(lián)網(wǎng)人構(gòu)建的技術(shù)應(yīng)用百科，以便幫助你更快更簡單的開發(fā)物聯(lián)網(wǎng)產(chǎn)品。

Cellular IoT Wiki初心：

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

Cellular IoT Wiki沉淀的技術(shù)內(nèi)容方向如下：

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

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

讓蜂窩物聯(lián)網(wǎng)應(yīng)用更簡單~~

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

千萬不！要！劃！走！忍住沖動(dòng)！~

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

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

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

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

這里是奇跡物聯(lián)的物聯(lián)網(wǎng)應(yīng)用技術(shù)開源wiki主陣地，歡迎關(guān)注公眾號(hào)，不迷路～

及時(shí)獲得最新物聯(lián)網(wǎng)應(yīng)用技術(shù)沉淀發(fā)布

審核編輯 黃宇