{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T18:32:00Z","timestamp":1780511520269,"version":"3.54.1"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,3]]},"abstract":"<jats:p>\n            Blockchain databases have attracted widespread attention but suffer from poor scalability due to underlying non-scalable blockchains. While blockchain sharding is necessary for a scalable blockchain database, it poses a new challenge named\n            <jats:italic>on-chain cross-shard database services.<\/jats:italic>\n            Each cross-shard database service (e.g., cross-shard queries or inter-shard load balancing) involves massive cross-shard data exchanges, while the existing cross-shard mechanisms need to process each cross-shard data exchange via the consensus of all nodes in the related shards (i.e., on-chain) to resist a Byzantine environment of blockchain, which eliminates sharding benefits.\n          <\/jats:p>\n          <jats:p>\n            To tackle the challenge, this paper presents GriDB, the first scalable blockchain database, by designing a novel\n            <jats:italic>off-chain cross-shard mechanism<\/jats:italic>\n            for efficient cross-shard database services. Borrowing the idea of off-chain payments, GriDB delegates massive cross-shard data exchange to a few nodes, each of which is randomly picked from a different shard. Considering the Byzantine environment, the untrusted delegates cooperate to generate succinct proof for cross-shard data exchanges, while the consensus is only responsible for the low-cost proof verification. However, different from payments, the database services' verification has more requirements (e.g., completeness, correctness, freshness, and availability); thus, we introduce several new\n            <jats:italic>authenticated data structures<\/jats:italic>\n            (ADS). Particularly, we utilize consensus to extend the threat model and reduce the complexity of traditional accumulator-based ADS for verifiable cross-shard queries with a rich set of relational operators. Moreover, we study the necessity of inter-shard load balancing for a scalable blockchain database and design an off-chain and live approach for both efficiency and availability during balancing. An evaluation of our prototype shows the performance of GriDB in terms of scalability in workloads with queries and updates.\n          <\/jats:p>","DOI":"10.14778\/3587136.3587143","type":"journal-article","created":{"date-parts":[[2023,5,8]],"date-time":"2023-05-08T23:11:35Z","timestamp":1683587495000},"page":"1685-1698","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":66,"title":["GriDB: Scaling Blockchain Database via Sharding and Off-Chain Cross-Shard Mechanism"],"prefix":"10.14778","volume":"16","author":[{"given":"Zicong","family":"Hong","sequence":"first","affiliation":[{"name":"Hong Kong Polytechnic University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Song","family":"Guo","sequence":"additional","affiliation":[{"name":"Hong Kong Polytechnic University, PolyU Shenzhen Research Institute"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Enyuan","family":"Zhou","sequence":"additional","affiliation":[{"name":"Hong Kong Polytechnic University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wuhui","family":"Chen","sequence":"additional","affiliation":[{"name":"Sun Yat-sen University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huawei","family":"Huang","sequence":"additional","affiliation":[{"name":"Sun Yat-sen University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Albert","family":"Zomaya","sequence":"additional","affiliation":[{"name":"The University of Sydney"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,5,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Chainspace: A Sharded Smart Contracts Platform. CoRR abs\/1708.03778","author":"Al-Bassam Mustafa","year":"2017","unstructured":"Mustafa Al-Bassam , Alberto Sonnino , Shehar Bano , Dave Hrycyszyn , and George Danezis . 2017 . Chainspace: A Sharded Smart Contracts Platform. CoRR abs\/1708.03778 (2017). arXiv:1708.03778 http:\/\/arxiv.org\/abs\/1708.03778 Mustafa Al-Bassam, Alberto Sonnino, Shehar Bano, Dave Hrycyszyn, and George Danezis. 2017. Chainspace: A Sharded Smart Contracts Platform. CoRR abs\/1708.03778 (2017). arXiv:1708.03778 http:\/\/arxiv.org\/abs\/1708.03778"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-007-9005-7"},{"key":"e_1_2_1_3_1","volume-title":"Public-Key Cryptography - PKC","author":"Canetti Ran","year":"2014","unstructured":"Ran Canetti , Omer Paneth , Dimitrios Papadopoulos , and Nikos Triandopoulos . 2014. Verifiable Set Operations over Outsourced Databases . In Public-Key Cryptography - PKC 2014 , Hugo Krawczyk (Ed.). Springer Berlin Heidelberg , 113--130. Ran Canetti, Omer Paneth, Dimitrios Papadopoulos, and Nikos Triandopoulos. 2014. Verifiable Set Operations over Outsourced Databases. In Public-Key Cryptography - PKC 2014, Hugo Krawczyk (Ed.). Springer Berlin Heidelberg, 113--130."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/296806.296824"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319889"},{"key":"e_1_2_1_6_1","volume-title":"Retrieved","author":"Database Azure SQL","year":"2022","unstructured":"Azure SQL Database . 2022 . Scaling out with Azure SQL Database . Retrieved March 20, 2023 from https:\/\/docs.microsoft.com\/en-us\/azure\/azure-sql\/database\/elastic-scale-introduction Azure SQL Database. 2022. Scaling out with Azure SQL Database. Retrieved March 20, 2023 from https:\/\/docs.microsoft.com\/en-us\/azure\/azure-sql\/database\/elastic-scale-introduction"},{"key":"e_1_2_1_7_1","volume-title":"Retrieved","year":"2023","unstructured":"DoltHub. 2023 . go-mysql-server . Retrieved March 20, 2023 from https:\/\/github.com\/dolthub\/go-mysql-server DoltHub. 2023. go-mysql-server. Retrieved March 20, 2023 from https:\/\/github.com\/dolthub\/go-mysql-server"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342636"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723726"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989356"},{"key":"e_1_2_1_11_1","volume-title":"Retrieved","year":"2022","unstructured":"Ethereum. 2022 . Hardware requirements for Go-Ethereum . Retrieved March 20, 2023 from https:\/\/geth.ethereum.org\/docs\/getting-started\/hardware-requirements Ethereum. 2022. Hardware requirements for Go-Ethereum. Retrieved March 20, 2023 from https:\/\/geth.ethereum.org\/docs\/getting-started\/hardware-requirements"},{"key":"e_1_2_1_12_1","volume-title":"Retrieved","year":"2023","unstructured":"Ethereum. 2023 . Go Ethereum . Retrieved March 20, 2023 from https:\/\/github.com\/ethereum\/go-ethereum Ethereum. 2023. Go Ethereum. Retrieved March 20, 2023 from https:\/\/github.com\/ethereum\/go-ethereum"},{"key":"e_1_2_1_13_1","unstructured":"Emmanuelle Ganne. 2018. Can Blockchain revolutionize international trade? World Trade Organization Geneva.  Emmanuelle Ganne. 2018. Can Blockchain revolutionize international trade? World Trade Organization Geneva."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3510397.3510406"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132757"},{"key":"e_1_2_1_16_1","volume-title":"Retrieved","year":"2023","unstructured":"Google. 2023 . The Go Programming Language . Retrieved March 20, 2023 from https:\/\/golang.org\/ Google. 2023. The Go Programming Language. Retrieved March 20, 2023 from https:\/\/golang.org\/"},{"key":"e_1_2_1_17_1","unstructured":"Lewis Gudgeon Pedro Moreno-Sanchez Stefanie Roos Patrick McCorry and Arthur Gervais. 2019. SoK: Layer-Two Blockchain Protocols. Cryptology ePrint Archive Paper 2019\/360. https:\/\/eprint.iacr.org\/2019\/360 https:\/\/eprint.iacr.org\/2019\/360.  Lewis Gudgeon Pedro Moreno-Sanchez Stefanie Roos Patrick McCorry and Arthur Gervais. 2019. SoK: Layer-Two Blockchain Protocols. Cryptology ePrint Archive Paper 2019\/360. https:\/\/eprint.iacr.org\/2019\/360 https:\/\/eprint.iacr.org\/2019\/360."},{"key":"e_1_2_1_18_1","volume-title":"Retrieved","year":"2023","unstructured":"Harmony. 2023 . Harmony . Retrieved March 20, 2023 from https:\/\/github.com\/harmony-one\/harmony Harmony. 2023. Harmony. Retrieved March 20, 2023 from https:\/\/github.com\/harmony-one\/harmony"},{"key":"e_1_2_1_19_1","volume-title":"Retrieved","year":"2023","unstructured":"Harmony. 2023 . Harmony consensus protocol design . Retrieved March 20, 2023 from https:\/\/github.com\/harmony-one\/harmony\/tree\/main\/consensus Harmony. 2023. Harmony consensus protocol design. Retrieved March 20, 2023 from https:\/\/github.com\/harmony-one\/harmony\/tree\/main\/consensus"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476275"},{"key":"e_1_2_1_21_1","volume-title":"Retrieved","year":"2020","unstructured":"Herumi. 2020 . High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves . Retrieved March 20, 2023 from https:\/\/github.com\/herumi\/ate-pairing Herumi. 2020. High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves. Retrieved March 20, 2023 from https:\/\/github.com\/herumi\/ate-pairing"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM42981.2021.9488747"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN53405.2022.00017"},{"key":"e_1_2_1_24_1","volume-title":"Retrieved","author":"IBM.","year":"2020","unstructured":"IBM. 2020 . Blockchain for supply chain solutions . Retrieved March 20, 2023 from https:\/\/www.ibm.com\/blockchain\/industries\/supply-chain IBM. 2020. Blockchain for supply chain solutions. Retrieved March 20, 2023 from https:\/\/www.ibm.com\/blockchain\/industries\/supply-chain"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings 41st Annual Symposium on Foundations of Computer Science. 565--574","author":"Karp R.","unstructured":"R. Karp , C. Schindelhauer , S. Shenker , and B. Vocking . 2000. Randomized rumor spreading . In Proceedings 41st Annual Symposium on Foundations of Computer Science. 565--574 . R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking. 2000. Randomized rumor spreading. In Proceedings 41st Annual Symposium on Foundations of Computer Science. 565--574."},{"key":"e_1_2_1_26_1","volume-title":"Retrieved","author":"Khalil Rami","year":"2018","unstructured":"Rami Khalil , Alexei Zamyatin , Guillaume Felley , Pedro Moreno-Sanchez , and Arthur Gervais . 2018 . Commit-chains: Secure, scalable off-chain payments . Retrieved March 20, 2023 from https:\/\/eprint.iacr.org\/2018\/642.pdf Rami Khalil, Alexei Zamyatin, Guillaume Felley, Pedro Moreno-Sanchez, and Arthur Gervais. 2018. Commit-chains: Secure, scalable off-chain payments. Retrieved March 20, 2023 from https:\/\/eprint.iacr.org\/2018\/642.pdf"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/3241094.3241117"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.000-5"},{"key":"e_1_2_1_29_1","volume-title":"Retrieved","year":"2021","unstructured":"Lightning. 2021 . The Lightning Network . Retrieved March 20, 2023 from https:\/\/lightning.network\/ Lightning. 2021. The Lightning Network. Retrieved March 20, 2023 from https:\/\/lightning.network\/"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978389"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813659"},{"key":"e_1_2_1_32_1","volume-title":"Conference on the theory and application of cryptographic techniques. Springer, 369--378","author":"Merkle Ralph C","year":"1987","unstructured":"Ralph C Merkle . 1987 . A digital signature based on a conventional encryption function . In Conference on the theory and application of cryptographic techniques. Springer, 369--378 . Ralph C Merkle. 1987. A digital signature based on a conventional encryption function. In Conference on the theory and application of cryptographic techniques. Springer, 369--378."},{"key":"e_1_2_1_33_1","volume-title":"Financial Cryptography and Data Security","author":"Miller Andrew","unstructured":"Andrew Miller , Iddo Bentov , Surya Bakshi , Ranjit Kumaresan , and Patrick McCorry . 2019. Sprites and State Channels: Payment Networks that Go Faster Than Lightning . In Financial Cryptography and Data Security . Springer International Publishing , 508--526. Andrew Miller, Iddo Bentov, Surya Bakshi, Ranjit Kumaresan, and Patrick McCorry. 2019. Sprites and State Channels: Payment Networks that Go Faster Than Lightning. In Financial Cryptography and Data Security. Springer International Publishing, 508--526."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484554"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1149976.1149977"},{"key":"e_1_2_1_36_1","volume-title":"Retrieved","author":"SQL.","year":"2023","unstructured":"My SQL. 2023 . MySQL 8.0 Reference . Retrieved March 20, 2023 from https:\/\/dev.mysql.com\/doc\/refman\/8.0\/en\/sql-data-manipulation-statements.html MySQL. 2023. MySQL 8.0 Reference. Retrieved March 20, 2023 from https:\/\/dev.mysql.com\/doc\/refman\/8.0\/en\/sql-data-manipulation-statements.html"},{"key":"e_1_2_1_37_1","volume-title":"Retrieved","author":"Nakamoto Satoshi","year":"2008","unstructured":"Satoshi Nakamoto . 2008 . Bitcoin: A peer-to-peer electronic cash system . Retrieved March 20, 2023 from https:\/\/bitcoin.org\/bitcoin.pdf Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. Retrieved March 20, 2023 from https:\/\/bitcoin.org\/bitcoin.pdf"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30574-3_19"},{"key":"e_1_2_1_39_1","volume-title":"Advances in Cryptology - CRYPTO","author":"Papamanthou Charalampos","year":"2011","unstructured":"Charalampos Papamanthou , Roberto Tamassia , and Nikos Triandopoulos . 2011. Optimal Verification of Operations on Dynamic Sets . In Advances in Cryptology - CRYPTO 2011 , Phillip Rogaway (Ed.). Springer Berlin Heidelberg , 91--110. Charalampos Papamanthou, Roberto Tamassia, and Nikos Triandopoulos. 2011. Optimal Verification of Operations on Dynamic Sets. In Advances in Cryptology - CRYPTO 2011, Phillip Rogaway (Ed.). Springer Berlin Heidelberg, 91--110."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/SRDS51746.2020.00013"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380594"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454112"},{"key":"e_1_2_1_43_1","volume-title":"Retrieved","author":"Poon Joseph","year":"2017","unstructured":"Joseph Poon and Vitalik Buterin . 2017 . Plasma: Scalable autonomous smart contracts . Retrieved March 20, 2023 from https:\/\/www.plasma.io\/plasma.pdf Joseph Poon and Vitalik Buterin. 2017. Plasma: Scalable autonomous smart contracts. Retrieved March 20, 2023 from https:\/\/www.plasma.io\/plasma.pdf"},{"key":"e_1_2_1_44_1","volume-title":"Retrieved","year":"2021","unstructured":"Raiden. 2021 . The Raiden Network . Retrieved March 20, 2023 from https:\/\/raiden.network\/ Raiden. 2021. The Raiden Network. Retrieved March 20, 2023 from https:\/\/raiden.network\/"},{"key":"e_1_2_1_45_1","volume-title":"Database Management Systems","author":"Ramakrishnan Raghu","unstructured":"Raghu Ramakrishnan and Johannes Gehrke . 2000. Database Management Systems ( 2 nd ed.). McGraw-Hill, Inc. Raghu Ramakrishnan and Johannes Gehrke. 2000. Database Management Systems (2nd ed.). McGraw-Hill, Inc.","edition":"2"},{"key":"e_1_2_1_46_1","volume-title":"Distributed Computing and Internet Technology","author":"Ramesh Sukriti","unstructured":"Sukriti Ramesh , Odysseas Papapetrou , and Wolf Siberski . 2009. Optimizing Distributed Joins with Bloom Filters . In Distributed Computing and Internet Technology . Springer Berlin Heidelberg , 145--156. Sukriti Ramesh, Odysseas Papapetrou, and Wolf Siberski. 2009. Optimizing Distributed Joins with Bloom Filters. In Distributed Computing and Internet Technology. Springer Berlin Heidelberg, 145--156."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3329772.3329775"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452789"},{"key":"e_1_2_1_49_1","volume-title":"Retrieved","year":"2020","unstructured":"SCIPRLab. 2020 . libsnark: a C++ library for zkSNARK proofs . Retrieved March 20, 2023 from https:\/\/github.com\/scipr-lab\/libsnark SCIPRLab. 2020. libsnark: a C++ library for zkSNARK proofs. Retrieved March 20, 2023 from https:\/\/github.com\/scipr-lab\/libsnark"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735508.2735514"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00121"},{"key":"e_1_2_1_52_1","volume-title":"Retrieved","author":"TPC.","year":"2023","unstructured":"TPC. 2023 . TPC-H Benchmark . Retrieved March 20, 2023 from http:\/\/www.tpc.org\/tpch\/ TPC. 2023. TPC-H Benchmark. Retrieved March 20, 2023 from http:\/\/www.tpc.org\/tpch\/"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318041.3355457"},{"key":"e_1_2_1_54_1","volume-title":"16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19)","author":"Wang Jiaping","year":"2019","unstructured":"Jiaping Wang and Hao Wang . 2019 . Monoxide: Scale out Blockchains with Asynchronous Consensus Zones . In 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19) . USENIX Association, Boston, MA, 95--112. https:\/\/www.usenix.org\/conference\/nsdi19\/presentation\/wang-jiaping Jiaping Wang and Hao Wang. 2019. Monoxide: Scale out Blockchains with Asynchronous Consensus Zones. In 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19). USENIX Association, Boston, MA, 95--112. https:\/\/www.usenix.org\/conference\/nsdi19\/presentation\/wang-jiaping"},{"key":"e_1_2_1_55_1","volume-title":"Proceedings of the 2017 USENIX Conference on Usenix Annual Technical Conference (Santa Clara, CA, USA) (USENIX ATC '17). USENIX Association, USA, 335--347","author":"Wei Xingda","year":"2017","unstructured":"Xingda Wei , Sijie Shen , Rong Chen , and Haibo Chen . 2017 . Replication-Driven Live Reconfiguration for Fast Distributed Transaction Processing . In Proceedings of the 2017 USENIX Conference on Usenix Annual Technical Conference (Santa Clara, CA, USA) (USENIX ATC '17). USENIX Association, USA, 335--347 . Xingda Wei, Sijie Shen, Rong Chen, and Haibo Chen. 2017. Replication-Driven Live Reconfiguration for Fast Distributed Transaction Processing. In Proceedings of the 2017 USENIX Conference on Usenix Annual Technical Conference (Santa Clara, CA, USA) (USENIX ATC '17). USENIX Association, USA, 335--347."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300083"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243853"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2947061"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00080"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2017.43"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813711"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00198"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3587136.3587143","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,8]],"date-time":"2023-05-08T23:13:26Z","timestamp":1683587606000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3587136.3587143"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3]]},"references-count":62,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["10.14778\/3587136.3587143"],"URL":"https:\/\/doi.org\/10.14778\/3587136.3587143","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,3]]},"assertion":[{"value":"2023-05-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}