去中心化的区块链世界里，谁说了算？解读拜占庭将军问题

在可能是史上最有趣的区块链科普一文中，我们讨论了中心化和去中心化。提到去中心化的分布式系统，就绕不过其中的一个难题 - “拜占庭将军问题”。在本文中我们将介绍区块链的又一伟大成就：将共识机制作为解决交易各方信任的方案，解决“拜占庭将军问题”。在后续推送中，我们将陆续讲解区块链技术的其他精妙之处。（没有关注公众号的小伙伴要赶紧上车了！）

问题介绍

拜占庭将军问题（Byzantine failures），是由莱斯利·兰伯特在1980年提出的点对点通信中的基本问题，即在缺少可信的中央节点和可信任的通道的情况下，分布在网络中的各个节点如何达成共识的问题。

拜占庭将军是Lamport在研究分布式系统容错性的时候编出的一个故事。

拜占庭帝国时期，出现了一个强大的敌人（比如小怪兽），帝国派出了9支军队包围这个敌人（全方位偷袭，最大化胜率），9支军队分散在小怪兽的四周。 小怪兽虽然还小，但还是足以抵挡4支军队的兵力，任何1支军队单点攻打都会失败。所以，这要求至少有5支以上的军队达成进攻共识才能打败小怪兽。同时，各个军队之间只能依靠通信兵相互通信来传递进攻或者撤退的命令，9个将军不能聚在一起讨论（聚在一起讨论，小怪兽会逃跑）。但现在的问题是，将军们不确定他们中间是否有叛徒，因为叛徒可以欺骗某些将军采取进攻行动，促成一个不是所有将军都同意的决定，如当将军们不希望进攻时促成进攻行动；或者迷惑某些将军，使他们无法做出决定。在这样恶劣的情况下，各位将军们如何才能协商一致，从而打败小怪兽呢？这个著名的“拜占庭将军问题“困挠了计算机领域的科学家们很多年。

要注意的一点是，我们假设通信通道是可以信任的、没有问题的，即每个通信兵都能顺利的把信息送达。如果要考虑通信兵遇到埋伏被歼灭的情况，那就涉及到两军问题。感兴趣的读者，小编文末有相关内容介绍。

后来科学家们发现此问题有两种解决方式：口头解决和书面解决。从这两种解决方案中得出结论：只要叛徒的数量少于1/3时，军队能达成共识。

（敲黑板，上数学课了！）

用数学方法推断其实很简单：我们设x为军队将军总数，y为叛徒人数。能达成共识的方式是：除去叛徒以外的人数仍然占据多数，即整个共识的达成是由那些忠诚的将军主导的。

x - y> (x-y)/2 + y

有些朋友说，你这不是对文科生太不友好了么。那小编用上述的故事再来说明一遍。假如现在有8个忠诚的将军，1个叛徒。叛徒可能故意给4名投进攻的将领送信表示投票进攻，而给4名投撤离的将领送信表示投撤离。但是由于其他8个将军都是忠诚的，所以他们在互相通信后能达到共识，这1个叛徒的扰乱无法左右最终的共识。当叛徒数量为2个的时候情况相同。

但当叛徒数量为3个时，叛徒们一面给3名进攻的将领送信表示投票进攻，而给3名投撤离的将领送信表示投撤离。3名主张进攻的忠诚将领和3名主张撤退的忠诚将领通信后发现，分别是6票进攻6票撤退。这样整个军队无法得到一致的进攻或者撤退决策。当叛徒数量多于3人时情况也相同。

由此可见，当叛徒人数大于1/3时，上述解决方式将失效。

终极解决方法 -POW（工作量证明）

在分布式计算上，不同的计算机通过信息交换尝试达成共识，但有时候，系统中的协调计算机或成员计算机可能因系统错误交换错的信息（出现叛徒），影响最终的系统一致性。对于在去中心化系统中出现的“拜占庭将军问题”，可以用区块链中的共识机制来解决，例如POW、POS、DPOS。篇幅所限，本文我们将只介绍如何使用POW来解决点对点系统中的共识问题。

工作量证明(Proof of Work，简称POW)，简单理解就是一份证明，用来确认你做过一定量的工作，被运用在比特币区块的生成过程中，也就是我们俗称的“挖矿”（关于挖矿的定义详见第一篇推送可能是史上最有趣的区块链科普）。

简要来说就是，现在已经存在第1000个区块了，我想挖出第1001个，第1001个区块是由区块头和区块主体构成（存放交易数据）。矿工们通过改变区块头中的随机数，经过哈希函数的计算输出一组值；例如：当输出值的前14位均为0时，即抢到了记账权，这样一个14个0的哈希值是极其罕见的。在网络中的机器随机的找到一个有效哈希值之前，上十亿个的无效值会被计算出来，这就是减慢信息传递速率并使得整个系统可用的“工作量证明”。

同时在这里要说明，哈希函数是当你改变输入值时，输出值无法预测，所以矿工们都是通过穷举法（一个数一个数地试）用大量算力来进行挖矿。

对应到上述的故事情景中，一方面各个军队派出信使送到不同的目的地需要时间，另一方面各个军队将军也需要对收到的信息进行判断。在这个过程中，9个军队间不断的相互交流信息。任何一个人都有可能收集到信息并传递给其他人（抢到了记帐权）。而其他军队也能够来验证，这些信息时正确的，有效的，从而达成共识。

而因为这个将军做出了贡献，使各个军队联合起来最终打败了小怪兽，这个将军将获得奖励，在比特币系统中，这个奖励就是比特币。

课外加餐 -两军问题

小怪兽又出现了，现在是一群小怪兽，所以只能上奥特曼了。现在有两个奥特曼军团，分别在1号星云和2号星云。任意一个奥特曼军团都打不过这一群小怪兽，所以需要两方联合起来。两个军团要就此协商进攻时间，所以1号星云上派出雷欧奥特曼去和对方进行沟通说：我们于2018年2月8日北京时间8点整一起进攻可以么？1号星云为了确定自己的消息的确被对方收到了，要求对方给回复：我收到了你的提议，我们也觉得这个时间很不错。但2号星云的军团也不确定对方是否已经知晓自己确认了这个消息，因为中间通信的雷欧奥特曼可能会被小怪兽捕了。所以需要1号星云军团继续给回复“我们收到了”。这仿佛就是一个无穷无尽的过程。这就是我们所说考虑传输信息时会存在丢失、监听或者篡改的两军问题。

希望读完本文的你，能和上面的青蛙产生同感。