Paper 2022/413

Instachain: Breaking the Sharding Limits via Adjustable Quorums

Mustafa Safa Ozdayi, Yue Guo, and Mahdi Zamani

Abstract

Sharding is a key approach to scaling the performance of on-chain transactions: the network is randomly partitioned into smaller groups of validator nodes, known as \textit{shards}, each growing a disjoint ledger of transactions via state-machine replication (SMR) in parallel to other shards. As SMR protocols typically incur a quadratic message complexity in the network size, shards can process transactions significantly faster than the entire network. On the downside, shards cannot be made arbitrarily small due to the exponentially-increasing probability that malicious nodes take over a sufficient majority in small shards, compromising the security of SMR. In practice, this dictates relatively large shards with hundreds of nodes each, significantly limiting the scalability benefits of sharding. In this paper, we propose \textit{Instachain}, a novel sharding approach that breaks the scalability limits of sharding by reducing the shard size to significantly-smaller numbers than was previously considered possible. We achieve this by relaxing the liveness property for some of the shards while still preserving the safety property across all shards. To do this, we carefully adjust the quorum size parameter of the intra-shard SMR protocol to achieve maximum parallelism across all shards without compromising security. In addition, Instachain is the first sharding protocol to adopt the stateless blockchain model in shards, which in conjunction with a novel cross-shard verification technique allows the protocol to efficiently prevent double-spending attempts across significantly-more shards than previous work.