基于社区发现的改进PBFT共识算法

Improved PBFT Consensus Algorithm Based on Community Discovery

摘要: 共识算法是区块链分布式系统的核心组成部分，它是通过遵循预设流程，使互不信任的节点最终实现数据一致性的关键算法。PBFT共识算法在这一过程中能够容忍一定数量的拜占庭错误节点。大规模区块链网络中，通过PBFT共识算法维护分布式账本的一致性，是区块链系统运行的关键。传统的PBFT共识算法通过多个节点间的交叉验证，防止恶意节点的篡改和欺瞒。然而，这种方式的共识过程复杂，在大规模网络中，共识效率低下，且无法有效应对恶意节点和故障节点的影响，导致网络的稳定性难以保证。本文提出一个基于社区发现的改进PBFT算法，通过节点间交易行为数据构建社交网络，根据节点间的业务关联度，利用Louvain社区发现算法进行社区划分。采用“先社区内共识，后社区间共识”的策略，降低大规模共识中的复杂度。实验结果表明，该算法能够显著降低大规模区块链网络的通信复杂度，缩短达成共识时间，提高系统的吞吐量。

Abstract: The consensus algorithm is the core component of the blockchain distributed system. It is the key algorithm that enables nodes that do not trust each other to ultimately achieve data consistency by following the preset process. The PBFT consensus algorithm can tolerate a certain number of Byzantine fault nodes in this process. In large-scale blockchain networks, maintaining the consistency of distributed ledgers through the PBFT consensus algorithm is the key to the operation of the blockchain system. The traditional PBFT consensus algorithm prevents tampering and deception by malicious nodes through cross-validation among multiple nodes. However, the consensus process of this method is complicated. In large-scale networks, the consensus efficiency is low, and it cannot deal with the influence of malicious nodes and faulty nodes, making it difficult to guarantee the stability of the network. This paper proposes an improved PBFT algorithm based on community discovery, constructs a social network through transaction behavior data between nodes, and uses the Louvain community discovery algorithm to divide communities based on the business correlation between nodes. We adopt the strategy of “consensus within the community first, then consensus between communities” to reduce the complexity of large-scale consensus. Experimental results show that this algorithm can significantly reduce the communication complexity of large-scale blockchain networks, shorten the time to reach consensus, and improve the throughput of the system.

1. 引言

区块链自“中本聪”(Satoshi Nakamoto)于2008年在论文《比特币：一种点对点电子现金系统》中首次提出以来，已引起了学者的广泛关注和深入研究[1]。区块链的巨大潜力已在供应链[2]、数字资产[3]、物联网[4]、金融[5]等多个领域得到实证。然而，比特币作为传统区块链在共识过程中需要消耗大量的资源保障区块链的安全和达到去中心化的目标，因此吞吐量相对较低，此外，比特币对于交易确认的延迟容忍度较高，通常需要数分钟到数小时来确认交易。相比之下，区块链的商业应用通常无法承担巨额资源消耗，且对吞吐量有更高的要求，特别在实时交易应用中，用户期望能够快速完成交易确认，因此需要更低的延迟。尤其是在大规模区块链网络中，对系统的吞吐量和延迟也提出了更高的要求[6]。但是，如何优化区块链的共识机制以适应大规模网络环境的研究却相对匮乏。因此，设计并实现一种能在大规模网络环境下支持高吞吐量和低延迟的区块链共识机制，已经成为了区块链研究和应用领域的重要课题[7]。

实用拜占庭容错算法(Practical Byzantine Fault Tolerance, PBFT)是BFT类共识算法之一，其可以处理节点的故障行为，且能够容忍一定比例的恶意节点[8]。PBFT算法将整个共识过程分为多个轮次。在每个轮次中，主节点提出提案，并通过多轮投票的方式使其他节点达成一致。在每个轮次的不同阶段，节点将发出投票以支持或反对提案。节点会等待来自多数其他节点的相同投票，以确定最终决策[9]。如果节点收到了不同的投票，它可以回退到之前的状态，以维护一致性。如果主节点出现故障或恶意行为，系统可以通过进行视图更改来选择新的主节点。保持系统的正常运行。然而，PBFT要求节点之间进行复杂的通信，包括多轮投票和消息的广播[10]。随着节点数量的增加，通信开销会显著增加，从而影响性能。如果主节点出现问题，需要进行更改，这会导致额外的开销和延迟，因为需要选举新的主节点并进行视图更改操作，降低了共识算法的效率[11]。综上所述，由于PBFT算法的通信复杂度高，以及单一主节点和对故障节点和恶意节点处理方式的问题，使得PBFT算法在大规模网络环境下的效率低下，无法限制故障节点和恶意节点，难以确保网络的稳定性[12]。

