陈忠贤 李秦伟，2 罗婧雯

（1.贵州大学计算机科学与技术学院 贵阳 550025）（2.贵州省公共大数据重点实验室 贵阳 550025）

1 引言

共识问题是计算机科学领域的经典问题，最早出现是在20个世纪80年代，Pease和Leslie Lamport对拜占庭将军问题进行了形式化的描述和分析［1～2］。自中本聪提出比特币以来［3］，共识成为了区块链系统中其中一个新的研究热点［4～5］，目前，区块链中主流的共识算法包括有工作量证明（PoW）［6］、股 权 证 明（PoS）［7～8］、委 任 权 益 证 明（DPoS）［9］、实用拜占庭容错算法（PBFT）［10］。工作量证明的思想最早来源于哈佛大学教授Cynthia Dwok［11］，其目的是为了通过邮件发送方计算一定难度的数学难题来增加垃圾邮件发送者的成本，从而解决垃圾邮件问题。在比特币系统中，PoW主要应用在数字货币系统中，旨在通过算力证明来获得一个区块的记账权，从而换取获得比特奖励的机会，这造成了为提高哈希计算而不断优化的挖矿设备的浪费和大量的电力资源的消耗。PoS弥补了PoW的不足，使用股权机制来代替算力证明完成记账节点的选取。目前，有Peercoin、NTX、Blackcoin使用了基于PoS思想的共识算法，但PoS也存在这样一些问题：某些节点拥有大量的区块链资产且长期持有，这就可能造成股份分配不均，从而造成拥有大部分股权的节点垄断出块。2014年，雷恩（Larry Ren）提出PosV共识算法［12］，Slimcoin提出了PoB共识算法［13］。PosV与PoB算法既解决了PoW的能源消耗问题又规避了PoS的风险问题。DPoS对PoS中心化进行了适当妥协［6］，有效解决了PoW的纯碎依靠算力以及PoS的首富账户的寡头垄断问题。但是DPoS对于恶意拜占庭节点的处理存在诸多困难。PBFT算法能容忍1/3的拜占庭节点，在性能上有着较好的表现，但三阶段的大量消息广播侵占有限带宽从而影响执行的效率。中国区块链社区NEO提出了一种改进的拜占庭容错算法DBFT［14］，该算法是一个PBFT与PoS算法的有机结合，首先根据节点的权益来选出一些记账人，然后记账人之间通过PBFT算法来达成共识。

上述常用的共识算法中，PoW和PoS是目前公有链［15］普遍采用的算法，PoW与PoS可拓展性良好，因为新加入的节点只要能提供算力证明或权益证明即可，但是两者的吞吐量以及交易速度等众多性能瓶颈使得很多应用场景被限制。不论是PoW、PoS、DPoS亦或是其衍生算法，它们的共识机制都是依赖于代币的，但国家法律法规不支持使用代币。相比之下，PBFT实用拜占庭容错算法更适合作为服务平台来搭建区块链应用。

1.1 相关工作

PBFT算法主要解决了缺少可信的中央节点和可信任的通道的情况下，分布在网络中的各个节点如何达成共识的问题。PBFT是由Miguel Castro和Barbara Liskov在1999年的OSD199会议上提出来的，它改进了拜占庭算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行［6］。PBFT算法容错模型为3f+1，即当存在f个错误节点时，总节点数n≥3f+1时，拜占庭将军问题可以被解决，其容错性为33%。但PBFT也存在这样的问题：要实现节点之间的协商状态一致，需要经过三阶段（预准备阶段、准备阶段、确认阶段）的节点间通信，其中有两次全网全节点广播，大量的消息广播非常占用通信资源。其次，从PBFT算法流程可知，传统的PBFT算法针对的是静态网络结构。该算法中节点数目的增多可以增强系统的容错性，但PBFT算法不能够动态的感知节点的加入或者退出，那么就无法根据拜占庭节点数量和总结点数量进行动态变化，这无疑是浪费了新加入节点的资源。

1.2 改进方案

