比特币系统解决拜占庭将军问题的方法时,工作量证明。
“拜占庭问题”(Byzantine Generals Problem)是分布式系统中的经典问题,它描述了在存在恶意节点或通信不可靠的情况下,如何达成一致决策。
一群拜占庭将军各自驻扎在敌方城市周围,他们只能通过信使通信。将军们必须达成一致,要么共同攻击,要么共同撤退。但:
- 有些将军可能是叛徒,会发送矛盾的信息。
- 即使大多数将军是忠诚的,他们也可能因为传来的信息被篡改而无法信任彼此。
在存在一些叛徒(最多 f
个)情况下,忠诚的将军必须达成一致决定,即满足以下两个条件:
假设有 3 个将军:
A 和 B 都收到 C 的消息:
那么 A 和 B 该怎么办?他们收到不同的情报,无法确定哪个是真的,这就导致一致性可能失败。
1982 年 Lamport 等人证明:
要在
n
个参与者中容忍f
个拜占庭错误节点,需要至少n ≥ 3f + 1
个节点。
换句话说:
f=1
)→ 需要至少 4 个将军。拜占庭问题是区块链、分布式系统、共识算法的核心问题之一。
算法 | 容错特性 | 使用例子 |
---|---|---|
PBFT(实用拜占庭容错) | 3f+1 节点容错 f 个恶意 | Hyperledger Fabric |
Tendermint | 拜占庭容错共识 + 区块链架构 | Cosmos 区块链 |
HotStuff | 改进型 PBFT,线性通信复杂度 | Facebook Diem(前Libra) |
Istanbul BFT | 面向以太坊的 PBFT 变体 | Quorum 企业链 |
比特币使用的是工作量证明(PoW),也能容忍拜占庭节点:
项目 | 说明 |
---|---|
问题核心 | 在有恶意节点时如何达成一致 |
最小节点要求 | n ≥ 3f + 1 |
应用场景 | 区块链、分布式数据库、投票系统 |
典型算法 | PBFT、HotStuff、Tendermint |