Efficient and Verifiable Query Mechanism of DAG Blockchain Based on Learned Index

Chang Jian; Lin Licheng; Li Binhong; Xiao Jiang; Jin Hai

doi:10.7544/issn1000-1239.202330272

Journal of Computer Research and Development > 2023 > 60(11): 2455-2468. > DOI: 10.7544/issn1000-1239.202330272 CSTR: 32373.14.issn1000-1239.202330272

Chang Jian, Lin Licheng, Li Binhong, Xiao Jiang, Jin Hai. Efficient and Verifiable Query Mechanism of DAG Blockchain Based on Learned Index[J]. Journal of Computer Research and Development, 2023, 60(11): 2455-2468. DOI: 10.7544/issn1000-1239.202330272

Citation:

PDF (1573 KB)

Efficient and Verifiable Query Mechanism of DAG Blockchain Based on Learned Index

School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074
National Engineering Research Center for Big Data Technology and System (Huazhong University of Science and Technology), Wuhan 430074
Key Laboratory of Services Computing Technology and System (Huazhong University of Science and Technology), Ministry of Education, Wuhan 430074
Key Laboratory of Cluster and Grid Computing (Huazhong University of Science and Technology), Wuhan 430074

Funds: This work was supported by the National Key Research and Development Program of China (2021YFB2700700), the Key Research and Development Program of Hubei Province (2021BEA164), the National Natural Science Foundation of China (62072197), and the Key Research and Development Program of Guangdong Province (2020B0101090005).

More Information

Author Bio:
Chang Jian: born in 1992. PhD candidate. His main research interests include blockchain, machine learning, and distributed systems

Lin Licheng: born in 2000. Master candidate. His main research interests include blockchain, machine learning, and distributed systems

Li Binhong: born in 1998. Master candidate. His main research interests include blockchain, machine learning, and distributed systems

Xiao Jiang: born in 1988. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include blockchain and distributed systems

Jin Hai: born in 1965. PhD, professor, PhD supervisor. Vice chairman of CCF, fellow of CCF. His main research interest includes distributed systems
Received Date: April 02, 2023
Revised Date: June 11, 2023
Available Online: July 12, 2023

Graphical Abstract

Abstract

Abstract

Blockchain system has been broadly applied and studied in the last few years with query being essential to facilitate a wide range of blockchain application scenarios such as data provenance in the logistics chain. As blockchain data continues to grow, the efficiency and verifiability of data query have become hot issues in blockchain research. The high concurrent blocks of the DAG-based blockchain make it difficult for queries to traverse sequentially like the traditional chain structure. Breadth-first or depth-first query strategies can be adopted according to the DAG structure, but this method has the problems of low efficiency and poor verification. We propose an efficient and verifiable query mechanism, called Lever, for DAG-based blockchains based on the learned index. The mechanism aims to improve the efficiency and verifiability of blockchain query by introducing learned index technology with the data distribution characteristic to optimize the indexing process in the blockchain. Learned index is a novel indexing technology that reduces the storage space and query time of indexes by learning the distribution of data. In this paper, learned index is applied to the mapping between epoch height and timestamp of the DAG-based blockchain, greatly improving query speed and efficiency. At the same time, in order to speed up the data filtering of multiple blocks in an epoch, a Bloom filter is added to the block header, and an aggregated Bloom filter is produced by miner for each epoch. In addition, to guarantee the authentication (i.e., correctness and completeness) of query results, the mechanism introduces a sorted Merkle tree to perform proof with the Merkle tree branch by combining the filtering and sorting processes, effectively reducing the size of the verification object (VO), thereby enhancing the verifiability of blockchain query. Experimental results show that Lever can effectively improve the efficiency and verifiability of DAG-based blockchain query, and Lever improves query performance by up to 10 times and reduces VO size overhead by 90% compared with the basic query mechanism of Conflux.
- DAG blockchain,
- verifiable query,
- learned index,
- aggregated Bloom filter,
- sorted Merkle tree

FullText(HTML)

References (30)

References

