区块链分片技术综述

doi:10.19678/j.issn.1000-3428.0063887

摘要/Abstract

摘要： 区块链作为分布式账本的关键技术之一，其去中心化、可匿名、不可篡改的特性受到学术界和工业界的青睐，被广泛应用于金融、数字货币、公共服务等领域。分片技术作为区块链扩容的主流方式之一，能够在不降低区块链去中心化程度的同时实现高性能的链上扩容，从而解决区块链可拓展性不足以及吞吐量较低的问题。介绍近年来出现的分片技术以及相关协议，总结分片技术的关键理论与方法，从分片配置、重配置、片内共识协议、跨片共识协议、状态存储等方面对分片技术方案进行对比，归纳不同分片方案在网络分片、交易分片、状态分片等设计中存在的优势和不足。同时，阐述一些经典分片技术在性能和实现方式上的特点，对许可区块链和无许可区块链、片内共识协议、跨片共识协议、准入性方案、状态分片方式等进行分析和概述。在此基础上，从分片内、分片间以及系统层级的角度总结分片技术当前所面临的困境和挑战，并对该领域的发展前景及未来研究方向加以展望。

关键词: 区块链, 分片技术, 共识机制, 分布式账本, 可扩展性

Abstract: As one of the key technologies of distributed ledger, blockchain is favored by academia and industry for its decentralized, anonymous, and tamper-proof characteristics.It is widely used in finance, digital currency, public services, and other fields.As one of the mainstream methods of blockchain, sharding technology can realize high-performance capacity expansion on the chain without reducing the degree of decentralization of the blockchain, to address problems of insufficient scalability and low throughput.This study introduces the sharding technology and related protocols of recent years, summarizing the key theories and methods of sharding, comparing the sharding technology schemes in terms of of sharding configuration, reconfiguration, intrachip consensus protocol, cross-chip consensus protocol, and state storage.The advantages and disadvantages of different sharding schemes are further summarized with respect to the design of the network, transaction, and sharding state.The characteristics of some classical fragmentation technologies are expounded upon in terms of performance and implementation mode, analyzing and summarizing licensed blockchain and unlicensed blockchain on-chip consensus protocol, cross-chip consensus protocol, access scheme, state fragmentation mode, and the like.On this basis, the current difficulties and challenges of sharding technology are presented from the perspective of system level intra-sharding and inter-sharding, suggesting future development prospects and research directions in this field.

Key words: blockchain, sharding technology, consensus mechanism, distributed ledger, scalability

中图分类号:

TP391

黄华威, 孔伟, 彭肖文, 郑子彬. 区块链分片技术综述[J]. 计算机工程, 2022, 48(6): 1-10.

HUANG Huawei, KONG Wei, PENG Xiaowen, ZHENG Zibin. Survey on Blockchain Sharding Technology[J]. Computer Engineering, 2022, 48(6): 1-10.

https://www.ecice06.com/CN/Y2022/V48/I6/1

图/表 3

参考文献

