基于综合选举的DPoS 共识算法

王 兵，李辉灵，牛新征

（1.西南石油大学 计算机科学学院，成都 610500；2.电子科技大学 计算机科学与工程学院，成都 611731）

0 概述

区块链的提出引起了学术界与业界的广泛关注，其为集中式机构的高成本、低效率和数据存储［1］不安全性提供了解决方案［2］。区块链底层是一系列技术集成的分布式账本系统，系统中每一个区块的架构包含了交易数据［3］、父区块Hash 值［4］、Merkle 树［5］等信息。根据技术的不同从下到上分为数据层、网络层、共识层、激励层、合约层、应用层［6］，且随着技术的不断发展，区块链能够与智能合约［7］相结合，并出现了许多的Dapp应用［8-10］，为现实世界提供了从信息到价值的传递功能。

区块链中各节点能自发、诚实地遵守协议中预先设定的规则并保持全局状态一致，共识算法起着至关重要的作用。工作量证明（Proof of Work，PoW）［11-12］机制作为主流的共识算法之一，其依赖计算机算力竞争记账权，一个新的区块生成需要计算出符合条件的哈希值，但算力争夺会消耗大量资源。为减缓资源的大量消耗，研究人员提出权益证明（Proof of Stake，PoS）［13］共识算法，根据持有数字货币数量和时间来分配相应利息的制度。PoS 的进一步演变是股份授权证明（Delegate Proof of Stake，DPoS）［14］共识算法，其原理是让每一个股份节点进行投票，由此产生权利对等的101位委托人节点。随着联盟链共识机制［15］的兴起，实用拜占庭容错（Practical Byzantine Fault Tolerance，PBFT）［16］共识算法被提出，按照少数服从多数原则，经主节点提交提议至其他共识节点进行确认，当超过2/3 的节点确认后则提议通过［17］。Raft［18］可作为一种典型的联盟链共识算法，该算法包含3 种角色，分别是跟随者、候选人和领导者，这3 种角色能随着时间和条件的变化而互相转换。

本文提出一种基于综合选举的DPoS（Comprehensive Election DPoS，CE-DPoS）共识算法。该算法摒弃原DPoS 按股份投票的方式，节点之间能够根据自身意愿进行投票，在符合现实情况的同时，新节点的加入不受股份的影响，提升了节点之间的投票活跃度。DPoS 节点的通信代价主要受前置节点和后置节点的影响，而CE-DPoS 共识算法根据预设的网络信息表选取节点，以降低网络通信消耗。

1 DPoS 共识算法相关研究

DPoS 共识算法凭借低延时、出块时间短、高吞吐量、几乎不分叉的特点及优势，得到了研究人员的广泛使用［19］，区块链架构如图1 所示。DPoS 相较于PoW 有更低的能源消耗，减少了硬件资源的消耗，且继承了PoS的股份思想，具有比PoS 更快的效率和更高的性能。DPoS 共识算法在选举委托人节点过程中，由持有股份的节点相互投票（投票权重与股份成正比），即每个股东节点可以将其持有的股份作为选票授予一个代理人，最终选定的节点为票数靠前的n个节点，选定的n个节点轮流进行打包交易和出块。但持有股份越多的节点当选委托人节点的概率极大，造成了弱中心化，并容易导致Dos 攻击［20］。

图1 区块链结构Fig.1 Structure of blockchain

由此，许多学者对DPoS 共识算法做了进一步优化。文献［21］提出了节点的升降机制，从对恶意节点的识别角度出发，对良好节点和恶意节点通过降级的方式加以区分。文献［22］在节点升降的基础上引入了诚实节点的动态选举，有效降低选取恶意节点的概率，但对节点投票活跃度没有明显提升。文献［23］引入了信用值，为每一个节点设定一个信用值，信用值作为当选委托人节点的一个重要参考指标，每轮共识结束后信用值发生改变，但信用值的积累可能导致信用值高者越高的情况。文献［24］将DPoS 中的节点分为不同的信誉状态，同样可能导致信誉值高的节点一直处于高信誉的问题。从优化投票的角度出发，文献［25］提出细化投票的思想，其中包括支持票、弃权票、反对票，通过3 种方式度量节点的意愿投票倾向，文献［26］根据细化的投票方式又做了进一步优化，增加10 分支持票、10 分反对票的投票方式，改善了单一投票的方式，但不能完全满足现实状况的实际投票人的意愿权重。

2 CE-DPoS 共识算法方案

由于经典DPoS 共识算法选举节点固定单一，且始终是股份占比较大的节点，导致股份占比少的节点活跃度急剧下降。同时选举出委托人节点后，出块顺序未考虑节点之间的通信消耗，加大了出块时间。针对上述问题，本文提出一种CE-DPoS 共识算法。每个节点根据自身的意愿相互投票，在一轮共识投票结束后，模型网络会计算出每个节点的最终加权票数，并进行降序排列。每个节点在加入区块链网络前，会和网络中的其他节点进行通信，随后根据通信的代价建立自身节点的网络信息表，网络信息表中存储的是与自身通信开销最小的某些节点。最终依据网络的连接情况，依次动态选择通信量少并且分值最大的节点。

