Blockchain sharding method for reducing cross-shard transaction proportion

doi:10.11772/j.issn.1001-9081.2023060757

Abstract

Abstract:

To address the problems of high cross-shard transaction proportion and complex cross-shard transaction validation in optimizing blockchain performance， a blockchain sharding method for reducing cross-shard transaction proportion was proposed. Firstly， from the perspective of data sharding， a blockchain transaction sharding model was constructed， and evaluation indicators for sharding performance were provided. Then， for the long-term historical transaction data in blockchain， the sets of transaction frequencies for the sender and the receiver were constructed from the perspective of accounts’ correlation. Finally， a Frequency-considered Blockchain Transcation Sharding algorithm （FBTS） was designed to solve the problem of high cross-shard proportion in transaction sharding. The proposed algorithm was compared with Random Sharding Algorithm （RSA） and Modular Sharding Algorithm （MSA） under the sharding size of 2，3，5，7，15，20，30 and 50. The proposed algorithm outperformed RSA and MSA in terms of performance indicators such as cross-shard transaction proportion， average cross-shard number of accounts， and weighted average cross-shard number of accounts. In addition， the most accounts and transactions were concentrated at low cross-shard number， indicating that the completion of transaction does not involve multiple shards. The experimental results show that proposed algorithm can effectively reduce the cross-shard transaction proportion and shorten the delay of cross-shard transaction.

Key words: blockchain scalability, transaction sharding, transaction frequency, sharding size, cross-shard transaction proportion

摘要：

针对分片技术在优化区块链性能时引起的跨分片交易比例过高、跨分片交易验证复杂的问题，提出一种降低跨分片交易比例的区块链分片方法。首先，从数据分片的角度出发，构造区块链交易分片模型，并给出分片性能评价指标；其次，针对区块链中长期积累的交易数据，从账号关联性角度出发，构造发送方和接收方的交易频次集合；最后，设计考虑交易频次的区块链交易分片算法（FBTS），从而解决交易分片中跨分片比例过高的问题。在分片粒度为2、3、5、7、15、20、30和50的情况下，所提算法在跨分片交易比例、账号平均跨分片次数、账号的加权平均跨分片次数等性能指标方面均优于随机分片算法（RSA）和取模分片算法（MSA）。另外所提算法的大多数账号和交易量都集中分布在低跨分片次数处，说明交易的完成不需要多次跨分片。实验结果表明，所提算法可以有效地降低跨分片交易比例，缩短跨分片的交易的时延。

关键词: 区块链可扩展性, 交易分片, 交易频次, 分片粒度, 跨分片交易比例

CLC Number:

TP309

Jiao LI, Xiushan ZHANG, Yuanhang NING. Blockchain sharding method for reducing cross-shard transaction proportion[J]. Journal of Computer Applications, 2024, 44(6): 1889-1896.

李皎, 张秀山, 宁远航. 降低跨分片交易比例的区块链分片方法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1889-1896.

Figures/Tables 10

Fig. 1 Blockchain transaction sharding model

Fig.2 Cross-shard transaction proportion comparison for different algorithms

Fig.3 Account proportion with high cross-shard transaction under different threshold

Fig. 4 Account proportion with high cross-shard transaction under different sharding size

Fig. 5 Account proportion under different cross-shard number

Fig. 6 Transaction proportion under different cross-shard number

Tab. 1 Account proportion and transaction proportion under different cross-shard number with sharding size of 10

跨分片次数	FBTS		MSA		RSA
跨分片次数	$A r$ /%	$T r$ /%	$A r$ /%	$T r$ /%	$A r$ /%	$T r$ /%
0	6.58	8.89	5.23	0.31	5.19	0.21
1	60.10	11.24	51.13	2.55	50.31	2.27
2	21.95	18.26	17.71	4.13	17.98	3.35
3	6.56	15.66	9.40	9.94	8.88	7.74
4	3.65	9.34	6.87	8.95	6.39	9.07
5	0.75	8.02	3.96	6.77	4.49	6.05
6	0.24	11.66	2.39	6.17	2.86	7.51
7	0.08	5.18	1.38	6.61	1.68	6.91
8	0.04	3.28	0.95	6.19	1.21	9.15
9	0.05	8.44	0.98	48.36	1.01	47.72

Tab. 1 Account proportion and transaction proportion under different cross-shard number with sharding size of 10

