微信服务号

微信订阅号

2025-4-24- 16
Home > Archive>Volume 34, Issue 11, 2023 >5312-5329. DOI:10.13328/j.cnki.jos.006748
PDF HTML XML Export Cite reminder
SMT: Efficient Authenticated Data Structure for Streaming Data on Blockchain
Author:
Affiliation:

Clc Number:

TP311

  • Article
    • | |
  • Metrics
    • |
  • Reference [31]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    The authenticated data structure (ADS) solves the problem of untrusted servers in outsourced data storage scenarios as users can verify the correctness and integrity of the query results returned by untrusted servers through the ADS. Nevertheless, the security of data owners is difficult to guarantee, and attackers can tamper with the ADS stored by data owners to impede the integrity and correctness verification of query results. Data owners can store the ADS on the blockchain to solve the above problem by leveraging the immutable nature of the blockchain. However, the existing ADS implementation schemes have high maintenance costs on the blockchain and most of them only support the verifiable query of static data. At present, an efficient ADS tailored to the blockchain is still to be designed. By analyzing the gas consumption mechanism of smart contracts and the gas consumption of the ADS based on the traditional Merkle hash tree (MHT), this study proposes SMT, a new ADS, which achieves efficient and verifiable query of streaming data and has a lower gas consumption on the blockchain. Finally, the study verifies the efficiency of SMT both theoretically and experimentally and proves the security of SMT through security analysis.

    Reference
    [1] Hacigumus H, Iyer B, Mehrotra M. Providing database as a service. In: Proc. of the 18th Int’l Conf. on Data Engineering. San Jose: IEEE, 2002. 29–38.
    [2] 胡钦超. 外包存储环境下完整性检测方案的研究 [硕士学位论文]. 成都: 电子科技大学, 2010.
    Hu QC. Research on integrity checking scheme in outsourced storage environment [MS. Thesis]. Chengdu: University of Electronic Science and Technology of China, 2010 (in Chinese with English abstract).
    [3] 张佳, 涂晓东. 基于外包存储的数据完整性检验的研究. 现代电信科技, 2009, 39(8): 41–45. [doi: 10.3969/j.issn.1002-5316.2009.08.011]
    Zhang J, Tu XD. Research on integrity checking of data based on outsourced storage. Modern Science & Technology of Telecommunications, 2009, 39(8): 41–45 (in Chinese with English abstract). [doi: 10.3969/j.issn.1002-5316.2009.08.011]
    [4] Li FF, Hadjieleftheriou M, Kollios G, Reyzin L. Dynamic authenticated index structures for outsourced databases. In: Proc. of the 2006 ACM SIGMOD Int’l Conf. on Management of Data. Chicago: Association for Computing Machinery, 2006. 121–132.
    [5] 姜涛. 云存储中数据安全关键技术研究 [博士学位论文]. 西安: 西安电子科技大学, 2016.
    Jiang T. Research on the key Technologies of data security in cloud storage [Ph.D. Thesis]. Xi’an: Xidian University, 2016 (in Chinese with English abstract).
    [6] Merkle RC. A certified digital signature. In: Brassard G, ed. Proc. of the 1990 Advances in Cryptology. New York: Springer, 1990. 218–238.
    [7] Parno B, Howell J, Gentry C, Raykova M. Pinocchio: Nearly practical verifiable computation. Communications of the ACM, 2016, 59(2): 103–112. [doi: 10.1145/2856449]
    [8] Ben-Sasson E, Chiesa A, Tromer E, Virza M. Succinct non-interactive zero knowledge for a von Neumann architecture. In: Proc. of the 23rd USENIX Conf. on Security Symp. San Diego: USENIX Association, 2014. 781–796.
    [9] Zhang YP, Genkin D, Katz J, Papadopoulos D, Papamanthou C. vSQL: Verifying arbitrary SQL queries over dynamic outsourced databases. In: Proc. of the 2017 IEEE Symp. on Security and Privacy. San Jose: IEEE, 2017. 863–880.
    [10] Mykletun E, Narasimha M, Tsudik G. Authentication and integrity in outsourced databases. ACM Transactions on Storage, 2006, 2(2): 107–138. [doi: 10.1145/1149976.1149977]
    [11] Narasimha M, Tsudik G. DSAC: Integrity for outsourced databases with signature aggregation and chaining. In: Proc. of the 14th ACM Int’l Conf. on Information and Knowledge Management. Bremen: Association for Computing Machinery, 2005. 235–236.
    [12] Pang H, Jain A, Ramamritham K, Tan KL. Verifying completeness of relational query results in data publishing. In: Proc. of the 2005 ACM SIGMOD Int’l Conf. on Management of Data. Baltimore: Association for Computing Machinery, 2005. 407–418.
    [13] Pang HH, Tan KL. Authenticating query results in edge computing. In: Proc. of the 20th Int’l Conf. on Data Engineering. Boston: IEEE, 2004. 560–571.
    [14] Yang Y, Papadopoulos S, Papadias D, Kollios G. Authenticated indexing for outsourced spatial databases. The VLDB Journal, 2009, 18(3): 631–648. [doi: 10.1007/s00778-008-0113-2]
    [15] Chen Q, Hu HB, Xu JL. Authenticated online data integration services. In: Proc. of the 2015 ACM SIGMOD Int’l Conf. on Management of Data. Melbourne: Association for Computing Machinery, 2015. 167–181.
    [16] Papamanthou C, Shi E, Tamassia R, Yi K. Streaming authenticated data structures. In: Proc. of the 32nd Annual Int’l Conf. on the Theory and Applications of Cryptographic Techniques. Athens: Springer, 2013. 353–370.
    [17] Papadopoulos S, Yang Y, Papadias D. Continuous authentication on relational streams. The VLDB Journal, 2010, 19(2): 161–180. [doi: 10.1007/s00778-009-0145-2]
    [18] Xu C, Zhang C, Xu JL. vChain: Enabling verifiable boolean range queries over blockchain databases. In: Proc. of the 2019 Int’l Conf. on Management of Data. Amsterdam: Association for Computing Machinery, 2019. 141–158.
    [19] Zhang C, Xu C, Xu JL, Tang YZ, Choi B. GEM2-tree: A gas-efficient structure for authenticated range queries in blockchain. In: Proc. of the 35th Int’l Conf. on Data Engineering (ICDE). Macao: IEEE, 2019. 842–853.
    [20] Xia Q, Sifah EB, Agyekum KOBO, Xia H, Acheampong KN, Smahi A, Gao JB, Du XJ, Guizani M. Secured fine-grained selective access to outsourced cloud data in IoT environments. IEEE Internet of Things Journal, 2019, 6(6): 10749–10762. [doi: 10.1109/JIOT.2019.2941638]
    [21] Asamoah KO, Xia H, Amofa S, Amankona OI, Luo KC, Xia Q, Gao JB, Du XJ, Guizani M. Zero-chain: A blockchain-based identity for digital city operating system. IEEE Internet of Things Journal, 2020, 7(10): 10336–10346. [doi: 10.1109/JIOT.2020.2986367]
    [22] 夏琦, 高建彬, 夏虎, 周涛, 张小松. 区块链数据主权技术与应用. 电子科技大学学报(社科版), 2020, 22(1): 5–11. [doi: 10.14071/j.1008-8105(2020)-1002]
    Xia Q, Gao JB, Xia H, Zhou T, Zhang XS. Blockchain data sovereignty technology and its applications. Journal of University of Electronic Science and Technology of China (Social Science Edition), 2020, 22(1): 5–11 (in Chinese with English abstract). [doi: 10.14071/j.1008-8105(2020)-1002]
    [23] 蔡婷, 林晖, 陈武辉, 郑子彬, 余阳. 区块链赋能的高效物联网数据激励共享方案. 软件学报, 2021, 32(4): 953–972. http://www.jos.org.cn/1000-9825/6229.htm
    Cai T, Lin H, Chen WH, Zheng ZB, Yu Y. Efficient blockchain-empowered data sharing incentive scheme for Internet of Things. Ruan Jian Xue Bao/Journal of Software, 2021, 32(4): 953–972 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6229.htm
    [24] 魏欣, 王心妍, 于卓, 郭少勇, 邱雪松. 基于联盟链的物联网跨域认证. 软件学报, 2021, 32(8): 2613–2628. http://www.jos.org.cn/1000-9825/6033.htm
    Wei X, Wang XY, Yu Z, Guo SY, Qiu XS. Cross domain authentication for IoT based on consortium blockchain. Ruan Jian Xue Bao/Journal of Software, 2021, 32(8): 2613–2628 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6033.htm
    [25] Merkle RC. A certified digital signature. In: Brassard G, ed. Proc. of the 2001 Advances in Cryptology. New York: Springer, 2001. 218–238.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

孙钰山,杨靖聪,夏琦,高建彬. SMT: 一种区块链上适用于流数据高效认证的数据结构.软件学报,2023,34(11):5312-5329

Copy
Share
Article Metrics
  • Abstract:918
  • PDF: 2453
  • HTML: 1455
  • Cited by: 0
History
  • Received:January 24,2022
  • Revised:March 29,2022
  • Online: March 29,2023
  • Published: November 06,2023
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063