区块链原理 / 系统课时

异步网络为何无法保证确定终止

异步网络为何无法保证确定终止

两个共识节点长期收不到彼此的消息时,对方究竟已经宕机,还是网络只是很慢?本课通过三种消息调度场景,解释为什么节点无法仅凭沉默判断故障,以及 FLP 不可能性结论怎样限制确定性共识的终止保证。

学习目标

  • 区分异步网络中的消息延迟、节点崩溃与超时怀疑。
  • 用两个节点的三种执行场景解释一致性和终止性为何发生冲突。
  • 准确识别 FLP 定理的适用前提,并判断实际区块链系统如何获得有条件的最终性保证。

异步网络究竟不保证什么

考虑两个节点 A 和 B,它们需要就一个二进制值达成共识,候选值为 0 和 1。A 在本地发送消息后,B 可能立即收到,也可能等待 30 秒才收到。在完全异步模型中,协议不能假设消息延迟和节点处理时间存在已知的有限上界。

这里的异步并不等于消息必然丢失。我们甚至可以假设通信可靠,发出的消息不会被篡改,并且发往持续运行节点的消息最终能够送达,但无法保证具体送达时间。

假设 A 已经等待 B 的回复 200 毫秒,以下两种情况在 A 看来完全相同:

  • B 已经崩溃,不会再发送回复。
  • B 正常运行,但消息被网络延迟了 30 秒。

将等待阈值改成 5 秒或 60 秒,也无法在完全异步模型中消除这种歧义,因为合法的消息延迟始终可以更长。

为了明确共识目标,先约定三项性质:

性质 必须满足的条件 违反示例
一致性(Agreement) 已作出决定的正确节点不能决定不同值 A 决定 0,B 决定 1
有效性(Validity) 如果所有节点都提议同一个值,决定必须是该值 全部提议 0,却决定 1
终止性(Termination) 每个未崩溃的节点最终必须作出决定 正常节点无限等待

这里的终止性指每一次符合模型的执行最终都会结束,而不只是正常网络中通常能够结束。它也不要求预先给出固定的完成时间。

两个节点为何无法区分延迟与崩溃

假设协议完全确定:节点下一步执行什么,只取决于自己的输入、当前状态和已经收到的消息,不使用随机选择。系统最多允许一个节点崩溃,崩溃节点会永久停止执行。

现在构造三种执行场景。

场景 A 的输入 B 的输入 执行条件 协议必须面对的结果
甲 0 0 B 在发送任何消息前崩溃 A 必须最终决定 0
乙 1 1 A 在发送任何消息前崩溃 B 必须最终决定 1
丙 0 1 两个节点均正常,双向消息暂时延迟 不能允许 A 和 B 决定不同值

场景甲中,A 无法再获得 B 的信息。如果协议保证容忍一个节点崩溃,它就必须让 A 在有限的本地执行步骤后决定。由于两个初始提议均为 0,有效性要求 A 决定 0。

场景乙与之对称。B 必须在有限步骤后决定 1。

关键在场景丙:A 的输入仍然是 0,B 的输入仍然是 1。网络调度器暂时不交付两者之间的消息,让 A 一直看不到 B,让 B 一直看不到 A。

在 A 作决定前,它经历的本地输入与收消息历史可以和场景甲完全一致;B 的本地经历则可以和场景乙完全一致。确定性协议无法区分这些本地经历,因此 A 会决定 0,B 会决定 1。

节点崩溃与消息延迟造成的局部视图不可区分性

场景丙中的消息无需永久丢失。调度器只需要将消息延迟到双方作出决定以后,再正常交付即可。因此,即使通信可靠,也无法挽救已经发生的一致性冲突。

如果协议为了避免这种冲突,规定必须收到对方消息才能决定,那么场景甲和乙中仍在运行的节点可能永远无法决定,终止性又会失败。

这个双节点反例表明,在要求容忍一个崩溃故障时,确定性协议无法同时满足上述三项性质。它揭示了 FLP 的关键直觉,但一般节点规模的完整证明还需要更严格的状态分析。

FLP 定理真正证明了什么

Fischer、Lynch 和 Paterson 于 1985 年提出的 FLP 不可能性结论表明:在完全异步的消息传递系统中,即使通信可靠、最多只有一个节点可能发生崩溃故障,也不存在能够在所有允许执行中同时保证一致性、有效性和终止性的确定性共识协议。

