PaperlayerView exact revision on arXiv

Source-linked AI summary

vChain: Enabling Verifiable Boolean Range Queries over Blockchain Databases

Cheng Xu, Ce Zhang, Jianliang Xu

arXiv:1812.02386v1cs.DBcs.CR

TL;DR

Blockchain users need queryable data without maintaining costly full replicas, but untrusted service providers cannot inherently guarantee result integrity. vChain combines an accumulator-based authenticated data structure with authenticated indexes and an inverted prefix tree for verifiable Boolean range and subscription queries. Security analysis and empirical evaluation validate the robustness and practicality of the techniques.

  • Problem

    Users need blockchain queries without maintaining costly full databases, yet outsourced processing lacks guaranteed result integrity when full nodes are untrusted.

  • Method

    vChain augments blocks with an accumulator-based authenticated data structure, intra- and inter-block indexes, and an inverted prefix-tree query index.

  • Results

    Security analysis and empirical study validate the robustness and practicality of the proposed techniques.

  • Takeaways & Limitations

    The framework supports verifiable Boolean range queries for lightweight users while reducing their storage and computing burden.

  • Takeaways & Limitations

    The framework leaves support for more complex analytics queries and privacy concerns as future research problems.

Abstract

from arXiv · show

Blockchains have recently been under the spotlight due to the boom of cryptocurrencies and decentralized applications. There is an increasing demand for querying the data stored in a blockchain database. To ensure query integrity, the user can maintain the entire blockchain database and query the data locally. However, this approach is not economic, if not infeasible, because of the blockchain's huge data size and considerable maintenance costs. In this paper, we take the first step toward investigating the problem of verifiable query processing over blockchain databases. We propose a novel framework, called vChain, that alleviates the storage and computing costs of the user and employs verifiable queries to guarantee the results' integrity. To support verifiable Boolean range queries, we propose an accumulator-based authenticated data structure that enables dynamic aggregation over arbitrary query attributes. Two new indexes are further developed to aggregate intra-block and inter-block data records for efficient query verification. We also propose an inverted prefix tree structure to accelerate the processing of a large number of subscription queries simultaneously. Security analysis and empirical study validate the robustness and practicality of the proposed techniques.

1 INTRODUCTION

Blockchain databases create growing demand for queries, but outsourced query processing cannot guarantee result integrity when trusted parties are absent. vChain addresses this by combining authenticated structures and verifiable processing for lightweight users.

  • Blockchain databases store timestamped records used in applications including finance, supply chains, and patent management.
  • Existing blockchain database solutions assume a trusted party to execute SQL-like queries, leaving query-result integrity unexplored when that assumption fails.
  • Maintaining a full blockchain copy can require substantial resources, including at least 200GB of disk space for a Bitcoin full node.
  • vChain augments each block with an authenticated data structure so untrusted full nodes can return verification objects for light-node result checking.
  • The accumulator-based authenticated data structure supports dynamic aggregation over arbitrary numerical and set-valued query attributes.
  • Two authenticated indexes aggregate intra-block and inter-block records, while a query index handles many subscription queries simultaneously.

2 RELATED WORK

Prior work covers blockchain infrastructure and verifiable queries, but existing approaches mainly target outsourced databases or constrained streaming scenarios. vChain builds on authenticated data structures for blockchain-specific queries.

  • Blockchain: A blockchain is a sequence of blocks containing transaction records and Merkle hash trees, with headers linking blocks and recording consensus information.
  • Blockchain: Database vendors and startups have integrated blockchains with database frontends that support user queries.
  • Verifiable Query Processing: Verifiable query research commonly uses circuit-based computation for general queries or authenticated data structures for specific queries.
  • Verifiable Query Processing: Authenticated-data-structure methods are generally more efficient for specific queries, whereas digital-signature approaches require signing every record and do not scale well.
  • Data Streams: Prior stream-query studies address one-time or subscription queries, but some require maintaining an MHT for all records or incur long query latency.

3 PROBLEM DEFINITION

vChain models a blockchain query system with miners, an untrusted service provider, and lightweight users, focusing on verifiable time-window and subscription Boolean range queries. The central design challenge is efficient authenticated verification under constrained user resources.

  • System Model: The system model contains miners, service providers, and query users; miners and service providers maintain full databases, while users retain block headers.
  • Data Model: Blockchain data are modeled as temporal objects with timestamps, numerical attributes, and set-valued attributes, with an ADS embedded into each block.
  • Time-Window Queries: Time-window queries combine temporal ranges, multidimensional numerical ranges, and monotone Boolean conditions on set-valued attributes.
  • Time-Window Queries: A Bitcoin example retrieves transactions from May to June 2018 with transfer amounts above 10 and specified sender and receiver addresses.
  • Subscription Queries: Subscription queries omit the temporal range and continuously return matching objects until deregistration.
  • Threat Model: The threat model requires soundness and completeness against an untrusted service provider that may return tampered or incomplete results.
  • Design Challenge: The main challenge is designing a blockchain-compatible ADS that enables small-bandwidth verification objects and fast verification for both query types.

