PBFT 共识算法性能分析论文

SCI论文（www.lunwensci.com）

　　摘 要：众所周知,共识机制是区块链的核心,是区块链实现分布式存储的关键。随着各种区块链共识机制地出现,基 于共识机制的优化方法也相继被提出,主要从优化共识过程以及控制共识节点的数量入手,解决共识机制吞吐量低、高时 延、高资源等问题。然而,许多基于共识机制的优化缺乏理论的分析,也没有提及关键参数会影响共识机制的性能。为此,文 中将以实用拜占庭算法 (Practical Byzantine Fault Tolerance Algorithm, PBFT)、基于分组的实用拜占庭算法 (Practical Byzantine Fault Tolerant Algorithm Based on Group, G-PBFT) 以 及 基 于 分 组 和 信 誉 的 实 用 拜 占 庭 算 法 (Practical Byzantine Fault Tolerant Algorithm Based on Clustering and Reputation, GR-PBFT) 为例,构建三者的数学模型,进行 性能分析。根据交易吞吐量、交易失败概率、区块认证失败概率和通信复杂度等性能指标进行对比。仿真结果表明 ：在同等节 点数量下,G-PBFTD、GR-PBFT 算法的吞吐量为 PBFT 的 1.57 倍、2.38 倍 ;G-PBFTD、GR-PBFT 算法的交易认证失败概率 比 PBFT 下降了 16%、39% ;G-PBFTD、GR-PBFT 算法的通信复杂度比 PBFT 下降了 3.1 倍、4.0 倍,优化效果显著。

　　(School of Electronical and Information Engineering, Shenzhen University, Shenzhen Guangdong 518060)

　　【Abstract】：As we all know, consensus mechanism is the core of blockchain, which is the key to achieve distributed storage in blockchain. With the emergence of various blockchain consensus mechanisms, optimization methods based on consensus mechanisms have been proposed one after another, mainly from optimizing the consensus process and controlling the number of consensus nodes to solve the problems of low throughput, high latency and high resources of consensus mechanisms. However, much of the consensus-based optimization lacks theoretical analysis and does not mention the key parameters that can affect the performance of the consensus mechanism. For this reason, the paper will construct mathematical models of the practical Byzantine algorithm, the grouping-based practical Byzantine algorithm, and the grouping- and reputation-based practical Byzantine algorithm as examples for performance analysis of all three. The performance metrics are compared based on transaction throughput, transaction failure probability, block authentication failure probability and communication complexity. The simulation results show that the throughput of G-PBFTD and GR-PBFT algorithms is 1.57 times and 2.38 times of PBFT with the same number of nodes; the transaction authentication failure probability of G-PBFTD and GR-PBFT algorithms decreases 16% and 39% compared with PBFT; The communication complexity of G-PBFTD and GR-PBFT algorithms decreases 3.1 times and 4.0 times, with significant optimization effects.

　　【Key words】：PBFT;consensus algorithm;clustering;credit score;blockchain

　　0 引言

　　随着物联网的深入应用,数据安全和设备可靠性的 问题也逐渐暴露出来。物联网设备与设备之间在共享数 据时, 容易遭受恶意攻击和隐私泄露等问题 [1]。另外, 物联网设备都需要通过云端服务器进行数据处理和管 理,一旦中心服务器被攻击,整个物联网系统将瘫痪, 造成无法估计的损失。因此,研究如何维护物联网的数 据安全是一个重要问题。

　　区块链具有去中心化、防篡改、可追溯性、共识机 制等特点,能够弥补物联网当前发展的不足,两者的结 合将会是未来技术研究的热点 [2]。区块链是基于点对点 的分布式账本,每一个节点都有与其他节点相同的账 本,账本由链状的区块组成,记录着区块链网络中产生 的所有事务。在区块链网络中,共识机制的设计是至关 重要的,共识机制使得网络在存在故障的情况下达成一 致 [3],这是构建用户间分布式可信的关键。目前区块链 中常用的共识机制有工作量证明机制 [4](Proof of Work, PoW)、权益证明机制 [5](Proof of Stake, PoS)、授权股 份证明机制 [6](Delegated Proof of Share, DPoS), 实 用拜占庭机制 [7], 其余共识机制大多是由这 4 种机制派 生而来。当面对设备数量众多时,计算能力和存储能力一 般,在分布广泛的物联网场景下, PoW、PoS 等需要节 点较高算力证明类算法并不适用于物联网设备。首先是 PoW 需要消耗大量的算力,但物联网设备中存在大量的 低功耗的设备,计算能力较低,两者结合难度较大 [8] ;其 次是 PoS 是基于币龄来选择共识节点,持有的货币量越 多成为共识节点的可能性越大。然而,这种方式容易出 现贫富不均的问题,影响了系统的安全性和公平性 [9]。 而 DPoS 也有去中心化程序不足的弊端 [10]。因此,相 比于其他 PoW 等证明类算法, PBFT 算法的吞吐量可 达数千 TPS,响应时间为秒级 [11],被认为是适合物联 网系统的共识算法 [12]。