2.1 CE-DPoS 投票模型计算方式

在公有链网络中，节点参与活跃度与网络的安全性息息相关，在经典DPoS 共识算法中，节点投票有失公平性，节点出现投票政治冷漠性。为极大程度地满足节点的投票意愿倾向和公平性，对投票意愿设置等级。CE-DPoS 投票模型中的符号说明如表1 所示。

表1 符号说明Table 1 Symbol description

设定投票权重为Si，其中Si={i|i=1，2，3，4，5}，权重依次递增为：S1≤S2≤S3≤S4≤S5，投票意愿分别对应于［0～19%］、［20%～39%］、［40%～59%］、［60%～79%］、［80%～100%］。CE-DPoS 和DPoS 共识算法中最大投票数相同，每个节点至多对其他30 个节点投票。本文通过实验仿真进行模拟投票，统计投票信息的权重占比，若曲线出现近似正态分布，权重S1、S2与权重S5投票数大致相同，且均低于投票权重S3、S4，便于系统票数的计算，采用3 个集合Γ1、Γ2、Γ3进行票数的统计：Γ1代表投票意向为（0，39%］，集合中投票评分对应S1、S2；Γ2代表投票意向为［40%，79%］，集合中投票评分对应S3、S4；Γ3代表投票意向为［80%，100%］，集合中投票评分对应S5。

设节点收到其他节点的投票数为m（m值不涉及投票分值，一个节点参与投票即一票），节点对另一个节点评分值用Φ表示，其中Φi表示第i个节点的评分值。所有投票分值的中位数为，平均值为，节点最终分值如式（1）所示：

表2 列举了3 个节点的得票情况，节点之间对其他节点进行权重投票。

表2 节点得票数Table 2 Number of votes by the node

按照式（1）计算得到节点的最终分值：

不失一般性，设当前有11 个节点参与投票，则对于11 个候选节点出现的得票权可能性p如式（2）所示：

其中：mi表示票权为i的票数总和。

节点投票出现的所有可能结果以概率的形式表示，所有结果的概率之和为1，如下式所示：

通过计算，将节点得分按降序排列：

2.2 CE-DPoS 委托人节点选取

在网络信息表的基础上，选定所有节点中分数排名最高的节点A，从节点A网络信息表中选出除节点A外分数排名最高的节点B，再从节点B网络信息表中选出除B外分数排名最高的节点C，直至选定n个委托人节点，整体过程如图2 所示。

图2 CE-DPoS 委托人节点选举流程Fig.2 Procedure of CE-DPoS delegate node election

区块链网络中的交互主要通过节点之间的通信，通信快慢直接或间接影响着整个区块链的性能。文献［27］定义了节点发生冲突块的概率Pr(F=0)，如式（3）所示：

其中：T为区块最大传播时延；G（t）代表多个区块传播给节点的概率积累值；P为挖矿难度。

区块传播时间定义如式（4）所示：

将式（4）变形得到：

其中：G(t)=，最终得出Pr(F≥1)≈P×ns×D。结果表明出块概率与区块传播时间成正相关。

在DPoS 共识算法中，委托人节点之间的传播主要是与后面一个节点通信，因此节点之间依靠通信代价最小的连接是提高性能的一种方式。

本文设置节点网络信息表用于保存每个节点与自己一定距离范围内（通信代价）其他节点的连接信息。为防止节点选举发生网络风暴，进而导致无法选取出委托人节点，设定每个节点与其他节点连接数为k，k≥n-1，其中k为固定值，n为选取的委托人节点总数。在节点加入网络时，向其他节点进行通信，当节点N1每收到一个返回消息时，发送者N2的IP 地址就被用来更新对应的网络信息表。如果N2的IP 地址没有记录在该信息表中，则N1节点的记录项小于k个，记录N2至自身信息表中；如果节点N1的记录项大于k个，则对该节点信息表中的节点进行检测操作。出现节点没有响应，从表中删除无响应的节点，并插入N2节点。如果所有节点都有响应，则忽略N2。网络信息表的建立具体流程如算法1～算法3 所示。

3 实验结果与分析

为测试模型的有效性，仿真实验设备配置为AMD Ryzen 5 3550H 处理器，16 GB 运行内存，Windows10 操作系统，采用Docker 容器技术，运用编程语言通过多端口模拟多节点来实现节点的投票行为。共识协议假定节点之间是诚信可靠的，并且网络与最终交付确保是异步通信的，每个节点能通过可靠的通信链路连接。

3.1 CE-DPoS 投票结果