4 PRELIMINARIES

This section introduces the cryptographic primitives underlying vChain, including hashes, bilinear pairings, multiset accumulators, and disjointness proofs.

  • Cryptographic hash functions map arbitrary-length strings to fixed-length bit strings and are collision resistant.
  • A bilinear pairing maps elements from two cyclic groups into a third group and provides the basic operation for the multiset accumulator.
  • The constructions rely on q-SDH and q-DHE assumptions as cryptographic security foundations.
  • A multiset accumulator compactly represents multisets, including repeated elements, as a group element.
  • The accumulator supports proving that two multisets are disjoint through probabilistic polynomial-time algorithms for setup, proof generation, and verification.

5 BASIC SOLUTION

The basic vChain solution combines accumulator-based authenticated data structures with verification objects and indexes to support verifiable Boolean and range queries. Its second accumulator construction enables aggregation, but requires a substantially larger public key.

  • Traditional Merkle hash trees are unsuitable because arbitrary attribute queries may require exponentially many trees and set-valued attributes are difficult to support.
  • vChain extends each block with an AttDigest generated during mining, enabling a full node to construct verification objects for light-node query verification.
  • AttDigest summarizes attributes in constant size and supports aggregation across multiple objects within or across blocks.
  • For a mismatching object, the service provider supplies a set-disjointness proof, which the user verifies against the object’s accumulated attribute digest.
  • Construction 2 aggregates accumulative values and disjointness proofs, but its public-key size scales with the largest possible attribute value rather than the largest multiset size.
  • Numerical range conditions are transformed into set-valued attributes, allowing range queries to map to Boolean queries.

6 BATCH VERIFICATION

vChain improves verification efficiency by aggregating mismatching objects within blocks and across blocks. Its intra-block and inter-block indexes organize authenticated data for pruning and batch proof generation.

  • Indexing for Batch Verification: The batch-verification framework introduces intra-block and inter-block authenticated indexes to aggregate mismatching objects during query processing.The techniques support online batch verification and allow the service provider to prove mismatching objects together.
  • Intra-Block Index: The intra-block index organizes each block’s objects in a binary Merkle tree whose nodes store hashes, attribute multisets, and accumulator digests.Non-leaf nodes aggregate child attribute multisets and compute corresponding accumulator values.
  • Intra-Block Index: During intra-block queries, matching subtrees are explored, while nodes whose attribute multisets fail the query receive disjoint proofs and are pruned.Matching objects are returned at leaf nodes, and verification objects contain the information needed to reconstruct the Merkle root.
  • Inter-Block Index: The inter-block index uses exponentially sized skips containing skipped-block hashes, aggregate attribute multisets, and accumulator digests.An eligible skip can represent multiple blocks that all mismatch a query, reducing block accesses and verification cost.
  • Inter-Block Index: Inter-block query processing scans skips from largest to smallest and adds mismatch proofs and skipped hashes to the verification object.If no mismatch skip is found, the procedure invokes intra-block querying for the current block before examining earlier blocks.

7 VERIFIABLE SUBSCRIPTION QUERIES

vChain supports scalable subscription queries with an inverted prefix tree and lazy authentication. The IP-Tree shares mismatch proofs across queries, while lazy authentication delays proof generation and aggregates it across blocks.

  • Subscription Processing: Subscription queries are continuously processed after registration, with results and verification objects published as new blocks are confirmed.The section addresses both large-scale query indexing and reduced verification costs.
  • IP-Tree Index: The IP-Tree combines a prefix tree with inverted files for numerical range and Boolean set conditions to share mismatch proofs across subscription queries.This design targets the overhead of generating separate proofs when queries mismatch for the same reason.
  • IP-Tree Index: IP-Tree processing traverses the path covering each arriving object and classifies associated queries using range and Boolean-condition information.Full-cover queries may produce results or mismatches, while partial-cover queries are handled through further subdivision.
  • Lazy Authentication: Lazy authentication returns results only when a matching object arrives or a time threshold passes, instead of immediately proving every mismatch.This optimization targets applications without real-time requirements.
  • Lazy Authentication: Lazy authentication uses the inter-block index to incrementally aggregate mismatch proofs and share them across subscription queries.It avoids both per-query proof generation and concentrating all proof work at the time of a matching result.
  • Lazy Authentication: Unlike time-window queries, subscription queries cannot back-traverse unavailable future blocks, so a stack tracks arrived blocks for incremental proof aggregation.The distinction arises because future objects may share mismatch conditions that are not yet known.

8 SECURITY ANALYSIS

