面向時空數(shù)據(jù)的區(qū)塊鏈構(gòu)建及查詢方法

華亞洲，丁琳琳，陳澤，王俊陸，朱珠

面向時空數(shù)據(jù)的區(qū)塊鏈構(gòu)建及查詢方法

華亞洲，丁琳琳*，陳澤，王俊陸，朱珠

（遼寧大學(xué) 信息學(xué)院，沈陽 110036）（?通信作者電子郵箱dinglinlin@lnu.edu.cn）

時空數(shù)據(jù)作為一種同時具有時間維度及空間維度的數(shù)據(jù)類型，被廣泛應(yīng)用于供應(yīng)鏈管理、電子商務(wù)等領(lǐng)域，它的完整性及安全性在實際應(yīng)用中具有重要意義。針對目前時空數(shù)據(jù)集中式存儲方式存在數(shù)據(jù)不透明且易被篡改的問題，將區(qū)塊鏈技術(shù)的去中心化、防篡改、可追溯等特性與時空數(shù)據(jù)管理相結(jié)合，提出面向時空數(shù)據(jù)的區(qū)塊鏈構(gòu)建及查詢方法。首先，提出一種基于改進(jìn)圖型區(qū)塊鏈（Block?DAG）的時空數(shù)據(jù)區(qū)塊鏈架構(gòu)ST_Block?DAG；其次，為了提升時空數(shù)據(jù)的存儲及查詢效率，在ST_Block?DAG區(qū)塊鏈內(nèi)部采取基于四叉樹及單鏈表的結(jié)構(gòu)存儲時空數(shù)據(jù)；最后，在ST?Block?DAG存儲結(jié)構(gòu)基礎(chǔ)上實現(xiàn)了多種時空數(shù)據(jù)查詢算法，如單值查詢、范圍查詢等。實驗結(jié)果表明，與STBitcoin、Block?DAG以及STEth相比，ST_Block?DAG的時空數(shù)據(jù)處理效率提升了70%以上，時空數(shù)據(jù)綜合查詢性能提升了60%以上。所提方法能夠?qū)崿F(xiàn)時空數(shù)據(jù)的快速存儲及查詢，可以有效支持時空數(shù)據(jù)的管理。

區(qū)塊鏈；時空數(shù)據(jù)；存儲架構(gòu)；索引結(jié)構(gòu)；查詢算法

0 引言

近年來，隨著比特幣［1］、以太坊［2-3］等區(qū)塊鏈技術(shù)迅速發(fā)展，引起了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。區(qū)塊鏈本身并不是一種新技術(shù)，而是基于密碼學(xué)技術(shù)［4］、分布式存儲技術(shù)、共識機(jī)制在內(nèi)的多種技術(shù)的混合體，是一種去中心化、可追溯防篡改的分布式賬本［5］，能夠安全可靠地存儲數(shù)據(jù)。

在區(qū)塊數(shù)據(jù)管理方面，文獻(xiàn)［6］中提出了基于許可型區(qū)塊鏈的數(shù)據(jù)管理；為了提升數(shù)據(jù)查詢效率，文獻(xiàn)［7］中在區(qū)塊鏈之上建立了數(shù)據(jù)庫層；文獻(xiàn)［8］中提出了關(guān)于時空數(shù)據(jù)的時間查詢策略；文獻(xiàn)［9］中通過塊頭優(yōu)化，提出一種時空數(shù)據(jù)的查詢方法；文獻(xiàn)［10］中提出一種基于區(qū)塊鏈的時序數(shù)據(jù)管理系統(tǒng)；文獻(xiàn)［11］中提出了一種細(xì)粒度的區(qū)塊數(shù)據(jù)溯源系統(tǒng)LineageChain；文獻(xiàn)［12］在區(qū)塊鏈數(shù)據(jù)庫上提出一種支持可驗證的數(shù)據(jù)查詢模型；文獻(xiàn)［13］中對不同貨幣下的交易數(shù)據(jù)進(jìn)行分析。

金融、醫(yī)療、供應(yīng)鏈［14］、電子商務(wù)等領(lǐng)域中的數(shù)據(jù)類型多為時空數(shù)據(jù)，而保證時空數(shù)據(jù)的完整、透明及安全存儲在實際應(yīng)用中具有重要意義。例如幾年前的疫苗事件中，關(guān)于疫苗的時空數(shù)據(jù)均存儲在公司內(nèi)部服務(wù)器中，數(shù)據(jù)集中不透明，當(dāng)出現(xiàn)問題由相關(guān)部門介入調(diào)查后，發(fā)現(xiàn)時空數(shù)據(jù)遭到篡改，而生產(chǎn)的劣質(zhì)疫苗已經(jīng)流通，時空數(shù)據(jù)的不透明、不完整對事件的調(diào)查取證造成了極大的困難。為此，有必要將時空數(shù)據(jù)管理與區(qū)塊鏈技術(shù)結(jié)合起來，利用區(qū)塊鏈技術(shù)的去中心化、防篡改、可追溯等特性管理時空數(shù)據(jù)。傅易文晉等［15］分析了區(qū)塊鏈技術(shù)用于時空數(shù)據(jù)管理的可行性，發(fā)現(xiàn)傳統(tǒng)的區(qū)塊鏈技術(shù)對于時空數(shù)據(jù)支持度有限，原因主要有以下幾個方面：

首先，傳統(tǒng)的區(qū)塊鏈技術(shù)難以滿足時空數(shù)據(jù)高吞吐量需求，如比特幣每秒僅能處理7筆交易，且單個區(qū)塊存儲容量低，這對于數(shù)據(jù)規(guī)模大、時間敏感、變化速度快的時空數(shù)據(jù)支持度有限。針對該問題，文獻(xiàn)［16］中提出了一種區(qū)塊擴(kuò)容架構(gòu)，通過一個轉(zhuǎn)發(fā)隊列擴(kuò)充區(qū)塊容量，提升對時空數(shù)據(jù)的支持度。其次，繁瑣的投票確認(rèn)機(jī)制導(dǎo)致時空數(shù)據(jù)確認(rèn)時間長，上鏈速度慢，為此文獻(xiàn)［17］中提出使用側(cè)鏈技術(shù)，通過兩條鏈并行投票提升確認(rèn)速度。最后，傳統(tǒng)區(qū)塊鏈技術(shù)在數(shù)據(jù)查詢方面查詢方式單一，僅支持基于哈希值的查詢，對于時空數(shù)據(jù)查詢支持度有限。而時空數(shù)據(jù)經(jīng)常需要基于時間及空間維度進(jìn)行大量查詢，如：“列出時間為、位置為的所有時空數(shù)據(jù)”“列出時間范圍［1，2］內(nèi)、位置在處的所有時空數(shù)據(jù)”。文獻(xiàn)［18］針對時空數(shù)據(jù)查詢速度慢的問題提出了一種Ethernity架構(gòu)，通過在數(shù)據(jù)層和共識層中加入一個解析層，將新產(chǎn)生的時空數(shù)據(jù)解析至本地數(shù)據(jù)庫并實時存儲，實現(xiàn)在本地數(shù)據(jù)庫上的快速查詢。

