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

01 引言

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

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

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

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

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

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

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

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

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

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

方案3：文件存儲

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

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

03 Merkle 樹的更新和節(jié)點編號策略

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

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

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

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

04 Merkle 樹的壓縮表示

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

type CompactMerkleTree struct {

hashes ［］common.Uint256

treeSize uint32

}

計算 Merkle 樹的根 Hash

根據(jù)壓縮 Merkle 樹的定義可知，只需要將 hashes 數(shù)組中的 hash 值從右向左依次 fold 計算，即可拿到根 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ù)返回兩個子節(jié)點 hash 對應的父節(jié)點 hash 值。

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

當有新的葉子節(jié)點插入時，會根據(jù) Merkle 樹當前狀態(tài)對該樹進行動態(tài)更新。插入新的葉子節(jié)點算法如下：

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ān)數(shù)據(jù)變更示意圖

Merkle 樹在增長過程中，存儲在文件中的 hash 值數(shù)據(jù)和其對應的壓縮表示數(shù)據(jù)變更示意圖如下。

圖一是 Merkle 樹單個節(jié)點時的狀態(tài)：

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

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

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

06 結(jié)論

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

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

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