针对上述问题，学者们从以下两个方面进行改进：1) 代理机制，降低问题规模。2) 分组共识策略。学者们采用代理机制改进算法，从全网节点中选取部分节点参与共识，以此提高算法的效率。具体来说，文献[13] [14]利用节点交易的有效性筛选出高效诚实的节点；而文献[15]和[16]则分别运用改进的C4.5算法和异常检测技术来选择高效诚实节点。文献[17]采用可验证的伪随机排序技巧将共识节点数量限制为一常数，使这些节点在共识过程中互相验证交易。文献[18]引入了Ripple共识协议中的UNL概念，选定网络中超过20%的UNL节点作为共识节点。文献[19]则着重于信任机制，使用Eigen Trust算法建立高信任值的共识群体，确保低信任度的节点不参与共识，从而提高整体效率。而文献[20] [21] [22] [23]进一步探讨信任机制，提出了一个综合的信任模型，结合节点评分、历史记录和参与度计算节点的信誉，使节点筛选更为合理。然而，这些策略虽然能有效降低通信复杂性和提升网络的扩展能力，但也存在潜在的风险。首先，它们与区块链的去中心化原则相冲突；其次，经筛选的共识节点承担的工作量加大，可能引发资源分配不均和节点活跃度的下降；最后，这些算法降低了共识节点的作恶成本，增加了联合作恶的风险，进而增加了整体的网络安全风险。因此，在采纳此策略时，必须权衡其潜在风险。

同时，还有学者选择从分组策略着手，通过将全网节点分组，从而实现整体共识的拆分，先实现局部共识，再通过各局部之间的共识达到整体共识。具体地，文献[24]创新性地将Raft与PBFT算法结合，其中PBFT算法处理局部共识，而Raft算法负责处理局部之间的共识。文献[25]则选择按信任度将信任节点进行分组，这种策略显著地降低了通信复杂度，并成功地筛除了恶意节点。进一步地，文献[26] [27] [28] [29]利用联盟链的节点身份验证机制，选定G个节点作为预备组长，之后依据各节点对这些组长的响应速度进行分组。为了强化分组的透明性与可靠性，他们还构建了信誉模型与投票机制，使得组长的产生更依赖于节点的信誉值，这增强了可信节点的主导性，并有效地减少了异常节点担任组长的可能性。另外，文献[30] [31]提出利用节点的位置特征进行聚类分组。总体而言，这些策略既保持区块链的去中心化特性，又同时减少共识算法中的通信交互。然而，这些策略无论是依据节点对组长的响应速度还是位置特征进行分组，均未考虑到由于难以准确预知或控制各组节点间的交易模式与频率，可能导致组间的交易频率极高，而组内交易频率相对较低。这样的分布可能会导致大量的跨组共识请求，从而反过来抵消了采用分组策略带来的效率提升。因此，为了最大化分组策略的优势，仍需对节点的分组依据和交易模式进行深入的研究和优化。

本研究提出了一种针对大规模网络的改进PBFT算法。该研究采用节点的信用值和业务关联度作为重要考虑因素对区块链网络进行社区划分。节点信用值反映了节点自身特性的重要指标，而节点间的业务关联度则反映网络内在因素的重要指标。通过结合这两个属性，可以更有效地对网络进行社区划分，从而形成内部联系紧密，而与外部联系相对较弱的社区。这不仅提高了共识的效率，同时也增强了网络的安全性和稳定性。同时，这种方式有助于确保社区内节点的稳定性，并将不稳定节点的影响限制在其所在社区，从而减轻其对整个网络的影响。在共识策略方面，该研究对原有的一致性协议进行了改进，采用了先进行社区内部共识，再进行社区间共识的策略。在社区内部达成初步共识后，再与其他社区进行整体共识。这种策略不仅有效提高了共识的效率，还增强了整个网络的稳定性。

本文主要贡献如下：

1) 提出了一种基于社区发现的改进PBFT (G-PBFT)算法，引入了社区的概念，根据区块链网络节点之间的业务关联度进行社区划分，然后进行先社区内后社区间的共识，提高了在大规模网络环境下的共识效率，降低了通信复杂度。

