{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T15:30:16Z","timestamp":1774539016592,"version":"3.50.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:p>Blockchains have gained wide adoption for secure data processing. As blockchain data volumes grow, the demand for efficient data analysis, especially aggregate queries, becomes increasingly critical. However, current blockchains lack native support for efficient analytical query processing, forcing users to either maintain full replicas or rely on third-party services without integrity guarantees.<\/jats:p>\n          <jats:p>In this paper, we propose an efficient framework, Merkle Bloom Filter Tree (MBFT), for authenticated aggregate queries that combine boolean keywords and range predicates on blockchains. At its core is a Bloom filter-based authenticated data structure that supports both types of predicates, constructed per block for efficient transaction indexing. For temporal predicates, we optimize time window queries through value pruning and block consolidation. We design a novel Merge Bloom Filter (MBF) for space-efficient handling of dynamic sets during query authentication. We provide a theoretical analysis of the storage overhead caused by the Bloom filter's false positive rates. Our framework employs data sketches to support various aggregate operations. Extensive experiments demonstrate that MBFT has improved the query speed by up to 286\u00d7 compared to state-of-the-art authenticated query solutions.<\/jats:p>","DOI":"10.14778\/3748191.3748219","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:50:16Z","timestamp":1756993816000},"page":"3615-3627","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Authenticated Aggregate Queries with Boolean Range Predicates on Blockchains"],"prefix":"10.14778","volume":"18","author":[{"given":"Weijie","family":"Sun","sequence":"first","affiliation":[{"name":"HKUST, Hong Kong SAR, China"}]},{"given":"Zihuan","family":"Xu","sequence":"additional","affiliation":[{"name":"Shenzhen Institute of Computing Sciences, Shenzhen, China"}]},{"given":"Wangze","family":"Ni","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"HKUST(GZ) &amp; HKUST, Guangzhou &amp; Hong Kong SAR, China"}]},{"given":"Peng","family":"Cheng","sequence":"additional","affiliation":[{"name":"Tongji University, Shanghai, China"}]},{"given":"Chen Jason","family":"Zhang","sequence":"additional","affiliation":[{"name":"The Hong Kong Polytechnic University, Hong Kong SAR, China"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"aappleby. 2025. Murmurhash3. https:\/\/github.com\/aappleby\/smhasher."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/j.ipl.2006.10.007","article-title":"Scalable bloom filters","volume":"101","author":"Almeida Paulo S\u00e9rgio","year":"2007","unstructured":"Paulo S\u00e9rgio Almeida, Carlos Baquero, Nuno Pregui\u00e7a, and David Hutchison. 2007. Scalable bloom filters. Inform. Process. Lett. 101, 6 (2007), 255\u2013261.","journal-title":"Inform. Process. Lett."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1006\/jcss.1997.1545","article-title":"The space complexity of approximating the frequency moments","volume":"58","author":"Alon Noga","year":"1999","unstructured":"Noga Alon, Yossi Matias, and Mario Szegedy. 1999. The space complexity of approximating the frequency moments. Journal of Computer and system sciences 58, 1 (1999), 137\u2013147.","journal-title":"Journal of Computer and system sciences"},{"key":"e_1_2_1_4_1","volume-title":"21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24)","author":"Amiri Mohammad Javad","year":"2024","unstructured":"Mohammad Javad Amiri, Chenyuan Wu, Divyakant Agrawal, Amr El Abbadi, Boon Thau Loo, and Mohammad Sadoghi. 2024. The bedrock of byzantine fault tolerance: A unified platform for {BFT} protocols analysis, implementation, and experimentation. In 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24). 371\u2013400."},{"key":"e_1_2_1_5_1","volume-title":"International Workshop on Randomization and Approximation Techniques in Computer Science. Springer, 1\u201310","author":"Bar-Yossef Ziv","year":"2002","unstructured":"Ziv Bar-Yossef, T S Jayram, Ravi Kumar, D Sivakumar, and Luca Trevisan. 2002. Counting distinct elements in a data stream. In International Workshop on Randomization and Approximation Techniques in Computer Science. Springer, 1\u201310."},{"key":"e_1_2_1_6_1","unstructured":"BigQuery. 2025. BigQuery official website. https:\/\/cloud.google.com\/bigquery."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/362686.362692","article-title":"Space\/time trade-offs in hash coding with allowable errors","volume":"13","author":"Bloom Burton H","year":"1970","unstructured":"Burton H Bloom. 1970. Space\/time trade-offs in hash coding with allowable errors. Commun. ACM 13, 7 (1970), 422\u2013426.","journal-title":"Commun. ACM"},{"key":"e_1_2_1_8_1","volume-title":"International Conference on Database Theory. Springer, 383\u2013397","author":"Cabibbo Luca","year":"1999","unstructured":"Luca Cabibbo and Riccardo Torlone. 1999. A framework for the investigation of aggregate functions in database queries. In International Conference on Database Theory. Springer, 383\u2013397."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings. 20th International Conference on Data Engineering. IEEE, 449\u2013460","author":"Considine Jeffrey","year":"2004","unstructured":"Jeffrey Considine, Feifei Li, George Kollios, and John Byers. 2004. Approximate aggregation techniques for sensor databases. In Proceedings. 20th International Conference on Data Engineering. IEEE, 449\u2013460."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"107367","DOI":"10.1016\/j.comnet.2020.107367","article-title":"Blockchain reputation-based consensus: A scalable and resilient mechanism for distributed mistrusting applications","volume":"179","author":"de Oliveira Marcela T","year":"2020","unstructured":"Marcela T de Oliveira, L\u00facio HA Reis, Dianne SV Medeiros, Ricardo C Carrano, S\u00edlvia D Olabarriaga, and Diogo MF Mattos. 2020. Blockchain reputation-based consensus: A scalable and resilient mechanism for distributed mistrusting applications. Computer Networks 179 (2020), 107367.","journal-title":"Computer Networks"},{"key":"e_1_2_1_11_1","volume-title":"Adjudicating violations in data sharing agreements using smart contracts. In 2018 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications","author":"Desai Harsh","unstructured":"Harsh Desai, Kevin Liu, Murat Kantarcioglu, and Lalana Kagal. 2018. Adjudicating violations in data sharing agreements using smart contracts. In 2018 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData). IEEE, 1553\u20131560."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"13784","DOI":"10.1109\/TVT.2020.3027568","article-title":"Attribute-based encryption with parallel outsourced decryption for edge intelligent IoV","volume":"69","author":"Feng Chaosheng","year":"2020","unstructured":"Chaosheng Feng, Keping Yu, Moayad Aloqaily, Mamoun Alazab, Zhihan Lv, and Shahid Mumtaz. 2020. Attribute-based encryption with parallel outsourced decryption for edge intelligent IoV. IEEE Transactions on Vehicular Technology 69, 11 (2020), 13784\u201313795.","journal-title":"IEEE Transactions on Vehicular Technology"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/0022-0000(85)90041-8","article-title":"Probabilistic counting algorithms for data base applications","volume":"31","author":"Flajolet Philippe","year":"1985","unstructured":"Philippe Flajolet and G Nigel Martin. 1985. Probabilistic counting algorithms for data base applications. Journal of computer and system sciences 31, 2 (1985), 182\u2013209.","journal-title":"Journal of computer and system sciences"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"1092","DOI":"10.14778\/3510397.3510406","article-title":"Hybrid Blockchain Database Systems: Design and Performance","volume":"15","author":"Ge Zerui","year":"2022","unstructured":"Zerui Ge, Dumitrel Loghin, Beng Chin Ooi, Pingcheng Ruan, and Tianwen Wang. 2022. Hybrid Blockchain Database Systems: Design and Performance. VLDB Endowment 15, 5 (2022), 1092\u20131104.","journal-title":"VLDB Endowment"},{"key":"e_1_2_1_15_1","unstructured":"BigchainDB GmbH. 2018. BigchainDB 2.0: the blockchain database."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. 174\u2013184","author":"Grumbach Stephane","year":"1999","unstructured":"Stephane Grumbach, Maurizio Rafanelli, and Leonardo Tininini. 1999. Querying aggregate data. In Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. 174\u2013184."},{"key":"e_1_2_1_17_1","first-page":"120","article-title":"The dynamic bloom filters","volume":"22","author":"Guo Deke","year":"2009","unstructured":"Deke Guo, Jie Wu, Honghui Chen, Ye Yuan, and Xueshan Luo. 2009. The dynamic bloom filters. IEEE Transactions on Knowledge and Data Engineering 22, 1 (2009), 120\u2013133.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 2019 international conference on management of data. 1921\u20131924","author":"Han Siyuan","year":"2019","unstructured":"Siyuan Han, Zihuan Xu, Yuxiang Zeng, and Lei Chen. 2019. Fluid: A blockchain based framework for crowdsourcing. In Proceedings of the 2019 international conference on management of data. 1921\u20131924."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 23rd ACM\/IFIP International Middleware Conference. 269\u2013280","author":"Ji Yang","year":"2022","unstructured":"Yang Ji, Cheng Xu, Ce Zhang, and Jianliang Xu. 2022. DCert: towards secure, efficient, and versatile blockchain light clients. In Proceedings of the 23rd ACM\/IFIP International Middleware Conference. 269\u2013280."},{"key":"e_1_2_1_20_1","volume-title":"proceedings of the 50th Hawaii international conference on system sciences.","author":"Korpela Kari","year":"2017","unstructured":"Kari Korpela, Jukka Hallikas, and Tomi Dahlberg. 2017. Digital supply chain transformation toward blockchain integration. In proceedings of the 50th Hawaii international conference on system sciences."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 2006 ACM SIGMOD international conference on Management of data. 121\u2013132","author":"Li Feifei","year":"2006","unstructured":"Feifei Li, Marios Hadjieleftheriou, George Kollios, and Leonid Reyzin. 2006. Dynamic authenticated index structures for outsourced databases. In Proceedings of the 2006 ACM SIGMOD international conference on Management of data. 121\u2013132."},{"key":"e_1_2_1_22_1","volume-title":"Authenticated Keyword Search on Large-Scale Graphs in Hybrid-Storage Blockchains. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE","author":"Li Siyu","year":"2024","unstructured":"Siyu Li, Zhiwei Zhang, Jiang Xiao, Meihui Zhang, Ye Yuan, and Guoren Wang. 2024. Authenticated Keyword Search on Large-Scale Graphs in Hybrid-Storage Blockchains. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 1958\u20131971."},{"key":"e_1_2_1_23_1","volume-title":"Authenticated Subgraph Matching in Hybrid-Storage Blockchains. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE","author":"Li Siyu","year":"2024","unstructured":"Siyu Li, Zhiwei Zhang, Meihui Zhang, Ye Yuan, and Guoren Wang. 2024. Authenticated Subgraph Matching in Hybrid-Storage Blockchains. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 1986\u20131998."},{"key":"e_1_2_1_24_1","volume-title":"International Conference on Database Systems for Advanced Applications. Springer, 556\u2013567","author":"Li Yang","year":"2017","unstructured":"Yang Li, Kai Zheng, Ying Yan, Qi Liu, and Xiaofang Zhou. 2017. EtherQL: a query layer for blockchain system. In International Conference on Database Systems for Advanced Applications. Springer, 556\u2013567."},{"key":"e_1_2_1_25_1","unstructured":"MongoDB. [n.d.]. MongoDB official website. https:\/\/www.mongodb.com."},{"key":"e_1_2_1_26_1","volume-title":"Bitcoin: A peer-to-peer electronic cash system. Decentralized Business Review","author":"Nakamoto Satoshi","year":"2008","unstructured":"Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. Decentralized Business Review (2008), 21260."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1340771.1340773","article-title":"Synopsis diffusion for robust aggregation in sensor networks","volume":"4","author":"Nath Suman","year":"2008","unstructured":"Suman Nath, Phillip B Gibbons, Srinivasan Seshan, and Zachary Anderson. 2008. Synopsis diffusion for robust aggregation in sensor networks. ACM Transactions on Sensor Networks (TOSN) 4, 2 (2008), 1\u201340.","journal-title":"ACM Transactions on Sensor Networks (TOSN)"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 2009 ACM SIGMOD International Conference on Management of data. 31\u201344","author":"Nath Suman","year":"2009","unstructured":"Suman Nath, Haifeng Yu, and Haowen Chan. 2009. Secure outsourced aggregation via one-way chains. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data. 31\u201344."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 1st international conference on Embedded networked sensor systems. 255\u2013265","author":"Przydatek Bartosz","year":"2003","unstructured":"Bartosz Przydatek, Dawn Song, and Adrian Perrig. 2003. SIA: Secure information aggregation in sensor networks. In Proceedings of the 1st international conference on Embedded networked sensor systems. 255\u2013265."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing. 2\u20132.","author":"Roughgarden Tim","year":"2024","unstructured":"Tim Roughgarden. 2024. Keynote: Provable Slashing Guarantees. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing. 2\u20132."},{"key":"e_1_2_1_31_1","volume-title":"2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS). IEEE, 257\u2013265","author":"Shao Qifeng","year":"2021","unstructured":"Qifeng Shao, Zhao Zhang, Cheqing Jin, and Aoying Zhou. 2021. Trusted slidingwindow aggregation over blockchains. In 2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS). IEEE, 257\u2013265."},{"key":"e_1_2_1_32_1","unstructured":"Weijie Sun Zihuan Xu Wangze Ni Lei Chen Peng Cheng and Chen Jason Zhang. 2025. https:\/\/github.com\/SwJay\/mbft."},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1109\/MC.2017.3571047","article-title":"Blockchain technology in finance","volume":"50","author":"Treleaven Philip","year":"2017","unstructured":"Philip Treleaven, Richard Gendal Brown, and Danny Yang. 2017. Blockchain technology in finance. Computer 50, 9 (2017), 14\u201317.","journal-title":"Computer"},{"key":"e_1_2_1_34_1","volume-title":"2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE","author":"Wang Haixin","year":"2024","unstructured":"Haixin Wang, Cheng Xu, Xiaojie Chen, Ce Zhang, Haibo Hu, Shikun Tian, Ying Yan, and Jianliang Xu. 2024. V2FS: A Verifiable Virtual Filesystem for Multi-Chain Query Authentication. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 1999\u20132011."},{"key":"e_1_2_1_35_1","volume-title":"2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE","author":"Wang Haixin","year":"2022","unstructured":"Haixin Wang, Cheng Xu, Ce Zhang, Jianliang Xu, Zhe Peng, and Jian Pei. 2022. vChain+: Optimizing verifiable blockchain boolean range queries. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 1927\u20131940."},{"key":"e_1_2_1_36_1","volume-title":"2011 IEEE 19th Annual International Symposium on Modelling, Analysis, and Simulation of Computer and Telecommunication Systems. IEEE, 466\u2013468","author":"Wei Jiansheng","year":"2011","unstructured":"Jiansheng Wei, Hong Jiang, Ke Zhou, and Dan Feng. 2011. DBA: A dynamic Bloom filter array for scalable membership representation of variable large data sets. In 2011 IEEE 19th Annual International Symposium on Modelling, Analysis, and Simulation of Computer and Telecommunication Systems. IEEE, 466\u2013468."},{"key":"e_1_2_1_37_1","volume-title":"Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper 151","author":"Wood Gavin","year":"2014","unstructured":"Gavin Wood. 2014. Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper 151, 2014 (2014), 1\u201332."},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/s00778-018-0517-6","article-title":"VBTree: forward secure conjunctive queries over encrypted data for cloud computing","volume":"28","author":"Wu Zhiqiang","year":"2019","unstructured":"Zhiqiang Wu and Kenli Li. 2019. VBTree: forward secure conjunctive queries over encrypted data for cloud computing. The VLDB journal 28, 1 (2019), 25\u201346.","journal-title":"The VLDB journal"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 2019 international conference on management of data. 141\u2013158","author":"Xu Cheng","year":"2019","unstructured":"Cheng Xu, Ce Zhang, and Jianliang Xu. 2019. vchain: Enabling verifiable boolean range queries over blockchain databases. In Proceedings of the 2019 international conference on management of data. 141\u2013158."},{"key":"e_1_2_1_40_1","unstructured":"YCharts. 2025. Bitcoin Blockchain Size. https:\/\/ycharts.com\/indicators\/bitcoin_blockchain_size."},{"key":"e_1_2_1_41_1","unstructured":"YCharts. 2025. Ethereum Blockchain Size. https:\/\/ycharts.com\/indicators\/ethereum_chain_full_sync_data_size."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415567"},{"key":"e_1_2_1_43_1","volume-title":"2017 IEEE European Symposium on Security and Privacy (EuroS&P). IEEE, 158\u2013173","author":"Zhang Yupeng","year":"2017","unstructured":"Yupeng Zhang, Jonathan Katz, and Charalampos Papamanthou. 2017. An expressive (zero-knowledge) set accumulator. In 2017 IEEE European Symposium on Security and Privacy (EuroS&P). IEEE, 158\u2013173."},{"key":"e_1_2_1_44_1","volume-title":"2020 IEEE 26th International Conference on Parallel and Distributed Systems (ICPADS). IEEE, 456\u2013465","author":"Zhu Yanchao","year":"2020","unstructured":"Yanchao Zhu, Zhao Zhang, Cheqing Jin, and Aoying Zhou. 2020. Enabling generic verifiable aggregate query on blockchain systems. In 2020 IEEE 26th International Conference on Parallel and Distributed Systems (ICPADS). IEEE, 456\u2013465."},{"key":"e_1_2_1_45_1","volume-title":"2019 IEEE 35th international conference on data engineering (ICDE). IEEE","author":"Zhu Yanchao","year":"2019","unstructured":"Yanchao Zhu, Zhao Zhang, Cheqing Jin, Aoying Zhou, and Ying Yan. 2019. SEBDB: semantics empowered blockchain database. In 2019 IEEE 35th international conference on data engineering (ICDE). IEEE, 1820\u20131831."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3748191.3748219","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:50:27Z","timestamp":1756993827000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3748191.3748219"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6]]},"references-count":45,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["10.14778\/3748191.3748219"],"URL":"https:\/\/doi.org\/10.14778\/3748191.3748219","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,6]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}