傳統(tǒng)區(qū)塊鏈對于時空數(shù)據(jù)的支持度有限，而圖型區(qū)塊鏈（Directed Asycline Garph Blockchain， Block?DAG）網(wǎng)絡(luò)采用異步通信機(jī)制，大幅提升了區(qū)塊鏈的吞吐量和交易速度，Block?DAG架構(gòu)及其快速投票協(xié)議對于時空數(shù)據(jù)的存儲及查詢等均有較高的支持度；但是在Block?DAG網(wǎng)絡(luò)中可能存在前向區(qū)塊鏈接失敗的情況，這將會導(dǎo)致數(shù)據(jù)確認(rèn)緩慢甚至無法確認(rèn)的情況。為此本文提出了一種基于改進(jìn)Block?DAG的時空數(shù)據(jù)區(qū)塊鏈架構(gòu)ST_Block?DAG（Spatio?Temporal Block?DAG）；在此基礎(chǔ)上，考慮到時空數(shù)據(jù)的時間及空間維度，還提出了一種基于四叉樹及單鏈表的存儲結(jié)構(gòu)F?L Tree（Four?Link Tree），以有效支持時空數(shù)據(jù)的查詢，提升查詢效率。本文主要工作如下：

1）提出新的時空數(shù)據(jù)區(qū)塊鏈架構(gòu)ST_Block?DAG，并在區(qū)塊內(nèi)部結(jié)合時空數(shù)據(jù)的時間及空間維度提出了一種基于四叉樹及單鏈表的存儲結(jié)構(gòu)F?L Tree。

2）基于四叉樹及單鏈表的存儲結(jié)構(gòu)，提出時空數(shù)據(jù)的查詢方法，包括單值查詢以及范圍查詢，查詢時首先根據(jù)區(qū)塊頭信息找出所有符合查詢要求的區(qū)塊，然后依次檢索區(qū)塊內(nèi)數(shù)據(jù)，獲取符合查詢條件的數(shù)據(jù)得到查詢結(jié)果。

3）通過實驗與傳統(tǒng)區(qū)塊鏈進(jìn)行對比分析，結(jié)果表明ST_Block?DAG在提升數(shù)據(jù)吞吐量以及提高時空數(shù)據(jù)查詢效率方面有效提升了對于時空數(shù)據(jù)的支持度。

1 預(yù)備知識及相關(guān)定義

1.1　DAG區(qū)塊鏈定義

區(qū)塊鏈的發(fā)展經(jīng)歷了三個階段，分別為：以比特幣為代表的區(qū)塊鏈1.0，以以太坊為代表的區(qū)塊鏈2.0以及以DAG結(jié)構(gòu)為代表的區(qū)塊鏈3.0［19］。區(qū)塊鏈?zhǔn)前凑諘r間順序?qū)?shù)據(jù)區(qū)塊以順序相連的方式組合成的一種鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)，其本質(zhì)是一種去中心化的分布式賬本，并通過密碼學(xué)的方式保證賬本的不可篡改。

在比特幣、以太坊區(qū)塊鏈系統(tǒng)中，數(shù)據(jù)記錄以區(qū)塊為最小單位進(jìn)行存儲，區(qū)塊為區(qū)塊鏈網(wǎng)絡(luò)中的基本數(shù)據(jù)組織單元。區(qū)塊分為區(qū)塊頭和區(qū)塊體兩部分：區(qū)塊頭存儲元數(shù)據(jù)，包括區(qū)塊產(chǎn)生時間timestamp、版本號version、共識隨機(jī)數(shù)nonce、前向區(qū)塊哈希prehash等；區(qū)塊體存儲數(shù)據(jù)記錄，比特幣中的存儲結(jié)構(gòu)為Merkle Tree，以太坊中為MPT（Merkle Patricia Tree）。新產(chǎn)生的區(qū)塊通過對前向區(qū)塊的哈希引用形成了一條鏈?zhǔn)浇Y(jié)構(gòu)。

隨著區(qū)塊鏈技術(shù)的發(fā)展，為滿足不同應(yīng)用場景，克服區(qū)塊鏈1.0及2.0存在的弊端，出現(xiàn)了以Block?DAG為代表的區(qū)塊鏈3.0架構(gòu)，它最大特點是共識時間短、允許并行出塊。Block?DAG架構(gòu)分為細(xì)粒度及粗粒度：細(xì)粒度Block?DAG的一個交易對應(yīng)一個區(qū)塊，當(dāng)新交易產(chǎn)生時，該交易需要在區(qū)塊鏈網(wǎng)絡(luò)中找到兩個或以上的未驗證的交易進(jìn)行驗證，驗證合法后保存它們的哈希值。粗粒度Block?DAG結(jié)構(gòu)如圖1所示，區(qū)塊仍由區(qū)塊頭和區(qū)塊體組成，區(qū)塊頭存儲元數(shù)據(jù)信息，與細(xì)粒度Block?DAG不同的是，其區(qū)塊體內(nèi)存儲多條數(shù)據(jù)記錄。當(dāng)新區(qū)塊發(fā)布時，引用兩個或兩個以上區(qū)塊的哈希值，并將新區(qū)塊指向其所引用的區(qū)塊。

1.2　時空數(shù)據(jù)定義

