EUVIMEDEUVIMED entdecken
Crossref

Efficient State Sharding in Blockchain via Density-based Graph Partitioning

Bo Yin, Peng Zhang, Tingxuan Chen

ACM Transactions on the Web · 28.02.2025 · 19 (1) · 1-28

DOI: 10.1145/3697840 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on the Web, online erschienen am 11.12.2024. Verfasst von Bo Yin und 2 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 50 Literaturangaben. Gefördert von: Natural Science Foundation of Changsha City, Natural Science Foundation of Hunan Province.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Sharding is a promising technique for increasing a blockchain system’s 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’s 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.

Förderung

  • Natural Science Foundation of Changsha City
  • Natural Science Foundation of Hunan Province

Zitieren

APA

Yin, B., Zhang, P., & Chen, T. (2025). Efficient State Sharding in Blockchain via Density-based Graph Partitioning. ACM Transactions on the Web, 19(1), 1-28. https://doi.org/10.1145/3697840

Vancouver

Yin B, Zhang P, Chen T. Efficient State Sharding in Blockchain via Density-based Graph Partitioning. ACM Transactions on the Web. 2025;19(1):1-28. doi:10.1145/3697840

BibTeX
@article{Yin2025,
  author = {Yin, Bo and Zhang, Peng and Chen, Tingxuan},
  title = {Efficient State Sharding in Blockchain via Density-based Graph Partitioning},
  journal = {ACM Transactions on the Web},
  year = {2025},
  volume = {19},
  number = {1},
  pages = {1--28},
  doi = {10.1145/3697840}
}
Kostenlos starten →