一种改进的实用拜占庭容错共识算法

冯 宁 庞 慧

(河北建筑工程学院，河北 张家口 075000)

0 引 言

区块链(Blockchain)在2008年作为比特币的底层技术被中本聪(Satoshi Nakamoto)在比特币白皮书中提出[1].区别于之前的交易过程，比特币系统不需要在第三方背书的情况下即可完成交易过程，并且兼具了安全性，隐私性等特征，这种不需要三方机构的交易模式引起了社会各界的巨大关注.而作为比特币在共识层所应用的技术，给众多学者们带来了启发，这种去中心化，不可篡改且兼具安全性的技术迅速在金融交易，信息共识，数据存储，匿名选举等领域崭露头角.但是，去中心化的特性同时也造成了信息的共识时延的大量增加，出块速度受到了很大限制，如何通过对于共识算法的优化，提高共识系统的吞吐量，成为了区块链技术的一个重要研究方向[2].

共识算法作为区块链共识层的关键一环，对于区块链系统的整体性能影响较大，目前主流的共识算法以提升算法的共识效率，增大算法的吞吐量，完善节点的准入规则等为目标，针对现有共识过程中各个模块的缺陷进行优化升级.文献[3]提出了一种在PBFT算法中引入升降级机制的SPBFT(Selection-based Practical Byzantine Fault Tolerance)算法，优化了一致性协议，降低了通信过程中的时间开销，但是针对于节点的动态加入与退出并没有给出有效地解决方案.文献[4]则主要针对于Raft共识算法中会产生的系统分区化的问题引入了节点标记划分集合的方法，通过减少选主节点的数量来降低系统分区化的可能性，但是该算法缺乏对于节点是否为恶意节点的判别，为共识过程后续的主节点的选取造成了不便.文献[5]针对于PoS算法生成区块间隔过长的问题，引入了Silkworm算法，重新在智能合约上定义了最快生成区块时间与最慢生成区块时间，但是该算法在处理区块链分叉与孤立块的奖惩机制上没有有效的解决方案.

在目前的实际应用场景中，兼顾部分去中心化特性与可观共识效率的联盟区块链成为了搭建区块链平台的首选.本文基于PBFT算法，提出了节点标记与动态节点缓冲区的方法，在原始的PBFT算法上优化了对于主节点的选举方案，同时针对新节点的动态加入与恶意节点的惩罚剔除给出了有效地解决办法.最后通过实验验证，在相同网络环境与硬件配置下，DM-PBFT算法的共识效率得到了极大的提升，并成功弥补了原始PBFT算法在动态增删节点上的不足.

1 共识算法分析

1.1 工作量证明算法

工作量证明(PoW)算法是区块链中应用最早的共识算法，被用作比特币的底层共识机制[6].算法以消耗大量计算机算力为代价，通过复杂的数学求解过程来获取满足生成区块条件的随机数.相较于复杂的求解过程，PoW算法的验证过程只需要简单地数学运算即可完成，正是在这种不对称的运算过程保障下，区块链上所添加的区块能够得到各个节点的认可.同时，这种高难度的求解过程通过博弈论的方法屏蔽了恶意节点对区块进行恶意操作的行为.但是PoW算法在严峻的算力竞争中产生了“池化”现象，很大程度上影响了区块链系统去中心化的形成.而该算法的能源消耗与电力资源浪费同样广受诟病.

1.2 所用时间证明算法

所用时间证明(PoET)算法侧重于共识效率，整个算法围绕着Leader节点的选取而设计.PoET算法会根据CPU指令为每个节点生成一个随机等待时间，率先结束等待的节点将被唤醒，用以生成新的区块.算法采用彩票机制的分布策略，因此，使得每个节点所消耗的资源与被选为Leader节点的概率形成正相关的趋势.由于过低的参与代价，令新节点的动态加入不再受到严格的准入机制束缚，保障了区块链去中心化的特性.由于PoET算法依赖于特定功能的硬件设备，因此很难运用在公有链上.

1.3 实用拜占庭容错算法

实用拜占庭容错(Practical Byzantine Fault Tolerance,PBFT)算法由Miguel Castro和Barbara Liskov在1999年提出[7]，PBFT算法相较于原始的拜占庭容错算法，大幅度提升了共识效率，将时间复杂度的规模降低为O(n2).

