The DOI matches its Crossref record; 43 of the 43 references it cites were found in a registry or an index.
RapidChain: Scaling Blockchain via Full Sharding
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. RapidChain employs 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, our protocol 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Douceur, J. R. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45748-8_24 · Cited by 4,419 · cited 3×
“In addition, the adversary can run a join-leave attack [25, 8], where it rejoins a constant (and small) number of corrupt nodes using fresh identities in order to compromise one or more committees.”
BackgroundMethodPolynomial Codes Over Certain Finite Fields
Reed, I. S., & Solomon, G. (1960) · Journal of the Society for Industrial and Applied Mathematics · doi:10.1137/0108018 · Cited by 3,662
Practical Byzantine fault tolerance
Castro, M., & Liskov, B. H. (1999) · Operating Systems Design and Implementation · doi:10.5555/296806.296824 · Cited by 3,205
Kademlia: A Peer-to-Peer Information System Based on the XOR Metric
Maymounkov, P., & Mazières, D. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45748-8_5 · Cited by 3,004
Lamport, L. (1998) · ACM Transactions on Computer Systems · doi:10.1145/279227.279229 · Cited by 2,737
Practical byzantine fault tolerance and proactive recovery
Castro, M., & Liskov, B. (2002) · ACM Transactions on Computer Systems · doi:10.1145/571637.571640 · Cited by 2,475
Reaching Agreement in the Presence of Faults
Pease, M., Shostak, R., & Lamport, L. (1980) · Journal of the ACM · doi:10.1145/322186.322188 · Cited by 2,359
Theory and practice of error control codes
Blahut, R. E. (1983) · Virtual Defense Library (Ministerio de Defensa) · Cited by 2,066
A Digital Signature Based on a Conventional Encryption Function
Merkle, R. C. (1988) · Lecture Notes in Computer Science · doi:10.1007/3-540-48184-2_32 · Cited by 1,998
Algorand: Scaling Byzantine Agreements for Cryptocurrencies
Gilad, Y., Hemo, R., Micali, S., Vlachos, G., & Zeldovich, N. (2017) · Proceedings of the 26th Symposium on Operating Systems Principles · doi:10.1145/3132747.3132757 · Cited by 1,499
A Secure Sharding Protocol For Open Blockchains
Luu, L., Narayanan, V., Zheng, C., Baweja, K., Gilbert, S., & Saxena, P. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978389 · Cited by 1,428
The Bitcoin Backbone Protocol: Analysis and Applications
Garay, J., Kiayias, A., & Leonardos, N. (2015) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-46803-6_10 · Cited by 1,366
Efficient dispersal of information for security, load balancing, and fault tolerance
Rabin, M. O. (1989) · Journal of the ACM · doi:10.1145/62044.62050 · Cited by 1,365
Pricing via processing or combatting junk mail
Dwork, C., & Naor, M. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48071-4_10 · Cited by 1,282
OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding
Kokoris-Kogias, E., Jovanovic, P., Gasser, L., Gailly, N., Syta, E., & Ford, B. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.000-5 · Cited by 1,253
Information propagation in the Bitcoin network
Decker, C., & Wattenhofer, R. (2013) · IEEE P2P 2013 Proceedings · doi:10.1109/p2p.2013.6688704 · Cited by 1,192
A practical scheme for non-interactive verifiable secret sharing
Feldman, P. (1987) · 28th Annual Symposium on Foundations of Computer Science (sfcs 1987) · doi:10.1109/sfcs.1987.4 · Cited by 1,125
The Honey Badger of BFT Protocols
Miller, A., Xia, Y., Croman, K., Shi, E., & Song, D. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978399 · Cited by 810
Spanner: Google's globally-distributed database
Corbett, J. C., Dean, J. B., Epstein, M., Fikes, A., Frost, C., Furman, J. J., Ghemawat, S., Gubarev, A., Heiser, C., Hochschild, P., et al. (2012) · doi:10.5555/2387880.2387905 · Cited by 807
Karp, R., Schindelhauer, C., Shenker, S., & Vocking, B. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892324 · Cited by 718
Micali, S., Rabin, M., & Vadhan, S. (2003) · 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) · doi:10.1109/sffcs.1999.814584 · Cited by 716
Analysis of the Blockchain Protocol in Asynchronous Networks
Pass, R., Seeman, L., & Shelat, A. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-56614-6_22 · Cited by 613
Asynchronous Byzantine agreement protocols
Bracha, G. (1987) · Information and Computation · doi:10.1016/0890-5401(87)90054-x · Cited by 440
Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement Using Cryptography
Cachin, C., Kursawe, K., & Shoup, V. (2005) · Journal of Cryptology · doi:10.1007/s00145-005-0318-0 · Cited by 437
Fast asynchronous Byzantine agreement with optimal resilience
Canetti, R., & Rabin, T. (1993) · Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 · doi:10.1145/167088.167105 · Cited by 309
Centrally Banked Cryptocurrencies
Danezis, G., & Meiklejohn, S. (2016) · Proceedings 2016 Network and Distributed System Security Symposium · doi:10.14722/ndss.2016.23187 · Cited by 300
An asynchronous [(n - 1)/3]-resilient consensus protocol
Bracha, G. (1984) · Proceedings of the third annual ACM symposium on Principles of distributed computing - PODC '84 · doi:10.1145/800222.806743 · Cited by 293
Hybrid Consensus: Efficient Consensus in the Permissionless Model
Pass, R., & Shi, E. (2017) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.disc.2017.39 · Cited by 234
On Expected Constant-Round Protocols for Byzantine Agreement
Katz, J., & Koo, C.-Y. (2006) · Lecture Notes in Computer Science · doi:10.1007/11818175_27 · Cited by 225
Bitcoin meets strong consistency
Decker, C., Seidel, J., & Wattenhofer, R. (2016) · Proceedings of the 17th International Conference on Distributed Computing and Networking · doi:10.1145/2833312.2833321 · Cited by 224
Cachin, C., Kursawe, K., & Shoup, V. (2000) · Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing · doi:10.1145/343477.343531 · Cited by 170
Economic Aspects of Bitcoin and Other Decentralized Public-Ledger Currency PlatformsPreprint
Evans, D. S. (2014) · SSRN Electronic Journal · doi:10.2139/ssrn.2424516 · Cited by 153
Distributed fingerprints and secure information dispersal
Krawczyk, H. (1993) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/164051.164075 · Cited by 90
ALGORAND: The Efficient and Democratic Ledger.Preprint
Micali, S. M. (2016) · arXiv (Cornell University) · Cited by 88
Bracha, G. F., & Toueg, S. (1983) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/800221.806706 · Cited by 87
Towards a scalable and robust DHT
Awerbuch, B., & Scheideler, C. (2006) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/1148109.1148163 · Cited by 76
PoW-Based Distributed Cryptography with No Trusted Setup
Andrychowicz, M., & Dziembowski, S. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48000-7_19 · Cited by 64
Commensal cuckoo: secure group partitioning for large-scale services
Sen, S., & Freedman, M. J. (2012) · ACM SIGOPS Operating Systems Review · doi:10.1145/2146382.2146389 · Cited by 61
Breaking the O ( n 2 ) bit barrier
King, V., & Saia, J. (2010) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/1835698.1835798 · Cited by 50
Scalable Secure Storage when Half the System Is Faulty
Alon, N., Kaplan, H. Y., Krivelevich, M., Malkhi, D., & Stern, J. P. (2000) · Lecture notes in computer science · doi:10.1007/3-540-45022-x_49 · Cited by 48
An O(lg n) expected rounds randomized Byzantine generals protocol
Bracha, G. F. (1985) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/22145.22180 · Cited by 43
Simple and efficient leader election in the full information model
Ostrovsky, R., Rajagopalan, S., & Vazirani, U. V. (1994) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/195058.195141 · Cited by 38
Addendum to “Scalable Secure Storage when Half the System is Faulty”
Alon, N., Kaplan, H. Y., Krivelevich, M., Malkhi, D., & Stern, J. P. (2004) · Cited by 13
Cited by
Blockchain for AI: review and open research challenges
Salah, K., Rehman, M. H. U., Nizamuddin, N., & Al-Fuqaha, A. (2019) · IEEE Access · doi:10.1109/access.2018.2890507 · Cited by 1,001
A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks
Wang, W., Hoang, D. T., Hu, P., Xiong, Z., Niyato, D., Wang, P., Wen, Y., & Kim, D. I. (2019) · IEEE Access · doi:10.1109/access.2019.2896108 · Cited by 995
Solutions to scalability of blockchain: a survey
Zhou, Q., Huang, H., Zheng, Z., & Bian, J. (2020) · IEEE Access · doi:10.1109/access.2020.2967218 · Cited by 689
Xu, M., Ng, W. C., Lim, W. Y. B., Kang, J., Xiong, Z., Niyato, D., Yang, Q., Shen, X., & Miao, C. (2023) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2022.3221119 · Cited by 564
Towards Scaling Blockchain Systems via Sharding
Dang, H., Dinh, T. T. A., Loghin, D., Chang, E.-C., Lin, Q., & Ooi, B. C. (2019) · Proceedings of the 2019 International Conference on Management of Data · doi:10.1145/3299869.3319889 · Cited by 559
Metadata
- Authors
- Zamani, M., Movahedi, M., & Raykova, M.
- Venue
- Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security
- Publisher
- ACM
- Published
- 2018-10-15
- Pages
- 931-948
- OpenAlex
- W2897676665
- Cited by
- 1,121
- References
- 43
- FWCI
- 66.97
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.