DS-PBFT：一种基于距离的面向区块链的共识算法

朱 海，金 瑜

1(武汉科技大学 计算机科学与技术学院，武汉 430065) 2(湖北省智能信息处理与实时工业系统重点实验室，武汉 430065)

1 引 言

自中本聪提出了比特币[1]后，区块链的概念就诞生了.由于区块链具有去中心化、防篡改和可追溯等特征[2]，近几年区块链的相关技术成为了研究热点.在此基础上，区块链的应用场景已经从加密货币[3]、数字资产[4]扩展到能源[5]、医疗保健[6]、教育[7]、供应链[8]等非金融行业的领域.

共识算法作为区块链的核心技术，其功能就是保证系统的一致性、安全以及稳定的运行[9].区块链分为公有链、联盟链和私有链[10].工作量证明(Proof of Work，PoW)、权益证明[11](Proof of Stake，PoS)以及授权股份证明[12](Delegated Proof of Stake，DPoS)是公有链主要的共识算法；实用拜占庭容错协议[13](Practical Byzantine Fault Tolerance，PBFT)是私有链、联盟链主要的共识算法.PBFT共识算法有效的解决了拜占庭将军问题[14]，使其可以实际应用于吞吐量较小的分布式系统.但该算法为了追求完全的去中心化，让系统中除客户端节点以外的所有节点都参与到共识过程中，并且其算法的时间复杂度为O(N2)，故其只能应用于节点数量较少的系统.目前，有很多对PBFT算法进行改进的一类方案，它们通过各种措施(比如通过VRF、投票等等)对系统中的节点进行筛选，从而单纯地通过减小共识节点的规模来提升PBFT算法的效率，但是其通信代价和共识时延仍然无法达到现实应用场景的要求.

本文基于PBFT算法的思想，提出了一种基于距离的面向区块链的共识算法.通过Grouping算法，将距离较近的节点分成一组进行共识，在减小共识节点规模的基础上缩短共识节点间的通信距离，从而减少共识时延.同时结合speculation技术[15]，降低算法的时间复杂度，从而减少系统的通信代价，使得DS-PBFT算法能够适用于更广泛的应用场景中.

2 相关工作

PBFT算法的共识过程是在所有共识节点的共同参与下完成的，使得系统中的共识节点数量增多时，算法的通信次数与共识时延成倍增加.因此，现阶段有许多的方案都是通过减少共识节点的规模来提升PBFT算法的效率.

以上共识算法虽然从各个角度减少了参与共识节点的规模，与传统的PBFT相比，确实在一定程度上提升了共识效率，但它们筛选共识节点都不是基于距离，并且不能从根本上克服传统PBFT的缺点，因此共识时延和通信代价都还是比较大的.为了简单，本文将这类算法统一称为ND-PBFT，即在n>m的条件下，从n个节点里面筛选出m个节点进行PBFT共识的算法.

3 DS-PBFT共识算法

3.1 相关定义

为了更加方便的对DS-PBFT共识算法进行描述，对相关概念进行如下定义：

定义1.初始节点集合

初始时系统提供的节点集合，用字母U表示，包含的节点数量较少，方便以较小的代价求解节点间的距离矩阵.使用U={n1，n2，…，nt}来表示拥有t个节点的初始节点集合，其中ni表示第i个节点.另外，初始集合中的节点是在一个固定周期内根据地理位置均匀地挑选出来的.

定义2.距离矩阵

距离矩阵是一个(t×t)的矩阵，用字母D表示，是由初始节点集合中任意两节点之间的最短距离而形成的矩阵.其中元素dij表示在某一时刻节点i到节点j的最短距离.

定义3.距离平均值

距离平均值指的是一个节点到一个节点集合中所有节点的距离的平均值，用字母md表示.例如，md(i，U1)表示节点i到节点集合U1中所有节点的距离的平均值，用公式表示如下：

(1)

定义4.距离标准差

距离标准差指的是一个节点到一个节点集合中所有节点的距离的标准差，用字母sd表示.例如，sd(i，U1)表示节点i到节点集合U1中所有节点的距离的标准差.用公式表示如下：

