存儲容量可擴展區(qū)塊鏈系統(tǒng)的高效查詢模型*

賈大宇,信俊昌,2,王之瓊,郭 薇,王國仁

1(東北大學(xué) 計算機科學(xué)與工程學(xué)院,遼寧 沈陽 110819)

2(遼寧省大數(shù)據(jù)管理與分析重點實驗室,遼寧 沈陽 110819)

3(東北大學(xué) 中荷生物醫(yī)學(xué)與信息工程學(xué)院,遼寧 沈陽 110819)

4(沈陽航空航天大學(xué) 計算機學(xué)院,遼寧 沈陽 110136)

5(北京理工大學(xué) 計算機學(xué)院,北京 100081)

通訊作者:信俊昌,E-mail:xinjunchang@mail.neu.edu.cn

區(qū)塊鏈技術(shù)起源于2008 年化名為“中本聰”(Satoshi nakamoto)的學(xué)者在密碼學(xué)郵件組發(fā)表的奠基性論文《比特幣:一種點對點電子現(xiàn)金系統(tǒng)》[1].區(qū)塊鏈技術(shù)具有去中心化、透明性、開放性、自治性、匿名性和信息不可篡改等特點[2],被認(rèn)為是繼大型機、個人電腦、互聯(lián)網(wǎng)、移動社交網(wǎng)絡(luò)之后,計算范式的第5 次顛覆式創(chuàng)新,是人類信用進(jìn)化史上繼血親信用、貴金屬信用、央行紙幣信用之后的第4 個里程碑[3].區(qū)塊鏈技術(shù)為解決中心化機構(gòu)普遍存在的高成本、低效率和數(shù)據(jù)存儲不安全等問題提供了解決方案[4].

但目前存在儲存擴展性較差的問題,以迄今為止最為成功的區(qū)塊鏈應(yīng)用場景比特幣為例,截至2018 年5 月6 日,產(chǎn)生了521 534個區(qū)塊[5]、17 019 個比特幣,總?cè)萘繛?74.34GB.截至2017 年5 月7 日,鏈上已認(rèn)證地址9 892 723 個[6],并且經(jīng)過一年多大家對比特幣關(guān)注度的增加,已認(rèn)證地址數(shù)量大幅提升.在區(qū)塊鏈系統(tǒng)中,節(jié)點有效保證區(qū)塊鏈數(shù)據(jù)安全的方法是作為完全節(jié)點保存完整的區(qū)塊鏈數(shù)據(jù).如果目前比特幣系統(tǒng)中所有節(jié)點都作為完全節(jié)點,那么近1 000 萬個節(jié)點各自提供近200GB 的磁盤空間來儲存區(qū)塊鏈數(shù)據(jù),整個系統(tǒng)將占用約2 000PB 的存儲容量保存200GB 左右的數(shù)據(jù),這極大地浪費了存儲空間.在未來,區(qū)塊鏈技術(shù)將會被大規(guī)模地應(yīng)用,預(yù)計到2027 年,全球10%的GDP 將會通過區(qū)塊鏈技術(shù)存儲[7].隨著區(qū)塊鏈容量的不斷增加,參與節(jié)點的存儲容量將逐漸不能滿足其存儲空間要求,這些不能滿足要求的節(jié)點就不能繼續(xù)作為完全節(jié)點保留在系統(tǒng)中.隨著系統(tǒng)中完全節(jié)點數(shù)量的減少,對區(qū)塊鏈系統(tǒng)的安全性必將產(chǎn)生影響,如:基于工作量證明(proof of work,簡稱POW)[8]機制的區(qū)塊鏈系統(tǒng)的總算力就會下降;基于股權(quán)證明(proof of stake,簡稱POS)[9]機制系統(tǒng)中的股權(quán)容易集中;基于委任權(quán)益證明(delegated proof of stake,簡稱DPOS)[10]機制的區(qū)塊鏈系統(tǒng)更容易被少數(shù)節(jié)點控制等.同時,如果不具備足夠存儲空間的節(jié)點不能加入到區(qū)塊鏈系統(tǒng)中,區(qū)塊鏈的可擴展性也會降低.因此,區(qū)塊鏈具有良好的存儲容量可擴展性是非常重要的.

目前,對于區(qū)塊鏈存儲容量可擴展性的研究不是很多,文獻(xiàn)[11]提出了名為ElasticChain 的區(qū)塊鏈模型,該模型在有效保證數(shù)據(jù)安全的前提下,增加了區(qū)塊鏈的存儲容量.但是在原有的區(qū)塊鏈模型中,全節(jié)點保存著完整的區(qū)塊鏈數(shù)據(jù),在查詢數(shù)據(jù)時,全節(jié)點只需要在本地磁盤進(jìn)行查找操作.而ElasticChain 模型在增加存儲容量之后,模型中的大部分節(jié)點沒有保存全部的區(qū)塊鏈數(shù)據(jù),所以當(dāng)一個節(jié)點發(fā)起查詢操作后,它將訪問系統(tǒng)中其他大量節(jié)點,遍歷一條完整的區(qū)塊數(shù)據(jù).因此,ElasticChain 模型與原區(qū)塊鏈模型相比,數(shù)據(jù)的查詢效率明顯降低.同時,由于ElasticChain 模型在查詢時數(shù)據(jù)來自不同節(jié)點,系統(tǒng)中也存在一些惡意節(jié)點返回的虛假數(shù)據(jù)的現(xiàn)象,這也給數(shù)據(jù)查詢的準(zhǔn)確度和數(shù)據(jù)的安全造成一定的影響.隨著區(qū)塊鏈技術(shù)的廣泛應(yīng)用,人們對區(qū)塊鏈中數(shù)據(jù)查找速度和準(zhǔn)確度的要求會越來越高,沒有有效的數(shù)據(jù)查詢方法,將會對未來區(qū)塊鏈技術(shù)的廣泛應(yīng)用帶來巨大限制.

因此,本文在ElasticChain 模型基礎(chǔ)上提出一種新的容量可擴展區(qū)塊鏈系統(tǒng)的高效查詢方法——ElasticQM(elastic query model).ElasticQM 的框架共有4 層,分別是用戶層、查詢層、存儲層和數(shù)據(jù)層.

· 在用戶層中,包括了數(shù)據(jù)緩存、數(shù)據(jù)驗證和數(shù)據(jù)同步等模塊:數(shù)據(jù)同步模塊保證了數(shù)據(jù)的時效性;數(shù)據(jù)緩存模塊將查詢過的數(shù)據(jù)緩存在本地磁盤中,增加再次查詢該數(shù)據(jù)的查詢速度;

· 在查詢層中,ElasticQM 結(jié)合了P2P 網(wǎng)絡(luò)超級節(jié)點查找技術(shù),提出了容量可擴展區(qū)塊鏈模型的全局查詢優(yōu)化算法.通過建立具有高可靠性和高穩(wěn)定性的查詢超級節(jié)點,在模型響應(yīng)數(shù)據(jù)查詢請求時,優(yōu)先訪問查詢超級節(jié)點,在保證數(shù)據(jù)安全的前提下,提高了數(shù)據(jù)查詢效率;

· 在存儲層中,模型采用基于ElasticChain 的區(qū)塊鏈模型,保證了區(qū)塊鏈數(shù)據(jù)的容量可擴展性;

