降低跨分片交易回滚概率的多轮验证方案

白 兵，李志淮，李 敏

大连海事大学 信息科学技术学院，辽宁 大连 116002

区块链技术在中本聪的论文[1]中首次提出。在技术层面，区块链是一种使用了P2P网络、分布式存储、密码学等计算机技术，具有去中心化、去信任化、难篡改特点的分布式数字账本。区块链因其技术特点，其应用已经延伸到银行、物流、金融等多个领域，对它们的数据存储和共享产生重大的影响[2-3]。同时，在2019年10月24日的中央政治局第十八次集体学习会议上，习近平总书记强调，要大力发展区块链关键技术，加快推动区块链技术和产业创新发展。

区块链的技术特点使其有着广阔的应用前景，但也同时面临可扩展性不足的瓶颈，存在扩容需求[4-5]。现有的扩容技术主要包括分片方案[6]、DAG[7]、扩块[8-9]、侧链技术[10]、状态通道[11]等。其中分片方案是目前扩容方案中最具可行性的方案，受到广大学者和社区人员的关注和重视。区块链分片的核心思想是将区块链网络节点划分为若干个集合，每个集合独立运行共识协议，对交易进行共识验证，并且每个集合可以并行地处理不同的交易集合甚至只存储部分网络状态，从而达到提高交易吞吐量的效果。

分片技术虽然可以提升区块链系统的性能，但同时也带来了新的挑战。分片后网络中必然存在跨分片交易，而跨分片交易的正确处理对系统的性能至关重要。在UTXO（unspent transaction outputs，未花费的交易输出）模型下，处理跨分片交易时，客户端将跨分片交易发送到涉及的输入分片中独立地验证处理，当全部输入分片成功验证跨分片交易后，会提交给输出分片进行验证处理。出现任一个输入分片验证交易失败或超时后，为保证区块链网络数据的一致性和完整性，需要对部分处理的跨分片交易进行回滚操作。

跨分片交易回滚的原因如下：（1）交易是无效的，部分输入分片验证无误且提交，而某输入分片验证交易失效，拒绝这笔交易，跨分片交易必须回滚以此释放其他分片已锁定的资源，保证后续交易对该对象的正常使用；（2）对于大多数分片项目采用的PBFT[12-14]类共识算法的分片方案中，存在总拜占庭节点比例不超过1/3，分片后单个分片拜占庭节点比例大于1/3的情况，使分片验证有效性受到威胁[15]，分配到某分片的跨分片交易迟迟无法达成共识，致使跨分片交易进行回滚。

针对因分片失效导致跨分片交易回滚的问题，文献[16]通过采用Rand Hound节点随机分配算法降低分片内拜占庭节点聚集的概率，提高分片的验证有效性，可以在一定程度上保证跨分片交易的正确处理。文献[17]通过将节点的通讯方式设为同步，以此来增加单个分片对拜占庭节点的容忍度，提高分片的验证有效性，从而减少跨分片交易回滚的发生，但同步的通讯方式应用具有局限性。文献[18]通过智能合约进行分片，使用了假设分片内安全的“SMART’s PBFT”协议来保证跨分片交易的处理。文献[19]提出了连弩挖矿的激励方案，在提高矿工收益的经济模型下，确保分片的有效性，可以一定程度上减少跨分片交易回滚的发生。

根据上述文献可知，现有的分片方案中缺少“跨分片交易中因某个分片失效导致分片内交易无法验证，进而造成跨分片交易回滚”的概率分析，以及对这种原因导致的跨分片交易回滚的进一步处理方案。故本文针对以上问题进行分析，提出了一种多轮共识验证的改进方案，较传统的单轮次验证其贡献如下：（1）该方案可以及时地为失效分片更换验证节点，让失效分片中的交易可以在下一轮验证中再次处理，降低有效的跨分片交易回滚的概率，减少了回滚的交易重新提交产生更大的延迟现象的发生；（2）该方案通过连续的多轮验证，可以在降低跨分片交易回滚的概率的基础上，增大分片规模，进一步提升系统的TPS；（3）通过实验表明，多轮验证方案的表现更优。

