比特币的工作证明：拜占庭将军的问题

“每个人都知道X是不够的。我们还需要每个人都知道每个人都知道X，并且每个人都知道每个人都知道每个人都知道X –就像拜占庭将军的问题一样，这是分布式的经典难题。数据处理。”

-詹姆斯·A·唐纳德

分布式网络中的一个基本问题是在存在错误或有缺陷的过程的情况下找到共识。当一个可靠的系统永久性崩盘，反复启动和关闭，或表现出拜占庭状态时，必须管理其一个或多个组件的故障，这意味着以最坏的方式损坏。例如，节点可能故意和恶意地歪曲或歪曲信息或传播信息，从而无法统一网络。这个问题在文献中被描述为“拜占庭将军的问题”。当整个网络需要就交易的安全性和不可逆转的有效性达成共识时，即当需要确定哪些块是公认的块时，这种情况尤其发生在比特币上。

拜占庭将军的问题可描述如下：许多将军将其军队安置在他们要征服的被围困的城市之外，他们需要选择进攻的时间。他们知道，只有至少一半人同时进攻才能取得胜利。但是，如果他们不能很好地协调进攻的时间，他们的人数将超过人数，将失去战斗力。他们还怀疑一些将军不忠，会发出有关袭击时间的虚假信息。而且由于将军们只能在骑马时通过信使彼此通信，因此他们无法验证消息的真实性。因此，我们要问自己，尽管缺乏信任且没有中央治理实体，在这种情况下如何就攻击时间达成共识。

在比特币问世之前，这个问题可能无法解决。计算机科学家在1982年宣布，将军的问题最多可以简化为“指挥官和中尉”的问题，在该问题中，只要忠实忠诚，所有中尉就必须按照指挥官的命令行事。他们表明，只有三分之二以上的将军忠诚，这个问题才能解决。[1]

比特币寻求提供一种解决该问题的通用解决方案，通过这种解决方案，超过50％的计算能力的忠诚度足以达成共识。在这种情况下，分歧被暂时接受，并且由多数表决决定对矛盾意见的解决方案。换句话说，由于计算资源稀缺并且因为自己的性能被用作投票，因此达成了共识。这样就可以以去中心化的方式构建应用程序，而这在没有中央控制器的情况下是不可能实现的。因此，比特币协议背后的技术-区块链和分布式共识-也越来越多地用于其他领域，不仅用于交易验证。

回到我们的示例，如果我们将将军视为类似于比特币网络的各个挖矿节点，那么比特币提供的解决方案如下：在任何时候，任何将军都可以宣布袭击时间。首次听到的起音时间被认为是正式计划。但是，消息的传递不是立即的，这就是为什么不同的将军首先会听到不同的计划的原因。因此，将军一旦收到一个计划，就必须根据该计划解决一个困难的数学问题-这项任务平均优选持续数分钟。他们中的一个找到解决方案后，他便将其添加到计划中，从而生成了一个新计划。他将新计划发送给其他将军。之后，所有听到它的人都会开始扩展这个新的官方计划，这又需要花费几分钟。

每个将军都在制定他所知的最频繁扩展的计划，以延长他在那之前听到的最长的生存解决方案。在多次扩展解决方案之后，最长的计算链（例如，最长的计划）中包含的攻击时间被认为是真实的攻击时间，因为它必然需要所有将军的一半以上的计算能力创建它。换句话说，这条最长的区块链的存在证明了大多数将军（超过50％）参与了其创建。计算能力不到一半的攻击者不可能在同一时间内产生另一条长度相似的链。该方案称为“工作量证明”，其结果是区块链的哈希树结构在以下示意图中显示。

比特币的一方面使上述问题变得复杂。在拜占庭将军的问题中，存在所有节点都同意的最终决定。对于比特币，此要求不存在，因此未提供确定性解决方案。比特币协议具有很高的概率和随机性。它保证了决策最终会收敛，但不设置最终日期。Dijkstra在1974年描述了比特币采用的这种自稳定解决方案，Angluin等人在2006年发布了这种自稳定解决方案，并将其应用于分布式系统中的共识发现。最终每个区块的有效性都可以绝对确定。同时，不能排除在任何时间点都会出现更长的链条，该链条将取代之前的链条。结果，较短链中的所有交易从发生分支（即所谓的“叉”）之时起就失去了有效性。只有那些交易保持有效，这些交易在长链中具有与短链中相同的输入和输出。在某些情况下，两个链之间的差异可能导致相同金额的重复支出。这是一个问题，我们将在下一个子章节中讨论。

从技术角度来看，可以在一定的间隔内预期出现这种分叉（或分支出来）。2013年3月发生了一次重大的此类分叉。由于缺乏向后兼容性，新版本的比特币软件客户端导致同一客户端的旧版本无法识别生成的区块。这导致老客户在自己的区块链上工作。分支存在24个区块（大约6个小时），并在大多数网络切换回旧版本后解散。

[1]（Lamport，Shostak和Pease，1982年）

本文摘自我的书《比特币的简要介绍》。