针对上一节提出的PBFT算法的不足，并根据文献［16］，提出基于时间分组的GBFT算法，该算法主要从以下几个方面进行了优化。

1）根据节点之间的通信时间分组分层进行共识。

GBFT算法的实现通过分组、选举、以及分层进行共识。基于最短通信时间，将区块链所有副本节点进行分组，每个组都有一个组长节点。首先各个组分别在组内进行三阶段的共识，组内共识依然严格遵循3f+1的原则，当组内各个节点收到的来自同一组不同节点的消息数为2f+1，即可进入下一阶段。在组内共识完成后，各组组长节点根据收到的消息执行全局共识，全局共识的执行过程和组内共识基本一致，最终由率先收到满足共识条件的组长节点更新区块链。

GBFT算法的改进主要是通过减少节点之间的消息数来进行改进，组内共识与全局共识依然遵循3f+1的容错模型，在效率提升的同时，也保证了安全性。

2）动态感知节点的加入和离开，资源利用最大化。

通过节点探测可以实时根据在线节点数目，调整分组的组数和组员数量。为每个节点设立的评分表可以动态删除共识表现差的节点。

2 GBFT算法的设计与实现

2.1 算法定义

1）GBFT算法分为组内共识与全局组长节点之间的共识，令组Gj中最大能容忍恶意节点的数量为f1，令全局组长节点中最大能容忍恶意节点的数量为f2，wj表示组Gj的组员个数，G表示所有组长节点的数目，则有：

2）根据视图编号v、当前区块高度h以及参与共识的节点总数n，可计算出主节点P，即：

2.2 分组

2.2.1 最优分组

只考虑平均时延的情况下，使用共识过程中的交互消息数计算出最优分组。

主节点发起提案ConsensusProposal发送消息数：

组内准备GroupedPrepare与组内确认Grouped-Commit发送消息数：

wj表示组Gj的组员个数，G为组数。

全局共识GlobalPrepare与GlobalCommit阶段共发送消息数：

由式（4）、（5）、（6）相加整理得到：

s为方差，由式（7）可看出，当s=0时，即平均分组时，MGBFT可以得到最小值。所以得到：

式（8）两边同时对G求导得到：

由式（9）可知，当n与G满足=0时，MGBFT最小，即所发送的消息数最少。

2.2.2 节点探测阶段

假设在整个区块链网络最初启动时，全网节点都处于孤立节点状态。首先给区块链网络内所有在线的参与共识的副本节点编号，用｛1，2，3…n｝表示各个副本节点的ID，参与共识算法的记账代表节点从ID号最小的节点开始，向比自己ID号大的节点发送探测消息＜DET ECT，status，self，t1＞，sel f包含节点自身信息，包括IP地址等信息，st at us字段有两个不同的状态，1表示请求计算通信时间的信息，2表示对请求信息的响应。t1为发送消息时区块链网络上的时间。其余共识节点在收到来自Ri的探测消息后，以区块链网络时间为标准，记录收到消息的时间t2，计算Ri与Rj之间的通信时间Tij=t2-t1，之后回复消息给相应的共识节点Ri，消 息 格 式 为＜D ET ECT-REP LY，status，self，Tij，t1＞，此时status置为2，表示对收到的消息进行回复。同样的Ri也会根据来自Rj的探测回复消息计算出Ti'j=t2-t1，Ri根据自己计算出的与来自Ri计算的Tij计算Ri与Rj平均通信时间=(Ti'j+Tij)/2，并将计算出来的记录在由共识节点组成的邻接表中。

等待节点Ri完成自己的邻接表后，向Ri之前的i-1个节点以及下一个节点Ri+1发送消息＜C OM M U N IC AT IO N-T IM E，sel f，sch ed ule＞，schedule表示由Ri更新后的通信时间邻接表，前i-1个已经完成节点探测的节点根据后续节点发送的消息，更新各自的邻接表，下一个节点Ri+1除了保存由上一个节点Ri发送的邻接表，还要向比自己ID号小的节点发送探测消息，也就是重复Ri节点的操作，直到节点Rn-1完成探测并将更新后的邻接表广播，则区块链网络内已经建立一个由各个节点组成的通信时间表。

