Ramburn, Tirathraj (2023) Improving Blockchain's Throughput via Small but Highly Fault-Tolerant Shards. Masters thesis, Concordia University.
Preview |
Text (application/pdf)
2MBRamburn_MCompSc_S2023.pdf - Accepted Version Available under License Spectrum Terms of Access. |
Abstract
Sharding increases concurrency in a blockchain system by splitting validators into groups (shards), thus allowing the system to increase throughput in proportion to the number of shards. Contemporary sharded systems assume that shards are ‘perfect’. Therefore, shards need to be formed in such a way that they have very low (negligible) probability of failure to be considered ‘perfect’. However, such an assumption has several limitations: 1) contemporary systems tend to use conservative parameters to satisfy the ‘perfect’ shard constraint. These include the use of large shard sizes or synchronous networks, which negatively affect throughput and performance; 2) in reality, shards can be faulty, and an invalid block validated by a faulty shard cannot be detected until after the block has been appended to the blockchain since there is no fault detection mechanism during transaction processing. We first present FlexiShard: a sharding protocol that uses a hybrid fault model (i.e., Byzantine and alive-but-corrupt faults) and Flexible Byzantine Fault Tolerance as its consensus algorithm, to allow for more practical parameters and create smaller shards that are responsive, more fault tolerant and more performant than contemporary bigger shards. Next, we present SecurShard: a hierarchical fault detection model that proposes mechanisms of combining shards into groups, one-to-all mapping of a transaction block to all shards in a group, and 100% consensus requirement to validate a block with finality; all these to ensure that a potentially invalid block is detected with high probability during transaction processing. This leads to the relaxation of the ‘perfect’ shard constraint and the possible usage of smaller shards, while still maintaining the collective fault tolerance of a system. Theoretical analyzes are presented for both models which demonstrate their advantages in terms of throughput, fault tolerance and performance over contemporary sharding systems.
| Divisions: | Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering |
|---|---|
| Item Type: | Thesis (Masters) |
| Authors: | Ramburn, Tirathraj |
| Institution: | Concordia University |
| Degree Name: | M. Comp. Sc. |
| Program: | Computer Science |
| Date: | 10 February 2023 |
| Thesis Supervisor(s): | Goswami, Dhrubajyoti |
| Keywords: | Blockchain, Sharding, Scalability, Byzantine Fault Tolerance, Consensus, Quorums |
| ID Code: | 991834 |
| Deposited By: | Tirathraj Ramburn |
| Deposited On: | 21 Jun 2023 14:42 |
| Last Modified: | 25 Jul 2024 00:00 |
References:
[1] S. Nakamoto, "Bitcoin: A Peer-to-Peer Electronic Cash System," May 2009.[2] V. Buterin, "Ethereum White Paper: A Next Generation Smart Contract & Decentralized Application Platform," 2013.
[3] "A Deep Dive Into Blockchain Scalability," 3 January 2020. [Online]. Available: https://crypto.com/university/blockchain-scalability.
[4] E. A. Brewer, "Lessons from giant-scale services," IEEE Internet Computing, vol. 5, pp. 46-55, 2001.
[5] N. Anita and M. Vijayalakshmi, "Blockchain security attack: A brief survey," in 2019 10th International Conference on Computing, Communication and Networking Technologies (ICCCNT), 2019.
[6] Y. Liu, J. Liu, M. A. V. Salles, Z. Zhang, T. Li, B. Hu, F. Henglein and R. Lu, "Building Blocks of Sharding Blockchain Systems: Concepts, Approaches, and Open Problems," Comput. Sci. Rev., vol. 46, p. 100513, 2021.
[7] L. Lamport, R. Shostak and M. Pease, "The Byzantine Generals Problem," ACM Trans. Program. Lang. Syst., vol. 4, p. 382–401, July 1982.
[8] M. Castro and B. Liskov, "Practical Byzantine Fault Tolerance," in Proceedings of the Third Symposium on Operating Systems Design and Implementation, USA, 1999.
[9] L. Ren, K. Nayak, I. Abraham and S. Devadas, "Practical Synchronous Byzantine Consensus," CoRR, vol. abs/1704.02397, 2017.
[10] M. Zamani, M. Movahedi and M. Raykova, "RapidChain: Scaling Blockchain via Full Sharding," in Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, New York, NY, USA, 2018.
[11] T. Hanke, M. Movahedi and D. Williams, "DFINITY Technology Overview Series, Consensus System," CoRR, vol. abs/1805.04548, 2018.
[12] E. Kokoris-Kogias, P. Jovanovic, L. Gasser, N. Gailly, E. Syta and B. Ford, "OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding," in 2018 IEEE Symposium on Security and Privacy (SP), 2018.
[13] L. Luu, V. Narayanan, C. Zheng, K. Baweja, S. Gilbert and P. Saxena, "A Secure Sharding Protocol For Open Blockchains," in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, New York, NY, USA, 2016.
[14] C. Dwork, N. Lynch and L. Stockmeyer, "Consensus in the Presence of Partial Synchrony," J. ACM, vol. 35, p. 288–323, April 1988.
[15] I. Abraham, "Synchrony, Asynchrony and Partial synchrony," 1 June 2019. [Online]. Available: https://decentralizedthoughts.github.io/2019-06-01-2019-5-31-models/.
[16] R. Pass and E. Shi, "Hybrid Consensus: Efficient Consensus in the Permissionless Model," in International Symposium on Distributed Computing, 2017.
[17] D. Malkhi, K. Nayak and L. Ren, "Flexible Byzantine Fault Tolerance," in Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, New York, NY, USA, 2019.
[18] S. King and S. Nadal, "Ppcoin: Peer-to-peer crypto-currency with proof-of-stake," self-published paper, August, vol. 19, 2012.
[19] V. Buterin, "An Incomplete Guide to Rollups," January 2021. [Online]. Available: https://vitalik.ca/general/2021/01/05/rollup.html.
[20] V. Buterin, Why Sharding is great: Demystifying the technical properties.
[21] V. Buterin, "The Limits to Blockchain Scalability," May 2021. [Online]. Available: https://vitalik.ca/general/2021/05/23/scaling.html.
[22] "HEDERA: A PUBLIC HASHGRAPH NETWORK & GOVERNING COUNCIL," 2018.
[23] S. Popov, "The tangle".
[24] C. Decker and R. Wattenhofer, "Information propagation in the Bitcoin network," IEEE P2P 2013 Proceedings, pp. 1-10, 2013.
[25] Y. Sompolinsky and A. Zohar, "Secure High-Rate Transaction Processing in Bitcoin," in Financial Cryptography, 2015.
[26] L. Lamport, "Proving the Correctness of Multiprocess Programs," IEEE Transactions on Software Engineering, Vols. SE-3, pp. 125-143, 1977.
[27] M. J. Fischer, N. A. Lynch and M. S. Paterson, "Impossibility of Distributed Consensus with One Faulty Process," J. ACM, vol. 32, p. 374–382, April 1985.
[28] H. Howard, D. Malkhi and A. Spiegelman, "Flexible Paxos: Quorum Intersection Revisited," ArXiv, vol. abs/1608.06696, 2016.
[29] J. R. Douceur, "The sybil attack," in Peer-to-Peer Systems: First InternationalWorkshop, IPTPS 2002 Cambridge, MA, USA, March 7–8, 2002 Revised Papers 1, 2002.
[30] C. Cachin, K. Kursawe and V. Shoup, "Random Oracles in Constantipole: Practical Asynchronous Byzantine Agreement Using Cryptography (Extended Abstract)," in Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, New York, NY, USA, 2000.
[31] A. Kate and I. Goldberg, "Distributed Key Generation for the Internet," in 2009 29th IEEE International Conference on Distributed Computing Systems, 2009.
[32] J. Bonneau, J. Clark and S. Goldfeder, "On Bitcoin as a public randomness source," IACR Cryptol. ePrint Arch., vol. 2015, p. 1015, 2015.
[33] I. Bentov, A. Gabizon and D. Zuckerman, "Bitcoin beacon," arXiv preprint arXiv:1605.04559, 2016.
[34] E. Syta, P. Jovanovic, E. K. Kogias, N. Gailly, L. Gasser, I. Khoffi, M. J. Fischer and B. Ford, "Scalable Bias-Resistant Distributed Randomness," in 2017 IEEE Symposium on Security and Privacy (SP), 2017.
[35] T. Ramburn and D. Goswami, "FlexiShard: a Flexible Sharding Scheme for Blockchain based on a Hybrid Fault Model," in 2022 21st International Symposium on Parallel and Distributed Computing (ISPDC), 2022.
[36] T. Rabin and M. Ben-Or, "Verifiable secret sharing and multiparty protocols with honest majority," in Proceedings of the twenty-first annual ACM symposium on Theory of computing, 1989.
[37] B. Schoenmakers, "A Simple Publicly Verifiable Secret Sharing Scheme and Its Application to Electronic," in Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, Berlin, 1999.
[38] M. O. Rabin, "Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance," J. ACM, vol. 36, p. 335–348, April 1989.
[39] I. S. Reed and G. Solomon, "Polynomial Codes Over Certain Finite Fields," Journal of The Society for Industrial and Applied Mathematics, vol. 8, pp. 300-304, 1960.
[40] M. Al-Bassam, A. Sonnino, S. Bano, D. Hrycyszyn and G. Danezis, "Chainspace: A sharded smart contracts platform," arXiv preprint arXiv:1708.03778, 2017.
[41] S. Kantesariya and D. Goswami, "Determining Optimal Shard Size in a Hierarchical Blockchain Architecture," in 2020 IEEE International Conference on Blockchain and Cryptocurrency (ICBC), 2020.
[42] G. Karame, E. Androulaki and S. Capkun, "Two Bitcoins at the Price of One? Double-Spending Attacks on Fast Payments in Bitcoin," IACR Cryptol. ePrint Arch., p. 248, 2012.
[43] D. Malkhi and M. Reiter, "Byzantine Quorum Systems," Distrib. Comput., vol. 11, p. 203–213, October 1998.
[44] H.-S. Siu, Y.-H. Chin and W.-P. Yang, "A note on consensus on dual failure modes," IEEE Transactions on Parallel and Distributed Systems, vol. 7, pp. 225-230, 1996.
[45] M. Christ, V. Nikolaenko and J. Bonneau, "Leader Election from Randomness Beacons and Other Strategies," November 2021. [Online]. Available: https://a16zcrypto.com/leader-election-from-randomness-beacons-and-other-strategies/.
[46] M. Zhang, J. Li, Z. Chen, H. Chen and X. Deng, "An Efficient and Robust Committee Structure for Sharding Blockchain," IEEE Transactions on Cloud Computing, pp. 1-14, 2022.
[47] S. Sen and M. J. Freedman, "Commensal Cuckoo: Secure Group Partitioning for Large-Scale Services," SIGOPS Oper. Syst. Rev., vol. 46, p. 33–39, February 2012.
[48] B. Awerbuch and C. Scheideler, "Towards a Scalable and Robust DHT," in Proceedings of the Eighteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, New York, NY, USA, 2006.
[49] M. Yin, D. Malkhi, M. K. Reiter, G. G. Gueta and I. Abraham, "HotStuff: BFT Consensus with Linearity and Responsiveness," in Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, New York, NY, USA, 2019.
Repository Staff Only: item control page
Download Statistics
Download Statistics