权游七大家族能否达成一致?区块链基础知识解读之⑦ - 拜占庭将军问题

成长为想要的样子  2019-08-09  新手入门/区块链知识栏目  

  

  《权利的游戏》九大家族中,除了拜拉席恩家族因为劳勃与瑟曦的夫妻关系之外,各大家族与兰尼斯特家族之间都有着各种恩怨情仇,他们都有联盟起来对抗兰尼斯特的理由。但是兰尼斯特家族实力雄厚,富甲一方。其他各家族只有在超过一半以上数量联合起来一起进攻,才有可能取胜,否则便有反被灭掉的危险。可是各大家族之间也因为各种利益纠葛,相互之间并不信任。现在摆在他们面前的问题是如何在只能通过渡鸦传递信息的情况下就是否进攻兰尼斯特家族达成一致。

  七大家族面对的难题包括但不限于下面这些:

  1. 各大家族中有没有叛徒?会是谁?有多少?

  2. 如果叛徒捣乱会对其他家族的决定和行动造成什么影响?

  3. 送信的渡鸦是否有被拦截的可能?

  4. 各大家族收到的信息如何确认真实可信?

  5. 怎样确保发信人不被冒充?

  6. 大家怎样才能达成意见一致?

  

  什么是拜占庭将军问题?

  虚构一个权游各家族结盟对付兰尼斯特的故事其实是为了让我们今天要讲的这个问题更好理解。它就是从1982年开始就困扰人们的拜占庭将军问题,是计算机科学家莱斯利·兰波特提出的一个思想实验,大致的故事情节是:

  拜占庭帝国想要进攻一个强大的敌人,为此派出了10支军队去包围。敌人虽不敌拜占庭帝国,但也足以抵御5支常规拜占庭军队的同时袭击。这10支军队相距都非常远,分散在敌人四周,进攻需要至少一半以上(6支军队)同时攻击才能攻下敌国,否则毫无胜算。由于通信条件所限他们只能依靠通信兵骑马相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是,他们不确定他们中是否有叛徒,叛徒可能在通信中恶意变更进攻意向或者进攻时间以迷惑其他将军。在这种状态下,拜占庭将军们如何才能保证至少有6支军队在同一时间一起发起进攻,从而赢取战斗?

  拜占庭将军同样面对这样一些问题:

  1. 军队有没有叛徒?有多少,叛徒会对忠诚军队的行动形成哪些影响?

  2. 各队派出的通信兵路上如果被敌军截杀怎么办?

  3. 各军队收到的信息是否真实,有没有被修改过?

  4. 如何验证发信人的身份真实可靠?

  5. 军队之间怎样才能达成一致的行动意见?

  

  还有一个很重要的问题是10支军队如果都只能依靠两两通信的方式传递信息,意味着仅仅了解所有其他将军的意见,每个将军至少需要派出9个通信兵把自己的意见发给其他9个人。那么仅仅初步了解相互的想法就需要90次通信往来的成本,如果还要几轮来表达对其他人意见的同意或者反对,到最后形成一致意见,恐怕需要几百上千次了,通信兵就算不被敌军截杀,也累死了。这还不能保证他们一定能够达成意见一致,因为还涉及可能会有叛徒捣乱,通信兵可能会出问题,信息可能会被篡改等等现实问题。

  所以如果不是默认通信兵,信道没有问题,忠诚军队传递的出去信息真实可靠,按照现实中的复杂情况,拜占庭将军的问题是无法解决的。就算假设现实情况很单纯都能按照我们的假设运行,通过两两通信的方式在这么多人中达成意见统一也是一件劳民伤财成本巨大的事。

  

  兰波特教授提出这么个古怪的问题到底是为啥呢?

  这还得从兰波特在斯坦福国际研究院工作时接手的一个项目说起,这是为NASA(美国国家航空航天局)建立的容错型航电计算机系统。这个系统应用于商业航空领域,所以计算机系统网络是不允许出现故障的。

  而在分布式计算网络中,计算机之间的通信,只能在一台计算机与另一台之间进行。所谓的广播,也只是一台计算机将消息一个一个发给其余的计算机。计算机之间的通信,跟我们看见的现实的人类社会有很大不同。习惯了各种群聊的我们,会有种错觉:以为我们可以同时跟所有人说话。其实计算机已经在后台自动帮我们的消息复制了好多遍。不过,就算在现实世界里说话其实也不能精确达到“同时”,毕竟人与人之间还是有距离的。

  另外不同的计算机之间要达成共识需要按照同一套协作策略进行通讯交换信息。但有时候,系统中的成员计算机可能出错而发送错误的信息,用于传递信息的通讯网络故障也可能导致信息损坏,使得网络中不同的成员对全体协作的策略得出不同结论,从而破坏系统一致性。

  计算机与现实世界之间的不同,还体现在:现实中的广播(即当众讲话),你发出来的信息与大家接收到的信息是一样的,而在计算机世界里,计算机的广播可以伪造。

  所以兰波特提出的拜占庭将军问题是为了解释在一个分布式系统中,在网络参与者缺乏信任和信息通道不可靠的前提下,试图通过消息传递的方式达到网络的一致性是不可能的。

  拜占庭将军问题是否有解?

  这个困扰人们数十年的问题直到一件事的出现才被解决,那就是2008年比特币的诞生。

  我们把拜占庭将军的故事映射到区块链系统中,可以将将军看作区块链的计算机节点,将通信骑兵看作区块链的信息收发通道。拜占庭将军问题的核心就抽象成了如何在可能存在不可靠节点和不可靠信息传输通道的情况下交换信息,达成共识。

  我们可以把这个问题总结为:
