请选择 进入手机版 | 继续访问电脑版
我的账户
区块链之家

在这里读懂区块链

亲爱的游客,欢迎!

已有账号,请

如尚未注册?

  • 联系我们
    点击联系客服

    在线时间:8:00-16:00

    客服QQ/微信

    80052616

    电子邮件

    80052616@qq.com
  • 快速入群

    扫一扫添加好友

    邀请进区块链行业群

  • 官方微信

    扫描二维码

    关注区块链之家网

学院丨"遇见"拜占庭将军

2017-12-26 20:42
原作者: 叶先生的鱼 来自: 区块链之家网 收藏 分享 邀请

区块链的起源,来自于拜占庭将军问题,通过把拜占庭将军问题通俗化、抽象化之后,几乎可以延伸到人类的任何领域,并采用全新思维和方法来解决问题,创造价值。 ...

但凡关于区块链或比特币相关的书籍,就算是相关问题深入探讨都绕不开一个永恒的话题——拜占庭将军问题(The Byzantine Generals Problem)。每一个想理解和掌握区块链技术原理的人也无法“逃过”拜占庭将军的“手掌心”,网络上关于拜占庭将军问题的讨论、描述、讲解多如牛毛,很多区块链大神,用了论文级别最科学,最严谨的算法、公式来推理,讲解,试图让人们更透彻的理解区块链技术是如何迎刃而解拜占庭将军问题的核心,往往却事与愿违,而本文试图化繁为简,让非技术人员也能理解拜占庭将军问题的前世今生。

抛开历史故事本身,拜占庭将军问题引申出三个关键问题

1、什么是拜占庭将军问题?

2、拜占庭将军问题实质是什么?

3、如何解决拜占庭将军问题?

什么是拜占庭将军问题?

追根溯源,从历史说起。拜占庭现在位于土耳其,但是在古代,那可是东罗马帝国的首都,那个时候,东罗马到处扩张,使得国土面积十分的辽阔,为了防御和管理,每只军队都会隔得很远,将军之间也就只能通过信差(传门负责送信的人)传递信息。在战争时期,拜占庭军队内所有将军和副官必须达成一致共识,决定是否有赢的机会才去攻打敌人的阵营。但是,军队可能有叛徒和敌军间谍,左右将军们的决定,扰乱军队整体的秩序。在达成共识的过程中,有些信息,往往并不代表大多数人的意见。这时候,在已知有成员谋反的情况下,其余忠诚的将军在不受叛徒的影响下如何达成一致的协议,就是“拜占庭将军问题”。(本故事来源于《区块链:重塑经济与世界》)

拜占庭将军问题实质是什么?

有人的地方就有江湖,林子大了,什么鸟都有,某些将军会不会意图谋反或者是敌军的卧底?信差会不会被收买谎报军情?信差送信途中会不会被谋杀?一些将军会不会故意诱导其它将军做出错误的决定?......针对这些可能出现的复杂情况,科学家们通过研究、推理得出一个结论:如果叛徒的数量大于或等于1/3,拜占庭问题不可解(没办法解决)。

这里有一个简单的逻辑推演:

假设只有3个人,A、B、C,三人中如果其中一个是叛徒。当A发出进攻命令时,B如果是叛徒,他可能告诉C,他收到的A的命令是“撤退”(其实是进攻)。这时C收到一个“进攻”,一个“撤退“,于是C被信息迷惑,而无所适从。

如果A是叛徒。他告诉B“进攻”,告诉C“撤退”。当C告诉B,他收到“撤退”命令时,B由于收到了司令“进攻”的命令,而无法与C保持一致。

正由于上述原因,在只有三个角色的系统中,只要有一个是叛徒,即叛徒数等于1/3,拜占庭问题便不可解。所以拜占庭将军问题的实质是——如何保证得到每个将军决策正确性的前提下,达成一致性(共识)。通俗地说就是要得到每位将军决定进攻还是撤退真正的意图,最后能保证忠诚的将军们所做的决定能达成一致,而不让叛徒达成目的。

归纳起来,整个拜占庭将军问题存在下面几个特性:

1、整个环境是不安全的,因为每一位将军都有可能是间谍或叛徒;

2、所有将军的地位都是平等的,没有一个更加权威的大将军凌驾于他们之上,也就是没有中心机构,能从中协调和统一;

3、让好人达成共识是唯一目的。

如何解决拜占庭将军问题?

为了解决拜占庭将军问题,将军和科学家们一共想出三个办法:


一、口头传达,口头确认

假设有四个将军A、B、C、D,将军A派出三个人分别通知B、C、D,X月X日X时进攻;同样,B、C、D也分别派出三个人通知其它三位将军自己的决定,当B收到A的信差通知之后,需要再派一个信差去回报将军A:我已经收到你的通知了;然后A再派人去告知B:我已经知道你已经收到我的通知了;然后B再派人回报将军A:我已经知道你已经知道我收到你的通知了;然后就变成没完没了,无限循环......最终无解。