· 在數(shù)據(jù)層中,我們提出了B-M tree 的數(shù)據(jù)存儲結(jié)構(gòu).該存儲結(jié)構(gòu)結(jié)合了平衡二叉樹(balanced binary tree)[12]和梅克爾樹(Merkle tree)[13]的各種特點,在保證區(qū)塊數(shù)據(jù)驗證速度的同時,提高了每個區(qū)塊內(nèi)的局部查詢速度,并使區(qū)塊鏈支持?jǐn)?shù)據(jù)范圍查詢.

本文的主要貢獻(xiàn)如下.

(1)提出了一種區(qū)塊鏈存儲容量可擴展模型的高效查詢方法——ElasticQM.此查詢模型由用戶層、查詢層、存儲層和數(shù)據(jù)層共4 層模塊組成;

(2)在ElasticQM 查詢層,提出了一種容量可擴展區(qū)塊鏈模型的全局查詢優(yōu)化算法,增加了查詢超級節(jié)點、查詢驗證節(jié)點和查詢?nèi)~子節(jié)點這3 種模型中的角色,提高了查詢效率;

(3)在ElasticQM 數(shù)據(jù)層,提出了一種基于B-M 樹的區(qū)塊鏈存儲結(jié)構(gòu),并給出了B-M 樹的建立算法和基于B-M 樹的查找算法.區(qū)塊鏈基于B-M 樹的存儲結(jié)構(gòu),會在區(qū)塊鏈進(jìn)行的塊內(nèi)局部查找時,提高區(qū)塊鏈的查詢速度;

(4)通過在不同節(jié)點可擴展區(qū)塊鏈中對不同數(shù)據(jù)量區(qū)塊進(jìn)行的查詢實驗結(jié)果表明,ElasticQM 查詢方法具有高效的查詢效率.

1 相關(guān)工作

近年來,對于區(qū)塊鏈技術(shù)的研究越來越受到人們關(guān)注.首先,在提高區(qū)塊鏈中數(shù)據(jù)查詢效率方面,文獻(xiàn)[14]開發(fā)了基于Ethereum 的高效查詢層EtherQL.EtherQL 會自動同步區(qū)塊鏈系統(tǒng)中新的區(qū)塊數(shù)據(jù),并將其存儲在專用數(shù)據(jù)庫中,以確保查詢準(zhǔn)確性和高效性.同時,EtherQL 提供了比其他區(qū)塊鏈應(yīng)用系統(tǒng)更高效、更靈活的數(shù)據(jù)查詢接口,并且支持對區(qū)塊鏈數(shù)據(jù)的范圍查詢和top-k查詢.在區(qū)塊鏈系統(tǒng)性能評價方面,文獻(xiàn)[15]首次提出了區(qū)塊鏈應(yīng)用的評價框架——Blockbench.文獻(xiàn)中,Blockbench 在Hyperledger Fabric 和以太坊的兩個客戶端(Parity 和Geth)這3 個區(qū)塊鏈私有鏈平臺上,評價了每個平臺在吞吐量、延遲、可擴展性和容錯方面的性能,并做了詳細(xì)的比較和分析.并且,區(qū)塊鏈技術(shù)在未來也是計算機、數(shù)據(jù)庫領(lǐng)域的研究熱點.文獻(xiàn)[16]通過查閱大量區(qū)塊鏈系統(tǒng)的框架和應(yīng)用情況,分析出未來在區(qū)塊鏈數(shù)據(jù)管理和分析方面的主要研究方向:區(qū)塊鏈充分利用現(xiàn)有成熟的數(shù)據(jù)和信息系統(tǒng)的方法、增強區(qū)塊鏈數(shù)據(jù)安全性和隱私性的有效方法、在區(qū)塊鏈上和區(qū)塊鏈下的數(shù)據(jù)分析方法和如何使基于區(qū)塊鏈的系統(tǒng)更加活躍和智能.

其次,在保證區(qū)塊鏈數(shù)據(jù)安全性方面,文獻(xiàn)[17]提出了基于股權(quán)證明(POS)的區(qū)塊鏈協(xié)議Ouroboros Praos.該協(xié)議通過設(shè)置安全的數(shù)字簽名和一種新型可驗證隨機函數(shù),來保證在半同步狀態(tài)下區(qū)塊鏈的安全性.文獻(xiàn)開發(fā)了一個通用的基于新協(xié)議的區(qū)塊鏈模型,并通過建立隨機預(yù)言機模型進(jìn)行模擬實驗,驗證了新協(xié)議的高安全性.文獻(xiàn)[18]提出ForkBase 數(shù)據(jù)庫存儲引擎,ForkBase 解決了在數(shù)據(jù)容易產(chǎn)生分叉或分歧的系統(tǒng)中出現(xiàn)的多版本、交叉語義和惡意篡改攻擊等問題.同時,文獻(xiàn)提出了名為POS-Tree 的管理大型數(shù)據(jù)對象的索引結(jié)構(gòu),減少了系統(tǒng)的存儲開銷.文獻(xiàn)評估了ForkBase 與區(qū)塊鏈平臺、wiki 服務(wù)和一個協(xié)作分析應(yīng)用軟件OrpheusDB 等3 個具有代表性的復(fù)雜應(yīng)用各自的性能,展示了Fork-Base 的可用性和高效性.文獻(xiàn)[19]分析了比特幣以外的區(qū)塊鏈的安全性和網(wǎng)絡(luò)可靠性,分析發(fā)現(xiàn),Namecoin 區(qū)塊鏈系統(tǒng)中擁有單個礦工在數(shù)月里的計算能力超過全網(wǎng)的51%,這是區(qū)塊鏈系統(tǒng)中非常嚴(yán)重的安全隱患.因此,文獻(xiàn)提出了開源軟件Blockstack,在Blockstack 框架中設(shè)計了4 層架構(gòu)——區(qū)塊鏈層、虛擬層、路由層和數(shù)據(jù)存儲層,避免了Namecoin 區(qū)塊鏈系統(tǒng)檢測出來的安全問題.文獻(xiàn)[20]提出了量化框架來分析基于PoW 共識機制的區(qū)塊鏈系統(tǒng)在不同網(wǎng)絡(luò)參數(shù)下的安全性.框架分析了區(qū)塊鏈系統(tǒng)在實際應(yīng)用中存在的網(wǎng)絡(luò)傳播、不同區(qū)塊大小、區(qū)塊生成時間間隔、信息傳播機制以及日食攻擊(eclipse attacks)等影響系統(tǒng)安全性的約束.設(shè)計了應(yīng)對雙重支付(double-spending)和自私挖掘(selfish mining)的最優(yōu)對抗策略.

2 預(yù)備知識和問題定義

2.1 區(qū)塊鏈的區(qū)塊結(jié)構(gòu)和查詢方法

目前,區(qū)塊鏈應(yīng)用的主要模型架構(gòu)基于中本聰?shù)恼撐腫1],如圖1 所示,在每個區(qū)塊中,存儲了版本號、上一個區(qū)塊的哈希值、本區(qū)塊產(chǎn)生的隨機數(shù)、時間戳、難度值和由交易信息生成的Merkle 樹的根.

· 版本號也是該區(qū)塊的區(qū)塊號;

· 上一個區(qū)塊的哈希值是上一個剛剛生成區(qū)塊的區(qū)塊頭通過SHA256 算法生成的哈希值,并填入到當(dāng)前區(qū)塊中;

· 本區(qū)塊產(chǎn)生的隨機數(shù)是在區(qū)塊鏈工作量證明機制下,區(qū)塊鏈各個節(jié)點根據(jù)上一個區(qū)塊的哈希值,并通過反復(fù)嘗試來找到的符合設(shè)定哈希函數(shù)的隨機數(shù);

