As the first study on shard allocation, the overlooked core component for shared permissionless blockchains, this paper
provides the first study on formalizing the shard allocation protocol
evaluates the shard allocation protocols in 7 state-of-the-art permissionless sharded blockchains, including Zilliqa and Ethereum 2.0
proves the impossibility of simultaneously achieving optimal self-balance and operability
identifies and defines a property memory-dependency that is necessary for shard allocation protocols to parameterize the trade-off between self-balance and operability
proposes Wormhole, a correct and efficient shard allocation protocol, and analyzes how to integrate Wormhole into sharded blockchains
implements Wormhole and evaluates its overhead and performance metrics in real-world settings
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.
Read the full text.
Authors
Runchao Han, Jiangshan Yu, Ren Zhang
Published in
4th ACM Conference on Advances in Financial Technologies (AFT '22), Sep 2022
More papers from the authors:
Which blockchain projects have published papers at the top security conferences? Here's an overview:
