區塊鏈中Merkle樹性能研究①

黃 根,鄒一波,徐 云

1(中國科學技術大學 計算機科學與技術學院,合肥 230026)

2(上海海洋大學 信息學院,上海 201306)

3(安徽省高性能計算重點實驗室,合肥 230026)

自從2009年比特幣[1]問世,區塊鏈技術逐漸進入人們的視野.區塊鏈本質就是一個新型的分布式存儲系統[2],是將傳統計算機技術中的分布式存儲、分布式共識、密碼學、點對點傳輸的各種技術進行創新性結合的新技術,它也被視為繼大型機、個人電腦、互聯網和移動/社交網絡之后的第五種顛覆性創新技術[3],目前已經用于物聯網[4]、智能制造[5]、供應鏈管理[6]、數據資產交易[7]等多個領域.對于區塊鏈,主要實現了分布式存儲中的去中心化、去信任化、數據的時間序列化、集體維護等特征,同時也保障了可編程性、安全性和可靠性[8].

在區塊鏈中的每個區塊中,主要分為區塊頭和區塊體[9].Merkle 樹是區塊體的主要構成部分,構建Merkle 樹也是構建區塊體的主要工作.因此Merkle 樹的構建時間和存儲大小都將影響區塊鏈的性能.

在區塊鏈的技術發展過程中,Merkle 樹的結構也在不斷的發生改變.目前,主流的區塊鏈框架主要指比特幣、以太坊[10]和超級賬本[11].在比特幣中,其采用傳統的Merkle 樹結構;以太坊在比特幣的基礎上進行了改造,汲取了Patricia 樹檢索高效的優點,融合Merkle樹和Patricia 樹而產生的Merkle Patricia 樹[12];超級賬本為了減少添加數據的代價,采用了融合Merkle 樹和Hash 桶的Bucket 樹[11]結構.

在本文中,我們首先對區塊鏈中Merkle 樹的結構和關鍵操作進行分析,從理論上對Merkle 樹的作用和復雜度進行解析;然后根據分析結果提出相應的性能評測指標,最后通過實驗進行驗證和分析.

1 區塊鏈中的Merkle 樹結構分析

1.1 傳統Merkle 樹結構

在計算機科學與密碼學中,Merkle 樹是一種樹形數據結構.每個葉子節點均以數據塊的哈希值作為標簽,而除了葉子節點之外的節點則以其子節點標簽的加密哈希值作為標簽.Merkle 樹可以實現快捷的數據驗證,因此能夠高效地驗證大型數據結構的內容[13].

如圖1所示,該圖表明了Merkle 樹的結構.Merkle樹可以被看成是Hash 表的推廣,即Hash 表其實是樹高為2 的Merkle 樹.其形成的過程主要為:

圖1 Merkle 樹結構

(1)在Merkle 樹的最底層,將數據分成一個個小的數據塊,且各數據塊擁有對應的Hash 值,作為葉子節點;

(2)葉子節點到上層樹結構時,將相鄰的兩個Hash值合并成一個字符串,計算該字符串的Hash 值;

(3)每一層都重復過程(2),相鄰兩個Hash 值便可以一個子Hash 值.若最底層的Hash 總數為單數,則直接對其做Hash 運算.

從葉子節點向上依此類推,最終形成Merkle 樹.到了根節點就只剩下一個根Hash 值了,我們將其稱為Merkle Root.

1.2 區塊鏈中的Merkle 樹結構

在以比特幣、以太坊和超級賬本為代表的主流區塊鏈系統中,在Merkle 上分別有著不同的設計與實現.下面,我們將依次介紹這三種不同區塊鏈系統中Merkle 樹的結構.

(1) 比特幣的Merkle 樹

在比特幣系統中,區塊分為區塊頭和區塊體,其中區塊體則是由Merkle 樹構成.其中,整個區塊的大小為2 M,區塊頭的大小固定為80 個字節,因此,區塊體的大小占了整個區塊的96%.

比特幣的Merkle 結構和傳統的Merkle 樹完全相同.如圖1所示,在比特幣中,Merkle 樹的葉子結點為系統中每一筆交易的Hash 值.不同交易利用Merkle樹的結構進行組合,最終生成比特幣的Merkle 樹,同時產生由所有交易產生的Merkle 根.

(2) 以太坊的Merkle 樹

