  Sharding is proposed to enhance blockchain scalability. However, a
size-security dilemma where every shard must be large enough to ensure its
security constrains the efficacy of individual shards and the degree of
sharding itself. Most existing sharding solutions therefore rely on either
weakening the adversary or making stronger assumptions on network links.
  This paper presents Arete, an optimally scalable blockchain sharding protocol
designed to resolve the dilemma based on an observation that if individual
shards can tolerate a higher fraction of (Byzantine) faults, we can securely
create smaller shards in a larger quantity. The key idea of Arete, therefore,
is to improve the security resilience/threshold of shards by dividing the
blockchain's State Machine Replication (SMR) process itself. Similar to modern
blockchains, Arete first decouples SMR in three steps: transaction
dissemination, ordering, and execution. However, unlike other blockchains, for
Arete, a single ordering shard performs the ordering task while multiple
processing shards perform the dissemination and execution of blocks. As
processing shards do not run consensus, each of those can tolerate up to half
compromised nodes. Moreover, the SMR process in the ordering shard is
lightweight as it only operates on the block digests. Second, Arete considers
safety and liveness against Byzantine failures separately to improve the safety
threshold further while tolerating temporary liveness violations in a
controlled manner. Apart from the creation of more optimal-size shards, such a
deconstructed SMR scheme also empowers us to devise a novel
certify-order-execute architecture to fully parallelize transaction handling,
thereby improving the performance of sharded blockchain systems. We implement
Arete and evaluate it on a geo-distributed AWS environment, showing that Arete
outperforms the state-of-the-art sharding protocol.
