提升分片规模和有效性的多轮PBFT验证方案

2020-12-26王夫森李志淮

计算机工程与应用 2020年24期

王夫森，李志淮，田娜

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

1 引言

区块链技术作为比特币[1]的底层协议，具有去中心化、难篡改、允许运行在非许可环境下的特点。区块链本质是一个去中心化的账本，有效解决了拜占庭将军问题[2]，实现了在点对点网络中互不信任的节点通过遵循预设的机制达成数据的最终一致性，从而降低了现实世界的信任成本。

但是，现阶段的区块链技术仍是不成熟的，面临着扩容困境[3-4]。现有的解决方案主要归纳为Layer1 层扩容和Layer2层扩容方案，Layer1扩容方案主要包括分片技术[5]、DAG[6]结构、代理共识协议、增大区块[7]等。Layer2扩容方案主要包括侧链[8]、状态通道[9-10]等。

区块链分片的概念最早是在文献[5]中提出，本质是一种将计算和存储分散到对等网络的分区方式，每个节点只维护与其分片相关的信息。分片方案通过切割网络中的节点和交易，以实现每秒处理数千笔交易的区块链网络。

POW 类共识算法属于概率性算法，采用最长链竞争原则[11]，不适合分片内；POS 类共识算法的逻辑是从整体上假定少数利益不能违背多数利益，也不适合被分割的分片内。目前分片内多采用聚合签名优化后的PBFT[12-13]共识算法，是一种被证明的P2P网络中实现数据最终一致性的确定型共识算法，它允许含有传递恶意消息或任意延迟消息的拜占庭节点，但其比例小于总节点数的1/3。

区块链分片方案尽管提高了区块链吞吐量，但在采用PBFT共识算法的分片方案中，即使总体拜占庭节点比例不超过三分之一，单个分片内拜占庭节点比例也可能会超过三分之一，使得这些分片的验证有效性和可用性受到威胁。

针对分片后单个分片验证有效性降低的问题，在文献[5]中，ELASTICO采用增加单个分片中的节点数目来降低单个分片失效的概率，通过将单个分片中的节点数目增加至600 个来保证单个分片失效的概率低于百万分之一。在文献[14-16]中，采用包括RandHound、VSS、VRF、Randao节点随机分配方案提高单个分片的验证有效性[14-16]。在节点随机分配方案中，节点不具有自主选择分片的可能性，将节点地址、IP地址、公钥等信息作为输入进行签名与Hash 计算，将得到的哈希结果依据映射关系分配到既定分片中。在文献[17]中，通过将矿工节点运行在TEE环境中以及通过SGX产生的随机数将节点分配到既定分片[17]，降低节点作恶的概率。在文献[18]中，提出连弩挖矿的方案[18]，每个矿工节点可以连接多个共识组，通过提高矿工收益的经济模型来降低矿工节点作恶的机率。

由上述文献可知，目前国内外关于分片方案的研究很多，各从不同方面对单个分片的验证有效性进行了分析。但是，目前关于分片验证有效性的研究侧重点集中在对分片验证有效性的定性分析，缺乏对分片失效概率与拜占庭节点比例、分片内节点数目之间量化关系的分析，以及对分片验证失效后的进一步处理。本文量化了影响分片验证有效性的各变量之间的关系，计算出单个分片失效的概率以及全部分片都不失效的概率。本文提出的多轮验证方案，通过连续多轮PBFT验证，确保分片内的交易得到更高概率的确认。通过实验数据可以表明，多轮验证方案在提升分片规模的同时，确保单个分片的验证有效性，实现分片方案下区块链整体TPS（Transaction Per Second）的显著提高。

2 问题描述与分析

2.1 问题描述

分片方案力图通过并行处理提高区块链TPS，但也可能因为分片内验证有效性明显降低，达不到预期吞吐量，产生分片规模与分片内验证有效性的矛盾。

针对分片中采用PBFT 共识的方案，假设在未分片之前，总节点数目为n，拜占庭节点数为b，拜占庭节点数所占比例为f，则f=b n(0 ≤f＜1/3)。现假定将n个节点均匀分配到k个分片中，假设每个分片内的节点数是L，则L=n k；每个分片中的拜占庭节点比例为，其中i(1 ≤i≤k)表示分片编号。将节点分配到k个分片中后，自然存在拜占庭节点分配不均，可能出现≥1/3 的问题，如图1所示。