1 问题描述与分析

1.1 问题描述

UTXO模型[1]由于具有良好的并发性，被应用于很多区块链网络中。在UTXO模型中，交易可以具有多个输入和输出。交易验证时，验证者需要验证每笔交易的输入尚未花费，并且确保在这笔交易完成后该交易的所有输入都已不可再花费。在基于UTXO模型的分片区块链系统中，交易的多个输入输出可能涉及到多个节点地址，根据分片协议，节点和交易按规则划分到不同的分片，这就导致一些交易需要在多个分片进行验证，也就是跨分片交易。

在跨分片交易中，一般设定管理输入对象所在的分片称为输入分片（input shard，IS），管理输出对象所在分片称为输出分片（output shard，OS）。由于一笔跨分片交易涉及多个分片，为保证分片间的全局一致性需要多个分片之间协调处理。跨分片交易处理时，客户端将跨分片交易发送到涉及的输入分片中，每个分片独立地对该分片内的交易进行共识验证处理，只有所有的输入分片验证成功后才会提交跨分片交易到一个或多个输出分片，并在输出分片中进行再次验证。当任何一个输入分片验证交易失败或超出时间限制时，为保证区块链系统的一致性，需要对部分处理的跨分片交易进行回滚操作。跨分片交易的处理流程如图1所示。

图1 跨分片交易的处理Fig.1 Processing of cross-shard transactions

采用PBFT类共识算法的分片方案可以保证数据的最终一致性，但在这类分片方案中，分片中存在由于拜占庭节点分配不均，导致分片验证有效性遭到破坏的问题，从而影响某个分片内交易的处理。一旦某个分片失效则导致涉及该分片内的跨分片交易无法得到验证，那么跨分片交易涉及的其他分片提交的跨分片事务就需要开始回滚操作，而回滚对于性能的负面影响是巨大的。设总节点个数为N，总体拜占庭比例为f<1/3，设将N个节点随机均匀地分到k个分片中，分片内节点数为L，分片后可能会存在单个分片拜占庭比例fi>1/3(1≤i≤k)致分片失效，如图2所示。

图2 拜占庭节点分配不均致分片失效Fig.2 Uneven distribution of Byzantine nodes making shards invalid

对于有效的跨分片交易，因某个分片内拜占庭节点比例f>1/3，而无法对片内交易达成共识验证，导致的跨分片交易回滚严重影响系统的性能，并且后续用户重新发送这笔交易到网络中谋求再次验证，将会产生更大的交易延迟。因此本文针对分片内拜占庭节过多导致分片失效，造成的跨分片交易回滚问题进行分析处理。

1.2 跨分片交易概率分析

在区块链UTXO模型的分片系统，交易的多个输入可能涉及到多个节点地址，节点会按照分片协议中的随机分配算法，随机分配到各个分片中。设分片规模为k，交易的输入数量为m，根据分片的随机分配算法，每个输入节点都等概率地随机分配到k个分片中。则在UTXO模型下的分片系统中，具有m个输入的交易，为跨分片交易的概率P(cross-shard)如公式（1）所示：

根据公式（1），模拟研究交易的输入个数m对跨分片交易概率P()cross-shard的影响情况。如表1所示。

表1 对跨分片交易概率P（cross-shard）的影响Table 1 Impact of m on probability P（cross-shard）

由表1可知，一笔多个输入的交易为跨分片交易的概率随着分片规模k和输入个数m的增大而增大。当分片规模k为16时，具有多个输入的交易为跨分片交易的概率已超过93%；若k、m继续增大，跨分片交易的概率将无限接近于1。综上所述，在分片系统中，处理具有多个输入的交易时，出现跨分片交易的概率很大。故保证涉及多个输入的跨分片交易的正确处理、减小跨分片交易发生回滚的概率对区块链系统的性能至关重要。

