状态分片中交易过载处理的节点竞选方案

秦文慧，李志淮，马洪程

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

区块链本质上是一个去中心化的账本，是一种融合了密码学技术、分布式数据库、计算机网络、共识算法等计算机技术的新型应用模式[1]。2021年6月，工信部发布文件指出：区块链成为建设制造强国和网络强国，发展数字经济，实现国家治理体系和治理能力现代化的重要支撑。在各种政策和环境的激励下，区块链技术研究得到大力支持。然而，目前区块链基础设施无法满足大规模应用的需求，其中限制区块链技术大规模落地的一个重要因素就是区块链的性能问题。

为了使区块链能够更好地适应实际需求，必须增强其可扩展性[2]。区块链扩容[3]是区块链亟待突破的核心技术之一，通过提升可扩展性，从而提升交易吞吐量。目前已有的扩容解决方案包括侧链[4]、分片技术[5]、DAG（directed acyclic graph）技术等[6]。

分片是目前最有效的实现高性能而不降低去中心化程度的区块链扩容方案。分片的思想是“分而治之”，在区块链系统中，分片是指将事务和存储划分为不同的分组，每个分组并行处理交易，从而提升区块链的性能[7]。分片包括网络分片、交易分片、状态分片等，其中状态分片难度最大，状态分片在网络分片和交易分片的基础上，不仅将交易处理并行化，且因每个分片只存储与本分片交易相关的状态信息，能够减少存储冗余。状态分片可以从本质上突破区块链的容量瓶颈[8]。

从理论上看，区块链分片可以有效提高网络的整体性能，但是由于交易根据一定规则随机分配，难以被预先规划，某个分片内极有可能因为交易量过大而发生交易拥堵。目前应用状态分片技术的区块链项目，尚未专门讨论状态分片后可能带来的交易过载的处理问题。此外，区块链中的验证节点，即共识节点的性能实际上存在较大的差异，而在目前主流方案中的验证节点分配时，没有考虑节点交易验证能力的差异。严重时，整个区块链网络的交易吞吐量也会因单个分片交易验证拥堵而受到影响[9-10]。

综上所述，本文针对区块链状态分片交易过载问题进行预研究，提出了一种状态约束下分片内交易过载处理的多轮验证节点竞选方案。方案考虑到状态分片约束下，节点不能随意调度到其他分片，将分片内的交易验证分为多轮，在不同轮次中优化节点竞选策略，进行区块链分片内的交易过载优化处理，当分片内交易过载时，分配性能高的节点进行下一轮的验证。实验表明，本文方案可以有效提升交易过载分片的交易验证率，减少分片交易拥堵的现象，提升区块链分片性能。

1 问题的提出与研究

1.1 分片模型中的过载

1.1.1 分片中的交易分配和分布特点

分片理论上能够提升整个系统层面的性能，但是单个分片仍然可能存在单点过热问题，即在具有分片的区块链系统中，为了避免双花攻击[11]，交易往往按发送地址随机分配到各个分片中，再次分配还是会分配到特定的分片，造成单个分片内部交易量过载，从而使得分片发生拥堵并且产生大量的交易成本。分片技术只是通过并行的方式实现了整体性能提升，但各分片本质上是小型的区块链系统，其性能并没有实质的提升，因此若在单个分片内存在过多交易，分片仍会发生拥堵，并且如果此分片内长期拥堵，所产生的交易成本也会远高于其他分片。分片交易过载如图1所示。

由图1可以看到，区块链网络中的交易进行随机分配后，可能会出现分片2与其他分片未验证交易数差距过大的现象。如果3个分片中节点处理能力恰好与1号分片中的交易数对应，此时2号分片可能会因为未验证交易数过多造成交易过载。

1.1.2 交易过载的概率

假设区块链系统中有ks个分片，未验证交易集合Tx={T1,T2,…,Tn}。由于区块链中的交易是根据交易发送方的地址随机分配到分片中的，可以将交易分配的过程视为n次独立重复的伯努利试验，每个未验证的交易被分配到某一特定分片的概率为1/k。用X表示n重伯努利试验中，新交易被分配到某一特定分片的次数，则X的取值可以是0,1,…,n，随机变量X的离散概率服从二项分布。

假设单个分片中验证节点Nsv数目保持均匀恒定并且每一轮可验证交易的最大数量为Tmax，可以通过式（1）计算出单个分片分配的交易数为Tmax的概率，其中n为区块链系统中的未验证交易数，x为分配到某一分片的未验证交易数。