图1 分片可能导致拜占庭节点在片内聚集

图1 描述了经过分片后存在一定概率使得片内拜占庭节点比例超过1/3。在图1中，经过节点分配后1号分片和3号分片中拜占庭节点数超过1/3，导致分片内无法达成共识。

2.2 节将对单个分片失效的概率P与f、L的关系进行量化，2.3节中将对所有分片都正常工作的概率Pr与f、L、k之间的关系进行量化。

2.2 单个分片失效概率的分析

假设在未进行分片之前，区块链中的拜占庭节点比例为f(0 ≤f＜1/3)，L表示一个分片中节点的数量。对于L中的每一个节点在进行共识的时候都会依据自己的身份进行验证，拜占庭或者非拜占庭身份。

令X=，其中Xi表示第i个节点表现出了拜占庭身份，X表示当前片中拜占庭节点总个数。由于Xi只能表现出拜占庭节点身份或者非拜占庭节点身份，且这两个身份之间相互独立，所以X服从Binomial(L,X,f)的二项分布，当X≥L/3时，分片失效。如公式（1）所示：

2.2.1 分片内节点数与分片验证有效性的关系

根据公式（1），设置f=[0.1,0.2,0.3]，改变L的值，用Python模拟研究L对P的影响情况。如表1所示。

表1 分片内节点数L 对单分片失效概率P 的影响

根据表1，在拜占庭节点比例f不变时，单个分片失效的概率随着分片中节点数目的增大而减小；当f=0.3，L=60 时，单个分片失效的概率超过0.3；即使L=600，单个分片失效的概率在f=0.3 时仍大于0.04，这仍是一个不可接受的值，并且分片内节点数目过多限制了分片规模。当分片内节点数目L不变时，在f=0.3的较高拜占庭比例下，单个分片的验证有效性迅速降低。

2.2.2 拜占庭节点比例与单个分片验证有效性的关系

根据公式（1），设定L=600 的情况下，研究不同数值的拜占庭节点比例f对于单个分片失效概率P的影响。如表2所示。

表2 拜占庭节点比例f 对单分片失效概率P 的影响

根据表2，当L=600，f≤0.25 时，单个分片失效的概率很小。随着f不断接近1/3，单分片失效的概率出现指数类型增长，这将使得该分片几乎失去了验证有效性，难以达成验证共识。单个分片的验证有效性成为了影响整个区块链TPS的瓶颈。

2.3 所有分片都正常工作的概率的分析

在进行分片的区块链中，区块链的整体TPS受限于单个分片的验证有效性。在分片后，若想提升区块链的并行验证能力，需要保证每个分片内的验证有效性。

下面计算分析分片之后所有分片都能正常工作的概率。假设：

区块链中总节点数目为n；拜占庭节点比例为f(0 ≤f＜1/3)；每个分片中的节点数目为L；分片规模为k；分片后第i个分片中的拜占庭节点比例为fi′，节点进入到任意分片概率相同。若想保证所有分片不失效，需要保证每个分片内的拜占庭节点的比例fi′＜1/3，为了追求结果的准确性，采用穷举遍历的方法，列举出所有满足分片都不失效的情况，如公式（2）所示。其中对于公式（2）有两个限定条件，分别为公式（3）、（4）。

在公式（3）中，i1表示第1 个分片内可能的拜占庭节点数目；i2表示第2 个分片内可能的拜占庭节点数目；ij表示第j(1 ≤j≤k)个分片内可能的拜占庭节点数目；所有满足公式（3）的序列均被放入到集合B中。

对于公式（4），借鉴贪心算法思想，若保证每个分片都能正常运行，每个分片中保持分片验证有效性的同时尽可能多地容纳拜占庭节点。假设前k-1 个分片中在保证不失效的情况下尽可能多地存储了拜占庭节点数，则第k个分片中可能的拜占庭节点数目分为两种情况：一种是拜占庭节点数目已经都分配到前k-1 个分片中，那么第k个分片中的拜占庭节点数目为0。另一种情况是前面k-1 个分片尽管尽可能多地分配了拜占庭节点，但仍有剩余，则剩下的拜占庭节点全部分配到第k个分片中。故第k个分片中的拜占庭节点的取值为0之间的较大值。