1.3 跨分片交易回滚的概率

设分片规模为k，在UTXO模型中，一笔交易包含的输入个数m是有可能大于分片个数k的，那么含有m个输入的交易Tx的跨片分布w，取值在1到min(m,k)个分片。为专注于跨片交易回滚的分析比较，一笔含有m个输入的交易Tx在分片系统中，跨分片交易回滚的概率归约为与跨片分布w和分片的验证有效性相关。设分片规模为k，单个分片验证失效的概率用Ps表示，m个输入分布在w个分片的交易Tx，它的回滚概率用P(rollback)表示，如公式（2）所示：

在文献[16]中，Omniledger方案对分片的有效性进行了具体的分析。其中，Xi表示第i个节点表现出了拜占庭属性，X表示单个分片中拜占庭节点的数量，L表示为分片内节点数，f为总体拜占庭节点比例。X符合Binomial(L,f,X)的二项分布，X≥1/3时，分片失效。分片失效概率Ps如公式（3）所示：

故P(rollback)可以展开如公式（4）所示：

在许多分片项目中设定总体拜占庭比例f=0.25[6，16-18]，被认为是一个合理的取值。故设定f=0.25时，计算不同w对跨分片交易回滚概率的影响，如表2所示。

表2 输入分片个数w对回滚概率P（rollback）的影响Table 2 Influence of w on P（rollback）

根据表2可知，在L不变时，跨分片交易回滚的概率随着w的增大而增大；当跨分片交易的输入分片个数w不变时，回滚的概率随着分片内节点个数L的增大而减小。但即使在L=600时，跨分片交易回滚的概率依旧无法忽视。

由表2可知，通过增大L可以使同样一笔跨分片交易回滚概率减小，但分片技术的目的是通过扩大分片规模提升吞吐量，分片内节点数过多不利于分片规模的扩大，从而达不到分片的最终目的。故本文提出了多轮验证的共识算法，可以在降低跨分片交易回滚的概率的基础上，扩大分片规模，提升系统的总体性能。

2 多轮共识处理跨片交易验证方案

通过以上的分析可以看出，分片后不仅会存在跨分片交易，且跨分片交易在网络的所有交易中，占了很大的比例，因此跨片交易的正确处理对系统性能是至关重要的。处理跨分片交易时，即使仅存在一个输入分片未完成验证交易，都需要对其他已处理的跨分片交易进行回滚。通过1.3节的模拟计算，对分片后拜占庭节点分布不均而使某些分片失效，进而导致的跨分片交易回滚的概率进行分析，发现跨分片交易的回滚概率很高，不可忽视。跨分片交易回滚将严重影响系统性能，为了保证系统的性能，应尽量减小跨分片交易的回滚概率。故提出多轮共识的验证方案，通过多轮验证，可以提升跨分片交易的验证率，从而保障系统总体的TPS。

2.1 多轮验证方案处理交易的流程

多轮共识的验证方案验证跨分片交易中心思想为当跨分片交易被发送到多个输入分片，由各分片独立地进行验证处理，验证成功则打包出块。若出现交易在分片内因拜占节点过多使交易验证超时，则重新分配节点到该分片，再次对该笔交易进行共识验证，使其在有限的轮数内可以验证成功，尽量避免跨分片交易因单个输入分片失效而无法完成有效验证。这减少了跨分片交易回滚情况的发生，也可避免重新发送已回滚的交易产生更大的延迟。

交易验证的具体过程为：（1）将交易根据映射规则分配到既定分片，并初始化交易的轮次；（2）由分片内的全部节点对分配到该分片全部交易进行共识验证，验证成功则将该组交易打包交易到区块；（3）若分片验证超时后还未得到有效共识，则通过随机分配算法重新分配一组节点到失效分片中（此时其他分片正常运行），对上一轮验证超时的那组交易进行新一轮共识验证；（4）若连续T轮过后仍未达成有效共识，则选择放弃该笔交易。通过有限牺牲交易的可用性，保全系统的总体性能；本文设定放弃一笔交易的概率为β<10-8。多轮共识验证的具体流程如图3所示。