如果单个分片中的未验证交易数超过该分片中当前轮次节点可验证交易的最大数量Tmax，验证节点在短时间内无法完成验证，该分片就会交易拥堵。可以运用式（2）计算出单个分片中交易数超出Tmax的概率。

根据式（2），设置n=1 000，ks=10，用Python模拟计算出当交易数为1 000，分片个数为10时，单个分片交易过载的概率。表1列举了分片内的交易数Tmax=[120,130,140,150]与其对应发生过载的概率。

表1 单个分片交易数分配过载的概率Table 1 Probability of single sharding transaction number distribution overload

根据表1可以发现，当交易数为1 000，分片个数为10时，单个分片交易数超过120的概率约为0.22，此时该分片的交易数已经比各分片平均分配交易多出20%。以以太坊为例，分析分片交易过载对区块链系统的影响。根据以太坊浏览器提供的相关数据，统计以太坊2021年10月28日至11月9日的每日交易笔数，如图2所示。

图2 中，横坐标表示日期，纵坐标表示相对应的交易量。平均24小时链上交易数约为100万笔。根据以太坊网络中的分片个数为64个，平均分配交易到各个分片，每个分片分到的交易数约为15 600笔。如果其中一个分片中的交易数比平均分配多出20%，则该分片比其他分片多出3 120笔交易。分析可知，随着网络中交易数的增多，各分片所分配交易数之间的差距会越来越大。区块链分片时无法保证各个分片内节点处理能力均衡。随机分配交易具有很大的概率，导致部分分片未验证交易过载。

1.2 相关解决方法与分析

目前的分片方案一般采用随机方式分配节点和交易，然而区块链网络中的节点因设备、网络环境等因素的不同，存在较大的性能差异。随机分配节点会导致各个分片的整体性能差异较大，随机分配交易又可能因性能较差的分片分得较多的交易负载而产生拥堵，导致整个区块链系统交易处理能力下降。目前，区块链分片交易过载的问题尚未在全球公有链中得到有效解决。

研究人员提出了OmniLedger[12]、NEAR[13]和以太坊[14-15]等状态分片协议，利用分片技术将网络中的节点和交易进行划分，各个分片并行处理交易，提高了区块链系统的交易处理能力。OmniLedger分片方案根据随机协议选择验证者分组，利用RandHound协议保证分配过程的安全性。该分片方案实现了状态分片，降低了节点的存储和启动开销，但是并没有考虑节点交易验证能力差异，无法处理分片内交易过载。与以太坊不同，NEAR协议是单条区块链，而各个分片植根于其上。像传统的区块链一样，每个区块都包含所有分片的所有交易，但是此数据并不存在于单个物理区块中。应对过量的交易，该分片方案采用延迟的交易处理方式，如果交易重新分配时仍指向同一个分片，该分片方案无力处理。以太坊市值高达25 400亿元，是规模仅次于比特币的区块链项目。以太坊2.0使用信标链进行节点分配，大大提高了区块链网络的性能，同时也面对着很多新的挑战。以太坊2.0尝试在信标链上部署负载均衡合约，当某个分片中出现交易拥堵时，通过调用合约将负载转移到其他分片。该方案目前还未在项目中实际应用，其稳定性仍需进一步研究。

1.3 无状态验证的局限

针对区块链分片随机分配交易机制产生的难以预知的区块链分片交易过载问题，文献[16]提出了一种基于节点验证能力积分的区块链分片负载的多轮验证方案。此方案根据各分片的剩余负载，将验证能力高的节点再分配到高负载的分片进行后续的验证，减少单个分片交易拥堵的情况。但是此方案没有考虑状态分片约束下，节点不能随意竞选的问题。

状态分片中每个分片只存储所负责分片中的状态，因此在下一次节点重新分配时，新节点加入分片之前必须等待同步完该分片中的状态信息后才可以加入分片并提供算力，否则将无法保证数据的连贯性，从而影响交易验证的有效性。而状态信息的同步需要消耗大量的时间，因此若频繁地在分片之间进行节点的轮换，会极大地增加系统的延迟，从而影响系统的活性。因此，仅考虑无状态验证，节点随意跨分片间调度是不可行的。

根据上述分析可知，在前期较少的关于交易过载处理的分片方案中存在无状态验证的局限。故本文针对以上问题进行分析及预研究，在跨分片节点调度外提出了一种状态约束下交易过载处理的多轮节点竞选方案。

2 分片多轮验证模型的交易过载处理

