区块链原理 / 系统课时

3f+1 为何只能容忍 f 个故障

3f+1 为何只能容忍 f 个故障

当验证者可能宕机、撒谎或给不同节点发送矛盾投票时,为什么经典 BFT 协议常要求至少 4 个节点才能容忍 1 个拜占庭故障?这里用法定人数的交集推导 3f+1 边界,并通过具体投票集合检查冲突提交的风险。

学习目标

  • 根据故障上限 f 算出最小节点数和提交门槛。
  • 用两组法定人数的交集判断是否必有诚实节点。
  • 区分安全性保证与网络条件下的继续提交能力。

从故障预算确定法定人数

假定验证者等权、成员集合固定、签名无法伪造,最多有 f 个节点可能任意作恶。经典 BFT 最小规模取 n=3f+1n=3f+1,提交法定人数取 q=2f+1q=2f+1;一个决定需要收集至少 q 个不同验证者的有效投票。

容忍故障 f 最少节点 n 提交票数 q 最多不投票节点
1 4 3 1
2 7 5 2
3 10 7 3

例如 7 个节点允许最多 2 个故障,即使这 2 个节点完全不响应,余下 5 个诚实节点仍能凑齐 5 票。这里的故障包含宕机与拜占庭行为;容忍数量不能按两种故障分别相加。

为什么交集必须包含诚实节点

同一成员集合中,两组各有 q 票的法定人数,交集至少有 2q−n2q-n 个节点。代入 n=3f+1n=3f+1 和 q=2f+1q=2f+1,最少交集为 f+1f+1。由于作恶节点至多 f 个,交集中必然有至少 1 个诚实节点。

以 A、B、C、D 四个验证者为例,提交集合甲为 {A, B, C},集合乙为 {B, C, D},交集 {B, C} 有 2 人。如果 B 作恶,C 仍诚实;只要诚实节点遵守对应阶段的投票及跨轮锁定规则,就不能为互相冲突的提交提供两份有效证明。

反过来,只有 A、B、C 三个节点却试图容忍 1 个拜占庭故障时,两组 2 票集合 {A, B} 与 {B, C} 只交于 B。若 B 双重签名,A 与 C 分别支持冲突区块,单靠 2 票门槛无法阻止双重提交。

四节点与三节点的 BFT 投票交集对比

用 Python 枚举最小交集

下面使用 Python 3 标准库枚举小规模节点的所有法定人数集合,检查最坏情况下的交集。这里验证的是票数条件,不是完整的 BFT 协议实现。

python
from itertools import combinations

def minimum_overlap(n, q):
    quorums = [set(group) for group in combinations(range(n), q)]
    return min(len(a & b) for a in quorums for b in quorums)

for n, f in [(3, 1), (4, 1), (7, 2)]:
    q = n - f  # 故障节点全部沉默时仍可收齐的票数
    overlap = minimum_overlap(n, q)
    # 交集超过 f,才能排除交集全部为拜占庭节点
    print(f"n={n} f={f} q={q} 交集={overlap} 安全交集={overlap > f}")

预期输出:

text
n=3 f=1 q=2 交集=1 安全交集=False
n=4 f=1 q=3 交集=2 安全交集=True
n=7 f=2 q=5 交集=3 安全交集=True

安全下界与活性边界

要排除两个冲突提交证据仅靠故障节点重叠,需满足 2q−n≥f+12q-n\ge f+1;要允许 f 个故障节点全不参与时仍可收齐票数,需满足 q≤n−fq\le n-f。合并两个条件得到 n≥3f+1n\ge 3f+1;在最小规模下,门槛恰好是 2f+12f+1。

这并不表示只要故障数不超过 f,网络就一定立刻出块。即使 7 个节点中仅 2 个失联,余下 5 个节点在持续分区或消息无限延迟时也可能暂时无法形成共同提交;经典部分同步 BFT 的活性还依赖网络最终恢复到有界延迟、轮次推进等条件。

实际检查一个等权 BFT 配置时,先核对成员数是否至少为 3f+13f+1,再检查提交证明是否来自足量且互不重复的验证者,最后检查跨轮锁定或等价安全规则。超过 f 个拜占庭节点时,不应继续宣称原有的确定性安全保证。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

3f+1 为何只能容忍 f 个故障

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通