· 時間戳記錄了該區(qū)塊產(chǎn)生的時間,標(biāo)識了該區(qū)塊的唯一性;

· 難度值會根據(jù)之前一段時間區(qū)塊的平均生成時間進(jìn)行調(diào)整,以應(yīng)對整個網(wǎng)絡(luò)不斷變化的整體計算總量,如果計算總量增長了,則系統(tǒng)會調(diào)高數(shù)學(xué)題的難度值,使得預(yù)期完成下一個區(qū)塊的時間依然在一定時間內(nèi);

· Merkle 樹的根是由區(qū)塊主體中所有交易的哈希值再逐級兩兩哈希計算出來的數(shù)值,主要用于快速檢驗一筆交易是否在這個區(qū)塊中存在[13].當(dāng)系統(tǒng)驗證區(qū)塊鏈中是否包含某筆交易時,只需要一個交易哈希,一個Merkle 樹根哈希和一個Merkle 路徑,實現(xiàn)了區(qū)塊鏈的簡易支付驗證(simplified payment verification,簡稱SPV)[21].

Fig.1 Structure of blocks圖1 區(qū)塊結(jié)構(gòu)

因為在區(qū)塊鏈的機制中,要求每個完全節(jié)點必須存儲一個區(qū)塊鏈的完整副本.當(dāng)查詢其中一條交易信息時,會在本地完整的區(qū)塊鏈副本中進(jìn)行遍歷查詢.但隨著越來越多的人使用區(qū)塊鏈系統(tǒng),不太可能每個人都去運行全節(jié)點,一部分區(qū)塊鏈的用戶會選擇使用輕量級錢包.輕量級錢包不會保存區(qū)塊鏈的數(shù)據(jù),當(dāng)其發(fā)起查詢請求時,需將查詢請求發(fā)送到相鄰全節(jié)點,在全節(jié)點中進(jìn)行查詢操作,并將查詢結(jié)果返回給輕量級節(jié)點.

2.2 區(qū)塊鏈存儲容量可擴展模型的結(jié)構(gòu)和查詢方法

目前,對于增加區(qū)塊鏈可擴展性的研究還不是很多.文獻(xiàn)[11]提出了區(qū)塊鏈存儲容量可擴展模型ElasticChain,將一條完整的區(qū)塊鏈副本進(jìn)行分片處理,并將分片數(shù)據(jù)保存在一定比例的節(jié)點中,提升了區(qū)塊鏈的存儲容量.ElasticChain 模型首先采用了區(qū)塊鏈數(shù)據(jù)副本分片策略,計算出了安全、合適的每個分片大小和分片被存儲的副本數(shù).然后,ElasticChain 模型增加了驗證節(jié)點對存儲數(shù)據(jù)的節(jié)點進(jìn)行基于POR(數(shù)據(jù)可檢索性證明)方法的實時檢測,并記錄更新存儲節(jié)點穩(wěn)定性值,依此選擇高穩(wěn)定性節(jié)點來儲存新產(chǎn)生的數(shù)據(jù)副本,提高了數(shù)據(jù)存儲的穩(wěn)定性.

如圖2 所示,ElasticChain 模型包括了用戶節(jié)點、儲存節(jié)點和驗證節(jié)點.用戶節(jié)點是原始數(shù)據(jù)擁有者,儲存節(jié)點是副本的保存者,而驗證節(jié)點是儲存節(jié)點穩(wěn)定性的驗證者.一個節(jié)點可以同時具備兩種或者3 種角色.當(dāng)用戶節(jié)點查詢區(qū)塊鏈數(shù)據(jù)時,需要首先訪問保存本地的P 鏈(P 鏈存儲區(qū)塊鏈數(shù)據(jù)分片存儲的位置),查找到分片數(shù)據(jù)保存的相應(yīng)存儲節(jié)點.然后訪問存儲節(jié)點,將每個分片數(shù)據(jù)逐一返回到用戶節(jié)點.最后才能在返回數(shù)據(jù)中進(jìn)行查詢操作.

Fig.2 Structure of ElasticChain model圖2 ElasticChain 模型架構(gòu)

2.3 問題定義

令S表示包含n個區(qū)塊的一條完整的區(qū)塊鏈數(shù)據(jù)集合,即S={B1,B2,...,Bn}.并且每一個區(qū)塊B被表示為元組B=〈H,K〉,其中,H表示區(qū)塊B的區(qū)塊頭信息;K表示區(qū)塊B中的交易數(shù)據(jù),交易數(shù)據(jù)K是由m個交易組成的集合,即K={T1,T2,...,Tm}.每一個交易T被表示為一個元組T=〈V,O,N,R,E〉,其中,V表示此時交易T的版本號,O表示交易T發(fā)起者的地址,N表示交易的數(shù)額,R表示交易T接收方公鑰的哈希,E表示交易的其他信息.一個區(qū)塊中第i個交易可以表示為Ti=〈Vi,Oi,Ni,Ri,Ei〉.

本文要解決的問題是,當(dāng)區(qū)塊鏈S存儲在區(qū)塊鏈存儲容量可擴展模型中,進(jìn)行基于交易發(fā)起者的地址O、交易的數(shù)額N、交易接收方地址R的條件查詢查詢時,提高其查詢速度.在本文中,以對地址為Oi的節(jié)點所發(fā)起的所有交易進(jìn)行查詢操作為例進(jìn)行闡述說明.

3 ElasticQM 查詢模型總覽

基于ElasticChain 區(qū)塊鏈存儲容量可擴展模型,我們提出了在擴展模型上的高效查詢方法——ElasticQM.ElasticQM 查詢模型一共由4 層模塊組成,分別是用戶層、查詢層、存儲層和數(shù)據(jù)層.ElasticQM 模型架構(gòu)如圖3所示.

· 用戶在發(fā)起查詢請求后首先訪問用戶層,在用戶層的緩存數(shù)據(jù)中進(jìn)行查找:如果找到了相應(yīng)數(shù)據(jù),則停止查找,返回查詢結(jié)果;如果沒有在用戶層緩存中找到查詢結(jié)果,則訪問模型查詢層;

· ElasticQM 查詢層會根據(jù)容量可擴展區(qū)塊鏈模型的全局查詢優(yōu)化算法找到查找到數(shù)據(jù)所在區(qū)塊;

· ElasticQM 的存儲層則是可擴展區(qū)塊鏈的基于ElasticChain 的區(qū)塊存儲方式,實現(xiàn)了區(qū)塊鏈數(shù)據(jù)的存儲可擴展性;

· 最后,ElasticQM 在數(shù)據(jù)層提出了基于B-M tree 的區(qū)塊數(shù)據(jù)存儲方式,提高了區(qū)塊鏈塊內(nèi)查找效率.

在ElasticQM 模型中,區(qū)塊鏈系統(tǒng)既實現(xiàn)了存儲容量的可擴展性,又在不影響區(qū)塊鏈去中心化特性和安全性的前提下,實現(xiàn)了區(qū)塊鏈數(shù)據(jù)的全局和局部的快速查詢.

Fig.3 Structure of ElasticQM modle圖3 ElasticQM 模型架構(gòu)

4 ElasticQM 查詢模型設(shè)計細(xì)節(jié)

用戶通過ElasticQM 查詢模型4 層模塊的處理,快速得到查詢結(jié)果.

