拜占庭将军问题

一句话

几支军队分头围城，只有同时进攻才能赢；信使会迟到，将军里还可能有叛徒故意传假消息。在这种条件下让所有忠诚的将军商定同一个行动，就是拜占庭将军问题。

为什么它比”传话可能丢”更难

如果只是消息会丢，问题相对好办：多发几遍、加确认重传。真正的难点在于参与者本身可能撒谊，而且可以对不同的人撒不同的谊——跟东边的将军说”进攻”，跟西边的说”撤退”。

这时候每个忠诚的将军收到的信息互相矛盾，而他没法判断矛盾来自网络延迟还是来自叛徒。更麻烦的是，达成一致要求的不只是”我知道计划”，而是”我知道你也知道计划，而且我知道你知道我知道”——这种层层嵌套的共同知识，是分布式系统里最难造出来的东西。

Lamport、Shostak、Pease 1982 年的论文给出了经典结论：在消息可能被任意伪造的模型下，要容忍 m 个叛徒，总人数至少需要 3m + 1。也就是容忍 1 个叛徒需要 4 人，容忍 2 个需要 7 人，容忍 3 个需要 10 人。换句话说，叛徒占比必须低于三分之一。

这个结论有个容易被忽略的前提：参与者的名单必须事先知道。3m+1 这个式子里的 m 和总数都得是确定的数，算法才跑得起来。谁在场、一共几个人，必须先说清楚。

术语考古：白皮书没提，但中本聪本人提了

关键事实：Byzantine 这个词在比特币白皮书正文出现 0 次。

不过中本聪自己在别处说得非常明确。2008 年 11 月 13 日，他在密码学邮件列表上回复 James A. Donald 时写道：

The proof-of-work chain is a solution to the Byzantine Generals’ Problem.

紧接着他给了一个自编的比喻，把将军们的任务换成了暴力破解国王的 wi-fi 密码：将军们只有在多数人同时开算时才有足够算力在被发现之前破解密码；他们不在乎具体几点动手，只要都同意同一个时间。谁想到一个时间就广播，大家把先听到的那个时间塞进哈希里开始算工作量证明，听到更长的链就切换过去。他给的数字是：工作量证明难度设为全网合力约 10 分钟出一个，那么两小时后，某一个进攻时间应当已经被一条 12 个工作量证明组成的链锚住。每个将军只要检查这条链的难度，就能估算出上面花掉了多少并行算力，从而确认参与者确实占了多数。

这里的巧思是：链的长度同时充当了投票、计时和确认三样东西。

两种”去中心化”不是同一个意思

把 1982 年的结论和中本聪的方案并排放，差别就清楚了：

经典 BFT 给的是确定性保证，代价是必须先知道谁在场。中本聪给的是开放准入加经济激励，代价是一致性只是概率性的——一笔交易永远不能说百分之百不可逆，只能说重写它的成本高到不值得。

所以”比特币解决了拜占庭将军问题”这句话要加限定词才准确：它在一个不同的问题设定下给出了工程上够用的解，而不是在 1982 年那个设定里改进了下界。

边界与常见误解

它不是”名字很吓人的容错技术”。 拜占庭故障特指任意行为的故障，包括故意撒谊和对不同对象说不同的话。相对的是崩溃故障（节点直接死掉，不会骗人），后者容易处理得多。两者不能混用。

多数算力不等于多数节点。 中本聪换掉的正是计数单位。见女巫攻击。

概率性一致不是缺陷，是取舍。 想要开放准入，就得放弃确定性终局；想要确定性终局，就得先固定参与者名单。这两样至今没人能同时拿到。