區(qū)塊鏈中Merkle樹性能研究①

黃 根,鄒一波,徐 云

1(中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,合肥 230026)

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

3(安徽省高性能計(jì)算重點(diǎn)實(shí)驗(yàn)室,合肥 230026)

自從2009年比特幣[1]問(wèn)世,區(qū)塊鏈技術(shù)逐漸進(jìn)入人們的視野.區(qū)塊鏈本質(zhì)就是一個(gè)新型的分布式存儲(chǔ)系統(tǒng)[2],是將傳統(tǒng)計(jì)算機(jī)技術(shù)中的分布式存儲(chǔ)、分布式共識(shí)、密碼學(xué)、點(diǎn)對(duì)點(diǎn)傳輸?shù)母鞣N技術(shù)進(jìn)行創(chuàng)新性結(jié)合的新技術(shù),它也被視為繼大型機(jī)、個(gè)人電腦、互聯(lián)網(wǎng)和移動(dòng)/社交網(wǎng)絡(luò)之后的第五種顛覆性創(chuàng)新技術(shù)[3],目前已經(jīng)用于物聯(lián)網(wǎng)[4]、智能制造[5]、供應(yīng)鏈管理[6]、數(shù)據(jù)資產(chǎn)交易[7]等多個(gè)領(lǐng)域.對(duì)于區(qū)塊鏈,主要實(shí)現(xiàn)了分布式存儲(chǔ)中的去中心化、去信任化、數(shù)據(jù)的時(shí)間序列化、集體維護(hù)等特征,同時(shí)也保障了可編程性、安全性和可靠性[8].

在區(qū)塊鏈中的每個(gè)區(qū)塊中,主要分為區(qū)塊頭和區(qū)塊體[9].Merkle 樹是區(qū)塊體的主要構(gòu)成部分,構(gòu)建Merkle 樹也是構(gòu)建區(qū)塊體的主要工作.因此Merkle 樹的構(gòu)建時(shí)間和存儲(chǔ)大小都將影響區(qū)塊鏈的性能.

在區(qū)塊鏈的技術(shù)發(fā)展過(guò)程中,Merkle 樹的結(jié)構(gòu)也在不斷的發(fā)生改變.目前,主流的區(qū)塊鏈框架主要指比特幣、以太坊[10]和超級(jí)賬本[11].在比特幣中,其采用傳統(tǒng)的Merkle 樹結(jié)構(gòu);以太坊在比特幣的基礎(chǔ)上進(jìn)行了改造,汲取了Patricia 樹檢索高效的優(yōu)點(diǎn),融合Merkle樹和Patricia 樹而產(chǎn)生的Merkle Patricia 樹[12];超級(jí)賬本為了減少添加數(shù)據(jù)的代價(jià),采用了融合Merkle 樹和Hash 桶的Bucket 樹[11]結(jié)構(gòu).

在本文中,我們首先對(duì)區(qū)塊鏈中Merkle 樹的結(jié)構(gòu)和關(guān)鍵操作進(jìn)行分析,從理論上對(duì)Merkle 樹的作用和復(fù)雜度進(jìn)行解析;然后根據(jù)分析結(jié)果提出相應(yīng)的性能評(píng)測(cè)指標(biāo),最后通過(guò)實(shí)驗(yàn)進(jìn)行驗(yàn)證和分析.

1 區(qū)塊鏈中的Merkle 樹結(jié)構(gòu)分析

1.1 傳統(tǒng)Merkle 樹結(jié)構(gòu)

在計(jì)算機(jī)科學(xué)與密碼學(xué)中,Merkle 樹是一種樹形數(shù)據(jù)結(jié)構(gòu).每個(gè)葉子節(jié)點(diǎn)均以數(shù)據(jù)塊的哈希值作為標(biāo)簽,而除了葉子節(jié)點(diǎn)之外的節(jié)點(diǎn)則以其子節(jié)點(diǎn)標(biāo)簽的加密哈希值作為標(biāo)簽.Merkle 樹可以實(shí)現(xiàn)快捷的數(shù)據(jù)驗(yàn)證,因此能夠高效地驗(yàn)證大型數(shù)據(jù)結(jié)構(gòu)的內(nèi)容[13].

