基于PBFT 算法的分片技术的研究∗

王旭东 符精晶 王 赟

（1.江苏大学计算机科学与通信工程学院 镇江 212013）（2.沙洲职业工学院电子信息工程系 张家港 215600）

1 引言

比特币［1］作为有史以来最成功的加密货币［2］，是一种突破和颠覆性的创新，其底层的区块链技术在分布式共识领域备受技术人员和研究者的关注。区块链（blockchain）是一种由对等网络以分散的方式保存且无法篡改［3］的分布式账本，其最初的目的是为了实现像比特币这样的数字资产而设计的，由于区块链技术拥有的巨大的潜力为现有业务能力的突破提供了新的可能性，故区块链技术在能源贸易，农业［4］，物联网（IoT）［5］等领域被广泛应用。

在区块链系统中当众多节点试图将一个区块添加到主链中时，就需要一种达成一致性协议算法来确定哪个区块才能被添加到主链中，这个算法被称为共识算法，共识算法具有非常重要的意义，它决定了要添加的数据的正确性、试图添加该区块的节点的可信度以及确保了区块链系统中分散的节点之间的一致性，高效的共识算法可实现更高的精度、更高的安全性、更好的性能和扩展性等，常见的共识算法有工作量证明（PoW）［1］，权益证明（PoS）［6］和实用拜占庭容错（PBFT）［7］等。

目前区块链的发展还处于最初阶段，面临着很多问题［8］，其中扩展性［9］问题亟待解决，分片技术是迄今为止被认为最能够解决区块链系统扩展性的最实用的解决方案，它通过将网络划分为不同的分片能够使系统的处理、存储和计算可以并行进行，从而减少通信、数据存储和计算等资源开销，同时保持去中心化和安全性，国内外许多专家针对分片提出了诸多解决方案，下面将进行分别的介绍。

Elastico［10］是一种无许可的分片协议，在Elastico 中节点首先需要解决一个用于确定共识委员会PoW 谜题，确定共识委员会后，该委员会负责对分片的共识结果作出最终决定，在Elastico 中每达成一轮共识，委员会就会重组一次，这种频繁的操作会降低交易执行的效率；OmniLedger［11］是在Elastico的基础上提出的一种分片协议，OmniLedger数据结构块采用了DAG，并使用了结合RndHound 和Algorand 的公共随机协议来进行分片，但Omniledger的缺点是共识过程中牵扯到跨分片交易时通信开销过大；RapidChain［12］是一种基于PBF 算法分片的公共区块链协议，RapidChain 通过减少每笔交易的数据交换量，并使用快速的跨分片验证技术，使交易不需要大范围传播，但是RapidChain 是采用PBF算法达成共识，依然没能解决通信开销大的问题；Monoxide［13］是一个横向扩展的区块链，它提出了异步共识区，线性扩展了区块链系统，但依然没能解决通信开销的问题；Zilliqa［14］是以Pow 为共识算法的区块链分片技术，Zilliqa 通过处理不同分片中的交易来改进吞吐量，但是Zilliqa中的节点需要存储整个区块链网络中的数据，阻碍了系统的扩展；Harmony 是一个具有多个分片链结构的方案，它可以同时处理交易和存储数据，但该分片协议可扩展性较差，还有很大的研究空间。

2 准备知识

2.1 实用拜占庭容错算法

PBFT 是一种经过改进的BFT 算法，经过改进，PBFT在异步环境下比BFT的响应时间降低了一个数量级，并能够容忍异步系统中故障节点引起的一致性问题。与PoW 相比，PBFT 的工作原理中没有计算任务，因此，它将共识的复杂性降低到多项式水平，并且显著降低了能耗。

图1 PBFT算法的共识过程

在PBFT的每个视图中，当主节点收到请求时，它会根据一个三阶段的协议向前移动：预准备、准备和提交。在预准备阶段，当主节点收到请求序列时，主节点按顺序将请求序列发送给其他副本节点，副本节点在收到请求序列后，检查其有效性，并将其添加到其本地日志中，并向其副本节点发送一条消息，以显示它已经收到了提议并识别了它。然后，副本节点进入准备阶段，副本节点成功收集2f+1反馈消息（f表示故障节点数量）时，将启动提交阶段。最后，主节点收集到2f+1 条提交消息后，就可以确保提案已经由足够的副本节点完成记录，可以执行反馈操作，并向客户端发送回复。

为了确保主节点不出现故障，PBFT 设计了一种称为视图更换的协议，如果备份节点发现主节点有恶意行为或停止工作，那么它会独立地宣布要将主节点更改为下一个节点的提议，如果2f+1副本发现主节点的异常，将确认更改视图，由下一个主节点接管。

