date
Oct 12, 2024
icon
password
Pin
Pin
Hide-in-Web
Hide-in-Web
网址
type
Page
slug
btc-flp
tags
知识点
category
bottom
bottom
Hide-in-Config
Hide-in-Config
comment
Show
status
Published
summary
FLP 是三位作者名字的首字母缩写。
FLP 不可能性（FLP Impossibility）结果是分布式计算领域中的一个重要理论，由 Michael J. Fischer、Nancy A. Lynch 和 Mike Paterson 于 1985 年提出。该理论证明了在 异步系统 中，如果存在一个可能崩溃的节点，就不可能确保一致性、终止性和无错误性同时满足。这是分布式系统中的一个基本限制，尤其是在需要容错和一致性的情况下。
为什么崩溃的节点会使得一致性、终止性和无错误性同时满足？
可以这样理解，想象一下，几个小朋友在不同的房间里玩一个游戏，他们需要通过对讲机互相沟通来决定大家一起做什么。每个小朋友都要同意做同一件事情才算赢。如果其中一个小朋友的对讲机坏了，或者信号很差，可能有时候消息会延迟到，甚至收不到。在这种情况下，就不可能保证所有小朋友都能在规定时间内达成一致，并且没有任何错误。
什么是异步系统呢？
异步系统就像这个对讲机聊天的过程，因为每个人发消息的速度不同，有时候消息会很快传到，有时候可能会因为信号问题或者噪音而变慢，甚至延迟很久才收到。所以，每个人在不同时间收到消息，可能消息到的顺序也不一样。
异步系统就是指信息传递的时间不固定，大家可能会在不同的时间收到消息，换句话说就是，网络传输，时延没有上限。
1. FLP 不可能性结果的内容
该结果表明，在以下条件下，不可能设计出一个能够总是成功解决共识问题的分布式算法：
- 异步系统：消息的传递时间不确定，网络延迟可能非常大。
- 节点可能崩溃：至少有一个节点可能会在任何时间点停止工作。
在这种环境中，共识算法无法保证所有节点在有限时间内达成一致，原因是异步系统中的网络延迟和节点崩溃使得系统无法区分究竟是一个节点崩溃了，还是网络传递延迟导致消息没有及时到达。因此，无法在异步系统中在一定时间内同时保证所有节点最终达成一致（终止性）并且没有错误。
2. FLP 与区块链的关系
区块链本质上是一个分布式系统，区块链中的节点需要就区块的顺序和内容达成共识。因此，FLP 不可能性结果与区块链的共识机制密切相关，尤其是在异步网络和可能出现节点崩溃的情况下。
尽管 FLP 结果表明在异步系统中无法设计一个完美的共识算法，但区块链共识机制通过一些策略来规避这个限制，尽量接近可靠的共识。
- 工作量证明（Proof of Work, PoW）：比特币和以太坊等区块链采用 PoW 机制。PoW 并不要求严格的同步，而是通过耗费资源的计算来解决共识问题，使得大多数节点最终达成一致。虽然不能完全避免 FLP 提到的不可能性，但通过概率性达成共识。
- 权益证明（Proof of Stake, PoS）：相比 PoW，PoS 通过验证节点的权益（即代币持有量）来选出区块的生成者。PoS 同样不要求严格的同步，但通过权重和经济激励机制，减少了节点崩溃对共识的影响。
- 拜占庭容错（Byzantine Fault Tolerance, BFT）算法：一些区块链，如 Tendermint 和 Algorand，采用了拜占庭容错算法，虽然理论上仍然受 FLP 限制，但通过实际系统中的设计假设和优化，尽可能保证在大部分正常节点存在时系统能够正确运行。【 拜占庭将军问题 】
3. 区块链中应对 FLP 的策略
区块链在设计时无法完全规避 FLP 不可能性定理，但通过以下方式处理该问题：
- 概率性共识：通过设计使得一致性在一定条件下以极高的概率达成，而不是绝对的保证。例如 PoW 中的链上共识是概率性最终一致。
- 经济激励机制：激励节点诚实参与共识，通过经济惩罚机制（如罚没权益）减少节点恶意行为或频繁崩溃的情况。
- 容错设计：通过设计节点容错机制，使得系统在节点崩溃或网络延迟的情况下仍能继续正常运行，而不会导致整个系统停止。