時空數(shù)據(jù)是指同時具有時間維度及空間維度的數(shù)據(jù)，其中：時間維度為數(shù)據(jù)的時間標(biāo)簽，代表數(shù)據(jù)的產(chǎn)生時間；空間維度表示數(shù)據(jù)空間位置，通常以經(jīng)緯度坐標(biāo)形式表示。時間屬性及空間屬性是時空數(shù)據(jù)必須具備的屬性。依據(jù)以上定義將時空數(shù)據(jù)抽象為以下類型：

在以比特幣及以太坊為代表的傳統(tǒng)區(qū)塊鏈的區(qū)塊體中存儲的通常為交易數(shù)據(jù)，交易數(shù)據(jù)是區(qū)塊內(nèi)的最小數(shù)據(jù)組織單元，交易數(shù)據(jù)也為時空數(shù)據(jù)的一種。

圖1　粗粒度Block?DAG結(jié)構(gòu)

1.3　問題描述

本文要解決的問題是：基于時空數(shù)據(jù)的區(qū)塊鏈構(gòu)建及查詢。一方面，當(dāng)區(qū)塊鏈系統(tǒng)產(chǎn)生大量時空數(shù)據(jù)后，能夠?qū)崿F(xiàn)數(shù)據(jù)快速上鏈并為其提供防篡改證明；另一方面，當(dāng)時空數(shù)據(jù)存儲到區(qū)塊鏈后，能夠支持時空數(shù)據(jù)的查詢并能夠提高時空數(shù)據(jù)的查詢效率，并且支持多類型的時空數(shù)據(jù)查詢，例如單值查詢、范圍查詢等以滿足用戶的查詢需求。

2 ST_Block?DAG區(qū)塊鏈構(gòu)建

本章主要從ST_Block?DAG區(qū)塊鏈網(wǎng)絡(luò)節(jié)點分類及作用、時空數(shù)據(jù)的產(chǎn)生及確認(rèn)、共識節(jié)點時空數(shù)據(jù)的獲取流程，以及基于四叉樹及單鏈表的索引構(gòu)建等方面分析介紹ST_Block?DAG區(qū)塊鏈的構(gòu)建過程，并分析ST_Block?DAG架構(gòu)的安全性。

2.1　ST_Block?DAG節(jié)點分類及作用

ST_Block?DAG區(qū)塊鏈網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示。其中：用戶節(jié)點產(chǎn)生時空數(shù)據(jù)，在對時空數(shù)據(jù)簽名確認(rèn)后將時空數(shù)據(jù)發(fā)布到區(qū)塊鏈網(wǎng)絡(luò)中，用戶節(jié)點僅保存區(qū)塊頭數(shù)據(jù)用以驗證查詢結(jié)果的正確性；共識節(jié)點負(fù)責(zé)收集并驗證區(qū)塊鏈網(wǎng)絡(luò)中時空數(shù)據(jù)簽名信息的合法性，并將驗證合法的時空數(shù)據(jù)存儲到區(qū)塊鏈；全節(jié)點負(fù)責(zé)存儲時空數(shù)據(jù)的完整副本，并響應(yīng)用戶的查詢請求，將符合查詢條件的數(shù)據(jù)返回給用戶節(jié)點。

在僅由用戶節(jié)點、全節(jié)點、共識節(jié)點組成的區(qū)塊鏈網(wǎng)絡(luò)中，用戶節(jié)點發(fā)布到區(qū)塊鏈網(wǎng)絡(luò)中的時空數(shù)據(jù)由所有的共識節(jié)點接收用以發(fā)布新的區(qū)塊。由于ST_Block?DAG結(jié)構(gòu)為有向無環(huán)圖結(jié)構(gòu)，節(jié)點可以并行發(fā)布區(qū)塊，這在一定程度上弱化了區(qū)塊之間的順序性。由于共識節(jié)點接收到的時空數(shù)據(jù)一致，當(dāng)多個節(jié)點在短時間內(nèi)均發(fā)布新區(qū)塊時，會造成區(qū)塊與區(qū)塊之間的數(shù)據(jù)冗余度高，即不同的區(qū)塊內(nèi)存儲著大量相同的時空數(shù)據(jù)，這在一定程度上降低了ST_Block?DAG的可擴(kuò)展性，造成節(jié)點存儲空間的浪費。

圖2　時空數(shù)據(jù)區(qū)塊鏈網(wǎng)絡(luò)架構(gòu)

針對上述問題，在ST_Block?DAG架構(gòu)中引入了輔助節(jié)點，輔助節(jié)點分為超級輔助節(jié)點與普通輔助節(jié)點：超級輔助節(jié)點負(fù)責(zé)與共識節(jié)點之間的數(shù)據(jù)交互，普通輔助節(jié)點用于保證所有輔助節(jié)點間時空數(shù)據(jù)的一致性。輔助節(jié)點結(jié)構(gòu)是由多個緩沖區(qū)組成的時空數(shù)據(jù)池，緩沖區(qū)的大小為單個區(qū)塊的存儲容量。首先，由輔助接點接收用戶節(jié)點發(fā)送到ST_Block?DAG區(qū)塊鏈網(wǎng)絡(luò)的時空數(shù)據(jù)，并將接收到的時空數(shù)據(jù)依次存儲在時空數(shù)據(jù)池中的緩沖區(qū)，并保證數(shù)據(jù)的一致性［20］。在初次以及再次填充緩沖區(qū)時，需要就緩沖區(qū)中的時空數(shù)據(jù)與其他輔助節(jié)點達(dá)成一致。當(dāng)共識節(jié)點需要獲取時空數(shù)據(jù)并發(fā)布新區(qū)塊時，需要與超級輔助節(jié)點進(jìn)行通信，從其內(nèi)部緩沖區(qū)中獲取時空數(shù)據(jù)。當(dāng)成功獲取數(shù)據(jù)后，超級輔助節(jié)點與普通輔助節(jié)點需要保證時空數(shù)據(jù)池中數(shù)據(jù)狀態(tài)的一致性。引入輔助節(jié)點后，超級輔助節(jié)點保證了緩沖區(qū)中時空數(shù)據(jù)的不一致性，從而保證了共識節(jié)點獲取的時空數(shù)據(jù)的不一致，降低了區(qū)塊之間的數(shù)據(jù)冗余度；而普通輔助節(jié)點保證了所有輔助節(jié)點間的數(shù)據(jù)一致性，降低了超級輔助節(jié)點篡改時空數(shù)據(jù)的可能性，保證了原始時空數(shù)據(jù)的安全性。

