面向時空數據的區塊鏈構建及查詢方法

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

面向時空數據的區塊鏈構建及查詢方法

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

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

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

區塊鏈；時空數據；存儲架構；索引結構；查詢算法

0 引言

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

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

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

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

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

1）提出新的時空數據區塊鏈架構ST_Block?DAG，并在區塊內部結合時空數據的時間及空間維度提出了一種基于四叉樹及單鏈表的存儲結構F?L Tree。

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

3）通過實驗與傳統區塊鏈進行對比分析，結果表明ST_Block?DAG在提升數據吞吐量以及提高時空數據查詢效率方面有效提升了對于時空數據的支持度。

1 預備知識及相關定義

1.1　DAG區塊鏈定義

區塊鏈的發展經歷了三個階段，分別為：以比特幣為代表的區塊鏈1.0，以以太坊為代表的區塊鏈2.0以及以DAG結構為代表的區塊鏈3.0［19］。區塊鏈是按照時間順序將數據區塊以順序相連的方式組合成的一種鏈式數據結構，其本質是一種去中心化的分布式賬本，并通過密碼學的方式保證賬本的不可篡改。

在比特幣、以太坊區塊鏈系統中，數據記錄以區塊為最小單位進行存儲，區塊為區塊鏈網絡中的基本數據組織單元。區塊分為區塊頭和區塊體兩部分：區塊頭存儲元數據，包括區塊產生時間timestamp、版本號version、共識隨機數nonce、前向區塊哈希prehash等；區塊體存儲數據記錄，比特幣中的存儲結構為Merkle Tree，以太坊中為MPT（Merkle Patricia Tree）。新產生的區塊通過對前向區塊的哈希引用形成了一條鏈式結構。

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

1.2　時空數據定義

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

在以比特幣及以太坊為代表的傳統區塊鏈的區塊體中存儲的通常為交易數據，交易數據是區塊內的最小數據組織單元，交易數據也為時空數據的一種。

圖1　粗粒度Block?DAG結構

1.3　問題描述

本文要解決的問題是：基于時空數據的區塊鏈構建及查詢。一方面，當區塊鏈系統產生大量時空數據后，能夠實現數據快速上鏈并為其提供防篡改證明；另一方面，當時空數據存儲到區塊鏈后，能夠支持時空數據的查詢并能夠提高時空數據的查詢效率，并且支持多類型的時空數據查詢，例如單值查詢、范圍查詢等以滿足用戶的查詢需求。

2 ST_Block?DAG區塊鏈構建

本章主要從ST_Block?DAG區塊鏈網絡節點分類及作用、時空數據的產生及確認、共識節點時空數據的獲取流程，以及基于四叉樹及單鏈表的索引構建等方面分析介紹ST_Block?DAG區塊鏈的構建過程，并分析ST_Block?DAG架構的安全性。

2.1　ST_Block?DAG節點分類及作用

ST_Block?DAG區塊鏈網絡結構如圖2所示。其中：用戶節點產生時空數據，在對時空數據簽名確認后將時空數據發布到區塊鏈網絡中，用戶節點僅保存區塊頭數據用以驗證查詢結果的正確性；共識節點負責收集并驗證區塊鏈網絡中時空數據簽名信息的合法性，并將驗證合法的時空數據存儲到區塊鏈；全節點負責存儲時空數據的完整副本，并響應用戶的查詢請求，將符合查詢條件的數據返回給用戶節點。

在僅由用戶節點、全節點、共識節點組成的區塊鏈網絡中，用戶節點發布到區塊鏈網絡中的時空數據由所有的共識節點接收用以發布新的區塊。由于ST_Block?DAG結構為有向無環圖結構，節點可以并行發布區塊，這在一定程度上弱化了區塊之間的順序性。由于共識節點接收到的時空數據一致，當多個節點在短時間內均發布新區塊時，會造成區塊與區塊之間的數據冗余度高，即不同的區塊內存儲著大量相同的時空數據，這在一定程度上降低了ST_Block?DAG的可擴展性，造成節點存儲空間的浪費。

圖2　時空數據區塊鏈網絡架構

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

2.2　區塊鏈構建過程

2.2.1時空數據產生及確認

在DAG區塊鏈網絡中，時空數據主要產生于用戶節點，時空數據的產生及確認需要用戶節點或者多個參與方共同完成，時空數據的表示范圍不僅僅局限于交易記錄，用戶節點產生的大部分數據記錄都可以抽象為具有時間及空間維度的時空數據。以電子商務為例，當用戶購買了某件商品后便產生了一條時空數據記錄，購買時間及發貨地點對應時空數據的時間及空間維度，后續過程中商品隨著時間的位置變化過程為時空數據的更新過程，并將更新后的時空數據再次存于區塊鏈網絡中。

2.2.2時空數據獲取

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

算法1 時空數據獲取算法。

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

Output：緩沖區中的數據。

1）向地址發送獲取時空數據請求。

2）節點接收節點請求，加入請求隊列；

3） for 1 to.（）

4）=.（）；

5） ifis not null

6） 從請求隊列中選擇節點發送編號及其中的時空數據；

7） else

8）++；

9） end if