(2)

定义5.节点

节点是区块链网络中的基本单元，其中包含index(序号)、sd(距离标准差)、md(距离平均值)、primary(该节点所在小组的主节点)、group(该节点所在小组序号)这些属性.

定义6.初始分组

初始分组是由初始节点集合通过Grouping算法产生的若干个小组，用字母G表示.每个小组中各自包含着距离相对较近的节点.令G={g1，g2，…，gm}表示m个小组，其中gi表示第i个小组.

定义7.主节点集合

主节点集合是由各个小组中选出的主节点所构成的节点集合，用pList表示.令pList={p1，p2，…，pm}表示由m个主节点构成的主节点集合，其中pi为第i个小组的主节点.

定义8.主节点候补集合

主节点候补集合是由各个小组中的候补集合构成的总的集合，用Alternate表示.当某个小组中的主节点发生故障时，该小组的候补集合中的节点会按照顺序进行替换.令Alternate={a1，a2，…，am}表示m个小组的候补集合，其中ai表示第i个小组的候补集合.

定义9.speculation共识阶段

当不存在拜占庭节点时，使用speculation技术进行共识的阶段，并且在共识执行的过程中首先进行.

定义10.group共识阶段

当存在拜占庭节点时即speculation共识阶段失败后，请求节点所在小组进行第一次PBFT共识的阶段.

定义11.primary共识阶段

当group共识阶段完成后，在主节点集合中进行第2次PBFT共识的阶段.

3.2 系统框架

DS-PBFT共识算法的框架如图1所示，系统中主要包含普通节点和共识节点两个实体.普通节点不参与共识，共识节点才参与到具体的共识过程，比如图1所示组1和所有主节点构成了一轮共识中的共识节点.DS-PBFT中参与每一轮共识的共识节点都是动态变化的，是由某个小组集合加上主节点集合构成的.共识节点变化的那部分是参与共识的小组集合，但是对于所有主节点来说，每一轮共识都需要参与，所以它们永远都是共识节点.因此对于具体某一轮共识中是由哪个小组中的节点加上所有主节点构成共识节点进行共识，可以按照轮询的方式进行确定.具体为系统在分成的若干个小组中按照小组序号进行轮询，若轮询到某个小组时该小组内存在请求，则该小组内的节点加上所有主节点构成共识节点进行共识，直到处理完从上次轮循完该小组开始到现在刚轮循到该小组时这段时间内产生的所有请求后，自动跳过该小组，轮询下一个小组；若轮询到某个小组时该小组内不存在请求，则直接跳过该小组轮询下一个小组，直到找到存在请求的小组，再加上所有主节点构成共识节点进行共识.下面通过图1介绍一个周期内DS-PBFT共识算法的大致步骤.

图1 系统框架Fig.1 System framework

a)通过Grouping算法首先将系统提供的初始节点集合中的节点分成若干个小组.

b)在产生的各个小组中分别通过主节点选取、轮换算法获得各个小组的主节点以及候补集合，接着再将各个主节点和候补集合分别构成主节点集合pList和主节点候补集合Alternate.

c)当系统中存在请求需要处理时，共识节点首先进行speculation共识.若speculation共识成功，则整个共识过程成功结束；若speculation共识失败，则进入到group共识阶段.

d)若speculation共识失败，请求节点所在小组以小组为单位进行第1次PBFT共识即group共识阶段.共识成功过后进入到primary共识阶段.

e)若group共识成功，主节点集合中进行第2次PBFT共识即primary共识阶段，共识成功后整个共识过程成功结束.

其中上述a)、b)这两个步骤属于初始化阶段，为后面的共识执行阶段做准备工作，c)、d)、e)3个步骤为共识执行阶段，进行实际的共识流程.另外在实际应用中，由于DS-PBFT在存在拜占庭节点(宕机或发生其它故障导致不能正常工作的节点)时是基于PBFT的，因此各个小组以及主节点集合需要满足n>3f的条件才能保证共识结果的正确性，其中n为小组或者主节点集合中节点的数量，f为小组或者主节点集合中能够容忍的拜占庭节点的数量.