如圖1所示,該圖表明了Merkle 樹的結(jié)構(gòu).Merkle樹可以被看成是Hash 表的推廣,即Hash 表其實(shí)是樹高為2 的Merkle 樹.其形成的過(guò)程主要為:

圖1 Merkle 樹結(jié)構(gòu)

(1)在Merkle 樹的最底層,將數(shù)據(jù)分成一個(gè)個(gè)小的數(shù)據(jù)塊,且各數(shù)據(jù)塊擁有對(duì)應(yīng)的Hash 值,作為葉子節(jié)點(diǎn);

(2)葉子節(jié)點(diǎn)到上層樹結(jié)構(gòu)時(shí),將相鄰的兩個(gè)Hash值合并成一個(gè)字符串,計(jì)算該字符串的Hash 值;

(3)每一層都重復(fù)過(guò)程(2),相鄰兩個(gè)Hash 值便可以一個(gè)子Hash 值.若最底層的Hash 總數(shù)為單數(shù),則直接對(duì)其做Hash 運(yùn)算.

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

1.2 區(qū)塊鏈中的Merkle 樹結(jié)構(gòu)

在以比特幣、以太坊和超級(jí)賬本為代表的主流區(qū)塊鏈系統(tǒng)中,在Merkle 上分別有著不同的設(shè)計(jì)與實(shí)現(xiàn).下面,我們將依次介紹這三種不同區(qū)塊鏈系統(tǒng)中Merkle 樹的結(jié)構(gòu).

(1) 比特幣的Merkle 樹

在比特幣系統(tǒng)中,區(qū)塊分為區(qū)塊頭和區(qū)塊體,其中區(qū)塊體則是由Merkle 樹構(gòu)成.其中,整個(gè)區(qū)塊的大小為2 M,區(qū)塊頭的大小固定為80 個(gè)字節(jié),因此,區(qū)塊體的大小占了整個(gè)區(qū)塊的96%.

比特幣的Merkle 結(jié)構(gòu)和傳統(tǒng)的Merkle 樹完全相同.如圖1所示,在比特幣中,Merkle 樹的葉子結(jié)點(diǎn)為系統(tǒng)中每一筆交易的Hash 值.不同交易利用Merkle樹的結(jié)構(gòu)進(jìn)行組合,最終生成比特幣的Merkle 樹,同時(shí)產(chǎn)生由所有交易產(chǎn)生的Merkle 根.

(2) 以太坊的Merkle 樹

在比特幣模型中,采用UTXO 模型表示數(shù)據(jù),因此采用傳統(tǒng)的Merkle 樹簡(jiǎn)單快捷[14];但是以以太坊為代表的第二代區(qū)塊鏈中,大多采用賬戶模型[15],此時(shí)傳統(tǒng)的Merkle 樹會(huì)帶來(lái)極大的存儲(chǔ)空間消耗,并且不易查詢.因此,在以太坊中,對(duì)Merkle 樹進(jìn)行改進(jìn),設(shè)計(jì)出一種新的數(shù)據(jù)結(jié)構(gòu)-Merkle Patricia 樹進(jìn)行數(shù)據(jù)存儲(chǔ).

Merkle Patricia 樹簡(jiǎn)稱MPT,其本質(zhì)上是先將前綴樹進(jìn)行改進(jìn),然后再和Merkle 樹進(jìn)行結(jié)合.

在原始的前綴樹中,存在空間浪費(fèi)、節(jié)點(diǎn)不易控制、深度長(zhǎng)等缺陷.MPT 在前綴樹的基礎(chǔ)上進(jìn)行了改進(jìn),主要做了以下幾個(gè)方面.

① 為了防止key 的長(zhǎng)度不同造成浪費(fèi),首先將所有的key 值進(jìn)行Hash,將所有的key 轉(zhuǎn)換成相同的長(zhǎng)度;