2.2 聚合签名

聚合签名［15］是一种用于消息身份验证和数据完整性验证的安全技术，通过将一组数字签名组合成一个单一的数字签名，可用作大量数据的完整性证明。聚合签名通过把多个签名进行聚合，节省了通信和存储空间，在聚合签名验证过程中只有当整个签名集都有效时，聚合签名的验证才会输出肯定的结果，如果在集合中有一个错误的签名，则表示所涉及数据的完整性无效。下面对聚合签名做简单验证，对于椭圆曲线上的两个点X，Y 和x，y 以及原点G：

聚合签名有诸多优点，对于验证者来讲，聚合签名可以提升交易的验证速度并节省了通信和存储空间，且无法通过聚合签名推导出参与方的公钥和签名的信息，可用于提高链上数据的隐私性。

3 分片失效概率分析

本章通过对节点数对分片失效概率的分析、分片节点数对分片均不失效的分析来验证导致分片有效性降低的原因。

3.1 节点数对分片失效概率的分析

根据式（4），设置初始参数值f=[0.1,0.2,0.3]，通过改变M 的值模拟研究M 对P的影响情况，如表1所示。

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

根据表1，在f 不变时，随着分片中节点数目的增多，分片失效的概率显著降低，在M不变时，随着f 增大分片失效概率越高，对于整个区块链系统而言，单个分片失效概率大于0.03已经是一个较高的数值了。

3.2 分片节点数对分片均不失效的分析

假设拜占庭节点比例为f(0 ≤f≤1/3) ，每个分片中节点数为M，分片个数为k，若想保证所有分片不失效，需要保证每个分片内的拜占庭节点的比例f<1/3，为了追求结果的准确性，采用穷举遍历的方法，如式（5）所示，式（6）和式（7）是式（5）的两个限定条件。

在探究M 与Pr 的关系时，为了研究高拜占庭节点比例下分片的失效概率，选取f=0.3，分片个数k=4，固定这两个值可准确地研究有效分片规模与高拜占庭比例下，分片内节点数M对所有分片都不失效的概率值Pr 影响，图2 是基于式（5），M 对P 的影响图。

图2 M对P的影响

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

4 分片内共识方案实现

为了解决以上问题，本文通过动态权值分配方法优化一致性hash 算法，解决节点分配的不均衡性，在此基础上实现基于PBFT 共识算法利用聚合签名技术改进动态实用拜占庭算法（DPBFT）。

4.1 节点随机性分配

在对节点进行随机划分时，采用一致性哈希算法［16］进行划分，但是在系统中每一个节点都存在差异，故本文通过动态权值分配的方法对一致性hash算法进行优化以支持动态权重，首先对权值进行计算，步骤如下：

1）节点负载

假设有n 个节点，分片数目为m，对于每个节点i，CPU 利用率是内核模式和空闲模式下CPU（t）时间之和的比值，采用以下公式计算：

节 点 闲 置 内 存 为METfree（t），节 点 总 内 存 为METtotal（t），主机内存利用率（MEM（t））为

网络利用率（NET（t））是节点在时间间隔t 内接收和发送的字节之和与网络带宽NETband（t）的比值，当一个节点加入集群时，可以使用以下公式计算网络利用率：

通过上面的计算，我们使用以下公式计算系统中节点i的负载Load：

其中λ1=0.3，λ2=0.3，λ3=0.4。

2）节点诚信值

共识完成率反映了节点在区块链中总体的完成程度，其可通过共识完成率γ表示，如式（12）计算：

式（12）中，s 为节点成功完成的共识次数，a 为调节常数，n为节点参与共识次数。

交易影响率用于表示交易对节点的影响程度，交易影响率可用交易影响函数f（x）计算，如式（13）：

节点交互程度是指节点在区块链系统中的参与共识的程度，节点交互程度用交互影响函数表示，交互影响函数可采用式（14）计算：

其中，η∊( ]0.5,1 用来控制活跃度比重，a为次数调节因子，n为共识次数。

则节点信用可采用式（15）计算：

其中Cinit为节点信任值初值，E 为行为评价影响因子。

3）节点完成速率可用式（16）计算：

其中，V0表示原始数值，Vmin和Vmax分别为节点完成速率的最大和最小值。

那么节点s的当前权重Ws为

经过多次实验验证，当ω1=0.3，ω2=0.3，ω3=0.4时最为合适。