2.2　區(qū)塊鏈構(gòu)建過程

2.2.1時空數(shù)據(jù)產(chǎn)生及確認(rèn)

在DAG區(qū)塊鏈網(wǎng)絡(luò)中，時空數(shù)據(jù)主要產(chǎn)生于用戶節(jié)點，時空數(shù)據(jù)的產(chǎn)生及確認(rèn)需要用戶節(jié)點或者多個參與方共同完成，時空數(shù)據(jù)的表示范圍不僅僅局限于交易記錄，用戶節(jié)點產(chǎn)生的大部分?jǐn)?shù)據(jù)記錄都可以抽象為具有時間及空間維度的時空數(shù)據(jù)。以電子商務(wù)為例，當(dāng)用戶購買了某件商品后便產(chǎn)生了一條時空數(shù)據(jù)記錄，購買時間及發(fā)貨地點對應(yīng)時空數(shù)據(jù)的時間及空間維度，后續(xù)過程中商品隨著時間的位置變化過程為時空數(shù)據(jù)的更新過程，并將更新后的時空數(shù)據(jù)再次存于區(qū)塊鏈網(wǎng)絡(luò)中。

2.2.2時空數(shù)據(jù)獲取

在ST_Block?DAG區(qū)塊鏈網(wǎng)絡(luò)中，共識節(jié)點負(fù)責(zé)更新區(qū)塊鏈數(shù)據(jù)即產(chǎn)生新區(qū)塊，并且共識節(jié)點內(nèi)保存了所有輔助節(jié)點的路由信息。在共識節(jié)點構(gòu)建新區(qū)塊時，根據(jù)本地保存的超級輔助接點的路由信息向超級輔助節(jié)點發(fā)送獲取時空數(shù)據(jù)請求。當(dāng)超級輔助節(jié)點收到共識節(jié)點的請求后，首先將其加入等待隊列并檢查時空數(shù)據(jù)池的狀態(tài)，查看是否存在不為空的緩沖區(qū)：若不存在，則所有共識節(jié)點進(jìn)入等待狀態(tài)，直到緩沖區(qū)再次填充后再獲取時空數(shù)據(jù)；若存在，則超級輔助節(jié)點按照請求隊列中的共識節(jié)點順序，依次將緩沖區(qū)中的時空數(shù)據(jù)及緩沖區(qū)編號發(fā)送給共識節(jié)點。當(dāng)共識節(jié)點收到時空數(shù)據(jù)及緩沖區(qū)編號后，依據(jù)本地保存的普通輔助節(jié)點的路由信息，向普通輔助節(jié)點發(fā)送獲取到的數(shù)據(jù)對應(yīng)的緩沖區(qū)編號；普通輔助節(jié)點收到共識節(jié)點的消息后，更新本地時空數(shù)據(jù)池中緩沖區(qū)的數(shù)據(jù)，并與其他輔助節(jié)點就緩沖區(qū)中的數(shù)據(jù)達(dá)成一致。至此共識節(jié)點獲取時空數(shù)據(jù)完成，具體過程見算法1。

算法1 時空數(shù)據(jù)獲取算法。

Input：超級輔助節(jié)點地址，共識節(jié)點，本地路由表；

Output：緩沖區(qū)中的數(shù)據(jù)。

1）向地址發(fā)送獲取時空數(shù)據(jù)請求。

2）節(jié)點接收節(jié)點請求，加入請求隊列；

3） for 1 to.（）

4）=.（）；

5） ifis not null

6） 從請求隊列中選擇節(jié)點發(fā)送編號及其中的時空數(shù)據(jù)；

7） else

8）++；

9） end if

10） if==.（）

11） 進(jìn)入等待狀態(tài)，直到緩沖區(qū)再次被填充；

12） end if

13） end for

14） return.；

15）接收到超級輔助接點發(fā)送的緩沖區(qū)數(shù)據(jù)及緩沖區(qū)編號；

16） for 1 to.（）

17）=.（）；

18） if！=

19）向發(fā)送緩沖區(qū)編號；

20） end if

21） end for

22）普通輔助節(jié)點依據(jù)接收的緩沖區(qū)編號同步數(shù)據(jù)

算法1第1）～2）行表示共識節(jié)點向超級輔助節(jié)點發(fā)送獲取時空數(shù)據(jù)請求；第3）～14）行表示超級輔助接點檢查時空數(shù)據(jù)池中的緩沖區(qū)狀態(tài)，查看是否有不為空的緩沖區(qū)，有則依據(jù)等待隊列發(fā)送數(shù)據(jù)，否則進(jìn)入等待狀態(tài)，直到緩沖區(qū)再次被填充；第15）～21）行表示共識節(jié)點獲取數(shù)據(jù)后，向其他輔助節(jié)點發(fā)送緩沖區(qū)編號，并同步輔助節(jié)點間的時空數(shù)據(jù)池。

2.2.3基于四叉樹及單鏈表的索引及其構(gòu)建過程

時空數(shù)據(jù)同時具有時間及空間維度，比特幣及以太坊區(qū)塊鏈內(nèi)部的存儲結(jié)構(gòu)對時空數(shù)據(jù)查詢的支持度有限，僅支持基于哈希值的查詢，無法實現(xiàn)時空數(shù)據(jù)的多屬性查詢，難以滿足用戶的查詢需求，為此在ST_Block?DAG區(qū)塊鏈內(nèi)部提出了一種基于四叉樹及單鏈表的索引結(jié)構(gòu)F?L Tree。F?L Tree 中的節(jié)點由葉子節(jié)點和非葉子節(jié)點組成，葉子節(jié)點和非葉子節(jié)點分別定義如下：

圖3　時空范圍劃分及F?L Tree節(jié)點劃分過程

算法2 F?L Tree構(gòu)建算法。

2）.（）

3） create；

6） create fouras􀆳s child；

7） forin

10） 回到第5）行

11） else

12） 創(chuàng)建鏈表存儲區(qū)域內(nèi)的是空數(shù)據(jù)

14） end if

15） end for

16） end if

17）從開始重復(fù)5）～16）行，直到每個子區(qū)域內(nèi)的時空數(shù)據(jù)量均小于；