② 為了方便對(duì)節(jié)點(diǎn)的控制,將所有的節(jié)點(diǎn)分為空節(jié)點(diǎn)、分支節(jié)點(diǎn)、葉子節(jié)點(diǎn)和擴(kuò)展節(jié)點(diǎn)4 種不同的節(jié)點(diǎn),分別存儲(chǔ)不同的內(nèi)容;

③ 為了更好的進(jìn)行比較,將key 中的每個(gè)參數(shù)進(jìn)行hex 編碼.同時(shí)使用hex 編碼后,每個(gè)值大小為[0-15],可以使每個(gè)分支節(jié)點(diǎn)的容量都減小;

④ 為了縮短樹的深度,將連續(xù)兩個(gè)級(jí)以上的擴(kuò)展節(jié)點(diǎn)進(jìn)行合并.

通過(guò)如上4 步改進(jìn),傳統(tǒng)的前綴樹結(jié)構(gòu)如圖2所示.最后,將改進(jìn)后的前綴樹和Merkle 樹進(jìn)行結(jié)合,將存儲(chǔ)的value 值轉(zhuǎn)換成所有子節(jié)點(diǎn)的Hash 值,即可組成Merkle Patricia 樹.

圖2 改進(jìn)的前綴樹

(3) 超級(jí)賬本的Merkle 樹

超級(jí)賬本采用賬戶模型來(lái)進(jìn)行數(shù)據(jù)存儲(chǔ)[16],但是以太坊的MPT 樹結(jié)構(gòu)復(fù)雜、性能低,超級(jí)賬本則提出了Bucket 樹[17]進(jìn)行數(shù)據(jù)存儲(chǔ).

Bucket 樹其實(shí)是揉合了Merkle 樹與Hash 桶兩種數(shù)據(jù)結(jié)構(gòu)組合而成的,即Bucket 樹本質(zhì)上是一棵建立在Hash 表上的Merkle 樹.

如圖3所示,B1-B6 為數(shù)據(jù)的Hash 桶,每個(gè)桶中儲(chǔ)存若干被散列到該桶中的數(shù)據(jù)項(xiàng),所有數(shù)據(jù)項(xiàng)都按序排列.每一個(gè)桶有可以用一個(gè)Hash 值表示其狀態(tài),該Hash 值是桶內(nèi)所有數(shù)據(jù)項(xiàng)的內(nèi)容進(jìn)行Hash 計(jì)算所得.除底層的Hash 表之外,上層是一系列Merkle 樹節(jié)點(diǎn).一個(gè)Merkle 樹節(jié)點(diǎn)對(duì)應(yīng)下一層的n個(gè)Hash 桶或Merkle 節(jié)點(diǎn).Merkle 節(jié)點(diǎn)的Hash 值是根據(jù)這n個(gè)孩子節(jié)點(diǎn)的Hash 值計(jì)算所得.通過(guò)這種方式不斷計(jì)算,與Merkle 樹類似,最頂端的值即為整棵樹的Hash 值,即Merkle 根.由此可以生成完整的Bucket 樹.

圖3 Bucket 樹

2 區(qū)塊鏈中Merkle 關(guān)鍵操作分析

區(qū)塊鏈本質(zhì)上是一個(gè)去中心化的數(shù)據(jù)庫(kù),Merkle樹是區(qū)塊鏈中核心存儲(chǔ)的數(shù)據(jù).和傳統(tǒng)的數(shù)據(jù)庫(kù)相比,區(qū)塊鏈只能進(jìn)行增加和查詢的操作,而不能進(jìn)行刪除和修改.因此,Merkle 樹中核心的操作就是數(shù)據(jù)插入.同時(shí),Merkle 樹的一個(gè)重要作用是SPV 驗(yàn)證(實(shí)現(xiàn)簡(jiǎn)單支付驗(yàn)證),即Merkle 樹可以直接下載一個(gè)分支并立即驗(yàn)證.因此,在本文中,我們主要分析Merkle 樹中兩個(gè)核心的操作:插入數(shù)據(jù)和SPV 驗(yàn)證.

2.1 數(shù)據(jù)插入