　　PBFT 的提出主要是为了解决拜占庭问题, 它是一 种基于状态机副本复制的算法。PBFT 系统中有 3 种角 色,分别是客户端、主节点和副节点。主节点接受客户 端请求之后, 执行一致性协议 [13]。若在执行过程中出 现共识超时或主节点不响应,副节点会发送视图转换请 求,更换主节点,产生新的视图编号,并在新主节点下 进行共识工作以维持系统的活性。

　　PBFT 算法具有吞吐量高、响应时间快、能容纳不 超过f个拜占庭节点(总节点的数量应大于 3f )等优 点。但是,随着系统节点数地增加,节点间的通信量会 急剧增加,这将会给网络带宽带来巨大的通信压力,导致共识效率较低,系统性能迅速下降。因此,在物联网 设备计算能力和能量有限的条件下, PBFT 共识算法仍 需要进一步优化,以满足物联网的需要 [14.15]。

　　目前针对 PBFT 算法的优化随着节点数量的增加, 网络通信开销呈平方式增长以及共识过程存在的安全风 险造成资源浪费等问题进行研究。在减少网络开销方 面,研究者大多从减少共识步骤以及共识数量入手,从 而提升共识效率。

　　然而,在区块链应用上,尤其是资源有限、网络负 载随机产生的物联网场景中,缺乏相对应的理论分析来 对 PBFT 优化方法有一个深入了解。为此本文将对实用 拜占庭算法、基于分组的实用拜占庭算法以及基于分组 和信誉的实用拜占庭算法的区块链性能进行了数学理论 分析,通过交易吞吐量、交易失败概率、区块认证失败 概率和通信复杂度等方面进行性能对比,为进一步物联 网的应用提供理论参考。

　　1 相关的工作

　　共识算法 [16.17] 是区块链的核心,是区块链实现分 布式存储的关键。PBFT 可用于解决分布式系统中状态 机副本一致性的问题,当拜占庭节点数不超过节点总数 的三分之一时, 可保证共识的安全性和一致性。PBFT 算法的执行过程如图 1 所示,共识过程分为 5 个阶段, 分 别 为 Request 阶 段、Pre-Parepare 阶 段、Prepare 阶段、Commit 阶段和 Reply 阶段。目前,国内外针 对 PBFT 算法的优化也有许多进展,首先是从共识过程 入手,减少达到共识一致所需要的步骤,从而减少节点 网络开销 ;其次是控制节点规模,选举部分节点代替全 部,从而提高共识效率。

　　在优化共识过程方面,文献 [18] 中针对 PBFT 共 识算法效率较低的问题,结合物联网的特点,提出了 EIoT-PBFT 的多阶段共识算法。EIoT-PBFT 通过采用 两阶段改进的 PBFT 算法和基于位置和声誉的评分机 制来满足物联网边缘计算设置,从而大大提高了共识效 率。文献 [19] 中作者提出一种适用于食品溯源的优化 PBFT 算法 trace-PBFT(t-PBFT)。 将节点划分 为 3 个 等级,根据节点在每次共识中实际通信量动态更新节点 状态,以此来评价节点的可靠性,作为选举主节点的依 据 ;其次,结合食品供应链的特点,优化原算法中的共 识阶段,减少节点通信次数。文献 [20] 中,针对 PBFT 共识算法中需要完成的两次复杂度为 O(N2), 作者提出 了 SPBFT 共识算法,通过对一致性协议进行优化,复 杂度从 O(N2) 降为 O(N),且算法依旧能完成共识。文 献 [21] 中作者提出基于动态机制与信用积分机制的实用拜占庭容错共识算法 DT-PBFT,采用惩罚机制降低节点 连续作恶的可能性 ;在此基础上,优化一致性流程, 减 少全网节点信息交互过程,从而降低通信开销。

　　在控制节点规模方面,文献 [22] 提出了基于 PBFT 的新型改进共识算法 IPBFT,把节点分为协商节点和执 行节点,分别负责协商请求和执行请求。在此基础上, 通过心跳检测以及最长链选举,使得主节点的选举更加 合理,提高吞吐量和减少延时。文献 [23] 中作者提出了 基于特征的 PBFT 算法,通过特征分组将网络节点进行 分组,通过减少节点在网络中的共识,提高共识效率。 文献 [24] 针对存在资源消耗大、时延高等问题,提出了 一种基于服务质量 (Quality of Service,QoS) 感知的 信任服务评估的改进 PBFT 区块链共识算法, QTPBFT 融合了 QoS 感知的信任服务全局评估机制,通过根据 服务的实时性能进行动态评估来实现服务可靠性排序, 提高共识效率。