18）讀取，并依據(jù)劃分情況加入節(jié)點哈希值；

19） return；

算法2的第1）～3）行確定時空范圍并創(chuàng)建根節(jié)點；第4）行將根節(jié)點除哈希值外的內(nèi)容添加到中；第5）～16）行用于判斷某個節(jié)點對應(yīng)的時空范圍內(nèi)的時空數(shù)據(jù)量是否大于，若大于則對子區(qū)域進(jìn)行進(jìn)一步的劃分，并繼續(xù)判斷劃分后的區(qū)域時空數(shù)據(jù)量與值的關(guān)系，直到子區(qū)域時空數(shù)據(jù)量小于，并創(chuàng)建鏈表存儲子區(qū)域內(nèi)數(shù)據(jù)；第17）行則表示從根節(jié)點開始重復(fù)執(zhí)行5）～16）行的步驟，直到每個節(jié)點所表示的子區(qū)域內(nèi)的時空數(shù)據(jù)量均小于；第18）～19）行讀取節(jié)點數(shù)據(jù)并加入哈希值。

2.3　ST_Block?DAG安全性分析

本節(jié)主要討論ST_Block?DAG區(qū)塊鏈架構(gòu)的安全性，并對其抗攻擊能力進(jìn)行分析。在安全性方面，首先，為了保證超級輔助節(jié)點返回給共識節(jié)點的數(shù)據(jù)的可靠性，在此基礎(chǔ)上引入了普通輔助節(jié)點，普通輔助節(jié)點的作用是同步所有輔助節(jié)點間的時空數(shù)據(jù)，保證超級輔助節(jié)點與普通輔助節(jié)點之間的數(shù)據(jù)一致性，從而能夠及時檢測超級輔助節(jié)點對于時空數(shù)據(jù)的篡改。除此之外，為了保證返回給用戶節(jié)點查詢結(jié)果的可靠性，在返回查詢結(jié)果時，將查詢路徑中對應(yīng)的非葉子節(jié)點的子哈希加入結(jié)果集中，用戶收到查詢結(jié)果后，根據(jù)其中的哈希值重構(gòu)出根哈希，通過與本地保存的根哈希比較，從而判斷查詢結(jié)果的可靠性。

在以比特幣及以太坊為代表的單鏈?zhǔn)絽^(qū)塊鏈系統(tǒng)中，攻擊者要想攻擊成功，至少需要掌握整個系統(tǒng)51%的算力。但隨著越來越多的節(jié)點加入?yún)^(qū)塊鏈網(wǎng)絡(luò)，整體區(qū)塊鏈系統(tǒng)的算力會迅速增長，且其中絕大多數(shù)的節(jié)點都是誠實節(jié)點，在這種情況下掌握51%的算力并進(jìn)行攻擊是一件相當(dāng)困難的事情。在單鏈?zhǔn)降膮^(qū)塊鏈網(wǎng)絡(luò)，攻擊者攻擊成功的概率會隨著區(qū)塊數(shù)量的增加呈指數(shù)級下降，而ST_Block?DAG架構(gòu)是基于Block?DAG網(wǎng)絡(luò)提出的，DAG本質(zhì)上是一種有向無環(huán)圖結(jié)構(gòu)，它可以看成是多條鏈?zhǔn)浇Y(jié)構(gòu)的復(fù)合，在這種情況下，攻擊者在攻擊時需要修改多條鏈才能達(dá)到目的，相較于單鏈?zhǔn)降膮^(qū)塊鏈系統(tǒng)，攻擊難度更大，因此ST_Block?DAG相較于傳統(tǒng)的單鏈?zhǔn)酱鎯Y(jié)構(gòu)具有更高的安全性。

3 基于ST_Block?DAG的時空數(shù)據(jù)查詢

本章基于所構(gòu)建的ST_Block?DAG區(qū)塊鏈架構(gòu)給出時空數(shù)據(jù)查詢類型，包括時空數(shù)據(jù)的單值查詢、范圍查詢，在ST_Block?DAG區(qū)塊鏈中，時空數(shù)據(jù)查詢依據(jù)F?L Tree索引結(jié)構(gòu)實現(xiàn)，時空數(shù)據(jù)的查詢即為F?L Tree遍歷的過程，在遍歷過程中將符合查詢條件的數(shù)據(jù)加入結(jié)果集并返回給用戶。除此之外還給出了查詢結(jié)果的驗證算法。用戶在收到結(jié)果集后，可以依據(jù)其中的驗證查詢結(jié)果的準(zhǔn)確性。

3.1　時空數(shù)據(jù)單值查詢

算法3 時空數(shù)據(jù)單值查詢算法。

Input：，查詢條件t，s，，區(qū)塊集合；

Output：查詢結(jié)果集。

1） create；

2） 找出區(qū)塊集合中未被引用的區(qū)塊放入隊列中

3） Function traverseFLtree（t，s，，）

4）=.（）；

5） ift<.mid&&s<.mid

6）指向編號為00的子節(jié)點；

7） else ift<.mid&&s>.mid

8）指向編號為01的子節(jié)點；

9） else ift>.mid&&s<.mid

10）指向編號為10的子節(jié)點；

11） else

12）指向編號為11的子節(jié)點；

13） end if

14） ifis

15） for 1 to.（）

16） ift==［］.&&s==［］.&&

==［］.

17）.（［］.）；

18） 將查詢路徑所有兄弟節(jié)點的哈希值加入中；

19） else

20） 回到5），繼續(xù)執(zhí)行5）～16）；

21） end if

22） while ?。ǎ?/p>

23）=（［］）；

24） if t∈.［start，end］ &&s∈.［start，end］

25） traverseFLtree（t，s，，）；

26）（該塊哈希指針指向的所有塊）；

27） end if

28） end while

29） return；

算法第1）～2）行創(chuàng)建隊列，并將所有最新的未被引用的區(qū)塊放入隊列中；第3）～21）行為檢索符合查詢條件的區(qū)塊內(nèi)部F?L Tree的過程，參數(shù)包括用戶的查詢條件以及要檢索的區(qū)塊，將要檢索的區(qū)塊內(nèi)的符合查詢條件的數(shù)據(jù)以及相應(yīng)的子節(jié)點的哈希值存放到結(jié)果集中；第22）～28）行找出所有符合查詢條件的區(qū)塊，并加入隊列中；第29）行返回查詢結(jié)果。

