拜占庭将军问题

比特币系统解决拜占庭将军问题的方法时,工作量证明。

bitcoin35
bitcoin36
bitcoin37

“拜占庭问题”(Byzantine Generals Problem)是分布式系统中的经典问题,它描述了在存在恶意节点或通信不可靠的情况下,如何达成一致决策


🏰 拜占庭将军问题原始描述

一群拜占庭将军各自驻扎在敌方城市周围,他们只能通过信使通信。将军们必须达成一致,要么共同攻击,要么共同撤退。但:

❓问题目标

在存在一些叛徒(最多 f 个)情况下,忠诚的将军必须达成一致决定,即满足以下两个条件:

  1. 一致性(Consistency):所有忠诚将军必须达成相同决定。
  2. 有效性(Validity):如果主将是忠诚的,那所有忠诚将军都应执行主将的命令。

⚔️ 举个例子

假设有 3 个将军:

A 和 B 都收到 C 的消息:

那么 A 和 B 该怎么办?他们收到不同的情报,无法确定哪个是真的,这就导致一致性可能失败。


📐 数学结论

1982 年 Lamport 等人证明:

要在 n 个参与者中容忍 f 个拜占庭错误节点,需要至少 n ≥ 3f + 1 个节点。

换句话说:


💡 在区块链中的应用

拜占庭问题是区块链、分布式系统、共识算法的核心问题之一

常见的解决算法:

算法 容错特性 使用例子
PBFT(实用拜占庭容错) 3f+1 节点容错 f 个恶意 Hyperledger Fabric
Tendermint 拜占庭容错共识 + 区块链架构 Cosmos 区块链
HotStuff 改进型 PBFT,线性通信复杂度 Facebook Diem(前Libra)
Istanbul BFT 面向以太坊的 PBFT 变体 Quorum 企业链

与比特币的关系:


✅ 总结

项目 说明
问题核心 在有恶意节点时如何达成一致
最小节点要求 n ≥ 3f + 1
应用场景 区块链、分布式数据库、投票系统
典型算法 PBFT、HotStuff、Tendermint