　　上述针对 PBFT 共识算法在优化过程和控制节点 规模上的研究已经有较大的突破,但在物联网的场景 下,区块链的应用仍需要数学理论上的分析,为进一步 应用提供理论参考。因此,本文将通过理论分析,研 究 PBFT 和两种常见的 PBFT 优化方法 (G-PBFT、GR- PBFT),通过交易吞吐量、交易认证失败概率、区块认 证失败概率和通信复杂度等方面比较三者的性能。

　　2 系统模型

　　本文以 PBFT、G-PBFT 以及 GR-PBFT 共识算法 为例,引入 4 个评价指标—通信复杂度、交易吞吐 量 TPS、交易失败概率和区块认证失败概率,研究三者 性能并进行对比。为了展示区块链系统中共识算法的性 能,通过通信复杂度、吞吐量来证明有效性,通过区块 认证失败概率和交易失败概率来说明鲁棒性。

　　假设系统模型中有 n 个基于 PBFT 的区块链节点, 其中所有节点都能直接在多跳网络中连接。另外,假设每个节点新交易到达的速率为 λi ,满足泊松分布, θ 为共识机制限制条件,任意节点j 等待被处理的交易的排 队队长为 Qj (排队队长大于区块最大交易容量)。由于 传输延迟要比计算时间和新交易到达时间要短得多,所 以在分析中忽略了网络传输时延。为了模型更加直观简 便,也忽略了当区块共识未能达成一致或主节点出现故 障时需要视图切换这一过程且假设拜占庭节点在参与 任何共识过程时只发送错误的信息和结果,符号说明如 表 1 所示。

　　2.1 实用拜占庭共识算法 PBFT

　　2.1.1 交易吞吐量和交易认证失败概率

　　定义在基于 PBFT 的区块链系统中,对于任意节点 j 计算 PBFT 的每阶段所需要的时间为 Tmij (i=1.2.3.4.5. 分别代表 PBFT 的 5 个阶段, j=1.2....,n,为节点数), 基于 PBFT 的区块链系统平均的区块认证时延为 TbPBFT, 每个节点计算能力大小为 rj 表示,参与共识的节点验证 每一个阶段所需要处理的数据集大小为 Ni (i=1.2.3.4.5)。 所以,在 PBFT 共识的每一个阶段,节点验证完成所需要的时延可表示为 Tmij=Ni/rj ,即每阶段节点所计算的数据 mij 的累计概率分布函数可以表示为如式(1)所示 [25] ：

　　在实际的应用环境中, θ ≪ 1.因此 log(1-θ) ≈ -θ , 则得到如式(2)所示 ：

　　可以看到, PBFT 每阶段节点验证时延 Tmij 是服从 以 θrj 为参数的指数分布的。

　　假设区块链系统中存在 n 个节点,每个节点的计算能力分别为 r1.r2.… ,rn , PBFT 中每阶段节点的验证时 延表示为 Tmij=Ni/rj (i=1.2.3.4.5.j=1.2....,n)。在 PBFT 的 Request 阶段 , 客户端向主节点 ( 假设节点 1 为初始主 节点 ) 发送区块信息请求,待主节点验证完进行全网广播 ,故 PBFT 中 Request 阶段的平均验证时间可以表示为如 式(3)所示 ：

　　在 PBFT 的 Pre-prepare 阶段,主节点接收到请求 服务信息并校验正确后,生成预准备信息,广播给每个副 节点, 这一阶段所有副节点的验证时间为 Tm2j=N2/rj (j= 2.3.… ,n),因此 PBFT 中 Pre-prepare 阶段的平均验 证时间可用所有验证时间的最大值表示,如式(4)所示 ：

　　在 PBFT 的 Prepare 阶段,从节点收到主节点的预 准备消息后,验证消息内容,确保消息内容在传输过程 中没有遭到篡改。待内容验证正确后,从节点会依据预 准备消息生成准备消息并将其广播给所有副本节点,此 时如果节点收到 2f+1prepare 信息时(f 为系统最大容 许的拜占庭节点数量),就可以认为大部分已经认可了这 个信息,则在这个阶段信息可以认为已经认证完成了, 故 PBFT 中 Prepare 阶段的平均验证时间可以表示为如 式(5)所示 ：

　　在 PBFT 的 Commit 阶段,当节点收到 2f +1commit 信息时(f 为系统最大容许的拜占庭节点数量)且都真 实有效时, 则该节点进入 Commit 状态, 准备请求进 入提交状态,此时,只通过这一个节点,就能判断该请 求服务已经被副本节点中的大部分节点验证通过,故PBFT 中 Commit 阶段的平均验证时间可以表示为如 式(6)所示 ：

　　在 PBFT 的 Reply 阶段,所有节点向客户端提交 共识结果。设置客户端的计算能力为 r 客, 则 PBFT 中 Reply 阶段的平均验证时间可以表示为如式(7)所示 ：