本文在现有区块链分片基础上，提出了状态分片约束下交易过载处理的多轮节点竞选方案。一轮验证后，通过节点综合积分方法更准确地评价节点，计算剩余的未确认交易数量并判断剩余负载，通过节点竞选策略有效地组织节点进行交易验证，以缩短区块链交易确认时间，使得节点筛选更快收敛，实施均衡化处理，提高区块链交易处理能力。

2.1 分片的多轮验证模型

通过上述分析可以发现，区块链状态分片中，交易通常按照一定的规则被随机分配到各个分片，且再次分配还是会被分配到特定分片，存在单个分片交易过载的问题。此外，区块链系统的交易负载具有滞后性，即无法预先获得各分片的交易负载对此进行处理。目前一些主流的分片项目并没有针对分片的交易过载问题提出切实可行的解决方案。

针对单个分片内拜占庭节点比例过高导致单个分片失效概率增大的问题，多轮PBFT验证（multiple rounds of PBFT verification，MRPV）方案[17]被提出。连续多轮进行交易验证，当各个分片开始对分片内的交易进行验证时，即为第一轮验证，当分片中产生一个区块后，即为一轮结束。本文基于此方案提出状态分片交易过载处理的多轮PBFT验证方案，利用多轮PBFT机制在每轮验证后获取到分片内的交易负载，通过调整分片内轮次间不同性能的验证节点，来处理状态分片内交易过载的问题，提升区块链系统的TPS（transaction per second）。

如图3所示，第t时隙，分片的状态为SS(t)，待验证的交易集合为Tx(t)，分片内共识节点组表示为Vsv(Nsv=||Vsv)。在第t时隙，共识验证节点组Vsv利用当前状态SS(t)对当前交易集合Tx(t)进行第1轮共识验证，记为Vsv(t,1)[SS(t),Tx(t)]。

若交易在第t时隙被验证成功，则将交易打包上链，并更新状态。第t时隙结束后，若Tx(t)中仍存在未经验证的交易，则重新选取共识节点对此批交易，在第t+1时隙进行第2轮的验证，如过程①所示，记为Vsv(t+1,2)[SS(t),Tx(t)]。若仍未验证成功，则继续重新选取共识节点进行第3轮验证，如过程②所示，记为Vsv(t+2,3)[SS(t),Tx(t)]，直至达到轮数上限放弃交易。

多轮方案中不同轮次可能对应多个共识组，分别处理不同的交易。若交易集合Tx(t)在第t时隙被确认，则将交易打包上链，并在第t+1时隙将分片状态更新为SS(t+1)。第t+1时隙又将有新的交易集合Tx(t+1)等待被处理，选取新的共识节点组对此批交易进行第一次验证，记为Vsv(t+1,1)[SS(t+1),Tx(t+1)]。随着轮数增多，每一时隙的交易验证延迟会带来更多的负载。

状态分片交易过载处理的多轮验证方案的具体过程如下：

（1）将节点随机分配到各个分片，再将交易根据映射规则随机分配到各个分片，然后初始化交易处理的轮次。

（2）待同步节点首先进行状态同步，并根据节点状态同步的快慢测评其通信能力。待同步节点完成状态同步后可以进入分片内并获得参与共识验证的资格，通过VRF随机函数选出共识节点。

（3）由分片内的共识节点集合Vsv对分配到该分片的全部交易进行共识验证，超过2/3共识节点达成一致则验证成功，将该组交易打包到区块。通过节点综合积分机制更新共识节点的分值，并进行交易负载的计算，判断是否有未验证交易。若分片内交易过载，则通过节点竞选策略选取通信能力高的节点进行下一轮的验证，更快地处理交易。

（4）若分片未达到共识，则扣除共识节点的分值，通过节点竞选策略分配共识表现较好的验证节点进行下一轮的验证。

（5）若连续T轮过后仍未达成有效共识，则选择放弃该笔交易。通过牺牲交易的可用性，保全系统的总体性能。

需注意，在步骤（3）中，达成共识的分片同样需要重新分配共识节点，一方面，如果分片内交易过载，需分配综合性能强的节点进行验证，提高分片的处理能力。另一方面，如果不进行节点重新分配，分片中的节点一直处于同一分片中，会导致如下两个问题：一是分片中的拜占庭节点会因为一次偶然的分配而一直留在正常工作的分片中，其共识表现分值无法被扣除，拜占庭节点身份无法体现，不利于系统整体的稳定。二是随着验证轮数的增加，同一分片中的节点熟悉彼此后，可能会为谋求更大的利益，互相勾结攻击分片，影响系统的安全性。

多轮验证的流程图如图4所示。

2.2 节点综合积分机制