3.3 DS-PBFT关键算法

3.3.1 初始化阶段

1)Grouping算法

在实际的网络中，节点之间距离的远近会影响节点间信息传递的时间，距离是影响数据传输延迟的关键因素.并且在实际生活中大部分节点的位置不会发生很大的变动，因此在某一个固定周期内，可以近似的将某一时刻节点之间的距离看作一个固定周期内节点之间的距离.基于此，本文设计一种Grouping算法，将系统中在某一固定周期内距离较近的节点分为一组，并且允许节点进行细微的位置变动(细微的位置变动对共识时延带来的影响可以忽略不记)，经过主节点选取后最终形成多个主节点领导下的多个小组，从而使算法在距离因素上减少节点间的信息传输时延.

为了能够以较低的计算代价将节点进行分组，系统初始时需要提供一个一定数量的初始节点集合U，并首先将初始集合中的节点进行分组.对于未分组或未来新加入区块链网络的节点，再根据初始分组G的信息判断加入哪个小组，这是Grouping算法的基本思想.另外，之所以对节点进行分组之前需要系统提供一个节点数量较少的初始节点集合，那是因为计算大量节点的距离矩阵所需要的代价是巨大的，而初始集合中的节点数量并不多，计算初始集合中节点的距离矩阵的代价相对较小，因此首先通过对初始集合中的节点进行分组并在此基础上对所有节点进行分组就成为了合理的选择.

另外，由于后续新节点的分配依赖于初始分组的信息，所以初始分组的结果对后面的节点分配起着关键性的作用，影响着最终的分组结果.所以，对初始节点集合中节点的分组应当足够的准确，防止误差的积累，导致误差越来越大.以下是Grouping算法的伪代码.

算法1.Grouping

Grouping algorithm

输入：Initial node collectionU

Distance matrixD

Number of groupsm

输出：Initial groupsG

1. initialize.G←{g1，g2，…，gm}

2. foriin range(1，m)

3.c←random(U)

4.gi.add(c)

5. avg←(∑j∈U，j≠cdcj)/(|U|-1)

6. forj∈U&&j≠c

7. ifdcj

8.gi.add(j)

9.U←U-{j}

10.U←U-{c}

11. whileU≠Ø&&n∈U

12. foriin range(1，m)&& !enough(i)

13.k，n←min(md(n，gi)，sd(n，gi))

14.gk.add(n)

15. returnG

Grouping算法在计算每一个分组时，首先会从初始节点集合U中随机地抽取一个节点，并将此节点作为当前的中心节点，使分布在中心节点一定阈值半径内的若干节点成为一个小组，包括中心节点.然后从初始集合U中移除已经分配好的节点，重复以上过程直到完成m个小组的分配.阈值半径avg是当前中心节点到U中其他所有节点距离的平均值.将节点映射到一个二维平面上，Grouping算法相当于用m个圆去覆盖一个平面节点集，并且这m个圆互不相交.由于这些圆之间互不相交，因此在初始集合中可能还会存在少量节点没有被包含.对于这些没有被包含即没有成功分组的节点，需要逐一地计算其到m个小组集合的距离平均值，然后根据计算出的最小的距离平均值将节点加入到对应的小组中，如果存在该节点到若干小组的最小距离平均值有多个的情况，就接着计算该节点到这些小组集合的距离标准差，最后根据最小的距离标准差将节点分配到对应的小组中.其中enough(i)函数的作用是当第i组的人数已经充分足够了返回true，否则返回false，确保每个小组中的节点数量满足n>3f的条件.

