基于改进PBFT算法防御区块链中sybil攻击的研究
2020-10-11赖英旭薄尊旭刘静
赖英旭，薄尊旭，刘静,4
（1.北京工业大学信息学部，北京 100124；2.信息保障技术重点实验室，北京 100072；3.智能感知与自主控制教育部工程研究中心，北京 100124；4.西安电子科技大学陕西省网络与系统安全重点实验室，陕西 西安 710071）
1 引言
自2008年比特币问世以来，电子加密货币已成为当今社会的热点话题。作为电子加密货币底层支撑技术的区块链也进入了大众视野并得到了广泛关注。目前，区块链被应用在金融、物联网和贸易管理等多种场景中，这对区块链的安全性提出了更高的要求，要使区块链真正得到实际应用，解决其安全性是首要条件[1]。已经出现的智能合约代码漏洞[2]、自私挖矿[3]、Eclipse攻击[4]等安全问题对区块链的存在与发展带来了危害。
区块链的网络架构一般采用点对点（P2P,peer-to-peer）网络架构，所有节点的地位都是对等的，并且以拓扑结构相互连通，节点之间采用中继转发的模式进行通信[5]。由于区块链采用P2P的网络架构，因此更容易遭受sybil攻击，这种攻击发生在恶意节点伪造多个虚假节点身份加入区块链网络的过程中。例如，共识节点进行投票的过程中，sybil节点为了谋取利益故意投票反对正确的共识结果，从而妨碍区块链中的节点达成共识。此外，sybil攻击也可以破坏数据的冗余机制，恶意节点通过伪造多个虚假节点，将之前需要备份到多个节点的数据备份到了同一个恶意节点，严重破坏了分布式存储系统的安全性和可靠性。
目前，区块链中的sybil攻击通常配合Eclipse攻击共同发起。当区块链中的正常节点受到攻击时，无论是发出的还是接收的请求信息都可能被sybil节点截获并进行篡改，如果正常节点收到的信息是被sybil节点篡改过的，就无法进行正常的共识过程，sybil攻击对区块链技术有极大的危害。本文针对防御区块链中的sybil攻击开展研究，主要贡献如下。
1)针对sybil攻击的特点，在区块链网络中建立信誉模型来计算各共识节点的信誉值，借鉴权益证明（PoS,proof of stack）引入币龄的概念，通过币龄大小的关系降低了计算机进行Hash计算的难度[6]。将共识节点的信誉值与共识节点的投票权重相对应，各节点的信誉值不同，其拥有的话语权也不同，在共识过程中各节点根据投票权重来达成共识。
2)对实用拜占庭容错（PBFT,practical Byzantine fault tolerance）算法进行改进，根据共识节点的信誉值选出信誉值最高的当前节点作为主节点Sp。共识协议中增加了pre-commit阶段，不仅保证了节点间仍能正常达成共识，而且减少了节点间通信的次数。
3)对改进的共识协议进行形式化证明，验证共识协议的安全性，通过实验证明改进的共识协议仍是安全的。
2 相关研究
2.1 sybil攻击
Douceur等[7]在P2P网络系统的应用中提出sybil攻击的存在，认为如果网络中没有一个集中式认证机构，很可能会出现sybil攻击。现阶段，大型P2P系统在处理远程攻击或者系统故障时，大多采用数据冗余措施来防御这些安全威胁，然而如果有一个恶意节点伪造出多个节点身份，同时对外宣称都是正常节点，那么这个恶意节点将会破坏系统的数据冗余机制。
如图1所示，sybil攻击是指攻击者通过创建多个虚假身份加入P2P网络，并使用这些sybil节点来获得不成比例的影响，从而为自身谋取不正当的利益。sybil攻击不仅会破坏对等网络中资源共享的安全性、消耗正常节点的计算资源，严重时甚至会控制整个网络系统，造成更大的危害。
图1 sybil攻击
当前针对sybil攻击防御和检测的方法主要分为4类：基于图的方法、基于机器学习的方法、手动验证和传统防御方法[8]。其中，基于图的方法[9-12]是利用社交网络信息来识别sybil节点，但这些方法都依赖sybil节点和正常节点的连接是有限的这一假设，因此这类方法的扩展性很差。基于机器学习的方法[13-15]是从节点的行为和日志中提取特征来区分正常节点和sybil节点，但这类方法是根据已知sybil节点的行为来检测未知sybil节点，因此sybil节点可以通过改变不利于自身的行为来轻松地逃避检测。手动验证的方法是给经过人工验证的社交网络账户设置特别标志，拥有这样标志的用户发布的内容最有可能是真实的，但这种方法不仅验证效率低，也不适用于拥有众多对等节点的P2P网络。传统防御sybil攻击的方法是通过引入可信任的权威认证机构来对加入网络的节点进行认证，这种方法同样不适用于没有集中式认证机构的分布式系统，并且Fabric1.0版本中采用CA（certificate authority）作为证书的颁发机构，节点之间通信使用的公私钥由CA提供，如果CA服务出现故障，那么整个系统都会出现问题，因此对于去中心化的区块链系统来说扩展性差。
2.2 实用拜占庭容错算法
PBFT算法由Castro和Liskov提出[16]，解决了BFT算法效率差的问题，并且算法的复杂度由指数级降为多项式级，使其可以应用于需要处理大量事件但吞吐量不大的系统。PBFT作为经典的BFT状态机副本复制算法和基于投票的主流算法，同时保证了安全性和活性。
活性：所有客户端都会收到针对他们请求的回复，使用弱同步假设保证在一定时间内传递消息规避FLP（Fischer,Lynch,Patterson）不可能性的结果。
在PBFT算法中，共识节点发送的消息都必须由节点进行签名，其他节点以此验证消息的真伪。该算法的共识过程主要分为3个阶段：预准备、准备和提交。如果收到超过不同节点的同意消息，则提交的交易信息是有效的。在使用PBFT算法作为共识算法的区块链网络中，N个节点可以包含f个拜占庭恶意节点，其中。也就是说，N-f≥2f+1，因此PBFT算法要达成共识，需要至少2f+1个节点将共识信息添加到分布式账本中。
由于PBFT算法是分布式系统中达成共识一致性的一种性能良好的解决方案，增强了分布式环境下数据和系统服务的可用性[17]，因此PBFT算法在区块链中得到了广泛的应用。王海勇等[18]提出在PBFT算法中引入投票机制，以监督生产节点诚实工作。Wang等[19]提出了基于信用授权的拜占庭容错（CDBFT,credit-delegated Byzantine fault tolerance）算法，通过投票奖惩和信用评估共识过程中每个节点的行为。文献[20]提出了一种高性能、可扩展的拜占庭容错（HSBFT,high performance and scalable Byzantine fault tolerance）算法，在正常情况下可将算法的复杂度降到O(n)。在Fabric项目0.6版本和Honey badger[21]项目中都使用PBFT作为核心的共识算法。然而，上述研究在防御恶意节点方面作用有限，缺乏对不同参与节点分配不同话语权的考虑。
在PBFT共识算法下关于防御sybil攻击的研究中，Alex等[22]将信誉系统与分布式一致性协议相结合，引入声誉模块ReCon放置在PBFT等各种共识协议上，对sybil攻击有很强的抵抗能力。闵新平等[23]提出了许可链多中心动态共识机制，并且设计了一种多主节点的PBFT算法（MPBFT,multi primary node Byzantine fault tolerance），通过安全性分析与证明，许可链多中心动态共识机制可保证交易不可篡改，同时预防sybil攻击。Zhang等[24]利用区块链的不可篡改性提出了一种Hash-oriented的PBFT算法，旨在减少共识确认的时延，安全性分析表明，其能够有效防御区块链中的双花攻击和sybil攻击。
2.3 信誉模型
在当前的研究工作中，P2P网络中已经实现了各种不同的信誉系统。实现电子商务等的信誉系统需要可靠的中央服务器，用来记录用户的历史行为并进行信誉评级。而有些信誉系统则使用分布式数据库，网络中所有节点的地位都是对等的并且都能实时更新本地副本，使用这种信誉系统的节点只记录与其发生信息交互的对等节点的信誉值。
Janbi等[25]提出了一种对分布式排名的信誉系统DRank进行结构优化的方法，提高了DRank的性能，但容易受恶意节点共谋攻击的影响。Sarah等[26]对AuthenticPeer进行改进，通过防止不受信任的文件传播来增加信誉，并减少恶意节点的集体欺骗行为。Gupta等[27]在P2P网络上实现了集中式服务器模型，确保网络中的所有节点都可以访问最新数据且不要求网络中的所有节点使用信誉服务，但该方案的前提是网络中不存在恶意节点，所以未能解决恶意节点可能串通来增加其自身信誉值以便从系统中获利的可能性。黄建华等[28]提出了基于信任度证明的共识机制（PoT,proof of trust），解决了权益证明机制中存在的易受贿赂攻击、币龄累积攻击，以及工作量证明机制中存在的自私挖矿等问题，但是对区块链中存在的sybil攻击没有提出很好的解决方案。
2.4 网络安全协议的形式化证明与分析
在网络安全协议的形式化证明与分析中，安全协议的分析方法主要包括模态逻辑技术、定理证明和模型检测技术[29]。其中，模态逻辑技术是一种比较重要的安全协议分析方法。模态逻辑用命题假设和推理规则来表示主体对消息的知识或信仰，运用推理规则可以从已知的知识和信仰推导出新的知识和信仰[30]。
在总结和完善BAN（Burrows,Abadi and Needham）逻辑和其他类BAN逻辑缺点和不足的基础上发展出了SVO（Syverson,Van Orschot）逻辑，它的出现也标志着模态逻辑在安全协议的分析方法中走向成熟。SVO逻辑不仅拥有规范的模态理论语义和极其出色的扩展能力，还建立了完备的理论模型和详细的计算模型，消除了在理解模态逻辑形式化表达式含义的过程中可能存在的歧义，通过规范的理论语义可以更好地理解协议消息所要表达的真正含义。
3 共识算法的改进
在本文改进的PBFT算法中，通过共识节点的可信状态选出一个信誉值最高的节点作为主节点Sp。由于在PBFT共识过程中，有2个阶段需要传输的网络消息数为O(n2)，造成了很大的网络开销，因此在改进的共识算法中增加了pre-commit阶段来减少节点间通信的次数。每轮共识过程中主节点Sp会生成一个新区块并广播到所有的共识节点，同时参与共识的节点依据信誉模型计算节点的信誉值，依据信誉值为共识节点赋予不同的话语权。在达成共识的投票过程中，各节点拥有不同的投票权重，信誉值高的节点拥有更大的投票权重，而恶意节点由于信誉值低拥有很小的投票权重甚至没有投票权重，因此可以杜绝恶意节点对投票结果的干扰。本文的全局变量参数如表1所示。
表1 全局变量参数
3.1 系统模型
本文假设在区块链系统中有N个共识节点S={S0,S1,...,SN-1}，每轮共识过程都存在一个主节点Sp，所有共识节点把接收的事务信息先缓存到本地，同时主节点Sp将客户端发来的有效交易事务打包到一个区块中。如果新区块被大多数共识节点验证通过，则认为它是有效的，该区块将被添加到区块链中。如果没有被大多数共识节点验证通过，那么这个区块被舍弃。在区块链系统中对PBFT算法进行改进，将共识节点的投票权重与所拥有的信誉值相对应，每个共识节点都维护更新一个共识节点信息表（CNIL,consensus node information table），如表2所示。
表2 共识节点信息
CNIL包含当前区块链系统中与本节点进行过信息交互的邻居节点的集合、信誉值、可信状态以及节点的ID，其中每个节点随机选择邻居节点建立连接[31]。及时更新和维护共识节点的信息列表非常重要，关系到节点的信誉值和节点拥有的不同话语权，将所有节点的信息列表的初始值设为相同值。
3.2 建立信誉模型
信誉模型用来计算每个节点的信誉值，而信誉值由共识过程中节点的行为决定。信誉模型作为共识协议的一部分，可以在每个参与共识的节点中执行，并且信誉值是独立计算的，可以与共识消息进行同步广播。在改进的共识算法中，设定的信誉值R是0～1的实数，信誉值越大，可信度越高。对于系统新添加的共识节点，其初始信誉值都设为0.5。由于主节点和其他副本节点在共识过程中的行为不同，本文分别讨论了2种情况。
3.2.1Si为主节点
对于主节点而言，在t轮共识过程中如果有新区块产生，那么主节点的信誉值会增加，并且随着共识轮次越来越多，信誉值增长的速度会越来越慢，但最大值不会超过1。如果没有新区块产生，那么主节点的信誉值会下降，下降的速度由系数x的值决定。如果主节点向其他节点发送了不同的节点信息列表，那么主节点的信誉值会降为0，并将其从当前的共识节点信息列表中删除。设Ri(t)为区块链中第t轮共识后节点Si的信誉值，则Ri(t+1)为
3.2.2Si为副本节点
对于副本节点而言，在t轮共识的过程中如果向其他节点发送了相同的信息列表并且投票结果与最终结果一致，则副本节点的信誉值会缓慢增加，但不会超过1。如果副本节点在本轮没有参与共识过程，则其信誉值会降低，下降的速度由x的取值决定。如果副本节点参与了共识过程，但是投票结果与最终结果不一致，则其信誉值会降低，下降速度由系数y的取值决定。虽然x和y的值都决定了信誉值降低的速度，但根据节点行为的不同，需要以不同的速度来降低节点的信誉值。如果检测到同一共识节点发送了不同的信息列表，则该节点将被视为sybil节点，其信誉值降为0，并将其从当前的共识节点信息列表中删除，如式(2)所示。
在上述信誉模型中，所有正常参与共识的节点的信誉值都是缓慢增加的。随着系统持续运行，系统的话语权将更多集中于正确的共识节点。此外，可以考虑在系统的实际应用中加入激励机制，正常工作的节点拥有更高的信誉值、更多的话语权，会获得更多实质性的奖励。如果节点的信誉值过低，则获得很少的奖励，甚至会将其从当前的共识节点信息列表中删除。
3.3 主节点更新算法
其中，S为共识节点集合；P为共识节点当选为主节点的概率；D为指数分布，在C2C（consumer to consumer）网络和大多数社交网络中的信誉分布都是指数分布[32]。指数分布的概率密度函数F(x)如式(4)所示。
为了保证信誉值越高的节点有越大的概率当选为主节点，根据文献[22]中模拟实验，当设置最小恶意节点的概率α1=0.05时，共识节点N={5 000,10 000,20 000,30 000}分别运行10 000轮后达成共识的成功率最高。本文不仅考虑共识节点的可信状态μ，同时确保指数分布截断在区间(0,N]，因此取μ=1,2,3分别对应共识节点的前3种可信状态，当共识节点的信誉值低于初始设定值0.5时，则其不在更换主节点的考虑范围内。共识节点的可信状态TS=1，则μ=1时，有
也就是说，可信状态TS=1的共识节点有95%的概率当选为主节点。依次类推，TS=2和TS=3的共识节点分别有80%和55%的概率当选为主节点。本文使用指数分布，信誉值较高的节点有较大的概率当选主节点，而信誉值较低的节点当选主节点的概率较小。如果有多个节点的信誉值相等，则优先选择没有当选过的节点作为主节点。
共识节点的可信状态由信誉值R决定，因此可将共识节点分为6种可信状态，分别为良好节点、正常节点、初始节点、异常节点、错误节点和恶意节点，如表3所示。
表3 节点可信状态
在本文设计的信誉模型中，分析了节点作为主节点和副本节点的不同行为特征的评价标准。在共识过程中，当主节点被认为是恶意节点时，其信誉值会直接降为0。这时需要在参与的共识节点中重新选举主节点。更新主节点的基本原则是，节点的信誉值越高越容易当选主节点。主节点的更新流程如图2所示。
图2 主节点的更新流程
变更主节点算法的具体步骤如下。
步骤1共识过程中，当主节点的信誉值低于设定的阈值时，各副本节点需要选取当前节点中信誉值最大的节点作为主节点，副本节点向其他节点广播primary-change消息的内容为
步骤2其他副本节点收集并计算是否有2f个不同副本节点（不包括其自身）发送更新主节点为Sm的priamry-change消息，如果是，则副本节点向Sm发送primary-change-ack消息，其内容为
步骤3新当选的主节点Sm向其他副本节点发送new-primary消息的内容为
3.4 改进共识算法
在共识算法的改进中，通过计算各节点的信誉值为各节点分配不同的话语权。根据各共识节点提供的信息列表评估共识过程中每个节点的信誉值，不仅可以检测出其中的恶意节点，而且可以将检测出的恶意节点从共识节点信息表清除。良好节点的信誉值会逐渐累加，在共识过程中的话语权也逐渐增加，而恶意节点的影响会逐渐减少。共识过程中，节点i更新共识状态的条件是向其发送消息的共识节点的信誉值总和Rv足够大。其他节点信誉值总和Rv的计算方式如下。
假设区块链网络是一个有向网络G(ε,E)，其中ε为n个节点集合，E为有向链路加权集合，可以用来预测共识节点之间协商的可能结果。
在区块链网络中，Rv由与其进行信息交互的节点信誉值共同决定，即节点i在t轮共识中收到的信誉值为
其中，Ri(t)为节点i在t轮共识时的信誉值，矩阵由网络拓扑及链路上的信誉值构成，φT为其转置矩阵。
如果Rv受到多个共识节点的影响，那么节点i收到的信誉值就是作用于i上所有影响的总和，如式(7)所示。
状态方程可表示为ΔR(t)=LR(t)，其中L是φT的Laplacian矩阵。因此，更新规则为
收到的其他节点Rv应不小于设定的阈值Rthreshold，如式(9)所示。
改进的PBFT算法共有6个阶段，其中最主要是以下4个阶段：预准备、准备、预提交和提交。改进的PBFT算法中引入了信誉模型，通过各节点共识过程中的行为对节点进行信誉评估，检测区块链中的sybil节点，工作流程如图3所示，具体步骤如算法1所示。
算法1改进PBFT算法
输入交易tx
输出共识结果
1)客户端c发起交易tx，并将交易广播到主节点0。主节点0收到发送的交易tx，首先验证tx是否有效，若无效直接将其删除；若有效则将tx打包到区块中，并根据区块体内的信息生成区块头Bhead。
2)主节点0广播预准备（pre-prepare）消息到各副本节点，内容为
图3 改进PBFT算法工作流程
其中，h是当前新区块的高度，d是区块头Bhead的摘要，t是当前的时间戳，P0是当前主节点0的ID，CNIL0是主节点0的共识节点信息表。
3)副本节点1,2收到主节点0发送的预准备消息，首先验证新区块的有效性，验证通过则分别向其他节点发送prepare消息，内容为
4)副本节点1,2收到其他副本节点发送的prepare消息，发送消息的节点拥有不同的信誉值。首先副本节点计算当前向其发送消息的节点的Rv，如果Rv≥Rthershold则在本地更新交易信息的共识状态并发送pre-commit信息，内容为
5)主节点0将收到的副本节点发送的pre-commit信息进行比较，根据信誉模型计算当前每个节点的信誉值，更新本地的共识节点信息列表，同时将共识结果反馈给客户端和所有的副本节点，发送commit消息，内容为
6)完成提交状态后，区块链中的副本节点更新本地的共识节点信息表，并将共识结果反馈给客户端，准备下一轮的共识过程。
在节点进行共识过程的不同阶段需要分别验证交易和新区块的有效性，验证的主要内容如下。
1)验证交易的有效性
在进行共识的预准备阶段，主节点需要验证收到客户端发送的交易tx的有效性。验证tx的格式是否正确和时间戳是否有效，验证事务中的脚本是否可以正确的执行，如果通过验证则tx是有效的。
2)验证新区块的有效性
当副本节点收到主节点生成的新区块时，需要验证新区块的有效性。验证区块头中的Merkle根是否正确和区块头中是否引用前一区块的哈希值，同时验证区块中的交易是否有效，如果通过验证则新区块则是有效的。
4 共识协议的形式化分析验证
共识协议的形式化分析验证主要分为共识协议的安全性分析和对协议的安全性测试。
4.1 共识协议的安全性分析
共识协议的安全性分析主要分为共识协议的理想化描述、初始化假设、设定安全目标和对协议进行理论分析4个部分。
4.1.1共识协议的理想化描述
使用SVO逻辑对改进的PBFT算法的共识协议进行安全分析。首先需要对该协议的工作流程进行符合SVO逻辑的理想化描述。描述结果如下。
1)客户端c向主节点0发送交易tx，交易信息中带有时间戳和客户端标识。
2)主节点0对tx进行验证，验证通过后向其他副本节点发送带有自己签名的预准备消息，该消息中包含当前区块的高度、区块头的哈希摘要、主节点的ID以及共识节点信息表。
3)副本节点1,2,3收到预准备消息验证之后向其他节点发送各自签名的准备消息，将接收到的其他共识节点信息表存储到本地。
4)各共识节点收集其他节点的准备消息，如果Rv≥Rthershold，则在本地更新交易信息的共识状态，并发送pre-commit信息。
5)主节点和各副本节点向客户端c发送响应消息，将达成的共识结果返回给客户端。
4.1.2协议的初始化假设
使用SVO逻辑对共识协议进行推理分析的过程中，首先进行初始假设，即定义共识协议中每个节点在初始时刻拥有的知识和信仰。初始化假设是进行推理证明的第一步，根据共识协议流程，设定如下假设。
1)关于密钥的有效性
2)关于信息的发送
客户端c向主节点0发送交易tx，并验证交易的格式和时间戳，以及事务的脚本能否正常执行，验证通过后向副本节点发送信息
副本节点收到主节点0发送的信息，验证新生成区块的Merkel根和指向前一区块的哈希值，验证通过后向其他节点发送消息
3)关于信息的接收
各共识节点收集其他节点的准备消息，如果Rv≥Rthershold，则在本地更新交易信息的共识状态。
主节点0收到的信息为
副本节点1收到的信息为
副本节点2收到的信息为
副本节点3收到的信息为
4)关于信息的新鲜性
4.1.3协议的安全目标
由于改进的PBFT算法中加入了共识节点信息表，每轮共识之后都要根据各节点的行为计算信誉值并且更新CNIL。因此共识协议需要达到的安全目标主要是各节点的能否收到其他节点发送的CNIL，同时保证客户端发送的请求能够达成共识。共识协议的安全目标用SVO逻辑语言表达如下。
首先，确保每个节点都能收到其他节点发送的共识节点信息表。
其次，确保每个节点都能收到客户端发送的请求
4.1.4协议分析
根据初始化假设，使用SVO逻辑对共识协议进行逻辑推理，验证共识协议是否达到预先设定的安全目标，以此分析共识协议的安全性。共识协议的分析过程如下。
由假设c:N1◁(h,d,P0,CNIL0)和接收公理，可得
同理，可得
由假设c:N1◁ (h,d,P0,CNIL0) 和接收公理，可得
同理，可得
综合上述分析，可得
4.2 协议的安全性测试
4.2.1测试工具
AVISPA（automated validation of internet security protocols and application）是自动验证网络协议和应用程序是否安全的模型工具，其融合了4种不同的分析组件：动态模型检验器（OFMC,on-the-fly model-checker）、基于逻辑约束的攻击搜索器（CL-AtSe,constraint-logic-based attack searcher）、基于SAT的模型检验器（SATMC,SAT-based model-checker）和基于自动逼近的树自动机安全协议分析（TA4SP,tree automata based on automatic approximations for analysis of security protocol）[33]。
AVISPA工具提供了一种模块化和富有表现力的高级协议规范语言HLPSL（high-level protocol specification language），用于指定安全问题和数据结构。其集成了多种不同的检测后端，能够自动进行各种分析技术，从协议伪造（通过发现输入协议的攻击）到有限和无限数量会话的基于抽象的验证方法[34]。其架构如图4所示。
图4 AVISPA 架构
4.2.2基本角色
在共识协议中分别为每个参与者定义一个角色，即客户端c、主节点N0、副本节点N1,N2,N3的角色，如表4所示。
4.2.3会话场景
本文根据改进的PBFT算法定义了3种会话场景来验证共识协议是否符合安全目标，如表5所示。场景1为正常的会话过程，其中包含所有合法的场景；场景2中主节点为sybil节点；场景3中副本节点为sybil节点。
4.2.4安全目标
为了评估改进的PBFT算法共识协议的安全性，首先要明确协议需要达到的安全目标。AVISPA工具中提供了不同的关键字表示安全目标。在本文的安全性测试中，用关键字描述如下。
1)共识过程中的请求信息Q是由客户端C产生的，并且将此信息广播给主节点N0。
其中，t是安全目标中的标识符。
2)关键字request声明副本节点N{1,2,3}收到了主节点N0发送的共识信息Q，关键字witness声明主节点N0向副本节点N{1,2,3}发送了共识信息Q。
为了对共识协议的安全性进行测试，本文定义了如下安全目标。
1)在共识协议中，主节点N0验证客户端C发送的请求信息的有效性，确保请求信息的交易格式和时间戳有效。其他副本节点N{1,2,3}需要验证主节点生成的新区块的有效性，验证区块头中的Merkel根是否正确，以及区块头是否引用前一区块的哈希值，以此判断主节点是否是sybil节点。用HLSPL描述如下。
2)在共识协议中，每一轮共识之后各节点之间需要同步共识节点信息表，防止sybil节点篡改共识信息，干扰正常的共识，保证各节点的信誉值能够同步进行更新。用HLSPL描述如下。
4.2.5实验结果
在AVISPA中使用OFMC和CL-AtSe分析工具对改进PBFT算法的共识协议进行分析，实验结果如图5所示。
由图5可知，使用OFMC和CL-AtSe分析组件对改进PBFT算法的共识协议的分析结果是安全的，即SUMMARY:SAFE，并且没有发现协议中存在缺陷。因为如果检测到协议中有缺陷，SUMMARY字段会显示UNSAFE，而DETAILS字段会提示ATTACK_FOUND。
在分析过程中，改进PBFT算法的共识协议由HLPSL的高级协议规范语言转换为IF语言形式，保存在PROTOCOL字段给出的路径中，其文件名为hlpslGenFile.if。图5中的BACKEND字段显示实验所用的分析工具的类型，STATISTICS字段显示分析工具所运行的时间以及搜索的节点数。
表4 基本角色定义
表5 会话场景定义
图5 测试结果摘要
5 改进PBFT算法的性能分析与评估
本文实现了一个简单的区块链系统，主要包括共识模块和生成区块模块两部分。其中，共识模块将达成共识的信息发送给生成区块模块，从而生成包含交易信息的区块链。共识模块中分别包含不同的共识算法，即PBFT和改进的PBFT，来验证交易、生成和提交新块。本文实验在平台上模拟不同的共识节点进行共识的过程。实验平台参数如下：Intel Core i5-8265U，2.60 GHz，8 GB RAM。
从3个方面来评估改进PBFT算法的性能，分别为事务吞吐量、时延和算法的时间复杂度。本文实验设计的共识节点数量分别为4、7、10、13和16，统计的块生成周期分别为3 s、6 s、9 s、12 s、15 s和18 s。当系统运行稳定时，统计区块链系统的TPS（transaction per second）和生成区块的时延。
5.1 TPS的比较
在区块链系统中，TPS是指系统每秒钟能够处理的事务数量。TPS的大小直接反映了系统处理能力的高低。
实验中分别设定不同数量的共识节点，不断向区块链系统中发送交易，待系统稳定后，每隔3 s统计一次区块链系统处理的交易数量，然后进行计算。图6对比了相同的实验平台下，PBFT算法和改进的PBFT算法在不同数量共识节点下的TPS。
由图6可知，当系统运行时间为12 s和18 s时，系统中的TPS基本保持在同一水平。当运行时间为15 s时，改进的PBFT算法的TPS达到最高，平均值约为3 850，PBFT算法的TPS平均值约为2 760，改进的PBFT算法的TPS提高了40%左右。与PBFT算法相比，改进的PBFT算法的TPS全面提高，并且随着共识节点数量的增多，TPS下降的速度也在放缓。
5.2 生成区块时延的比较
生成区块的时延Tdelay是指区块从生成到经过共识算法得到节点确认的过程。时延越短表示共识算法的执行时间越短，共识的效率也就越高。区块时延包括共识算法的执行时间Tconsensus、信息的广播时间Tbroadcast、区块中交易的打包时间Tpackage和区块的确认时间Tconfirm。
图6 2种算法不同数量共识节点的TPS对比
区块时延主要由Tconsensus和Tbroadcast组成，而Tpackage和Tconfirm可以忽略。在相同的实验平台下，本节分别统计了PBFT算法和改进的PBFT算法在不同数量共识节点下生成区块的时延，如图7所示。
由图7可知，改进的PBFT算法中共识节点生成区块的时延比PBFT算法整体上减少了10 ms左右，并且随着共识节点数量的增多，共识节点生成区块的时延减少的效果更加明显，尤其在运行时间为15 s时，生成区块的时延减少最多。以上数据说明改进的PBFT算法在减少生成区块的时延方面也有很大的提升。
5.3 时间复杂度的比较
在PBFT算法的3个主要阶段中，在预准备阶段主节点广播pre-prepare消息给其他副本节点，通信次数为(n-1)；在准备阶段，每个节点向其他节点广播parepare消息，总的通信次数为n(n-1)；在提交阶段，每个节点向其他节点广播commit消息，通信次数也为n(n-1)。PBFT算法总通信次数为(2n2-n-1)，时间复杂度为O(n2)。
改进的PBFT算法在节点进行共识的过程中加入了对节点信誉值的计算，并且增加了pre-commit阶段，因此改进PBFT算法的总通信次数为(n2+2n-3)。虽然改进算法的时间复杂度仍维持在O(n2)，但减少了节点间通信的次数。
6 结束语
图7 2种算法不同数量共识节点生成区块的时延对比
本文说明了sybil攻击对区块链的危害，分析了各种防御sybil攻击的方案的不足。本文提出了一种能有效防御区块链中sybil攻击的方法，借鉴基于权益证明的共识思想在PBFT算法中加入信誉模型，将共识节点的投票权重与所拥有的信誉值相对应，根据共识节点的信誉值为节点分配不同的权重，在达成共识的投票过程中，不同节点拥有不同的投票权重。通过对PBFT算法进行改进，根据共识节点的可信状态选择当前信誉值最高的节点作为主节点，同时在共识协议的过程中加入pre-commit阶段来减少节点间通信的次数。
通过设计的一个简单区块链系统开展实验，将改进的PBFT算法与原PBFT算法在TPS、生成区块的时延和算法复杂度3个方面进行了对比，得出的主要结论如下。
1)改进的PBFT算法在系统运行时间为15 s时，TPS提高最多，整体上提高了40%左右，并且随着共识节点数量的增多，TPS下降的速度也在放缓。
2)改进的PBFT算法在共识节点数量为4、统计时间为15 s时生成区块的时延减少最多，相比PBFT算法生成区块的时延整体上减少了约10 ms。
3)改进的PBFT算法增加了pre-commit阶段，虽然时间复杂度仍维持在O(n2)，但减少了节点间通信的次数。
本文对改进的PBFT算法共识协议的安全性进行了形式化证明，通过理论推导以及实验证明改进的共识协议在通信过程中仍然是安全的。
本文方案不仅可以有效地防御区块链中的sybil攻击，而且使区块链的TPS和生成区块的时延的性能全面提升，因此本文方案可以满足大多数区块链系统的性能要求，同时可以保证系统的安全和性能的稳定。接下来的工作重点是进一步优化PBFT算法，降低PBFT算法的时间复杂度，在保证达成共识一致性的前提下减少节点间通信的次数。
