基于状态树的链上数据高效可信查询索引模型及方法
作者:
作者单位:

大连理工大学 软件学院,辽宁 大连 116620

作者简介:

原旭(1970—),男,副教授,主要从事人工智能与区块链、工业互联网方向研究,(E-mail) david@dlut.edu.cn。

通讯作者:

陈志奎(1968—),男,博士,教授,主要从事大数据计算、物联网和人工智能方向研究,(E-mail) zkchen@dlut.edu.cn。

中图分类号:

TP311

基金项目:

国家自然科学基金项目资助(62076047);中央高校基本科研业务费专项资金资助(DUT20LAB136,DUT20TD107)。


Efficient and trusted query index model and method for blockchain data based on Merkle Patricia tree
Author:
Affiliation:

School of Software Technology, Dalian University of Technology, Dalian, Liaoning 116620, P. R. China

Fund Project:

Supported by National Natural Science Foundation of China (62076047), and the Fundamental Research Funds for the Central Universities (DUT20LAB136, and DUT20TD107).

  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [16]
  • |
  • 相似文献
  • | | |
  • 文章评论
    摘要:

    区块链技术以其去中心化,不可篡改等特性在分布式数据管理领域中逐渐得到关注。但区块链系统在数据查询处理方面存在查询功能单一、效率低以及查询可信性难以保证等问题。笔者基于以太坊状态树的设计思路,在保证索引不可篡改的前提下,提出一种全局索引结构KMPT,可一次定位目标区块,避免了遍历区块的检索过程,同时结合块内索引TMPT,实现了基于内容的高效区块链数据检索。经实验验证,相比于仅构建块内索引的方法,该索引模型在可接受的索引构建代价内极大提升了查询检索的效率和稳定性,还可同时提供查询数据存在或不存在证明,提升了查询结果的可信性。

    Abstract:

    Blockchain technology has attracted significantly attention in the field of distributed data management because of its decentralized and immutable nature. However, current blockchain systems face limitations in data query processing including single query function, low query efficiency and difficulties in ensuring query credibility. To address these challenges, in this paper, a global index structure called KMPT is proposed, inspired by the design concept of Ethereum Merkle Patricia tree on the premise of ensuring the immutability of index. The KMPT structure aims to realize the function of locating the target block at one time, avoiding the retrieval process of traversing blocks. Furthermore, by incorporating the intra-block index TMPT, the proposed approach enables high-efficiency content-based blockchain data retrieval. Experiments demonstrate that, compared with the method of only building intra block index, the proposed index model significantly improved the efficiency and stability of query retrieval within the acceptable index construction cost. In addition, it can provide the proof of existence or non-existence of data query at the same time, enhancing the credibility of query results.

    参考文献
    [1] Nakamoto S. Bitcoin: a peer-to-peer electronic cash system [EB/OL]. [2021-05-12]. https://www.bitcoinpaper.info/bitcoinpaper-html/.
    [2] Buterin V. Ethereum: a next-generation smart contract and decentralized application platform[EB/OL]. [2021-05-12]. https://courses.cs.duke.edu/spring23/compsci512/papers/ethereum.pdf.
    [3] 袁勇, 王飞跃. 区块链技术发展现状与展望[J]. 自动化学报, 2016, 42(4): 481-494.Yuan Y, Wang F. Blockchain: the state of the art and future trends[J]. Acta Automatica Sinica, 2016, 42(4): 481-494. (in Chinese)
    [4] Bamakan S M H, Motavali A, Bondarti A B. A survey of blockchain consensus algorithms performance evaluation criteria[J]. Expert Systems With Applications, 2020, 154: 113385.
    [5] Tikhomirov S. Ethereum: state of knowledge and research perspectives[C]//International Symposium on Foundations and Practice of Security. Cham: Springer, 2018: 206-221.
    [6] Wood G. Ethereum: a secure decentralised generalised transaction ledger[EB/OL]. [2021-05-12]. https://www.win.tue.nl/~mholende/seminar/references/ethereum_yellowpaper.pdf.
    [7] 于戈, 聂铁铮, 李晓华, 等. 区块链系统中的分布式数据管理技术: 挑战与展望[J]. 计算机学报, 2021, 44(1): 28-54.Yu G, Nie T Z, Li X H, et al. The challenge and prospect of distributed data management techniques in blockchain systems[J]. Chinese Journal of Computers, 2021, 44(1): 28-54. (in Chinese)
    [8] 王千阁, 何蒲, 聂铁铮, 等. 区块链系统的数据存储与查询技术综述[J]. 计算机科学, 2018, 45(12): 12-18.Wang Q G, He P, Nie T Z, et al. Survey of data storage and query techniques in blockchain systems[J]. Computer Science, 2018, 45(12): 12-18. (in Chinese)
    [9] Li Y, Zheng K, Yan Y, et al. EtherQL: a query layer for blockchain system[C]//International Conference on Database Systems for Advanced Applications. Cham: Springer, 2017: 556-567.
    [10] Muzammal M, Qu Q, Nasrulin B, et al. A blockchain database application platform[EB/OL]. 2018 [2021-05-12]. https://arxiv.org/abs/1808.05199.
    [11] Peng Y Q, Du M, Li F F, et al. FalconDB: blockchain-based collaborative database[C]//Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, June 14-19, 2020, Portland, OR, USA. New York: ACM, 2020: 637-652.
    [12] 焦通, 申德荣, 聂铁铮, 等. 区块链数据库: 一种可查询且防篡改的数据库[J]. 软件学报, 2019, 30(9): 2671-2685.Jiao T, Shen D R, Nie T Z, et al. BlockchainDB: querable and immutable database[J]. Journal of Software, 2019, 30(9): 2671-2685. (in Chinese)
    [13] 贾大宇, 信俊昌, 王之琼, 等. 存储容量可扩展区块链系统的高效查询模型[J]. 软件学报, 2019, 30(9): 2655-2670.Jia D Y, Xin J C, Wang Z Q, et al. Efficient query model for storage capacity scalable blockchain system[J]. Journal of Software, 2019, 30(9): 2655-2670. (in Chinese)
    [14] Zhang C, Xu C, Xu J L, et al. GEM^2-tree: a gas-efficient structure for authenticated range queries in blockchain[C]//2019 IEEE 35th International Conference on Data Engineering (ICDE), April 8-11, 2019, Macao, China. IEEE, 2019: 842-853.
    [15] 郑浩瀚, 申德荣, 聂铁铮, 等. 面向混合索引的区块链系统的可查询性优化[J]. 计算机科学, 2020, 47(10): 301-308.Zheng H H, Shen D R, Nie T Z, et al. Queryability optimization of blockchain system for hybrid index[J]. Computer Science, 2020, 47(10): 301-308. (in Chinese)
    [16] Abdennebi A, Kaya K. A bloom filter survey: variants for different domain applications[EB/OL]. 2021-06-23 [2021-07-12]. https://arxiv.org/abs/2106.12189.
    相似文献
    引证文献
引用本文

原旭,黄笠煌,陈志奎,于硕.基于状态树的链上数据高效可信查询索引模型及方法[J].重庆大学学报,2023,46(7):9-22.

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-08-12
  • 在线发布日期: 2023-08-02
文章二维码