口头消息的特点:

1、每个被发送的消息都能够被正确投递;

2、信息接受者知道消息是谁发的;

3、沉默(不发消息)可以被检测;

口头消息的缺点:

口头协议并不会告知消息的上一个来源是谁,也就是消息不可追根溯源,出现信息不一致也很难找到叛徒在哪。

二、书面协议

假设还是这四位将军A、B、C、D,将军A写了三封信(内容一样)——X年X月X日X时一起进攻,如果同意请签名盖章。A将军自己先签名盖章,然后派出三个信差分别送给B、C、D,同理B、C、D分别签名盖章后再各自派出三名信差送给其它三位将军,一直循环,直到同时被A、B、C、D签名和盖章的信出现,才停止确认。

和口头消息相比书面协议还具备以下特点:

1、每条消息都有记录可查,从而追根溯源;

2、将军们因为使用签名技术,签名没法篡改,因为一旦篡改就会被发现;

3、任何人都可以验证签名的可靠性;

但书面协议也具有以下缺点:

1、由于距离较远,靠信差传递,效率很低;

2、真正可信的签名体系难以实现。签名造假的问题也没法避免;

3、完成一轮信息确认需要多次来回确认,常常要达成共识,需要很多轮的协商,这导致达成共识的过程繁琐,成本奇高;

三、区块链技术

为了从根本上解决拜占庭将军问题,终于,有数学家(传说中的中本聪)设计了一套算法,让将军们在接到上一位将军的信息之后,加上自己的签名再转发给除自己之外的其他将军。在这样的信息连环周转中,将军们可以在不找出叛徒的情况下达成共识,从而保证得到的信息和作出的决策是正确的。

随着互联网科技的发展,靠信差骑马送信的场景已不复存在,相应的消息确认信息延迟问题也得到了根本解决,假设四个将军都配有一台电脑,可以通过网络来确认消息,如果四个将军A、B、C、D同时向其它三位将军发出自己的决策消息(各自的决策很可能不一致)——XX年XX月XX日XX时进攻(撤退),势必会造成系统的混乱,行动难以一致。为了解决这个问题,中本聪又制定了一个策略,谁都可以发起确认信息,但一段时间之内只能有一位将军可以传播信息,这样有效地保证了信息的有序性。如何保证一段时间之内只有一位将军获得传播信息的权限?天才中本聪设计了一个算法——给每一位将军出一道难度很高的题,谁先计算出来正确结果(工作量证明),谁才能传播信息。

当某位将军发出确认信息之后,收到消息的将军必须签名盖章,以验证自己的身份。这里运用了一种非对称加密技术为这个信息签名。这样彻底解决了在古代难以解决的签名问题:

1、消息传送过程中的私密性;

2、真实身份验证;

3、签名不可伪造、篡改。

写到这里,也应该明白了工作量证明(Proof Of Work)的意义。工作量证明,可以简单的理解就是一份证明,现实中的毕业证、驾驶证都属于工作量证明,它用以检验结果的方式证明你过去所做过了多少工作,实中毕业证证明你完成了三年初中学业,达到了某个知识水平;驾驶证证明你完成了驾校培训,具备开车的驾驶水平。而将军们通过工作量证明,可以得到传播信息的权限,从而保证某一时间段只有一位将军能够广播。

归结起来,通过区块链技术,中本聪彻底解决了拜占庭将军问题延伸出的三大核心问题——

1、每个将军都有一份实时与其他将军同步的消息账本,就算有个别将军丢失,篡改自己的账本,都不影响最终结果(集体维护、去中心化、可靠数据库、分布式账本);

2、账本里有每个将军的签名都是可以验证身份的,如果有哪些消息不一致,可以知道消息不一致的是哪些将军,保证每一位将军的传播出去的都是自己的真实意图,最关键的是其它所有将军都知道这位将军的真实意图。(去信任)

3、尽管有消息不一致的情况发生,但只要超过半数同意进攻,少数服从多数,共识达成。(共识机制)



区块链的起源,来自于拜占庭将军问题,通过把拜占庭将军问题通俗化、抽象化之后,几乎可以延伸到人类的任何领域,并采用全新思维和方法来解决问题,创造价值。

最后用我非常喜欢的一段话作为结束。古老的“拜占庭将军问题”,让人生,让人死,让人痴迷,让人疯狂。某种程度上,问题比答案更重要。很难想象:如果没有“拜占庭将军问题”,没有它揭示出在人类散兵游勇的状态下,永恒的“共识”困境,那么对于这种困境的反思和探索便无法成为可能,逃离困境到达光明之地也无法成为可能。所以在我们向伟大的“答案”——区块链致以敬意之时,请不要忘记它的源头,不要忘记拜占庭。

关注我们
ID:qklzjw

客服邮箱:80052616@qq.com

周一至周五 9:00-18:00

区块链之家网2017-2018 鲁ICP备16029435号-6

鲁公网安备 37010202001341号