在生成初始分组后，为了提高系统的动态性，DS-PBFT共识算法允许节点动态的加入或退出小组.由于参与到一轮共识中的共识节点是请求节点所在小组加上主节点集合中的节点，其它小组处于空闲期.因此为了防止组内成员节点的变化而影响共识，小组内节点的动态加入或退出是在当前小组处于空闲时期时进行的，即在当前小组没有参与到某轮共识期间.对于新加入到区块链中的节点，通过Grouping算法分配到某个具体小组后，系统会将该节点信息在该小组处于空闲时期记录到该小组集合中.对于想要退出当前小组的节点(非主节点)，首先需要向系统提出申请，申请通过后，系统会将该节点信息在当前小组处于空闲时期时从相关节点集合中删除.另外如果该节点是候补节点，系统会重新按照生成候补集合的算法补充候补节点的数量.退出的节点如果想要再次加入某个小组时，需要重新根据其距离信息以及Grouping算法对其进行分配.最后对于小组中的主节点想要退出当前小组，必须首先向系统申请降级为非主节点，由系统根据候补集合中获得有资格的候补节点替换当前主节点后，再在该节点处于空闲时期时将其有关信息在相关集合中进行删除，最后更新其它小组的候补集合.

另外，DS-PBFT每隔一定周期需要对节点重新进行分组，具体周期时长可以根据实际适当的进行设置.之所以要每隔一定周期对节点重新进行分组，是因为在实际过程中，经过较长的一段时间后，各个小组内小部分节点的位置可能会发生很大的变动，导致组内节点之间的距离会发生很大的改变，从而较大地影响共识时延.在重新分组时，系统会根据地理位置均匀地挑选出适量节点重构初始节点集合和距离矩阵.最后通过Grouping算法对所有节点重新进行分组，重新构建小组集合、主节点集合以及候补集合.而对于在具体的某个周期内，系统生成的小组集合、主节点集合以及候补节点集合就是固定的，只会由于主节点替换、节点动态加入、退出这些操作才会带来细微变化.

2)主节点选取算法

主节点选取算法的目的同样是为了在各个小组中选出若干个距离较近的主节点，从而减少primary共识阶段的消息传输时延.下面详细描述主节点选取算法的步骤.

对于系统中通过Grouping算法形成的m个初始分组{g1，g2，…，gm}，首先在g1组中计算出各个节点到{g2，g3，…，gm}集合中的距离平均值，将距离平均值最小的节点作为主节点加入到主节点集合pList中，接着在g2内计算各个节点到pList集合中的距离平均值，将距离平均值最小的节点加入到pList中.对于后续其它小组中选取主节点的步骤和在g2内一样，直到主节点集合中存在m个主节点才结束选举过程.当以上选举过程中存在多个最小平均值的情况时，同样是接着比较距离标准差，从而获得唯一的主节点加入到主节点集合中.主节点选取算法的伪代码如下.

算法2.Primary nodes selection

Primary nodes selection algorithm

输入：Initial groupsG

Distance matrixD

输出：Collection of primary nodespList

1.pList←null

2.node←getMin(g1，G-g1，D)

3.pList.add(node)

4. foriin range(2，G.size())

5.node←getMin(gi，pList，D)

6.pList.add(node)

7. returnpList

3)主节点轮换算法

主节点轮换算法分成两部分，一个是生成主节点候补集合，另一个是轮换拜占庭主节点.用于当小组中的主节点发生故障或者宕机时进行轮换，从而保持系统的正常工作.下面详细地描述主节点轮换算法的步骤.

a)生成主节点候补集合

对于系统中通过Grouping算法在初始节点集合中形成的m个初始分组{g1，g2，…，gm}，假设在g1中有q个节点，在g1中计算各个节点到pList中的距离平均值(不包括g1中的当前主节点)，按照从小到大的顺序将节点排列为{n1，n2，…，nq-1}.如果存在距离平均值相同的情况，则将节点按照距离标准差从小到大的顺序进行排列，最终获得的由(q-1)个节点构成的序列即为该小组的候补集合.其它小组按照g1中同样的方式进行，最终系统会获得m个候补集合.最后，系统会将各个小组中产生的候补集合整合成主节点候补集合.另外，各个小组中候补集合的节点数是固定的并且可能各不相同，依赖于初始分组时的节点数量，等于初始分组时的节点数量减1.

b)轮换拜占庭主节点

