摘要

高效且鲁棒的拜占庭容错（Byzantine Fault Tolerance, BFT）共识协议是联盟链应用的基础。现有协议在提案过程中，主节点通常需发送 $O(n^2)$ 数量的签名，严重制约了协议效率。部分协议虽实现了线性视图切换，即主节点仅需发送 $O(n)$ 数量的签名来证明提案的有效性，但这往往以牺牲积极乐观响应或增加一轮消息交换为代价。

针对上述问题，本文提出 Climber，一种同时满足线性视图切换、积极乐观响应与两阶段提交的 BFT 共识协议。首先，在视图切换时，新任主节点通过穷举未上锁承诺，在不增加提交阶段的前提下，向副本节点证明提案的有效性。其次，利用聚合签名技术，将同一视图内的未上锁承诺聚合成未上锁证书，使视图切换时的通信复杂度降至 $O(n)$。最后，引入恶意节点黑名单机制，使主节点仅需 $O(n)$ 的时间代价验证签名。仿真实验结果表明，与 Fast-HotStuff 等先进 BFT 协议相比，Climber 展现出更优的鲁棒性。

关键词： BFT共识协议；联盟链；线性视图切换；鲁棒性；Fast-HotStuff

1 引言

复制状态机（State Machine Replication, SMR）旨在确保分布式系统中的所有服务器节点，即使接收客户端请求的顺序存在差异，也能以一致的顺序执行这些请求，从而维持各节点状态机的一致性。为实现 SMR，Lamport 提出了 Paxos 共识协议。该协议从所有节点中选举一个主节点，由其负责对客户端请求进行排序并通过管道分发至副本节点。Paxos 能容忍节点故障宕机，但无法应对恶意节点的作恶行为。此类协议（如 Raft）被称为故障容错（Crash Fault Tolerance, CFT）协议。为解决 CFT 协议中的拜占庭将军问题，拜占庭容错（Byzantine Fault Tolerance, BFT）协议应运而生，其目标是在分布式系统中容纳一定数量的恶意节点。

首个 BFT 协议——实用拜占庭容错协议（Practical Byzantine Fault Tolerance, PBFT），通过两个提交阶段（PREPARE 和 COMMIT）及视图切换机制，确保在恶意节点数量少于总节点数三分之一的情况下，无论主节点是否为恶意，所有节点均能以一致顺序执行客户端请求。

自比特币诞生以来，区块链技术，尤其是联盟链的兴起，推动了 PBFT 的大规模应用。然而，PBFT 难以满足联盟链在大规模网络环境下对高吞吐量与低延迟的需求，制约了其发展。PBFT 性能不佳的主要原因有二：其一，在两个提交阶段中，所有节点均需广播消息，导致全网通信压力巨大；其二，每次视图切换后，新任主节点在 PRE-PREPARE 阶段需发送 $O(n^3)$ 个签名（其中 $n$ 为系统节点总数），且每个副本节点需验证 $O(n^2)$ 个签名。

在 BFT 协议的改进方面，SBFT（Scalable Byzantine Fault Tolerance）采用聚合签名技术，将法定人数证书（Quorum Certificates, QC）中的签名数量从 $O(n)$ 降至 $O(1)$，进而将新任主节点在 PRE-PREPARE 阶段所需发送的签名数量降至 $O(n^2)$，但副本节点验证签名的时间复杂度仍为 $O(n^2)$。Tendermint 与 Casper 放弃了大多数 BFT 协议所追求的积极乐观响应特性，这使得新任领导者在使用聚合签名技术的情况下，仅需发送 $O(n)$ 个签名即可推动协议运行，即实现线性视图切换，从而使频繁视图切换成为可能，更契合区块链的去中心化理念。