PBFT算法于联盟链中广泛运用，是一种以BFT为核心机制的高容错算法，PBFT算法允许最多f个拜占庭节点存在，在网络中的全部节点数N>3f+1的前提下，仍能保证系统的共识完成[8].

该算法依赖于加密算法，对于主节点向从节点发送的共识消息进行生成签名，并在从节点接收到主节点消息后对于共识消息签名进行验证.节点会向其他节点发送自身的共识结果，并计算其他节点验证通过的个数来完成共识过程.

整个算法基于状态机复制原理，由一致性协议，视图切换协议与检查点协议三部分组成[9-10].PBFT算法的一致性协议通过共识三阶段实现，分别为预准备(pre-prepare)、准备(prepare)和提交(commit)3个阶段，三阶段的执行流程见图1,从节点在三阶段中完成一致性共识，则将共识结果响应回主节点完成整个共识过程.若共识失败则会引起备份节点发起视图更换协议，对主节点进行轮换，下一任主节点的编号由当前视图编号对节点总数取模得到，如公式(1)：

图1 PBFT算法一致性协议三阶段流程

p=vmod|R|

(1)

式中：p为所选取的下一任节点编号，v代表当前视图编号，并将节点总数以R表征.

同时PBFT算法为了保证在执行视图切换协议后能够恢复之前的请求，需要将存储在备份节点Log中的消息进行状态同步，每一轮Reply后都要进行一次状态同步显然造成了大量的时间浪费，为了避免这种情况，PBFT算法采用在K条请求后执行一次状态同步的方案.主节点会摒弃水位区间[h,H]范围以外的请求消息并在区间内进行选取请求，而H的选取则是由周期内消息条数K的整数倍规定[11].通过检查点协议可以舍弃日志中不必要的请求消息，从而保障了PBFT算法的频率稳定.

2 PBFT算法改进方案

通过对PBFT算法的分析研究发现，该算法虽然有着不俗的容错能力，但是在对于恶意节点作恶后，并没有给出明确的惩罚机制[12].随着共识系统中节点数量的增加，恶意节点担任主节点的几率也随之增大，这极大的增加了通信量上的浪费，同时，过多的视图切换也将导致系统过多的时间开销.为了改变这种现状，改进后的DM-PBFT算法为参与到系统中进行共识的节点设置了节点状态信息日志，通过此种方法对恶意节点施加惩罚.同时，共识系统中的节点由于网络环境影响并未在规定时间内做出回应，这也将可能与恶意节点造成相同的后果，共识系统中的共识节点的减少将导致最后的共识消息的信任度减少，为了避免这种共识节点只减不增的情况，在系统中构建节点缓冲池，以实现共识系统中节点的动态增加，以此协调共识系统中恶意节点与正常节点的比例，使二者数量始终保持动态平衡.

2.1 节点状态信息日志

联盟链一般运用于没有强中心化、多方合作、安全可控的业务流程中[13]，相较于节点可匿名动态加入的公有链系统，联盟链设有严格的准入机制，但是仍然无法屏蔽全部的拜占庭节点担任主节点的情况，而由于过长的网络延迟导致无法正常向从节点发送共识信息的主节点同样不适合继续担任主节点[14-15].

对于恶意节点以及由于网络环境等因素导致无法正常发送共识信息的节点，本算法将对其施以相应的惩罚机制来避免其二次担任主节点的情况产生，造成不必要的花费在视图切换上的时间开销和通信资源浪费.

DM-PBFT算法使共识系统中的共识节点各自维持一份节点状态日志，日志中记录着每一轮共识结束后的节点状态.

所有共识节点在初始状态下的日志中存储着“Routine”信息，节点日志存储为“Routine”信息的节点被认作为常态节点，即不存在恶意行为并且网络环境良好的节点.

而对于当前视图中不进行共识的备选节点的日志中则存放“Alternative”信息，直到备选节点通过网络延迟测试被选为共识节点后，将其对应的日志信息更新为“Routine”.

