首页/
艾贝学院/
拜占庭将军问题——区块链共识算法系列讲堂之二
如今区块链已成为一个高频词汇,不时出现在公众视野里,但是伴随其出现的种种专业术语和生僻词汇,又让人望而生畏。那么区块链究竟是怎样一种技术?能为我们的生活带来什么改变?
艾贝链动作为区块链技术研发机构,旗下智库组织“艾贝学院”,将致力于为大家体系化的讲解区块链知识。上一讲中我们讲解了共识以及算法的概念,并且提到了数字世界并不那么岁月静好,猜疑的个体之间为共识系统带来了极大挑战。那么这些挑战是什么以及该如何消减?这便是本文将要回答的。
拜占庭将军问题的由来
拜占庭帝国即东罗马帝国(395年-1453年),是欧洲历史上最悠久的君主制国家,其首都君士坦丁堡是在希腊古城拜占庭的基础上建立起来的。
拜占庭将军问题并不是真实存在于历史中的,而是由图灵奖获得者莱斯利·兰伯特(Leslie Lamport)在1982年提出的一个假想问题:
由于当时拜占庭罗马帝国国土辽阔,每支军队的驻地分隔很远,将军们只能靠信使传递消息。发生战争时,将军们必须制定统一的行动计划。然而,这些将军中有叛徒,叛徒希望通过影响统一行动计划的制定与传播,破坏忠诚将军们的一致行动计划。因此,将军们必须要有一个预定的方法协议,使所有忠诚的将军能够达成一致,而且少数几个叛徒不能使忠诚的将军做出错误的计划。也就是说,拜占庭将军问题的实质就是要寻找一个方法,使得将军们能在一个有叛徒的非信任环境中建立对战斗计划的共识。
在分布式系统中,特别是在区块链网络环境中,也和拜占庭将军的环境类似,有运行正常的服务器(类似忠诚的拜占庭将军),有故障的服务器,还有破坏者的服务器(类似叛变的拜占庭将军)。
拜占庭将军问题的共识博弈
在拜占庭将军问题中,将军作为命令发起者,副官作为命令执行者,副官可以执行将军的命令,也可以不执行。
作为忠诚阵营的成员,需要达成这样的共识:
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),即持币越多越久,获得奖励的概率越大;再后来DPos、PoA等机制的先后诞生,构成了一部波澜起伏的区块链共识发展史,它们分别有着各自的特点以及优劣势,我们会在下一讲中为大家道来。