2) 通过引入节点信用值到社区划分中，将信用值相近的节点划分到同一社区，减少信用值差别过大的节点划分到同一个社区，提高社区内部的稳定性。同时，将社区内信用值最高的节点作为共识的主节点，有助于提高共识的稳定性。

3) 对社区稳定性进行深入分析，从节点的自身属性和网络的内在属性出发，论述了采用以节点之间的业务关联度和节点信用值为作为社区发现算法的指标进行社区划分的稳定性，以及社区划分对整个区块链网络的共识效率和稳定性的影响。

4) 对提出的G-PBFT算法进行了实验评估，通过仿真实验验证了G-PBFT相比传统PBFT算法在通信复杂度、共识时间以及系统吞吐量等方面的优势。

2. 相关工作

2.1. PBFT算法流程

在1999年由Miguel Castro和Barbara Liskov提出PBFT算法[32]来提高原始拜占庭容错算法效率。算法由三个协议组成：一致性协议、检查点协议、视图更换协议。一致性协议旨在确保在分布式系统中的不同节点之间达成一致的共识，以确保数据的一致性和正确性，检查点协议旨在提高分布式系统的容错性和恢复性，视图更换协议用于处理拜占庭容错系统中的主节点故障或恶意行为。在一致性协议和检查点协议下，PBFT算法可以正常运行，而只有当主节点出错或者超时的情况下才会启动视图更换协议，以保持系统对客户端请求的响应。PBFT算法中有三种角色：客户端、主节点和从节点，具有f个故障或者恶意节点的容忍度。因此，为保障整个系统可以正常运转，需要有2f + 1个正常节点，系统的总节点数为：N = 3f + 1。而一致性协议是PBFT算法的核心，其流程如图1所示：

Figure 1. PBFT algorithm flow

图1. PBFT算法流程

传统PBFT算法一致性协议分为五个阶段：1) Request，客户端c向主节点p发送进行签名的消息；2) Pre-prepare，主节点收到客户端的请求，向其他节点广播主节点签名的pre-prepare消息；3) Prepare，其他节点对pre-prepare消息进行校验，广播校验后自己进行签名的pre-prepare以及同意进入下一阶段，当收到2f + 1个从节点同意进入下一阶段才能进入commit阶段；4) Commit，全部节点校验2f + 1个prepare消息，当确认消息与pre-prepare消息一致时，即进入下一阶段；5) Reply，节点完成Prepare阶段后，向客户端发送回复消息，客户端C只要收到f + 1个消息，表示客户端发起的请求已经达成全网共识，否则客户端需要判断是否重新发送请求给主节点。

2.2. Louvain算法

Louvain [33]算法是一种基于模块度的社区发现算法。其基本思想是在复杂网络中通过评估网络中社区结构的质量标准——模块度来识别节点的社区结构。一个高模块度的网络表示该网络的社区结构分布是紧密且合理的。

Louvain算法的基本过程如下：

1) 初始阶段：每个节点初始作为一个社区。

2) 局部优化：每个社区通过算法遍历每个节点，考虑将其与相邻节点合并至同一个社区，计算合并后带来的模块度变化，如果合并能够增加模块度，那么就进行合并，持续进行这一操作直至模块度无法进一步提高为止。

3) 社区划分：将上一步得到的社区视为单个节点并形成一个新的网络。社区之间的权重等于社区内部节点之间的权重之和。

4) 重复第2步和第3步，直到整个网络被合并成数个社区，即每个社区的模块度达到最大。

3. G-PBFT算法

3.1. 算法概述

在当今区块链网络中，特别是面对节点数量不断增加和交易请求日益复杂化的环境，实现高效且可靠的共识算法已成为一个紧迫和关键的问题。传统的PBFT (Practical Byzantine Fault Tolerance)算法在处理小规模网络时，以其优良的容错性和稳定性得到了广泛的认可。然而，在面对大规模节点的环境中，该算法的性能表现出明显的局限性。在仅有四个节点的情况下，PBFT算法就需要高达22次的通信交换，而随着节点数量的增加，这个数字会呈指数级别递增，使得整体通信效率大幅度降低。当我们将应用领域扩展到如大规模制造业这种大规模多主体场景时，如何有效提升PBFT算法的共识效率，成为区块链应用面临的主要挑战。本文提出了改进PBFT (G-PBFT)算法，该算法利用社区发现的思想，通过社区内共识和社区间共识两个阶段的共识，降低问题规模，从而解决大规模区块链网络中的共识问题。通过引入了基于模块度的社区发现算法——Louvain算法，对区块链网络进行社区划分。社区内的节点具有更强的相关性，因而在共识过程中更具有代表性。而通过最大化模块度划分的社区，可以保证社区内部的节点之间的联系更紧密，与其他社区节点的联系则相对较少。同时，为了保证社区网络的稳定性以及精确描述社区内节点之间的连接强度，我们引入了节点的信用值和业务关联度这两个关键度量因子。节点信用值反映了一个节点在区块链网络中的可信度，它包括该节点的历史行为的稳定性和可靠性。通过将信用值相近的节点分入同一社区，可以提高网络的安全性和稳定性。业务关联度主要反映了节点之间在业务层面上的关联程度。由于高度关联的节点更频繁地进行交易，所以将这些节点分配到同一社区可以减少跨社区的传输需求，并加快具体交易的确认速度。该算法通过引入节点信用值和业务关联度，在保障网络安全和稳定的同时，还提高了区块链网络的共识效率。G-PBFT算法流程如图2。