经过上述对分片权重的计算，我们使用一致性哈希算法来获取系统中所有节点的动态权值Ws，并将节点的动态权重值作为哈希值，映射到哈希空间中，然后利用一致性哈希算法来确保节点与哈希空间动态权值之间的对应关系，并用哈希表进行记录，最后通过跳跃查找算法对节点的所有权重进行索引查找然后随机分配，跳跃查找算法如下所示：

4.2 PBFT共识算法改进

选择生成元定义为P∈G1，Q∈G2，定义双线性映射为e：G1×G1→G2，散列函数为H0、H1、H2、HDV。

1）利用当下的视图计算Pv=vP，得到系统参数Params=｛G1，G2，e，q，P，Q，Pv，H0，H1，H2，HDV｝。

2）用户ui选择随机值xi∈Zq*计算Pi=xiP，Qi=H1（IDi||Pi），Di=vQi生成用户的私钥Si=（Di，xi）。

3）用户ui执行以下过程：ri∈Zq，计算Ri=riP，hi=H0（IDi||mi||Pi||Ri），T=H2（Pv）。

4）若要验证u对m的签名σi=（Vi，Ri）的有效性，计算hi=H0（IDi||mi||Pi||Ri），Qi=H1（IDi||Pi），T=H2（Pv），并验证下列等式是否成立：

为了说明上述论述是正确的，下面给出了单个签名验证过程和聚合签名验证过程的正确性的证明过程。

u 对m 的签名σi=（Vi，Rn）证明单个签名验证过程是正确的过程如下：

对上述问题进行正确性验证之后，改进的共识算法DPBFT的共识过程如下。

1）令H：{0,1}*→G1是一个哈希函数，T/B 是一个交易。 发送者使用私钥sk 计算哈希值h=H((T/B)||v)，计算的签名为σ=hsk，节点附上发送者签名的数据向全网广播；

2）聚合签名者通过给定的公钥pk，交易T/B，签名σ=hsk，计算哈希函数值h=H((T/B)||v)，验证为真，则接受，反之放弃。聚合签名者通过聚合签名算法得到的聚合集表示为U={u1,u2,…,un}，收集到的签名为σ，消息集为T/B={(T/B)1,(T/B)2,…,(T/B)n}，则聚合签名为

3）主节点在经过时间t 后，发送σi>给副本节点；

4）副本节点i在收到消息后，检查其有效性，并添加到本地日志中，并发送σi>给其他副本节点，以显示已经收到了提议；

5 实验测试结果与分析

本文将分别从系统容错性、交易吞吐量，交易延迟三个方面对改进后的DPBFT 与Omniledger 两个方案进行对比，实验平台为Hyperledger Fabric，实验中通过对节点收到消息后延迟处理与发送模拟拜占庭节点的行为。

5.1 系统容错性测试

在系统容错性实验中，主要统计Omniledger和DPBFT 两种方案在不同的拜占庭节点数目下的出块时间，在实验室中我们将拜占庭节点个数逐次增加至超过节点总数的1/3。

由图3 可以看出，随着拜占庭节点数目的增多Omniledger 和DPBFT 两种方案的出块时间都在增加，但DPBFT 方案的增加幅度比较小，相比而言DPBFT方案更优。

图3 分片内拜占庭节点数目对出块时间影响

5.2 交易吞吐量测试

交易吞吐量测试过程中，只改变拜占庭节点比例，其他参数均保持保持不变，对比DPBFT 和Omniledger两种方案的交易吞吐量，结果如图4所示。

图4 不同拜占庭节点比例对TPS的影响

根据图4 所示，随着拜占庭节点比例的增大，两种方案的TPS均在降低，但是DPBFT方案下降幅度稍缓，DPBFT方案较优。

5.3 交易延迟测试

在系统对拜占庭节点比例容忍范围内，通过改变分片个数，对DPBFT 和Omnildger 两种方案的交易延迟进行测试，结果如图5所示。

图5 分片数量对交易延迟的影响

根据图5 所示，随着区块链系统中分片数量不断增加，DPBFT方案和Omniledger方案交易延迟都在增加，但DPBFT 方案具有更低的交易延迟，DPBFT方案更优。

经过上述实验分析可知，DPBFT共识算法提高了系统容错性和交易吞吐量并降低了交易延迟，保证区块链系统分片后的系统效率，使该改进后的共识算法能够应用于更多去中心化场景。

6 结语

扩展性是区块链系统面临的一大问题，受到越来越多的专家的关注，本文针对区块链分片以及分片内达成一致性的的问题进行研究，提出了DPBFT共识算法，在保证分片数据的可信性前提下有效地提升了系统容错性、交易吞吐量并降低了交易延迟。