數(shù)據(jù)插入是Merkle 樹中最為核心的操作,是實(shí)現(xiàn)區(qū)塊鏈系統(tǒng)中數(shù)據(jù)插入功能的底層.因此,理解不同區(qū)塊鏈系統(tǒng)中Merkle 樹的數(shù)據(jù)插入的原理,是理解不同區(qū)塊鏈系統(tǒng)性能瓶頸的重要途徑.

對(duì)于比特幣中的Merkle 樹,當(dāng)需要插入一個(gè)新的數(shù)據(jù)時(shí),通常在之前的Merkle 樹基礎(chǔ)上進(jìn)行插入.如圖4所示,如果插入數(shù)據(jù)L4,通常情況下只需要在之前的Mekle 的基礎(chǔ)上重新插入一條新的路徑,然后通過(guò)和之前的Merkle 樹中的節(jié)點(diǎn)進(jìn)行Hash 計(jì)算,即可產(chǎn)生新的Merkle 樹.

圖4 Merkle 樹的插入

對(duì)于以太坊中的MPT,其插入數(shù)據(jù)的過(guò)程相對(duì)比較復(fù)雜,其核心的思想為:按照key 的內(nèi)容,從根節(jié)點(diǎn)依次從上往下尋找相同長(zhǎng)度的路徑,同時(shí)隨時(shí)根據(jù)MPT 的性質(zhì)改變節(jié)點(diǎn)的性質(zhì),插入新的key 的值,直到key 遍歷結(jié)束.如圖5所示,該虛線路徑展現(xiàn)了鍵值對(duì)為＜‘1,2,2,4,5’,‘gen’＞的數(shù)據(jù)插入.

圖5 MPT 的插入

對(duì)于超級(jí)賬本中的Bucket 樹,當(dāng)插入新的數(shù)據(jù)時(shí),需要對(duì)進(jìn)行計(jì)算和合并兩個(gè)過(guò)程.

如圖6所示,在Bucket 樹中新插入兩條數(shù)據(jù)項(xiàng)Entry1,通常通過(guò)以下兩個(gè)步驟:

圖6 Bucket 樹插入數(shù)據(jù)

計(jì)算:經(jīng)過(guò)散列值計(jì)算,Entry1 應(yīng)該放到B2 中.

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

當(dāng)Hash 桶計(jì)算完成之后,便可進(jìn)行Merkle 節(jié)點(diǎn)的Hash 計(jì)算.該過(guò)程僅對(duì)需要改變的節(jié)點(diǎn)進(jìn)行Hash重計(jì)算.對(duì)沒(méi)有變化的孩子節(jié)點(diǎn)可直接使用歷史的Hash值.即需要重新計(jì)算Hash0-1,Hash0,Root 節(jié)點(diǎn).

2.2 SPV 驗(yàn)證

在比特幣中,Merkle 的主要作用是實(shí)現(xiàn)SPV 驗(yàn)證.SPV 驗(yàn)證全稱叫做簡(jiǎn)單支付驗(yàn)證,即區(qū)塊鏈中的SPV節(jié)點(diǎn)(輕型節(jié)點(diǎn))驗(yàn)證某個(gè)交易是否已經(jīng)在交易中,是區(qū)塊鏈系統(tǒng)可以在手機(jī)等移動(dòng)端運(yùn)行的關(guān)鍵.

在SPV 驗(yàn)證中,Merkle 主要完整交易的存在性檢查.其過(guò)程主要是

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

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

如圖7所示,SPV 節(jié)點(diǎn)驗(yàn)證交易L3 的存在性,只需要通過(guò)全節(jié)點(diǎn)獲取L3 的Merkle 分支,即＜Hash1-1,Hash0＞節(jié)點(diǎn),然后通過(guò)L3 與Merkle 分支的計(jì)算即可獲得Root,最后通過(guò)比較Root 和本地存儲(chǔ)的Merkle根是否相同判斷L3 是否已經(jīng)在區(qū)塊中[16].

圖7 SPV 驗(yàn)證過(guò)程

