拜占庭将军问题:如何在互不信任的环境下,达成有效共识?

想全面了解区块链,就必须了解拜占庭将军问题,这也是区块链共识机制所要解决的核心问题之一。

为了便于大家理解,先说一段我曾经的职场经历。

刚从大学毕业不久,我到了一家郭企子公司做业务。我所在部门一共6个人,5位普通员工,1位主管。主管老P是个职场老油条,最擅长欺下瞒上,暗地里做了不少见不得人的勾当,但公司却毫不知情。

终于有一天,同事小W看不下去了,把我们5个人聚在一起说:“后天的例会上,我要向领导揭发老P,到时候我牵头发言,你们附和就行,怎么样?”

年轻气盛的我早就看老P不顺眼,于是第一个答应:没问题!其他3位互相看了看,也点点头说:好吧。由此,我们达成了所谓的“共识”。

例会上,小W义正言辞的控诉老P六大罪状,我也跟着附和了几句,但万没想到的是,另外3人却背叛了我们。

他们一边和稀泥,一边为老P说话:他这么做也是为公司好,年轻人要体谅老同志嘛!小W当时脸都绿了,我的内心也有一万匹草泥马呼啸而过......

随后,我俩就从公司离职了。

这段悲惨的职场经历,其实就是个典型的“拜占庭将军问题”。

拜占庭将军问题的提出

拜占庭将军问题,是由美国计算机学家莱斯利•兰伯特于上世纪80年代提出的,本质上描述的是信息传递中的信任问题。

中世纪的拜占庭帝国富得流油,周围10个邻邦国垂诞不已。但拜占庭固若金汤,任何一个邻邦单独入侵必定失败,同时也有可能被其他9个邻邦趁机入侵。由于拜占庭帝国城防坚不可摧,10个邻邦中至少要有6国同时参与进攻,才可能攻破。

拜占庭问题假设将军们通过“信使”传达进攻信息,而非点对点直接通信。

假如一个或几个邻邦答应一起进攻,但最后却出现叛徒(就好像上面我那个职场的例子),那么进攻者就会被拜占庭全部歼灭。虽然邻邦的将军都想攻进拜占庭,但他们面临共同的困扰,就是不确定中间是否有叛徒,因为叛徒可以擅自改变、伪报进攻或撤退的命令。

问题来了,如果每个城邦向其他九个城邦派出一名信使,意味着这十个城邦每个都派出了九名信使,也就是在任何一个时间,都有总计九十次的信息传输,并且每个城市分别收到九条信息,可能每一条都写着不同的进攻时间。

而如果叛徒想要破坏原有的约定时间,就会自己修改相关信息,然后发给其他城邦以混淆视听,遵循错误信息的城邦将重新广播一条错误信息链,原本正确的信息链,会随着他们所发送的错误信息,变成攻击时间与攻击指令相互矛盾的纠结体。

于是,每个邻国的将军都疑神疑鬼,彼此无法达成有效共识——这就是拜占庭将军问题。

解决问题的终极方法:区块链共识机制

我们可以把这些邻国,看成一个由互不信任的多个节点组成的分布式网络。

解决拜占庭问题的传统方法主要有两种:口头协议算法、书面协议算法。但这两种算法都存在显著的缺陷,前者无法做到信息的溯源,后者无法解决信息传输延时、签名记录中心化存储的问题。

直到密码学家中本聪的出现,困扰多年的拜占庭将军问题才得以解决。

其实中本聪只做出了一个简单的变化,即在发送信息的过程中引入了“成本”,并加入了一个随机元素,以保证在一个时间只有一个城邦可以进行广播。

这个所谓的“成本”就是“工作量证明”(即挖矿),并且工作量证明是基于计算一个随机哈希值。任何节点(城邦)必须完成一个计算工作之后,才能向其他节点传播消息,谁第一个完成工作,谁最先传播消息。当某节点发出“进攻”的消息后,各个节点收到消息猴必须签名盖章,确认各自的身份。在这里,中本聪又引入了“非对称加密”技术为信息签名。

我们在之前的文章中提到过过非对称加密,讲过私钥和公钥。简单来说,凭借非对称加密技术,可以有效保护消息内容, 让消息接收者能够确定发送方的身份。

比如,将军A给将军B发送进攻消息,为防止消息泄露,将军A只需要用B的公钥为信息加密,然后B用只有他自己才能使用的私钥解密,验证有效哈希值和附加的签名和时间戳信息即可。将军B可以写一段”签名文本“来证明自己的身份,用私钥签名并广播出去,其他城邦可用B的公钥来验证该签名,确定B的身份。

随后,将军B发给将军C时,会在原来的消息上加入将军B已查阅该信息的记录,并加盖时间戳。其他将军接受消息后,重复此流程直至所有城邦都收到消息。

如果叛徒想要修改进攻信息,其他城邦会立刻识到无法通过加密技术验证的异常信息,同步的虚假信息将不被认可。而且叛徒无法破坏10个城邦中的至少6个,也就是无法破坏大部分的节点,这样信息的一致性就得到了保证。

由此,一个不可信的分布式网络变成了一个可信的网络,所有的参与者可以在某件事在达成共识。

区块链的共识机制通过不断同步各个节点的信息,使得各分布式节点之间达成一种平衡,保证了绝大多数节点的一致性,即达成了共识。这就是区块链共识机制为何如此的特别和关键,它是区块链技术最核心的解决方案。

下次,我们将聊聊区块链共识机制的发展与变迁。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180809A0W55800?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券