Figure 2. G-PBFT algorithm flow

图2. G-PBFT算法流程

3.2. 区块链网络模型构建

3.2.1. 节点与边的定义

在大规模制造产业的中，为了应用区块链实现跨域追溯，供应商、制造商、运输商、销售商等主体加入区块链网络，构成大规模区块链网络。我们使用无向图来表示区块链网络。在这个网络图中，制造产业中的供应商、制造商、运输商、销售商是区块链网络中的节点，产业中的每笔交易(例如，零部件采购、产品销售等)可以表示为一个边。

3.2.2. 边权重的定义

边的权重采用业务关联度表示，例如，两个节点之间的交易次数、交易金额和交易频率。在网络中，为了突显节点之间最近的业务关联度对总体的影响，引入时间衰减因子。然后，采用基于模块度的社区发现算法——Louvain算法，在网络中节点遍历其他节点，并选择最大化模块度增量的合并节点为一个新的社区。在最大化模块度之后，区块链网络就被划分成多个社区，这代表着划分出的社区内部的业务关联度高，而社区之间的业务关联度低。

3.3. 节点信用值与业务关联度

3.3.1. 节点信用值的定义与计算

节点信用值是由节点在共识算法中的历史行为的指标来表示的，考虑到节点在共识算法的数据难以计算，通过节点的共识参与度，节点的共识成功率的指标并分配权重计算出节点信用值。

节点i的信用值，可以表示为：

$w_i={\omega }_1{a}_1+{\omega }_2{a}_2$ (1)

其中，$w_i$ 代表节点i的信用值，${\omega }_1$ 、${\omega }_2$ 是信用值各指标的权重，$a_1$ 、$a_2$ 是节点各指标。

节点i共识参与度。可以表示为：

$a_1=\frac{C_i}{B_i}$ (2)

其中，$C_i$ 是节点i的共识次数，$B_i$ 是总共识次数。

节点i共识成功率。可以表示为：

$a_2=\frac{C{S}_i}{C_i}$ (3)

其中，$C{S}_i$ 是节点共识成功次数。

3.3.2. 业务关联度的定义与计算

业务关联度表示节点之间在交易上的关系程度的指标。首先，根据节点之间的交易次数、交易金额和交易频率等多个因素体现两个节点之间的业务关联度。其次，将交易次数、交易金额和交易频率等指标进行归一化。然后，根据这些因素在场景中的重要性分配权重再进行计算。最后，为了更精确地评估近期节点间业务关联度对总体业务关联度的影响，我们将每个共识周期内的业务关联度作为单独的个体来计算出总体业务关联度。

$G_{ij}{}^T=\alpha S_{ij}+\beta M_{ij}+\gamma F_{ij}$ (4)

其中，$W_{ij}^T$ 代表两个节点之间在一个共识周期内的业务关联度。$S_{ij}$ 是交易次数，$M_{ij}$ 是交易金额，$F_{ij}$ 是交易频率。$\alpha$ 、$\beta$ 、$\gamma$ 是权重系数。

在业务关联度的评估中，通过引入时间衰减因子来强调最近的节点之间的业务关联度，时间衰减因子可以由时间计算得到，例如使用指数衰减函数或者其他类型的衰减函数。衰减因子随着时间的增长而减小，因此最近的衰减因子较大，对总体业务关联度的比重也就更大。

$G_{ij}=G_{ij}{}^T*\text{e^}\left(-\frac{delt{a}_t}{T}\right)$ (5)