2.2 多轮验证方案轮数选择

2.2.1拜占庭合谋攻击的概率

即使总体拜占庭节点比例小于1/3，节点在随机分配到各个分片后，也会存在分片内拜占庭节点占据大多数且相互串通的情况。串通作恶的节点目的是进行合谋攻击，让分片内达成一致且错误的共识。若在分片内达成合谋，联合作恶拜占庭节点在分片中占比需要大于2/3，但这具有较大的复杂性。假设只要分片内拜占庭节点大于(2L)/3+1，拜占庭节点就会互相串通达成合谋攻击。在文献[6]中，提出了Elastico方案并对分片的合谋概率进行了分析。其中令，Xi表示第i个节点表现出了拜占庭属性，X表示单个分片中拜占庭节点数量，其中L为分片内节点数，f表示拜占庭节点总数所占比例。X符合Binomial(L,f,X)的二项分布，分片内合谋攻击发生的概率如公式（5）所示：

根据公式（5）模拟计算了不同L以及不同f下的合谋概率，如表3所示。

表3 节点数L及拜占庭比例f对合谋概率P的影响Table 3 Impact of L and f on probability P

根据表3可知，单个分片内节点数量越多时，分片发生合谋攻击的概率越低。可以看出当f=0.333时，只要分片内节点数L超过60时，合谋攻击概率低于10-8，合谋概率足够低，近似认定分片内节点达成的决定为集体诚实，不考虑合谋攻击的发生。

2.2.2 多轮轮数对回滚概率的影响

根据表3，在L不小于60时，合谋攻击概率足够小，可以假定分片内节点达成的决定为集体诚实。故表4分析了在分片节点数L=60时，跨分片交易在不同的轮数T和不同的输入分片个数w下的回滚概率。

表4 轮数T对跨分片交易回滚概率P（rollback）的影响Table 4 Impact of rounds T on P（rollback）

由表4可以看出，使用多轮共识的验证方案与传统的单轮次验证方案（第一轮的回滚的概率）相比，跨分片交易的回滚的概率大幅度降低。随着轮数T的增大，跨分片交易回滚的概率将越来越低，逐渐降低至一个相当微小的数值。虽然跨分片交易回滚的概率随着w的增大而增大，但使用多轮的验证方案仅当T=2,w=16时，比传统单轮验证方案w=2时的跨分片交易回滚概率还小很多。由此证明，使用了多轮共识的验证方案处理跨分片交易对减少跨分片交易回滚的概率效果显著，也利于实现更大规模的分片。

输入分片个数w=4，据统计是跨分片交易中占比最大的数值。表5分析了在输入分片个数w=4，在分片内节点数L不断增长的情况下，使用了多轮验证方案和未使用多轮验证方案，跨分片交易回滚概率的差别。