DM-PBFT在原始PBFT算法的基础上对恶意节点增添惩罚机制，即将不再适合充当主节点的共识节点所维持的日志信息更新为“Byzantine”.而之后的共识过程中，日志信息为“Byzantine”将不再有资格充当主节点来完成对客户端信息的接收.但其仍可以完成在后续的一致性协议中的共识过程，以此来满足DM-PBFT算法的容错能力稳定.整体流程如图2所示.

图2 添加节点状态信息日志的具体流程

2.2 一致性协议优化方案

DM-PBFT算法允许共识系统中存在f个拜占庭节点，节点总数N应满足公式(2)：

N>3f+1

(2)

式中：N为节点总数，f为共识系统中的拜占庭节点个数.

本算法允许共识系统在拜占庭节点不大于1/3的情况下仍然可以完成共识过程，保障了DM-PBFT的容错能力与原始PBFT算法持平.而对于拜占庭节点担任主节点的情况，则为其设定相应的惩罚机制.

对于优化后的一致性协议进行如下描述：

请求阶段(REQUEST):客户端c在向节点发送请求之前，会首先对节点的状态信息日志进行读取，若节点的状态信息被读取为“Byzantine”，则进行节点更换选择，对当前节点编号n进行加一操作，并重复上述过程.若读取到的节点的状态信息为“Routine”，则可以选取该节点作为该轮视图的主节点，并向该主节点p发送请求.其中o表示客户端对主节点发送的操作信息，t代表请求时客户端为其添加的时间戳，c为客户端所对应的标识信息.该阶段客户端会将自己所请求的内容m以及m生成的消息摘要d(m)发送给主节点.

预准备阶段(PRE-PREPARE):主节点接收到客户端的请求后会对请求的消息进行校验，并剔除非法的请求信息.对于合法消息，主节点会为其进行编号操作,编号完成后即可向其他从节点发送<,m>消息.v:当前视图的编号，d:客户端的消息摘要.若主节点在一轮共识时长内未向其它从节点发送请求消息，可以认为该节点资质已不符合继续担任主节点，共识系统将读取该节点的状态信息日并将其更新为“Byzantine”，并且运行视图切换协议，选取出节点状态日志为“Routine”的节点作为新的主节点.

准备阶段(PREPARE):从节点在接收到主节点的PRE-PREPARE请求后，将对请求信息进行验签操作，并且检测消息编号n是否在正常的水位区间[h,H]范围内，若消息被检测为非法状态，则开启检查点协议，丢弃该请求.若请求通过，从节点则会向包括主节点的其他节点发送请求，其中i为当前从节点所属编号.

提交阶段(COMMIT):当各个节点在接收到PREPARE消息后将对其进行二次验证，若验证失败，则将该PREPARE消息丢弃.若节点收到2f+1条验证通过的PREPARE消息，节点就会向除自己以外的其他节点发送消息.

应答阶段(REPLY):在节点接收到2f+1条COMMIT消息后，则说明共识的核心三个阶段已经成功运行，并且大多数的节点已经对消息完成了共识，这时即可运行客户端发来的请求操作o,并向客户端发送应答消息.

2.3 新增节点缓冲池

为了使共识系统在剔除被惩罚的节点后仍能维持其原有的公平性，保障共识消息的可信度，DM-PBFT算法将为新节点的动态加入共识系统提供方案.

DM-PBFT引入节点缓冲池概念，将请求加入共识系统的新节点先存储于节点缓冲池中，在K轮共识后向共识系统添加M个新节点，M为小于或等于K的1/3最大整数，假设每3轮会产生一个拜占庭主节点，那么在3的倍数轮次后为共识系统进行节点填补，并完成一次标记信息日志为“Byzantine”的节点剔除工作.若节点缓冲池中不存在请求加入的备选节点，则在下一个K轮共识中保留拜占庭节点，保证节点总数的平衡.

为了使加入到节点缓冲池中的备选节点具备高可靠性，DM-PBFT设定了严格的准入机制，对备选节点进行网络环境测试以及基于数字签名技术的可信度检测，如图3所示.通过测试的节点将被选为备选节点，并将其状态信息日志更新为“Alternative”，直至共识系统向节点缓冲池发来请求新节点的选取后，被选中的备选节点的状态信息日志将更新为“Routine”.

图3 节点缓冲池流程

