Multiple Rounds Validation Scheme to Reduce Rollback Probability of Cross-Shard Transactions

doi:10.3778/j.issn.1002-8331.2009-0080

Abstract

Abstract: The cross-shard transaction in the blockchain sharding scheme is coordinated by multiple shards. In the sharding scheme using the practical Byzantine fault tolerance（PBFT） class consensus algorithm, there is a problem that the Byzantine node is gathered in a single shard after the sharding, which causes the shard failure and the transaction cannot be verified. Therefore, in order to ensure consistency of the data between the shards, a rollback operation is required for partially processed cross-shard transactions, which affects the overall performance of the system. In response to the above problems, a multi-round consensus verification scheme is proposed, which can increase the scale of sharding and improve the TPS of the system on the basis of the lower rollback probability. First, it briefly describes the advantages and disadvantages of existing sharding projects, and analyzes the cross-shard transactions probability and rollback probability. Then, a multi-round consensus verification processing transactions is proposed, and the impact of multiple rounds on the rollback probability of cross-shard transactions is analyzed. Finally, a reasonable upper limit of the number of rounds is proposed. The comparison to experiment with the existing scheme shows that the multi-round verification scheme can effectively ensure the transaction verification rate, reduce the probability of cross-shard transaction rollback, and improve the overall TPS of the system.

Key words: sharding, cross-shard transactions, roll back, practical Byzantine fault tolerance（PBFT）, multi-round verification

摘要： 区块链分片方案中的跨分片交易由多个分片协调处理。在采用实用拜占庭容错（practical Byzantine fault tolerance，PBFT）类共识算法的分片方案中，存在因分片后拜占庭节点在单个分片聚集，导致分片失效无法验证交易的问题。因此，为保证分片间数据的一致性，需要对部分处理的跨分片交易进行回滚操作，这影响了系统的总体性能。针对以上问题，提出了一种多轮共识的验证方案，可以在降低回滚概率的基础上，支持更大分片规模，提升系统的每秒交易数（transaction per second，TPS）。简述了现有分片项目解决方案的优缺点，对跨分片交易的概率和回滚概率进行了分析，提出多轮共识的验证方案，分析了多轮方案对跨片交易回滚概率的影响，得出合理的多轮轮数上限值。通过与现有方案的对比实验表明，多轮验证方案可以有效提升交易验证率，降低跨片交易回滚的概率，提升系统总体的TPS。

关键词: 分片, 跨分片交易, 回滚, 实用拜占庭容错（PBFT）, 多轮验证

BAI Bing, LI Zhihuai, LI Min. Multiple Rounds Validation Scheme to Reduce Rollback Probability of Cross-Shard Transactions[J]. Computer Engineering and Applications, 2022, 58(2): 129-136.

白兵, 李志淮, 李敏. 降低跨分片交易回滚概率的多轮验证方案[J]. 计算机工程与应用, 2022, 58(2): 129-136.

References

[1] NAKAMOTO S.Bitcoin：a peer-to-peer electronic cash system[EB/OL].[2020-06-10].http：//bitcoin.org/bitcoin.pdf.
[2] 张森，叶剑，李国刚.面向冷链物流的区块链技术方案研究与实现[J].计算机工程与应用，2020，56（3）：19-27.
ZHANG S，YE J，LI G G.Research and implementation of blockchain technology scheme for cold chain logistics[J].Computer Engineering and Applications，2020，56（3）：19-27.
[3] 韩璇，袁勇，王飞跃.区块链安全问题：研究现状与展望[J].自动化学报，2019，45（1）：206-225.
HAN X，YUAN Y，WANG F Y.Security problems on blockchain：the state of the art and future trends[J].Acta Automatica Sinica，2019，45（1）：206-225.
[4] 潘晨，刘志强，刘振，等.区块链可扩展性研究：问题与方法[J].计算机研究与发展，2018，55（10）：7-18.
PAN C，LIU Z Q，LIU Z.Research on scalability of blockchain：problems and methods[J].Computer Research and Development，2018，55（10）：7-18.
[5] DANG H，LOGHIN D，CHANG E，et al.Towards scaling blockchain systems via sharding[C]//Proceedings of the 2019 International Conference on Management of Data，June 2019.New York，USA：Association for Computing Machinery，2019：123-140.
[6] LUU L，NARAYANAN V，ZHENG C，et al.A secure sharding protocol for open blockchains[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security，New York，USA，October，2016.Vienna，Austria：ACM Press，2016：17-30.
[7] 高政风，汤舒扬.基于DAG的分布式账本共识机制研究[J].软件学报，2020，31（4）：1124-1142.
GAO Z F，TANG S Y.Research on DAG-based distributed ledger consensus mechanism[J].Journal of Software，2020，31（4）：1124-1142.
[8] 曾帅，袁勇，倪晓春，等.面向比特币的区块链扩容：关键技术，制约因素与衍生问题[J].自动化学报，2019，45（6）：1015-1030.
ZENG S，YUAN Y，NI X C，et al.Scaling blockchain towards bitcoin：key technologies，constraints and related issues[J].Acta Automatica Sinica，2019，45（6）：1015-1030.
[9] JAVARONE M，WRIGHTC.From bitcoin to bitcoin cash：a network analysis[C]//CryBlock’18，2018：77-81.
[10] POON J，BUTERIN V.Plasma：scalable autonomous smart contracts[EB/OL].[2020-06-10].http：//plasma.io/plasma.pdf.
[11] JOSERPH P，THADDEUS D.The bitcoin lighting network：scalable off-chain instant payments[EB/OL].[2020-06-10].https：//lightning.network/lightning-network-paper.pdf.
[12] CASTRO M，LISKOV B.Practical Byzantine fault tolerance[C]//Proceedings of the Third Symposium on Operating Systems Design and Implementation，1999：173-186.
[13] ELEFTHERIOS K， PHILIPP J，NICOLAS G，et al.Enhancing bitcoin security and performance with strong consistency via collective signing[C]//25th USENIX Security Symposium，2016：279-296.
[14] RAFAEL P，ELAINE S.Hybrid consensus：efficient consensus in the permissionless model[C]//The 31st International Symposium on Distributed Computing，2017.
[15] 王夫森，李志淮，田娜.提升分片规模和有效性的多轮PBFT验证方案[J].计算机工程与应用，2020，56（24）：102-108.
WANG F S，LI Z H，TIAN N.Multile round of PBFT verification scheme to improve scale and validity of sharding[J].Computer Engineering and Applications，2020，56（24）：102-108.
[16] KOKORS E，JOVANOVIC P，GASSER L，et al.OmniLedger：a secure，scale-out，decentralized ledger via sharding[C]//2018 IEEE Symposium on Security and Privacy（SP），San Francisco，USA，2018：583-598.
[17] ZAMANI M，MOVNEDI M，RAYKOVA M.RapidChain：scaling blockchain via full sharding[C]//Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security.Toronto，Canada，January，2018.New York，USA：ACM，2018：931-948.
[18] ALBASSAM M，SONNINO A，BANO S，et al.Chainspace：a sharded smart contracts platform[J].arXiv：1708.
03778，2017.
[19] WANG J，WANG H.Monoxide：scale out blockchains with asynchronous consensus zones[C]//16th USENIX Symposium on Networked Systems Design and Implementation，2019：95-112.
[20] MICALI S，RABIN M O，VADHAN S P.Verifiable random functions[C]//Proceedings of the 40th Symposium on Foundations of Computer Science，1999：120-130.