Paper 2020/943

Analysing and Improving Shard Allocation Protocols for Sharded Blockchains

Runchao Han and 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, there exists Byzantine participants, who may launch various attacks on the blockchain. To address these issues, participants should be securely and dynamically allocated into different shards uniformly. 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 then 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 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 identify a fundamental property non-memorylessness that enables parametrisation on 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.