Query Processing On Blockchain Systems

Blockchain is a distributed ledger co-maintained by multiple participants.The query service provided by it must satisfy the requirements that the ledger data are immutable and valid,and query results have not been tampered with and are verifiable.To ensure the integrity of the query results,queries in blockchain systems are classified into two cate-gories:full-node query and light-node query.In particular,the full-node query requires the node which initiates a query to maintain a copy of blockchain data,while the light-node query erases such overhead for it only maintains the block headers to verify the integrity of results received from full nodes.For full-node query,blocks are usually stored either in a Key-Value store(e.g.,LevelDB)or in a file system,both of which support limited query types.Existing work supports richer queries on blocks by maintaining a copy of blocks in the off-chain database,introducing additional storage overhead.For the light-node query,traditional blockchain systems only support the existence of a single transaction or state To handle these issues,we focus on improving the performance of query processing on blockchain systems,and our main contributions are listed below1.To enrich query types for full node,we add relational semantics to blockchain,where all blocks are treated as relations with multiple attributes so that complex queries in RDBMS are also supported.We devise indexing mechanisms to hasten data access because the tuples belonging to a table are distributed in blocks according to the time when they are packaged,based on which basic operations in RDBMS are re-implemented to suit for blockchain,which greatly improves the query performance2.Because the light-node query cannot support the verification of the integrity of the range and the join query results at the same time,and the traditional authenticated data structure such as MB-tree is inefficient if directly used in blockchain,we design an efficient authenticated index structure AC-tree(Authenticated Compacted Tree)to support authenticated range and j oin query.In the AC-tree,data updates are written to the memory,and when the data size reaches a threshold,they are merged to the disk in a batch manner,thereby reducing the impact of index updates.Based on AC-tree,we also design AC*-tree to improve the query performance for time-window queries.Efficient authenticated join query is also supported based on AC-tree,AC*-tree.3.Since existing blockchain systems cannot support authenticated multi-dimensional aggregate range queries,we propose GCA2-tree(Generic Capacity-efficient Authenti-cated Aggregate Tree),an authenticated data structure based on cryptographic accumu-lators.GCA2-tree supports multi-dimensional aggregate range query for any combination of attributes,and the storage cost is linearly related to the query dimension.In addition,we propose two optimization strategies:batch processing and merging,which greatly reduce the network and verification overhead of light nodes.4.To solve the problem of insufficient query types and low performance of existing blockchain systems,we design and implement StarChain,a blockchain database with rich queries,by integrating key techniques,including full-node query optimization,authenti-cated range,join and aggregate queries for the light-node query.Extensive experiments carried out on a standard benchmark BChainBench show the effectiveness of the proposed methods.In summary,we focus on the function and performance deficiencies of the existing blockchain systems in query processing.We add relational semantics to blocks so that complex queries in RDBMS are also supported for a full node.To improve the query per-formance of full-node query,we propose novel index structures and re-implemented basic operations in RDBMS to suit blockchain.Besides,We propose several authenticated data structures to support authenticated range query,join query,and multi-dimensional aggre-gate range query.All the above technologies are integrated into the blockchain database system-StarChain to satisfy various query demands.Experimental results verify the ef-fectiveness of the methods proposed in this paper.