在比特幣模型中,采用UTXO 模型表示數據,因此采用傳統的Merkle 樹簡單快捷[14];但是以以太坊為代表的第二代區塊鏈中,大多采用賬戶模型[15],此時傳統的Merkle 樹會帶來極大的存儲空間消耗,并且不易查詢.因此,在以太坊中,對Merkle 樹進行改進,設計出一種新的數據結構-Merkle Patricia 樹進行數據存儲.

Merkle Patricia 樹簡稱MPT,其本質上是先將前綴樹進行改進,然后再和Merkle 樹進行結合.

在原始的前綴樹中,存在空間浪費、節點不易控制、深度長等缺陷.MPT 在前綴樹的基礎上進行了改進,主要做了以下幾個方面.

① 為了防止key 的長度不同造成浪費,首先將所有的key 值進行Hash,將所有的key 轉換成相同的長度;

② 為了方便對節點的控制,將所有的節點分為空節點、分支節點、葉子節點和擴展節點4 種不同的節點,分別存儲不同的內容;

③ 為了更好的進行比較,將key 中的每個參數進行hex 編碼.同時使用hex 編碼后,每個值大小為[0-15],可以使每個分支節點的容量都減小;

④ 為了縮短樹的深度,將連續兩個級以上的擴展節點進行合并.

通過如上4 步改進,傳統的前綴樹結構如圖2所示.最后,將改進后的前綴樹和Merkle 樹進行結合,將存儲的value 值轉換成所有子節點的Hash 值,即可組成Merkle Patricia 樹.

圖2 改進的前綴樹

(3) 超級賬本的Merkle 樹

超級賬本采用賬戶模型來進行數據存儲[16],但是以太坊的MPT 樹結構復雜、性能低,超級賬本則提出了Bucket 樹[17]進行數據存儲.

Bucket 樹其實是揉合了Merkle 樹與Hash 桶兩種數據結構組合而成的,即Bucket 樹本質上是一棵建立在Hash 表上的Merkle 樹.

如圖3所示,B1-B6 為數據的Hash 桶,每個桶中儲存若干被散列到該桶中的數據項,所有數據項都按序排列.每一個桶有可以用一個Hash 值表示其狀態,該Hash 值是桶內所有數據項的內容進行Hash 計算所得.除底層的Hash 表之外,上層是一系列Merkle 樹節點.一個Merkle 樹節點對應下一層的n個Hash 桶或Merkle 節點.Merkle 節點的Hash 值是根據這n個孩子節點的Hash 值計算所得.通過這種方式不斷計算,與Merkle 樹類似,最頂端的值即為整棵樹的Hash 值,即Merkle 根.由此可以生成完整的Bucket 樹.

圖3 Bucket 樹

2 區塊鏈中Merkle 關鍵操作分析

區塊鏈本質上是一個去中心化的數據庫,Merkle樹是區塊鏈中核心存儲的數據.和傳統的數據庫相比,區塊鏈只能進行增加和查詢的操作,而不能進行刪除和修改.因此,Merkle 樹中核心的操作就是數據插入.同時,Merkle 樹的一個重要作用是SPV 驗證(實現簡單支付驗證),即Merkle 樹可以直接下載一個分支并立即驗證.因此,在本文中,我們主要分析Merkle 樹中兩個核心的操作:插入數據和SPV 驗證.

2.1 數據插入

數據插入是Merkle 樹中最為核心的操作,是實現區塊鏈系統中數據插入功能的底層.因此,理解不同區塊鏈系統中Merkle 樹的數據插入的原理,是理解不同區塊鏈系統性能瓶頸的重要途徑.

對于比特幣中的Merkle 樹,當需要插入一個新的數據時,通常在之前的Merkle 樹基礎上進行插入.如圖4所示,如果插入數據L4,通常情況下只需要在之前的Mekle 的基礎上重新插入一條新的路徑,然后通過和之前的Merkle 樹中的節點進行Hash 計算,即可產生新的Merkle 樹.

圖4 Merkle 樹的插入

對于以太坊中的MPT,其插入數據的過程相對比較復雜,其核心的思想為:按照key 的內容,從根節點依次從上往下尋找相同長度的路徑,同時隨時根據MPT 的性質改變節點的性質,插入新的key 的值,直到key 遍歷結束.如圖5所示,該虛線路徑展現了鍵值對為＜‘1,2,2,4,5’,‘gen’＞的數據插入.

圖5 MPT 的插入

對于超級賬本中的Bucket 樹,當插入新的數據時,需要對進行計算和合并兩個過程.