由于Pr的值受分片个数k、拜占庭比例f、分片内节点数L的影响，采用控制变量的方法，分别研究f、L、k对Pr的影响。

2.3.1 分片内节点数与所有分片都不失效的关系

根据上述2.2.1小节的分析，总结出分片内节点数L会对分片的验证有效性造成影响。探究L与Pr的关系，需要控制分片个数和拜占庭节点比例不变。本文主要研究高拜占庭节点比例下分片的失效概率，故选取f=0.3；分片个数k=4 是保证分片规模有效的合理有效值，固定这两个值可准确地研究有效分片规模与高拜占庭比例下分片内节点数L对所有分片都不失效的概率值Pr影响。图2 是基于公式（2）～（4）模拟k=4，f=0.3，分片中节点数目L对所有分片都不失效的概率影响图。

图2 L 对于Pr 的影响

图2显示，增加分片内的节点数在一定程度上能提高分片不失效的概率，但所有分片不失效的概率依然很低，且随着不断增加分片内节点数，Pr增大的幅度也在减小，仅增大分片中的节点数目在f=0.3 的较高拜占庭比例下仍无法解决分片失效率高的问题。

2.3.2 拜占庭比例与所有分片都不失效的关系

根据2.2.2小节分析，得出拜占庭节点比例对于分片验证有效性的影响很大，参考文献[14]，单个分片内节点数适中为宜，故单个分片内的节点数设定为L=180，根据公式（2）～（4），计算在n=720,L=180,k=4 时，不同的拜占庭节点比例f与所有分片都正常工作的概率Pr的关系，如图3所示。

图3 f 对Pr 的影响

依据图3，当每个分片中的节点数目固定时，所有分片正常工作的概率随着拜占庭节点比例的增大而减小。当拜占庭节点比例f=0.25 时，所有分片正常工作的概率为0.034；当拜占庭节点比例f=0.3 时，所有分片正常工作的概率为0.015。较高拜占庭节点比例对分片验证有效性影响较大。

2.3.3 分片规模与所有分片都不失效的关系

根据公式，计算在L=180，f=0.3 时，不同的分片规模k对所有分片都不失效的概率的影响。结果如图4所示。

图4 k 对Pr 的影响

在区块链分片中，增加分片规模会使得系统的吞吐量线性增加，但分片规模的增加会使得分片的验证有效性降低。当k=3 时，所有分片正常工作的概率为0.022 3，而当分片规模k=10 时，所有分片全部正常工作的概率低于0.005，此时分片已基本失去了验证有效性。

3 多轮共识方案设计

通过第2 章量化影响分片验证有效性的各变量之间的关系，数据表明当拜占庭节点比例f较高时，扩大分片规模k，分片内验证有效性P降低。当拜占庭节点比例f越接近于1/3，单个分片失效的概率P越高，所有分片都不失效的概率Pr也就越小，单个分片的验证有效性将成为提高区块链TPS的关键，扩大分片规模则又是解决当前区块链扩容瓶颈的重要方法。在这样一个难两全的环境下，本文提出多轮PBFT共识验证的方案，通过扩大分片规模，并降低分片验证失效率，力图使区块链整体TPS显著提高。

多轮验证方案的主要思想为当一笔交易根据映射规则被分配到一个既定的分片后，由此分片中的所有节点对分片中的交易进行共识验证。如果共识验证成功，则将交易打包进区块。如果交易验证超时未得到有效共识，可依据节点的随机分配算法重新分配一组新的节点到该分片，对此交易进行新一轮共识验证。

在拜占庭节点比例较高的情况下，如果连续经过T次都没有达成共识，将选择放弃该笔交易，牺牲交易的可用性，同时要求放弃一笔交易的概率ε＜10-7。

对于轮数T的上限，在3.1节中给出。对于节点随机分配算法，在3.2节中描述。

3.1 多轮轮数的选择

3.1.1 拜占庭节点合谋的概率

在拜占庭节点比例比较高的情况下，可能在某个分片内拜占庭节点占据大多数，且相互串通，进行合谋攻击。此时，尽管主节点收集到足够多的消息，但是这些确认消息是拜占庭节点之间串通合谋发送给主节点的，使得最终达成错误的共识。

