區(qū)塊鏈的重要組成部分——梅克爾樹
cc 當(dāng)你想要了解區(qū)塊鏈技術(shù)時，梅克爾樹總是繞不開的話題。梅克爾樹作為區(qū)塊鏈的基本組成部分，在其中承擔(dān)著不可取代的作用。下面我們就通過本文來一起了解一下梅克爾樹。
梅克爾樹簡介
梅克爾樹因?yàn)槊麨镸erkle trees，又叫哈希樹，簡單來說就是區(qū)塊鏈中存儲hash值的一種樹狀型機(jī)構(gòu)，它由一個根節(jié)點(diǎn)、一組中間節(jié)點(diǎn)和一組葉節(jié)點(diǎn)組成。最下面的葉節(jié)點(diǎn)包含存儲數(shù)據(jù)或其哈希值，每個中間節(jié)點(diǎn)是它的兩個孩子節(jié)點(diǎn)內(nèi)容的哈希值，根節(jié)點(diǎn)也是由它的兩個子節(jié)點(diǎn)內(nèi)容的哈希值組成。
梅克爾樹的原理
梅克爾樹通常包含區(qū)塊體的底層數(shù)據(jù)庫， 區(qū)塊頭的根哈希值 (即Merkle根) 以及所有沿底層區(qū)塊數(shù)據(jù)到根哈希的分支。梅克爾樹運(yùn)算過程一般是將區(qū)塊體的數(shù)據(jù)進(jìn)行分組哈希， 并將生成的新哈希值插入到梅克爾樹中，如此遞歸直到只剩最后一個根哈希值并記為區(qū)塊頭的Merkle根。
最常見的梅克爾樹是比特幣采用的二叉梅克爾樹,，其每個哈希節(jié)點(diǎn)總是包含兩個相鄰的數(shù)據(jù)塊或其哈希值。其特點(diǎn)如下：
- 梅克爾樹是一種樹，大多數(shù)是二叉樹，也可以多叉樹，無論是幾叉樹，它都具有樹結(jié)構(gòu)的所有特點(diǎn)；
- Merkle Tree的葉子節(jié)點(diǎn)的value是數(shù)據(jù)集合的單元數(shù)據(jù)或者單元數(shù)據(jù)hash。
- 非葉子節(jié)點(diǎn)的value是根據(jù)它下面所有的葉子節(jié)點(diǎn)值，然后按照Hash算法計(jì)算而得出的。
梅克爾樹的作用
梅克爾樹大多用來進(jìn)行完整性驗(yàn)證。比如分布式環(huán)境下，從多臺主機(jī)獲取數(shù)據(jù)，怎么驗(yàn)證獲取的數(shù)據(jù)是否正確呢，只要驗(yàn)證梅克爾樹根哈希一致即可。
梅克爾樹還可以用來對數(shù)據(jù)進(jìn)行快速比對，快速定位到不一致的數(shù)據(jù)。比如分布式存儲中，一份數(shù)據(jù)會有多個副本，并且分布在不同的機(jī)器上。為了保持?jǐn)?shù)據(jù)一致性，需要進(jìn)行副本同步。如果采用直接傳輸數(shù)據(jù)進(jìn)行比對，非常低效，所以一般采用對數(shù)據(jù)進(jìn)行哈希，傳輸哈希值進(jìn)行對比的方法。因此，可以對每臺機(jī)器需要比對的數(shù)據(jù)構(gòu)造梅克爾樹，如果根哈希一致，則數(shù)據(jù)相同，如果根哈希不一致，則通過梅克爾樹快速檢索到不一致的數(shù)據(jù)。
梅克爾樹的種類
即根哈希（root hash）
梅克爾樹最為常見和最簡單的形式，是二進(jìn)制梅克爾樹（ binary Mekle tree），其中一bucket單位的數(shù)據(jù)塊總是包含了兩個相鄰的塊或哈希。哈希算法允許了一個整齊的機(jī)制，被稱之為梅克爾證明（Merkle proofs）。一個梅克爾證明包含了一個數(shù)據(jù)塊，這顆梅克爾樹的根哈希，以及包含了所有沿?cái)?shù)據(jù)塊到根路徑哈希的“分支”。
帕特里夏樹
以太坊所使用的梅克爾樹，被稱為“梅克爾.帕特里夏樹”（Merkle Patricia tree）。其工作原理，最為簡單的解釋是，一個以編碼形式存儲到記錄樹的“路徑”的值。每個節(jié)點(diǎn)會有16個子（children），所以路徑是由十六進(jìn)制編碼來確定的。
梅克爾樹的優(yōu)點(diǎn)
- 梅克爾樹極大地提高了區(qū)塊鏈的運(yùn)行效率和可擴(kuò)展性，使得區(qū)塊頭只需包含根哈希值而不必封裝所有底層數(shù)據(jù)，這使得哈希運(yùn)算可以高效地運(yùn)行在智能手機(jī)甚至物聯(lián)網(wǎng)設(shè)備上；
- 梅克爾樹可支持 “簡化支付驗(yàn)證” 協(xié)議，即在不運(yùn)行完整區(qū)塊鏈網(wǎng)絡(luò)節(jié)點(diǎn)的情況下，也能夠?qū)Γń灰祝?shù)據(jù)進(jìn)行檢驗(yàn)。
免責(zé)聲明：素材源于網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系刪稿。
