Paper 2020/943

Analysing and Improving Shard Allocation Protocols for Sharded Blockchains

Runchao Han and Jiangshan Yu and Ren Zhang

Abstract

Sharding is considered one of the most promising approaches to solve the scalability issue of permissionless blockchains. In a sharding design, participants are split into groups, called shards, and each shard only executes part of the workloads. Despite its wide adoption in permissioned systems, where participants are fixed and known to everyone, transferring such success to permissionless blockchains is challenging, as it is difficult to allocate participants to different shards uniformly. Specifically, in a permissionless network, participants may join and leave the system at any time, and there can be a considerable number of Byzantine participants. This paper focuses on the shard allocation protocols designed for permissionless networks. We start from formally defining the shard allocation protocol, including its syntax, correctness properties, and performance metrics. Then, we apply this framework to evaluate the shard allocation subprotocols of seven state-of-the-art sharded blockchains. Our evaluation shows that none of them is fully correct or achieves satisfactory performance. We attribute these deficiencies to their redundant security assumptions and their extreme choices between two performance metrics: self-balance and operability. We further prove a fundamental trade-off between these two metrics, and prove that shard allocation should be non-memoryless in order to parametrise this trade-off. Non-memorylessness specifies that each shard allocation does not only rely on the current and the incoming system states, but also previous system states. Based on these insights, we propose WORMHOLE, a non-memoryless shard allocation protocol that minimises security assumptions and allows parametrisation between self-balance and operability. We formally prove WORMHOLE’s correctness, and show that WORMHOLE outperforms existing shard allocation protocols.