13 拜占庭将军问题

本章介绍一个中本聪发表的可能最有意思的帖子，他解释了区块链如何解决在计算机科学中被称为“拜占庭容错”的问题，这是比“两将军问题”更广义的版本 。问题中，两个或更多人需要在不可靠的通信环境中共享信息，为共享信息而发送的消息可能丢失或被篡改。这个问题的陈述首次出现在20世纪70年代的网络计算机文献中，那时该问题无解。中本聪在这篇文章中声称比特币解决了这个问题 。

为了说明这个问题，假设两个将军计划同时进攻一个城市。如果只有一方进攻，攻城部队将被城防部队消灭。因为传递何时发起进攻消息的信使必须要经过城市，他可能被拦截，所以将军之间的通信不可靠。第一个将军可能在上午9点派出信使通知攻击将在当天开始。然而，信使一旦派出，将军就无法知道他是否穿过了城市。这种不确定性导致第一个将军犹豫不决，因为如果第二个将军没有收到他的消息，他就有可能会只身犯险。

鉴于此，第二个将军就要向第一个将军发送确认消息，表明自己收到了攻击消息。但是这个消息也可能被拦截，导致第二个将军也犹豫不决。第一个将军可以发出确认收到消息的确认信，但还是可能被敌人拦截。因此，第一个将军可能再次犹豫，除非他得到对方确认收到他发出的第一个消息的确认信。这个过程可以循环，任何一个将军都无法知道消息是否已发出，或者是否已经被敌人截获。 要了解更多信息，请阅读下面维基百科文章中的“问题说明”一节： http://en.wikipedia.org/wiki/Two_Generals%27_Problem 也可以参阅这篇关于拜占庭容错的文章： http://en.wikipedia.org/wiki/Byzantine_fault_tolerance

回复：比特币：点对点的电子现金支付

中本聪，星期四，2008年11月13日，19： 34： 25 UTC-8

詹姆斯_A.唐纳德写道：

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

工作量证明链是解决拜占庭将军问题的方法。我试着在那种语境下复述如下。

一些拜占庭将军每人拥有一台电脑，他们想暴力破解密码来攻击国王的wifi，他们知道密码是一定长度的字符串。一旦网络开始生成数据包，就必须在有限的时间内破解密码，攻入并清除日志，否则就会被发现并陷入困境。只有在大多数人同时攻击的情况下他们才能获得足够的计算能力来快速破解。

他们并不特别在意进攻何时发动，只要达成一致就可以。事先已定好任何人认为时机到了都会宣布一个时间，而不论何时，听到的第一个时间就是正式的进攻时间。问题在于网络传递并非瞬时，如果两个将军几乎同时宣告不同的进攻时间，有些人可能会先听到一个，而其他的人先听到另一个。

将军们用工作量证明链来解决该问题。各个将军一旦听到首次的攻击时间， 他就会让电脑开始解决一个极其困难的工作量证明问题，其哈希数据中包含了进攻时间。工作量证明非常困难，在其中一人发现问题答案之前，预计所有人要一 起工作10分钟。一旦一个将军发现了工作量证明答案，他就会在网络上广播，而收到消息的每个人会改变当前的工作量证明计算工作，并将该工作量证明包含到他们正在工作的哈希数据中。如果有人还在为另一个不同的进攻时间做准备，此时就会切换到这个新的时间，因为它的工作量证明链现在更长。

两小时后，一条有12个工作量证明的链通过哈希计算得出攻击时间。每个将军只要验证工作量证明链的难度，就能估算出每小时需要耗费多少并行的算力， 而且知道必须要大多数计算机在规定的时间内工作才能产生那么多的工作量证明 。他们必须都能看到该链，因为工作量证明是他们行动的证据。如果工作量证明链展示出的计算能力足以破解密码，将军们就能在约定的时间安全地发起进攻。

中本聪

密码学邮件组

http://btc.mom/8789/