HotStuff 是首个同时满足线性视图切换与积极乐观响应的 BFT 协议。它定义了 PREPARE 阶段的法定人数证书（记为 PQC），并提出：若在视图切换时，主节点不再向副本节点证明视图编号最大的 PQC（记为 highPQC）的有效性，则可将 PREPARE 阶段主节点所需发送的签名数量及副本节点验证签名所需时间均降至 $O(n)$。然而，这需要额外增加一个提交阶段（PRE-COMMIT 阶段）以保证协议活性，即 HotStuff 包含三个提交阶段。Fast-HotStuff 指出，HotStuff 的流水线模式在遭受恶意分叉攻击时将严重影响系统性能，并通过仿真实验说明有必要放弃线性视图切换以确保在分叉攻击下的鲁棒性。尽管主节点在 PREPARE 阶段仍需发送签名以向副本节点证明提案有效性，但副本节点验证签名的时间可降至 $O(n)$。此外，Fast-HotStuff 声称在视图切换阶段可将节点验证签名的时间降至 $O(n)$，但未能解决主节点验证签名所需时间无法同步降至 $O(n)$ 的问题。

综上所述，在 PBFT、SBFT、Fast-HotStuff 等协议中，无法实现线性视图切换；而能够实现线性视图切换的 HotStuff 等协议中，主节点无法证明 highPQC 的有效性，导致需要增加提交阶段，降低了协议效率。

为此，本文基于超时副本节点建立未上锁承诺，新任主节点利用聚合签名技术将相同视图内的未上锁承诺聚合为未上锁证书。仅需通过 $O(c+1)$ 数量的签名，即可向副本节点证明 highPQC 的有效性，使主节点在视图切换时的签名发送量降至 $O(n + cn)$，在不增加提交阶段的同时，实现了 highPQC 有效性证明与线性视图切换。

此外，针对 HotStuff 等协议未考虑主节点验证签名所需时间的问题，本文引入了恶意节点黑名单机制。主节点在 NEWVIEW 阶段收集消息时，实时剔除提交错误签名或无效承诺的恶意节点，最终将主节点总验证签名时间优化为 $O(n + cn)$。图1为 Climber 的结构示意图。

2 本文主要贡献

本文的主要贡献包括以下三个方面：

1. 提出了一种新方法，使主节点在视图切换时以 $O(n + cn)$ 数量的签名代价向副本节点证明 highPQC 的有效性，以替代传统发送 $O(n^2)$ 数量签名的方法，称之为穷举证明。分析表明，$c$ 的大小取决于连续出现恶意主节点的数量。在恶意节点占系统节点总数三分之一的极端情况下，$c$ 的数学期望为 $1/2$，且其尾界上界呈指数衰减。

2. 分析了视图切换时主节点验证签名所需时间无法降至 $O(n)$ 的原因，并引入恶意节点黑名单机制以完善 Fast-HotStuff，使主节点在视图切换时的平均验证签名时间降至 $O(n + cn)$。

3. 基于穷举证明与完善 Fast-HotStuff 的方法，设计了 Climber——一个同时满足线性视图切换、积极乐观响应与两阶段提交三个特性的 BFT 协议，并分析了其安全性、活性及签名复杂度。

3 总结

随着区块链技术的兴起与应用，现有 BFT 共识协议难以满足大规模分布式网络对高吞吐量、低延迟及高鲁棒性的需求。为此，本文提出了一种具备线性视图切换与高鲁棒性的 BFT 共识协议——Climber。该协议首先构建未上锁承诺并生成聚合证书，通过穷举证明，在不增加提交阶段的前提下，实现了具有积极乐观响应的线性视图切换；在此基础上，引入恶意节点黑名单机制，将主节点视图切换的验证时间复杂性优化至线性级别，在提升效率的同时增强了鲁棒性。实验结果表明，本文提出的 Climber 具有低延迟、高吞吐量、高效性与抗分叉攻击的鲁棒性，有效突破了现有 BFT 协议的性能瓶颈，为高可用与抗攻击的分布式共识部署提供了新方案，有助于推动 BFT 协议的进一步发展。