其中，$e\text{^}\left(-delt{a}_t/T\right)$ 是一个时间衰减因子，其中$delt{a}_t$ 代表现在的时间与每一轮共识完成的时间的差值，T是一个共识周期。时间衰减因子$e\text{^}\left(-delt{a}_t/T\right)$ 的值在0到1之间，其值随着$delt{a}_t$ 的增大而减小。这表示距离现在越近的业务关联度对整体的权重越大。

3.4. 基于Louvain算法的网络社区划分

Louvain算法是一种基于模块度的社区发现算法，其基本原理是最大化网络的模块度。它是一种分层的、贪心的优化方法，可以在大规模网络中有效地识别出社区结构。

3.4.1. 模块度的定义与计算

模块度(Modularity)是社区划分的一种重要度量，用于描述社区内部连接紧密度和社区间连接稀疏度的特性。它能够帮助我们理解网络的社区结构，衡量社区划分的质量。

模块度Q的定义为：

$Q=\frac{1}{2m}{\displaystyle {\sum }_{ij}\left[A_{ij}-\frac{k_i{k}_j}{2m}\right]*}\delta \left(c_i,c_j\right)$ (6)

其中，$A_{ij}$ 是节点i和j之间的边的权重，$k_i$ 和$k_j$ 是节点i和j的度(即与它们相连的所有的边的权重之和)，$c_i$ 和$c_j$ 是节点i和j所属的社区，$\delta \left(c_i,c_j\right)$ 是社区标签匹配函数，如果节点i和节点j在同一个社区，$\delta \left(c_i,c_j\right)=\text{1}$ ，否则$\delta \left(c_i,c_j\right)=0$ 。这能够保证只有在同一社区内的节点对才会对模块度有贡献。m是网络中所有的边的权重之和。Q的值在−1到1之间，Q越接近1表示社区划分越好，即同一社区内的节点间连接紧密，不同社区间的节点连接稀疏。

3.4.2. 基于Louvain算法的社区划分过程

Louvain算法是一种常用的用于大规模网络社区发现的算法，在初始化阶段，每个节点都是一个社区，然后在每次迭代过程中，算法都会尝试把每个节点移动到它的邻居社区中，如果这种移动可以带来模块度的增加，那么就执行这种移动。对所有节点重复此过程直到模块度无法进一步提高为止，使社区内达到最紧密的连接程度。

在本文中，考虑到将节点之间的业务关联度作为边的权重，同时引入节点信用值，需要使用加权的模块度定义，如下：

$Q^{\prime }=\frac{1}{2m}\left[{\displaystyle {\sum }_{ij}\left(\mu G_{ij}-\rho S_{ij}-\frac{k_i{k}_j}{2m}\right)*\delta \left(c_i,c_j\right)}\right]$ (7)

$S_{ij}=\sqrt{{\displaystyle \sum _{R=1}^N{\left(m_{iR}-m_{jR}\right)}^2}}$ (8)

其中，$G_{ij}$ 是边的权重，也就是节点之间的业务关联度；$k_i$ 和$k_j$ 是节点i和节点j的信用值，m是区块链网络中所有的边的权重之和，参数α和β可以用来调整业务关联度和信用值的影响权重。$S_{ij}$ 表示节点的属性相似度，指节点i和节点j在共识中的每一个信用周期R的信用值的相似度；$m_{iR}$ 和$m_{jR}$ 分别表示节点i和节点j的第R周期的信用值。因此，当信用值都高的节点之间的业务关联度高时，模块度会增加，这意味着算法会倾向于将这样的节点划分到同一社区。另一方面，当两个节点的信用值差距大时即使它们之间的业务关联度高，模块度也不会增加很多，这意味着算法不太可能将这样的节点划分到同一社区。

除此之外，为了保证每个社区的节点在平均值的范围内，需要在社区发现算法之后，进行一些额外的后处理步骤。例如，如果一个社区太大，可以尝试将它分割成几个较小的社区；如果一个社区太小，可以尝试将它与最近的其他社区合并。处理的方法在算法后引入一个惩罚项来惩罚过大或过小的社区。

定义一个新的模块度$Q^{″}$ ：

$Q^{″}=Q^{\prime }-\lambda {{\displaystyle \sum \left(n_c-n_{avg}\right)}}^2$ (9)

其中，$Q^{\prime }$ 是原始的模块度，$n_c$ 是社区c的大小，$n_{avg}$ 是平均社区大小，∑是对所有社区的求和，$\lambda$ 是一个正的惩罚系数。这个新的模块度会在最大化原始模块度的同时，尽量使每个社区的大小接近平均值。

