vChain: Enabling Verifiable Boolean Range Queries over Blockchain Databases
对这篇论文方案简单的翻译，以及罗列用到的数学工具
文章介绍
区块链数据库中对于查询数据的需求越来越大。
现存方案
现存的方案：为了保证查询的完整性，用户维护整个区块链数据库，并在本地查询数据。
现存方案的不足：由于区块链庞大的数据容量和可观的维护成本，这种方法即使不是不可行，也是不经济的。
文章提出的方案
迈出了研究区块链数据库上可验证查询处理问题的第一步。提出了一个新的框架，称为vChain，它减轻了用户的存储和计算成本，并使用可验证的查询来保证结果的完整性。
为了支持可验证的布尔范围查询，提出了一种基于累加器的验证数据结构，该结构支持对任意查询属性进行动态聚合。进一步开发了两个新的索引来聚合块内和块间的数据记录，以实现高效的查询验证。
还提出了一种反向前缀树结构来同时加速对订阅查询的大量误码率的处理。安全性分析和实证研究验证了所提技术的鲁棒性和实用性。
介绍---区块链介绍
自比特币加密货币问世以来，区块链技术受到了学术界和业界的广泛关注[1,2,5]。区块链本质上是默克哈希树(MHT)[19]的一种特殊形式，它被构造为一个块序列。如图2所示，每个块存储一个交易记录列表和建立在它们之上的MHT。每个区块的头部由四个部分组成:(i) PreBkHash，它是前一个区块的散列; (Ⅱ) TS，它是区块创建时的时间戳;(三)共识，由矿工组成，保证区块的协商一致;(iv) MerkleRoot，是MHT的根哈希。
共识协议通常基于 PreBkHash 和 merkleroot 计算，根据共识协议的不同而不同。在广泛使用的工作证明(PoW)共识协议中，consprove 是由矿工计算的一个nonce，其值为:hash(PreBkHash | TS | MerkleRoot | nonce)≤ Z，其中 Z 对应挖掘难度。当矿商发现了 nonce 后，它会将新区块打包并向整个网络广播。其他矿商会验证交易记录和新区块的nonce，一旦验证，就会将其添加到区块链。
为了解决区块链系统的各种问题，已经做出了大量的努力，包括系统协议[20,21]、共识算法[22,23]、安全性[24,25]、存储[7]和性能基准[4]。
最近，主要的数据库供应商，包括IBM [26]， Oracle[27]和sap[28]，都已经将区块链与他们的数据库管理系统集成在一起，他们允许用户通过数据库前端执行区块链查询。
此外，许多初创公司，如FlureeDB[10]、BigchainDB[11]和SwarmDB[12]，都在为去中心化应用开发基于区块链的数据库解决方案。
然而，它们通常将查询处理与底层区块链存储分开，并依赖可信的数据库服务器来保证查询完整性。
相反，我们提出的 vchain 解决方案将经过验证的数据结构构建到区块链结构中，这样即使是不可信的服务器也可以提供完整性保证的查询服务。
介绍---可验证查询处理的介绍
针对不可信的服务提供者的完整性结果的情况来说，可验证查询处理技术已被广泛研究。(例如，[14,15,16,17,18,29])。
现有的研究大多集中在外包数据库上，有两种典型的方法: 使用基于电路的可验证计算(VC)技术支持一般查询，使用经过验证的数据结构(ADS)支持特定查询。
基于 vc 的方法(如SNARKs[30])可以支持任意的计算任务，但代价是非常高的，有时是不切实际的开销。此外，它需要一个昂贵的预处理步骤，因为数据和查询程序都需要硬编码到证明密钥和验证密钥中。为了解决这个问题，Ben-Sasson等人。[31]开发了一种SNARKs的变体，其中的预处理步骤只依赖于数据库和查询程序的上限大小。最近，Zhang等人。[29]提出了一个vSQL系统，它利用了一个交互式协议来支持可验证的SQL查询。然而，它仅限于具有固定模式的关系数据库。
相比之下，基于 ADS 的方法通常更有效，因为它针对特定的查询进行定制。我们提出的解决方案属于这种方法。通常用于ADS的两种结构:数字签名和mht。
数字签名是基于非对称加密对数字消息的内容进行身份验证。为了支持可验证的查询，它要求每个数据记录都要签名，因此不能扩展到大型数据集[14]。
另一方面，MHT是建立在[19]层次树上的。叶节点中的每个条目被分配一个数据记录的散列摘要，内部节点中的每个条目被分配一个从子节点派生的摘要。数据所有者对MHT的root digest 进行签名，MHT可用于验证数据记录的任何子集。MHT已被广泛应用于各种指标结构中[15,16,17]。最近，有关于集值数据的可验证查询的研究[32,33,34,35,36]。另一个密切相关的研究方向是数据流的verifiablequery处理[37,38,39,40]。
然而，以前的研究[38,39]关注的是一次性查询来检索流数据的最新版本。[40]要求数据所有者为所有数据记录维护MHT，并存在较长的查询延迟，这不适用于实时流媒体服务。另一方面，[41,42,43]对数据流的订阅查询进行了研究。到目前为止，还没有工作考虑到区块链数据库上的订阅查询的完整性问题。
技术方案
上图，是该方案的系统模型，模型中主要有三种角色，矿工、服务提供商 以及 查询用户。
三者关系：
矿工 和 服务提供商 都是维护整个区块链数据库的全节点。
查询用户是一个轻量级节点，只存储跟踪区块头。
矿工 负责构造共识证明并将新的区块添加到区块链中。
服务提供商 为轻量级用户提供查询服务。
区块链中的存储的数据建模为时间对象块{o1, o2，···，on}的序列。
每个对象oi由⟨ti,Vi,Wi⟩表示，其中 ti 是对象的时间戳，Vi是表示一个或多个数字属性的多维向量，Wi是集值属性。
为了实现可验证的查询处理，一个经过验证的数据结构 (ADS) 由矿工构造并嵌入到每个块中。
主要有两种形式的布尔范围查询:时间窗口查询 ( Time-Window Queries ) 和订阅查询 ( subscription Queries ) 。
Time-Window Queries
用户可能希望搜索出现在某一时间段内的记录。
在这种情况下，可以发出一个时间窗口查询。
具体地说,一个时间窗口的形式查询 q =⟨(ts, te),(α,β),ϒ⟩,其中(ts, te)是一个时间范围选择谓词的时期,(α,β)是一个多维范围选择谓词的数值属性,和ϒ单调集值的布尔函数属性。
因此，SP返回所有对象，使得{oi = = ti,Vi,Wi⟩| ti∈[ts,te]∧Vi∈[α， β]∧ϒ(Wi) = 1}。
为简单起见，我们假设ϒ是连接范式(CNF)。
Subscription Queries
除了时间窗口查询外，用户还可以通过订阅查询注册他们的兴趣。具体地说，订阅查询的形式是q = ⟨−,[α, β], ϒ⟩,，其中[α， β]和ϒ与时间窗口查询中的查询条件相同。
反过来，SP连续地返回所有对象，例如{oi = = ti,Vi,Wi⟩| Vi∈[α， β]∧ϒ(Wi) = 1}，直到查询取消注册。
证明模型可用性的方法
安全性分析和实证研究验证了所提技术的鲁棒性和实用性。
j健全性（Soundness）：作为结果返回的对象都没有被篡改，并且它们都满足查询条件。
完整性（Completeness）：没有关于查询窗口或订阅期的有效结果缺失。
数学模型、技术方法：
- 累加器的验证数据结构 （accumulator-based authenticated data structure）
目的：支持可验证的布尔范围查询
基于累加器的ADSscheme，它将数值属性转换为集值属性，从而支持对任意查询属性的动态聚合。
- 反向前缀树结构 （inverted prefix tree structure）
目的：加速对订阅查询的大量误码率的处理、
- 加密哈希算法（Cryptographic Hash Function）
- 双线性配对（Bilinear Pairing）
设G和H是两个素数阶p的循环乘群。设g为G的产生器。一个双线性映射是一个函数e: G × G→h，具有以下性质:
• 双线性:如果u,v∈G, e(u,v)∈H，那么e(ua,vb) =e(u,v)ab对于任意u,v。
• 非简并性:e(g,g) = 1。
双线性配对将会是 多集合累加器 的基本操作。
- q-Strong Diffie-Hellman (q-SDH) Assumption
- q-Diffie-Hellman Exponent (q-DHE) Assumption
- Cryptographic Multiset Accumulator
- 时间窗口查询（Time-Window Queries）
指的是查询某一段时间内的在区块链上存储的数据。 查询的模型为：q = ⟨[ts, te],[α,β],ϒ⟩ 看上去很复杂，其实很简单 [ ] 中存放的查询条件是 范围，
ϒ 中存放的查询条件是 异或查询。 ⟨[2018-05, 2018-06], [10, +∞], send:1FFYc∧receive:2DAAf⟩ 代表的是 2018年5月 到 6月，大于 10，发送者是某，接收者是某的所有交易。
- 订阅查询
用户可以通过订阅查询注册他们感兴趣的数据。
订阅查询的形式是 q = ⟨−,[α, β], ϒ⟩,
功能：相当于持续在 持续请求访问。
未来方向
有许多有趣的研究问题值得进一步研究，例如，如何支持更复杂的分析查询;如何利用现代硬件(如多核和多核)来扩展性能;以及如何解决查询处理中的隐私问题。