拜占庭将军问题快速理解

拜占庭将军问题快速理解

前面分析的Paxos和Raft对节点的前提假设是不作恶，只是偶尔可能不响应而已。而真实情况是节点可能会作恶（伪造消息），在这样的场景下，如何在众多节点中达成一致性问题，这是拜占庭将军问题所要讨论的。

拜占庭将军问题（Byzantine Generals Problem）

Leslie Lamport在1982年提出的虚拟模型，用来解释一致性问题。拜占庭作为东罗马帝国的首都，地域辽阔，在首都周边有众多将军负责城防，将军之间通过信使来传递消息，达成某些一致的决定。但由于将军中存在叛徒，叛徒会想尽一切办法干扰一致性的达成，甚至是达成叛徒想要的共识从而实现攻击。

拜占庭问题，假设节点总数是N，叛徒将军数为F，则当 N 》= 3F 1 时，问题才有解，共识才能达成，这就是Byzantine Fault Tolerant（BFT）算法。

快速理解案例一

假设将军总数3，叛徒将军数1.

提案人不是叛徒，提案人发送一个提案，叛徒收到后，回复不同的命令，对于第三个将军就收到两个相反的消息，也无法判断出谁是叛徒，系统无法达成一致。

image

提案人是叛徒，发送两个相反的提案给另外两个，另外两个收到两个相反的消息，无法判断究竟谁是叛徒，系统无法达成一致。

image

快速理解案例二

假设将军总数4，叛徒将军数1.

提案人不是叛徒，提案人发送一个提案，叛徒同样作恶，但受到的消息结果，能很容易就找出哪个节点是叛徒。从而快速达成共识。

image

提案人是叛徒，发送不同的提案给不同的节点，但其他三个节点之间进行通信后，他们自己也能达成一个共识。

image

Leslie Lamport证明，当叛徒不超过1/3时，存在有效的算法，不论叛徒如何折腾，忠诚的将军们总能达成共识。当叛徒超过三分之一时，则无法保证一定能达成一致性。

Byzantine Fault Tolerant算法

面向拜占庭将军问题的容错算法，解决的是网络通信可靠，但节点可能故障情况下的一致性达成。

最早由Castro和Liskov在1999年提出的Practical Byzantine Fault Tolerant（PBFT）是第一个得到广泛应用的BFT算法。只要系统有2/3的节点是正常工作的，则可以保证一致性。

PBFT算法包括三个阶段来达成共识：Pre-Prepare，Prepare和Commit。

流行方案思路

拜占庭将军问题之所以难解，在于任何时候系统中都可能存在多个提案（作恶成本很低），并且要完成最终的一致性确认过程十分困难，容易受到干扰。但是一旦确认，即最终确认，概率上是100%。

但比特币采用的方案就不是完全按照PBFT来的，比特币的区块链网络采在设计时提出了PoW（Proof of Work）算法思路，计算高难度的hash是为了限制在一段时间内整个网络中出现提案的个数（增加作恶成本），另外一个是放宽对最终一致性确认的需求，是约定好大家都确认并沿着已知最长的链进行延展，系统的最终确认是概率上的确认，不是100%。这样，有人想作恶，会付出很大的经济代价（超过系统一半的算力）。

后来各种PoX的算法，也是沿着这个思路进行改进，采用经济上的惩罚来制约破坏者。