· 首先,在ElasticQM 查詢層中,用戶在執(zhí)行查詢操作后,ElasticQM 會與區(qū)塊鏈數(shù)據(jù)實時同步,并經(jīng)過數(shù)據(jù)驗證緩存在支持SQL 查詢的數(shù)據(jù)庫中,第4.1 節(jié)將具體描述數(shù)據(jù)查詢過程;

· 然后,在ElasticQM 查詢層中,結(jié)合P2P 網(wǎng)絡(luò)超級節(jié)點查找技術(shù),提出了容量可擴展區(qū)塊鏈模型的全局查詢優(yōu)化算法.在算法中,將區(qū)塊鏈節(jié)點分為了查詢超級節(jié)點、查詢?nèi)~子節(jié)點和驗證節(jié)點,葉子節(jié)點在查詢數(shù)據(jù)時會優(yōu)先訪問查詢超級節(jié)點,并將返回數(shù)據(jù)進(jìn)行區(qū)塊安全檢驗和數(shù)據(jù)未被篡改檢驗.模型中的驗證節(jié)點實時記錄節(jié)點的穩(wěn)定性,來確定是否可以作為超級查詢節(jié)點.查詢操作詳情可以在第4.2 節(jié)看到;

· 其次,在ElasticQM 存儲層中,基本采用了文獻(xiàn)[11]中ElasticChain 模型的數(shù)據(jù)存儲方法,實現(xiàn)了區(qū)塊鏈的容量可擴展存儲.但在ElasticChain 模型的節(jié)點可靠性驗證部分進(jìn)行了改進(jìn).模型中,用戶節(jié)點不再存儲保存著分片存儲路徑的P 鏈,減少了ElasticChain 模型的存儲空間,存儲過程在第4.3 節(jié)詳細(xì)描述;

· 最后,在ElasticQM 數(shù)據(jù)層中,為了能高效查詢區(qū)塊鏈數(shù)據(jù)中一個區(qū)塊內(nèi)的某一條數(shù)據(jù),我們將區(qū)塊里的數(shù)據(jù)保存在了B-M tree 中,提高了每個區(qū)塊內(nèi)的局部查詢速度.相關(guān)存儲過程在第4.4 節(jié)描述.

4.1 用戶層

在ElasticQM用戶層中,當(dāng)一個節(jié)點發(fā)起查詢請求后,會首先訪問ElasticQM用戶層緩存數(shù)據(jù):如果節(jié)點找到相應(yīng)數(shù)據(jù),則停止查找,返回查詢結(jié)果;如果節(jié)點沒有在用戶層中找到查詢結(jié)果,則訪問模型ElasticQM 查詢層進(jìn)行查找操作.

因此,ElasticQM 在用戶層中設(shè)計了數(shù)據(jù)同步、安全檢測、數(shù)據(jù)處理和數(shù)據(jù)緩存這4 個模塊.數(shù)據(jù)緩存模塊的作用是:當(dāng)用戶層在每個節(jié)點成功完成一次查詢之后,將查詢結(jié)果緩存在用戶層緩存模塊中.用戶層緩存模塊是一個持SQL 查詢的數(shù)據(jù)庫,因此在下一次查詢相同數(shù)據(jù)時,ElasticQM 就可以在SQL 數(shù)據(jù)庫中進(jìn)行查找,增加了查詢速度.但是,區(qū)塊鏈數(shù)據(jù)每時每刻都在不斷地更新和變化,這就需要緩存模塊的數(shù)據(jù)也隨這不斷更新.用戶層中的數(shù)據(jù)同步模塊就會在每經(jīng)過一個相同的時間段,對數(shù)據(jù)緩存模塊中的數(shù)據(jù)與區(qū)塊鏈中數(shù)據(jù)進(jìn)行實時的同步和更新.在數(shù)據(jù)更新過程中,用戶層的安全檢查模塊會對新增數(shù)據(jù)進(jìn)行安全檢驗,保證數(shù)據(jù)的真實性.通過安全檢測模塊的數(shù)據(jù),才能被保存在數(shù)據(jù)緩存模塊中.而數(shù)據(jù)處理模塊則是在用戶層經(jīng)過數(shù)據(jù)同步和數(shù)據(jù)安全檢測后,將區(qū)塊鏈數(shù)據(jù)處理成可以保存在SQL 數(shù)據(jù)庫中的形式.例如在比特幣交易系統(tǒng)中,將進(jìn)行比特幣交易的買方地址、賣方地址和交易數(shù)量以表格的形式分別存入數(shù)據(jù)緩存模塊,加快下次查找速度.

4.2 查詢層

ElasticQM 的查詢層模塊接收模型用戶層發(fā)送的查詢請求,再根據(jù)查詢層中的查詢算法,在模型的存儲層快速找到相應(yīng)的數(shù)據(jù)返回給用戶層.在ElasticQM 查詢層中,我們提出了基于容量可擴展區(qū)塊鏈模型的全局查詢優(yōu)化算法.該算法結(jié)合了P2P 網(wǎng)絡(luò)中基于Super-peer 的分布式拓?fù)浣Y(jié)構(gòu),將可擴展區(qū)塊鏈模型中的節(jié)點分為了查詢超級節(jié)點、查詢?nèi)~子節(jié)點和查詢驗證節(jié)點,查詢層結(jié)構(gòu)如圖4 所示.

Fig.4 Architecture of query layer in ElasticQM圖4 ElasticQM 查詢層架構(gòu)

模型中,查詢超級節(jié)點上存儲了系統(tǒng)中相鄰葉子結(jié)點的信息和超級節(jié)點間的路由信息.當(dāng)進(jìn)行查詢操作時,發(fā)現(xiàn)算法僅在查詢超級結(jié)點之間轉(zhuǎn)發(fā),超級結(jié)點再將查詢請求轉(zhuǎn)發(fā)給適當(dāng)?shù)娜~子結(jié)點.模型中,查詢?nèi)~子節(jié)點至少保存著區(qū)塊鏈每個區(qū)塊的區(qū)塊頭數(shù)據(jù),來驗證收到的查詢數(shù)據(jù)是否被篡改,這個與比特幣錢包中的輕量級錢包相似.同時,查詢?nèi)~子節(jié)點保存著相鄰查詢超級節(jié)點位置,在查詢數(shù)據(jù)時,如果本地沒有完整的區(qū)塊鏈數(shù)據(jù),則會優(yōu)先訪問網(wǎng)絡(luò)中查詢超級節(jié)點.每一個新加入?yún)^(qū)塊鏈系統(tǒng)的節(jié)點,都會先被視為查詢?nèi)~子節(jié)點.查詢驗證節(jié)點和區(qū)塊中每個查詢超級節(jié)點和活躍的查詢?nèi)~子節(jié)點相連,實時記錄相連節(jié)點的可靠性.

查詢驗證節(jié)點會根據(jù)記錄的查詢超級節(jié)點是否出現(xiàn)惡意篡改區(qū)塊鏈數(shù)據(jù)來判斷超級節(jié)點的安全性,根據(jù)記錄的查詢超級節(jié)點在線時間和工作量得出超級節(jié)點的穩(wěn)定性,根據(jù)記錄的查詢超級節(jié)點工作速度得到超級節(jié)點的處理能力.超級節(jié)點的工作量和工作速度通過查詢?nèi)~子節(jié)點實時向驗證節(jié)點反饋,查詢驗證節(jié)點會根據(jù)查詢超級節(jié)點的安全性、穩(wěn)定性和處理能力決定其是否繼續(xù)作為查詢超級節(jié)點.同時,查詢驗證節(jié)點還會實時檢查整個區(qū)塊鏈數(shù)據(jù),對于在區(qū)塊鏈上操作較多的活躍的查詢?nèi)~子節(jié)點,驗證節(jié)點也會記錄其節(jié)點的可靠性,作為查詢超級的候補節(jié)點.

