Towards Efficient and Secure Sharding-Based Blockchain

Blockchain technology, despite its growing importance, has been argued for its poor scalability. Sharding has become an effective approach to addressing the scalability issue faced in the blockchain. It divides nodes into multiple groups (shards) so that they can process transactions in parallel. However, the 
efficiency and security in existing blockchain sharding ystems, despite being the basic design objectives, still suffer from many problems. To address these issues and achieve an efficient and secure blockchain sharding system, this thesis makes the following contributions.

First, existing blockchain sharding protocols do not scale well when tackling smart contracts (functions executing various logic). We present Jenga, a novel sharding-based approach for efficient smart contract processing. It requires all shards to share the logic for all contracts, hence multiple smart contracts can be executed within one round. Moreover, different shards store distinct states (state shards), and several orthogonal execution channels are established based on the state shards to reduce cross-shard communication. We implement Jenga and evaluation results illustrate that it achieves more than 1.5x throughput gain compared to the existing cutting-edge work.

Second, existing works, for security, tend to configure large shard sizes to maintain a small fraction of intra-shard malicious nodes, at an expense of limited concurrency. This leads to limited concurrency. Therefore, we propose CoChain, a highly concurrent and recoverable blockchain sharding system. It allows shards to have a larger fraction of malicious nodes (up to 2/3), thus reducing the shard size and increasing concurrency. To ensure security, CoChain requires shards to monitor each other, hence a shard with a high fraction of malicious nodes can recover from failure with the help of other shards. We implement CoChain based on Harmony and experimental results show that CoChain achieves a 35x throughput gain compared with Harmony.

Third, existing blockchain sharding, during intra-shard consensus and cross-shard transaction processing, either faces security issues or sacrifices great performance for security. Therefore, we propose SS-Chain for enhanced intra/cross-shard security and per- formance. We design pipelined consensus 
with less communication overhead to improve intra-shard consensus efficiency and defend against attacks via frequent leader rotations. We attach proofs to cross-shard transactions to ensure cross-shard security and improve efficiency through transaction batching and proof pruning. We implement SS-Chain and large-scale evaluation results demonstrate that it achieves a throughput of more than 10,000 tx/sec even under malicious behaviors.