本文在现有区块链分片的基础上，提出了节点综合积分机制。文献[18]通过节点处理交易能力来进行节点积分，本文考虑到实际网络中的影响因素，根据节点的共识表现和节点的通信能力两个指标来评估节点性能，并且为每个指标都设置一个指标权重占比，然后再根据这些指标数据，计算分数，综合权衡两个指标。在下一轮节点重新分配时，遵循基于节点积分的分配算法，选取综合积分高的节点进入下一轮共识，解决区块链系统分片内剩余负载不均衡的问题，提高系统的交易吞吐量。

2.2.1 节点共识表现评估

节点在共识过程中的表现是降低选中拜占庭节点参与共识的重要指标，同时也是区块链中节点提供资源和服务可靠性的评价因素。通过对区块链网络中节点行为信息的收集、评价、量化、更新，从而达到利用节点的可靠性评估对其行为进行规范和限制的目的。在区块链网络通信中，选择共识表现好的节点参与验证，在一定程度上可以保证区块链网络的可靠性。因此，节点共识表现评价机制须体现多粒度、动态更新的特点，同时符合人类社会信任评价中“信任积累缓慢，信任迅速消减”的特性，即信任的增加是缓慢的，信任的衰减是迅速的。如果只是根据节点每次的共识结果对其积分进行累加，会太过于片面，可能会导致一些恶意节点故意通过节点通信能力来累积分值，从而得到参与验证的机会，这样会对系统的性能造成比较大的负面影响。

基于此，本文引入了基于时间的信任衰减函数以及节点信任积分的动态更新策略，来提升区块链网络的可靠性和安全性。随着时间的推移，节点成功参与两次共识之间相差的时间越长，共识积分的占比会越小。共识积分的衰减函数如式（3）所示：

式（3）中，Ti表示随着时间的推移，节点的共识表现分值的衰减程度；tnew表示节点当前共识发生的时间；tpre表示节点上次共识发生的时间。|tnew-tpre|值越大，Ti就越小。当节点长时间不在线，或者出现网络故障，导致节点参加两次共识时间的间隔比较长，则衰减程度就会相应增大。根据节点的投票信息与最终的共识结果是否一致来判断节点是否成功参与共识。

节点共识分值Ri(x)的具体计算方式如式（4）所示。如果投票信息与最终的共识结果一致，则节点的可靠值是结合时间衰减函数进行累加。若共识成功则加1分。若不一致或者检测到验证节点作恶，则表明此节点为恶意，共识分值减10分。如果节点超时没有进行响应，表明此节点可能是因为网络故障造成超时，但是也有可能节点是恶意不回应，此时的积分不会直接降为初始值，而是将积分值减5分。

式（4）中，x表示节点i参与共识的次数，Ri(x)表示节点i参与x次共识后的积分，Ri(x)的初始值Ri(0)设为0，Ti表示节点i的共识表现随时间的衰减程度。

2.2.2 节点通信能力评估

在区块链真实网络中，区块链节点具有异构性，主要表现在节点的验证能力、存储能力、通信能力的差异[19]。一笔交易信息要快速可靠地传输给网络中的其他节点，需要重点考虑节点通信能力，本文中节点的通信能力评测是在状态同步过程中进行的。本文对节点的通信时间和通信效率进行研究，将节点的硬件性能作为通信影响因子来量化节点的通信能力。

节点由于硬件配置的异构性导致其在区块链通信过程中的传输能力存在差异。文献[2]通过CPU内核数n、CPU频率C、内存容量M、磁盘I/O速率D、网络带宽T等指标来计算一个节点的硬件性能。本文的积分重点在节点对共识的贡献力度，因此主要考虑节点的CPU处理频率、内存大小以及CPU利用率和内存利用率。通信能力Pi的量化公式如下：

其中，Ci代表节点i的CPU处理频率，n表示CPU内核数，Mi表示节点i的内存大小，Uc表示节点的CPU利用率，Um表示节点的内存利用率。

2.2.3 节点综合性能评估

节点的综合性能MergeScore评估计算方式如式（6）所示：

其中，Ri(x)表示节点i的共识表现积分，Pi表示节点的通信能力积分，β是指标的权重参数，可根据具体情况设定合理的值。考虑到没有可靠传输的保障，负载的优化是无意义的。因此要严格杜绝通信能力强，但是共识表现差的节点作为验证节点，可适当调整β的值。

2.3 交易负载计算模型

