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

01 引言

Merkle 樹是一種樹型數據結構，其葉子節點是數據塊的 hash 值，而非葉子節點是其對應子節點 hash 值串聯后字符串的 hash 值。利用 Merkle 樹，能夠在只有部分數據塊的情況下校驗數據完整性。因此，Merkle 樹通常可以用于 p2p 網絡等場景中，從不可信的數據源中取得數據，對數據一邊進行同步，一邊進行校驗。在這些場景中，Merkle 樹的引入可以避免對整個大數據集同步完后校驗出錯，不得不丟棄所有數據，而浪費帶寬的問題。

對于區塊鏈平臺，客戶端通常只需要關注自己賬戶的信息。在這種情況下，如果客戶端完整地同步所有賬本信息，效率將會十分低下。因此，在區塊鏈中，一般引入 SPV （Simple Payment Verification） 驗證技術，通過構造 Merkle 證明，客戶端只需要同步部分數據，就可以達到驗證相關數據的目的。這會極大地節省存儲空間，減輕終端用戶存儲和網絡傳輸的負擔。

在 Ontology 中，Merkle 樹也有不少應用場景，其中之一就是將每個區塊的交易根作為葉子節點，構造出一個區塊 Merkle 樹，用于提供交易上鏈的存在性證明。本文主要描述 Ontology 在實現 Merkle 樹時的相關優化細節。

02 Merkle 樹數據結構的存儲

在大多數區塊鏈中，Merkle 樹一般用在單個區塊里，由多個交易的 hash 值作為葉子節點構成。

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

方案1：內存存儲

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

方案2：k-v 型數據庫存儲

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

方案3：文件存儲

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

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

03 Merkle 樹的更新和節點編號策略

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

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

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

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

04 Merkle 樹的壓縮表示

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

type CompactMerkleTree struct {

hashes ［］common.Uint256

treeSize uint32

}

計算 Merkle 樹的根 Hash

根據壓縮 Merkle 樹的定義可知，只需要將 hashes 數組中的 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 函數返回空 hash，hash_children 函數返回兩個子節點 hash 對應的父節點 hash 值。

插入新的葉子節點

當有新的葉子節點插入時，會根據 Merkle 樹當前狀態對該樹進行動態更新。插入新的葉子節點算法如下：

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 樹增大過程的相關數據變更示意圖

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

圖一是 Merkle 樹單個節點時的狀態：

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

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

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

06 結論

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

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

另外，在需要提供證明服務的情況下，Ontology 實現的方案可以避免頻繁地讀寫數據以及維護樹的關系，只需要對相關文件進行 append 操作，極大地簡化了數據一致性的容錯設計。
責任編輯；zl