　　因此,区块链系统的平均区块产生时延可以表示为 如式(8)所示 ：

　　由于区块链系统中区块的交易容量有限,因此在区 块产生间隔时间内有多少新交易到达区块链网络中,区 块能够处理的交易数量大小不能大于区块的交易容量 L。因此基于 PBFT 的区块链系统的交易吞吐量 TPS 由 区块的交易容量和新交易的到达速率两者决定,可以表示为如式(9)所示 ：

　　PBFT 的区块链系统中交易失败概率 PfPBFT 可以表 示为如式(10)所示 ：

　　2.1.2 区块认证失败概率

　　在区块链网络中,若拜占庭节点数为f,且 3f>n(n 为节点总数 ),则每次区块验证时都将会失败。因为在 系统共识的过程中, f 个拜占庭节点可能不回应消息或 回应错误信息,那么必须在 (n-f ) 个状态复制机的沟通 内做出决定,但在最坏的情况下, (n-f ) 中可能还混有f 个错误节点发送而来的错误信息,所有只有当(n-f ) -f>f 时, 即 n>3f 时,在请求不超时的情况下,可以保证整 个系统共识的正确性。所以,假设网络中某节点是拜占 庭节点的概率是 P,而正常节点的概率是 1-P, 那么存在 n 个节点的区块链网络中存在f个拜占庭节点的概率可以用二项分布表示如式(11)所示 ：

　　另外,当区块链系统的拜占庭节点的个数f 是满足 3f ≤ n 时, PBFT 每一个共识阶段存在节点响应超时, 也会导致区块认证失败,因此假设每阶段其最大认证时 间为 Tmaxj (j=1.2.3.4.5), 由式 (2) 得到关于共识算法 PBFT 每阶段响应时间超时的概率如式(12)所示 ：

　　其中 rz 为每阶段平均验证时间所对应的节点的计 算能力。假设在共识阶段过程中,忽略视图切换,当存 在某一阶段执行时间响应超时,则认为整个共识是失 败的。那么,共识过程中某阶段能够被执行,前提条 件是之前阶段都已被成功执行。因此,在 PBFT 共识 算法中,各阶段出现区块认证失败的概率如式(13)、 式(14)所示 ：

　　其中 i=2. 3. 4. 5. 所以, 区块认证失败的总概率 如式(15)所示 :

　　2.1.3 通信复杂度

　　从图 1 可以看到,在 PBFT 的 Request 阶段,客户端 向主节点发送区块共识请求, 其通信复杂度为 1 ;在 PBFT的 Pre-prepare 阶段,主节点向副节点进行广播,其通信 复杂度为 n-1 ;在 PBFT 的 Prepare 阶段,子节点们验证来 自主节点的区块信息后,将验证结果进行全网广播,其通 信复杂度为 (n-1)2 ;同理, 在 PBFT 的 Commit 阶段, 通 信复杂度为 (n-1)2.最后,在 PBFT 的 Prepare 阶段,通信复 杂度为 n-1.因此整个共识过程的时间复杂度为 ：2n2-2n。

　　2.2 基于分组的 PBFT 共识算法 G-PBFT

　　PBFT 算法的复杂度为 o(n2),随着节点的增加,通 信复杂度会急剧增加,将会导致大量的网络资源被占 用, 当节点数达到 100 左右时, 系统性能大幅度下降, 网络压力巨大。因此也有许多学者针对 PBFT 节点可扩 展性差问题进行研究,相应地提出了基于分组的 PBFT 优化方法。本小节探讨将分组与 PBFT 共识算法相结合 后的性能变化,具体过程如图 2 所示,将所有节点按照 评判标准分成若干个组,每个组的节点先进行局部的内 部共识。待局部共识完成后,每个组的主节点将携带组内共识结果进行一轮全局共识,最后将共识结果返回给 客户端。

　　2.2.1 交易吞吐量和交易认证失败概率

　　相比于常规的 PBFT 过程,基于分组的 PBFT 共识 算法中参与共识的节点数量减少了,因此设参与共识的 节点在每一个阶段所需要计算的数据集大小为 Ni'。

　　假设节点们计算能力 rj 不变的情况下, 共识过程中 每一阶段每个节点的验证时延表示为 T 'mkj=Nj'/rk ( 其中 k=1.… ,7.j=1.2.… ,n), 其中 k 代表共识过程的 7 个阶 段, j 代表节点。