[1]	Nakamoto S. Bitcoin: A peer-to-peer electronic cash system [EB/OL]. [2019-09-27].https://bitcoin.org/bitcoin.pdf
[2]	Popov S. The tangle [EB/OL]. [2020-02-17]. http://www.descryptions.com/Iota.pdf
[3]	Churyumov, A. Byteball: A decentralized system for storage and transfer of value [EB/OL]. [2021-07-02].https://byteball.org/Byteball.pdf
[4]	Li Chenxing, Li Peilun, Zhou Dong, et al. A decentralized blockchain with high throughput and fast confirmation [C] //Proc of the USENIX Annual Technical Conf (ATC). Berkeley, CA: USENIX Association, 2020: 515−528
[5]	Xu Rui, Liu Zihao, Hu Huiqi, et al. An efficient secondary index for spatial data based on LevelDB [C] //Proc of the 25th Int Conf on Database Systems for Advanced Applications (DASFAA). Berlin: Springer, 2020: 750−754
[6]	于戈,聂铁铮,李晓华,等. 区块链系统中的分布式数据管理技术——挑战与展望[J]. 计算机学报,2021,44(1):28−53 Yu Ge, Nie Tiezheng, Li Xiaohua, et al. The challenge and prospect of distributed data management techniques in blockchain systems[J]. Chinese Journal of Computers, 2021, 44(1): 28−53 (in Chinese)
[7]	Chen Huashan, Pendleton M, Njilla L, et al. A survey on ethereum systems security: Vulnerabilities, attacks, and defenses[J]. ACM Computing Surveys, 2020, 53(3): 1−43
[8]	Jin Hai, Xiao Jiang. Towards trustworthy blockchain systems in the era of “Internet of value”: Development, challenges, and future trends[J]. Science China Information Sciences, 2022, 65: 1−11
[9]	Wang Qing, Lu Youyou, Shu Jiwu. Sherman: A write-optimized distributed B+ Tree index on disaggregated memory [C] //Proc of the 2022 Special Interest Group on Management of Data (SIGMOD). New York: ACM, 2022: 1033−1048
[10]	张洲,金培权,谢希科. 学习索引:现状与研究展望[J]. 软件学报,2021,32(4):1129−1150 doi: 10.13328/j.cnki.jos.006168 Zhang Zhou, Jin Peiquan, Xie Xike. Learned indexes: Current situations and research prospects[J]. Journal of Software, 2021, 32(4): 1129−1150 (in Chinese) doi: 10.13328/j.cnki.jos.006168
[11]	Chang Jian, Li Binhong, Xiao Jiang, et al. Anole: A lightweight and verifiable learned-based index for time range query on blockchain systems [C] //Proc of the 28th Int Conf on Database Systems for Advanced Applications (DASFAA). Berlin: Springer, 2023: 519−534
[12]	周炜,王超,徐剑,等. 基于区块链的隐私保护去中心化联邦学习模型[J]. 计算机研究与发展,2022,59(11):2423−2436 doi: 10.7544/issn1000-1239.20220470 Zhou Wei, Wang Chao, Xu Jian, et al. Privacy-Preserving and decentralized federated learning model based on the blockchain[J]. Journal of Computer Research and Development, 2022, 59(11): 2423−2436 (in Chinese) doi: 10.7544/issn1000-1239.20220470
[13]	贾大宇,信俊昌,王之琼,等. 存储容量可扩展区块链系统的高效查询模型[J]. 软件学报,2019,30(9):2655−2670 doi: 10.13328/j.cnki.jos.005774 Jia Dayu, Xin Junchang, Wang Zhiqiong, et al. ElasticQM: A query model for storage capacity scalable blockchain system[J]. Journal of Software, 2019, 30(9): 2655−2670 (in Chinese) doi: 10.13328/j.cnki.jos.005774
[14]	Ruan Pingcheng, Chen Gang, Dinh T T A, et al. Fine-grained, secure and efficient data provenance on blockchain systems[J]. Proceedings of the VLDB Endowment, 2019, 12(9): 975−988 doi: 10.14778/3329772.3329775
[15]	Zhang Ce, Xu Cheng, Xu Jianliang, et al. GEM²-Tree: A gas-efficient structure for authenticated range queries in blockchain [C] //Proc of the 35th Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2019: 842−853
[16]	蔡磊,朱燕超,郭庆兴,等. 面向区块链的高效物化视图维护和可信查询[J]. 软件学报,2020,31(3):680−694 doi: 10.13328/j.cnki.jos.005914 Cai Lei, Zhu Yanchao, Guo Qingxing, et al. Efficient materialized view maintenance and trusted query for blockchain[J]. Journal of Software, 2020, 31(3): 680−694 (in Chinese) doi: 10.13328/j.cnki.jos.005914
[17]	Gupta H, Hans S, Aggarwal K, et al. Efficiently processing temporal queries on hyperledger fabric [C] //Proc of the 34th Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2018: 1489−1494
[18]	Xu Cheng, Zhang Ce, Xu Jianliang. vChain: Enabling verifiable Boolean range queries over blockchain databases [C] //Proc of the 2019 Special Interest Group on Management of Data (SIGMOD). New York: ACM, 2019: 141−158
[19]	Dai Xiaohai, Xiao Jiang, Yang Wenhui, et al. LVQ: A lightweight verifiable query approach for transaction history in bitcoin [C] //Proc of the 40th Int Conf on Distributed Computing Systems (ICDCS). Piscataway, NJ: IEEE, 2020: 1020−1030
[20]	Zhang Ce, Xu Cheng, Wang Haixin, et al. Authenticated keyword search in scalable hybrid-storage blockchains [C] //Proc of the 37th Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2021: 996−1007
[21]	Hao Kun, Xin Junchang, Wang Zhiqiong, et al. Outsourced data integrity verification based on blockchain in untrusted environment[J]. World Wide Web, 2020, 23(4): 2215−2238 doi: 10.1007/s11280-019-00761-2
[22]	Shao Qifeng, Pang Shuaifeng, Zhang Zhao, et al. Authenticated range query using SGX for blockchain light clients [C] //Proc of the 25th Int Conf on Database Systems for Advanced Applications (DASFAA). Berlin: Springer, 2020: 306−321
[23]	Li Yang, Zheng Kai, Yan Ying, et al. EtherQL: A query layer for blockchain system [C] //Proc of the 22nd Int Conf on Database Systems for Advanced Applications (DASFAA). Berlin: Springer, 2017: 556−567
[24]	Peng Zhe, Wu Haotian, Xiao Bin, et al. VQL: Providing query efficiency and data authenticity in blockchain systems [C] //Proc of the 35th Int Conf on Data Engineering Workshops (ICDEW). Piscataway, NJ: IEEE, 2019: 1−6
[25]	Zhu Yanchao, Zhang Zhao, Jin Cheqing, et al. SEBDB: Semantics empowered blockchain database [C] //Proc of the 35th Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2019: 1820−1831
[26]	张长贵,张岩峰,李晓华,等. 区块链新技术综述:图型区块链和分区型区块链[J]. 计算机科学,2020,47(10):2423−2436 Zhang Changgui, Zhang Yanfeng, Li Xiaohua, et al. Survey of new blockchain techniques: DAG based blockchain and sharding based blockchai[J]. Computer Science, 2020, 47(10): 2423−2436 (in Chinese)
[27]	Yu Haifeng, Nikoli´c I, Hou Ruomu, et al. OHIE: Blockchain scaling made simple [C] //Proc of the 2020 IEEE Symp on Security and Privacy (S&P). Piscataway, NJ: IEEE, 2020: 90−105
[28]	Kraska T, Beutel A, Chi E H, et al. The case for learned index structures [C] //Proc of the 2018 Special Interest Group on Management of Data (SIGMOD). New York: ACM, 2018: 489−504
[29]	许可,李彦彪,谢高岗,等. 基于混合计数布隆过滤器的高效数据名查找方法[J]. 计算机研究与发展,2023,60(5):1136−1150 Xu Ke, Li Yanbiao, Xie Gaogang, et al. Efficient name lookup using hybrid counting Bloom filters[J]. Journal of Computer Research and Development, 2023, 60(5): 1136−1150 (in Chinese)
[30]	Athanassoulis M, Ailamaki A. BF-tree: Approximate tree indexing[J]. Proceedings of the VLDB Endowment, 2014, 7(14): 1881−1892 doi: 10.14778/2733085.2733094

