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

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

问题介绍

拜占庭将军问题(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号星云军团继续给回复“我们收到了”。这仿佛就是一个无穷无尽的过程。这就是我们所说考虑传输信息时会存在丢失、监听或者篡改的两军问题。

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

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180207G13G2M00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券