在当Louvain算法尝试把一个节点i移动到另一个社区c时，会计算移动前后的模块度变化$\Delta Q$ ，具体的计算公式为：

$\Delta Q=\left[\frac{{\displaystyle \sum _{in}+k_{i,in}}}{2m}-{\left(\frac{{\displaystyle \sum _{tot}+k_{i,in}}}{2m}\right)}^2\right]-\left[\frac{{\displaystyle \sum _{in}}}{2m}-{\left(\frac{{\displaystyle \sum _{out}}}{2m}\right)}^2-{\left(\frac{k_i}{2m}\right)}^2\right]$ (10)

其中，${\displaystyle \sum {}_{in}}$ 是社区c内部边的权重之和，${\displaystyle \sum {}_{tot}}$ 是社区c所有边的权重之和，$k_i$ 是节点i所有边的权重之和，$k_{i,in}$ 是节点i到社区c的边的权重之和。

如果$\Delta Q>0$ ，那么就把节点i移动到社区c。通过这样的方式，Louvain算法可以考虑边的权重来寻找模块度最大的社区划分。同时，在每个社区中选择信誉值高的节点作为每个社区的主节点，提高算法的稳定性。

3.5. G-PBFT一致性协议描述

G-PBFT算法采用基于模块度的Louvain算法，在区块链网络中根据节点之间的业务关联度来发现节点关系紧密型的社区，进而将区块链网络划分为多个紧密型社区，然后通过社区内共识再进行社区间共识的方法达到全网共识。同时，引入节点信用值提高社区的稳定性和安全性，通过节点的信用值选择每个社区最高信用值的作为社区的主节点，而全网主节点由各个社区主节点随机选择。一致性协议是PBFT算法的核心，而G-PBFT算法的一致性协议对原协议各个过程进行一些优化和调整，其优化流程如下：

1) Request：

客户端C向各个社区主节点G发送请求。REQUEST：包含消息内容m，以及消息的摘要d (m)，o：请求的具体操作，t：发送请求时客户端追加的时间戳，c：客户端标识。最后，客户端对请求进行签名。

2) Pre-prepare：

每个社区主节点在收到客户端的请求后，需要校验客户端发送的请求消息签名是否正确。如果签名正确，社区主节点会给客户端发送的请求消息分配一个编号n，编号n主要用于对客户端的请求进行排序。然后广播一条<,m>消息给其他副本节点。v：视图编号，d：客户端消息的摘要，m：消息内容，同时，消息需要社区主节点进行签名。

3) Prepare：

社区内节点收到社区主节点的PRE-PREPARE消息，需要校验消息签名是否正确、是否已经收到了一条在同一view下并且编号也是n，但是签名不同的信息、消息中的d与m的摘要是否一致。如果请求校验正确，节点要向其他节点包括主节点发送一条消息，消息需要节点i进行签名。

4) Commit：

社区内节点收到PREPARE消息，需要校验消息签名是否正确、当前节点是否已经收到了同一视图v下的n、d是否和当前已收到消息中的d相同。如果请求校验正确，则当节点收到了2f + 1个验证通过的PREPARE消息，则向其他节点包括社区主节点发送消息，消息需要节点i进行签名。

5) In-reply：

社区主节点收到COMMIT消息，需要校验其他节点COMMIT消息签名是否正确、当前节点是否已经收到了同一视图v下的n、d与m的摘要是否一致。如果请求校验正确，则当社区主节点收到了2f + 1个验证通过的COMMIT消息，说明社区内的大部分节点已经达成共识。然后向各个社区主节点发送<, m>，v：视图编号，a：社区编号，d：客户端消息的摘要，m：消息内容，同时，消息需要社区主节点进行签名。

6) Out-parpare：

社区主节点收到其他社区主节点的IN-REPLY消息，需要校验消息签名是否正确、是否已经收到了一条在同一view下、社区编号是a并且消息编号是n，但是签名不同的信息、消息中的d与m的摘要是否一致。如果请求校验正确，社区主节点要向其他主节点包括网络主节点发送一条消息，消息需要社区主节点i进行签名。

7) Out-reply：

社区主节点收到IN-REPLY消息，需要校验消息签名是否正确、当前节点是否已经收到了同一视图v下的a和n、d是否和当前已收到消息中的d相同。如果请求校验正确，则当节点收到了全部社区主节点的验证通过的IN-REPLY消息，运行客户端的请求操作o，并返回消息给客户端，r：是请求操作结果，如果客户端收到全部社区主节点的IN-REPLY消息，说明客户端发起的请求已经达成全网共识，否则客户端需要判断是否重新发送请求给全网主节点。G-PBFT算法图3如下：