如圖6所示,在Bucket 樹中新插入兩條數據項Entry1,通常通過以下兩個步驟:

圖6 Bucket 樹插入數據

計算:經過散列值計算,Entry1 應該放到B2 中.

合并:在B2 中需要將新插入的數據與歷史數據進行合并,且按固定的排序算法進行重排序,最終得到一個新Hash 桶,即改變B2 的值;

當Hash 桶計算完成之后,便可進行Merkle 節點的Hash 計算.該過程僅對需要改變的節點進行Hash重計算.對沒有變化的孩子節點可直接使用歷史的Hash值.即需要重新計算Hash0-1,Hash0,Root 節點.

2.2 SPV 驗證

在比特幣中,Merkle 的主要作用是實現SPV 驗證.SPV 驗證全稱叫做簡單支付驗證,即區塊鏈中的SPV節點(輕型節點)驗證某個交易是否已經在交易中,是區塊鏈系統可以在手機等移動端運行的關鍵.

在SPV 驗證中,Merkle 主要完整交易的存在性檢查.其過程主要是

(1) SPV 節點從身邊的全節點向獲取待交易的Merkle分支;

(2) 利用Merkle 分支與本地的交易生成Merkle根,與本地的Merkle 根進行比較,驗證交易的存在性.

如圖7所示,SPV 節點驗證交易L3 的存在性,只需要通過全節點獲取L3 的Merkle 分支,即＜Hash1-1,Hash0＞節點,然后通過L3 與Merkle 分支的計算即可獲得Root,最后通過比較Root 和本地存儲的Merkle根是否相同判斷L3 是否已經在區塊中[16].

圖7 SPV 驗證過程

如上分析,使用Merkle 分支進行存在性檢查,對于n 個交易來說,傳輸的區塊數為log(n),可以大大較少數據傳輸的數量,降低網絡傳輸的負擔.

對于以太坊來說,因為其在前綴樹的基礎上集成了Merkle 樹,因此在其SPV 驗證和比特幣系統相同:在SPV 節點中,也是主要存儲了Merkle 根,之后從鄰居的全節點獲取Merkle 分支,通過哈希計算查詢獲取Root,最后和本地存在的Merkle 根進行比較以判斷交易的存在性.

對于超級賬本的Bucket 樹來說,由于其葉子結點為有序的哈希桶,哈希桶中存在大量的數據.如果需要實現SPV 驗證,其不僅僅需要傳輸Merkle 分支,同時需要傳輸Hash 桶中的其他元素,會大大增加傳輸數據的數量,增加網絡負擔.因此,在超級賬本中很少有提及SPV 相關的操作.

2.3 性能總結

從上述的所有內容中,我們分析了比特幣中的Merkle 樹、以太坊中的Merkle Patricia 樹以及超級賬本中的Bucke 樹的結構和主要操作.假設對于n個＜key,value＞鍵值對的數據,MPT 樹中每個key 值Hash后的長度為m,Bucket 樹中每個節點有a個子節點,葉子節點個數為C,那么從理論上進行分析,Merkle 樹,MPT和Bucket 樹的插入時間復雜度,空間復雜度和SPV 傳輸節點數的理論復雜度如表1所示.

表1 不同種類樹理論性能分析

3 實驗性能分析指標設計

在之前的工作中,我們分析了Merkle 樹的結構和兩大核心操作.因此,在實驗中,我們主要從插入數據性能,數據存儲和SPV 驗證性能3 個方面進行相關的實驗,以驗證之前的理論分析.為了更好的定量表現出相關性能,我們設計了相關的指標,分別體現出插入數據,數據存儲和SPV 驗證的相關性能.

3.1 構建時間

首先考慮插入數據的時間開銷.對于一個相關的數據來說,插入數據的時間極短,其插入數據的時間開銷可能比程序代碼在其他地方運行的時間更短,因此較難使用程序來統計一個數據的插入時間.但是,在區塊鏈系統中,構建區塊的過程中存在非常重要的一步就是將交易池中的眾多交易進行打包構建成Merkle樹,其本質上就是將交易池的數據一個個插入到Merkle樹中以構成最終的Merkle 樹并存入區塊中.因此,在本實驗中,我們采用統計不同規模數據集下Merkle 樹的構建時間來進一步的表現出不同Merkle 樹的插入性能.

3.2 節點數及樹的深度

