PolyShard: Coded sharding achieves linearly scaling efficiency and trust simultaneously in Blockchains

Sreeram Kannan
Assistant Professor, University of Washington
Date: Nov. 30, 2018 / Time: 1:15pm

Abstract

Today's blockchains do not scale in a meaningful sense. This is because the system is built on the basis of full replication - every node stores the entire blockchain as well as validating each blockchain entry. As more nodes join the system, the efficiency of the system (computation, communication, and storage) degrades, or at best stays constant. 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 - it is sufficient for the nodes in a given shard to get corrupted in order to lose that portion of the data. We observe that sharding is similar to replication coding, which is known to be inefficient and fragile in the coding theory community. In this talk, we demonstrate a new protocol for coded storage and computation in blockchains. In particular, we propose PolyShard: "Polynomially coded sharding" scheme that achieves information-theoretic lower bounds on storage, computational costs as well as on trust, thus enabling a truly scalable system. We show why existing sharding proposals cannot achieve these lower bounds, and highlight practical considerations in building such a system.

This is joint work with Songze Li, Mingchao Yu, Salman Avestimehr, and Pramod Viswanath. The full paper can be found at https://arxiv.org/abs/1809.10361.

Bio

Sreeram Kannan is currently an assistant professor at University of Washington, Seattle. He was a postdoctoral scholar at University of California, Berkeley between 2012-2014 before which he received his Ph.D. in Electrical and Computer Engineering and M.S. in mathematics from the University of Illinois Urbana Champaign. He is a recipient of the 2017 NSF Faculty Early CAREER award, the 2015 Washington Research Foundation Early Career Faculty award, the 2013 Van Valkenburg outstanding dissertation award from UIUC, a co-recipient of the 2010 Qualcomm Cognitive Radio Contest first prize, a recipient of 2010 Qualcomm (CTO) Roberto Padovani outstanding intern award, a recipient of the gold medal from the Indian Institute of Science, 2008, and a co-recipient of Intel India Student Research Contest first prize, 2006. His research interests are in information theory and its applications in communication networks, machine learning, computational biology and blockchain systems.