如上分析,使用Merkle 分支進(jìn)行存在性檢查,對(duì)于n 個(gè)交易來(lái)說(shuō),傳輸?shù)膮^(qū)塊數(shù)為log(n),可以大大較少數(shù)據(jù)傳輸?shù)臄?shù)量,降低網(wǎng)絡(luò)傳輸?shù)呢?fù)擔(dān).

對(duì)于以太坊來(lái)說(shuō),因?yàn)槠湓谇熬Y樹的基礎(chǔ)上集成了Merkle 樹,因此在其SPV 驗(yàn)證和比特幣系統(tǒng)相同:在SPV 節(jié)點(diǎn)中,也是主要存儲(chǔ)了Merkle 根,之后從鄰居的全節(jié)點(diǎn)獲取Merkle 分支,通過(guò)哈希計(jì)算查詢獲取Root,最后和本地存在的Merkle 根進(jìn)行比較以判斷交易的存在性.

對(duì)于超級(jí)賬本的Bucket 樹來(lái)說(shuō),由于其葉子結(jié)點(diǎn)為有序的哈希桶,哈希桶中存在大量的數(shù)據(jù).如果需要實(shí)現(xiàn)SPV 驗(yàn)證,其不僅僅需要傳輸Merkle 分支,同時(shí)需要傳輸Hash 桶中的其他元素,會(huì)大大增加傳輸數(shù)據(jù)的數(shù)量,增加網(wǎng)絡(luò)負(fù)擔(dān).因此,在超級(jí)賬本中很少有提及SPV 相關(guān)的操作.

2.3 性能總結(jié)

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

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

3 實(shí)驗(yàn)性能分析指標(biāo)設(shè)計(jì)

在之前的工作中,我們分析了Merkle 樹的結(jié)構(gòu)和兩大核心操作.因此,在實(shí)驗(yàn)中,我們主要從插入數(shù)據(jù)性能,數(shù)據(jù)存儲(chǔ)和SPV 驗(yàn)證性能3 個(gè)方面進(jìn)行相關(guān)的實(shí)驗(yàn),以驗(yàn)證之前的理論分析.為了更好的定量表現(xiàn)出相關(guān)性能,我們?cè)O(shè)計(jì)了相關(guān)的指標(biāo),分別體現(xiàn)出插入數(shù)據(jù),數(shù)據(jù)存儲(chǔ)和SPV 驗(yàn)證的相關(guān)性能.

3.1 構(gòu)建時(shí)間

首先考慮插入數(shù)據(jù)的時(shí)間開銷.對(duì)于一個(gè)相關(guān)的數(shù)據(jù)來(lái)說(shuō),插入數(shù)據(jù)的時(shí)間極短,其插入數(shù)據(jù)的時(shí)間開銷可能比程序代碼在其他地方運(yùn)行的時(shí)間更短,因此較難使用程序來(lái)統(tǒng)計(jì)一個(gè)數(shù)據(jù)的插入時(shí)間.但是,在區(qū)塊鏈系統(tǒng)中,構(gòu)建區(qū)塊的過(guò)程中存在非常重要的一步就是將交易池中的眾多交易進(jìn)行打包構(gòu)建成Merkle樹,其本質(zhì)上就是將交易池的數(shù)據(jù)一個(gè)個(gè)插入到Merkle樹中以構(gòu)成最終的Merkle 樹并存入?yún)^(qū)塊中.因此,在本實(shí)驗(yàn)中,我們采用統(tǒng)計(jì)不同規(guī)模數(shù)據(jù)集下Merkle 樹的構(gòu)建時(shí)間來(lái)進(jìn)一步的表現(xiàn)出不同Merkle 樹的插入性能.

3.2 節(jié)點(diǎn)數(shù)及樹的深度

其次,我們考慮不同Merkle 樹帶來(lái)的數(shù)據(jù)存儲(chǔ).目前區(qū)塊過(guò)大已經(jīng)是區(qū)塊鏈系統(tǒng)中十分關(guān)鍵的問(wèn)題,而Merkle 樹作為區(qū)塊中主要存儲(chǔ)的數(shù)據(jù),對(duì)比不同Merkle 樹的存儲(chǔ)性能對(duì)我們之后選擇不同的區(qū)塊鏈結(jié)構(gòu)是十分有必要的.

