TY - JOUR
T1 - PolyShard
T2 - Coded Sharding Achieves Linearly Scaling Efficiency and Security Simultaneously
AU - Li, Songze
AU - Yu, Mingchao
AU - Yang, Chien Sheng
AU - Avestimehr, Amir Salman
AU - Kannan, Sreeram
AU - Viswanath, Pramod
N1 - Funding Information:
Manuscript received January 23, 2020; revised May 27, 2020; accepted June 24, 2020. Date of publication July 15, 2020; date of current version July 31, 2020. This work was supported in part by the Distributed Technology Research Foundation, Input–Output Hong Kong, in part by the National Science Foundation under Grant CCF-1705007, Grant CCF-1763673, and Grant CCF-1703575, in part by the Army Research Office under Grant W911NF1810332, and in part by the Defense Advanced Research Projects Agency (DARPA) under Contract HR001117C0053. This article was presented at the IEEE ISIT 2020. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Debdeep Mukhopadhyay. (Corresponding author: Chien-Sheng Yang.) Songze Li, Mingchao Yu, Chien-Sheng Yang, and Amir Salman Avestimehr are with the Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, CA 90089 USA (e-mail: songzeli@usc.edu; mingchay@usc.edu; chienshy@usc.edu; avestimehr@ee.usc.edu).
Funding Information:
This work was supported in part by the Distributed Technology Research Foundation, Input Output Hong Kong, in part by the National Science Foundation under Grant CCF-1705007, Grant CCF-1763673, and Grant CCF-1703575, in part by the Army Research Office under Grant W911NF1810332, and in part by the Defense Advanced Research Projects Agency (DARPA) under Contract HR001117C0053.
Publisher Copyright:
© 2005-2012 IEEE.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
KW - Scalability
KW - blockchain
KW - coded sharding
KW - decentralized networks
KW - information theory
KW - security and trust
UR - http://www.scopus.com/inward/record.url?scp=85089569669&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089569669&partnerID=8YFLogxK
U2 - 10.1109/TIFS.2020.3009610
DO - 10.1109/TIFS.2020.3009610
M3 - Article
AN - SCOPUS:85089569669
SN - 1556-6013
VL - 16
SP - 249
EP - 261
JO - IEEE Transactions on Information Forensics and Security
JF - IEEE Transactions on Information Forensics and Security
M1 - 9141331
ER -