ElasticQM 查詢層采用了容量可擴展區(qū)塊鏈模型的全局查詢優(yōu)化算法,如圖5 所示.當(dāng)一個節(jié)點收到查詢請求時,節(jié)點首先判斷自身是否為查詢超級節(jié)點:如果該節(jié)點不為查詢超級節(jié)點,則會訪問距離最近的查詢超級節(jié)點,然后,該超級節(jié)點根據(jù)本地保存路由信息,找到接近查找目標(biāo)的超級節(jié)點;如果該節(jié)點為查詢超級節(jié)點,則直接訪問本地路由信息,找到接近查找目標(biāo)的超級節(jié)點.接著,由這個接近查找目標(biāo)的超級節(jié)點找到與它相連的保存著需要查找的數(shù)據(jù)的葉子節(jié)點,將查詢結(jié)果同查詢結(jié)果所在的區(qū)塊和與之相連的其他區(qū)塊的區(qū)塊頭作為最終查詢結(jié)果.最后,將最終查詢結(jié)果按查找時的相同路徑返回給發(fā)送查詢請求的節(jié)點.當(dāng)最初送查詢請求的節(jié)點收到了查詢數(shù)據(jù)后,首先要通過本地保存的區(qū)塊鏈的區(qū)塊頭數(shù)據(jù)與返回數(shù)據(jù)做對比,檢驗查詢結(jié)果所在的區(qū)塊鏈沒有在查詢過程中被篡改過.然后,查詢發(fā)起節(jié)點通過對查詢結(jié)果的哈希值與查詢結(jié)果所在區(qū)塊的區(qū)塊頭哈希值進(jìn)行校驗,檢驗查詢結(jié)果是在其區(qū)塊中的真實數(shù)據(jù),未被惡意篡改.查詢發(fā)起節(jié)點會將檢驗結(jié)果返回給驗證節(jié)點,使驗證節(jié)點能夠?qū)崟r地監(jiān)督查詢路徑上的超級節(jié)點和葉子節(jié)點的可靠性程度.如果出現(xiàn)某一節(jié)點惡意篡改數(shù)據(jù)的情況,驗證節(jié)點則會減少該節(jié)點的可靠性值;如果數(shù)據(jù)查詢結(jié)果正常,則增加路徑上所有節(jié)點的可靠性值.可靠值低的節(jié)點將不能繼續(xù)作為查找超級節(jié)點,而可靠性較高的葉子節(jié)點可以成為新的查詢超級節(jié)點.

Fig.5 Global query optimization algorithm for query layer in ElasticQM圖5 ElasticQM 查詢層的全局查詢優(yōu)化算法

容量可擴展區(qū)塊鏈模型的全局查詢優(yōu)化算法的具體過程見算法1.

算法1.容量可擴展區(qū)塊鏈模型的全局查詢優(yōu)化算法.

輸入:發(fā)起查詢節(jié)點A,查詢條件:Oi,Ni或Ri;

輸出:查詢結(jié)果,交易集合T.

ElasticQM 的查詢層模塊中,查詢超級節(jié)點只有在區(qū)塊鏈系統(tǒng)中發(fā)起查詢操作請求時,才會被優(yōu)先訪問.查詢層的超級節(jié)點在區(qū)塊鏈數(shù)據(jù)存儲時沒有任何優(yōu)先級,與網(wǎng)絡(luò)中其他節(jié)點相同.因此,查詢層中的超級節(jié)點不會影響整個可擴展區(qū)塊鏈系統(tǒng)的安全性和去中心化的特征.

在算法1 的步驟8 中,由于ElasticQM 模型中一些節(jié)點沒有保存著一條完整的區(qū)塊鏈數(shù)據(jù),因此節(jié)點需要在訪問完整的區(qū)塊鏈數(shù)據(jù)后,才能驗證查詢結(jié)果的安全性.不在節(jié)點內(nèi)存儲的區(qū)塊鏈數(shù)據(jù),將由模型中其他節(jié)點(查詢超級節(jié)點、查詢?nèi)~子節(jié)點和查詢驗證節(jié)點)共同恢復(fù)并驗證.ElasticQM 的查詢層采用全局查詢優(yōu)化算法后,避免了目前ElasticChain 模型查詢區(qū)塊數(shù)據(jù)時采用泛洪方法在系統(tǒng)中盲目查找的過程,減少了數(shù)據(jù)查找對區(qū)塊鏈網(wǎng)絡(luò)帶來的巨大處理壓力,并有效地減少了查詢所需時間,增加了查詢效率.

ElasticQM 在查詢層采用全局查詢優(yōu)化算法后,同樣可以保證區(qū)塊鏈系統(tǒng)對數(shù)據(jù)的一致性要求.當(dāng)模型中的超級節(jié)點將本地的路由信息惡意修改或丟失,附近的葉子節(jié)點將不能訪問這個超級節(jié)點或超級節(jié)點返回錯誤路徑.在這種情況下,葉子節(jié)點會訪問附近其他超級節(jié)點進(jìn)行數(shù)據(jù)查詢.如果系統(tǒng)中存儲節(jié)點將本地的數(shù)據(jù)丟失或篡改,在查詢發(fā)起節(jié)點收到查詢結(jié)果后,會根據(jù)本地存儲的區(qū)塊鏈哈希頭的數(shù)據(jù),對查詢結(jié)果的哈希值進(jìn)行驗證.如果發(fā)起節(jié)點發(fā)現(xiàn)數(shù)據(jù)錯誤或不完整的情況,將會把驗證信息發(fā)個查詢超級節(jié)點,超級節(jié)點確認(rèn)后,將惡意的存儲節(jié)點從路由表中刪除.因此,節(jié)點在ElasticQM 在查詢層中可以達(dá)到共識.

4.3 存儲層

ElasticQM 的存儲層響應(yīng)查詢層的查詢請求,并發(fā)送請求到數(shù)據(jù)層進(jìn)行數(shù)據(jù)查詢.在ElasticQM 存儲層中,基本采用了文獻(xiàn)[11]中ElasticChain 模型的數(shù)據(jù)存儲方法,實現(xiàn)了區(qū)塊鏈的容量可擴展存儲.ElasticQM 的存儲層主要包括了數(shù)據(jù)分片、節(jié)點驗證和分片存儲這3 個部分.在數(shù)據(jù)數(shù)據(jù)分片和分片存儲部分,ElasticQM 的存儲層采用了和ElasticChain 模型相同的算法,得到分片的方法、每個分片的大小和分片的副本數(shù).但存儲層在節(jié)點可靠性驗證部分對ElasticChain 模型進(jìn)行了改進(jìn):在ElasticQM 存儲層中的用戶節(jié)點完成每次數(shù)據(jù)分片存儲后,不再存儲P 鏈來記錄分片的存儲位置.其他節(jié)點的可靠性驗證過程都與ElasticChain 模型相同.

ElasticChain 模型中,用戶節(jié)點保存P 鏈數(shù)據(jù)是為了快速查詢數(shù)據(jù),但是P 鏈占據(jù)了大量的存儲空間.經(jīng)過ElasticQM 模型的改進(jìn),在區(qū)塊鏈上的查詢操作交給了模型查詢層完成,因此減少了區(qū)塊鏈模型的存儲空間,進(jìn)一步增加了區(qū)塊鏈的存儲容量可擴展性.