對(duì)于Merkle 樹來(lái)說(shuō),節(jié)點(diǎn)數(shù)目的大小會(huì)直接影響Merkle 樹的存儲(chǔ)大小:更多節(jié)點(diǎn)的Merkle 樹節(jié)點(diǎn)存儲(chǔ)規(guī)模顯然會(huì)更大.對(duì)于不同的Merkle 樹結(jié)構(gòu)來(lái)說(shuō),相同的數(shù)據(jù)在不同的Merkle 樹結(jié)構(gòu)上的節(jié)點(diǎn)數(shù)目和樹的深度是不同的.因此可以統(tǒng)計(jì)不同規(guī)模的數(shù)據(jù)在Merkle 樹上的節(jié)點(diǎn)數(shù)和深度來(lái)定量的表示在不同Merkle樹的存儲(chǔ)性能.

3.3 SPV 驗(yàn)證中Merkle 分支節(jié)點(diǎn)數(shù)

如第2 節(jié)所述,區(qū)塊鏈中的SPV 驗(yàn)證是Merkle 樹中的重要功能之一,因此檢測(cè)SPV 驗(yàn)證的相關(guān)性能也是對(duì)Merkle 樹性能分析的重要組成部分.

在進(jìn)行SPV 驗(yàn)證時(shí),主要關(guān)心兩個(gè)性能指標(biāo).首先是Merkle 分支的節(jié)點(diǎn)數(shù),該指標(biāo)會(huì)影響在網(wǎng)絡(luò)傳輸中的性能,太大的Merkle 分支會(huì)造成較大網(wǎng)絡(luò)傳輸?shù)呢?fù)擔(dān),嚴(yán)重影響網(wǎng)絡(luò)傳輸?shù)男阅?其次,Merkle 分支樹也會(huì)影響SPV 驗(yàn)證的時(shí)間性能,因?yàn)楦嗟腗erkle 分支節(jié)點(diǎn)就需要更多的重組Hash 運(yùn)算,影響做SPV 驗(yàn)證的時(shí)間效率.因此,在本實(shí)驗(yàn)分析中,我們只需要利用Merkle 分支的節(jié)點(diǎn)數(shù)目來(lái)分析對(duì)SPV 驗(yàn)證的網(wǎng)絡(luò)傳輸和時(shí)間的性能.

4 比較實(shí)驗(yàn)結(jié)果與分析

在本實(shí)驗(yàn)中,我們通過(guò)實(shí)驗(yàn)設(shè)計(jì),利用Merkle 樹的構(gòu)建時(shí)間、Merkle 樹的節(jié)點(diǎn)數(shù)、樹的深度和SPV驗(yàn)證的Merkle 分支節(jié)點(diǎn)數(shù)來(lái)進(jìn)一步分析和驗(yàn)證不同區(qū)塊鏈系統(tǒng)中Merkle 樹的相關(guān)性能.

4.1 實(shí)驗(yàn)設(shè)計(jì)

本文中,我們主要進(jìn)行分析和比較比特幣中的Merkle 樹,以太坊中Merkle Patricia 樹和超級(jí)賬本中的Bucket 樹.為了消除其他因素的影響而直接分析不同Merkle 的性能,我們利用統(tǒng)一的語(yǔ)言(Java)對(duì)3 種樹的結(jié)構(gòu)進(jìn)行實(shí)現(xiàn).

在數(shù)據(jù)方面,為了更好的適配MPT 結(jié)構(gòu),我們統(tǒng)一使用賬戶模型.如圖8所示,在本實(shí)驗(yàn)中,我們通過(guò)隨機(jī)產(chǎn)生的方式,生成了數(shù)量為1000、10 000、50 000和100 000 的鍵值對(duì).這些鍵值對(duì)的key 值不固定大小,其長(zhǎng)度從4 到20 不等;value 的值也不固定大小,長(zhǎng)度從6 到30 不等.