假设在g1内检测到主节点是拜占庭节点时，会按照该小组候补集合中的顺序选择第一个候补节点(距离平均值最小并且距离标准差最小)轮换当前主节点，但前提是这个候补节点不是宕机节点，如果是宕机节点就接着按照顺序往下找候补节点.被轮换的主节点将从主节点集合及其所属的小组集合中移除.成为了主节点的候补节点将从候补集合中移除并将其加入到主节点集合中，使其他的候补节点能够拥有机会成为主节点，否则会导致垄断的问题.另外在该小组内，为了保证候补集合中始终有(q-1)个候补节点，当后续新加入到该小组的节点达到一定数量时，系统会对新加入的节点同样通过计算距离平均值以及距离标准差的方式按照从小到大的顺序将新节点插入到当前小组的候补集合中.最后由于各个小组的候补节点是依赖于其它小组的主节点，当某个小组的主节点发生替换时，应当及时更新其它各个小组的候补节点集合即重新按照生成候补集合的算法重构候补集合，保证从当前候补集合中挑选出的主节点总是距离其它主节点是较近的.

算法3.Rotation of primary node

Rotation of primary node algorithm

输入：Initial groupsG

Distance matrixD

Collection of new nodesnewNodes

输出：Primary nodepri，Alternate set of primary nodesAlternate

Alternate collection of primary nodeAlternate

1. initialize.Alternate←{a1，a2，…，am}

2. foriin range(1，G.size())

3. forningi&&nnot inpList

4.n.sd←sd(n，pList-n.primary)

5.n.md←md(n，pList-n.primary)

6.ai.add(n)

7.ai←sorted(ai)

8.pNode←System.supervise()

9.index←pNode.group

10.pri←getFirst(aindex)

11.pList.add(pri)

12.aindex，pList←remove(aindex，pList，pri，pNode)

13.Alternate←update(Alternate-aindex)

14. if(aindex).size()<(aindex).size()-1

15. (aindex).add(newNodes)

16. returnpri，Alternate

3.3.2 共识执行阶段

在共识执行阶段，共识算法的运行步骤存在两种情况.下面根据系统中是否存在拜占庭节点对共识过程进行详细描述，DS-PBFT共识算法的共识流程如图2所示.

图2 GS-PBFT共识流程Fig.2 DS-PBFT consensus process

1.若共识节点中不存在拜占庭节点

1)节点发送请求消息给其所在小组的主节点.

2)主节点收到节点请求后首先校验请求，验证通过后为请求分配序号，然后将排序好的请求消息广播给其它所有共识节点.

3)节点在收到排序好的请求消息后，执行该请求，最后向发出请求的节点反馈结果.如果该节点收到其他所有节点反馈的消息并且全部相同，则共识成功.如果该节点没有收到来自其它所有节点的反馈消息，或者反馈消息存在不同的情况，则speculation共识失败.说明共识节点中存在拜占庭节点，转到下面的共识流程.

2.若共识节点中存在拜占庭节点

1)节点将请求消息发送给其所在小组的主节点.

2)主节点收到请求后，首先校验其正确性，校验成功后为请求分配序号，接着生成预准备消息广播给其所在小组内的其他节点开始进行group共识即第1次PBFT共识.

3)group共识成功后，该小组的主节点会将生成的预准备消息广播给其它主节点.主节点们在收到消息后会进行primary共识即第2次PBFT共识，在primary共识过程中各个主节点会将各自的数字签名广播给其他主节点并收集来自其他主节点的数字签名.

4)primary共识成功后，各个主节点将收集到的数字签名集合附带请求生成打包消息广播给其所在小组的其他节点，通知组内其他节点共识成功.打包消息的数据结构如图3所示，其中Signaturei表示主节点i的数字签名.

图3 打包消息的数据结构Fig.3 Data structure of packaged message

5)各个小组的节点在收到来自其主节点的打包消息后，为了保证请求通过了primary共识，会验证数字签名集合.验证通过后执行该请求内容，然后各节点更新本地区块链账本，保证数据的一致性.

DS-PBFT共识算法伪代码如下：

算法4.Consensus

Consensus algorithm

输入：Initial node collectionU

Requestnodeclient

Initial groupsG

Collection of primary nodespList

输出：Consensus resultsres

1.sendReq(client，client.primary，req)

2.res←false

3.res←startSC(gclient.group+pList)

4. ifresis false