区块链系统中的交易根据交易发送方的地址随机分配到各个分片，因此无法保证交易数量均匀分配。本文方案引入多轮验证的思想，分片中的节点在每一轮达成共识打包交易出块后，计算本轮分片内剩余交易负载，剩余负载进入下一轮与新交易一起打包处理，根据分片内的剩余负载来选取已有节点在不同轮次之间均衡使用。本文的每一轮待处理的交易负载包括上一轮次分片内的剩余负载和当前轮次的交易负载两部分，由式（7）计算：

其中，shardLi(t)为分片i在第t轮的交易负载值，Counti(T(t-1))为该分片上一轮交易验证后的剩余负载，即未确认交易数，Counti(T(t))表示该分片第t轮新提交的交易数。分片的交易负载与轮次的关系如图5所示。

需注意，不同轮次对应不同的共识组，且每一轮次可能对应多个共识组。第i轮的剩余负载作延后处理，后续轮次的验证一定是对未确认交易的重复验证。

2.4 节点竞选策略

2.4.1 节点状态转移机制

状态分片中活跃节点的角色是动态转变的，本文根据网络中的节点不同的状态，将节点划分为全局候选节点、待同步状态节点、分片内就绪节点、分片内共识节点和局外节点。处于不同状态的节点对应不同的行为。

待同步状态节点由于没有存储当前分片的状态信息，需要先进行状态同步，即同步节点所在分片的账本信息后才有资格参与交易的验证。此外，通过节点状态同步的快慢来测定节点的通信能力。以下三种情况的节点统称为待同步状态节点：

（1）状态分片后被分配到指定分片并等待加入分片进行工作的节点。

（2）后续新加入系统的节点。

（3）部分节点因为网络问题掉线重连，可能会丢失部分状态，同样需要先同步信息后再参与共识流程。

状态同步后的节点会进入分片内，获取参与交易验证的资格，转换为分片内就绪节点。每一轮通过节点竞选策略选出共识节点集合进行交易的验证。

在完成一轮验证并进行积分核算后，共识节点集合按照分值进行排序，并将排名末位的节点淘汰转入全局候选节点队列，进入静默期静默一段时间等待进入待同步状态节点。

全局候选节点队列依据分值按序排列，等待加入分片进行工作，后续可依据轮次通过随机算法选中进入到分片内的待同步节点集合。

分片内的就绪节点需要监督共识节点进行共识验证，若通过欺诈性证明检测出共识节点作恶，例如节点随意篡改转发信息、丢弃信息、破坏网络资源等，则进行举报，将作恶节点转入分片外的局外节点集合，剥夺其进入分片内参与验证的资格，并对提交了欺诈性证明的就绪节点进行奖励。节点状态转换流程如图6所示。

2.4.2 可验证的随机分配算法

VRF（verifiable random function）是可验证的随机函数，是结合了哈希函数与非对称加密的应用算法。通过随机输入一个数值，得到一个任意的输出，且该输出的结果，可以通过零知识证明来验证其正确性。

本文基于以下三种情况采用可验证的随机分配算法VRF进行节点的分配：

（1）状态分片交易依据相应规则被分配到分片中，通过VRF算法随机分配节点到各个分片。

（2）每一轮次通过VRF算法从就绪节点中重新选取验证节点，以此来保证节点分配时较高的随机性、不可预测性和可验证性。

（3）全局待分配同步节点需要通过VRF算法，依据当前轮次随机选中进入分片内待同步状态节点集合，以此保证其在不同时刻进入不同的分片。

由于VRF的不可预测性、可验证和无偏倚的特性优势，节点的分配无法预测，可以高效、安全且随机地分配节点，保证了分片的验证有效性和系统安全性。

2.4.3 状态分片约束下的节点竞选策略

针对第1章的分析，本文提出了一种适应于状态分片约束下的多轮PBFT验证的节点竞选方案。利用分片内节点能力的差异，每一轮验证结束后通过更新共识节点组，对交易过载的分片进行快速调整处理，同时可以降低分片内的拜占庭节点比例，有效提高验证效率。

方案进行节点竞选的具体步骤如下：

（1）每轮交易验证完成后，根据节点综合积分机制进行节点积分核算。

（2）打包交易成功出块后，计算本轮剩余交易负载，下一轮次再结合新分配的交易根据交易负载计算模型计算出本轮的交易负载。

（3）节点竞选首先借助VRF随机算法，从分片内的节点Ns中随机选出一半节点，以此保证一定的随机性和公平性。再选取前端分值最高的Nsv个共识节点进入下一轮验证。

（4）每轮验证结束后，根据节点的共识表现更新节点分值，共识节点组按照分值进行排序，分值最低的节点进行末位淘汰，作为本轮转出当前分片的节点，按照最新分值转入全局候选节点序列的相应位置。