針對(duì)3 種Merkle 樹結(jié)構(gòu),具體的實(shí)驗(yàn)過(guò)程為:

在Merkle 樹的實(shí)驗(yàn)中,將key 和value 的值利用“--”字符串進(jìn)行合并,組成一個(gè)新的字符串.之后將新的字符串的Hash 值,作為Merkle 樹的葉子節(jié)點(diǎn).

在Merkle Patricia 樹的實(shí)驗(yàn)中,首先要對(duì)key 值進(jìn)行Hash 運(yùn)算,將key 編成16 字節(jié)的固定長(zhǎng)度.然后利用Hex 編碼進(jìn)行編碼,之后采用MPT 樹的相關(guān)算法實(shí)現(xiàn)完整的MPT 樹結(jié)構(gòu).

圖8 數(shù)據(jù)集格式

在Bucket 樹的實(shí)驗(yàn)中,確定100 個(gè)Hash 桶,每個(gè)節(jié)點(diǎn)最多有3 個(gè)子節(jié)點(diǎn).然后將所有的鍵值隨機(jī)分配到Hash 桶中,保證每個(gè)Hash 桶的鍵值對(duì)應(yīng)數(shù)目基本均勻,最后構(gòu)建Bucket 樹.

4.2 實(shí)驗(yàn)結(jié)果

在本實(shí)驗(yàn)中,我們首先對(duì)3 種不同Merkle 樹架構(gòu)的存儲(chǔ)進(jìn)行分析.如3.2 節(jié)所述,在Merkle 樹存儲(chǔ)分析時(shí),我們利用樹的規(guī)模作為反映存儲(chǔ)空間的指標(biāo).即利用樹的節(jié)點(diǎn)數(shù)和樹的深度來(lái)進(jìn)行表示.通過(guò)實(shí)驗(yàn),表2和表3表示在不同數(shù)據(jù)規(guī)模下3 種不同Merkle 樹結(jié)構(gòu)的節(jié)點(diǎn)數(shù)和深度.

表2 不同規(guī)模樹節(jié)點(diǎn)數(shù)比較(個(gè))

表3 不同規(guī)模樹深度比較

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

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

其次,如3.1 節(jié)所述,我們進(jìn)一步對(duì)3 種不同Merkle樹的構(gòu)建時(shí)間進(jìn)行分析.如表4所示,表明了3 種不同的Merkle 樹分別創(chuàng)建1000、10 000、50 000 和100 000組數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)所需的時(shí)間.

表4 不同規(guī)模樹創(chuàng)建時(shí)間比較(ms)

由表4可以看出,在相同規(guī)模的數(shù)據(jù)下,Merkle Patricia 樹的創(chuàng)建時(shí)間最多,遠(yuǎn)大于其他兩種Merkle 結(jié)構(gòu);Merkle 樹的創(chuàng)建時(shí)間居中,Bucket 樹的創(chuàng)建時(shí)間最短.

最后,我們需要評(píng)測(cè)3 種Merkle 樹在做SPV 驗(yàn)證.在實(shí)驗(yàn)中,我們分別取了3 種Merkle 樹的Merkle路徑,如表5所示.

表5 不同規(guī)模樹Merkle 分支(個(gè))

從表5可以看到,可以看到比特幣,以太坊和超級(jí)賬本在不同規(guī)模數(shù)據(jù)下的Merkle 路徑的長(zhǎng)度,相比之下3 種系統(tǒng)的規(guī)模有著明顯的差異.Merkle 樹的Merkle路徑所需要的節(jié)點(diǎn)最少,其次是MPT 樹.Bucket 樹我們采用和Merkle 樹相同SPV 驗(yàn)證的方法進(jìn)行統(tǒng)計(jì)Merkle路徑,所需要的Merkle 路徑總體來(lái)說(shuō)最長(zhǎng).

4.3 實(shí)驗(yàn)總結(jié)與分析

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