[1]	Wang Haotian, Ding Yan, He Xianhao, Xiao Guoqing, Yang Wangdong. SparseMode: A Sparse Compiler Framework for Efficient SpMV Vectorized Code Generation[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202550139
[2]	Yan Zhiyuan, Xie Biwei, Bao Yungang. HVMS: A Hybrid Vectorization-Optimized Mechanism of SpMV[J]. Journal of Computer Research and Development, 2024, 61(12): 2969-2984. DOI: 10.7544/issn1000-1239.202330204
[3]	Feng Jingge, He Yeping, Tao Qiuming, Ma Hengtai. SLP Vectorization Method Based on Multiple Isomorphic Transformations[J]. Journal of Computer Research and Development, 2023, 60(12): 2907-2927. DOI: 10.7544/issn1000-1239.202220354
[4]	Li Xiaodan, Wu Wenling, Zhang Li. Efficient Search for Optimal Vector Permutations of uBlock-like Structures[J]. Journal of Computer Research and Development, 2022, 59(10): 2275-2285. DOI: 10.7544/issn1000-1239.20220485
[5]	Chen Yu, Liu Zhongjin, Zhao Weiwei, Ma Yuan, Shi Zhiqiang, Sun Limin. A Large-Scale Cross-Platform Homologous Binary Retrieval Method[J]. Journal of Computer Research and Development, 2018, 55(7): 1498-1507. DOI: 10.7544/issn1000-1239.2018.20180078
[6]	Li Junnan, Yang Xiangrui, Sun Zhigang. DrawerPipe: A Reconfigurable Packet Processing Pipeline for FPGA[J]. Journal of Computer Research and Development, 2018, 55(4): 717-728. DOI: 10.7544/issn1000-1239.2018.20170927
[7]	Zhao Jianghua, Mu Shuting, Wang Xuezhi, Lin Qinghui, Zhang Xi, Zhou Yuanchun. Crowdsourcing-Based Scientific Data Processing[J]. Journal of Computer Research and Development, 2017, 54(2): 284-294. DOI: 10.7544/issn1000-1239.2017.20160850
[8]	Luo Zhangqi, Huang Kun, Zhang Dafang, Guan Hongtao, Xie Gaogang. A Many-Core Processor Resource Allocation Scheme for Packet Processing[J]. Journal of Computer Research and Development, 2014, 51(6): 1159-1166.
[9]	Wen Shuguang, Xie Gaogang. libpcap-MT: A General Purpose Packet Capture Library with Multi-Thread[J]. Journal of Computer Research and Development, 2011, 48(5): 756-764.
[10]	Tian Daxin, Liu Yanheng, Li Yongli, Tang Yi. A Fast Matching Algorithm and Conflict Detection for Packet Filter Rules[J]. Journal of Computer Research and Development, 2005, 42(7): 1128-1135.