　　在 Global-request 阶 段, 参 与 共 识 的 主 节 点 只 需要接收来自客户端的信息请求与常规 PBFT 中的 Request 一样,故可以近似认为计算量 N1' ≈ N1.根据 公式 (3),该阶段的平均验证时间 T1'=max(T 'mkz),其中 T 'mkz 为主节点集验证时间集合。

　　在 Local-Pre-prepare 阶段, 组 内 的副节点只需 要接收来自组内主节点的信息与常规 PBFT 中的 Pre- prepare 一样,所以可以近似认为计算量 N2' ≈ N2.据 公式 (4),该阶段的平均验证时间 T2' ≈ T2.

　　在 Local-prepare 阶段, 设 n 个节点的区块链网络 分成了 k 组,即每组有 n/k 个节点,那么该阶段下原本 是 n 个节点的广播,基于分组的优化后,变成了 n/k 个 节点的全网广播,则参与共识的节点所需要计算的数据 集大小可以近似表示为 N3' ≈ N3/k,根据公式 (5),该阶 段的平均验证时间 T3' ≈ T3/k。

　　在 Local-commit 阶段, 与 Local-prepare 阶段类 似,基于分组的优化后,变成了每个组 n/k 节点的全网 广播,则每个组中参与共识的节点所需要计算的数据集 大小可以近似表示为 N4' ≈ N4/k,根据公式 (6),该阶段 的平均验证时间 T4' ≈ T4/k。

　　在 Local-reply 阶段,每个组的主节点都将接收到 组内副节点发送的共识结果,那么主节点所需要计算的 数据集大小可近似于 k× 节点 PBFT 的 Reply 阶段的计 算量 N5.故参与共识的节点所需要计算的数据集大小可 以近似表示 N5' ≈ kN5/n,根据公式(7),该阶段的平均 验证时间 T5' ≈ kT5/n。

　　在 Global-commit 阶段,参与共识节点的计算量 可近似于 k×PBFT 节点的 Commit 阶段的计算量 N4. 因此参与共识的节点所需要计算的数据集大小和平均验 证时间可近似表示为 N6' ≈ kN4/n ，T6' ≈ kT4/n。

　　而在 Reply 阶段,基于分组的优化后,只需要 k 个 主节点的共识结果,无需 n 个节点的所有共识,因此参 与共识的节点所需要计算的数据集大小和平均验证时间可近似表示为 N7' ≈ kN5/n ，T7' ≈ kT5/n。

　　那么,基于分组的区块链系统的平均区块产生时延 可以表示为如式(16)所示 ：

　　2.2.2 区块认证失败概率

　　通过分组的方式将 n 个节点划分到 k 组后每一个共 识阶段已变成了 n/k 个节点的共识,但是每个组要保证 3f ' ≤ n/k( 其中f ' 为每个组可容许的最大拜占庭个数 ) 满足。因此在 n/k 个节点的区块链网络中存在f ' 个拜占 庭节点的概率可以用二项分布表示为如式(19)所示 ：
　　另外,在 PBFT 每一个共识阶段存在节点响应超 时,也会导致区块认证失败。因此假设每阶段最大认证 时间为 T 'maxj=kTmaxj/n (j=1.2.3.4.5.6.7), 由公 式(12)公式 (13) 得,每阶段响应时间超时的概率和各 阶段出现区块认证失败的概率如式(20) - 式(22)所示 ：

　　其中 rz 为每阶段平均验证时间所对应的节点计算能力。

　　其中j=2. 3. 4. 5. 6. 7.因此,区块认证失败的 总概率为如式(23)所示 :

　　2.2.3 通信复杂度

　　从图 2 可以看到, 在 Global-request 阶段, 客户端向 每个组主节点发送区块共识请求,总通信复杂度为k ;在 Local-Pre-prepare 阶段,每个组主节点向组内副节点进行 广播,总通信复杂度为 n-k ;在 Local-Prepare 阶段, 组内 子节点们验证信息无误后,将验证结果进行全网广播,总 通信复杂度为 k((n-k)/k)2; 同理, 在 Local-commit 阶段, 通 信复杂度为 k(n/k)2 ;在 Local-reply 阶段,组内主节点收 到副节点的信息反馈后,准备进行全局的 Commit 广播, 通信复杂度为k((n-k)/k) ;在 Global-commit、Global-reply 阶段,通信复杂度与 k 个节点的 Commit、Reply 阶段一样,故通信复杂度分别为 (k-1)2. k。因此整个共 识过程的通信复杂度为 ：2/k n2+n+k2-k+1.

　　2.3 基于分组和信誉的 PBFT 共识算法 CR-PBFT

　　网络共识过程的工作效率与安全主要依靠网络中节 点贡献自身计算能力来达到的。在 PBFT 共识机制中, 能容许的最大拜占庭的节点数为f,( 其中 3f ≤ n)。因 此,在 PBFT 共识过程中,节点工作的积极程度将会很 大程度上影响区块链系统的性能。另外,由于 PBFT 共 识机制缺乏惩罚机制,纵容作恶节点参与共识过程,将 会耗费巨大的网络资源才能达成共识,需要提出一个节 点信誉评分机制,通过限制节点的恶意行为,提高区块 链共识的高效性与可靠性。