这个结论有几个不能省略的限定条件:

  • 完全异步:消息传输与节点执行速度没有已知的时间上界。
  • 确定性:相同状态及相同输入消息总会产生相同的协议行为。
  • 崩溃故障:节点可能停止执行,但不需要假设它会恶意发送伪造信息。
  • 全执行保证:协议必须对模型允许的每一种执行都满足共识要求,而不是只在大多数实际运行中成功。

FLP 的一般证明使用双值状态(Bivalent Configuration)的概念:从同一个系统状态出发,未来可能决定 0,也可能决定 1,具体结果取决于后续消息的调度顺序。

证明首先说明存在这样的初始状态,然后利用异步调度可以推迟关键消息这一事实,反复构造仍然保持双值性的后续状态。这样就存在一种符合模型要求的执行,使协议始终无法到达决定状态。

因此,FLP 并不是说所有异步执行都会无限停滞,也不是说网络中只要出现一次延迟,共识就必然失败。它说明的是:无法对每一种允许的执行无条件承诺确定终止。

原始论文可参考:Impossibility of Distributed Consensus with One Faulty Process(1985)。

实际共识协议怎样获得进展

真实系统并非只能无限等待。工程实现通常会调整 FLP 的某项前提,或者降低对终止保证的要求。

处理方式 增加的条件或改变的保证 实际效果
部分同步模型 假设某个未知时刻之后,网络延迟和处理时间存在有限上界 网络稳定后可恢复终止性保证
随机化共识 引入随机选择 在指定故障条件下可获得概率意义上的终止保证,而非所有随机执行都确定终止
超时与领导者切换 使用超时怀疑和视图切换,通常依赖最终稳定的网络条件 解决正常运行中的长时间等待,但超时本身不证明节点已经崩溃

例如,一个基于部分同步假设的协议初始使用 500 毫秒超时。如果网络长期拥塞导致消息需要 2 秒才能到达,协议可能连续切换领导者,无法完成提交。将超时调整为 1 秒、2 秒、4 秒并继续重试,是一种实际策略;只有结合协议的具体安全规则、故障界限和最终稳定的网络条件,才能论证它最终能够结束。

这也解释了为什么区块链协议需要把安全性与活性分别分析。对于带最终确认投票的区块链,假设有 4 个验证者,一次确认要求至少 3 个有效投票。如果网络将它们分成两个各含 2 个验证者的分区,任何一侧都无法单独获得 3 票。系统可能暂时停止最终确认,但不应该为了维持出块速度而降低投票规则,使冲突区块同时获得最终确认。

这个四验证者场景是确认阈值的工程示例,并非 FLP 定理本身的证明。恢复通信以后,能否继续完成确认,还需要检查协议的投票规则、故障上限、领导者选择以及网络时序假设。

如何判断一份共识保证是否可信

审查共识协议时,可以针对一个具体故障场景逐项核对:

  1. 查明网络假设:协议要求同步、部分同步,还是完全异步?是否依赖某个最终稳定阶段?
  2. 查明故障模型:允许多少个节点崩溃,是否还允许拜占庭节点发送冲突消息?
  3. 查明最终性规则:哪些投票、证明或链上条件意味着决定不可撤销?
  4. 查明终止性条件:在长期分区和消息无限期延迟时,协议是否仍然声称一定完成?
  5. 查明保证类型:最终确认是确定性的、概率性的,还是依赖额外网络和诚实节点条件?

例如,一份设计文档同时宣称‘完全异步’‘确定性协议’‘容忍至少一个节点崩溃’‘所有执行必定完成共识’,就与 FLP 的结论冲突。设计者必须指出其中哪项假设实际上发生了变化,或者重新限定终止保证的适用范围。

对交易最终性而言,暂时无法决定不等于已经出现冲突决定。网络分区可能使交易持续处于待确认状态;只要协议仍坚持正确的确认条件,就可以在牺牲部分活性的情况下保留安全性。FLP 划定的正是这条边界:完全异步且可能崩溃的环境中,不能同时承诺无条件的确定性终止与正确共识。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

异步网络为何无法保证确定终止

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通