{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T17:07:14Z","timestamp":1781284034355,"version":"3.54.1"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,12,11]],"date-time":"2024-12-11T00:00:00Z","timestamp":1733875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Natural Science Foundation of Changsha City","award":["kq2402030"],"award-info":[{"award-number":["kq2402030"]}]},{"DOI":"10.13039\/501100004735","name":"Natural Science Foundation of Hunan Province","doi-asserted-by":"crossref","award":["2024JJ5043"],"award-info":[{"award-number":["2024JJ5043"]}],"id":[{"id":"10.13039\/501100004735","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Web"],"published-print":{"date-parts":[[2025,2,28]]},"abstract":"<jats:p>Sharding is a promising technique for increasing a blockchain system\u2019s throughput by enabling parallel transaction processing. The main challenge of state sharding lies in ensuring the atomicity verification of cross-sharding transactions, which results in double communication overhead and increases the transaction\u2019s confirmation time. Previous research has primarily focused on developing cross-shard protocols for the fast and reliable validation of transactions involving multiple shards. These studies typically generate a large number of cross-shard transactions because they primarily use simple address mapping for state sharding, that is, the prefix\/suffix of the account address. In this article, we propose a state sharding scheme via density-based partitioning of the account-transaction graph. In order to reduce cross-shard transactions, the scheme groups correlated accounts into the same shard by generating the densest subgraphs, as the graph density describes the correlation among accounts, i.e., how often transactions have occurred among accounts. We formulate the graph density-based state sharding problem, with the goal of maximizing the average density across all shards under the workload constraint. We prove the NP-completeness of the problem. To reduce the complexity of finding the densest subgraph, we propose the pruning-based algorithm that reduces the search space by pre-pruning some invalid edges based on the concept of core number. We also extend the linear deterministic greedy algorithm and PageRank algorithm to handle new transactions in the dynamic scenario. We conduct extensive experiments using real transaction data from Ethereum. The experimental results demonstrate a strong correlation between the shard density and the number of cross-shard transactions, and the pruning-based algorithm can reduce the running time by an order of magnitude.<\/jats:p>","DOI":"10.1145\/3697840","type":"journal-article","created":{"date-parts":[[2024,9,27]],"date-time":"2024-09-27T14:54:37Z","timestamp":1727448877000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Efficient State Sharding in Blockchain via Density-based Graph Partitioning"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0281-5970","authenticated-orcid":false,"given":"Bo","family":"Yin","sequence":"first","affiliation":[{"name":"School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-5911-4796","authenticated-orcid":false,"given":"Peng","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-0621-0699","authenticated-orcid":false,"given":"Tingxuan","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,12,11]]},"reference":[{"issue":"1","key":"e_1_3_1_2_2","first-page":"143","article-title":"Zipf\u2019s law and the Internet.","volume":"3","author":"Adamic Lada A","year":"2002","unstructured":"Lada A Adamic and Bernardo A Huberman. 2002. Zipf\u2019s law and the Internet. Glottometrics 3, 1 (2002), 143\u2013150.","journal-title":"Glottometrics"},{"key":"e_1_3_1_3_2","doi-asserted-by":"crossref","unstructured":"Mustafa Al-Bassam Alberto Sonnino Shehar Bano Dave Hrycyszyn and George Danezis. 2018. Chainspace: A sharded smart contracts platform. In Network and Distributed System Security Symposium (NDSS\u201918). Internet Society.","DOI":"10.14722\/ndss.2018.23241"},{"key":"e_1_3_1_4_2","unstructured":"J Alvarez-Hamelin Luca Dall\u2019Asta Alain Barrat and Alessandro Vespignani. 2005. Large scale networks fingerprinting and visualization using the k-core decomposition. In Proceedings of the 18th International Conference on Neural Information Processing Systems. 41\u201350."},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452807"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95995-3_3"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1007912.1007931"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-99073-6_6"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11634-010-0079-y"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2021.08.032"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.techfore.2020.120166"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/646688.702972"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.pmcj.2019.04.004"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319889"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-31277-0_10"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.resconrec.2020.105064"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/DSN-W.2018.00051"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0464-z"},{"key":"e_1_3_1_19_2","unstructured":"Andrew V. Goldberg. 1984. Finding a maximum density subgraph. Tech. Rep. University of California at Berkeley (1984) 1\u201314."},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM42981.2021.9488747"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM48880.2022.9796859"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850471"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.000-5"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS54860.2022.00022"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978389"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/EuroSPW51379.2020.00060"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNSM.2020.3031355"},{"key":"e_1_3_1_29_2","first-page":"1","article-title":"Bitcoin: A peer-to-peer electronic cash system","author":"Nakamoto Satoshi","year":"2008","unstructured":"Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. Decentralized Business Review 4, 2 (2008), 1\u201310.","journal-title":"Decentralized Business Review"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2019.00059"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783299"},{"issue":"1","key":"e_1_3_1_32_2","first-page":"64","article-title":"Blockchain revolution: How the technology behind bitcoin is changing money, business, and the world","volume":"25","author":"Radziwill Nicole","year":"2018","unstructured":"Nicole Radziwill. 2018. Blockchain revolution: How the technology behind bitcoin is changing money, business, and the world. The Quality Management Journal 25, 1 (2018), 64\u201365.","journal-title":"The Quality Management Journal"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3360611"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSC.2022.3231619"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339722"},{"key":"e_1_3_1_36_2","first-page":"1628","article-title":"Kclist++: A simple algorithm for finding k-clique densest subgraphs in large graphs","author":"Sun Bintao","year":"2010","unstructured":"Bintao Sun, Maximilien Danisch, TH Hubert Chan, and Mauro Sozio. 2010. Kclist++: A simple algorithm for finding k-clique densest subgraphs in large graphs. Proceedings of the VLDB Endowment (PVLDB) 13, 10 (2010), 1628\u20131640.","journal-title":"Proceedings of the VLDB Endowment (PVLDB)"},{"key":"e_1_3_1_37_2","doi-asserted-by":"crossref","unstructured":"Zilliqa Team. 2017. The zilliqa technical whitepaper. (2017). Retrieved from https:\/\/docs.zilliqa.com\/whitepaper.pdf","DOI":"10.2139\/ssrn.3442330"},{"key":"e_1_3_1_38_2","doi-asserted-by":"crossref","unstructured":"Charalampos Tsourakakis Francesco Bonchi Aristides Gionis Francesco Gullo and Maria Tsiarli. 2013. Denser than the densest subgraph: Extracting optimal quasi-cliques with quality guarantees (Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). 104\u2013112.","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318041.3355457"},{"key":"e_1_3_1_40_2","first-page":"95","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). 95\u2013112."},{"key":"e_1_3_1_41_2","first-page":"1","article-title":"GradingShard: A new sharding protocol to improve blockchain throughput","author":"Wang Yu","year":"2023","unstructured":"Yu Wang, Wenyong Wang, Youlu Zeng, and Ting Yang. 2023. GradingShard: A new sharding protocol to improve blockchain throughput. Peer-to-Peer Networking and Applications 16 (2023), 1\u201313.","journal-title":"Peer-to-Peer Networking and Applications"},{"issue":"2014","key":"e_1_3_1_42_2","first-page":"1","article-title":"Ethereum: A secure decentralised generalised transaction ledger","volume":"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.","journal-title":"Ethereum Project Yellow Paper"},{"issue":"2","key":"e_1_3_1_43_2","first-page":"1","article-title":"Efficient and effective algorithms for generalized densest subgraph discovery","volume":"1","author":"Xu Yichen","year":"2023","unstructured":"Yichen Xu, Chenhao Ma, Yixiang Fang, and Zhifeng Bao. 2023. Efficient and effective algorithms for generalized densest subgraph discovery. Proceedings of the ACM on Management of Data 1, 2 (2023), 1\u201327.","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"e_1_3_1_44_2","first-page":"1","article-title":"Blockchain for healthcare data management: opportunities, challenges, and future recommendations","author":"Yaqoob Ibrar","year":"2021","unstructured":"Ibrar Yaqoob, Khaled Salah, Raja Jayaraman, and Yousof Al-Hammadi. 2021. Blockchain for healthcare data management: opportunities, challenges, and future recommendations. Neural Computing and Applications 34 (2021), 1\u201316.","journal-title":"Neural Computing and Applications"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243853"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3404397.3404460"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00390"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-23495-8_6"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/Blockchain60715.2023.00063"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/TII.2022.3164433"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00165"}],"container-title":["ACM Transactions on the Web"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3697840","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3697840","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:30Z","timestamp":1750295850000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3697840"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,11]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,28]]}},"alternative-id":["10.1145\/3697840"],"URL":"https:\/\/doi.org\/10.1145\/3697840","relation":{},"ISSN":["1559-1131","1559-114X"],"issn-type":[{"value":"1559-1131","type":"print"},{"value":"1559-114X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,11]]},"assertion":[{"value":"2023-11-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-15","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}