本文设定从11 个节点中选择4 个节点作为委托人节点，此外，各节点相互之间能够对其他节点进行权重为0～5 的对等投票，其中0 表示未进行投票打分，图3 展示了11 个节点相互投票的结果。

图3 11 个节点互相投票结果Fig.3 Result of 11 nodes voting with each other

表3 所示为对图3 结果的分析，将各个节点得分进行统计，计算出票权数总和Total 值，但会出现多个Total 值相等的情况，并不满足实际的投票意愿，因此使用式（1）计算它们的偏差度，得出最终的分数V#。

表3 节点得分票权占比和最终分值Table 3 Proportion of node’s scoring votes and final score

图4 为本文预先设定的节点之间路由表的连接，连接数k设定为3（单向箭头指向代表该节点网络信息表中包含箭头指向的节点），各个节点通过与其他节点的交互行为形成各自的网络信息表，最终所有的节点共同维护全局网络信息表，矩阵R表示路由连接信息，1 表示连接，0 表示未连接。

图4 节点网络信息表连接情况Fig.4 Connection status of node network information table

通过图4 中各个节点之间的关系，采用局部最优的思想，最终选取的委托人节点如表4 所示。

表4 委托人节点选取的最终结果Table 4 Final result selected by delegate node

3.2 CE-DPoS 动态选举节点百分占比

本文模型中委托人节点的选取是动态的，并且兼顾了各节点的票数，选出的节点既满足通信量小且得分较高。在一轮共识结束后，计算选出的4 个节点的分数平均值，从剩下的7 个节点中随机选取另外4 个节点并计算出平均值。最终分别计算出与一轮共识中最高分的比值，如式（5）所示：

重复共识选举20 次，实验结果如图5 所示。由图5 可知，pa和pβ值呈现相似的波动。随着共识次数从0～20 的增长，使用CE-DPoS 共识算法选举模型比随机选取算法在满足现实情况投票方面的优势更加突出。当共识次数增加到15 次时，CE-DPoS 共识的委托人选举百分占比为97.23%，而同等条件下随机选取委托人百分占比仅有91.05%。

图5 选举委托人节点分数占比1Fig.5 Election delegate node score percentage 1

增加共识次数至100 次，结果如图6 所示，随着共识次数的增加，CE-DPoS 共识算法选取委托人百分占比整体波动相对稳定，而随机选取波动幅度较大。

图6 选举委托人节点分数占比2Fig.6 Election delegate node score percentage 2

3.3 CE-DPoS 出块时间

传统DPoS 共识算法在选出节点后，委托人节点之间的先后通信方式没有明确的规定，采用随机的见证人出块顺序，出块速度大致为3 s 左右。BFT-DPoS 共识算法选取委托人后互相协商出一个出块的顺序，见证人出块时进行全网广播，其他见证人收到新区块后，立即对此区块进行验证，不需等待其他见证人自己出块时再确认。CE-DPoS 共识算法通过设定网络信息表记录节点之间通信代价，在信息表中依次选取委托人节点，降低了随机选取委托人节点之间不必要的通信消耗。

实验仿真3 种共识算法的出块时间进行对比，结果如图7 所示。随着区块个数从0～1 000 的增长，使用CE-DPoS 共识算法比DPoS、BFT-DPoS 共识算法在降低出块时间方面的优势更加突出。当区块个数增加到1 000 个时，CE-DPoS 共识算法的出块时间降至0.4 s，比同等条件下DPoS 共识算法节约了80%的时间，能更好地应对日益增长的交易量。

图7 出块时间对比Fig.7 Block time comparison

3.4 CE-DPoS 节点活跃度

DPoS 共识算法由于存在去中心化程度低下、节点投票不积极等问题而被业界与学术界所诟病。本文实验仿真3 种共识算法，计算节点投票占比并将其进行对比，结果如图8 所示。随着共识次数的不断增加，使用CE-DPoS 共识算法比DPoS、BFT-DPoS共识算法在提升节点投票活跃度方面优势更加突出。由于DPoS 和BFT-DPoS 都采用股份的投票方式，股份较少的节点失去了投票的积极性，全局投票活跃度仅为34%左右，同程度的CE-DPoS 共识算法节点活跃度提升至85%。

图8 节点活跃度对比Fig.8 Node activity comparison

4 结束语

DPoS 共识算法作为主流公有链共识算法，存在选择委托人节点单一固定、委托人节点之间出块顺序采用随机方式以及通信消耗成本较高的问题。本文提出一种意愿评分的模型方案，该方案节点相互评分，计算出每个节点的综合分值，然后通过排序选取出当前分数最高的节点，再按照网络信息表的连接情况依次选择出后续的委托人节点。实验结果表明，本文方案选择的委托人节点之间的出块顺序与节点之间的通信密切相关，能够加快节点的出块时间，满足日益增大的交易量，并提升节点的投票活跃度。后续工作将进一步优化CE-DPoS 投票模型的时间复杂度，并应用到实际场景中。