李无知

拜占庭环境

在拜占庭环境中，假设总节点数为N，恶意节点数为F，恶意节点的行为有两种:

• 一是收不到来自该节点的消息
• 二是该节点发送任意多的错误消息。

证明

不发送消息的节点是无法侦测的，在一个拜占庭容错环境中，某个节点在参与共识判断时，最坏情况要假设有F个未发送消息的恶意节点存在，我们标注为$latex F_{nomsg}$

总节点数为N, 能收到消息的节点数$latex N-F_{nomsg}$，得满足以下条件才能达成共识

$latex N-F_{nomsg}>F_{nomsg}$

即能收到消息的节点数得大于未收到消息的节点数

但收到$latex N-F_{nomsg}$个节点消息后，还不能得出结论，注意恶意节点的第二个行为，恶意节点可能发出错误消息，因此$latex N-F_{nomsg}$个节点中，最多可能包含F个恶意节点。

我们标注恶意节点为$latex F_{mal}$，诚实节点为$latex I$，此时：

$latex (N-F_{nomsg}=F_{mal} + I) >F_{nomsg} $
$latex (I=N-F_{nomsg}-F_{mal}) >F_{nomsg}$

Wait a minute

等等，咱们不是假设了最多F个恶意节点了吗？既然F个恶意节点$latex F_{nomsg}$已经出现在了等式右边，为什么还有另外F个恶意节点$latex F_{mal}$，这一共不是2F个恶意节点吗？

这是因为，从接收者的角度，他无法判断F的分布，F即可能是$latex F_{nomsg}$，也可能是
$latex F_{mal}$，要万无一失的得出正确结论的话，只有假设两个地方都存在F个错误节点，这也是很多人困惑的地方

结论

其中$latex F_{mal}$和$latex F_{nomsg}$都最多F个，因此

$latex N-F_{nomsg}-F_{mal} >F_{nomsg}$

等于

$latex N-F-F>F$
$latex N>3F$

即N至少为3F+1。