拜占庭将军问题（实用拜占庭容错）
拜占庭将军问题是一个分布式系统中的协议问题，描述了当部分参与者（如将军）可能是恶意或叛徒时，如何保证所有参与者达成一致决策。此问题由莱斯利·兰伯特提出，是点对点通信中的基本问题，用于模拟在存在消息丢失的不可靠信道上通过消息传递达成一致性的困难。拜占庭将军问题提供了一个模型，反映了在硬件错误、网络阻塞或恶意攻击下，计算机和网络可能表现出不可预测的行为。拜占庭容错算法（BFT）旨在解决这类问题，确保在节点出错或行为恶意时，系统仍能正常运作。这种容错性表现在即使部分节点出现问题，系统也能继续执行大多数节点的共同决定。拜占庭容错机制是区块链、分布式系统等领域的重要组成部分，它确保了系统的安全性和活性。拜占庭容错算法通常要求系统中节点数量和身份预先确定，并需要在每次节点变化时对网络进行初始化。因此，它们不适用于像工作量证明（PoW）这样的开放网络。然而，基于BFT的权益证明（PoS）共识算法是一个例外，它结合了BFT和公有链的特性。
拜占庭将军问题
Lamport在其论文中描述了如下问题：
一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。
将军之间通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样每位将军根据自己收到的投票结果选择多数票进行进攻或撤退。
二忠一叛难题
假设有三位拜占庭将军，分别为 A、B、C。三位将军要决定的只有一件事情：「明天是进攻还是撤退」。为此将军们需要依据「少数服从多数」的原则投票表决，只要两个人意见达成一致就可以了。
举例一个投票情况：A、B 投票进攻，C 投票撤退。
- 那么 A 的信使传递给 B 和 C 的消息都是进攻。
- B 的信使传递给 A 和 C 的消息都是进攻。
- C 信使传递给 A 和 B 的消息都是撤退。
如此一来，三位将军就都知道进攻方和撤退方二者的占比是 2:1 了。显而易见，按照少数服从多数原则，C 也会进攻，最终三位将军同时进攻，战争获得胜利。
叛徒的目标是破坏忠诚将军们之间的一致性达成，让拜占庭军队收到损失。譬如将军 A 向将军 B、C 分别发送撤退的消息，将军 B 向将军 A、C 分别发送进攻的消息。如果将军 C 是叛徒，那么我们思考 C 该做什么才能让两位忠诚的将军做出相反的决定？
目前看来 撤退：进攻 = 1：1，无论 C 投哪一方，都会变成 2:1，这时候还是会形成一个一致性的作战方案。可是，作为叛徒，将军 C 肯定不会按常理出牌，于是将军 C 让信使告诉将军 A 要进攻，让另一个信使告诉将军 B 要撤退。至此：
- 将军 A 看到的投票结果是 进攻方：撤退方 = 2:1
- 将军 B 看到的投票结果是 进攻方：撤退方 = 1:2
按照少数服从多数的原则，忠诚的将军 A 单独冲向战场，结果当然是将军 A 寡不敌众，败给了敌人。
截止目前，我们是否发现：明明大多数将军都是忠诚的（2/3），却被少数的叛徒（1/3）耍得团团转？实质上，拜占庭将军问题恰恰在此：一致性的达成过程中，叛徒将军（恶意节点）甚至不需要超过半数，就可以破坏占据多数正常节点一致性的达成，这也是我们常说的二忠一叛难题。
Lamport 在论文中也给出了一个更加普适的结论：如果存在 m 个叛将，那么至少需要 3m+1个 将军，才能最终达到一致的行动方案
解决方案
口信消息型解决方案
首先，对于口信消息（Oral message）的定义如下：
- 任何已经发送的消息都将被正确传达。
- 消息的接收者知道是谁发送了消息。
- 消息的缺席可以被检测。
基于口信消息的定义，我们可以知道，口信消息不能被篡改但是可以被伪造。在口信消息型解决方案中，首先发送消息的将军称为指挥官，其余将军称为副官。对于 3 忠 1 叛的场景需要进行两轮作战信息协商，如果没有收到作战信息那么默认撤退。
- 第一轮 指挥官向 3 位副官发送了进攻的消息。
- 第二轮 三位副官再次进行作战信息协商，由于将军 A、B 为忠将，因此他们根据指挥官的消息向另外两位副官发送了进攻的消息，而将军 C 为叛将，为了扰乱作战计划，他向另外两位副官发送了撤退的消息。最终指挥官、将军 A 和 B 达成了一致的进攻计划，可以取得胜利。
指挥官为叛将的场景
- 在第一轮作战信息协商中，指挥官向将军 A、B 发送了撤退的消息，但是为了扰乱将军 C 的决定向其发送了进攻的消息。
- 在第二轮中，由于所有副官均为忠将，因此都将来自指挥官的消息正确地发送给其余两位副官。最终所有忠将都能达成一致撤退的计划。
这个解决方法，其实就是 Lamport 在论文中提到的口信消息型拜占庭将军问题之解（A Solution with Oral Message）：如果叛将人数为 m，将军人数不少于 3m+1，那么最终能达成一致的行动计划。值的注意的是，在这个算法中，叛将人数 m 是已知的，且叛将人数 m 决定了递归的次数，即叛将数 m 决定了进行作战信息协商的轮数，如果存在 m 个叛将，则需要进行 m+1 轮作战信息协商。这也是上述存在 1 个叛将时需要进行两轮作战信息协商的原因。
假设有n个节点其中有f个恶意节点，在此场景下达成一致的前提是n>3f
证明：一共n个节点，其中f个恶意节点，n-f个正常节点，节点必须在收到n-f个消息后做出决定（因为f个恶意节点可能全都选择不回复）节点收到的n-f个消息中可能有f个是假的，也就是说有n-f-f个真的，要想达成一致需要真实的消息大于虚假的消息，因此得出n-2f>f n>3f
实用拜占庭容错PBFT
拜占庭将军问题（实用拜占庭容错）