若想在某个分片内进行合谋攻击，则要求此分片中至少含有(2×L)/3+1 个拜占庭节点且进行合谋，但这是比较困难的。假设当该分片中的拜占庭节点数目大于(2×L)/3，则串通在一起进行合谋。X表示分配到该分片中的节点总数，L表示分片内节点数。X符合Binomial(L,X,f)的二项分布。如公式（5）所示：

根据公式（5）运用python模拟计算出在不同的拜占庭比例f和单个分片内不同的节点数目L下，该分片中的拜占庭节点发生合谋的概率，见表3。

表3 单个分片中拜占庭节点间合谋的概率

根据表3 发现，即使当f=0.333，若保证单个分片中的节点数目超过60 个，该分片中的拜占庭节点达成合谋的概率β也会低于4×10-8。

3.1.2 拜占庭节点比例和分片内节点数对轮数的影响

在拜占庭节点比例低的情况下，共识可以在较少的轮数t(1 ≤t＜T)内结束。在4.1节实验中会得出在不同拜占庭比例下达成一轮共识的最少次数、最多次数和平均次数。最大共识次数T的取值范围需要根据拜占庭节点不合作的概率和合谋的概率确定。T的下限是当拜占庭节点合谋的概率小于10-7时的取值，T的上限是拜占庭节点不合作的概率低于10-7时的取值。保证最终共识超时的概率低于10-7时，计算出在不同的拜占庭比例f和分片中不同的节点数目L下，轮数T的取值范围，如表4 所示。表5 分析了在L=60，不同轮数下，不同拜占庭节点比例与共识超时概率的关系。

表4 轮数T 在不同f 和L 下的取值范围

表5 共识超时概率

通过表4 发现，随着分片内节点数的增多，对轮数影响不大。表5表明f=0.3 时，需要更多的轮数来保证可用性。

3.2 节点随机分配算法

当出现共识过程超时的情况时，需要对分片中的节点进行新一轮的分配，节点随机分配算法需要尽可能满足具有比较高的随机性和不可预测的特点。基于此，选用VRF（Verifiable Random Function）作为节点随机分配算法的随机函数。VRF 随机函数具有很好的随机性和不可预测的特性。

在区块链中，每个节点都具有节点地址和一对公私钥。在需要进行重新分配节点时，节点i将输入m通过数字签名和哈希函数映射为固定长度的输出H[SIGi(m)]，即m→H[SIGi(m)]，其中m可以是节点的IP 地址或者是节点公钥。对于任何输入m，不同的调用节点i生成的数字签名SIGi(m)是确定且唯一的；而对于不同输入，哈希函数H的输出具有随机性，符合随机性的特点。

为保证不可预测性，需要为VRF 随机函数提供一个随机的且不断变化的种子。在本文的VRF 函数中，引入一个随机的、不断更新的种子参数G(h)，G(h)=H(Bh-1,Sk)，其中h为第h个区块，Bh-1为上一区块的哈希值。要求每个参与节点都需要和网络中的两个邻居节点互换一个数字，Sk为每个参与的节点从邻居节点获得的数字集合。可以看出，G(h)在每一轮都会发生变化，且与交易本身无关。当G(h-1)是随机的，则G(h)也是随机的。因此恶意节点无法通过改变交易集去影响下一个种子的生成。符合所要求的不可预测性。

4 实验验证与结果分析

为验证本文方法确实能够降低单个分片失效的概率，且多轮对交易的延迟确认不会使得总体TPS 降低。实验以ELASTICO为基础进行，增加了多轮方案和节点的随机分配方法，选用Linux 作为实验平台，以Go 语言作为开发语言，以Docker和Goland作为开发工具，在每台服务器的不同端口模拟不同的节点，实验数据用MATLAB进行绘制。

4.1 实验设置

4.1.1 实验环境设定

本文所设计的多轮方案，在使用之前需要设定下列条件：

（1）节点可以动态加入和退出，假设在分片期间总节点数目保持均匀恒定。

（2）区块链中节点的位置和网络情况会影响达成共识的效率，实验在局域网内进行，P2P 网络中各个节点之间通信良好，延迟在可控范围内。

（3）在每一轮共识中，节点是否诚实是可变的，即非拜占庭节点有可能在下一轮中变为拜占庭节点。

4.1.2 实验参数设置与实验流程

本文设计两个对比实验，随着拜占庭比例的变化，观察对比首个区块链分片方案ELASTICO、采用节点随机分配算法并取得较好效果的Omniledger方案、多轮方案的单个分片的失效概率和平均TPS 的表现情况。在实验时，为了更能体现单一变量对结果的影响，需要对一些实验参数进行设定，如下：