（5）若检测出节点作恶，则将节点转入局外节点，使其失去加入分片内参与验证工作的资格。

节点竞选的详细流程如图7所示。

3 实验设计与结果分析

3.1 实验基本设置

为验证本文提出的状态分片内的交易过载多轮节点竞选方案的可用性和有效性，对本方案进行分片规模与有效性分析和交易验证轮数的研究，并将本方案与未进行交易过载处理的MRPV方案进行对比实验，观察两种方案在交易验证率、系统吞吐量方面的性能。实验设置总节点数为1 000，每100个节点为1个分片，设置共识节点数为10。节点的共识表现初始分值为100分，节点通信能力初始分值为60～100分。

本文设计的状态分片内的交易过载多轮节点竞选方案在实验室环境下进行，需要设置以下假设条件：

（1）分片期间总节点数目保持均匀恒定。

（2）本实验所设置的交易均不属于跨分片交易。

（3）本实验的节点属性可变，即本轮诚实的节点，下一轮可变成拜占庭节点。

3.2 分片规模及有效性分析

在本文的多轮PBFT验证方案中，由于每一轮共识时间较短，且状态分片中的待同步节点还需同步每一轮共识后产生的区块，增加了分片内的通信量，本节将分析共识节点的数目，在降低分片内通信开销的同时，保证每个分片内的验证有效性。

3.2.1 通信量与分片内共识节点数目的关系分析

在真实区块链网络中，考虑到每个节点的实际网络的带宽可能并不一致，因此网络中的通信量会有一定的限制。由于PBFT共识机制中验证节点增多，分片内的通信复杂度也会显著增加。本文将选取尽量少的验证节点进行共识，降低通信开销成本。为了满足系统的活性，节点的网络带宽必须足以让整个网络能同时进行上一区块的广播验证，客户端发布待验证交易、主节点共识以及普通节点投票几项工作。本文将满足网络主节点所需的最低网络带宽抽象为式（8）：

其中，B为网络带宽的最小值，Nsv为分片内共识节点的数目，HashSize为转发哈希的大小（固定32 Byte），a为普通节点投票产生主节点所产生的通信量。BlockSize为打包的一个区块的大小，其计算公式如下所示：

式（9）中，HeaderSize为区块头的大小，txSize为一条交易信息的大小。

式（10）中，TxCount为一个区块打包的交易数量，TPS为每秒可打包的交易数量，TD为上一区块进入主节点共识的时刻与本轮进入主节点共识阶段的时间差。

式（11）中，CP为一致性协议产生的通信量，p为prepare阶段节点广播的确认消息的大小，c为commit阶段各节点广播的确认消息的大小。

通过式（11）可以看出，网络中最小带宽取决于分片内共识节点的数量Nsv。若仅仅将Nsv设置过小，虽然通信量较低，但是这将导致严重的中心化以及安全性问题，这与本文分片规模设置的初衷不符。分片内共识节点的数量Nsv如果设置过大，将会使得网络中的通信量过大，从而造成网络拥堵。其中节点数量带来的通信量占网络带宽比如图8所示。

本文为了控制整个过程中所产生的通信量占用百分比为网络带宽的30%到40%，通过仿真计算得出共识节点应该控制在10到19个的范围内。

3.2.2 单个分片内不同拜占庭节点比例的概率分析

设置系统总节点数N为1 000，单个分片内节点数Ns为100，系统内拜占庭节点比例为1/3。X1表示单个分片内节点数Ns中拜占庭节点的数量，X1服从超几何分布，记为X1～H(Ns,N×Pn,N)，系统中总的拜占庭节点比例Pn为1/3。系统进行节点分配时，可看作从系统N个节点中为每个分片选取Ns个节点，则在分片内拜占庭节点数量为K1时，分片内拜占庭节点比例Ps在不同点的取值概率P1如式（12）所示：

根据公式运用Python模拟计算出单个分片内不同拜占庭节点比例的概率如图9所示。

由图9可知，当系统内总拜占庭节点比例Pn为1/3时，单个分片内拜占庭节点比例Ps在[0，0.2]范围内的概率之和为1.50E-3；在[0.2，0.45]范围内的概率为0.99，其中，当Ps等于0.33时的概率最大；在[0.45，1]范围内的概率之和为7.02E-3。可以发现单个分片拜占庭节点比例在[0.2，0.45]范围内的概率较大。经验算，P1的概率总和近似为1。

3.2.3 不同共识节点数目导致共识失效的概率分析