　　具体过程如下,在共识之前,每个节点有一个初始 信誉值 Value,每次共识之后,系统会根据节点在这一 轮的表现对节点信誉值进行加减。节点表现的评判标准 是节点的计算能力,当节点的计算能力低于平均水平时, 其节点信誉值减 a ;若计算能力高于平均水平,则节点 信誉值加 b。当节点信誉值 Value 低于阈值 Threshold 时,将判定节点为拜占庭节点并禁止参加之后的共识过 程。则节点信誉变化可以表示为如式(24)所示 ：

　　2.3.1 交易吞吐量和交易认证失败概率

　　当存在节点 i 被判定为拜占庭节点时,则该节点会 被剔除共识过程。由于参与共识节点中所需要计算得数 据集的大小 Nj''=Nj', 在节点计算能力不变的情况下,共识的每一阶段每个节点的验证时延表示为 Tmkj ''=(Nj')/rk ( 其中 k=1.2.… ,i-1.i+1.… ,n,j=1.2.3.4.5.6.7)。根据公式(3)式(7)可知,在每个共识阶段,平均验证时间 分别为如式(25) - 式(31)所示 ：

　　其中, Tmk1'' 为 Global-request 阶段每个组的主节 点验证时间集合。

　　其中, T ''mk5 为 Local-reply 阶段每组的主节点验证 时延集合。

　　那么,基于分组和信誉的区块链系统的平均区块产生时延可以表示为如式(32)所示 ：
　　因此,基于分组和信誉的区块链系统的 TPS 和交 易失败概率可以计算如式(33)、式(34)所示 ：

　　2.3.2 区块认证失败概率

　　与公式 (18) 相同, 在 n/k 个节点的区块链网络中存 在f ' 个拜占庭节点的概率可以用二项分布表示为如式 (35)所示 ：

　　另外,在 PBFT 每一个共识阶段存在节点响应超时, 也会导致区块认证失败。因此假设每阶段其最大认证时 间为 T ''maxj=kTmaxj/n (j=1.2.3.4.5.6.7), 由 公 式 (12)、 公式 (13)、公式 (14) 得到关于共识算法 PBFT 每阶段 响应时间超时的概率和各阶段出现区块认证失败的概率如是(36) - 式(38)所示 ：

　　其中 rz 为每阶段平均验证时间所对应的节点的计算 能力。

　　其中j=2. 3. 4. 5. 6. 7.因此,区块认证失败的 总概率如式(39)所示 :

　　2.3.3 通信复杂度