算法中，为每个节点设置评分，初始评分设置为0分。

2.2.3 平均时延估计

各个共识节点Ri根据邻接表的值，计算出平均通信时延。平均时延的估计，是为了在后续分组中，将分散的节点分为多个通信时间基本一致的组。根据计算出的平均时延，各个节点分别统计在平均时延以内的节点编号数量di、节点编号Ri和通信时间，并根据通信时间升序。

2.2.4 分组形成阶段

根据公式计算出的主节点P在给定的共识时间间隔Δtc，发起一轮新的共识。由主节点启动快速分组协议，按照以下五个步骤进行分组。

步骤1：根据全网共识节点的数目计算出最优分组的组数G和最佳组员人数W，G和W的值由上一节介绍的最优分组中式（6）决定。

步骤2：凡是满足di≥W的节点为拟组长节点（拟组长节点是尚未组建成功的节点，若成功组建则成为组长节点），各个拟组长节点开始根据邻接表选取组员，将选取的节点添加到分组向量表chosen中，向选择的组员节点发送消息＜Q UI C KG R OU P，sel f，fl ag，ID＞σi，self包含节点自身信息，包括IP地址，节点编号等，fla g置1表示组长节点。选取组员满足以下几个规则。

规则1：di最小的拟组长节点Ri为第一组G1的组长节点首先选取组员，若多个节点的di相同，则由ID号最小的节点优先分组。

规则2：Ri将通信时间在以内的前W-1个的节点选为组员，被选取的节点不再参与下一轮的选取。

规则3：若共识节点Ri的邻接表里在平均通讯时延以内的节点不足W-1个，则依次顺延至下一个拟组长节点。

规则4：若根据规则3遍历整个拟组长节点，仍不能组建组员通信时间在以内且人数为W的组，则Ri根据邻接表选取通信时间为前W-1个节点作为组员。

步骤3：组员节点收到QUICK-GROUP后，解密验证，看到组长节点发送的消息fla g的值为1，表示组长节点在选举组员，立即根据self的值作出回复，向组长节点回复消息＜GROUPRE P L Y，self，flag，ID＞σi，fl ag置0表示为非组长节点。

分组的最终结果是形成以组长节点为中心的多个圆簇，每个组长节点负责维护组内成员。

图2 分组形成过程

2.2.5 重新分组

每次共识的发起都有一定的时间间隔，共识的时间间隔根据区块链网络内的交易数据来决定，但并不是每次共识都会发起一次分组协议。重新分组主要考虑以下几个方面。

1）拜占庭节点增多

每个组设立一个拜占庭区，通过组内共识，组内每个节点都可以知道哪些节点为拜占庭节点，将拜占庭节点添加至拜占庭区，当某一组的拜占庭区的节点数目多于f1，则认为这个组宕机，这个组的所有节点不再参与到组内共识与全局共识当中，组内非拜占庭节点向区块链网络内其他节点广播宕机消息＜DOWN-ME S S AG E，sel f＞σi，其余节点根据监测到的消息将宕机的整个组的组员添加至拜占庭区，当拜占庭区的组数大于f2时，则需重新进行分组。

如果某一个组Gj的组长节点为拜占庭节点，而Gj组的拜占庭区的节点数目少于f1，Gj组仍可以继续参与共识，此时由除拜占庭节点外评分最高的节点担任组长节点，若分数相同，则取ID号最小的节点担任，并向其余组长节点广播变更消息＜GROUP-C HA N G E，self，chosen＞σi，这里chosen仅为Gj组的组员向量表。

2）节点的加入

当有新的节点加入共识，新加入节点需要向全网发送探测消息，在收到新节点的探测消息后向新节点发送通信时间邻接表sch edule，新加入节点根据节点探测阶段所描述的方法计算平均通信时延以及更新邻接表schedule，并将新的邻接表广播至全网。每次当有新的节点加入，则由主节点发起新一轮的快速分组协议。