跨分片次数	FBTS		MSA		RSA
跨分片次数	$A r$ /%	$T r$ /%	$A r$ /%	$T r$ /%	$A r$ /%	$T r$ /%
0	6.58	8.89	5.23	0.31	5.19	0.21
1	60.10	11.24	51.13	2.55	50.31	2.27
2	21.95	18.26	17.71	4.13	17.98	3.35
3	6.56	15.66	9.40	9.94	8.88	7.74
4	3.65	9.34	6.87	8.95	6.39	9.07
5	0.75	8.02	3.96	6.77	4.49	6.05
6	0.24	11.66	2.39	6.17	2.86	7.51
7	0.08	5.18	1.38	6.61	1.68	6.91
8	0.04	3.28	0.95	6.19	1.21	9.15
9	0.05	8.44	0.98	48.36	1.01	47.72

Fig. 7 Average cross-shard number of accounts

Fig.8 Weighted average cross-shard number of accounts

Fig. 9 Delay time under different cross-shard number

References 21

1	孙知信，张鑫，相峰，等. 区块链存储可扩展性研究进展［J］. 软件学报， 2021， 32（1）： 1-20.
	ZHANG Z X， ZHANG X， XIANG F， et al. Survey of storage scalability on blockchain ［J］. Journal of Software， 2021， 32（1）： 1-20.
2	毛志来，刘亚楠，孙惠平，等. 区块链性能扩展与安全研究［J］. 信息网络安全， 2020， 20（3）： 56-64.
	MAO Z L， LIU Y N， SUN H P， et al. Research on blockchain performance scalability and security ［J］. Netinfo Security， 2020， 20（3）： 56-64.
3	潘晨，刘志强，刘振，等区块链可扩展性研究：问题与方法［J］.计算机研究与发展， 2018， 55（10）： 2099-2110.
	PAN C， LIU Z Q， LIU Z， et al. Research on scalability of blockchain technology： problems and methods［J］. Journal of Computer Research and Development， 2018， 55（10）： 2099-2110.
4	黄华威，孔伟，彭肖文，等. 区块链分片技术综述［J］. 计算机工程， 2022， 48（6）： 1-10.
	HUANG H W， KONG W， PENG X W， et al. Survey on blockchain sharding technology［J］. Computer Engineering， 2022， 48（6）： 1-10.
5	王夫森，李志淮，田娜.提升分片规模和有效性的多轮PBFT验证方案［J］. 计算机工程与应用， 2020， 56（24）： 102-108.
	WANG F S， LI Z H， TIAN N. Multiple rounds of PBFT verification scheme to improve scale and validity of sharding ［J］. Computer Engineering and Applications， 2020， 56（24）： 102-108.
6	陈幻，王意洁.一种面向公有链的轻量级可扩展技术［J］. 计算机研究与发展， 2020， 57（7）： 1555-1567.
	CHEN H， WANG Y J. A lightweight scalable protocol for public blockchain ［J］. Journal of Computer Research and Development， 2020， 57（7）： 1555-1567.
7	WU X， JIANG W， SONG M， et al. An efficient sharding consensus algorithm for consortium chains［J］. Scientific Reports， 2023， 13： 20.
8	DANG H， DINH T T A， LOGHIN D， et al. Towards scaling blockchain systems via sharding ［C］// Proceedings of the 2019 International Conference on Management of Data. New York： ACM， 2019： 123-140.
9	潘吉飞，黄德才. 基于跳跃Hash和异步共识组的区块链动态分片模型［J］. 计算机科学，2020， 47（3）： 273-280.
	PAN J F， HUANG D C. Blockchain dynamic sharding model based on jump Hash and asynchronous consensus group［J］. Computer Science， 2020， 47（3）： 273-280.
10	ZAMANI M， MOVAHEDI M， RAYKOVA M. RapidChain：scaling blockchain via full sharding ［C］// Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM，2018： 931-948.
11	YU G， WANG X， YU K， et al. Survey： sharding in blockchains［J］. IEEE Access， 2020， 8： 14155-14181.
12	LIU Y， LIU J， SALLES M A V， et al. Building blocks of sharding blockchain systems： concepts， approaches， and open problems［J］. Computer Science Review， 2022， 46： 100513.
13	WANG J， WANG H. Monoxide：scale out blockchains with asynchronous consensus zones ［C］// Proceedings of the 16th USENIX Conference on Networked Systems Design and Implementation. Berkeley： USENIX Association， 2019： 95-112.
14	KOKORIS-KOGIAS E， JOVANOVIC P， GASSER L， et al. OmniLedger：a secure，scale-out，decentralized ledger via sharding ［C］// Proceedings of the 2018 IEEE Symposium on Security and Privacy. Piscataway： IEEE， 2018： 583-598.
15	CORTES-GOICOECHA M， FRANCESCHINI L， BAUTISTA-GOMEZ L. Resource analysis of Ethereum 2.0 clients ［C］// Proceedings of the 2021 3rd Conference on Blockchain Research & Applications for Innovative Networks and Services. Piscataway： IEEE， 2021： 1-8.
16	CASSEZ F， FULLER J， ASGAONKAR A. Formal verification of the Ethereum 2.0 Beacon Chain ［C］// Proceedings of the 2022 International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Cham： Springer， 2022： 167-182.
17	The ZILLIQA Team. The ZILLIQA technical whitepaper［EB/OL］. （2017-08-10）［2023-05-18］. .
18	西安石油大学. 一种基于交易频次分析的区块链分片方法： CN202210589229.8 ［P］. 2022-05-26.
	Xi’an Shiyou University. A blockchain sharding method based on transaction frequency analysis： CN202210589229.8 ［P］. 2022-05-26.