3.2　時空數(shù)據(jù)范圍查詢

上文描述了在ST_Block?DAG中時空數(shù)據(jù)的單值查詢算法，即用戶要查詢在某個時間點以及某個位置的所有時空數(shù)據(jù)，該查詢方式只能查詢某個時間點的時空數(shù)據(jù)狀態(tài)，無法追溯時空數(shù)據(jù)的完整歷史，為此除了單值查詢外，用戶節(jié)點可能還需要范圍查詢來追溯時空數(shù)據(jù)的更新歷史。范圍查詢模式為=｛［t1，t2］，［s1，s2］，｝，其中［t1，t2］為要查詢的時間范圍，［s1，s2］為要查詢的空間范圍。在查詢過程中全節(jié)點首先判斷最新的未被引用的區(qū)塊頭中的時空范圍是否與查詢條件的時空范圍存在交集，只有存在交集時才檢索區(qū)塊，否則順序檢索下一區(qū)塊。直到區(qū)塊頭中的時空范圍均不滿足查詢條件。范圍查詢的具體過程見算法4。

算法4 時空數(shù)據(jù)范圍查詢算法。

Input：查詢條件｛［t1，t2］，［s1，s2］，｝，區(qū)塊集合；

Output：查詢結(jié)果集。

1） create；

2） for 1 to.（）

3）=.（）

4） if.satisfy

5）（）；

6） end if

7） end for

8） Function（［t1，t2］［s1，s2］）

9）=（）；

10） ift1<.mid<t2&&s1<.mid<s2

11）依次指向編號為00、01、10、11的子節(jié)點；

12） else ift1<.mid<t2&&s1>.mid

13）依次指向編號為01、11的子節(jié)點；

14） else ift1<.mid<t2&&s2<.mid

15）依次指向編號為00、10的子節(jié)點；

16） else ift1>.mid&&s1<.mid<s

17） node依次指向編號為10、11的子節(jié)點；

18） else ift1>.mid&&s1>.mid

19）指向編號為11的子節(jié)點；

20） else ift1>.mid&&s2<.mid

21）指向編號為10的子節(jié)點；

22） else ift2<.mid&&s2<s1<.mid<s2

23）依次指向編號為00、01的子節(jié)點；

24） else ift2<.mid&&s1>.mid

25）指向編號為01的子節(jié)點；

26） else

27）指向編號為00的子節(jié)點；

28） ifis

29） for 1 to.（）

30） ift==［］.&&s==［］.&&

==［］.；

31）.（［］.）；

32） 將查詢路徑所有兄弟節(jié)點的哈希值加入中；

33） else

34） 回到10），繼續(xù)執(zhí)行10）～25）；

35） end if

36） while ?。ǎ?/p>

37）=（［］）；

38）（［t1，t2］，［s1，s2］，）；

39） end while

40） return；

算法第1）～7）行創(chuàng)建隊列，利用BFS算法檢索區(qū)塊集合中的每個區(qū)塊，將區(qū)塊頭中的時空范圍與查詢條件存在交集的區(qū)塊加入隊列中；第8）～35）行遍歷符合查詢條件的區(qū)塊內(nèi)部的F?L Tree，參數(shù)包括時間范圍、空間范圍等，并依據(jù)時間范圍及空間范圍與時間中值及空間中值的關(guān)系，分為了9種情況，直到遍歷到葉子節(jié)點，并將符合查詢時空范圍及簽名信息的數(shù)據(jù)及相關(guān)兄弟節(jié)點哈希值存入到結(jié)果集；第36）～39）行對隊列中的每個區(qū)塊執(zhí)行第8）～35）行的檢索步驟，即不斷擴(kuò)充結(jié)果集中的數(shù)據(jù)；第40）行返回查詢結(jié)果。

3.3　時空數(shù)據(jù)驗證

圖4　查詢結(jié)果驗證過程

4 實驗與結(jié)果分析

4.1　實驗環(huán)境及對比實驗

實驗的硬件環(huán)境為Inter Core i5?7400 CPU（3.00 GHz）RAM為16 GB的PC，利用VMware WorkStation15.0.2建立節(jié)36個節(jié)點，每個節(jié)點為內(nèi)存1 GB、硬盤20 GB的CentOS7系統(tǒng)。36個節(jié)點分別為9個用戶節(jié)點、12個共識節(jié)點、6個全節(jié)點和9個輔助節(jié)點（其中2個節(jié)點為超級輔助節(jié)點）。數(shù)據(jù)集為Pokeman Go數(shù)據(jù)集，其中每條數(shù)據(jù)記錄包含經(jīng)度、緯度、時間戳，將其中的經(jīng)緯度利用GeoHash算法轉(zhuǎn)化為可以比較大小的字符串。

本文以Block?DAG原有架構(gòu)以及比特幣及以太坊的原有架構(gòu)作為對比。由于比特幣及以太坊原有架構(gòu)僅支持基于哈希值的數(shù)據(jù)查詢，因此修改了原有的數(shù)據(jù)結(jié)構(gòu)，增加了其中屬性，使其支持時空數(shù)據(jù)的時空查詢，并將其稱為STBitcoin （Spatio?Temporal Bitcoin）以及STEth （Spatio? Temporal Ethereum）。

4.2　實驗結(jié)果分析

4.2.1時空數(shù)據(jù)處理效率比較

實驗首先針對不同時空數(shù)據(jù)量，比較四種架構(gòu)在時空數(shù)據(jù)處理方面的效率。在實驗中，待處理時空數(shù)據(jù)的變化范圍為20～80 MB。通過比較時空數(shù)據(jù)從產(chǎn)生到上鏈的處理時間來比較不同架構(gòu)時空數(shù)據(jù)處理的效率。重復(fù)實驗50次，取平均值作為四種架構(gòu)對于不同時空數(shù)據(jù)量的處理效率。

