Paper 2020/943

Analysing and Improving Shard Allocation Protocols for Sharded Blockchains

Runchao Han, Jiangshan Yu, and Ren Zhang

Abstract

Sharding is a promising approach to scale permissionless blockchains. In a sharded blockchain, participants are split into groups, called shards, and each shard only executes part of the workloads. Despite its wide adoption in permissioned systems, transferring such success to permissionless blockchains is still an open problem. In permissionless networks, participants may join and leave the system at any time, making load balancing challenging. In addition, the adversary in such networks can launch the single-shard takeover attack by compromising a single shard’s consensus. To address these issues, participants should be securely and dynamically allocated into different shards. However, the protocol capturing such functionality – which we call shard allocation – is overlooked. In this paper, we study shard allocation protocols for permissionless blockchains. We formally define the shard allocation protocol and propose an evaluation framework. We apply the framework to evaluate the shard allocation subprotocols of seven state-of-the-art sharded blockchains, and show that none of them is fully correct or achieves satisfactory performance. We attribute these deficiencies to their extreme choices between two performance metrics: self-balance and operability. We observe and prove the fundamental trade-off between these two metrics, and identify a new property memory-dependency that enables parameterisation over this trade-off. Based on these insights, we propose Wormhole, a correct and efficient shard allocation protocol with minimal security assumptions and parameterisable self-balance and operability. We implement Wormhole and evaluate its overhead and performance metrics in a network with 128 shards and 32768 nodes. The results show that Wormhole introduces little overhead, achieves consistent self-balance and operability with our theoretical analysis, and allows the system to recover quickly from load imbalance.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
blockchainshardingshard allocation
Contact author(s)
runchao han @ monash edu
jiangshan yu @ monash edu
ren @ nervos org
History
2022-03-01: last of 4 revisions
2020-07-31: received
See all versions
Short URL
https://ia.cr/2020/943
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/943,
      author = {Runchao Han and Jiangshan Yu and Ren Zhang},
      title = {Analysing and Improving Shard Allocation Protocols for Sharded Blockchains},
      howpublished = {Cryptology ePrint Archive, Paper 2020/943},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/943}},
      url = {https://eprint.iacr.org/2020/943}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.