2.3 共识

我们定义主节点作为一次共识的发起者，如同比特币网络中，通过调节难度控制出块时间为10min，我们可以根据区块链网络的交易数量，调控主节点发起一次共识的时间间隔。在整个区块链网络中，所有的共识节点都有可能是最终的记账节点，所以不仅参与共识也要保存区块链数据。当收到交易数据，所有共识节点验证交易合法性，将通过验证的交易数据添加至自己的内存中并根据前一区块的哈希索引、版本号、区块高度等信息构造一个候选区块，并广播至其他共识节点，不合法则直接丢弃，这确保了只有有效的交易才能在区块链网络中传播。

1）主节点P向所有副本节点发起共识提案，消息格式为＜C O NSE N S US-P RO P OSA L，v，n，h，d，self＞σi，b l ock，t1＞，v为当前视图编号，n为在当前视图编号下主节点分配的序列号，h为当前区块的高度，block为请求的区块信息，d为block的摘要，t1为时间戳，目的是为了计算通信时延，不断更新邻接表。

其余的副本节点收到来自P的共识提案后，验证签名、检查提案、h的值、n的值是否在水线范围内。若为真，则进入组内共识阶段。若发现提案为假或在超过共识间隔时间后仍未发起共识提案，备份节点怀疑主节点失效，则进行视图变更。详细的变更细节在文章的后续做出介绍。

5）与全局准备阶段一致，组长节点间互发确认消 息＜GL OB A L-C O M MIT，v，n，h，d，self，t1＞σi，当组长节点中的任意一个在收到来自2f2+1个其他组长的相同确认消息后，即认为共识达成，可以发布来自主节点提案的区块block。

6）其余节点根据最新的区块，将自己内存中的与区块block中相同的交易删除，同时开始构造新的区块，准备下一轮的共识。

算法中，产生区块的节点评分score加1分，若主节点被副本节点怀疑，引发视图变更，若变更成功，则主节点score减2分，该备份节点score加1分。

整个算法的共识过成如图3所示。

图3 GBFT算法流程

2.3.1 邻接表更新

邻接表建立之后并不是一成不变的，除了节点的加入和退出需要变更邻接表外，组内共识和全局共识动态更新部分的邻接表的通信时间。

组内共识以及全局共识的消息都包含时间戳，根据节点探测一节介绍的通信时间的计算方法，每次收到共识阶段内的消息后自动计算传播时间并记录，待一轮共识完成后，将所有收集到的消息的通信时间累加并取平均值，将计算出的值填入邻接表的对应位置。

2.3.2 组长节点的轮换

我们为每个共识节点都设置了评分score，在GBFT算法中，根据评分建立一个忠诚度表1。

表1 忠诚度计算方法

每个节点计算出各自的忠诚度c：

c的计算是综合了score与担任组长次数t的结果，平衡每个节点成为组长节点的几率，避免分数高的节点长期担任组长。α与β为调节系数。c的值最高的成为下一轮次的组长节点。

2.3.3 视图变更

当备份节点怀疑主节点或者在共识间隔时间Δtc后仍未发起新的共识，则由怀疑主节点的备份节点或随机选取的备份节点发起视图变更消息，具体的变更流程如下。

1）令新的视图vnew=vold+1，假设由备份节点Ri向全网发送视图变更消息＜V IEW-C H A N GE，vold，vnew，h，Ri＞σi。

2）其余备份节点收到视图变更消息后，验证消息的签名、vold以及h的值是否为真，若为真，则拒绝主节点的共识提案并向全网广播视图变更确认 消 息＜V IE W-CH A N GE-C ON FIR M，vold，vnew，h＞σi。

3）任何一个节点如果收到来自其他（2n-1）/3条图变更确认消息后，视图变更得到确认，新的视图编号变为vnew。新的主节点开始下一轮的共识提案。

3 实验模拟与分析

3.1 实验设计