圖5展示了四種架構(gòu)對于不同數(shù)據(jù)量的時空數(shù)據(jù)，從數(shù)據(jù)產(chǎn)生到數(shù)據(jù)處理到數(shù)據(jù)上鏈的時間。通過分析可知，實驗結(jié)果符合預(yù)期，隨著待處理的時空數(shù)據(jù)量的增加，四種架構(gòu)的處理時間均呈現(xiàn)增加的趨勢；但ST_Block?DAG架構(gòu)的增長幅度最小，原始Block?DAG架構(gòu)的處理效率優(yōu)于STBitcoin以及STEth。這是由于DAG存儲結(jié)構(gòu)允許節(jié)點并行出塊，從而增加了時空數(shù)據(jù)的上鏈速度，并且由于ST_Block?DAG結(jié)構(gòu)中輔助節(jié)點的作用，其效率略高于Block?DAG架構(gòu)；而STBitcon以及STEth的結(jié)構(gòu)為單鏈結(jié)構(gòu)，僅能依次產(chǎn)生區(qū)塊，并且STBitcoin繁瑣的確認(rèn)機(jī)制進(jìn)一步增加了STBitcoin的時空數(shù)據(jù)處理時間。實驗結(jié)果表明，本文所提出的時空數(shù)據(jù)區(qū)塊鏈架構(gòu)的時空數(shù)據(jù)處理效率較其他架構(gòu)綜合提升70%以上。

圖5　四種架構(gòu)的數(shù)據(jù)處理時間比較

4.2.2單區(qū)塊查詢效率比較

實驗比較了單個區(qū)塊內(nèi)Block?DAG、ST_Block?DAG、STBitcoin及STEth四種架構(gòu)的查詢效率，通過改變區(qū)塊內(nèi)的交易數(shù)量并比較四種架構(gòu)查詢的時間開銷來衡量其查詢性能。查詢方式為單區(qū)塊單值查詢及單區(qū)塊范圍查詢。針對不同的查詢方式重復(fù)實驗50次，取平均值作為其查詢開銷。

圖6　單區(qū)塊下單值查詢與范圍查詢比較

4.2.3多區(qū)塊查詢效率比較

實驗比較了查詢結(jié)果在多個區(qū)塊內(nèi)的查詢效率，固定每個區(qū)塊內(nèi)的交易數(shù)量為2 048，通過改變區(qū)塊的深度并比較四種架構(gòu)查詢時間的開銷衡量其查詢性能，查詢方式為多區(qū)塊單值查詢及多區(qū)塊范圍查詢，針對不同查詢方式重復(fù)實驗50次，取平均值作為其查詢開銷。

實驗結(jié)果表明，本文所提出的時空數(shù)據(jù)區(qū)塊鏈架構(gòu)對時空數(shù)據(jù)的單區(qū)塊以及多區(qū)塊查詢均有較好的支持度，其時空數(shù)據(jù)查詢效率較其他架構(gòu)綜合提升60%以上。

圖7　多區(qū)塊下單值查詢與范圍查詢比較

5 結(jié)語

本文介紹了時空數(shù)據(jù)的應(yīng)用場景，指出了目前時空數(shù)據(jù)管理存在的數(shù)據(jù)不透明等問題，提出將區(qū)塊鏈技術(shù)用于時空數(shù)據(jù)管理，但傳統(tǒng)的區(qū)塊鏈技術(shù)對時空數(shù)據(jù)的支持度有限，為此提出了一種改進(jìn)Block?DAG的時空數(shù)據(jù)區(qū)塊鏈架構(gòu)和關(guān)鍵查詢方法ST_Block?DAG，并提出了基于四叉樹及單鏈表的索引結(jié)構(gòu)。實驗表明，本文提出的索引結(jié)構(gòu)大大提高了時空數(shù)據(jù)的查詢效率。下一步擬在ST_Block?DAG節(jié)點的P2P（Peer to Peer）網(wǎng)絡(luò)架構(gòu)之間做出改進(jìn)，優(yōu)化節(jié)點間的網(wǎng)絡(luò)架構(gòu)，通過提升節(jié)點間的通信效率，進(jìn)一步提高時空數(shù)據(jù)的上鏈及查詢速度。

[1] NAKAMOTO S. Bitcoin： a peer?to?peer electronic cash system［EB/OL］. ［2021-07-25］.https：//bitcoin.org/bitcoin.pdf.

[2] BUTERIN V. A next?generation smart contract and decentralized application platform［EB/OL］. ［2021-07-28］. https：//www.weusecoins.com/assets/pdf/library/Ethereum_white_paper?a_next_ generation_smart_contract_and_decentralized_application_platform? vitalik?buterin.pdf.

[3] WOOD G. Ethereum： a secure decentralised generalised transaction ledger［EB/OL］. ［2021-07-30］.http：//gavwood.com/Paper.pdf.

[4] XU J， WEI L， ZHANG Y， et al. Dynamic fully homomorphic encryption?based Merkle tree for lightweight streaming authenticated data structures［J］. Journal of Network and Computer Applications， 2018， 107： 113-124.

[5] 袁勇，王飛躍. 區(qū)塊鏈技術(shù)發(fā)展現(xiàn)狀與展望［J］. 自動化學(xué)報， 2016， 42（4）： 481-494.（YUAN Y， WANG F Y. Blockchain： the state of the art and future trends［J］. Acta Automatica Sinica， 2016， 42（4）：481-494.）

[6] ANDROULAKI E， BARGER A， BORTNIKOV V， et al. Hyperledger Fabric： a distributed operating system for permissioned blockchains［C］// Proceedings of the 13th EuroSys Conference. New York： ACM， 2018： No.30.

[7] EL?HINDI M， BINNIG C， ARASU A， et al. BlockchainDB — a shared database on blockchains［J］. Proceedings of the VLDB Endowment， 2019， 12（11）： 1597-1609.

[8] QU Q， NURGALIEV I， MUZAMMAL M， et al. On spatio?temporal blockchain query processing［J］. Future Generation Computer Systems， 2019， 98： 208-218.

[9] 中國科學(xué)院深圳先進(jìn)技術(shù)研究院. 一種區(qū)塊鏈時空數(shù)據(jù)查詢方法，系統(tǒng)及電子設(shè)備： 201810765882.9［P］. 2018-09-28.（Shenzhen Institute of Advanced Technology， Chinese Academy of Sciences. A blockchain spatio?temporal data query method， system and electronic device： 201810765882.9［P］. 2018-09-28.）