Figure 3. G-PBFT consistency protocol

图3. G-PBFT一致性协议

3.6. G-PBFT一致性协议描述

社区稳定性是评估社区划分结果质量的重要指标。本文通过改进的模块度保证了同一社区内的节点具有高度的业务关联度，即同一社区的节点间存在大量的交易，业务关联度高。因此，单个节点的行为变化，如交易频率、交易金额的波动，对整体社区的影响较小，从而增加了社区内部的稳定性。同时，本研究引入时间衰减因子强调节点之间最近的交易程度在社区划分中的影响，过去的交易对社区划分的影响逐渐减弱，从而降低了历史交易对社区划分指标的影响，使得社区划分结果能够更好地反映出区块链网络的最新状态，提高了社区划分的实时性，进一步提高社区的稳定性。除此之外，本文引入节点信用值作为关键因素。节点的信用值是基于其在共识过程中的历史行为来确定的，从而反映了节点在共识过程中的稳定性和可靠性。通过将信用值相近的节点划分到同一社区，避免信用值差别过大的节点划分到同一个社区，有助于提高社区内的共识效率，并增强社区的稳定性，因为这些节点在未来的共识过程中更可能表现出一致的行为，而信用值较高的节点划分到同一社区可以提高社区的共识效率，并增加社区的稳定性。反之，将信用值较低的节点划分到同一社区，虽然可能降低该社区的共识效率，但由于该社区的影响被限制在社区内，不会对整个网络产生较大影响。此外，通过信用值选择的社区内主节点能够有效提高社区间的共识效率和稳定性。

4. 分析和实验

4.1. 实验环境

本实验基于Go编程语言对G-PBFT和PBFT的共识流程进行了仿真模拟。实验环境为VMware虚拟机，Ubuntu 20.04.5系统和8GB内存。实验结果用Python对数据进行了处理。实验分别测试了总节点N为10、16、22、25、28和31的两种共识算法的时延和吞吐量。为了减少实验误差，实验重复进行了20次取平均值。本节从通信复杂度、时延测试、吞吐量三方面对两种算法进行对比。

4.2. 通信复杂度分析

设区块链网络总节点数为N，在PBFT共识算法的Pre-prepare、prepare、commit的通讯复杂度分别为(N-1)、N(N-1)、N(N-1)，则总通讯次数为：

$f\left(N\right)=1+N-1+N\left(N-1\right)+N\left(N-1\right)+N=2N^2$ (11)

G-PBFT算法将区块链网络分成M个社区，在Pre-prepare阶段通讯次数为(N/M − 1)、在prepare阶段通讯次数为N/M(N/M − 1)、在commit阶段通讯次数为N/M(N/M − 1)、在In-reply阶段通讯次数为N/M、在Out-prepare阶段通讯次数为M(M − 1)，则总通讯次数为：

$f\left(N\right)=M+\left(\frac{N}{M}-1\right)+\frac{N}{M}\left(\frac{N}{M}-1\right)+\frac{N}{M}\left(\frac{N}{M}-1\right)+\frac{N}{M}+M\left(M-1\right)+M=2{\left(\frac{N}{M}\right)}^2+M^2+M-1$ (12)

随着社区数量M的增加，我们观察到G-PBFT算法的通信次数有显著的降低趋势。具体如图4所示，从图中看出，随着区块链网络节点的增长，G-PBFT算法对通信次数的降低效果愈发显著，尤其在网络节点达到1000时。以1000个节点的区块链网络为例，将网络分为两个社区后，G-PBFT算法的通信次数降至PBFT算法通信次数的1/4。如果我们继续增加社区的划分，例如将网络分为四个社区，那么G-PBFT的通信次数将进一步降低，只有PBFT通信次数的1/16。如果我们更进一步将区块链网络划分为更多的社区，G-PBFT算法的通信效率提升将更为显著。比如将网络划分为八个社区时，G-PBFT的通信次数仅为PBFT通信次数的1/66；当网络划分为十六个社区时，G-PBFT的通信次数甚至可以降至PBFT通信次数的1/250。

由此可见，G-PBFT算法在处理大规模区块链网络时，通过对网络进行合理的社区划分，能够显著降低通信次数，并显著提高通信效率，其性能表现出了显著的优越性。G-PBFT和PBFT通信次数对比图如图4。