（1）总节点数目n=600；

（2）每个分片中的节点数L=60；

（3）拜占庭比例的取值为f=[0.1，0.15，0.2，0.25，0.28，0.3]；

（4）轮数T的值取为在f=0.3,L=60,ε＜10-7条件下的最多轮数。如图5所示。

图5 共识次数与拜占庭节点比例的关系

在图5中，分别统计了在多轮方案中上述条件下轮数的最多、最少和平均情况。当0 ≤f＜0.15 时，最多轮数、最少轮数、平均轮数均可在一轮内结束；当0.15 ≤f＜0.25 时，最多轮数的值在增大，但平均轮数和最少轮数仍可在一轮内结束。当0.25 ≤f≤0.3 时，最多轮数出现指数增长的趋势，平均轮数稳定在两轮，最少轮数仍可在一轮内结束。

实验样本：实验以局域网内10 台服务器的不同端口号模拟600个节点；在3.1.1小节的计算中，保证L＞60时合谋的概率即女巫攻击成功的概率β＜4×10-8，故设定每个分片中的节点数为60。

实验中采用对收到消息不进行转发，来模拟拜占庭节点的行为：即拜占庭节点虽然收到了消息，但是不向主节点以及其他共识节点进行反馈。基本实验流程如图6所示。

图6 多轮方案处理一笔交易流程

4.2 实验结果与分析

单个分片失效的概率受分片规模和区块链中拜占庭节点比例的影响。实验1 模拟以n=600,L=60,T=7 为条件，随着f的不断变化，观察ELASTICO 方案、Omniledger 方案、多轮方案与单个分片验证有效性的关系。实验结果分别如图7所示。

图7 不同拜占庭比例下两种方案中单个分片失效概率

在实验1中，当f＜0.15 时，三种方案在单个分片失效的概率上都很低；当0.15 ≤f＜0.25 时，ELASTICO 方案出现了失效概率增大的情况，Omniledger 方案和多轮方案表现仍然良好；当0.25 ≤f≤0.3 时，ELASTICO方案的单分片失效的概率值出现了指数型增长，Omniledger方案的单分片失效概率值出现了小幅增长，这是由于在Omniledger 中节点随机分配算法尽管在一定程度上可降低分片失效的概率，但是无法根本解决较高拜占庭比例下拜占庭节点聚集的问题；多轮中单个分片失效的概率值尽管也出现了增长，但在f=0.3 情况下值依然较小，这是因为在某个分片中连续多轮拜占庭节点发生累次聚集的概率极小，因此更能保证单个分片的验证有效性。

本文的目的是保证分片验证有效性的同时，显著提高分片规模，确保整体区块链TPS 提升，故实验2 模拟以n=600,L=60,T=7 为条件，随着f的不断变化，调整拜占庭节点数目，观察ELASTICO 方案、Omniledger方案和多轮方案TPS的表现情况。结果如图8所示。

图8 不同拜占庭节点比例下两种方案TPS表现情况

在实验2中，随着拜占庭节点比例的不断增大，三种方案的TPS值均在降低。当0.1 ≤f≤0.15 时，ELASTICO方案和Omniledger方案的平均TPS比多轮方案稍高；当0.15 ＜f≤0.2 时，三种方案TPS 值差距很小；当0.2 ＜f≤0.3，ELASTICO 的TPS 急剧下降，Omniledger 方案的TPS 也在迅速下降，但整体TPS 较ELASTICO 稍优，多轮方案尽管也出现了下降，但下降幅度稍缓，且整体TPS均优于前两种方案。

在多轮PBFT 共识验证算法中，在吞吐量方面，T轮共识验证虽然使得单个分片的交易确认得到延迟，但保证了单个分片具有更高的验证有效性；同时，因分片的个数已增至M(M≫k)，平均共识验证轮数为t，总体区块链TPS提高M/t倍。在保证单个分片中的节点数目不低于60 时，可使得单个分片中的拜占庭节点达成合谋攻击的概率低至4×10-8。两个实验综合表明：减少分片内节点数、扩大分片规模、增加轮数验证，比分片规模较小、分片内节点数较多的单轮验证方案，总体验证有效性更好、区块链TPS更高。