本算法的基础是分布式系统，即需要在多个节点下运行，为模拟出大量的分布式节点的计算，有如下设计。

1）共识节点：以进程来模拟共识节点，共识节点的端口号分布在10001～20000之间，共识节点是整个系统的关键，负责交易和区块的共识确认。

2）交易产生节点：以进程来模拟交易节点，一个进程一个交易节点，每个进程拥有不同的的端口号，端口号分布在20001～30000之间，交易节点主要负责交易数据的模拟，以最快的速度生产交易信息并发送给共识节点。

3）由于共识节点是在同一局域网下一台或多台电脑上进行模拟，为了更好地验证算法的有效性，用随机函数事先生成一个n×n的对称矩阵模拟通信延迟时间。

4）整个区块链系统采用Python语言编写，搭建了Linux操作系统环境，用脚本语言开启多个进程。本实验以PBFT算法作为对照，分别对99个、216个、336个、420个、512个节点进行改进共识算法GBFT的时间测试。实验中，各个进程依次开启，开始执行GBFT算法。针对不同数量的共识节点，我们各测试10次，取10次的平均值来作为最后的结果。

3.2 运行效率分析

GBFT设计的目的就是为了提高区块链系统运行的效率。以PBFT算法作为对照，分别对99个、130个、176个、216个、273个、350个节点进行PBFT算法、GBFT算法的时间测试。测试结果如图4所示。

图4 不同节点数PBFT与GBFT共识时间折线图

从图4知随着共识体系中节点数量不断的增加，GBFT的效率提升越明显。

3.3 吞吐量

区块链应用中对于吞吐量的定义是：

其中，Δt为交易发出到区块确认的时间，即出块时间，transacti on为Δt时间段内打包进区块的交易数。

实验对PBFT算法以及GBFT算法，统计1000条交易所花费的共识时间，根据式（11），计算出吞吐量，如图5是PBFT算法与GBFT算法的吞吐量折线图。

图5 PBFT与GBFT吞吐量折线图

从吞吐量折线图可知，PBFT算法与GBFT算法的吞吐量与参与共识的节点数成反比，节点越多，吞吐量越低。但在相同节点数量的情况下GBFT算法的吞吐量是远高于PBFT算法的。

3.4 安全性分析

1）主节点的选取根据视图编号和区块高度计算所得，而组长节点的选取根据最小ID号，两者的选取都具有随机性和公平性。

2）由主节点P发起的快速分组并不是说全网的副本节点全部由主节点安排分组，而是根据节点探测阶段所统计的通信时间以及随机ID号进行分组，这个组要获得最大利益就会根据邻接表选择通信时间最短的成为组员，这样不仅可以防止主节点成为拜占庭节点后安排最差的分组，而且可以提高节点间的通信时间。

3）GBFT共识算法的实质是将PBFT算法分解为组内共识与全局共识两个阶段，共识协议和试图更换的核心并没有改变，依然严格遵循3f+1的模型。

4）每个组设立拜占庭区，且每个节点都独立监听其余节点的状态，根据最大容仍失效节点的数目动态调整算法，当拜占庭节点数大于f个，则触发重新分组协议。

5）信用评分协议与组长更换协议使得各个节点成为组长节点的机会均等，满足区块链去中心以及节点间对等的特性。

4 结语

针对区块链共识算法中的实用拜占庭容错算法表现出的由于大量的消息广播造成的通信资源浪费和效率低下问题，提出基于通信时间分组分层算法。在分组形成前，采用节点探测获知共识节点的“地理位置”——构建一个通信时间对称矩阵，根据通信时间对称矩阵将节点分成多个以组长节点为中心，平均通信时延为半径的圆。在组保持阶段，根据节点的行为进行信用评分与组长更换，使得所有节点成为组长节点的概率尽可能均等。整个共识算法可以通过节点探测动态感知新加入节点，拜占庭区的设立感知失效节点，从而确定是自适应调整共识还是调整分组结构。仿真表明，本文算法很好地解决了PBFT算大的通信资源消耗和效率低下问题。