[1] LUU L, NARAYANAN V, ZHENG C D, et al.A secure sharding protocol for open blockchains[C]//Proceedings of 2016 ACM SIGSAC Conference on Computer and Communications Security.New York, USA:ACM Press, 2016:17-30.
[2] CORBETT J C, DEAN J, EPSTEIN M, et al.Spanner:Google's globally distributed database[J].ACM Transactions on Computer Systems, 2013, 31(3):8.
[3] GLENDENNING L, BESCHASTNIKH I, KRISHNAMURTHY A, et al.Scalable consistency in scatter[C]//Proceedings of the 23rd ACM Symposium on Operating Systems Principles.New York, USA:ACM Press, 2011:15-28.
[4] DANEZIS G, MEIKLEJOHN S.Centrally banked cryptocurrencies[EB/OL].[2022-01-05].http://www0.cs.ucl.ac.uk/staff/G.Danezis/papers/ndss16currencies.pdf.
[5] CROMAN K, DECKER C, EYAL I, et al.On scaling decentralized blockchains[M].Berlin, Germany:Springer, 2016.
[6] SYTA E, JOVANOVIC P, KOGIAS E K, et al.Scalable bias-resistant distributed randomness[C]//Proceedings of 2017 IEEE Symposium on Security and Privacy.Washington D.C., USA:IEEE Press, 2017:15-22.
[7] ABRAHAM I, MALKHI D, NAYAK K, et al.Solidus:an incentive-compatible cryptocurrency based on permissionless Byzantine consensus[EB/OL].[2022-01-05].https://www.cs.umd.edu/~kartik/papers/8_solidus.pdf.
[8] SONNINO A, BANO S, AL-BASSAM M, et al.Replay attacks and defenses against cross-shard consensus in sharded distributed ledgers[C]//Proceedings of 2020 IEEE European Symposium on Security and Privacy.Washington D.C., USA:IEEE Press, 2020:134-145.
[9] SQUAREPANTS S.Bitcoin:a peer-to-peer electronic cash system[EB/OL].[2022-01-05].https://bitcoin.org/bitcoin.pdf.
[10] Bitcoin Wiki.Scalability[EB/OL].[2022-01-05].https://blochchain.info/stats.
[11] CHERNET H F, JILLEDI S K.A next-generation smart contract and decentralized blockchain platform:a case study on ethiopia[EB/OL].[2022-01-05].https://www.researchgate.net/publication/348863176_A_Next-Generation_Smart_Contract_and_Decentralized_blockchain_Platform_A_case_study_on_Ethiopia.
[12] Visa.Visa's transcations per second[EB/OL].[2022-01-05].https://usa.visa.com/content_library/modal/benefits/accepting/visa.html.
[13] QI X D, ZHANG Z, JIN C Q, et al.BFT-store:storage partition for permissioned blockchain via erasure coding[C]//Proceedings of 2020 IEEE International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2020:15-26.
[14] ZHOU Q H, HUANG H W, ZHENG Z B, et al.Solutions to scalability of blockchain:a survey[J].IEEE Access, 2020, 8:16440-16455.
[15] MILOJICIC D S, KALOGERAKI V, LUKOSE R, et al.Peer-to-peer computing[EB/OL].[2022-01-05].https://www.hpl.hp.com/techreports/2002/HPL-2002-57R1.pdf.
[16] JIA D Y, XIN J C, WANG Z Q, et al.Optimized data storage method for sharding-based blockchain[J].IEEE Access, 2021, 9:67890-67900.
[17] POON J, DRYJA T.The bitcoin lightning network:scalable off-chain instant payments[EB/OL].[2022-01-05].https://coinrivet.com/research/papers/the-bitcoin-lightning-network-scalable-off-chain-instant-payments/.
[18] DAS P, ECKEY L, FRASSETTO T, et al.FastKitten:practical smart contracts on bitcoin[C]//Proceedings of the 28th USENIX Security Symposium.San Diego, USA:USENIX Association, 2019:801-818.
[19] ZHANG P Y, ZHOU M C.Security and trust in blockchains:architecture, key technologies, and open issues[J].IEEE Transactions on Computational Social Systems, 2020, 7(3):790-801.
[20] Sharding FAQ[EB/OL].[2022-01-05].https://github.com/ethereum/wiki/wiki/sharding/faq.
[21] EYAL I, GENCER A E, SIRER E G, et al.Bitcoin-NG:a scalable blockchain protocol[C]//Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation.San Diego, USA:USENIX Association, 2016:45-59.
[22] DWORK C, NAOR M.Pricing via processing or combatting junk mail[C]//Proceedings of International Cryptology Conference on Advances in Cryptology.Berlin, Germany:Springer, 1993:139-147.
[23] WANG Z Y, LIU J W, ZHANG Z Y, et al.A combined micro-block chain truncation attack on bitcoin-NG[M].Berlin, Germany:Springer, 2019.
[24] 高政风, 郑继来, 汤舒扬, 等.基于DAG的分布式账本共识机制研究[J].软件学报, 2020, 31(4):1124-1142. GAO Z F, ZHENG J L, TANG S Y, et al.State-of-the-art survey of consensus mechanisms on DAG-based distributed ledger[J].Journal of Software, 2020, 31(4):1124-1142.(in Chinese)
[25] ANDROULAKI E, BARGER A, BORTNIKOV V, et al.Hyperledger fabric:a distributed operating system for permissioned blockchains[C]//Proceedings of the 13th EuroSys Conference.Washington D.C., USA:IEEE Press, 2018:1-15.
[26] ZHENG P L, XU Q Q, ZHENG Z B, et al.Meepo:sharded consortium blockchain[C]//Proceedings of IEEE International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2021:1847-1852.
[27] ESPEL T, KATZ L, ROBIN G.Proposal for protocol on a quorum blockchain with zero knowledge[EB/OL].[2022-01-05].https://eprint.iacr.org/2017/1093.pdf.
[28] DANG H, DINH T T A, LOGHIN D, et al.Towards scaling blockchain systems via sharding[C]//Proceedings of 2019 International Conference on Management of Data.Washington D.C., USA:IEEE Press, 2019:123-140.
[29] MCKEEN F, ALEXANDROVICH I, BERENZON A, et al.Innovative instructions and software model for isolated execution[EB/OL].[2022-01-05].https://dl.acm.org/doi/10.1145/2487726.2488368.
[30] AMIRI M J, AGRAWAL D, EL ABBADI A.SharPer:sharding permissioned blockchains over network clusters[C]//Proceedings of 2021 International Conference on Management of Data.New York, USA:ACM Press, 2021:16-23.
[31] KOKORIS-KOGIAS E, JOVANOVIC P, GASSER L, et al.OmniLedger:a secure, scale-out, decentralized ledger via sharding[C]//Proceedings of IEEE Symposium on Security and Privacy.Washington D.C., USA:IEEE Press, 2018:583-598.
[32] ZAMANI M, MOVAHEDI M, RAYKOVA M.RapidChain:scaling blockchain via full sharding[C]//Proceedings of 2018 ACM SIGSAC Conference on Computer and Communications Security.New York, USA:ACM Press, 2018:931-948.
[33] WANG J, WANG H.Monoxide:scale out blockchains with asynchronous consensus zones[C]//Proceedings of the 16th USENIX Symposium on Networked Systems Design and Implementation.San Diego, USA:USENIX Association, 2019:95-112.
[34] 袁勇, 倪晓春, 曾帅, 等.区块链共识算法的发展现状与展望[J].自动化学报, 2018, 44(11):2011-2022. YUAN Y, NI X C, ZENG S, et al.Blockchain consensus algorithms:the state of the art and future trends[J].Acta Automatica Sinica, 2018, 44(11):2011-2022.(in Chinese)
[35] BAGUI S, NGUYEN L T.Database sharding:to provide fault tolerance and scalability of big data on the cloud[J].International Journal of Cloud Applications and Computing, 2015, 5(2):36-52.
[36] LI S Z, YU M C, YANG C S, et al.PolyShard:coded sharding achieves linearly scaling efficiency and security simultaneously[C]//Proceedings of IEEE International Symposium on Information Theory.Washington D.C., USA:IEEE Press, 2020:203-208.
[37] KING V, SAIA J, SANWALANI V, et al.Towards secure and scalable computation in peer-to-peer networks[C]//Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science.Washington D.C., USA:IEEE Press, 2006:87-98.
[38] JOHNSON D, MENEZES A, VANSTONE S.The elliptic curve digital signature algorithm[J].International Journal of Information Security, 2001, 1(1):36-63.
[39] BONNEAU J, FELTEN E W, GOLDFEDER S, et al.Why buy when you can rent?Bribery attacks on bitcoin consensus[C]//Proceedings of International Conference on Financial Cryptography and Data Security.Berlin, Germany:Springer, 2016:19-26.
[40] DOUCEUR J R.The sybil attack[EB/OL].[2022-01-05].https://nakamotoinstitute.org/static/docs/the-sybil-attack.pdf.
[41] HUANG H W, HUANG Z Y, PENG X W, et al.MVCom:scheduling most valuable committees for the large-scale sharded blockchain[C]//Proceedings of IEEE International Conference on Distributed Computing Systems.Washington D.C., USA:IEEE Press, 2021:629-639.
[42] FRÉVILLE A.The multidimensional 0-1 knapsack problem:an overview[J].European Journal of Operational Research, 2004, 155(1):1-21.
[43] SEN S, FREEDMAN M.Commensal cuckoo:secure group partitioning for large-scale services[J].ACM SIGOPS Operating Systems Review, 2012, 46(1):33-39.
[44] CHEN H, WANG Y J.SSChain:a full sharding protocol for public blockchain without data migration overhead[J].Pervasive and Mobile Computing, 2019, 59:101055.
[45] SZYDLO M.Merkle tree traversal in log space and time[J].Lecture Notes in Computer Science, 2004, 3027:541-554.
[46] 甘俊, 李强, 陈子豪, 等.区块链实用拜占庭容错共识算法的改进[J].计算机应用, 2019, 39(7):2148-2155. GAN J, LI Q, CHEN Z H, et al.Improvement of blockchain practical Byzantine fault tolerance consensus algorithm[J].Journal of Computer Applications, 2019, 39(7):2148-2155.(in Chinese)
[47] KOKORIS-KOGIAS E, JOVANOVIC P, GAILLY N, et al.Enhancing bitcoin security and performance with strong consistency via collective signing[EB/OL].[2022-01-05].https://www.usenix.org/system/files/conference/usenixsecurity16/sec16_paper_kokoris-kogias.pdf.
[48] KARP R, SCHINDELHAUER C, SHENKER S, et al.Randomized rumor spreading[C]//Proceedings of the 41st Annual Symposium on Foundations of Computer Science.Washington D.C., USA:IEEE Press, 2000:565-574.
[49] ABRAHAM I, GUETA G, MALKHI D, et al.Revisiting fast practical Byzantine fault tolerance[EB/OL].[2022-01-05].https://arxiv.org/abs/1712.01367.
[50] PLATFORM S B.The Zilliqa project:a secure, scalable blockchain platform[EB/OL].[2022-01-05].https://cryptorating.eu/whitepapers/Zilliqa/positionpaper.pdf.
[51] MAXWELL G, POELSTRA A, SEURIN Y, et al.Simple Schnorr multi-signatures with applications to bitcoin[J].Designs, Codes and Cryptography, 2019, 87(9):2139-2164.
[52] LIU Y, LIU J, LI D, et al.Fleetchain:a secure scalable and responsive blockchain achieving optimal sharding[C]//Proceedings of International Conference on Algorithms and Architectures for Parallel Processing.Berlin, Germany:Springer, 2020:409-425.
[53] Ethereum 2.0 Spec.Ethereum 2.0 phase 0-the beacon chain, 2020[EB/OL].[2022-01-05].https://github.com/ethereum/eth2.0-specs/blob/dev/specs/phase0/beacon-chain.md.
[54] MAYMOUNKOV P, ERES D M.Kademlia:a peer-to-peer information system based on the XOR metric[EB/OL].[2022-01-05].https://www.scs.stanford.edu/~dm/home/papers/kpos.pdf.
[55] HUANG H, PENG X, ZHAN J, et al.BrokerChain:a cross-shard blockchain protocol for account/balance-based state sharding[C]//Proceedings of IEEE International Conference on Computer Communications.Washington D.C., USA:IEEE Press, 2022:145-156.
[56] KARYPIS G, KUMAR V.A fast and high quality multilevel scheme for partitioning irregular graphs[J].SIAM Journal on Scientific Computing, 1998, 20(1):359-392.
[57] NGUYEN L N, NGUYEN T D T, DINH T N, et al.OptChain:optimal transactions placement for scalable blockchain sharding[C]//Proceedings of IEEE International Conference on Distributed Computing Systems.Washington D.C., USA:IEEE Press, 2019:525-535.
[58] HUANG H W, YUE Z Y, PENG X W, et al.Elastic resource allocation against imbalanced transaction assignments in sharding-based permissioned blockchains[J].IEEE Transactions on Parallel and Distributed Systems, 2022, 33(10):2372-2385.
[59] HONG Z C, GUO S, LI P, et al.Pyramid:a layered sharding blockchain system[C]//Proceedings of IEEE Conference on Computer Communications.Washington D.C., USA:IEEE Press, 2021:1-10.
[60] SYTA E, TAMAS I, VISHER D, et al.Keeping authorities "honest or bust" with decentralized witness cosigning[C]//Proceedings of IEEE Symposium on Security and Privacy.Washington D.C., USA:IEEE Press, 2016:526-545.
[61] YAO W, YE J Y, MURIMI R, et al.A survey on consortium blockchain consensus mechanisms[EB/OL].[2022-01-05].https://arxiv.org/abs/2102.12058.
[62] SABT M, ACHEMLAL M, BOUABDALLAH A.Trusted execution environment:what it is, and what it is not[C]//Proceedings of IEEE Trustcom/BigDataSE/ISPA.Washington D.C., USA:IEEE Press, 2015:57-64.
[63] ZHANG S J, LEE J H.Double-spending with a sybil attack in the bitcoin decentralized network[J].IEEE Transactions on Industrial Informatics, 2019, 15(10):5715-5722.
[64] ZOU D Q, ZHENG W D, LONG J J, et al.Constructing trusted virtual execution environment in P2P grids[J].Future Generation Computer Systems, 2010, 26(5):769-775.
[65] ZHANG J T, HONG Z C, QIU X Y, et al.SkyChain:a deep reinforcement learning-empowered dynamic blockchain sharding system[C]//Proceedings of the 49th International Conference on Parallel Processing.Washington D.C., USA:IEEE Press, 2020:1-11.
[66] ZHENG J, HUANG H W, LI C L, et al.Revisiting double-spending attacks on the bitcoin blockchain:new findings[C]//Proceedings of IEEE/ACM International Symposium on Quality of Service.Washington D.C., USA:IEEE Press, 2021:1-6.
[67] GOLAN GUETA G, ABRAHAM I, GROSSMAN S, et al.SBFT:a scalable and decentralized trust infrastructure[C]//Proceedings of the 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks.Washington D.C., USA:IEEE Press, 2019:568-580.
[68] YIN M F, MALKHI D, REITER M K, et al.HotStuff:BFT consensus with linearity and responsiveness[C]//Proceedings of 2019 ACM Symposium on Principles of Distributed Computing.New York, USA:ACM Press, 2019:347-356.
[69] SAAD M, COOK V, NGUYEN L, et al.Partitioning attacks on bitcoin:colliding space, time, and logic[C]//Proceedings of IEEE International Conference on Distributed Computing Systems.Washington D.C., USA:IEEE Press, 2019:1175-1187.
[70] NGUYEN T, THAI M T.Denial-of-service vulnerability of Hash-based transaction sharding:attacks and countermeasures[EB/OL].[2022-01-05].https://arxiv.org/abs/2007.08600.

选择文件类型/文献管理软件名称

选择包含的内容