假设分片内共识节点数量为Nsv，分片内共识节点组中拜占庭节点比例为Psv,X2表示选取的Nsv个共识节点中拜占庭节点的数量，则X2服从超几何分布，X2～H(Nsv,Ns×Ps,Ns)。Psv在不同共识节点数取值的概率P2如式（13）所示：

单个分片内节点数Ns中拜占庭节点的数量X1和共识组中拜占庭节点的数量X2所有情况下分片失效的概率取值之和Psum如式（14）所示。经验算，Psum的总和近似为1。当共识节点组中拜占庭节点比例超过1/3时，共识节点组会无法达成共识，导致共识失效。当分片内共识节点数量Nsv不同时，共识节点中拜占庭节点所占的比例Psv也不同，从而导致节点共识失效的概率不同。共识失效的概率Pfailure如式（15）所示。

根据式（15）运用Python进行模拟计算，当分片内拜占庭节点比例Ps在[0.2，0.45]范围内，共识节点的数目在[10，19]范围内，不同共识节点数目导致共识失效的概率如图10所示。

根据图10可知，共识失效的概率随着分片内拜占庭节点比例Ps的增大而增大。而共识节点数量和共识失效概率存在振荡的情况。

选取分片内拜占庭节点比例Ps出现概率最高的值0.33，共识节点的数目在{10，19}范围内，不同共识节点数目导致共识失效的概率如图11所示。

根据图11可得知，随着共识节点数量的增加，共识失效的概率呈现总体上升的趋势，并产生周期长度为3的振荡，因此Nsv的节点数量可按3i+C来选定范围。其中，C是常数0、1、2，i取正整数。

综上分析，本文将分片内共识节点数Nsv取值定为[10，13，16]，在降低通信开销的同时，保证了分片内PBFT共识的验证有效性。

3.3 交易验证轮数的研究

3.3.1 多轮轮数与验证成功概率的关系

本方案中设置一笔交易被验证失败的次数高于某一限定值后就放弃该笔交易。对轮数上限的设置关系到系统整体的性能，若轮数上限设置过低，会导致大量交易被放弃，系统的交易验证率降低。若轮数上限设置过高，又会影响到交易的处理延迟，导致过多交易拥堵，对系统的负荷带来压力。下面将详细分析对于验证轮数的设置。

根据以上分析，当分片内拜占庭节点比例较高时，共识失效概率依旧不可忽视，威胁系统的安全性。因此本文通过多轮验证以有限地牺牲交易的可用性，保全系统的性能。多轮验证中，一笔交易进行x轮验证直到被验证成功才被打包到区块上，用X表示多轮的验证次数，假设交易在第x轮被成功验证，则前x-1轮次均验证失败，那么X近似服从几何分布，记为X～GE(p)，其中p为验证成功的概率，pfailure表示交易验证失败的概率，则p=1-pfailure。交易验证成功的概率P如式（16）所示：

根据公式模拟出分片内不同共识节点数下，轮数x对交易验证成功率P的影响，如图12所示。

根据图12可以看出，随着轮数的加大，一笔交易在k轮内被验证成功的概率也在增大。而随着共识节点数目的增加，交易成功率会随之降低，需要更多的轮数来保证其可用性。

此外，根据公式模拟出分片内不同拜占庭节点比例，轮数x对交易验证成功率P的影响，如图13所示。

根据图13可知，当分片内拜占庭节点比例Ps不变时，随着交易验证轮数的增加，交易共识成功率会逐渐增大。当分片内拜占庭节点比例低于0.3时，大多数交易在1到4轮有很大的概率共识成功。当分片内拜占庭节点比例为0.3时，经过4轮验证，交易验证成功的概率就可以达到99%。当分片内拜占庭节点比例为出现概率最高的值0.33时，在交易验证轮数为8时，交易验证成功的概率达到了99%。当交易轮数达到14时，即使在分片内拜占庭节点比例为0.45的情况下，交易验证成功率也达到了99%。

综上所述，多轮验证方案相较于传统的单轮验证方法，交易验证成功率大幅提高，证明多轮方法达到了以牺牲交易的可用性提升系统性能的目的。

3.3.2 轮数实验

实验环境设置分片内节点数Ns为100，每个节点完成同步后随机对应60～100的通信分值，并给其设置100分的共识表现初始值。取分片内拜占庭节点比例Ps出现概率最高的值0.33，共投放10万笔交易。根据第3.2节分析，共识节点数目Nsv取值范围[10，13，16]。每轮根据共识节点的表现更新其共识表现分值。通过实验计算本文方案中每轮的交易成功率，如表2所示。