[10] 中國地質(zhì)大學(xué)（武漢）. 一種基于區(qū)塊鏈的時間序列數(shù)據(jù)組織記錄方法及系統(tǒng)： 201810351188.2［P］. 2018-11-16.（China University of Geosciences （Wuhan）. A time series data organization and recording method and system based on blockchain： 201810351188.2［P］. 2018-11-16.）

[11] RUAN P C， DINH T T A， LIN Q， et al.： a fine? grained， secure and efficient data provenance system for blockchains［J］. The VLDB Journal， 2021， 30（1）：3-24.

[12] XU C， ZHANG C， XU J L. vChain： enabling verifiable boolean range queries over blockchain databases［C］// Proceedings of the 2019 International Conference on Management of Data. New York： ACM， 2019： 141-158.

[13] CHAN W， OLMSTED A. Ethereum transaction graph analysis［C］// Proceedings of the 12th International Conference for Internet Technology and Secured Transactions. Piscataway： IEEE， 2017： 498-500.

[14] SALAH K， NIZAMUDDIN N， JAYARAMAN R， et al. Blockchain?based soybean traceability in agricultural supply chain［J］. IEEE Access， 2019， 7： 73295-73305.

[15] 傅易文晉，陳華輝，錢江波，等. 面向時空數(shù)據(jù)的區(qū)塊鏈研究綜述［J］. 計算機(jī)工程， 2020， 46（3）：1-10.（FU Y W J， CHEN H H， QIAN J B， et al. Survey of blockchain research for spatiotemporal data［J］. Computer Engineering， 2020， 46（3）：1-10.）

[16] WANG J P， WANG H. Monoxide： scale out blockchain with asynchronous consensus zones［C］// Proceedings of the 16th USENIX Conference on Networked Systems Design and Implementation. Berkeley： USENIX Association， 2019：95-112.

[17] WORLEY C， SKJELLUM A. Blockchain tradeoffs and challenges for current and emerging applications： generalization， fragmentation， sidechains， and scalability［C］// Proceedings of the 2018 IEEE International Conference on Internet of Things/ Green Computing and Communications/ Cyber， Physical and Social Computing/ Smart Data/ Blockchain/ Computer and Information Technology. Piscataway： IEEE 2018：1582-1587.

[18] HELMER S， ROGGIA M， EL IOINI N， et al. EthernityDB — integrating database functionality into a blockchain［C］// Proceedings of the 2018 European Conference on Advances in Databases and Information Systems， CCIS 909. Cham： Springer， 2018：37-44

[19] 張長貴，張巖峰，李曉華，等. 區(qū)塊鏈新技術(shù)綜述：圖型區(qū)塊鏈和分區(qū)型區(qū)塊鏈［J］. 計算機(jī)科學(xué)， 2020， 47（10）：282-289.（ZHANG C G， ZHANG Y F， LI X H， et al. Survey of new blockchain techniques： DAG based blockchain and sharding based blockchain［J］. Computer Science， 2020， 47（10）：282-289.）

[20] VAN RENESSE R， DUMITRIU D， GOUGH V， et al. Efficient reconciliation and flow control for anti?entropy protocols［C］// Proceedings of the 2nd Workshop on Large?Scale Distributed Systems and Middleware. New York： ACM， 2008： No.6.

Blockchain construction and query method for spatio?temporal data

HUA Yazhou， DING Linlin*， CHEN Ze， WANG Junlu， ZHU Zhu

（，，110036，）

As a type of data with both temporal and spatial dimensions， spatio?temporal data is widely used in supply chain management， e?commerce and other fields， which integrity and security are of great importance in practical applications. Aiming at the problems of lack of transparency and easily being tampered of data in the current centralized storage of spatial?temporal datasets， a blockchain construction and query method for spatio?temporal data was proposed by combining the decentralized， tamper?proof and traceable characteristics of blockchain technology with spatio?temporal data management. Firstly， an improved Directed Asycline Graph Blockchain （Block?DAG） based blockchain architecture for spatio?temporal data， namely ST_Block?DAG （Spatio?Temporal Block?DAG）， was proposed. Secondly， to improve the efficiency of spatio?temporal data storage and query， a storage structure based on quadtree and single linked list was adopted to store spatio?temporal data in the ST_Block?DAG blockchain. Finally， a variety of spatio?temporal data query algorithms were implemented on the basis of the storage structure of ST_Block?DAG， such as single?value query and range query. Experimental results show that compared with STBitcoin （Spatio?Temporal Bitcoin）， Block?DAG and STEth （Spatio?Temporal Ethereum）， ST_Block?DAG has the spatio?temporal data processing efficiency improved by more than 70% and the comprehensive query performance of spatio?temporal data improved by more than 60%. The proposed method can realize fast storage and query of spatio?temporal data， and can effectively support the management of spatio?temporal data.

blockchain; spatio?temporal data; storage architecture; index structure; query algorithm

This work is partially supported by National Natural Science Foundation of China （72102096）.

HUA Yazhou， born in 1996， M. S. candidate. His research interests include blockchain.

DING Linlin， born in 1983， Ph. D.， associate professor. Her research interests include big data management，graph data management， blockchain.

CHEN Ze， born in 1996， M. S. candidate. His research interests include natural language processing， data mining.

WANG Junlu， born in 1988， Ph. D. candidate. His research interests include blockchain， time series flow.

ZHU Zhu， born in 1983， Ph. D.， associate professor. Her research interests include logistics and supply chain， blockchain.

TP311

A

1001-9081（2022）11-3429-09

10.11772/j.issn.1001-9081.2021111933

2021?11?13；

2021?12?20；

2022?01?05。

國家自然科學(xué)基金資助項目（72102096）。

華亞洲（1996—），男，山東濟(jì)寧人，碩士研究生，主要研究方向：區(qū)塊鏈；丁琳琳（1983—），女，遼寧錦州人，副教授，博士，CCF會員，主要研究方向：大數(shù)據(jù)管理、圖數(shù)據(jù)管理、區(qū)塊鏈；陳澤（1996—），男，遼寧錦州人，碩士研究生，CCF會員，主要研究方向：自然語言處理、數(shù)據(jù)挖掘；王俊陸（1988—），男，遼寧丹東人，博士研究生，CCF會員，主要研究方向：區(qū)塊鏈、時序流；朱珠（1983—），女，貴州赫章人，副教授，博士，CCF會員，主要研究方向：物流與供應(yīng)鏈、區(qū)塊鏈。