在传统的PBFT共识算法中，通信复杂度为O (N2)，其中N是区块链网络中的节点数量。然而，当我们引入基于社区发现的改进PBFT (G-PBFT)算法后，通信复杂度可以得到显著的降低。

在G-PBFT算法中，我们首先将整个网络划分为M个社区，每个社区内部含有N/M个节点。G-PBFT算法的共识过程分为两个阶段：社区内共识和社区间共识。在社区内共识阶段，由于只涉及社区内的节点通信，其通信复杂度将降为O ((N/M)^2)。随后，在社区间共识阶段，主要的通信过程发生在各个社区主节点之间，其通信复杂度为O (M^2)。

因此，总体而言，引入基于社区发现的G-PBFT算法后，通信复杂度将降低为O ((N/M)^2 + M^2)。为了在实际的区块链应用环境中实现最优的通信效率，我们需要根据应用的具体业务需求，以及社区内外通信复杂度的平衡，来合理地选择社区数量M。

Figure 4. Comparison of communication complexity between PBFT and G-PBFT

图4. PBFT和G-PBFT通讯复杂度对比

Figure 5. Consensus delay comparison between PBFT and G-PBFT

图5. PBFT与G-PBFT的共识时延对比

4.3. 共识时延

共识时延是从节点发送请求到整个共识过程完成所需的时间，可通过以下公式来表示：

$\text{Delay}=T_c-T_r$ (13)

其中，$T_c$ 是共识完成结束的时间，而$T_r$ 是节点发送请求的时间。共识时延是衡量共识算法性能的一个关键因素。时延越短意味着共识算法更高效。

在本实验中，PBFT算法的性能数据将作为基准标准，与G-PBFT算法进行综合对比。实验设计出不同网络规模，如节点数量为10、16、22、25、28和31，并在不同网络规模下进行了20次共识实验。采用20次实验数据的平均值进行比较，具体如图5所示。从图5的数据曲线中，我们发现PBFT算法的共识时延随着节点数量增加呈现出快速的上升趋势，在节点数量达到30个时，该时延升至约6秒。相对地，G-PBFT算法展示了更优异的性能：在划分为四个社区的情况下，其共识时延仅缓慢增长至3秒；而在划分为七个社区的情况下，该指标更是稳定在1.5秒。更重要的是，无论G-PBFT划分为四个社区还是七个社区，共识时延都没有因为节点数量的增加而显著上升。这一结果意味着G-PBFT算法能够维持较低的共识时延，从而提高整体区块链的运行速度。

4.4. 交易吞吐量

吞吐量(TPS, Transactions Per Second)是评价共识算法性能的关键指标之一，它表示每秒内可以处理的交易数量。该指标可用公式来计算：

$TPS=\text{ Transaction}/\Delta t$ (14)

其中，$\Delta t$ 为出块时间，Transaction即从$\Delta t$ 时间段内成功打包进区块的交易数量。在实验中，我们分别对PBFT和GBFT进行了20轮共识测试，500次交易的吞吐量测试。根据以上公式，我们计算出了两种算法的吞吐量，并将结果绘制在图6中。从图6可以明显看出，PBFT与G-PBFT算法的交易吞吐量都是随着节点数量增加而下降。在相同实验条件和相同数量的节点下，G-PBFT的交易吞吐量明显高于PBFT算法。当将网络划分为七个社区的G-PBFT算法的交易吞吐量也高于将网络划分为四个社区的G-PBFT算法。具体来说，PBFT随着节点达到30节点时就趋近于0，而将网络划分为四个社区的G-PBFT算法的交易吞吐量只是缓慢下降到250，将网络划分为七个社区的G-PBFT算法的交易吞吐量则下降到了280。这一结果意味着G-PBFT算法随着节点的增加依然保持较高的交易吞吐量，从而提升了整体系统的运行效率。

Figure 6. Comparison of transaction throughput between PBFT and G-PBFT

图6. PBFT与G-PBFT的交易吞吐量对比

5. 结论

本文提出了一种新型的共识算法G-PBFT，根据网络的内在因素业务关联度，采用社区发现算法进行社区划分，再结合节点信用值提高划分后的社区的稳定性，最后通过先社区内共识再社区间共识从局部共识到全网共识。该算法能在大规模区块链网络中实现高效的共识，从而能够推进区块链在制造领域的应用。本文研究主要以大规模制造业的区块链网络作为主要场景，未来还需要根据具体业务模式研究不同领域的网络构建和社区划分方法，把本文成果推广至类似的基于大规模主体协作的应用场景。