賈大宇,信俊昌,2,王之瓊,郭 薇,王國(guó)仁

1(東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,遼寧 沈陽(yáng) 110819)

2(遼寧省大數(shù)據(jù)管理與分析重點(diǎn)實(shí)驗(yàn)室,遼寧 沈陽(yáng) 110819)

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

4(沈陽(yáng)航空航天大學(xué) 計(jì)算機(jī)學(xué)院,遼寧 沈陽(yáng) 110136)

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

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

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

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

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

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

· 在用戶層中,包括了數(shù)據(jù)緩存、數(shù)據(jù)驗(yàn)證和數(shù)據(jù)同步等模塊:數(shù)據(jù)同步模塊保證了數(shù)據(jù)的時(shí)效性;數(shù)據(jù)緩存模塊將查詢過(guò)的數(shù)據(jù)緩存在本地磁盤(pán)中,增加再次查詢?cè)摂?shù)據(jù)的查詢速度;

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

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

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

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

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

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

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

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

1 相關(guān)工作

近年來(lái),對(duì)于區(qū)塊鏈技術(shù)的研究越來(lái)越受到人們關(guān)注.首先,在提高區(qū)塊鏈中數(shù)據(jù)查詢效率方面,文獻(xiàn)[14]開(kāi)發(fā)了基于Ethereum 的高效查詢層EtherQL.EtherQL 會(huì)自動(dòng)同步區(qū)塊鏈系統(tǒng)中新的區(qū)塊數(shù)據(jù),并將其存儲(chǔ)在專用數(shù)據(jù)庫(kù)中,以確保查詢準(zhǔn)確性和高效性.同時(shí),EtherQL 提供了比其他區(qū)塊鏈應(yīng)用系統(tǒng)更高效、更靈活的數(shù)據(jù)查詢接口,并且支持對(duì)區(qū)塊鏈數(shù)據(jù)的范圍查詢和top-k查詢.在區(qū)塊鏈系統(tǒng)性能評(píng)價(jià)方面,文獻(xiàn)[15]首次提出了區(qū)塊鏈應(yīng)用的評(píng)價(jià)框架——Blockbench.文獻(xiàn)中,Blockbench 在Hyperledger Fabric 和以太坊的兩個(gè)客戶端(Parity 和Geth)這3 個(gè)區(qū)塊鏈私有鏈平臺(tái)上,評(píng)價(jià)了每個(gè)平臺(tái)在吞吐量、延遲、可擴(kuò)展性和容錯(cuò)方面的性能,并做了詳細(xì)的比較和分析.并且,區(qū)塊鏈技術(shù)在未來(lái)也是計(jì)算機(jī)、數(shù)據(jù)庫(kù)領(lǐng)域的研究熱點(diǎn).文獻(xiàn)[16]通過(guò)查閱大量區(qū)塊鏈系統(tǒng)的框架和應(yīng)用情況,分析出未來(lái)在區(qū)塊鏈數(shù)據(jù)管理和分析方面的主要研究方向:區(qū)塊鏈充分利用現(xiàn)有成熟的數(shù)據(jù)和信息系統(tǒng)的方法、增強(qiá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é)議通過(guò)設(shè)置安全的數(shù)字簽名和一種新型可驗(yàn)證隨機(jī)函數(shù),來(lái)保證在半同步狀態(tài)下區(qū)塊鏈的安全性.文獻(xiàn)開(kāi)發(fā)了一個(gè)通用的基于新協(xié)議的區(qū)塊鏈模型,并通過(guò)建立隨機(jī)預(yù)言機(jī)模型進(jìn)行模擬實(shí)驗(yàn),驗(yàn)證了新協(xié)議的高安全性.文獻(xiàn)[18]提出ForkBase 數(shù)據(jù)庫(kù)存儲(chǔ)引擎,ForkBase 解決了在數(shù)據(jù)容易產(chǎn)生分叉或分歧的系統(tǒng)中出現(xiàn)的多版本、交叉語(yǔ)義和惡意篡改攻擊等問(wèn)題.同時(shí),文獻(xiàn)提出了名為POS-Tree 的管理大型數(shù)據(jù)對(duì)象的索引結(jié)構(gòu),減少了系統(tǒng)的存儲(chǔ)開(kāi)銷.文獻(xiàn)評(píng)估了ForkBase 與區(qū)塊鏈平臺(tái)、wiki 服務(wù)和一個(gè)協(xié)作分析應(yīng)用軟件OrpheusDB 等3 個(gè)具有代表性的復(fù)雜應(yīng)用各自的性能,展示了Fork-Base 的可用性和高效性.文獻(xiàn)[19]分析了比特幣以外的區(qū)塊鏈的安全性和網(wǎng)絡(luò)可靠性,分析發(fā)現(xiàn),Namecoin 區(qū)塊鏈系統(tǒng)中擁有單個(gè)礦工在數(shù)月里的計(jì)算能力超過(guò)全網(wǎng)的51%,這是區(qū)塊鏈系統(tǒng)中非常嚴(yán)重的安全隱患.因此,文獻(xiàn)提出了開(kāi)源軟件Blockstack,在Blockstack 框架中設(shè)計(jì)了4 層架構(gòu)——區(qū)塊鏈層、虛擬層、路由層和數(shù)據(jù)存儲(chǔ)層,避免了Namecoin 區(qū)塊鏈系統(tǒng)檢測(cè)出來(lái)的安全問(wèn)題.文獻(xiàn)[20]提出了量化框架來(lái)分析基于PoW 共識(shí)機(jī)制的區(qū)塊鏈系統(tǒng)在不同網(wǎng)絡(luò)參數(shù)下的安全性.框架分析了區(qū)塊鏈系統(tǒng)在實(shí)際應(yīng)用中存在的網(wǎng)絡(luò)傳播、不同區(qū)塊大小、區(qū)塊生成時(shí)間間隔、信息傳播機(jī)制以及日食攻擊(eclipse attacks)等影響系統(tǒng)安全性的約束.設(shè)計(jì)了應(yīng)對(duì)雙重支付(double-spending)和自私挖掘(selfish mining)的最優(yōu)對(duì)抗策略.

2 預(yù)備知識(shí)和問(wèn)題定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 問(wèn)題定義

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

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

3 ElasticQM 查詢模型總覽

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 用戶層

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

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

4.2 查詢層

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3 存儲(chǔ)層

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

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

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

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

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

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

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

算法2.B-M 樹(shù)建立算法.

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

輸出:B-M 樹(shù)存儲(chǔ)模型.

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

Fig.7 Establishment process of B-M tree圖7 B-M 樹(shù)建立過(guò)程

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

算法3.B-M 樹(shù)查找算法.

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

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

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

4.5 理論分析與討論

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

5 實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)環(huán)境

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

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

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

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

首先,實(shí)驗(yàn)分析在可擴(kuò)展模型上,基于ElasticQM 查詢方法的查詢效率.

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

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

通過(guò)分析圖8 的實(shí)驗(yàn)結(jié)果,可以得到以下結(jié)論.

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

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

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

然后,實(shí)驗(yàn)分析ElasticQM 模型所占用存儲(chǔ)空間的大小.

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

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

通過(guò)分析圖9 的實(shí)驗(yàn)結(jié)果,可以得到以下結(jié)論.

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

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

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

6 總結(jié)與展望

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

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