其次,我們考慮不同Merkle 樹帶來的數據存儲.目前區塊過大已經是區塊鏈系統中十分關鍵的問題,而Merkle 樹作為區塊中主要存儲的數據,對比不同Merkle 樹的存儲性能對我們之后選擇不同的區塊鏈結構是十分有必要的.

對于Merkle 樹來說,節點數目的大小會直接影響Merkle 樹的存儲大小:更多節點的Merkle 樹節點存儲規模顯然會更大.對于不同的Merkle 樹結構來說,相同的數據在不同的Merkle 樹結構上的節點數目和樹的深度是不同的.因此可以統計不同規模的數據在Merkle 樹上的節點數和深度來定量的表示在不同Merkle樹的存儲性能.

3.3 SPV 驗證中Merkle 分支節點數

如第2 節所述,區塊鏈中的SPV 驗證是Merkle 樹中的重要功能之一,因此檢測SPV 驗證的相關性能也是對Merkle 樹性能分析的重要組成部分.

在進行SPV 驗證時,主要關心兩個性能指標.首先是Merkle 分支的節點數,該指標會影響在網絡傳輸中的性能,太大的Merkle 分支會造成較大網絡傳輸的負擔,嚴重影響網絡傳輸的性能.其次,Merkle 分支樹也會影響SPV 驗證的時間性能,因為更多的Merkle 分支節點就需要更多的重組Hash 運算,影響做SPV 驗證的時間效率.因此,在本實驗分析中,我們只需要利用Merkle 分支的節點數目來分析對SPV 驗證的網絡傳輸和時間的性能.

4 比較實驗結果與分析

在本實驗中,我們通過實驗設計,利用Merkle 樹的構建時間、Merkle 樹的節點數、樹的深度和SPV驗證的Merkle 分支節點數來進一步分析和驗證不同區塊鏈系統中Merkle 樹的相關性能.

4.1 實驗設計

本文中,我們主要進行分析和比較比特幣中的Merkle 樹,以太坊中Merkle Patricia 樹和超級賬本中的Bucket 樹.為了消除其他因素的影響而直接分析不同Merkle 的性能,我們利用統一的語言(Java)對3 種樹的結構進行實現.

在數據方面,為了更好的適配MPT 結構,我們統一使用賬戶模型.如圖8所示,在本實驗中,我們通過隨機產生的方式,生成了數量為1000、10 000、50 000和100 000 的鍵值對.這些鍵值對的key 值不固定大小,其長度從4 到20 不等;value 的值也不固定大小,長度從6 到30 不等.

針對3 種Merkle 樹結構,具體的實驗過程為:

在Merkle 樹的實驗中,將key 和value 的值利用“--”字符串進行合并,組成一個新的字符串.之后將新的字符串的Hash 值,作為Merkle 樹的葉子節點.

在Merkle Patricia 樹的實驗中,首先要對key 值進行Hash 運算,將key 編成16 字節的固定長度.然后利用Hex 編碼進行編碼,之后采用MPT 樹的相關算法實現完整的MPT 樹結構.

圖8 數據集格式

在Bucket 樹的實驗中,確定100 個Hash 桶,每個節點最多有3 個子節點.然后將所有的鍵值隨機分配到Hash 桶中,保證每個Hash 桶的鍵值對應數目基本均勻,最后構建Bucket 樹.

4.2 實驗結果

在本實驗中,我們首先對3 種不同Merkle 樹架構的存儲進行分析.如3.2 節所述,在Merkle 樹存儲分析時,我們利用樹的規模作為反映存儲空間的指標.即利用樹的節點數和樹的深度來進行表示.通過實驗,表2和表3表示在不同數據規模下3 種不同Merkle 樹結構的節點數和深度.

表2 不同規模樹節點數比較(個)

表3 不同規模樹深度比較

從表2中可以看出,在1000、10 000、50 000、100 000組數據的情況下,Merkle 樹的節點數均為最多,分別為2001、20 004、99 938 和199 750 個;MPT 的節點數居中,Bucket 樹的節點數最小,均為154 個.

再看樹的深度,從表3可知,在1000、10 000、50 000、100 000 組數據的情況下,Merkle Patricia 樹的樹深均為32,Merkle 樹的深度分別為11,15,17 和18,Bucket 樹的深度均為6.因此,在樹的深度方面,Merkle Patricia 樹的樹深遠遠大于Merkle 樹和Bucket 樹兩種算法.同時Merkle Patricia 樹和Bucket 樹的樹深比較穩定,不會隨著節點數的增加而增加.