4.4 數(shù)據(jù)層

目前,區(qū)塊鏈數(shù)據(jù)在每個塊中以梅克爾樹的形式存儲.梅克爾樹的特點是一個數(shù)據(jù)利用其生成的哈希值,可以快速地驗證是否存在于區(qū)塊鏈中.當(dāng)用戶想要訪問區(qū)塊鏈中的一條具體數(shù)據(jù)信息時,對于一個完全節(jié)點就需要遍歷區(qū)塊內(nèi)利用梅克爾樹存儲的全部數(shù)據(jù).但是隨著區(qū)塊鏈應(yīng)用的廣泛普及,區(qū)塊鏈中保存的數(shù)據(jù)量也會急劇增加,在一條完整的區(qū)塊鏈上進(jìn)行數(shù)據(jù)查詢,效率隨之越來越慢.因此,本節(jié)提出了基于B-M 樹的區(qū)塊鏈存儲結(jié)構(gòu),既實現(xiàn)了梅克爾樹的特點(一個節(jié)點可以在不下載整個塊的情況下,驗證區(qū)塊中是否包含某筆交易),又提高了在一條完整區(qū)塊鏈上的數(shù)據(jù)查詢效率,并使區(qū)塊鏈支持?jǐn)?shù)據(jù)范圍查詢.

基于B-M 樹的區(qū)塊鏈存儲結(jié)構(gòu)結(jié)合了平衡二叉樹和梅克爾樹的的各自特點,其節(jié)點的數(shù)據(jù)結(jié)構(gòu)如圖6 所示.一個B-M 樹的節(jié)點包括了數(shù)據(jù)序列化后的哈希值或合并后的哈希值(hash)、其包含所有葉子節(jié)點記錄發(fā)起者地址的最大值(max)和最小值(min)、該位置在平衡二叉樹映射節(jié)點地址(K)和指向葉子節(jié)點的左指針(L1)與右指針(R1).

Fig.6 Structure of B-M tree圖6 B-M 樹數(shù)據(jù)結(jié)構(gòu)

在B-M 樹建立過程中,首先,系統(tǒng)確認(rèn)在一個區(qū)塊產(chǎn)生的固定時間里寫入?yún)^(qū)塊的數(shù)據(jù);然后,根據(jù)每個用戶地址數(shù)值的大小,建立起平衡二叉樹,保證樹中每個節(jié)點左右兩個子樹的高度差的絕對值不超過1;最后,從樹的底部開始,逐層地將這個平衡二叉樹的葉子節(jié)點的哈希值兩兩進(jìn)行合并,組成新的哈希值,并同時保存著所有合并的記錄發(fā)起者用戶地址的最大值和最小值、該位置在平衡二叉樹映射節(jié)點地址和指向葉子節(jié)點的左指針與右指針.模型會不斷重復(fù)這個過程,直到合并成一個哈希值,并將其保存在區(qū)塊頭.在哈希值兩兩合并過程中,從平衡二叉樹的底部開始,左葉子節(jié)點和其父節(jié)點先做一次合并,然后將得到的合并哈希值與右葉子節(jié)點再次合并,得到父節(jié)點和左右兩個葉子節(jié)點的合并在一起的哈希值,直到合并成一個哈希值.這樣,B-M 樹的存儲結(jié)構(gòu)就被建立起來,B-M 樹詳細(xì)的建立算法見算法2.

算法2.B-M 樹建立算法.

輸入:一串交易數(shù)據(jù)的數(shù)組;

輸出:B-M 樹存儲模型.

同時,我們通過舉例具體闡述B-M 樹的建立過程.當(dāng)記錄發(fā)起者的用戶地址為4,7,8,10,14,20,25,30,40 時,B-M 樹的建立過程如圖7 所示.

Fig.7 Establishment process of B-M tree圖7 B-M 樹建立過程

當(dāng)某節(jié)點發(fā)起一個范圍查詢時,首先,如果這個節(jié)點是完全節(jié)點,則在本地查詢;如果不是完全節(jié)點,則連接一個完全節(jié)點,在這個完全節(jié)點中進(jìn)行查詢.在完全節(jié)點中查詢數(shù)據(jù)時,首先從新區(qū)塊到舊區(qū)塊的順序遍歷每個區(qū)塊的區(qū)塊頭中B-M 樹的樹根,根據(jù)B-M 樹根中所有葉子節(jié)點的記錄發(fā)起者地址最大值和最小值,判斷要查詢數(shù)據(jù)是否存在于這個區(qū)塊中:如果不在樹根的最大值和最小值范圍內(nèi),則校驗下一個區(qū)塊;如果在范圍內(nèi),則根據(jù)B-M 樹中保存的平衡二叉樹映射節(jié)點地址K進(jìn)行基于平衡二叉樹查找算法的搜索,直至找到相關(guān)數(shù)據(jù),將結(jié)果返回給發(fā)起查找節(jié)點.如果搜索完整個B-M 樹還沒有找到所查找數(shù)據(jù),則以相同方法搜索下一個區(qū)塊.B-M 樹查找算法見算法3.例如在圖7 的B-M 樹中,如果查找記錄發(fā)起者地址為8 的數(shù)據(jù),首先從B-M 樹根節(jié)點處判斷其葉子節(jié)點包括記錄的發(fā)起者地址范圍為4～40,地址8 在其范圍內(nèi),對這個B-M 樹進(jìn)行查找操作.在B-M 樹內(nèi)查找時,首先訪問根節(jié)點保存的K值為20,大于8,所以向這個B-M 樹的左葉子節(jié)點進(jìn)行搜索.當(dāng)訪問到K值為10 的節(jié)點,地址值仍然大于8,所以繼續(xù)范圍左葉子節(jié)點,到K值為7 的節(jié)點.因為該節(jié)點K值小于所搜索地址,因此B-M 樹繼續(xù)查找該節(jié)點的右葉子節(jié)點,并訪問到了記錄發(fā)起者地址為8 的數(shù)據(jù).最后,將查找結(jié)果返回給查找節(jié)點.當(dāng)一個節(jié)點發(fā)起交易驗證時,驗證過程同目前區(qū)塊鏈系統(tǒng)相似.當(dāng)一個節(jié)點驗證區(qū)塊鏈中是否包含某筆交易時,節(jié)點利用Merkle 樹特點,只需要一個交易哈希,一個Merkle 樹根哈希和一個Merkle 路徑,在不下載整個塊的情況下進(jìn)行驗證.

算法3.B-M 樹查找算法.

輸入:基于B-M 樹的區(qū)塊鏈數(shù)據(jù),查詢條件:Oi;

輸出:查詢結(jié)果,交易集合T.

基于B-M 樹存儲結(jié)構(gòu)的區(qū)塊鏈模型,既保證了數(shù)據(jù)在區(qū)塊中可快速驗證,又充分利用二叉樹特點保證了查詢的高效性.基于B-M 樹模型與使用B+樹建立區(qū)塊內(nèi)數(shù)據(jù)索引的方法相比,省略了根據(jù)索引再查找數(shù)據(jù)的過程,因此具有更快的查詢速度.

4.5 理論分析與討論