1. 意见一致难达成:在任意时间,系统中会存在多条信息,就如将军们会在同一时间向其他9个人发送信息传达自己的意见,也可能同时收到9条信息。而每个将军的意见可能都不一样,导致很难在一个时刻对结果进行一致性的确认。所以在异步通信模式下,几乎很难达成一致。

  2. 信息真伪难确认:每个将军都无法确认自己收到的信息是否被篡改,也无法确认发信人的身份是否真实,因此无法确认信息的真伪。

  

  针对这两个问题,区块链给出了解决思路:

  1. 限制任意时间的信息数量:原理是用权限来选择唯一的信息发送人。比特币采用工作量证明来确保在10分钟的时间范围内只有一个节点可以发送信息提出自己的提案表达意见。它是通过让所有参与发送信息的节点共同解答一道哈希算法的难题,来竞争发出提案的权利。谁第一个解出答案,谁就有权限发送信息。而其他节点只需要对收到的提案进行验证和确认,并向网络广播自己的跟进结果即可。

  另外,比特币采用最终一致性代替过程一致性,对所有意见的结果不需要所有节点马上验证和确认,只需要在能搜寻到的所有提案中,选择确认和验证数量最多那一条作为最终一致性意见即可。

  2. 用非对称加密和数字签名来确认信息真伪:发信人对发送的信息用用哈希算法计算出哈希值,再利用非对称加密,用自己的私钥加密哈希值,作为自己的数字签名。同时将信息原文和数字签名发送到网络,收到信息的节点只需要将数字签名用发信人的公钥解密得到原文信息的哈希值,再将收到的信息进行一次哈希计算,对两个哈希值进行对比就能轻松验证发信人的身份。

  

  区块链的解决方案意不在于确认网络中是否存在恶意节点,而是绕过了这个问题,允许恶意节点的存在,只要保证其数量少于一半就不会破坏最终一致性的达成。而所有其他节点要做的也只是验证收到的信息并尽力地广播出去。

  数十年未解的拜占庭将军问题, 终于等到了解开谜团的天使中本聪,他用区块链构建的一套分布式系统中大家都遵守的协议完美地让将军们得以解脱。

版权信息
作者:雪儿小姐姐
来源:成长为想要的样子

关于我们

联系我们

作者进驻

手机版

Copyright © 2013 比特巴 www.btb8.com
始建于2013年,提供比特币 区块链及数字货币新闻、技术教程、测评、项目周报、人物等资讯
本页面提供的是新手入门教程资讯,提供入门级的比特币知识、区块链知识以及各类数字货币知识,是数字货币爱好者入门、精通的好导师。