表2每轮的共识成功率Table 2 Success rate of each round

由表2可见，随着共识节点数的增加，交易验证率减少。当Nsv=10时，第4轮交易验证率就已接近99%。随着轮数的加大，交易在k轮内被验证成功的概率也在增大。当轮数为6时，对一笔交易验证成功的概率达到了99%，表明系统能以较低的处理延迟确保更高的验证成功率且更快收敛。

此外，在保证最终共识超时的概率低于10-7时，计算出分片中不同的共识节点数目Nsv下，轮数T与共识超时概率的关系，如表3所示。

表3共识超时Table 3 Consensus timeout

由表3可见，当分片失效概率小于10-7时，此时的多轮轮数Tmax=8。本文方案将多轮轮数上限定为8轮，即对同一笔交易进行8轮共识验证仍没得到统一验证结果，就放弃这笔交易。

3.4 交易验证率对比实验

区块链系统的交易验证率指的是在一段时间内被成功验证交易数目占总交易数目的比重，在相同时间内，系统内节点验证的交易数目越多，则该系统的交易验证率越高，其性能越高。本实验目的是验证本文方案可以有效提高系统的交易验证率。

本实验的研究目标是证明本文方案能够有效地提升系统的交易验证率。设定总节点数目为1 000，分片数目为10。初始时将节点随机分配到各分片，统计各分片的交易验证情况，分别计算本文方案和MRPV分片方案以及OmniLedger方案中每轮验证完成后各分片的交易验证率。交易验证率对比结果如图14所示。

实验结果如图14，随着时隙的增加，三种方案的交易验证率均不断提升。本文方案与MRPV方案由于采用了多轮验证，通过连续多轮次的交易验证，对之前未确认的交易重新验证，保证了交易的最终确认，最终的交易验证率均趋近100%。而OmniLedger方案由于设定一笔交易在一次验证失败后将直接丢弃该笔交易，交易验证率仅可达到90%。通过对比分析本文方案和MRPV方案两种多轮模拟系统，可以看出本文方案在第8轮交易验证率就已达到99.99%，而MRPV方案的交易验证成功率在第15轮才达到99.99%。

3.5 交易吞吐量对比实验

交易吞吐量代表系统单位时间内处理事务或交易的能力，是衡量系统性能的重要指标，一般用TPS表示系统吞吐量，计算公式如式（17）所示：

其中，Δt表示一笔交易从发起到写入区块的时间间隔，Transactions表示在Δt时间内写入区块的交易总数。为了验证本文方案可以提高算法的吞吐量，在实验室环境中，根据公式计算本文方案、MRPV分片方案以及OmniLedger三种方案在不同共识节点规模下的TPS。

由图15可以看出，本文方案的平均TPS优于没有进行交易过载处理的MRPV和OmniLedger方案，且在任意拜占庭节点比例下，这种优势都比较明显。主要原因有三点：一是本文方案根据剩余负载在轮次间竞选性能高的节点进行交易过载处理；二是减少单个分片内参与验证的节点数量，提高了共识达成的速度；三是本文方案能够通过节点综合积分机制，将拜占庭节点淘汰，使得拜占庭节点参与交易验证的机会降低，提高系统的稳定性以及交易处理的效率。综上所述，本文方案体现出了更高的平均TPS，能够满足更大规模的系统实现。

4 总结

本文针对区块链状态分片内的交易过载问题，提出了一种状态分片约束下的多轮节点竞选验证方案。本文方案将分片内的交易验证分为多轮，在每轮验证完成后根据节点的通信能力和节点共识表现进行综合积分核算，并计算分片内的交易负载，确认分片的交易过载情况，进而在下一轮验证中增强分片的处理能力；通过利用节点竞选策略对分片内的节点在不同轮次之间均衡使用，实现状态分片内交易过载处理，在牺牲延迟来保证安全性的前提下，提高系统的性能。

通过实验验证，本文方案提出的状态分片多轮节点任务竞选方案可以有效处理分片内交易过载，提升分片内的交易验证率，提升整体TPS。但是本文方案存在一定局限性，由于考虑到状态分片的约束，节点不能在分片间随意调度。目前实现了分片内部的已有节点在不同轮次间均衡使用，对状态分片约束下分片间的负载均衡和信标链上负载均衡的实现还在探索中，可在后续的研究中改进和优化。

此外，本文基于大连海事大学区块链实验室团队成员陈静、段培培、高冬雪、厚香莹、王冬雪、马洪程等同学的共同基础研究。