本節(jié)總結(jié)ElasticQM 查詢模型中查詢層所提出的容量可擴展區(qū)塊鏈模型的全局查詢優(yōu)化算法、數(shù)據(jù)層所提出的B-M 樹建立算法和B-M 樹查找算法的時間代價和空間代價.對于區(qū)塊鏈容量可擴展模型ElasticChain,進(jìn)行查詢操作時,最壞的情況是不能根據(jù)P 鏈中信息找到存儲分片數(shù)據(jù)的節(jié)點(節(jié)點故障),這樣,模型需要采用泛洪搜索算法,在區(qū)塊鏈網(wǎng)絡(luò)中進(jìn)行搜索,這樣,搜索的時間復(fù)雜度為O(np),np為系統(tǒng)中的節(jié)點數(shù).而在ElasticQM 容量可擴展區(qū)塊鏈模型的全局查詢優(yōu)化算法中,查詢?nèi)~子節(jié)點通過向查詢超級節(jié)點請求,再由超級節(jié)點間進(jìn)行查詢,這樣,在查詢層ElasticQM 模型的查詢時間復(fù)雜度為O(nsp),nsp為系統(tǒng)中的查詢超級節(jié)點數(shù).在ElasticQM 數(shù)據(jù)層,基于B-M 樹的查找算法時間復(fù)雜度接近于平衡二叉樹為O(lognt),nt為一個區(qū)塊中的交易總數(shù).而在 ElasticChain 模型中,在區(qū)塊內(nèi)進(jìn)行查詢需要遍歷區(qū)塊完整數(shù)據(jù),查詢時間復(fù)雜度為O(nt).因此,ElasticQM 查詢模型整體查詢時間復(fù)雜度為O(nsp×lognt),ElasticChain 模型整體查詢時間復(fù)雜度為O(np×nt).在空間代價方面,ElasticQM 模型在查詢層的全局優(yōu)化算法與ElasticChain 模型相同,都是基于副本分片策略進(jìn)行存儲.而在ElasticQM 模型數(shù)據(jù)層,與區(qū)塊鏈和ElasticChain 模型相比增加了指針和葉子節(jié)點范圍等數(shù)據(jù),但在一個區(qū)塊中.兩個模型空間復(fù)雜度同為O(nt),nt為一個區(qū)塊中的交易總數(shù).

5 實驗與分析

5.1 實驗環(huán)境

實驗的開發(fā)環(huán)境為Intel Core i5-6500 3.20GHz CPU 和16GB 內(nèi)存的PC 機上.利用VMware Workstation 12.5.2建立了4,8,12 和16 個節(jié)點.每個節(jié)點為內(nèi)存1GB 硬盤大小為60GB 的ubuntu16.04 系統(tǒng).借助IBM 開發(fā)的開源的Hyperledge fabric v0.6 版本,構(gòu)建起ElasticChain 區(qū)塊鏈的容量可擴展模型.

在實驗中,我們在ElasticQM 模型、基于ElasticChain 容量可擴展區(qū)塊鏈模型和基于fabric 的區(qū)塊鏈系統(tǒng)上分別進(jìn)行查詢操作.實驗循環(huán)運行調(diào)用chaincode_example02.go 交易代碼,每完成一次交易,會生成大小為5.39KB 的廣播消息和具有唯一標(biāo)識的哈希值.在查詢一條交易或驗證交易安全性時,都可以根據(jù)生成的唯一的哈希值進(jìn)行查詢驗證操作.當(dāng)3 個模型分別產(chǎn)生127MB,635MB 和1270MB 數(shù)據(jù)時,停止調(diào)用交易代碼.

在基于ElasticChain 區(qū)塊鏈模型中,我們將數(shù)據(jù)進(jìn)行基于副本分配策略分片處理,在分片時,我們設(shè)置了每64MB 數(shù)據(jù)作為一個分片,每個分片保存的副本數(shù)根據(jù)分配策略計算得出,每個分片的最小副本數(shù)為2 份.并且在ElasticQM 的存儲層,也采用相同的副本分配方法.同時,實驗分析了3 種區(qū)塊鏈模型在不同節(jié)點數(shù)下(當(dāng)在網(wǎng)絡(luò)中共有4 個節(jié)點、8 個節(jié)點、12 個節(jié)點和16 個節(jié)點時)查詢速度的快慢.當(dāng)網(wǎng)絡(luò)中節(jié)點數(shù)為4,8,12 和16 時,在ElasticQM 查詢層實驗設(shè)置的查詢超級節(jié)點數(shù)分別為1 個～4 個,其余節(jié)點為查詢?nèi)~子節(jié)點,每個查詢超級節(jié)點分別鏈接著3 個不重復(fù)的葉子節(jié)點,并且實驗在查詢?nèi)~子節(jié)點中隨機選取了2 個作為查詢驗證節(jié)點.

5.2 評估與結(jié)果分析

首先,實驗分析在可擴展模型上,基于ElasticQM 查詢方法的查詢效率.

實驗的查詢目標(biāo)是在容量大小為127MB,635MB 和1270MB 的區(qū)塊鏈數(shù)據(jù)中,隨機抽取90 條交易記錄和10 條惡意編造的交易記錄;然后,在基于ElasticQM 和基于ElasticChain 區(qū)塊鏈模型中,對這100 條記錄進(jìn)行查找操作.兩種模型在4 個、8 個、12 個和16 個節(jié)點時在總?cè)萘繛?27MB 區(qū)塊鏈數(shù)據(jù)中,平均查找一條交易記錄所需時間如圖8(a)所示.基于ElasticQM 和基于ElasticChain 模型在總?cè)萘繛?35MB 和1270MB 區(qū)塊鏈數(shù)據(jù)中,平均查找一條交易記錄所需時間如圖8(b)和圖8(c)所示.

Fig.8 Queries speed for ElasticQM and ElasticChain model圖8 ElasticQM 和ElasticChain 模型的查詢速度

通過分析圖8 的實驗結(jié)果,可以得到以下結(jié)論.

(1)在相同的區(qū)塊鏈數(shù)據(jù)中進(jìn)行查詢操作時,ElasticQM 模型與ElasticChain 模型相比,當(dāng)網(wǎng)絡(luò)中節(jié)點數(shù)較少時,ElasticChain 模型的平均查詢一條記錄的速度比ElasticQM 模型略快;而當(dāng)網(wǎng)絡(luò)中節(jié)點數(shù)較增加時,ElasticChain 模型的平均查詢一條記錄的所需時間明顯增加,而ElasticQM 模型所用的查詢時間增量較小;并且當(dāng)節(jié)點數(shù)量越多時,ElasticQM 的查詢速度優(yōu)于 ElasticChain 模型越明顯.這是由于ElasticChain 模型將區(qū)塊鏈數(shù)據(jù)分片存儲后,數(shù)據(jù)查詢算法會首先遍歷P 鏈數(shù)據(jù),而當(dāng)P 鏈中存儲的節(jié)點存在故障,模型就會采用基于P2P 網(wǎng)路中的泛洪算法,因此查詢效率較低.而ElasticQM 模型在查詢層采用了基于超級節(jié)點的查詢算法,網(wǎng)絡(luò)中當(dāng)節(jié)點數(shù)增加后,ElasticQM 在查詢時仍然可以通過超級節(jié)點中保存的路由信息快速找到相應(yīng)的數(shù)據(jù);

(2)通過對圖8(a)～圖8(c)進(jìn)行對比可以看出:如果網(wǎng)絡(luò)中節(jié)點數(shù)相同,當(dāng)區(qū)塊鏈數(shù)據(jù)增加后,ElasticQM 模型和ElasticChain 模型在區(qū)塊鏈上數(shù)據(jù)查詢時間隨著查找范圍的擴大成比例地增加.但由于兩種模型采用副本分配策略將數(shù)據(jù)分片處理后再存儲,查詢時間開銷主要包括了在區(qū)塊鏈中查找時間和訪問存儲節(jié)點和驗證節(jié)點的時間.隨著區(qū)塊鏈數(shù)據(jù)增加,ElasticQM 模型和ElasticChain 模型節(jié)點間的通訊次數(shù)增加緩慢.因此,兩個模型與基于fabric 的區(qū)塊鏈模型相比,查詢時間增速較慢;