由表5看出，随着分片内节点数增加，两种方案跨分片交易回滚的概率都大幅降低，但使用多轮的验证方案在节点数较小时依然比单轮次多节点的跨分片交易回滚概率低许多；且分片内节点数减小，分片规模增大，此时分片规模已增加至M(M>>k)；而达到与分片内节点较大时相同的回滚概率，所需的轮数T(T<

表5 轮数T对跨分片交易回滚概率P（rollback）的影响Table 5 Impact of rounds T on P（rollback）

2.2.3 多轮轮数的上限

为限定延迟上限，防止对一笔交易无限循环共识影响系统的总体性能，对轮数的上限进行设定。轮数T的上限即共识的最多轮数，取值为跨分片交易回滚概率小于10-8时的轮数。根据表4，当分片节点数和拜占庭比例固定时，w的增大对使交易的回滚概率小于10-8的轮数几乎没有影响。故表6分析计算了在输入分片个数w=4时（可以粗略代表不同的输入分片个数w），在不同的分片内节点个数L和拜占庭节点比例f下，跨分片交易回滚的概率小于10-8时的轮数上限Tmax。

表6 轮数上限Tmax在不同L和f下的取值Table 6 Value of upper limit of Tmax under different L and f

当一笔交易连续经过Tmax轮共识验证后，仍无法对同一笔交易达成共识，则放弃该笔交易，保全系统的总体性能。

2.3 节点随机分配算法

当分片拜占庭节点过多致分片失效验证超时时，需通过节点随机分配算法重新为失效分片重新分配一组节点，该算法需保证节点分配时较高的随机性和不可预测性的特点，VRF（verifiable random function，可验证随机函数）[20]具有上述特点，因此本方案选用VRF函数作为节点随机分配算法的随机函数。

VRF包含3个函数：VRFG、VRFF、VRFV。

（1）VRFG：公私钥生成函数，根据椭圆曲线函数随机生成一对非对称加密的密钥，即一对公私钥(Pk,Sk)。

（2）VRFF：随机数和证明生成函数，根据输入（Sk和一个输入x），输出两个字符串，随机数value=F1(Sk,x)和零知识证明函数proof=F2(Sk,x)，其中对于任何输入x，不同的调用节点生成的value值确定且唯一。

（3）VRFV：验证函数，调用节点根据广播的输入x和零知识证明proof，结合生成随机数的公钥Pk，对随机数value进行验证，验证通过则表明随机数有效，反之则无效。

在需要重新分配节点时，根据验证有效的且唯一的随机数value，通过哈希函数将value映射为固定长度的输出，让验证节点根据结果进入相应的分片中。

VRF中的输入x为生成随机数的种子参数，为函数的不可预测性提供了保障。x需具有公开、随机且不断更新的特点。据此，对VRF输入x进行设置，如公式（6）所示：

其中，h为第h个区块，Bh-1为当前区块高度的上一个区块的哈希值，{Nk}为每个参与节点与网络中的相邻节点互换一个数字所获得的数字集合，可以得出x每一轮都将做出改变，具有很好的不可预测性。

3 实验设置及结果分析

现有的采用PBFT类共识跨分片方案，都存在分片的验证有效性对跨分片交易的回滚产生影响的现象。为验证本文方案确实可以降低跨分片交易回滚的概率，且多轮验证牺牲的延迟不会降低系统总体的交易吞吐量TPS，分别选用分片方案中效果较好的方案，以文献[12]提出的支持跨分片交易且分片内采用了PBFT类共识算法（即ByzCoinX）的Omniledger分片方案为基础，增加了多轮共识的验证方案，与Omniledger分片方案进行对比实验，对比两种方案的交易验证率、吞吐量，在使用多轮验证后的差异。

3.1 实验环境及参数设置

本实验以实验室局域网搭建的P2P测试网络作为实验所需的网络环境，通过实验室10台服务器构建10个分片，用不同服务器的不同端口号模拟创建不同的共识节点，以普通PC机模拟网络中发起交易请求的客户端，其中具体硬件环境和软件环境如下。

（1）硬件环境

局域网内8台服务器：CPU i5四核，RAM 16 GB，Disk 500 GB；另2台服务器：CPU i5八核，RAM 16 GB，Disk 1 TB。

（2）软件环境

操作系统：Linux，开发环境：Goland。

在2.2.1小节的计算中，当分片内节点数L超过60时，合谋攻击的概率低于3.2×10-8，故实验中设定L为60。对有着较优跨分片交易处理能力的Omniledger方案和使用多轮验证的方案进行实验对比，观察它们在交易验证率、吞吐量的差异，实验数据用MATLAB进行绘制。在本文的设计方案中，实验前需要对一些参数条件进行设定，如下：

（1）节点的属性是可变的，即在本轮诚实的节点，下一轮可变为拜占庭节点。

（2）设定总节点数目N=600,分片内节点数L=60,节点可以动态加入或退出，分片期间节点数量保持不变。

3.2 实验设计和结果分析

3.2.1 交易验证率测试

设定总节点个数N=600，分片内节点数L=60的区块链网络下，验证在两种方案下的交易验证率，向两种方案分别投放相同50 000笔交易，设定每笔交易的输入分片数量w分别为1、2、4、6、8几种情况，观察两种方案的跨分片交易验证率变化。如图4所示。

图4 交易验证率Fig.4 Transaction verification rate

根据图4可以看出，两种方案的交易的验证率随着交易涉及的输入分片数量的增加而减少。使用了多轮共识的验证的方案，交易的验证率明显比单轮的Omniledger方案的验证率高，这是因为使用多轮的验证方案可以通过有限的延迟避免因分片失效导致的跨分片交易回滚的问题，可以让某个失效分片的跨分片交易在下一轮继续验证，不用回滚交易并等待重新提交。而Omniledger方案若出现单个分片失效，则分片内交易无法在有限的时间得到及时的验证处理，跨分片交易需要进行回滚，降低了交易验证率。本实验可以表明，多轮共识的验证方案可以增加交易验证率即降低交易回滚概率。

3.2.2 交易吞吐量测试

交易吞吐量含义为系统服务器在单位时间内处理事务的数量，一般表示为TPS（transaction per second，每秒的交易数），如公式（7）所示：

公式（7）中Δt表示为交易发送到网络后直到交易上链的时间间隔，SumTransactionΔt表示在该时间间隔中打包进区块上链的交易总数。设定总节点个数N=600，分片内节点数L=60的区块链网络下，验证在两种方案下的交易吞吐量，在系统分别运行5，10，30，60，120，300 min对交易处理情况进行统计，计算该时间段的平均TPS。观察两种方案随着时间的变化，TPS的变化情况，根据公式（7）计算平均TPS，如图5所示。

图5 两种方案的TPS表现情况Fig.5 TPS performance of two solutions

在实验2可以看出，采用了多轮共识的验证方案的TPS略高于原始单轮的Omniledger方案。系统在运行时，拜占庭节点会联合作恶，影响单个分片的交易验证有效性，加入多轮的方案可以快速恢复，重新分配节点在下一轮继续对交易谋求验证，故TPS表现略优。而单轮验证交易的Omniledger方案，失效分片无法在短时内快速恢复，跨分片交易发生了回滚，影响了跨分片交易的有效验证，所以平均TPS较低。多轮共识的验证方案在系统运行过程中，对失效的分片重新分配节点，会产生短暂的延迟，可能会略微降低交易的吞吐量，但增大了分片规模的同时也能提高交易验证率，使总体性能还是略高于未使用多轮的方案，达到了提升系统交易吞吐量的效果。

两实验综合表明，减小分片内节点数，增大分片规模的多轮共识的验证方案，较分片内节点数较多，分片数量较小的单轮次验证方案相比，有效地降低了跨分片交易回滚的概率，提升了交易的验证率，提升了系统总体的TPS。

4 总结

针对采用PBFT类共识算法的分片方案，因分片后拜占庭节点分配不均致分片失效所导致跨分片交易回滚的问题，提出了一种对交易进行多轮共识验证的方案。选取分片方案中综合效果最好，应用范围最为广泛的Omniledger方案进行模拟对比实验，通过对交易验证率、交易吞吐量的实验结果进行分析，比较两种方案的区别。实验表明，采用了多轮验证的分片方案可以在支持更大分片规模的同时，提高交易的验证率，降低跨分片交易的回滚概率和重新提交的概率。这保证了数据一致性的同时，并提升了分片系统总体的TPS。

分片技术是解决扩容难题的方案中最具前景的方案，而跨分片交易的有效处理是保证分片系统性能的重要前提。因此，本文对许多区块链分片项目降低跨片交易的回滚概率的研究都具有一定的参考价值。本方案还有需要改进之处，进一步考虑分片间负载均衡的问题，动态调整分片间性能差异，避免出现单个分片单点过热问题，继续增强系统的性能。