5.res←startGC(gclient.group)&&startPC(pList)

6. ifresis true

7.pm←package(req)

8. forpinpList

9.broadcast(pNode，gpNode.group，pm)

10. fornodeingpNode.group&&verify(pm)

11.execute(req)

12. returnres

4 分 析

本文针对DS-PBFT算法、PBFT算法以及ND-PBFT算法，进行了理论分析以及实验分析，理论上分析了两个指标：节点间的平均延迟、通信次数，它们是影响共识时延和通信代价的因素.接下来从实验的角度分析了单次共识的共识时延.

4.1 理论分析

4.1.1 节点间的平均延迟

对于DS-PBFT共识算法，在某个小组内，假设已知节点A、B到另一个节点C的距离，那么根据三角不等式关系可以说明节点A、B之间的距离要小于节点A、B到节点C的距离之和.换句话说，如果节点A、B都是节点C的相邻节点，那么肯定存在一个值，A、B之间的距离小于它.用数学公式表示如下：

|AC|<ε，|BC|<ε⟹|AB|<|AC|+|BC|<2ε

(3)

其中ε为小组内两个节点之间距离的上限值也就是前面说的阈值半径.对于在以节点O为中心节点的小组里，用集合{An}表示在小组内除O以外的节点，根据距离矩阵可以计算出各个节点之间距离的总和Distances，这里的距离指的是两个节点之间的最短距离，最短距离可以通过Dijkstra算法求得.根据公式(3)可以推导出以下关系：

(4)

结合公式(3)和公式(4)，便可以推导出各个小组(包括主节点集合)内任意两节点之间的平均距离满足公式(5).

(5)

对于PBFT共识算法，可以将所有共识节点当成一个小组，即可以看成所有节点分布在一个圆内，取阈值半径等于任意两节点之间距离的最大值的一半.用同样的方式也可以推导出系统中任意两节点之间的平均距离，唯一的不同在于PBFT算法的阈值半径以及节点数肯定大于DS-PBFT算法的，将它们反映到平面上也就是一个大圆包含若干个小圆，大圆的半径肯定是大于包含其中的小圆的半径.因此，DS-PBFT共识算法任意两节点之间的平均距离肯定是小于传统PBFT共识算法的.

对于ND-PBFT共识算法，假设DS-PBFT算法和ND-PBFT算法两者参与到共识过程中的节点数是相同的.按照对PBFT算法同样的分析方式也可以推导出DS-PBFT共识算法任意两节点之间的平均距离是小于ND-PBFT共识算法的.

由此可知，在DS-PBFT中任意两节点之间的平均距离都小于PBFT和ND-PBFT的情况下，DS-PBFT算法中任意两节点的平均延迟肯定更小.由小及大，在消息传输速率相同的情况下，DS-PBFT共识算法的总的通信时延会更低.

4.1.2 通信次数

1)PBFT共识算法的通信次数

假设系统中有n(n>=16)个节点，下面按照PBFT共识算法的流程计算单次共识所需要的通信次数.

预准备阶段，主节点将预准备消息发送给其他所有节点，需要进行(n-1)次通信；准备阶段，各个节点需要发送准备消息给其他节点，需要进行(n-1)(n-1)次通信；确认阶段，各个节点生成确认消息并广播给其他节点，又需要n(n-1)次通信.因此完成一次PBFT共识，总共需要的通信次数如下：

N1=n-1+(n-1)(n-1)+n(n-1)=2n(n-1))

(6)

2)DS-PBFT共识算法的通信次数

(7)

(8)

3)ND-PBFT共识算法的通信次数

(9)

显然，ND-PBFT共识算法的通信次数要比PBFT少，因为ND-PBFT只是在PBFT的基础上减少了参与共识的节点数量.下面比较ND-PBFT算法和DS-PBFT算法的通信次数.

根据公式(7)、公式(8)可知，DS-PBFT算法当系统中不存在拜占庭节点时的通信次数要远远少于当系统中存在拜占庭节点时的.因此ND-PBFT算法只需要和当存在拜占庭节点时的DS-PBFT算法比较即可.于是可以推导出N4-N3满足以下关系：