(3)隨著區(qū)塊鏈數(shù)據(jù)的增加,網(wǎng)絡(luò)中相同節(jié)點數(shù)時,ElasticQM 模型在區(qū)塊鏈數(shù)據(jù)上進(jìn)行查找的時間增長的速率比ElasticChain 模型的查找時間增長較慢.因為在ElasticQM 模型的每個區(qū)塊中,數(shù)據(jù)以B-M樹的結(jié)構(gòu)進(jìn)行存儲,其在塊內(nèi)的查詢效率接近平和二叉樹查找效率.

然后,實驗分析ElasticQM 模型所占用存儲空間的大小.

在實驗中,在ElasticQM 模型、基于ElasticChain 容量可擴展區(qū)塊鏈模型和基于fabric 的區(qū)塊鏈系統(tǒng)上分別存儲比特幣錢包中前一個、五個和十個區(qū)塊數(shù)據(jù)(數(shù)據(jù)大小分別為127MB,635MB 和1270MB).ElasticQM 模型的存儲層和ElasticChain 模型的副本分片策略與查詢實驗相同.當(dāng)網(wǎng)絡(luò)中節(jié)點數(shù)為4,8,12 和16 時(ElasticQM查詢層查詢超級節(jié)點、查詢?nèi)~子節(jié)點和查詢驗證節(jié)點的設(shè)置也與上述查詢實驗相同),ElasticQM 模型、ElasticChain 模型和基于fabric 的區(qū)塊鏈系統(tǒng)中所有節(jié)點存儲數(shù)據(jù)的總量如圖9 所示.

Fig.9 Storage space occupied by ElasticQM,ElasticChain and fabric-based blockchain model圖9 ElasticQM,ElasticChain 和基于fabric 區(qū)塊鏈模型占用的存儲空間總量

通過分析圖9 的實驗結(jié)果,可以得到以下結(jié)論.

(1)ElasticQM 和ElasticChain 模型的所有節(jié)點儲存總量與fabric 區(qū)塊鏈相比,在節(jié)點數(shù)較少的情況下相差不大;但當(dāng)節(jié)點數(shù)增多時,ElasticQM 和ElasticChain 模型所占用的存儲空間與fabric 區(qū)塊鏈系統(tǒng)相比明顯減少.這是由于在實驗中fabric 區(qū)塊鏈系統(tǒng)節(jié)點都是完全節(jié)點,隨節(jié)點數(shù)的增加,系統(tǒng)存儲開銷也正比例地增加;而ElasticQM 和ElasticChain 模型采用了副本分片策略,在保證安全的情況下將數(shù)據(jù)進(jìn)行了分片處理并保存,實現(xiàn)了區(qū)塊鏈數(shù)據(jù)的存儲容量的可擴展性;

(2)當(dāng)網(wǎng)絡(luò)中的區(qū)塊鏈數(shù)據(jù)量較小時,ElasticQM 和ElasticChain 模型儲存總量與fabric 區(qū)塊鏈相比相差不大.這是由于ElasticChain 模型在存儲交易數(shù)據(jù)的同時,在P 鏈中保存了存儲節(jié)點位置信息,在POR 鏈中保存了儲存節(jié)點的可靠性評價信息.而ElasticQM 模型在查詢層查詢超級節(jié)點中保存了超級節(jié)點間的路由信息,查詢驗證節(jié)點存儲了各個節(jié)點的查詢穩(wěn)定性,在數(shù)據(jù)層每個區(qū)塊中數(shù)據(jù)以B-M 樹的結(jié)構(gòu)進(jìn)行存儲,B-M 樹中記錄著發(fā)起者地址的最大值和最小值、該位置在平衡二叉樹映射節(jié)點地址和指向葉子節(jié)點的左指針與右指針,并且在用戶層增加了數(shù)據(jù)緩存模塊.這些ElasticQM 和ElasticChain 模型比目前區(qū)塊鏈系統(tǒng)增加的數(shù)據(jù)占據(jù)著一定比例的存儲空間.但隨著區(qū)塊鏈中區(qū)塊的不斷增加,基于實驗中的副本分配策略就會大量減少ElasticQM 和ElasticChain 模型中的存儲總量.

(3)ElasticQM 模型占用的存儲空間略少于ElasticChain 模型,但兩個模型占用的存儲空間的差距不大;并且當(dāng)網(wǎng)絡(luò)中的區(qū)塊鏈數(shù)據(jù)不斷增加時,ElasticQM 和ElasticChain 模型儲存總量的增量趨于平緩.

6 總結(jié)與展望

區(qū)塊鏈技術(shù)是目前計算機領(lǐng)域的研究熱點,隨著其廣泛應(yīng)用,對于區(qū)塊鏈存儲容量的可擴展有著越來越高的要求.基于ElasticChain 區(qū)塊鏈存儲容量可擴展模型,將一條完整的區(qū)塊鏈副本進(jìn)行分片處理,并將分片數(shù)據(jù)保存在一定比例的節(jié)點中,提升了區(qū)塊鏈的存儲容量.本文提出一種區(qū)塊鏈容量可擴展模型的高效查詢方法——ElasticQM,將數(shù)據(jù)保存在用戶層、查詢層、存儲層和數(shù)據(jù)層模塊中:在用戶層,模型將查詢結(jié)果緩存,加快再次查詢相同數(shù)據(jù)時的查詢速度;模型在查詢層采用容量可擴展區(qū)塊鏈模型的全局查詢優(yōu)化算法,增加了查詢超級節(jié)點、查詢驗證節(jié)點和查詢?nèi)~子節(jié)點這 3 種模型中的角色,提高了查詢效率;在存儲層,模型基于ElasticChain 區(qū)塊鏈存儲方法實現(xiàn)了區(qū)塊鏈的容量可擴展存儲;在數(shù)據(jù)層,ElasticQM 采用基于B-M 樹的區(qū)塊鏈存儲結(jié)構(gòu),并給出了B-M 樹的建立算法和基于B-M 樹的查找算法.通過在多節(jié)點不同數(shù)據(jù)量的區(qū)塊鏈中查詢的實驗表明,ElasticQM 所有節(jié)點占用存儲空間略小于ElasticChain 模型,但明顯小于目前區(qū)塊鏈模型,并且ElasticQM 的查詢效率明顯優(yōu)于ElasticChain 模型.

在未來區(qū)塊鏈技術(shù)的應(yīng)用中,多鏈共存將是一個普遍現(xiàn)象.為了解決不同體系的區(qū)塊鏈中的代幣互轉(zhuǎn)的問題,就產(chǎn)生了對跨鏈操作的需求.目前,主流的跨鏈技術(shù)包括公證人機制、側(cè)鏈技術(shù)和中繼技術(shù)等.但在本文的模型中,尚未對可跨鏈的區(qū)塊鏈模型的高效查詢方法進(jìn)行研究.因此,在可以實現(xiàn)跨鏈操作的區(qū)塊鏈系統(tǒng)中進(jìn)行高效的數(shù)據(jù)查詢,將是未來區(qū)塊鏈技術(shù)的重要研究方向之一.