Improving Blockchain's Throughput via Small but Highly Fault-Tolerant Shards

Sharding increases concurrency in a blockchain system by splitting validators into groups (shards), thus allowing the system to increase throughput in proportion to the number of shards. Contemporary sharded systems assume that shards are ‘perfect’. Therefore, shards need to be formed in such a way that they have very low (negligible) probability of failure to be considered ‘perfect’. However, such an assumption has several limitations: 1) contemporary systems tend to use conservative parameters to satisfy the ‘perfect’ shard constraint. These include the use of large shard sizes or synchronous networks, which negatively affect throughput and performance; 2) in reality, shards can be faulty, and an invalid block validated by a faulty shard cannot be detected until after the block has been appended to the blockchain since there is no fault detection mechanism during transaction processing. We first present FlexiShard: a sharding protocol that uses a hybrid fault model (i.e., Byzantine and alive-but-corrupt faults) and Flexible Byzantine Fault Tolerance as its consensus algorithm, to allow for more practical parameters and create smaller shards that are responsive, more fault tolerant and more performant than contemporary bigger shards. Next, we present SecurShard: a hierarchical fault detection model that proposes mechanisms of combining shards into groups, one-to-all mapping of a transaction block to all shards in a group, and 100% consensus requirement to validate a block with finality; all these to ensure that a potentially invalid block is detected with high probability during transaction processing. This leads to the relaxation of the ‘perfect’ shard constraint and the possible usage of smaller shards, while still maintaining the collective fault tolerance of a system. Theoretical analyzes are presented for both models which demonstrate their advantages in terms of throughput, fault tolerance and performance over contemporary sharding systems