其次,如3.1 節所述,我們進一步對3 種不同Merkle樹的構建時間進行分析.如表4所示,表明了3 種不同的Merkle 樹分別創建1000、10 000、50 000 和100 000組數據的數據結構所需的時間.

表4 不同規模樹創建時間比較(ms)

由表4可以看出,在相同規模的數據下,Merkle Patricia 樹的創建時間最多,遠大于其他兩種Merkle 結構;Merkle 樹的創建時間居中,Bucket 樹的創建時間最短.

最后,我們需要評測3 種Merkle 樹在做SPV 驗證.在實驗中,我們分別取了3 種Merkle 樹的Merkle路徑,如表5所示.

表5 不同規模樹Merkle 分支(個)

從表5可以看到,可以看到比特幣,以太坊和超級賬本在不同規模數據下的Merkle 路徑的長度,相比之下3 種系統的規模有著明顯的差異.Merkle 樹的Merkle路徑所需要的節點最少,其次是MPT 樹.Bucket 樹我們采用和Merkle 樹相同SPV 驗證的方法進行統計Merkle路徑,所需要的Merkle 路徑總體來說最長.

4.3 實驗總結與分析

如4.2 節所示,在存儲方面,如果從節點數目來看,Merkle 所擁有的節點較多,即所占存儲較大,其次是MPT 樹,Bucket 樹所占空間最小.從之前的理論上分析來看,由于Merkle Patricia 樹和Bucket 樹均采取措施壓縮數據,其中MPT 樹使用前綴樹算法,Bucket 樹使用Hash 桶,故其節點數均小于Merkle 樹.值得注意的是,MPT 樹的節點數其實與Merkle 樹較為接近.

從樹的深度來看,MPT 樹最大,Merkle 其次,Bucket中樹的深度最小.從理論上分析,由于在生成MPT 樹的過程中,首先要將key 值Hash 運算為16 的長度,同時采用Hex 編碼,會擴大樹的深度,因此MPT 應該是一個非常狹長的樹狀結構;但是由于key 的長度一定,因此其深度永遠不會進行增長;而Merkle 樹的深度是數據個數的log(n),會隨著數據的增多而增加;Bucket樹中底層的Hash 桶數量不會發生改變,因此其樹的深度很小,同時其不會因為數據規模的增加而改變.

從構建時間來看,同樣是MPT 的構造時間最長,Bucket 樹的構造時間最短.出現這種情況是由其算法的特殊性導致的:首先,為了提高節點的查找效率和減少存儲空間浪費,MPT 樹對單獨存在的key 進行了合并,這需要占用一定時間;其次,為避免樹中出現很長的路徑并提高MPT 樹的安全性,需要對每個key 求Hash 值,這一過程需要花費大量時間.而Bucket 只需要進行Hash 桶的排序和求Hash,上層的Merkle 樹的規模較小;而Merkle 樹只需要進行結構的構建.因此,MPT 樹創建時間遠大于其他兩種算法.

從SPV 來看,在3 種Merkle 樹中,比特幣中Merkle路徑最短,超級賬本最多,以太坊居中.其原因是因為比特幣和超級賬本中只需要獲取相應的路徑上的節點即可,因此其Merkle 路徑的長度應該和對應Merkle 樹的深度成正比;而Bucket 樹底層是對有序的Hash 桶求Hash,所以如果進行SPV 驗證即不僅僅需要傳遞路徑上的數據,同時也需要Hash 桶中其他的數據.因此,在三種區塊鏈結構中,比特幣應該最適合于在手機移動端使用,超級賬本不適合在移動端實現.

5 結論與展望

在本文中,我們首先分析了比特幣,以太坊和超級賬本這3 種主流區塊鏈中Merkle 樹的相關結構和核心操作,同時根據Merkle 樹的作用和特性,提出了相應的性能指標.然后利用統一的語言進行了實現,并進行了相關性能指標的檢測.實驗結果表明,比特幣的Merkle 樹結構會造成更多的存儲消耗,以太坊的MPT結構會造成更多的時間消耗,超級賬本的Bucket 樹SPV 驗證最難.本文的操作分析和實驗環境為我們接下來的工作也奠定了基礎,接下來我們將針對Merkle樹的特性和不足,希望提出新的Merkle 樹結構,在插入時間、存儲或者SPV 的驗證上取得更好的發展.