如何存儲(chǔ)Merkle樹

苗，由樹根長(zhǎng)出樹干，樹干長(zhǎng)出樹枝，樹枝又長(zhǎng)出葉子，最后就這樣長(zhǎng)成了參天大樹。計(jì)算機(jī)界也有棵樹，名叫 Merkle，由一個(gè)根節(jié)點(diǎn)、一組中間節(jié)點(diǎn)和一組葉子節(jié)點(diǎn)組成。根節(jié)點(diǎn)表示是最終的那個(gè)節(jié)點(diǎn)，且只有一個(gè)。葉子節(jié)點(diǎn)可以有很多，但是無(wú)法再繼續(xù)擴(kuò)散出更多的子節(jié)點(diǎn)了。這棵樹有什么神奇的作用呢？

01 引言

Merkle 樹是一種樹型數(shù)據(jù)結(jié)構(gòu)，其葉子節(jié)點(diǎn)是數(shù)據(jù)塊的 hash 值，而非葉子節(jié)點(diǎn)是其對(duì)應(yīng)子節(jié)點(diǎn) hash 值串聯(lián)后字符串的 hash 值。利用 Merkle 樹，能夠在只有部分?jǐn)?shù)據(jù)塊的情況下校驗(yàn)數(shù)據(jù)完整性。因此，Merkle 樹通?？梢杂糜?p2p 網(wǎng)絡(luò)等場(chǎng)景中，從不可信的數(shù)據(jù)源中取得數(shù)據(jù)，對(duì)數(shù)據(jù)一邊進(jìn)行同步，一邊進(jìn)行校驗(yàn)。在這些場(chǎng)景中，Merkle 樹的引入可以避免對(duì)整個(gè)大數(shù)據(jù)集同步完后校驗(yàn)出錯(cuò)，不得不丟棄所有數(shù)據(jù)，而浪費(fèi)帶寬的問(wèn)題。

對(duì)于區(qū)塊鏈平臺(tái)，客戶端通常只需要關(guān)注自己賬戶的信息。在這種情況下，如果客戶端完整地同步所有賬本信息，效率將會(huì)十分低下。因此，在區(qū)塊鏈中，一般引入 SPV （Simple Payment Verification） 驗(yàn)證技術(shù)，通過(guò)構(gòu)造 Merkle 證明，客戶端只需要同步部分?jǐn)?shù)據(jù)，就可以達(dá)到驗(yàn)證相關(guān)數(shù)據(jù)的目的。這會(huì)極大地節(jié)省存儲(chǔ)空間，減輕終端用戶存儲(chǔ)和網(wǎng)絡(luò)傳輸?shù)呢?fù)擔(dān)。

在 Ontology 中，Merkle 樹也有不少應(yīng)用場(chǎng)景，其中之一就是將每個(gè)區(qū)塊的交易根作為葉子節(jié)點(diǎn)，構(gòu)造出一個(gè)區(qū)塊 Merkle 樹，用于提供交易上鏈的存在性證明。本文主要描述 Ontology 在實(shí)現(xiàn) Merkle 樹時(shí)的相關(guān)優(yōu)化細(xì)節(jié)。

02 Merkle 樹數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)

在大多數(shù)區(qū)塊鏈中，Merkle 樹一般用在單個(gè)區(qū)塊里，由多個(gè)交易的 hash 值作為葉子節(jié)點(diǎn)構(gòu)成。

而在 Ontology 方案中，由于區(qū)塊 Merkle 樹是隨著區(qū)塊高度的增長(zhǎng)進(jìn)行動(dòng)態(tài)增量增長(zhǎng)的結(jié)構(gòu)，因此要更加復(fù)雜。這就涉及到如何存儲(chǔ) Merkle 樹的問(wèn)題。一般來(lái)說(shuō)，可以考慮如下三種方案：

方案1：內(nèi)存存儲(chǔ)

該方案就是把 Merkle 樹存儲(chǔ)在內(nèi)存中。該方案存在兩個(gè)缺陷。首先，由于沒有進(jìn)行持久化存儲(chǔ)，在節(jié)點(diǎn)關(guān)機(jī)重啟時(shí)，需要遍歷所有區(qū)塊，重新構(gòu)造出完整的 Merkle 樹，相對(duì)耗時(shí)；其次，隨著交易和區(qū)塊的增長(zhǎng)，Merkle 樹不斷增大，內(nèi)存的占用也會(huì)線性增長(zhǎng)，影響擴(kuò)展性。因此，內(nèi)存存儲(chǔ)方案并非長(zhǎng)久之計(jì)。

方案2：k-v 型數(shù)據(jù)庫(kù)存儲(chǔ)