[1] Ethereum Cross-Shard Function Call. https://ethresear.ch/t/atomic-cross-shard-function-calls-using-system-events-live-parameter-checking-contract-locking/7114.  
[2] Ethereum Sharding. https://ethereum.org/en/upgrades/sharding/.  
[3] Ethereum Smart Contract. https://ethereum.org/en/developers/docs/smart-contracts/.  
[4] Ethereum Yanking. https://ethresear.ch/t/cross-shard-contract-yanking/1450.  
[5] Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Maofan Yin. Synchotstu: Simple and practical synchronous state machine replication. In 2020 IEEE Symposium on Security and Privacy (SP), pages 106–118. IEEE, 2020.  
[6] Hayden Adams. Uniswap whitepaper. URL: https://hackmd. io/C-DvwDSfSxuhGd4WKE ig, 2020.  
[7] Mustafa Al-Bassam, Alberto Sonnino, Shehar Bano, Dave Hrycyszyn, and George Danezis. Chainspace: A sharded smart contracts platform. arXiv preprint arXiv:1708.03778, 2017.  
[8] Mohammad Javad Amiri, Divyakant Agrawal, and Amr El Abbadi. Sharper: Sharding permissioned blockchains over network clusters. In Proceedings of the 2021 International Conference on Management of Data, pages 76–88, 2021.  
[9] Georgia Avarikioti, Eleftherios Kokoris-Kogias, and Roger Wattenhofer. Divideand scale: Formalization of distributed ledger sharding protocols. arXiv preprint arXiv:1910.10434, 2019.  
[10] Shehar Bano, Alberto Sonnino, Mustafa Al-Bassam, Sarah Azouvi, Patrick McCorry,Sarah Meiklejohn, and George Danezis. Sok: Consensus in the age of blockchains.In Proceedings of the 1st ACM Conference on Advances in Financial Technologies,pages 183–198, 2019.  
[11] P Barrett. Zilliqa technical whitepaper, 2017.  
[12] Rafael Belchior, Andr´e Vasconcelos, S´ergio Guerreiro, and Miguel Correia. A survey on blockchain interoperability: Past, present, and future trends. arXiv preprint arXiv:2005.14282, 2020.  
[13] Dan Boneh, Joseph Bonneau, Benedikt B¨unz, and Ben Fisch. Verifiable delay functions. In Annual international cryptology conference, pages 757–788. Springer, 2018.  
[14] Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the weil pairing.In International conference on the theory and application of cryptology and information security, pages 514–532. Springer, 2001.  
[15] Ignacio Cascudo and Bernardo David. Scrape: Scalable randomness attested by public entities. In International Conference on Applied Cryptography and Network Security, pages 537–556. Springer, 2017.  
[16] Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance and proactive recovery. ACM Transactions on Computer Systems (TOCS), 20(4):398–461, 2002.  
[17] Miguel Castro, Barbara Liskov, et al. Practical byzantine fault tolerance. In OSDI, volume 99, pages 173–186, 1999.  
[18] Canhui Chen, Qian Ma, Xu Chen, and Jianwei Huang. User distributions in shardbased blockchain network: Queueing modeling, game analysis, and protocol design.In Proceedings of the Twenty-second International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing,pages 221–230, 2021.  
[19] Tyler Crain, Vincent Gramoli, Mikel Larrea, and Michel Raynal. Dbft: E!cient leaderless byzantine consensus and its application to blockchains. In 2018 IEEE 17th International Symposium on Network Computing and Applications (NCA), pages 1– 8. IEEE, 2018.  
[20] Tyler Crain, Christopher Natoli, and Vincent Gramoli. Red belly: a secure, fair and scalable open blockchain. In 2021 IEEE Symposium on Security and Privacy (SP), pages 466–483. IEEE, 2021.  
[21] Rasmus Dahlberg, Tobias Pulls, and Roel Peeters. E!cient sparse merkle trees. In Nordic Conference on Secure IT Systems, pages 199–215. Springer, 2016.  
[22] Hung Dang, Tien Tuan Anh Dinh, Dumitrel Loghin, Ee-Chien Chang, Qian Lin, and Beng Chin Ooi. Towards scaling blockchain systems via sharding. In Proceedings of the 2019 international conference on management of data, pages 123–140, 2019.  
[23] Sourav Das, Vinith Krishnan, and Ling Ren. E!cient cross-shard transaction execution in sharded blockchains. arXiv preprint arXiv:2007.14521, 2020.  
[24] Haihan Duan, Jiaye Li, Sizheng Fan, Zhonghao Lin, Xiao Wu, and Wei Cai. Metaverse for social good: A university campus prototype. In Proceedings of the 29th ACM International Conference on Multimedia, pages 153–161, 2021.  
[25] A Elrond. Highly scalable public blockchain via adaptive state sharding and secure proof of stake, 2019.  
[26] Paul Feldman. A practical scheme for non-interactive verifiable secret sharing. In 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), pages 427–438. IEEE, 1987.   
[27] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. Algorand: Scaling byzantine agreements for cryptocurrencies. In Proceedings of the 26th Symposium on Operating Systems Principles, pages 51–68, 2017. 
[28] Suyash Gupta, Sajjad Rahnama, Jelle Hellings, and Mohammad Sadoghi. Resilientdb: Global scale resilient blockchain fabric. arXiv preprint arXiv:2002.00160, 2020. 
[29] Jelle Hellings and Mohammad Sadoghi. Byshard: Sharding in a byzantine environment. Proceedings of the VLDB Endowment, 14(11):2230–2243, 2021. 
[30] Zicong Hong, Song Guo, Peng Li, and Wuhui Chen. Pyramid: A layered sharding blockchain system. In IEEE INFOCOM 2021-IEEE Conference on Computer Communications. IEEE, 2021. 
[31] Chenyu Huang, Zeyu Wang, Huangxun Chen, Qiwei Hu, Qian Zhang, Wei Wang, and Xia Guan. Repchain: A reputation-based secure, fast, and high incentive blockchain system via sharding. IEEE Internet of Things Journal, 8(6):4291–4304, 2020. 
[32] Huawei Huang, Xiaowen Peng, Jianzhou Zhan, Shenyang Zhang, Yue Lin, Zibin Zheng, and Song Guo. Brokerchain: A cross-shard blockchain protocol for account/balance-based state sharding. In IEEE INFOCOM, 2022. 
[33] Richard Karp, Christian Schindelhauer, Scott Shenker, and Berthold Vocking. Randomized rumor spreading. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 565–574. IEEE, 2000. 
[34] Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. Ouroboros: A provably secure proof-of-stake blockchain protocol. In Annual International Cryptology Conference, pages 357–388. Springer, 2017. 
[35] Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, Ewa Syta, and Bryan Ford. Omniledger: A secure, scale-out, decentralized ledger via sharding. In 2018 IEEE Symposium on Security and Privacy (SP), pages 583–598. IEEE, 2018. 
[36] Peilun Li, Guosai Wang, Xiaoqi Chen, Fan Long, and Wei Xu. Gosig: a scalable and high-performance byzantine consensus for consortium blockchains. In Proceedings of the 11th ACM Symposium on Cloud Computing, pages 223–237, 2020. 
[37] Songze Li, Mingchao Yu, Chien-Sheng Yang, Amir Salman Avestimehr, Sreeram Kannan, and Pramod Viswanath. Polyshard: Coded sharding achieves linearly scaling e!ciency and security simultaneously. IEEE Transactions on Information Forensics and Security, 16:249–261, 2020. 
[38] Yizhong Liu, Jianwei Liu, Marcos Antonio Vaz Salles, Zongyang Zhang, Tong Li, Bin Hu, Fritz Henglein, and Rongxing Lu. Building blocks of sharding blockchain systems: Concepts, approaches, and open problems. arXiv preprint arXiv:2102.13364, 2021. 
[39] Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, Seth Gilbert, and Prateek Saxena. A secure sharding protocol for open blockchains. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 17–30, 2016. 
[40] Dahlia Malkhi, Kartik Nayak, and Ling Ren. Flexible byzantine fault tolerance. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pages 1041–1053, 2019. 
[41] Petar Maymounkov and David Mazieres. Kademlia: A peer-to-peer information system based on the xor metric. In International Workshop on Peer-to-Peer Systems, pages 53–65. Springer, 2002. 
[42] Ralph C Merkle. Method of providing digital signatures, January 5 1982. US Patent 4,309,569. 
[43] Silvio Micali, Michael Rabin, and Salil Vadhan. Verifiable random functions. In 40th annual symposium on foundations of computer science (cat. No. 99CB37039), pages 120–130. IEEE, 1999. 
[44] Satoshi Nakamoto and A Bitcoin. A peer-to-peer electronic cash system. Bitcoin.– URL: https://bitcoin. org/bitcoin. pdf, 4, 2008. 
[45] Satoshi Nakamoto et al. Bitcoin: A peer-to-peer electronic cash system. 2008. 
[46] Lan N Nguyen, Truc DT Nguyen, Thang N Dinh, and My T Thai. Optchain: optimal transactions placement for scalable blockchain sharding. In 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS), pages 525–535. IEEE, 2019. 
[47] Rafael Pass and Elaine Shi. Hybrid consensus: E!cient consensus in the permissionless model. Cryptology ePrint Archive, 2016. 
[48] George Pˆırlea, Amrit Kumar, and Ilya Sergey. Practical smart contract sharding with ownership and commutativity analysis. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, pages 1327–1341, 2021. 
[49] Alejandro Ranchal-Pedrosa and Vincent Gramoli. Blockchain is dead, long live blockchain! accountable state machine replication for longlasting blockchain. arXiv preprint arXiv:2007.10541, 2020. 
[50] Liuyang Ren and Paul AS Ward. Evaluating optchain with bitcoin transactions. arXiv preprint arXiv:2109.07670, 2021. 
[51] Peter Robinson and Raghavendra Ramesh. Layer 2 atomic cross-blockchain function calls. arXiv preprint arXiv:2005.09790, 2020. 
[52] Pingcheng Ruan, Tien Tuan Anh Dinh, Dumitrel Loghin, Meihui Zhang, Gang Chen, Qian Lin, and Beng Chin Ooi. Blockchains vs. distributed databases: Dichotomy and fusion. In Proceedings of the 2021 International Conference on Management of Data, pages 1504–1517, 2021. 
[53] Mohamed Sabt, Mohammed Achemlal, and Abdelmadjid Bouabdallah. Trusted execution environment: what it is, and what it is not. In 2015 IEEE Trustcom/BigDataSE/ISPA, volume 1, pages 57–64. IEEE, 2015. 
[54] Siddhartha Sen and Michael J Freedman. Commensal cuckoo: Secure group partitioning for large-scale services. ACM SIGOPS Operating Systems Review, 46(1):33– 39, 2012. 
[55] Alex Skidanov and Illia Polosukhin. Nightshade: Near protocol sharding design. URL: https://nearprotocol. com/downloads/Nightshade. pdf, page 39, 2019. 
[56] Alberto Sonnino, Shehar Bano, Mustafa Al-Bassam, and George Danezis. Replay attacks and defenses against cross-shard consensus in sharded distributed ledgers. In 2020 IEEE European Symposium on Security and Privacy (EuroS&P), pages 294– 308. IEEE, 2020. 
[57] Ewa Syta, Philipp Jovanovic, Eleftherios Kokoris Kogias, Nicolas Gailly, Linus Gasser, Ismail Kho!, Michael J Fischer, and Bryan Ford. Scalable bias-resistant distributed randomness. In 2017 IEEE Symposium on Security and Privacy (SP), pages 444–460. Ieee, 2017. 
[58] Harmony Team. Harmony: Technical whitepaper, 2018. 
[59] Surya Viswanathan and Aakash Shah. The scalability trilemma in blockchain. Medium online, 20, 2018. 
[60] Dejan Vujiˇci´c, Dijana Jagodi´c, and Siniˇsa Rani´c. Blockchain technology, bitcoin, and ethereum: A brief overview. In 2018 17th international symposium infoteh-jahorina (infoteh), pages 1–6. IEEE, 2018. 
[61] Jiaping Wang and Hao Wang. Monoxide: Scale out blockchains with asynchronous consensus zones. In 16th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 19), pages 95–112, 2019. 
[62] Gavin Wood et al. Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper, 151(2014):1–32, 2014. 
[63] Zhuolun Xiang, Dahlia Malkhi, Kartik Nayak, and Ling Ren. Strengthened fault tolerance in byzantine fault tolerant replication. arXiv preprint arXiv:2101.03715, 2021. 
[64] Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham. Hotstu↵: Bft consensus with linearity and responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 347–356, 2019. 
[65] Mahdi Zamani, Mahnush Movahedi, and Mariana Raykova. Rapidchain: Scaling blockchain via full sharding. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 931–948, 2018. 
[66] Mengqian Zhang, Jichen Li, Zhaohua Chen, Hongyin Chen, and Xiaotie Deng. Cycledger: A scalable and secure parallel protocol for distributed ledger via sharding. In 2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 358–367. IEEE, 2020. 
[67] Peilin Zheng, Zibin Zheng, Jiajing Wu, and Hong-Ning Dai. Xblock-eth: Extracting and exploring blockchain data from ethereum. IEEE Open Journal of the Computer Society, 1:95–106, 2020.