19	李莉，吴怡，杨祉坤，等. 基于分区型区块链医疗电子病历共享方案［J］. 计算机应用， 2022， 42（1）： 183-190.
	LI L， WU Y， YANG Z K， et al. Medical electronic medical record sharing scheme based on sharding-based blockchain［J］. Journal of Computer Applications， 2022， 42（1）： 183-190.
20	HUANG H， PENG X， ZHAN J， et al. BrokerChain： a cross-shard blockchain protocol for account/balance-based state sharding［C］// Proceedings of the 2022 IEEE Conference on Computer Communications. Piscataway： IEEE， 2022： 1968-1977.
21	李皎，王煜田，高耀芃. 一种抗合谋攻击的区块链网络分片算法［J］.计算机应用研究， 2023，40（1）： 28-32，41.
	LI J， WANG Y T， GAO Y P. Anti-collusion attack network sharding algorithm for blockchain ［J］. Application Research of Computers， 2023， 40（1）： 28-32，41.

[1]	Rui GAO, Xuebin CHEN, Zucuan ZHANG. Dynamic social network privacy publishing method for partial graph updating [J]. Journal of Computer Applications, 2024, 44(12): 3831-3838.
[2]	Yong XIANG, Yanjun LI, Dingyun HUANG, Yu CHEN, Huiqin XIE. Differential and linear characteristic analysis of full-round Shadow algorithm [J]. Journal of Computer Applications, 2024, 44(12): 3839-3843.
[3]	Zhenhao ZHAO, Shibin ZHANG, Wunan WAN, Jinquan ZHANG, zhi QIN. Delegated proof of stake consensus algorithm based on reputation value and strong blind signature algorithm [J]. Journal of Computer Applications, 2024, 44(12): 3717-3722.
[4]	Yiting WANG, Wunan WAN, Shibin ZHANG, Jinquan ZHANG, Zhi QIN. Linkable ring signature scheme based on SM9 algorithm [J]. Journal of Computer Applications, 2024, 44(12): 3709-3716.
[5]	Jing LIANG, Wunan WAN, Shibin ZHANG, Jinquan ZHANG, Zhi QIN. Traceability storage model of charity system oriented to master-slave chain [J]. Journal of Computer Applications, 2024, 44(12): 3751-3758.
[6]	Deyuan LIU, Jingquan ZHANG, Xing ZHANG, Wunan WAN, Shibin ZHANG, Zhi QIN. Cross-chain identity authentication scheme based on certificate-less signcryption [J]. Journal of Computer Applications, 2024, 44(12): 3731-3740.
[7]	Xin ZHANG, Jinquan ZHANG, Deyuan LIU, Wunan WAN, Shibin ZHANG, Zhi QIN. Cross-chain identity management scheme based on identity-based proxy re-encryption [J]. Journal of Computer Applications, 2024, 44(12): 3723-3730.
[8]	DENG Yilin, YU Fajiang. Pseudo-random number generator based on LSTM and separable self-attention mechanism#br# #br# [J]. Journal of Computer Applications, 0, (): 0-0.
[9]	. Correlation power analysis of advanced encryption standard algorithm based on uniform manifold approximation and projection [J]. Journal of Computer Applications, 0, (): 0-0.
[10]	. Dynamic searchable encryption scheme based on puncture pseudorandom function [J]. Journal of Computer Applications, 0, (): 0-0.
[11]	. fedPF: Federated learning for personalization and fairness [J]. Journal of Computer Applications, 0, (): 0-0.
[12]	. Review of research on conflict-based cache side-channel attacks and eviction sets [J]. Journal of Computer Applications, 0, (): 0-0.
[13]	. Secure and efficient frequency estimation method based on shuffled differential privacy [J]. Journal of Computer Applications, 0, (): 0-0.
[14]	. Blockchain-based model for notarization of simulation testing data in autonomous driving [J]. Journal of Computer Applications, 0, (): 0-0.
[15]	. Fine-grained result verifiable searchable encryption scheme with designated tester in cloud [J]. Journal of Computer Applications, 0, (): 0-0.