IBM发布的PBFT白皮书中谈到从三个将军中识别叛徒的公式是如何来的？
IBM发布的PBFT白皮书中如下内容：如果系统中有3f+1个节点，那么PBFT可以容忍拜占庭服务器不超过f个。简单解释一下原因：假设有三个将军, 只有一个叛徒。如果A是叛徒，那么A可能会给B发出进攻，然后给C发出撤退的命令。当B和C互相同步信息的时候他们会发现两个不一致的信息。但是B和C谁也无法判断谁是叛徒，比如从B的角度来看，他无法判断A是叛徒或者C是叛徒。所以三个将军里有一个叛徒是无法解决的。为了确保正确，PBFT两两交互确定交集后才能确定一个非叛徒：因此由-(N-f)＋(N-f)-N>=f+1推导出N>=3f+1。
(N-f)＋(N-f)-N>=f+1 这个公式怎么来的？能否解释下？
3同行回答
拜占庭算法的本质是三阶段提交，具体步骤如下图PBFT两两相交确定一个非叛徒节点。已知网络中有N个节点，其中f个是拜占庭节点，这f个拜占庭节点的行为有2种 1).对请求不做相应 2).广播错误的消息到网络。 为了使整个网络仍然能运行，那么对某一个正确节点来说它只需收到N-f条消息就应该能执行接下来的交易,因为f个拜占庭节点可能不响应。这又会产生其他问题，因为这个节点收到的N-f条消息中可能包含了f条拜占庭消息(拜占庭节点网络响应快)。
以节点1(收到N-f条消息)和节点2(收到N-f条消息)收到的消息集为例做交集来确定一个非叛徒节点，由于交集中可能包含f个叛徒节点来的消息，所以交集中至少要有f+1个节点的消息才能确定有至少1个正确节点，因此 (N-f) + (N-f) -N >= f+1.
还有一种更为简单的理解方式，每个节点收到N-f条消息，这其中可能包含了f条拜占庭消息，根据少数服从多数原则，其中还包含至少f+1条正确消息才能做出正确的判断。因此N-f >= f + (f+1), 即 N >= 3f + 1
收起浏览2805
