首页 能链洞察 区块链百科

区块链的共识机制,从一个拜占庭将军的问题说起

区块链的共识机制,从一个拜占庭将军的问题说起

发布时间:2020.05.11

莱斯利?兰伯特说:故事让问题变得受欢迎。

 

大家在了解区块链的共识算法时,多少都听说过拜占庭将军问题,我们曾在区块链共识机制篇就稍有介绍。实际上,拜占庭将军问题,是莱斯利·兰伯特在研究分布式系统容错性时,引入的一个故事。其核心描述是军中可能有叛徒,却要保证进攻一致,由此引申到计算领域,发展成了一种容错理论。

 

随着区块链技术的出现和兴起,这个著名问题又重入大众视野

 

一、什么是拜占庭将军问题

 

拜占庭将军问题是由Leslie Lamport等人在1982年提出,被称为The Byzantine Generals Problem或者Byzantine Failure,其可简单描述为:

 

拜占庭帝国想要进攻一个强大的敌城,由拜占庭将军们分别率领一支军队共同围攻。因为这座城市很强大,如果不协调统一将军们的行动策略,部分军队进攻、部分军队撤退会造成围困失败。因此各位将军必须通过投票来达成一致策略,要么一起进攻,要么一起撤退

 

 

但因为拜占庭将军们是分散在各个角落,他们只能通过信使互相联系。这样一来每位将军根据自己的投票和其他将军送过来的投票,获得投票结果,从而决定是进攻还是撤退。

 

而问题的复杂性就在于:将军中可能出现叛徒,他们不仅可以投票给错误的决策,还可能会选择性地发送投票。假设忠诚的将军中一半投“进攻”,另一半投“撤退”,这时候叛徒可能故意给投“进攻”的将军投“进攻”,而给另外投“撤退”的将军投“撤退”。这样,双方得到的投票结果都是按自己的决策实施,一致性就遭到了破坏。此外,即便所有的将军都是忠诚的,将军之间派出去的信使也可能被敌军截杀,甚至被间谍替换,也就是说将军之间进行交流的信息通道是不能保证可靠性的。

 

那拜占庭将军问题有解吗?答案是有的,但有个前提,那就是叛徒的数量不能大于等于1/3,也就是实现拜占庭容错,使得即便存在叛徒的情况下,忠诚的将军们仍能达一致目标。

 

简单来说,拜占庭容错是能够抵抗拜占庭将军问题导致的一系列失败的系统属性。看到这里想必大家已经知道了,这不就是区块链技术的共识机制吗?

 

 

二、拜占庭容错与共识机制

 

实际上,拜占庭容错就是解决去中心化系统的共识问题,而区块链的核心价值之一就是共识

 

在区块链项目中,最常用的BFT共识机制是实用拜占庭容错算法PBFT(Practical Byzantine Fault Tolerance)。该算法是Miguel Castro和Barbara Liskov在1999年提出来的,解决了原始拜占庭容错算法效率不高的问题,将算法复杂度由节点数的指数级降低到节点数的平方级,使得拜占庭容错算法在实际系统应用中变得可行

 

在PBFT 模型下,有一个节点会被当做主节点,而其他节点都是备份节点,PBFT就是是针对状态机副本复制为主的分布式系统执行环境开发的算法,旨在让系统中大部分的诚实节点来覆盖恶意节点或无效节点的行为。在PBFT算法中,首先采用密码学算法保证节点之间的消息传送是不可篡改,其次一个节点代表一票,最终以少数服从多数的方式实现了拜占庭的容错演算,至多容错量以不超过全部节点数的1/3,意即如果有超过2/3的正常节点,整个系统就便可正常运作(R≥ 3F + 1; R:节点总数,F:有问题节点总数)。

 

正是通过共识机制、加密算法等技术,区块链将一个去中心化的不可信网络变为可信网络,使得所有参与者可以在某些事情上达成一致,也让价值传递成为了可能

 

有关区块链共识机制的精彩内容,可戳下方往期精选查阅更多~