Lecture 3 原版讲义链接：https://timroughgarden.github.io/fob21/l/l3.pdf
Lecture 3 原版PPT链接：https://timroughgarden.github.io/fob21/slides/F21L3.pdf
注：标题中的“节点模拟”指的是在FLM不可能结果证明过程中，对手为了破坏协议所使用的一种策略，用类似虚拟机的技术虚拟出n个节点与其副本节点，试图让诚实节点以为自己正在和一个真实的节点进行交互。“不可区分性”指的是诚实节点无法区分自己正在和真实节点进行交互，还是在和对手所虚拟出的节点进行交互。
FLM不可能结果的意义在于，它证明了在无PKI的同步网络模型中，我们无法设计出一个协议能够同时满足终止性、一致性和有效性，除非做出一些必要的取舍。同时也深刻反映了密码学和可信设置（trusted setting）在协议设计中的重要性。计算机科学领域从一开始就有对于不可能性的证明，例如图灵的停机问题，NP完备性问题等。这些证明看上去是令人沮丧的，因为这意味着**我们无法既要又要，但它们给了工程师一个最底层的基础原则，从而避免工程师们在不可能的幻想中浪费时间——在设计协议和软件的时候，必须有所取舍**。
不可能结果/不可解结果，指的是在某些假设或条件下，某个问题采用任何算法或协议都不可能满足所有期望的性质。
定理3.1：[PSL 80, FLM 86] 当$f \ge \frac{n}{3}$时，不存在任何拜占庭广播协议能够在异步模型中同时满足终止性、一致性和有效性。$f$表示拜占庭节点的上界。
注：该定理最初由Pease、Shostak和Lamport于1980年在论文《Reaching Agreement in the Presence of Faults》中提出。
其中，确定性协议的定义：
该定理和上述Dolev-Strong协议不冲突（Dolev-Strong协议已被证明$\forall f \in N^*$是满足BB协议性质的），因为它们的假设不同。Dolev-Strong假设PKI存在，而FLM不可能结果没有PKI假设。但两者都使用了同步假设。
注：协议证明很重要，请读者务必不要跳过。
下述是FLM的证明（由M. J. Fischer, N. A. Lynch和M. Merritt在Distributed Computing 1(1):26-39, 1986上发表的论文"Easy impossibility proofs for distributed consensus problems"中证明）。
证明思路：
要证明这样的一个不可能结果是困难的。因为这样的协议的设计空间非常庞大，我们可以对协议有任意的设计，如果用枚举法来一一排除这些设计从而证明不可能结果，几乎是很难完成的任务。因此我们可以假设这个协议存在，这个协议同时满足了这些性质，然后将协议部署在一些节点上去运行，用黑盒测试的方式看看会发生什么？是否能导出矛盾？这样不就能利用反证法来证明不可能结果了吗！
为了使得课程时间长度在合理范围内，我们先做一些假设限制证明的范围。首先我们假设协议是确定的（deterministic protocol），不要引入随机性。并且先从简单的基本情况入手，例如从$n=3, f=1$开始，然后再想办法试证更一般的情况（留作读者的家庭作业）。
假设有三个节点分别是A、B和C节点（即上图中的顶点），用边表示两个节点之间有连接：即能够进行通信并且互相知道各自的IP地址。
假设A节点是拜占庭节点，那么A节点会给B节点（0）和C节点（1）发送不一致的消息，假设C节点是诚实的，那么C节点会将从A节点收到的消息（1）echo给B节点：
此时B节点会收到冲突的消息——从A节点那里收到了0，从C节点收到了1。
考虑另一种情况，假设C节点是拜占庭节点，而A节点是诚实的sender节点。A节点给B和C都发送0，而C节点给B节点发送1而非它收到的0。如下图：
此时B节点收到的消息依然是冲突的。
上述两种情况都是冲突的，因此B节点无法区分A节点和C节点到底哪个是拜占庭节点，也无法输出一个确定的值，即无法达成agreement。但是，当$n=4,f=1$时，B节点是可以输出一个确定的值的，此时不会违反agreement。
该证明使用反证法，假设定理不成立，即假设存在一个确定性的算法$\pi$使得协议能够在$n=3, f=1$的情况下满足BB协议的全部性质。通过推理得出该协议在满足全部BB协议性质的情况下与假设矛盾，得出该确定性的算法不存在。
命题：当$f \ge \frac{n}{3}$时，不存在任何确定性协议（deterministic protocol）能够在异步模型中实现同时满足终止性、一致性和有效性的拜占庭广播。
前提：
协议$\pi$约束条件：
$n=3, f=1$ -
$s$ 节点会告知其他节点自己是sender，并且会发送$private\ input\ v$ - 运行$\pi$协议的节点会获得3个IP地址，包括自己的IP地址和另外2个节点的IP地址
证明：
令$\pi$为一个确定性的BB协议（同时满足终止性、有效性和一致性，即termination、validity和agreement）。
构造一个网络结构如下：
通过观察可以发现，上述网络结构的实际节点数量超过前提约束的$n=3$，但并不违反协议$\pi$的约束，因为每个节点无法发现第4个节点的存在。
在这个六边形网络中，validity和agreement不能被定义。因此我们需要构造几种场景使得这两种性质能够被定义并推导出矛盾的结果，从而得证。
考虑下述三种场景：
I.
假设B和C'节点是$hns$节点，X节点是$fs$节点。
根据$\pi$协议的约束与假设，B节点和C'节点对X节点具体是什么样的节点是一无所知的，它们只能通过X的行为推断X是否是拜占庭的。
那么可以通过这样一种方式欺骗B和C'：让X节点模拟六边形拓扑中的A-C-B'-A'。可以想象，X是一台物理的计算机，而A节点、C节点、B'节点和A'节点都是X上的虚拟机。这些虚拟机节点根据$\pi$协议的定义，模拟运行$\pi$协议的行为，并且试图以C'所预期的A'行为与C'交互，以B所预期的A的行为与B交互。使得C'以为自己正在和A'交互，B以为自己正在和A交互。这种策略的目的是为了达成indistinguishability，即使得B和C'无法分辨自己处在什么样的环境中，是存在拜占庭节点的环境，还是没有拜占庭节点的环境。
推论1：由于$\pi$满足agreement，因此B和C'会输出同样的值$v_i$。
II.
假设A和B分别是$hs$节点和$hns$节点，X节点是$fns$节点。
X节点依照同样的策略：模拟C'-A'-B'-C节点，对A和B节点进行欺骗。
推论2：由于$\pi$满足validity，因此A和B都会输出0。
III.
假设A'和C'分别是$hs$节点和$hns$节点，X节点是$fns$节点。
X节点依照同样的策略：模拟B-A-C-B'节点，对C'和A'节点进行欺骗。
推论3：由于$\pi$满足validity，因此C'和A'都会输出1。
综上所述，推论2、推论3与推论1矛盾，故$\pi$协议不存在，命题成立。$\square$
为何FLM不可能结果与Solev-Strong协议对任意个$f$都可容忍的性质不冲突？
因为Solev-Strong协议成立的前提是存在PKI假设的，而FLM不可能结果的成立并不存在PKI假设。并且，当PKI存在时，FLM不可能结果就不成立。这种节点组成的网络是许可网络，亦即，节点知道与之连接的节点的IP地址和节点名称，并且节点知道与之连接的节点的公钥之假设，是一种称为“可信设置”（trusted setup）假设的一个实例。
但是，当我们把PKI假设附加到3.2所证明的FLM不可能结果所使用的环境设置上时，FLM不可能结果就不成立了。
如上图所示，除了3.2已有的假设外，我们对这个网络设置附加PKI假设。A节点和A'节点使用密钥对$(pk_A,sk_A)$，B节点和B'节点使用密钥对$(pk_B,sk_B)$，C节点和C'节点使用密钥对$(pk_C,sk_C)$
我们考虑3.2证明中的第一个场景：
如图，对手试图模拟A-C-B'-A'，但由于PKI假设中包含了“其他节点无法获取本节点私钥”，因此对手试图虚拟出B'节点和C节点来混淆网络是不可能的，因为B'节点和C节点无法虚拟出一个真实的B节点和C'节点的消息签名。如此一来，FLM不可能结果就无法成立。