該方案就是把 Merkle 樹存儲(chǔ)在 k-v 型數(shù)據(jù)庫(kù) （如 LevelDB） 中。由于 k-v 的關(guān)系比較簡(jiǎn)單，用來(lái)表示樹形關(guān)系結(jié)構(gòu)，需要對(duì) key 和 value 進(jìn)行特定的編碼，同時(shí)對(duì)具體的樹節(jié)點(diǎn)的檢索也需要多次讀取，其整體效率比較低下。

方案3：文件存儲(chǔ)

由于 Merkle 樹的節(jié)點(diǎn)都是長(zhǎng)度固定的 hash 值，如果能夠?qū)涞墓?jié)點(diǎn)和整數(shù)值進(jìn)行一一映射，那么就可以將整個(gè)樹壓縮為一維數(shù)組。要訪問(wèn)特定的樹節(jié)點(diǎn)時(shí)，可以先將其對(duì)應(yīng)的整數(shù)值算出來(lái)，并將它作為數(shù)組的下標(biāo)，就可以拿到樹節(jié)點(diǎn)的數(shù)據(jù)。將這個(gè)數(shù)組存儲(chǔ)在文件里就可以解決樹線性增長(zhǎng)的問(wèn)題。

樹節(jié)點(diǎn)和整數(shù)進(jìn)行映射的方式有多種，最直觀的就是根據(jù)樹的深度一層層編號(hào)，然而這種方案有一個(gè)問(wèn)題：樹的大小改變后節(jié)點(diǎn)的編號(hào)和其原先的編號(hào)會(huì)不一致，導(dǎo)致需要把數(shù)據(jù)全部讀取出來(lái)，再按新的編號(hào)進(jìn)行保存，將會(huì)大大降低效率。因此，找到一種穩(wěn)定的節(jié)點(diǎn)編號(hào)方式是該方案可行的關(guān)鍵。

03 Merkle 樹的更新和節(jié)點(diǎn)編號(hào)策略

采用文件存儲(chǔ)的方案除了需要穩(wěn)定的節(jié)點(diǎn)編號(hào)方式外，還有另一個(gè)問(wèn)題。由于不斷有新的區(qū)塊節(jié)點(diǎn)插入，會(huì)導(dǎo)致 Merkle 樹節(jié)點(diǎn)需要頻繁更新，也就是說(shuō)需要對(duì)存儲(chǔ)文件進(jìn)行不停地改寫，這也會(huì)導(dǎo)致效率降低。

更為復(fù)雜的是，這需要一種數(shù)據(jù)一致性處理機(jī)制。我們考慮這樣一種場(chǎng)景，在將樹節(jié)點(diǎn)更新到一半時(shí)，區(qū)塊鏈節(jié)點(diǎn)突然宕機(jī)，那么文件里存儲(chǔ)的 Merkle 樹數(shù)據(jù)就會(huì)產(chǎn)生不一致。

通過(guò)對(duì) Merkle 樹節(jié)點(diǎn)插入的觀察可知，Merkle 樹中存在兩類節(jié)點(diǎn)：一種是會(huì)隨著后續(xù)節(jié)點(diǎn)的插入，節(jié)點(diǎn)值會(huì)改變的臨時(shí)節(jié)點(diǎn)；另一種是不會(huì)隨后續(xù)節(jié)點(diǎn)插入而改變的恒定節(jié)點(diǎn)。不難證明，成為恒定節(jié)點(diǎn)的條件是當(dāng)該節(jié)點(diǎn)及其子孫節(jié)點(diǎn)構(gòu)成的子樹是一個(gè)完全樹。另外，臨時(shí)節(jié)點(diǎn)的個(gè)數(shù)較少，只有 log（n），且可以由恒定節(jié)點(diǎn)計(jì)算出來(lái)，持久化后會(huì)因后續(xù)節(jié)點(diǎn)的插入立馬改變。

所以，在 Ontology 的方案中，文件里只保存了恒定節(jié)點(diǎn)。同時(shí)，一個(gè)巧妙的地方是，按恒定節(jié)點(diǎn)出現(xiàn)的順序進(jìn)行編號(hào)，正好就是一種穩(wěn)定的編號(hào)方案。在這種情況下，對(duì)文件只有 append 操作，也就避免了因文件改寫而導(dǎo)致的數(shù)據(jù)不一致的問(wèn)題。

04 Merkle 樹的壓縮表示

由于恒定節(jié)點(diǎn)不變的特性，也就是說(shuō)其子節(jié)點(diǎn)對(duì)后續(xù) Merkle 樹更新不會(huì)有貢獻(xiàn)，因此對(duì)于那些只需要計(jì)算最新的 Merkle 根 hash 值，而不需提供構(gòu)造證明服務(wù)的節(jié)點(diǎn)，可以只保存 log（n） 個(gè)子完全樹的樹根節(jié)點(diǎn)。這可以代表整個(gè) Merkle 樹的狀態(tài)，同時(shí)可以使整個(gè)樹的存儲(chǔ)降至 log（n），方便存儲(chǔ)在 LevelDB 的一個(gè) key 中，Merkle 樹的更新只需一次讀寫。其結(jié)構(gòu)定義如下：

