Paper 2018/925

PolyShard: Coded Sharding Achieves Linearly Scaling Efficiency and Security Simultaneously

Songze Li, Mingchao Yu, A. Salman Avestimehr, Sreeram Kannan, and Pramod Viswanath

Abstract

Today’s blockchains do not scale in a meaningful sense. 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 - corrupting the nodes in a given shard will lead to the permanent loss of the corresponding portion of 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 paper, 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 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
BlockchainCoded ShardingEfficiency ScalingInformation Theory
Contact author(s)
songzeli @ usc edu
History
2018-10-02: received
Short URL
https://ia.cr/2018/925
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/925,
      author = {Songze Li and Mingchao Yu and A.  Salman Avestimehr and Sreeram Kannan and Pramod Viswanath},
      title = {PolyShard: Coded Sharding Achieves Linearly Scaling Efficiency and Security Simultaneously},
      howpublished = {Cryptology ePrint Archive, Paper 2018/925},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/925}},
      url = {https://eprint.iacr.org/2018/925}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.