在严格的准入规则束缚下，节点缓冲池中存在的拜占庭节点数应维持在1/4以下，使得更新后的共识系统总结点数N＇满足公式(3)：

(3)

式中：N＇为更新后共识系统中的总结点数，M为K轮共识后向共识系统添加的新节点个数，N为更新前共识系统中的节点总数.

使得更新后的共识系统的容错能力仍然保持总节点数的1/3.

3 DM-PBFT算法实验与结果分析

DM-PBFT算法由Golang语言编译而成，在整个系统中将模拟四个共识节点，并为其设置四个不同的监听端口号，实现对请求服务的监听测试，如图4所示.以下将对同一环境下的PBFT算法与DM-PBFT算法进行共识时延的比对分析，同时对于最终的共识结果进行基于信任度的分析讨论.

图4 节点及其端口号

3.1 测试环境

实验运行于Intel(R)Core(TM)i5-4200H硬件平台之上，网络环境为300Mbit/s,通过比对原始PBFT算法与DM-PBFT算法对于同一共识消息的共识时延，分析改进后算法所带来的提升幅度.

3.2 共识时延对比

在共识算法的比对分析过程中，通过设定共识系统中不存在拜占庭节点，与存在拜占庭节点两种情况来对PBFT算法与DM-PBFT算法的共识时延进行对比.在测试过程中，选取20组不同的共识消息进行发送请求，为保证实验结果具备鲁棒性，采取对20次实验求取平均值的方式求得结果，如图5所示.

图5 共识延迟比对

通过共识延迟比对图，可以清晰的看出，在整个共识系统无拜占庭节点的情况下，DM-PBFT算法具备着和原始PBFT算法同样的共识延迟.而在存在拜占庭节点的共识系统中，由于原始PBFT算法对于拜占庭节点当选主节点的情况并没有有效的规避方案，所以在拜占庭节点担任主节点后，开启视图切换的过程上浪费了大量时间，而反观DM-PBFT算法由于只有拜占庭节点首次担任主节点时才会引起视图切换，而在下次主节点选举时，节点状态日志被标记为“Byzantine”的节点将不再有资格担任主节点，这样将极大地节省了后续在视图切换上的大量时间花费，所以，在存在拜占庭节点的共识系统中，DM-PBFT算法的共识延迟仅有小幅度的上涨现象.

3.3 共识信任度分析

DM-PBFT算法为了使共识系统能够动态的进行新节点的补充，保障系统在对恶意节点进行惩罚剔除后仍能保证共识的可信度，引入了节点缓冲池的机制，通过以下两点来保证共识结果的可信度：

1)由于节点缓冲池采用严格的准入机制，新节点在申请进入节点缓冲池时将接收网络测试与可信度测试，通过多次实验得出，节点缓冲池中的备选节点为拜占庭节点或网络环境不佳的节点的占比小于1/4.

2)K轮共识后被添加至共识系统的新共识节点与原共识系统被剔除部分恶意节点后的总数将继续维持原有的拜占庭容错占比，即拜占庭节点占共识系统中节点总数的1/3.

综上所述，DM-PBFT算法有着与原始PBFT算法同样优秀的容错能力，亦可保障在共识系统中参与共识完成的节点数不会产生有减无增的现象，使得共识结果不会产生过度中心化，保证了共识结果的可信度.

4 结束语

本文针对于联盟链中的实用拜占庭容错(PBFT)算法无法阻止拜占庭节点以及网络环境不良的节点继续担任主节点，与PBFT算法无法支持节点动态加入和退出共识系统这两个问题进行优化改进.在PBFT算法基础上加入了节点状态信息日志与节点缓冲池机制提出了DM-PBFT算法.实验结果表明，在允许共识过程中存在拜占庭节点的情况下，有效的阻止了拜占庭节点二次担任主节点的情况发生.同时在节点缓冲池机制对于共识节点的增补，实现了共识系统中新节点的动态加入，保障了共识系统中的节点数量，避免由于共识系统中参与共识节点数量减少而产生的“中心化”，“高集成度”现象.接下来将对PBFT算法通信量过大以及签名的安全性如何增强等问题展开研究，以进一步提升PBFT算法的吞吐量，降低其共识延迟.