type CompactMerkleTree struct {

hashes ［］common.Uint256

treeSize uint32

}

計(jì)算 Merkle 樹的根 Hash

根據(jù)壓縮 Merkle 樹的定義可知，只需要將 hashes 數(shù)組中的 hash 值從右向左依次 fold 計(jì)算，即可拿到根 hash。算法如下：

func （self *CompactMerkleTree） Root（） common.Uint256 {

if len（self.hashes） == 0 {

return hash_empty（）

}

hashes = self.hashes

l ：= len（hashes）

accum ：= hashes［l-1］

for i ：= l - 2; i 》= 0; i-- {

accum = hash_children（hashes［i］， accum）

}

return accum

}

其中，hash_empty 函數(shù)返回空 hash，hash_children 函數(shù)返回兩個(gè)子節(jié)點(diǎn) hash 對(duì)應(yīng)的父節(jié)點(diǎn) hash 值。

插入新的葉子節(jié)點(diǎn)

當(dāng)有新的葉子節(jié)點(diǎn)插入時(shí)，會(huì)根據(jù) Merkle 樹當(dāng)前狀態(tài)對(duì)該樹進(jìn)行動(dòng)態(tài)更新。插入新的葉子節(jié)點(diǎn)算法如下：

func （self *CompactMerkleTree） Append（leaf common.Uint256） {

size ：= len（self.hashes）

for s ：= self.treeSize; s%2 == 1; s = s 》》 1 {

leaf = hash_children（self.hashes［size-1］， leaf）

size -= 1

}

self.treeSize += 1

self.hashes = self.hashes［0:size］

self.hashes = append（self.hashes， leaf）

}

05 Merkle 樹增大過(guò)程的相關(guān)數(shù)據(jù)變更示意圖

Merkle 樹在增長(zhǎng)過(guò)程中，存儲(chǔ)在文件中的 hash 值數(shù)據(jù)和其對(duì)應(yīng)的壓縮表示數(shù)據(jù)變更示意圖如下。

圖一是 Merkle 樹單個(gè)節(jié)點(diǎn)時(shí)的狀態(tài)：

當(dāng)在該 Merkle 樹中插入另外一個(gè)節(jié)點(diǎn) b 時(shí)，樹的大小增加了1。同時(shí)，新節(jié)點(diǎn) b 可以和原節(jié)點(diǎn) a 串聯(lián)后，計(jì)算 hash 值得到 c：

當(dāng)在該 Merkle 樹中再插入另外一個(gè)節(jié)點(diǎn) d 時(shí)，由于已存在節(jié)點(diǎn)形成一棵完全樹，因此壓縮表示時(shí)只要簡(jiǎn)單加入 d 即可。

下面的圖表示了 Merkle 樹節(jié)點(diǎn)從3個(gè)增加到7個(gè)的情況。小伙伴們可以根據(jù)我們的存儲(chǔ)策略進(jìn)行推導(dǎo)。

06 結(jié)論

Merkle 樹在很多應(yīng)用場(chǎng)景中都有著廣泛應(yīng)用。在 Ontology 中，Merkle 樹的一個(gè)應(yīng)用場(chǎng)景就是將每個(gè)區(qū)塊的交易根作為葉子節(jié)點(diǎn)，構(gòu)造出一個(gè)區(qū)塊 Merkle 樹，用于提供交易上鏈的存在性證明。

在不需要提供證明服務(wù)的情況下，可以使共識(shí)節(jié)點(diǎn)的性能和存儲(chǔ)能力得到極大提升。Ontology 在實(shí)現(xiàn)區(qū)塊 Merkle 樹的過(guò)程中，只將區(qū)塊 Merkle 樹的關(guān)鍵節(jié)點(diǎn)進(jìn)行存儲(chǔ)。通過(guò)這種方法，我們只讀寫一次 LevelDB 就可以更新 Merkle 樹，計(jì)算復(fù)雜度達(dá)到 O（log n）。

另外，在需要提供證明服務(wù)的情況下，Ontology 實(shí)現(xiàn)的方案可以避免頻繁地讀寫數(shù)據(jù)以及維護(hù)樹的關(guān)系，只需要對(duì)相關(guān)文件進(jìn)行 append 操作，極大地簡(jiǎn)化了數(shù)據(jù)一致性的容錯(cuò)設(shè)計(jì)。