The security analysis formalizes accumulator and query-authentication unforgeability. The paper proves that malicious service providers have negligible probability of forging disjoint proofs or incorrect query results.

  • Security Definitions: The analysis formalizes security notions for multiset accumulators, set-disjoint proofs, and query-authentication algorithms.The query-authentication definition covers both time-window and subscription queries.
  • Accumulator Security: Accumulator unforgeability requires that no polynomial-time adversary can produce an accepted disjoint proof for multisets with a nonempty intersection.This property makes the success probability negligible.
  • Accumulator Security: The paper states that accumulator unforgeability provides the foundation for securing the query-authentication algorithms.The corresponding construction is claimed to satisfy the defined accumulator security property.
  • Query Authentication: Query-authentication unforgeability rules out accepted results containing nonexistent objects, query-invalid objects, or omitted valid objects.The definition applies to results and verification objects produced for supported query types.
  • Query Authentication: The paper states that its query-authentication algorithms satisfy the defined unforgeability property.Detailed proofs are referenced in Appendix C.

9 PERFORMANCE EVALUATION

Experiments evaluate vChain on three datasets using processing time, verification time, and verification-object size. Indexing and lazy authentication generally improve query performance, while some gains trade service-provider computation for lower user cost.

  • Experimental Setup: The evaluation uses Foursquare, Weather, and Ethereum datasets and measures SP CPU time, user CPU time, and verification-object size.The experiments average results over 20 randomly generated queries.
  • Experimental Setup: The miner constructs ADSs with no index, an intra-block index, or both intra-block and inter-block indexes, using two accumulator constructions.The resulting comparison contains six schemes.
  • Setup Cost: ADS size ranges from 2.6KB to 11.1KB per block across indexes and datasets.The size is independent of the accumulator used.
  • Time-Window Queries: Index-based schemes are at least 2X better than the same-accumulator scheme without indexes for 4SQ and ETH time-window queries.Index-based costs increase only sublinearly as the query window expands.
  • Time-Window Queries: The combined intra- and inter-block scheme is generally no worse than the intra-only scheme, except in SP CPU time for 4SQ.Larger multisets used in inter-block disjoint proofs increase SP CPU time, while ETH gains more from skip-list use.
  • Subscription Queries: The IP-Tree reduces subscription-query SP overhead by at least 50% in all tested cases.The gain is more substantial for ETH because its data distribution is sparser.
  • Subscription Queries: Lazy authentication performs much better than real-time schemes in user CPU time, with CPU time and verification-object size increasing sublinearly with subscription-period length.Its SP CPU time is generally worse because aggregation requires additional service-provider computation.

10 CONCLUSION

The paper introduces vChain for verifiable Boolean range queries over blockchain databases and develops authenticated structures and indexes for efficient processing. Security analysis and empirical results support the framework’s practical implementability, while broader analytics, scalability, and privacy remain open directions.

  • vChain addresses verifiable query processing over blockchain databases for lightweight users.
  • Its accumulator-based authenticated data structure enables dynamic aggregation by transforming numerical attributes into set-valued attributes.
  • Tree-based intra-block, skip-list-based inter-block, and prefix-tree-based subscription indexes support query processing and subscription queries.
  • Security analysis and empirical results substantiate the robustness and practical implementability of the proposed techniques.
  • Open problems include more complex analytics, hardware-based scalability, and privacy in query processing.

B PROOF OF THEOREM 8.1

Theorem 8.1 establishes unforgeability for the multiset accumulator constructions. The second construction is proved by contradiction: a valid disjointness proof for intersecting multisets would violate the q-DHE assumption.

  • Theorem 8.1 states that the multiset accumulator constructions satisfy the unforgeability security property.
  • The proof for the second construction assumes an adversary produces intersecting multisets with a valid set-disjoint proof.
  • The intersection yields a nonzero polynomial relation involving Csq and Q(s), contradicting the assumed disjointness proof.
  • The contradiction violates the q-DHE assumption, establishing the theorem for the second construction.

C PROOF OF THEOREM 8.2

Theorem 8.2 states that the query authentication algorithms satisfy unforgeability. Verification uses synchronized latest block headers and multiset accumulative values covering the query window or subscription period to detect missing objects.

  • Theorem 8.2 states that the proposed query authentication algorithms satisfy the unforgeability security property.
  • A contradiction proof considers a result containing an object absent from the authentic object set.
  • The light-node verifier synchronizes block headers and checks results against the latest header.
  • Multiset accumulative values covering the full query window or subscription period expose missing objects during verification.

D.1 Comparison with MHT

The experiments compare vChain’s accumulator-based solutions with MHT-based construction costs and evaluate query performance across selectivity and SkipList settings. vChain maintains low authenticated-data overhead and efficient query behavior across the tested settings.

  • Comparison with MHT: MHT construction time increases dramatically with dimensionality because it builds an MHT for every attribute combination.
  • Comparison with MHT: vChain’s solutions use a negligible fixed-size ADS, whereas MHT space overhead grows exponentially with dimensionality.
  • Comparison with MHT: When dimensionality exceeds 3, MHT ADS overhead reaches more than 10X–1,000X the original block size.
  • Impact of Selectivity: Across datasets, increasing selectivity generally decreases service-provider CPU time while leaving user CPU time largely unchanged.
  • Impact of Selectivity: Increasing selectivity slightly increases verification-object size because more query results introduce more hashes.
  • Impact of SkipList: Inter-block indexing monotonically reduces user CPU time and verification-object size by aggregating mismatching objects.
Loading 1812.02386v1…