　　假设在区块链网络中,存在 t 个节点被判定为拜 占庭节点(假设若所有拜占庭节点全在一个组内,则 t ≤f '),则该节点会被剔除共识过程。那么在 Global- request 阶段, 客户端向每个组内主节点发送区块共 识请求,其通信复杂度为 k ;在 Local-Pre-prepare 阶 段,组内主节点向副节点进行信息广播,其通信复杂度 为 n-k-t ;在 Local-Prepare 阶段, 组内副节点验证来 自主节点的区块信息后,验证结果后进行全网广播,总 通信复杂度为 k((n-k-t)/k)2.同理, 在 Local-Commit阶段 , 组内所有节点验证完毕,准备将执行结果发送给 主节点,总通信复杂度为 k((n-t)/k)2 ;在 Local-reply 阶 段,组内主节点收到副节点的信息反馈后,准备进行全 局的 Commit 广播,通信复杂度为 n-k-t ;在 Global- commit、Global-reply 阶段,总通信复杂度与 k 个节点 的 Commit、Reply 阶段一样,因此通信复杂度分别为 (k-1)2. k。因此整个过程的总通信复杂度为 ：1/k(2n2- 4nt+2t2)+k2-k+1.

　　3 仿真与结论

　　3.1 区块链系统的吞吐量和区块链交易认证失败的概率

　　本节将从交易吞吐量 TPS、交易失败概率、区块认证 失败概率和通信复杂度四个方面来评估 PBFT 以及优化的 PBFT 共识算法的性能。实验环境如下 ：硬件环境为 CPU i7-6700. 内存为 16GB, 操作系统为 Windows10 64bit, 软件环境为 MATLAB R2021b。假设区块链网络中有 20 个节点(n=20),其中有两个拜占庭节点(t=2), 选 择节点 1. 6. 11. 15 为每个组的初始主节点, 同时将 所有节点按顺序分成四组(k=4),其中正常节点的计算 能力为 rj 在 [139.149] 之间随机产生,而拜占庭节点的 计算能力为 80. 90 低于正常节点的计算能力。交易的 排队队长为 Q=255.共识限制条件 θ=0.01.PBFT 的 每一阶段参与节点所需计算量设为 N1=16. N2=16. N3=48. N4=48. N5=16.系统可容许的最大拜占庭数量 f=6 以及每组可容许的最大拜占庭节点数量f '=1.

　　首先,为了体现网络负载的影响,其交易到达速率 从低负载逐渐变化到高负载区制。如图 3 所示为 PBFT、 G-PBFT、GR-PBFT 吞吐量的性能对比。可以看出,它 们都在一定的交易速率下达到最大值,因为它们受到了 区块所能容纳最大交易的限制。另外, GR-PBFT 共识 吞吐量最大,其次是 G-PBFT,最后是常规的 PBFT。 相比于常规的 PBFT,基于分组的优化方法明显较好, 因为基于分组的 PBFT 减少参与共识阶段的节点数,使 得参与共识的节点所需要处理的数据量大大降低的同时通信复杂度也急剧减少,从而得到较低的区块共识时间 和较高的吞吐量。而相比于 G-PBFT, GR-PBFT 在吞 吐量方面达到最佳。因为在每次共识之前,系统通过节 点的信誉分来判断该节点是否有权力参与共识过程,这 一方面又进一步降低了参与共识的节点数 ;另一方面, 将拜占庭节点剔除区块链网络,能减少系统为了达成共 识所消耗的资源以及缩短共识时间,从而进一步提高了 吞吐量 TPS。

　　如图 4 所示,当交易到达速率从低负载到高负载 时,交易失败概率也将随着上升。由于节点的队列缓存 有限,随着交易到达速率的增加,网络逐渐进入了高负 载模式,当缓冲区满后,新到达的交易将会被舍弃,交 易也将失败,因此交易失败概率也随着上升。另外,随 着优化方法的提出,其区块认证平均时延 TPBFT 也将进 一步降低,那么单位时间内,系统中产生块的速率也将 增加,从而区块链网络能在更高的负载下保持稳定性, 因此交易认证失败概率也比常规的 PBFT 更低。

　　3.2 区块认证失败概率

　　实验仿真可知,常规的 PBFT 区块认证失败概率最 低为 0.0030. 其次是 GR-PBFT, 失败概率为 0.1879. 最高是 G-PBFT,失败概率为 0.3871.常规的 PBFT 区 块认证失败概率最低,因为通过聚类的优化方法,虽然 可以减少参与共识的节点来减少节点间的通信,但是它 会带来新的问题,即系统所能容许的恶意节点数量会降 低,系统内达成共识的条件会更加严苛,导致区块认 证失败的概率会上升。而 GR-PBFT 优化方法,相比于 G-PBFT 来说, 由于在共识之间会剔除拜占庭节点, 虽 然系统所能容许的恶意节点数量没有变,但是节点共识 过程的可信度会增加,从而导致区块认证失败概率下 降,但远不及达到常规的 PBFT 认证失败概率,因为可 容许的恶意节点数量对区块认证失败的影响是主要的。

　　3.3 通信复杂度

　　如图 5 所示, GR-PBFT 通信复杂度最少,其次是G-PBFT, 最后是 PBFT 共识算法。可以知道, 通过分 组的方式,来减少参与共识的节点,从而减少节点间 的通信,达到减少通信复杂度的效果。而 GR-PBFT 效 果,相比于 G-PBFT 来说,它能在共识之前剔除掉拜占 庭节点,进一步地减少了参与共识的节点,减少网络资 源,从而达到进一步降低复杂度的效果。

　　3.4 总结

　　通过仿真结果,可以知道 PBFT、G-PBFT 以及 GR-PBFT 它们之间的性能对比。采用分组的方法降低 PBFT 的通信复杂度和交易吞吐量,与 PBFT 性能相 比,优化效果显著,但这一种好处是以牺牲系统内可容 许的最大拜占庭节点数为代价的,这将会增加区块认证 失败概率。而基于分组 + 信誉评分 (GR-PBFT) 的方式, 在 G-PBFT 的基础上,进一步地优化了区块链系统的性 能,同时降低了区块认证失败的概率。另外,可以了解 到 PBFT 共识算法容易受到网络资源(节点计算能力、 区块容量)和网络负载(交易到达速率)条件的影响, 它们是影响区块链系统性能的关键参数。

　　4 结语

　　本文将对 PBFT、G-PBFT 和 GR-PBFT 共识过程 进行理论分析和结果仿真。同时,通过交易吞吐量、交 易失败概率、区块认证失败概率和通信复杂度等主要性 能指标进行三者性能对比。另外,通过这项工作,可以 很容易知道网络参数对区块链性能的一些限制,也可以 了解到几种常规的 PBFT 优化方法将会对区块链系统的 性能产生怎样的影响。这项工作可以为进一步的基于区 块链的物联网的应用,提供相应的理论参考依据。

　　参考文献

　　[1] Elhachmi Jamal,Kobbane Abdellatif.Blockchain- based Security Mechanisms for Internet of Medical Things (IOMT)[J].International journal of Computer Networks & Communications,2022.14(6).
　　[2] 范思嘉.基于区块链的可信物联网研究[D].电子科技大学,2021.
　　[3] Auhl Zachary,Chilamkurti Naveen,Alhadad Rabei, et al. A Comparative Study of Consensus Mechanisms in Blockchain for IoT Networks[J].Electronics,2022.11(17).
　　[4] 曹傧,聂凯君,彭木根,等.无线网络中区块链共识算法的开销 分析[J].北京邮电大学学报,2020.43(06):140-146.
　　[5] XU G X,LIU Y,KHAN P W.Improvement of the DPoS Consensus Mechanism in Blockchain Based on Vague Sets[J].IEEE Transactions on Industrial Informatics,2020. 16(6):4252-4259.
　　[6] Meshcheryakov Yaroslav,Melman Anna,Evsutin Oleg,et al.On Performance of PBFT Blockchain Consensus Algorithm for IoT-Applications With Constrained Devices[J].IEEE ACCESS,2021:9.
　　[7] HUANG Y,ZHANG J.DUAN J,et al. Resource Allocation and Consensus on Edge Blockchain in Pervasive EdgeComputing Environments[C]// 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS). IEEE,2019:1476-1486.
　　[8] 张亮,刘百祥,张如意,等.区块链技术综述[J].计算机工程, 2019.45(05):1-12.
　　[9] 靳世雄,张潇丹,葛敬国,等.区块链共识算法研究综述[J].信 息安全学报,2021.6(02):85-100.
　　[10] TIAN Z H,ZHAOJ D.Overview of Blockchain Consensus Mechanism for Internet of Things[J].Journal of Computer Applications,2021.41(4):917-929.
　　[11] SALIMITARI M.CHATTERJEE M.FALLAH Y.A Survey on Consensus Methods in Blockchain for Resource- constrained IoT Networks[J].Internet of Things,2020.11: 1-19.
　　[12] 刘炜,阮敏捷,佘维,等.面向物联网的PBFT优化共识算法 [J].计算机科学,2021.48(11):151-158.
　　[13] SI H,SUN C,LI Y,et al.IoT Information Sharing Security Mechanism Based on Blockchain Technology[J] Future Generation Computer Systems,2019.101(Dec.):1028-1040.
　　[14] BISWAS S,SHARIF K,LI F,et al.PoBT:A Light Weight Consensus Algorithm for Scalable IoT Business Blockchain[J].IEEE Internet of Things Journal,2020.7 (3):2343-2355.
　　[15] 袁勇,倪晓春,曾帅,等.区块链共识算法的发展现状与展望 [J]. 自动化学报,2018.44(11):2011-2022.
　　[16] NGUYEN G,KIM K.A Survey about Consensus Algorithms Uused in Blockchain[J].Journal of Information Proccessing Systems,2018.14(1):101-128.
　　[17] GAN B,WANG Y J,WU Q W,et al.EIoT-PBFT:A Multi- stage Consensus Algorithm for IoT Edge Computing Based on PBFT[J].Microprocessors and Microsystems,2022:95. [18] 李博,向海昀,张宇翔,等.面向食品溯源场景的PBFT优化算 法应用研究[J].计算机科学,2022.49(S1):723-728.
　　[19] 方维维,王子岳,宋慧丽,等.一种面向区块链的优化PBFT共 识算法[J].北京交通大学学报,2019.43(05):58-64.
　　[20] 刘泽坤,王峰,贾海蓉.结合动态信用机制的PBFT算法优化 方案[J].计算机工程,2023.49(02):191-198.
　　[21] 韩镇阳,宫宁生,任珈民.一种区块链实用拜占庭容错算法 的改进[J].计算机应用与软件,2020.37(02):226-233+294.
　　[22] CHEN Y N,LI M,ZHU X Het al .An Improved Algorithm for Practical Byzantine Fault Toleranceto Large- scale Consortium Chain[J].Information Processing and Management,2022(2):59.
　　[23] LIU W,ZHANG X H,FENG W L,et al.Optimization of PBFT Algorithm Based on QoS-Aware Trust Service Evaluation[J].Sensors (Basel, Switzerland),2022.22(12): 4590-4595.
　　[24] 张正辉. 面向物联网的区块链共识机制的性能分析与优化 算法研究[D].重庆:重庆邮电大学,2021.
　　[25] LIU S N,ZHANG R H,LIU C Z,et al.Improvement of the PBFT Algorithm Based on Grouping and Reputation Value Voting[J].International Journal of Digital Crime and Forensics(IJDCF),2022.14(3):1-15.
 
关注SCI论文创作发表，寻求SCI论文修改润色、SCI论文代发表等服务支撑，请锁定SCI论文网！

文章出自SCI论文网转载请注明出处：https://www.lunwensci.com/jisuanjilunwen/62511.html