10） if==.（）

11） 進入等待狀態，直到緩沖區再次被填充；

12） end if

13） end for

14） return.；

15）接收到超級輔助接點發送的緩沖區數據及緩沖區編號；

16） for 1 to.（）

17）=.（）；

18） if！=

19）向發送緩沖區編號；

20） end if

21） end for

22）普通輔助節點依據接收的緩沖區編號同步數據

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

2.2.3基于四叉樹及單鏈表的索引及其構建過程

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

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

算法2 F?L Tree構建算法。

2）.（）

3） create；

6） create fouras􀆳s child；

7） forin

10） 回到第5）行

11） else

12） 創建鏈表存儲區域內的是空數據

14） end if

15） end for

16） end if

17）從開始重復5）～16）行，直到每個子區域內的時空數據量均小于；

18）讀取，并依據劃分情況加入節點哈希值；

19） return；

算法2的第1）～3）行確定時空范圍并創建根節點；第4）行將根節點除哈希值外的內容添加到中；第5）～16）行用于判斷某個節點對應的時空范圍內的時空數據量是否大于，若大于則對子區域進行進一步的劃分，并繼續判斷劃分后的區域時空數據量與值的關系，直到子區域時空數據量小于，并創建鏈表存儲子區域內數據；第17）行則表示從根節點開始重復執行5）～16）行的步驟，直到每個節點所表示的子區域內的時空數據量均小于；第18）～19）行讀取節點數據并加入哈希值。

2.3　ST_Block?DAG安全性分析

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

在以比特幣及以太坊為代表的單鏈式區塊鏈系統中，攻擊者要想攻擊成功，至少需要掌握整個系統51%的算力。但隨著越來越多的節點加入區塊鏈網絡，整體區塊鏈系統的算力會迅速增長，且其中絕大多數的節點都是誠實節點，在這種情況下掌握51%的算力并進行攻擊是一件相當困難的事情。在單鏈式的區塊鏈網絡，攻擊者攻擊成功的概率會隨著區塊數量的增加呈指數級下降，而ST_Block?DAG架構是基于Block?DAG網絡提出的，DAG本質上是一種有向無環圖結構，它可以看成是多條鏈式結構的復合，在這種情況下，攻擊者在攻擊時需要修改多條鏈才能達到目的，相較于單鏈式的區塊鏈系統，攻擊難度更大，因此ST_Block?DAG相較于傳統的單鏈式存儲結構具有更高的安全性。

3 基于ST_Block?DAG的時空數據查詢

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

3.1　時空數據單值查詢

算法3 時空數據單值查詢算法。

Input：，查詢條件t，s，，區塊集合；

Output：查詢結果集。

1） create；

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

3） Function traverseFLtree（t，s，，）

4）=.（）；

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

6）指向編號為00的子節點；

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

8）指向編號為01的子節點；

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

10）指向編號為10的子節點；

11） else

12）指向編號為11的子節點；

13） end if

14） ifis

15） for 1 to.（）

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

==［］.

17）.（［］.）；

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

19） else

20） 回到5），繼續執行5）～16）；

21） end if

22） while ！（）

23）=（［］）；

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

25） traverseFLtree（t，s，，）；

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

27） end if

28） end while

29） return；

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

3.2　時空數據范圍查詢

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

算法4 時空數據范圍查詢算法。

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

Output：查詢結果集。

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的子節點；

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

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

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

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

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

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

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

19）指向編號為11的子節點；

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

21）指向編號為10的子節點；

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

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

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

25）指向編號為01的子節點；

26） else

27）指向編號為00的子節點；

28） ifis

29） for 1 to.（）

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

==［］.；

31）.（［］.）；

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

33） else

34） 回到10），繼續執行10）～25）；

35） end if

36） while ！（）

37）=（［］）；

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

39） end while

40） return；

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

3.3　時空數據驗證

圖4　查詢結果驗證過程

4 實驗與結果分析

4.1　實驗環境及對比實驗

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

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

4.2　實驗結果分析

4.2.1時空數據處理效率比較

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

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

圖5　四種架構的數據處理時間比較

4.2.2單區塊查詢效率比較

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

圖6　單區塊下單值查詢與范圍查詢比較

4.2.3多區塊查詢效率比較

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

實驗結果表明，本文所提出的時空數據區塊鏈架構對時空數據的單區塊以及多區塊查詢均有較好的支持度，其時空數據查詢效率較其他架構綜合提升60%以上。

圖7　多區塊下單值查詢與范圍查詢比較

5 結語

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

[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] 袁勇，王飛躍. 區塊鏈技術發展現狀與展望［J］. 自動化學報， 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] 中國科學院深圳先進技術研究院. 一種區塊鏈時空數據查詢方法，系統及電子設備： 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] 中國地質大學（武漢）. 一種基于區塊鏈的時間序列數據組織記錄方法及系統： 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] 傅易文晉，陳華輝，錢江波，等. 面向時空數據的區塊鏈研究綜述［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] 張長貴，張巖峰，李曉華，等. 區塊鏈新技術綜述：圖型區塊鏈和分區型區塊鏈［J］. 計算機科學， 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。

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

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