基于信誉的动态授权PBFT共识机制
2019-10-08李俊清辛衍森宋长青
李俊清 辛衍森 宋长青
摘 要： 区块链是一种基于零信任基础、去中心化及不可篡改的分布式账本技术。共识算法作为区块链主要技术之一，其效率直接影响区块链系统性能。针对PBFT共识算法运行效率低的问题，本文提出了基于信誉的动态授权PBFT共识机制，引入信誉评价体系对系统节点进行信誉评价，动态决定从信誉最高的节点中选取共识节点，同时实现了非停机情况下动态增删节点的功能，且随着系统长期运行，所能容忍的拜占庭节点动态增加;优化了一致性协议，将传统的一致性协议与基于speculation技术的拜占庭协议进行融合，降低了算力开销和通信代价;通过对共识节点的信誉及行为分析，进一步降低恶意节点成为共识节点的概率，解决了由拜占庭节点作为主节点带来的交易延迟增加问题。最后从算力开销、交易吞吐量和容错性能等方面进行了论证分析。
关键词： 区块链;PBFT共识算法;全局信誉模型;动态授权;speculation技术
中图分类号： TP311.13 文献标识码： A DOI：10.3969/j.issn.1003-6970.2019.05.001
本文著录格式：李俊清，辛衍森，宋长青，等. 基于信誉的动态授权PBFT共识机制[J]. 软件，2019，40（5）：0107
【Abstract】： Blockchain is a distributed ledger technology based on zero-trust foundation， decentralization and non-tamperability. Consensus algorithm is one of the main techniques of blockchain， and its efficiency directly affects the performance of blockchain system. Aiming at the low efficiency of PBFT consensus algorithm， this paper proposes a reputation-based dynamic authorization PBFT consensus mechanism， introduces a reputation evaluation system to evaluate the reputation of system nodes， and dynamically decides to select consensus nodes from the nodes with the highest reputation. At the same time， the function of dynamically adding and deleting nodes in the case of non-downtime is realized， and the Byzantine nodes that can be tolerated dynamically increase with the long-term operation of the system; The consistency protocol is optimized， and the traditional consistency protocol is merged with the Byzantine protocol based on speculation technology， which reduces the computational overhead and communication cost; Through the analysis of the reputation and behavior of the consensus node， the probability of the malicious node becoming the consensus node is further reduced， and the problem of increased transaction delay caused by the Byzantine node as the master node is solved. Finally， the argumentation analysis is carried out from the aspects of computational power， transaction throughput and fault tolerance.
【Key words】： Blockchain; PBFT consensus algorithm; Global reputation model; Dynamic authorization; Speculation technology
0 引言
區块链（Blockchain）作为当下热门的分布式数据库技术方案，包含分布式数据存储技术、P2P网络传输机制、分布式节点间的共识机制、加密算法、可编程的智能合约等技术[1]。由于其具有去中心化、开放性、自治性、不可篡改和匿名性的特点，区块链不仅在数字货币等数字资产中发挥巨大作用，而且对金融服务、公共服务、社会生活等领域产生深远影响。
区块链的快速发展的同时，其存储、共识、监管和安全等方面问题凸显，其中共识算法效率制约着区块链技术大范围应用。起初比特币区块链采用依赖节点算力的工作量证明共识算法（POW）来实现一致性选择[1]。随着技术发展，非许可链中相继涌现出权益证明机制（POS）和股份授权证明机制（DPOS），许可链发展了实用拜占庭容错机制（PBFT）[2]等共识机制，但每种机制在吞吐量、时延、功耗等方面都难以兼顾。
本文基于DPOS的思想，利用信誉评价体系进行共识节点的选取，在PBFT共识机制基础上融合基于speculation技术的拜占庭算法，同时引入拜占庭节点检测机制，以保障系统长期运行环境的安全性和高效性。
1 相关知识
1.1 共识机制介绍
共识就是使得在权力高度分散的去中心化系统中各个节点达成一致，共识机制在去中心化的基础上解决了节点间互相信任的问题。如何在分布式系统中高效达成共识是分布式计算领域的重要研究问题之一[1]。区块链网络中节点数目越多，去中心化程度越高，那么节点决策权越小，系统达成共识的效率越低。
1.1.1 工作量证明机制（POW）
中本聪在2009年实现的比特币系统中采用了POW共识机制，其核心思想是通过算力进行挖矿，获取记账权。比特币所采用的是一种可重复使用的Hashcash工作证明机制，使得生成工作证明量是一个概率意义上的随机过程[2]。在系统中，所有的节点（矿工）都要根据各自计算机算力使用不同的随机数持续计算一个特定的哈希值，该过程被称为“挖矿”。为了驱使矿工进行挖矿，该行为设定了相应的奖励机制。由此可知，该共识机制的优点是通过算力竞争保证系统的完全去中心化和安全性，缺点是挖矿造成大量能源消耗和硬件资源浪费。比特币系统动态调整目标值，维持生成区块的平均时间和交易确认时间分别在十分钟和一小时左右，效率低，难以大范围应用。
1.1.2 权益证明机制（POS）
Nick Szabo提出的POS可以说是为了解决POW的资源消耗问题的一种节能替代机制，本质上是用对货币所有权的证明取代算力竞争。货币的来源是在生成一个区块时，由矿工发起关于特定货币分配的交易，POS是基于币龄来选择节点创建下一个区块，节点所持有的代币越多、时间越长，挖矿的难度越低，达成共识的时间越短。与POW相比，POS可以节省更多的资源，性能有所提高，而其容错能力与POW相当，并没有摆脱节点挖矿，不具有普适性。由于该机制相信权益高的节点攻击网络的可能性低，所以一定程度上安全性降低。
1.1.3 股份授权证明机制（DPOS）
DPOS是在POW及POS的基础上，用节点的权益作为选票选出一定数量的代表节点轮流进行区块的生成和验证。过程中产生的收益由这些代表节点平分，并且含有权益的节点可以随时发起投票更换“有问题”的代表节点。DPOS机制大幅降低了直接参与共识的节点，减少了对确认的需求，使共识验证过程可以在秒级单位内完成。随之带来的是节点参与投票不积极或者代理投票的问题，同时对于代币的依赖使得该机制难以适用于商业应用。
1.1.4 实用拜占庭容错机制（PBFT）
拜占庭容错技术能够容忍任意形式的软件错误和安全漏洞，作为一种解决分布式系统容错问题的通用方案，复杂度由指数级降到了多项式级，大大降低了拜占庭协议的开销[3]。PBFT作为一种状态机副本复制算法，其前提要求节点共识时状态相同，且对同一消息处理结果也必须相同。PBFT中，区块链网络中存在拜占庭节点数f，则总节点须大于3f，而多于3f的节点带来是系统算力增加，容错性能较低。其在交易吞吐量和共识延迟方面性能有较大提高，符合大部分应用要求，是目前最主流的共识算法。目前，HyperLedger联盟、中国ChinaLedger联盟等区块链联盟都在进行该共识机制的实际部署应用[2]。
1.2 全局信誉模型
胡建理等学者提出的一种基于反馈可信度的分布式P2P信任模型（FCTrust）[4]是在原有的基于信誉的全局信任模型上[5，6]，为了防止恶意节点进行虚假评价、共谋欺骗等恶意行为，提出的一种节点反馈信息评价机制，将全局可信度高的节点与反馈信息可信度高的节点区分开来。该反馈信息评价机制将节点间交易频率和节点评价的相似度纳入主要参考因素。FCTrust是通过参与交易的节点之间相互评价，分析节点之间的交易次数、评分比较和节点的全局信誉值，为该节点分配一个信任值，然后通过迭代运算得到一个在全局范围内的信誉值，该信誉值在没有交易进行的情况下对所有节点是保持不变并且唯一的。
由于其引入了节点反馈信息评价机制，所以相比EigenTrust模型对恶意节点的虚假评价、对抗共谋等恶意行为的处理更加有效，给予恶意节点更低的全局信誉值。综合考虑了交易节点之间的局部信任、节点自身的全局信誉值和节点间反馈信息可信度，降低系统信任误差度，使得节点最终得到的全局信誉值更加可靠和精确。FCTrust要求所取得最终的全局信誉值依赖的节点评价及反馈信息具有近期有效性，并且利用分布式求解协议计算全局信誉值，因此大大降低了算法的复杂度。例如在消息复杂度的测试中，得到EigenTrust模型為O（n2），而FCTrust模型仅为O（n）[4]。
2 共识机制优化
本文提出了一种优化的共识机制，以下称为基于信誉的实用拜占庭容错机制，简称RPBFT（reputation practical byzantine fault tolerance）。利用全局信任模型决定直接参与共识的节点;采用传统一致性协议融合基于speculation技术的拜占庭协议，降低网络开销，提高系统效率;通过对共识节点的行为和其自身的全局信誉值分析，引入拜占庭节点的检测机制，对拜占庭节点进行降级处理，提高该系统所能容忍的最大恶意节点数。
2.1 共识节点的选择
基于DPOS的思想，同时为了避免投票机制带来的投票者不积极、代理投票等导致投票的有效性降低的问题，本文利用全局信任模型，将节点的全局信誉值作为选择共识节点的重要标准。为了确保选取的共识节点都处于正常在线状态，为每一个节点设置一个状态标识。然后按照公式1：
Rf=GrfState （1）
公式1中，Rf是节点信用系数值，Grf代表节点的全局信誉值，State（Boolean类型）表示节点状态;当节点出现挂机、被攻击、自身故障、网络问题、离线状态等不能正常运行时State为0。由公式得出每个节点的信用系数值，按照该信任系数值从高到低选取前100位组成共识节点集，其中各节点之间是相互平等的，继续选取前50位组成预备共识节点集，两节点集中节点数目可由所有节点投票动态决定。
当共识节点集正在进行区块的生成及验证时，由于节点的State可能发生变化，要求预备共识节点集是动态变化的。随着交易进行对节点评价和反馈消息会不断更新，同时要求这些评价和反馈消息具有近期有效性，以保证节点的全局信誉值是动态变化的。因此，为保障系统实时有效性，共识节点集每经过一段时间需进行更新。该时间间隔内若在共识节点集中发现恶意节点，系统将恶意节点赋予更低全局信誉值并将其剔除共识节点集，由预备共识节点集的首个节点代替该节点参与共识。随着系统的运行，正常节点交易越频繁，全局信誉值越高，而各类恶意节点能够被全局信任模型有效识别并赋予更低的全局信誉值，系统开始良性循环，恶意节点被选作共识节点的可能性非常低。共识算法中所能容忍的拜占庭节点数不变，但恶意节点被选作共识节点的可能性降低，因此整个系统可容忍的恶意节点数量动态增加。
2.2 RPBFT共识算法
2.2.1 算法定义
PBFT共识机制在保证活性和安全性的基础上，当总节点数目为3f+1时，其能容忍的拜占庭节点数最大为f。该算法中由一致性协议保证每一个正常节点以相同顺序执行客户端的请求消息;在主节点发生系统错误或成为拜占庭节点时利用视图更换协议更换主节点，使正常节点执行过的客户端请求不被篡改;检查点协议用以清除日志记录、设置水线值（h和H）、同步节点状态。
RPBFT共识机制，相对于传统的一致性协议，融合了基于Zyzzyva5协议[7]的拜占庭算法，该算法引入了speculation技术，在节点接收请求后直接执行请求，省去了一致性协议中耗时的两两交互环节，但在共识过程中若存在拜占庭节点，其性能会大大降低。因此，我们利用全局信任模型和拜占庭节点检测机制大幅降低甚至消除共识节点中拜占庭节点的存在，将传统的一致性协议和基于speculation技术的拜占庭协议进行结合。
2.2.2 算法流程
假设共识节点共有n个，则从0到n-1对节点进行编号，所有节点的相同状态信息称为视图，同时对视图由0开始递增编号。视图中要求有一个主节点（primary），该主节点采用公式2选取，
p=（h+v）mod n （2）
公式2中p代表节点编号，h代表当前共识区块高度，v代表视图编号;其余共识节点称作从节点（replica）;当primary节点失效时，从replica节点中依据公式2选取一个新的primary节点[8]。算法如下：
（1）若共识节点中无拜占庭节点
RPBFT共识的具体步骤如下：
a）客户端将交易信息发送到primary节点。
b）primary节点收到客户端请求消息后打包排序，然后广播预准备消息给replica节点。
c）节点执行该请求，最后向客户端反馈结果，如果客户端收到3f+1个节点反馈的信息并且信息全部相同，则共识成功。
d）若客户端没有收到所有节点的反馈信息或者存在不相同的反馈信息，则说明共识失败，共识节点中存在拜占庭节点，转到一致性协议共识流程重新共识。
RPBFT共识流程采用基于Zyzzyva5协议的共识流程，如图1所示。
（2）若共识节点中存在拜占庭节点
RPBFT共识的具体步骤如下：
a）客户端将交易信息发送到primary节点。
b）primary节点接收消息后进行打包并检验其中交易合法性，删除非法交易信息，分配序列号。然后向replica节点发送预准备消息<
c）replica节点收到预准备消息，则表明消息通过节点验证（该验证包括视图编号、消息序号、摘要、签名等）且进入准备阶段，发送准备消息
d）在节点收到2f个准备消息后进行合法性验证，写入日志，准备消息必须写入日志，而预准备消息则可进行选择记录，日志的写入标志着准备阶段完成。发送确认消息
e）节点收到2f+1个确认消息，代表着达成共识，然后節点执行该请求并写入数据，最后向客户端反馈信息。
RPBFT共识流程采用基于传统一致性协议流程，如图2所示。
随着系统运行，节点的全局信誉值越来越精确，共识节点中存在拜占庭节点的可能性大大降低，因此系统将会采用基于speculation技术的算法进行共识并保持良性循环。从而降低共识的响应延迟、增加系统吞吐量、减少算力、降低功耗。图3为系统完整的共识算法流程图。
2.3 拜占庭节点检测与降级
在共识节点集没进行更新的这段时间内，共识节点有可能会发生系统故障、网络延迟或遭受恶意攻击等错误，则该节点被称为拜占庭节点。因此，当一个共识阶段完成后，未能向客户端发送反馈消息或者反馈消息不一致的节点，则认为产生错误行为，此时本算法将降低其全局信誉值并且立即剔除共识节点集，由预备共识节点集中首个节点代替参与共识。进一步降低了共识节点中拜占庭节点存在的可能性，配合全局信任模型为系统执行基于speculation技术的拜占庭协议提供保障，提高系统效率。
3 性能分析
現有的共识算法中，全球大部分算力被比特币区块链系统所吸引，因此其它采用POW的系统很难获得足够算力以保障系统安全，而且系统达成共识时间较长;POS虽然解决了一部分资源浪费的问题，但仍然没有摆脱挖矿过程，没有解决其本质问题;DPOS是在POS的基础上发展而来，却没有摆脱代币的制约;因此，POW、POS、DPOS在众多的应用中都存在着制约问题。许可链中普遍采用的PBFT共识效率和吞吐量高，但是较低的容错性和两两交互的通信代价导致其只适用于小规模的许可链。本文提出的RPBFT在PBFT基础上，利用全局信任模型选取共识节点，提高共识效率，增强系统容错性;将PBFT中静态的共识节点机制调整为动态可加入、剔除和降级处理机制，适用于非许可链系统和大规模的许可链系统。
从算力开销、交易吞吐量和容错性能三个方面进行RPBFT与PBFT对比分析如下：
3.1 算力开销
PBFT共识算法中存在两次全网节点相互通信的过程，通信代价高，所以限制了该共识在公有链和大规模的联盟链系统中的适用性。RPBFT相比PBFT大大降低两两通信交互的过程，因此其通信代价大幅降低。
由于RPBFT引用了全局信任模型，通信代价有所增加，但其复杂度远小于PBFT的复杂度;同时RPBFT将传统的一致性协议与基于speculation技术的拜占庭协议进行结合，全局信誉值低的恶意节点参与共识的概率非常低，配合拜占庭节点检测与降级机制，最优情况下可以消除共识节点中拜占庭节点，所以大部分共识过程中，系统采用基于speculation技术的拜占庭协议进行区块生成与验证。
下面利用该全局信任模型求解所选出的共识节点中恶意节点的概率，该模型的性能评价中引入成功交易率（STR），即系统中成功交易次数占总交易次数的比例。这里可以认为是一个节点选择另一个节点进行交易，若交易节点是正常节点，则交易成功，否则交易失败，可以认为成功交易率亦代表节点选择正常节点的概率。恶意节点包括简单恶意节点（SMS）、不诚实推荐节点（SMR）、协同恶意节点（CM）和策略型恶意节点（SMP）[4]。由于SMP节点能够视具体情况进行相应评价，以避免被模型识别并赋予较低信誉值，因此，其对系统的影响要大于其他种类的恶意节点。假设系统中恶意节点全为SMP节点且占系统总节点33%，STR在随SMP节点的变化情况，如图4
由图4可知，当SMP节点占比为33%时，STR约为0.84。由于现实系统中恶意节点不只是SMP类型，即说明在恶意节点为33%的系统中，选择共识节点时正常节点的概率要大于84%。若节点在共识中不作为，则可认为该节点为“漏网”的拜占庭节点，赋予低信誉值并且降级处理，进一步降低拜占庭节点的存在，降低算力开销。
3.2 交易吞吐量
区块链系统的交易吞吐量是量化系统运行效率高低的一个重要标准。RPBFT有效的降低了交易延迟、提高吞吐量。
RPBFT中主节点发生故障的可能性降低，降低调用试图切换协议的频率，降低了交易延迟;算力开销降低，缩短了交易处理时间，进一步提高了交易吞吐量;因此，RPBFT的交易吞吐量随着系统运行时间增加而增加，相比PBFT的相对稳定值有较大提高。
3.3 容错性能
PBFT共识算法要求系统能容忍的最大拜占庭节点数不超过全网结点的1/3，容错能力较低，对系统性能影响较大。RPBFT的容错性能要大于33%。
RPBFT能够随着系统的长期运行，共识节点中拜占庭节点数大大降低甚至消除，恶意节点的全局信誉值越来越低，所以恶意节点在共识节点的选取上所发挥的作用微乎其微。由图4可知，SMP节点占比增加至40%时，STR仍高达0.8，配合拜占庭检测机制，则当系统中恶意节点适当增加时并不会对系统产生影响。因此，RPBFT能容忍的恶意节点数随着系统进入良性循环而增加，可由交易吞吐量检测来间接反应适当增加恶意节点时对系统性能的影响。
以上分析对比在相同的非必要因素条件下，论证了RPBFT共识机制具有更低的通信开销、更高的交易吞吐量和容错能力。
4 总结与展望
本文提出的基于信誉的PBFT共识机制，通过全局信任模型为每个节点分配全局信誉值，配合拜占庭节点检测和剔除机制，并融合了传统一致性协议算法和基于speculation技术的协议，有效改善了PBFT的容错性能较低和静态节点结构，进一步提高系统性能。
本文下一步工作是：如何利用信誉评价模型赋予每个节点更加精确和准确的信誉值，缩短系统运行进入良性循环的时间;在共识节点选取和读取节点信誉值进行比较时，如何严格的保障数据的隐私安全。
参考文献
[1] 袁勇， 王飞跃. 区块链技术发展现状与展望[J]. 自动化学报， 2016， 42（4）： 481-494.
[2] 蔡亮， 李启雷， 梁秀波. 区块链技术进阶与实战[M]. 北京： 人民邮电出版社， 2018.
[3] 范捷， 易乐天， 舒继武. 拜占庭系统技术研究综述[J]. 软件学报， 2013， 24（06）： 1346-1360.
[4] 胡建理， 吴泉源， 周斌， 刘家红. 一种基于反馈可信度的分布式P2P信任模型[J]. 软件学报， 2009， 20（10）： 2885- 2898.
[5] 窦文， 王怀民， 贾焰， 邹鹏. 构造基于推荐的Peer-to-Peer环境下的Trust模型[J]. 软件学报， 2004（04）： 571-583.
[6] Xiong L， Liu L. PeerTrust： Supporting Reputation-Based Trust for Peer-to-Peer Electronic Communities[J]. IEEE Transactions on Knowledge & Data Engineering， 2004， 16（7）： 843-857.
[7] Kotla R， Alvisi L， Dahlin M， Clement A， Wong E. Zyzzyva： Speculative Byzantine fault tolerance. In： Proc. of the 21st ACM SIGOPS Symp. on Operating Systems Principles. New York： ACM Press， 2007， 45-58. [doi：10.1145/1294261. 1294267]
[8] 劉肖飞. 基于动态授权的拜占庭容错共识算法的区块链性能改进研究[D]. 浙江大学， 2017.
[9] Miguel Castro， Barbara Liskov. Practical byzantine fault tolerance and proactive recovery[J]. ACM Transactions on Computer Systems （TOCS）， 2002， 20（4）.
[10] Cowling J， Myers D， Liskov B， Rodrigues R， Shrira L. HQ replication： A hybrid quorum protocol for Byzantine fault tolerance. In： Proc. of the 7th Symp. on Operating Systems Design and Implementation. Berkeley： USENIX Association， 2006. 177-190.
[11] 王晓光. 区块链技术共识算法综述[J]. 信息与电脑（理论版）， 2017（9）： 72-74.
[12] 周邺飞. 区块链核心技术演进之路——共识机制演进（1）[J]. 计算机教育， 2017（4）： 155-158.
[13] Nakamoto S. Bitcoin： A peer-to-peer electronic cash system[J]. Consulted， 2008.
[14] Hendricks J， Sinnamohideen S， Ganger GR， Reiter MK. Zzyzx： Scalable fault tolerance through Byzantine locking. In： Proc. of the 2010 IEEE/IFIP Intl Conf. on Dependable Systems and Networks. 2010. 363-372. [doi：10.1109/DSN.2010.5544297]
[15] 常文军， 孙超平， 胡鑫. 基于分布式偏好关系的多属性决策方法及应用[J]. 计算机应用研究， 2017， 34（12）： 3693- 3697+3707.
[16] 闵新平， 李庆忠， 孔兰菊， 张世栋， 郑永清， 肖宗水. 许可链多中心动态共识机制[J]. 计算机学报， 2018， 41（05）： 1005-1020.
[17] I Bentov， C Lee， A Mizrahi， M Rosenfeld. Proof of Activity： Extending BitcoinS Proof of Work via Proof of Stake. Acm Sigmetrics Performance Evaluation Review， 2014. 42（3）： 34-37.
[18] 苑超， 徐蜜雪， 斯雪明. 基于聚合签名的共识算法优化方案[J]. 计算机科学， 2018， 45（02）： 53-56+83.
[19] 张永， 李晓辉. 一种改进的区块链共识机制的研究与实现[J]. 电子设计工程， 2018， 26（01）： 38-42+47.
[20] Happe A， Krenn S， Lornnser T. PBFT and Secret—Sharing in Storage Settings[C]//Twenty-fourth International Workshop on Security Protocols. 2016.