(10)

由式(10)可知，即使在存在拜占庭节点的情况下，DS-PBFT共识算法的通信次数也是远远少于ND-PBFT共识算法的.并且随着系统中节点数的增加，DS-PBFT和ND-PBFT之间通信次数的差距还会越来越大.综上所述，DS-PBFT在3者之间，单次共识所需要的通信次数是最少的，即总的通信代价是最低的.

4.2 实验分析

4.2.1 实验环境

操作系统：64位Windows10；编程语言：go；编程工具：GoLand，NS2[20]，GT-ITM[21]，go1.13.4.

实验基于Transit-Stub模型[22]，通过NS2以及GT-ITM网络拓扑生成器获得一个带有权值的网络拓扑作为初始的节点集合，通过Dijkstra最短路径算法计算节点之间的距离矩阵，使用Grouping算法将节点分成了若干组.基于go语言实现了PBFT共识算法、ND-PBFT共识算法以及DS-PBFT共识算法.最后在共识时延这个方面对这3种算法进行实验分析.

4.2.2 共识时延

共识时延是指从节点发送请求到整个共识过程完成所需要的时间，公式如下所示：

Delay=Tfinish-Treq

(11)

实验1.设置自变量为节点数量，将节点固定分成4组.实验设置节点数量为16，20，24，28，32，36，40，通过增加节点数量来对比两种算法的单次共识时延.在调整节点数的同时，始终保证DS-PBFT与ND-PBFT中共识节点数量一致.最终实验结果如图4所示，其中DS-PBFT(1)和DS-PBFT(2)分别指的是DS-PBFT算法在存在拜占庭节点和不存在拜占庭节点时的两种情况.

图4 固定分组数的共识时延对比Fig.4 Consensus delay comparison of fixed number of groups

由图4可知，在分组数固定的情况下，DS-PBFT算法在两种情况下的共识时延都要远远低于另外两种算法的共识时延.随着节点数量的增加，相比另外两种算法，DS-PBFT算法的共识时延增长相对缓慢.说明DS-PBFT共识算法相对比较稳定.同样在两种情况下的DS-PBFT算法，在不存在拜占庭节点时的共识时延更低，并且更稳定.

实验2.设置自变量为小组的数量，具体设置为4，5，6，7，8，9，10，将总的节点数固定为40个并始终保证DS-PBFT与ND-PBFT中共识节点的数量一致.通过增加小组数将存在拜占庭节点时的DS-PBFT算法与另外两种算法进行对比，由于小组数量对当不存在拜占庭节点时的DS-PBFT算法没有影响，因此不需要比较.最终实验结果如图5所示.

图5 固定节点数的共识时延对比Fig.5 Consensus delay comparison of fixed number of nodes

由图5可知，在总的节点数量一定时，分组数对DS-PBFT共识算法的共识时延有一定影响，但是始终还是要远远低于另外两种算法的共识时延.并且当分组数为6的时候，DS-PBFT共识算法的共识时延相对是最低的；因此可以得出结论，当节点数量一定时，适当的分组数会使DS-PBFT算法有一个理想的共识时延.

5 总结与展望

5.1 总 结

本文为了解决PBFT算法和ND-PBFT这一类算法效率低下的问题，提出了DS-PBFT共识算法.基于Grouping算法的思想，将系统中距离较近的节点分成一组，选出各个小组中的主节点并且生成主节点候补集合，降低节点间的通信时延.同时结合speculation技术，减少算法的通信次数，从而降低算法的通信代价.最后通过理论以及实验对比分析，本文提出的DS-PBFT共识算法相对传统的PBFT以及ND-PBFT这一类算法，在共识时延、通信代价等方面有着很大的提升，提高了系统效率，更加适应于当前的区块链系统.

5.2 展 望

虽然本文提出的DS-PBFT共识算法的运行效率相比传统PBFT共识算法提升了许多，但还是存在着一些缺陷.比如，在未来的工作中可以完善奖惩机制，对系统中的拜占庭节点进行惩罚，减少系统中出现拜占庭节点的概率，从而提高系统的运行效率、稳定性以及安全性.