Cryptology ePrint Archive: Report 2018/460

RapidChain: Scaling Blockchain via Full Sharding

Mahdi Zamani and Mahnush Movahedi and Mariana Raykova

Abstract: A major approach to overcoming the performance and scalability limitations of current blockchain protocols is to use sharding, which is to split the overheads of processing transactions among multiple, smaller groups of nodes. These groups work in parallel to maximize performance while requiring significantly smaller communication, computation, and storage per node, allowing the system to scale to large networks. However, existing sharding-based blockchain protocols still require a linear amount of communication (in the number of participants) per transaction, and hence, attain only partially the potential benefits of sharding. We show that this introduces a major bottleneck to the throughput and latency of these protocols. Aside from the limited scalability, these protocols achieve weak security guarantees due to either a small fault resiliency (e.g., 1/8 and 1/4) or high failure probability, or they rely on strong assumptions (e.g., trusted setup) that limit their applicability to mainstream payment systems.

We propose RapidChain, the first sharding-based public blockchain protocol that is resilient to Byzantine faults from up to a 1/3 fraction of its participants, and achieves complete sharding of the communication, computation, and storage overhead of processing transactions without assuming any trusted setup. We introduce an optimal intra-committee consensus algorithm that can achieve very high throughputs via block pipelining, a novel gossiping protocol for large blocks, and a provably-secure reconfiguration mechanism to ensure robustness. Using an efficient cross-shard transaction verification technique, RapidChain avoids gossiping transactions to the entire network. Our empirical evaluations suggest that RapidChain can process (and confirm) more than 7,300 tx/sec with an expected confirmation latency of roughly 8.7 seconds in a network of 4,000 nodes with an overwhelming time-to-failure of more than 4,500 years.

Category / Keywords: cryptographic protocols / Blockchain, Consensus, Distributed Cryptography

Original Publication (with minor differences): ACM Conference on Computer and Communications Security (CCS 2018)
DOI:
10.1145/3243734.3243853

Date: received 16 May 2018, last revised 29 Aug 2018

Contact author: mzamani at visa com

Available format(s): PDF | BibTeX Citation

Version: 20180829:063438 (All versions of this report)

Short URL: ia.cr/2018/460


[ Cryptology ePrint archive ]