面向时空数据的区块链构建及查询方法
时间：2023-02-21 12:25:07 来源：千叶帆 本文已影响人
华亚洲，丁琳琳，陈泽，王俊陆，朱珠
面向时空数据的区块链构建及查询方法
华亚洲，丁琳琳*，陈泽，王俊陆，朱珠
（辽宁大学 信息学院，沈阳 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%以上。所提方法能够实现时空数据的快速存储及查询，可以有效支持时空数据的管理。
区块链；
时空数据；
存储架构；
索引结构；
查询算法
近年来，随着比特币［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 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 问题描述
本文要解决的问题是：基于时空数据的区块链构建及查询。一方面，当区块链系统产生大量时空数据后，能够实现数据快速上链并为其提供防篡改证明；
另一方面，当时空数据存储到区块链后，能够支持时空数据的查询并能够提高时空数据的查询效率，并且支持多类型的时空数据查询，例如单值查询、范围查询等以满足用户的查询需求。
本章主要从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 fourass 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相较于传统的单链式存储结构具有更高的安全性。
本章基于所构建的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.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 多区块下单值查询与范围查询比较
本文介绍了时空数据的应用场景，指出了目前时空数据管理存在的数据不透明等问题，提出将区块链技术用于时空数据管理，但传统的区块链技术对时空数据的支持度有限，为此提出了一种改进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会员，主要研究方向：物流与供应链、区块链。