從樹的深度來(lái)看,MPT 樹最大,Merkle 其次,Bucket中樹的深度最小.從理論上分析,由于在生成MPT 樹的過(guò)程中,首先要將key 值Hash 運(yùn)算為16 的長(zhǎng)度,同時(shí)采用Hex 編碼,會(huì)擴(kuò)大樹的深度,因此MPT 應(yīng)該是一個(gè)非常狹長(zhǎng)的樹狀結(jié)構(gòu);但是由于key 的長(zhǎng)度一定,因此其深度永遠(yuǎn)不會(huì)進(jìn)行增長(zhǎng);而Merkle 樹的深度是數(shù)據(jù)個(gè)數(shù)的log(n),會(huì)隨著數(shù)據(jù)的增多而增加;Bucket樹中底層的Hash 桶數(shù)量不會(huì)發(fā)生改變,因此其樹的深度很小,同時(shí)其不會(huì)因?yàn)閿?shù)據(jù)規(guī)模的增加而改變.

從構(gòu)建時(shí)間來(lái)看,同樣是MPT 的構(gòu)造時(shí)間最長(zhǎng),Bucket 樹的構(gòu)造時(shí)間最短.出現(xiàn)這種情況是由其算法的特殊性導(dǎo)致的:首先,為了提高節(jié)點(diǎn)的查找效率和減少存儲(chǔ)空間浪費(fèi),MPT 樹對(duì)單獨(dú)存在的key 進(jìn)行了合并,這需要占用一定時(shí)間;其次,為避免樹中出現(xiàn)很長(zhǎng)的路徑并提高M(jìn)PT 樹的安全性,需要對(duì)每個(gè)key 求Hash 值,這一過(guò)程需要花費(fèi)大量時(shí)間.而Bucket 只需要進(jìn)行Hash 桶的排序和求Hash,上層的Merkle 樹的規(guī)模較小;而Merkle 樹只需要進(jìn)行結(jié)構(gòu)的構(gòu)建.因此,MPT 樹創(chuàng)建時(shí)間遠(yuǎn)大于其他兩種算法.

從SPV 來(lái)看,在3 種Merkle 樹中,比特幣中Merkle路徑最短,超級(jí)賬本最多,以太坊居中.其原因是因?yàn)楸忍貛藕统?jí)賬本中只需要獲取相應(yīng)的路徑上的節(jié)點(diǎn)即可,因此其Merkle 路徑的長(zhǎng)度應(yīng)該和對(duì)應(yīng)Merkle 樹的深度成正比;而Bucket 樹底層是對(duì)有序的Hash 桶求Hash,所以如果進(jìn)行SPV 驗(yàn)證即不僅僅需要傳遞路徑上的數(shù)據(jù),同時(shí)也需要Hash 桶中其他的數(shù)據(jù).因此,在三種區(qū)塊鏈結(jié)構(gòu)中,比特幣應(yīng)該最適合于在手機(jī)移動(dòng)端使用,超級(jí)賬本不適合在移動(dòng)端實(shí)現(xiàn).

5 結(jié)論與展望

在本文中,我們首先分析了比特幣,以太坊和超級(jí)賬本這3 種主流區(qū)塊鏈中Merkle 樹的相關(guān)結(jié)構(gòu)和核心操作,同時(shí)根據(jù)Merkle 樹的作用和特性,提出了相應(yīng)的性能指標(biāo).然后利用統(tǒng)一的語(yǔ)言進(jìn)行了實(shí)現(xiàn),并進(jìn)行了相關(guān)性能指標(biāo)的檢測(cè).實(shí)驗(yàn)結(jié)果表明,比特幣的Merkle 樹結(jié)構(gòu)會(huì)造成更多的存儲(chǔ)消耗,以太坊的MPT結(jié)構(gòu)會(huì)造成更多的時(shí)間消耗,超級(jí)賬本的Bucket 樹SPV 驗(yàn)證最難.本文的操作分析和實(shí)驗(yàn)環(huán)境為我們接下來(lái)的工作也奠定了基礎(chǔ),接下來(lái)我們將針對(duì)Merkle樹的特性和不足,希望提出新的Merkle 樹結(jié)構(gòu),在插入時(shí)間、存儲(chǔ)或者SPV 的驗(yàn)證上取得更好的發(fā)展.