  Today's blockchain designs suffer from a trilemma claiming that no blockchain
system can simultaneously achieve decentralization, security, and performance
scalability. For current blockchain systems, as more nodes join the network,
the efficiency of the system (computation, communication, and storage) stays
constant at best. A leading idea for enabling blockchains to scale efficiency
is the notion of sharding: different subsets of nodes handle different portions
of the blockchain, thereby reducing the load for each individual node. However,
existing sharding proposals achieve efficiency scaling by compromising on trust
- corrupting the nodes in a given shard will lead to the permanent loss of the
corresponding portion of data. In this paper, we settle the trilemma by
demonstrating a new protocol for coded storage and computation in blockchains.
In particular, we propose PolyShard: ``polynomially coded sharding'' scheme
that achieves information-theoretic upper bounds on the efficiency of the
storage, system throughput, as well as on trust, thus enabling a truly scalable
system. We provide simulation results that numerically demonstrate the
performance improvement over state of the arts, and the scalability of the
PolyShard system. Finally, we discuss potential enhancements, and highlight
practical considerations in building such a system.
