academy

拜占庭将军问题——区块链共识算法系列讲堂之二

article-photo

艾贝学院|2021-07-16 11:26:16

如今区块链已成为一个高频词汇,不时出现在公众视野里,但是伴随其出现的种种专业术语和生僻词汇,又让人望而生畏。那么区块链究竟是怎样一种技术?能为我们的生活带来什么改变

 

艾贝链动作为区块链技术研发机构,旗下智库组织“艾贝学院”,将致力于为大家体系化的讲解区块链知识。上一讲中我们讲解了共识以及算法的概念,并且提到了数字世界并不那么岁月静好,猜疑的个体之间为共识系统带来了极大挑战。那么这些挑战是什么以及该如何消减这便是本文将要回答的

 

拜占庭将军问题的由来

拜占庭帝国即东罗马帝国395-1453年),是欧洲历史上最悠久的君主制国家其首都君士坦丁堡是在希腊古城拜占庭的基础上建立起来的。

 

拜占庭将军问题并不是真实存在于历史中,而是图灵奖获得者莱斯利·兰伯特Leslie Lamport1982提出的一个假想问题

 

由于当时拜占庭罗马帝国国土辽阔,每支军队的驻地分隔很远,将军们只能靠信使传递消息。发生战争时,将军们必须制定统一的行动计划。然而,这些将军中有叛徒,叛徒希望通过影响统一行动计划的制定与传播,破坏忠诚将军们一致行动计划。因此,将军们必须有一个预定的方法协议,使所有忠诚的将军能够达成一致,而且少数几个叛徒不能使忠诚的将军做出错误的计划。也就是说,拜占庭将军问题的实质就是要寻找一个方法,使得将军们能在一个有叛徒的非信任环境中建立对战斗计划的共识。

 

在分布式系统中,特别是在区块链网络环境中,也和拜占庭将军的环境类似,有运行正常的服务器(类似忠诚的拜占庭将军),有故障的服务器,还有破坏者的服务器(类似叛变的拜占庭将军)。

 

拜占庭将军问题的共识博弈

在拜占庭将军问题中,将军作为命令发起者,副官作为命令执行者,副官可以执行将军的命令,也可以不执行。

作为忠诚阵营的成员,需要达成这样的共识:

1一致原则:忠诚副官之间要保证进攻和撤退的一致

2服从忠诚将军:如果将军是忠诚的,所有忠诚的副官都要执行将军的命令

3多数原则:副官之间询问各自接受到的命令,会执行多数副官接收到的命令

对此,莱利斯·兰伯特提出,当忠诚者的人数达到叛徒人数三倍以上时,可以保证协议的有效达成。

假设将军,副官1,副官2,副官3四个人中,副官2是叛徒。在将军下达撤退命令后,副官的心理活动如下:

副官1在不能确定将军身份的情况下,不会直接撤退,会询问副官2

副官2因为自己叛徒身份,会传递给副官1假信息,即进攻命令

副官3忠诚的副官3会告诉副官1 传递撤退命令

副官1将军发布的是撤退命令,副官3 接收的是撤退命令,所以整体服从多数指令,从而指挥士兵撤退。

如果当忠诚者的人数达不到叛徒人数3倍,副官1和副官2 接收的信息不一致,所以无法做出最终决策。由于副官3的出现,打破了平衡,副官1和副官3的进攻命令大于副官2的干扰,从而做出正确判断。

 

假设将军,副官1,副官2,副官3四个人中,将军是叛徒,三位副官都是忠诚的,三位副官两两互通,服从多数人的命令即可,同样能保证信息的一致性。

同理,如果6名副官,其中有两人是叛徒,副官1需要“副官2所接收到的命令是什么”分别问副官3,副官4,副官5,副官6,再根据多数原则最终达成了撤退的共识

 

拜占庭将军问题引出的共识机制

拜占庭将军问题阐述的是:在信息交互不可靠的情况下,达成共识、协同行动存在很大的困难。叛徒对错误信息的肆意发布,很可能会导致战争失败类比区块链世界,网络上的两个节点直接通信也存在着失败的可能性,所以建立有效的共识机制是非常必要的。

 

由于不同的区块链项目类型对信息记录和区块生成有不同的要求,所以目前发展到有30多种共识机制来解决不同项目中的拜占庭将军问题

 

比如比特币系统是通过一个称为“工作量证明”(Proof of Work,PoW)的机制完成的;以太坊系统采用权益证明”(Proof of Stake,PoS),即持币越多越久,获得奖励的概率越大;再后来DPosPoA等机制的先后诞生,构成了一部波澜起伏的区块链共识发展史它们分别有着各自的特点以及优劣势,我们会在下一讲中为大家道来