LOADING...
LOADING...
LOADING...
当前位置: 玩币族首页 > 区块链资讯 > SCRY技术分享拜占庭将军问题的简述

SCRY技术分享拜占庭将军问题的简述

2021-06-30 scry 来源:区块链网络

拜占庭的简述

本文将用于介绍著名的拜占庭将军问题。在介绍拜占庭将军问题之前,先简单说一下拜占庭。拜占庭帝国,在古代西欧也被称之为东罗马帝国。是一个位于欧亚交界处的封建君主制国家,其领土包括现在的欧洲南部,西亚和北非。公元四世纪左右,罗马帝国开始分列为罗马东部和罗马西部,这两个国家都被视为罗马正统,大概到公元十世纪,罗马西部陷落,随着神圣罗马帝国的建立,罗马东部失去了罗马这个单词的独占权,开始被称之为东罗马帝国。大概在16世纪之后,开始出现了拜占庭帝国的说法。值得一提的是,拜占庭帝国的首府君士坦丁堡被第四次十字军东征攻陷,从此一蹶不振。1453年5月29日,君士坦丁堡被强大的奥斯曼帝国攻陷,末代皇帝君士坦丁十一世战死。东罗马帝国就此终结。当然,此文不是介绍东罗马帝国历史的文章,在此仅简述拜占庭帝国的历史。

拜占庭将军问题是什么

拜占庭将军问题和拜占庭的历史其实并无关联,拜占庭将军问题也不是历史上真实存在的问题,他是著名计算机大神兰伯特于1982年提出的。拜占庭问题描述的是如下的场景:

假设有一座城堡,拜占庭帝国想攻陷这座城堡。所以派出了很多支军队,因为通讯条件很落后,军队和军队之间必须经过信使来传递作战命令。城堡十分坚固,可以抵御一两只军队的进攻。只有所有军队同时进攻,才可以攻陷城堡。为了保证作战命令的统一,提出一个办法,投票。超过半数投票决定作战命令。比如:决定明天早上进攻,如果有半数的军队同意这个作战计划。则在明日早晨开始一起进攻。反之,如果一大半人都不同意明天早上进攻,则明早就不进攻。现在存在的问题是:军队中有叛徒。叛徒会随意调整作战命令。

我们现在用图一来表示这种困境,在图示中,我们用黄色的小人代表正常的部队,粉色的小人代表判叛徒。A表示进攻Attack,R代表拒绝Reject。因为正直的的部队会忠实的执行命令,所以我们把A和R标记在他们身上。

如图所示,身上标记A的三位将军表示他们决定“明早发动进攻”,身上标记R的三位将军决定明早不应该发动进攻,现在叛徒至关重要。叛徒的这一票将决定明早是否决定进攻。这时候叛徒给三位决定进攻的将军传递的消息是明早发动进攻,给三位不进攻的将军发送的消息是明早不发动进攻。所以三位决定进攻的将军知道了,有4票发动进攻的,那么大多数人决定进攻那我明早就发动攻势。三位不进攻的将军则知道,有四票不发动进攻的,那我明早不进攻。所以拜占庭难度就产生了,这些部队有的进攻有的撤退,战斗就失败了。

以上的图示和背景就是拜占庭问题或者称之为拜占庭容错问题。

兰波特之问

所以兰波特提出这个问题是为什么呢?

兰波特描述的是:世界上有很多个计算机,分布在世界上不同的位置。这些分布在不同地理位置的计算机,就像是驻扎在不同城市的将军们一样。但是计算机会出故障,也有可能会有黑客攻击,或者直接加入恶意节点。这些坏掉的计算就相当于叛徒。在这种状况下,我们如何保持一致性,就是指这些忠诚的计算机,他们的结果是一样的。另外我们关心的问题是,如何保持正确性。这里对正确性作出解释:如果大多数将军说要进攻,那我们就应该进攻,如果大多数将军说撤退,那我们就该撤退。尽管系统中存在故障和恶意节点,但是我们大多数节点都可以保持一致性和正确性,我们的系统还是正常的。这个问题发展至今,已经有四十余年的历史了。

为此也提出了分布式系统的原则

一致性

正确性

兰波特针对这个问题提出了自己的解法。

口头协议

书面协议

为了描述口头协议,我们提出了一个将军副官模型,其实哪个人是将军,哪个人是副官并不重要。所谓将军就是第一个发起命令的人:比如将军做出决定明早进攻,然后传递给其他人。其他人都叫做副官,副官可以执行将军的命令。为此我们需要两个假设:

忠诚副官,所有忠诚的副官必须执行同一个命令。比如一起进攻,一起撤退。

忠诚将军,如果将军是忠诚的,所有忠诚的副官必须执行他的命令。

以上的假设的前提是忠诚,因为无论是司令还是副官,他们都有可能是叛徒,叛徒的行为不可预测。以上两个原则分别对应分布式协议的基本原则,一致性,准确性。

怎么做到这一点呢?

兰波特提出,假如一共有n个将军,其中有m个叛徒。当n>3m时,这个问题是可解的。

比如我们有10个将军,有2个是恶意的10>3*2,这个问题是可解的。但是有三个人,其中有一个是叛徒,那这个问题是不可解的。因为没有满足n>3m。

举个栗子:

假定有3个将军1个叛徒,n = 3, m =1

如上图所示,身上带有c标志的为commander,表示为发起命令的人。其他人副官,身上标记1,2。继续用粉色表示叛徒。现在将军给副官1,2发送进攻命令。忠诚副官1接到进攻命令之后并不会决定发起进攻,因为他也不知道将军是否是忠诚的,所以他继续询问2,是否发动进攻。但是2是叛徒,他自己接受到c的进攻命令,他传递给1的命令是不进攻。这时1会收到两个消息,进攻和不进攻,1比1。所以他就没办法决定自己是进攻还是不进攻。

接下来,我们转换视角,考虑将军是叛徒的问题。将军分别给1下达了进攻指令,给2下达了撤退指令。此时1收到进攻指令后,继续询问2。2忠诚的传递了自己收到的命令不进攻。此时1收到的信息又是一票进攻一票撤退,无法决定。2面临的也是同样的问题。所以在n=3,m=1的情况下,这个问题是无解的。

下面我们来看有解的状况。

下一种状况下,n=4,m=1。即一共有四个将军,一个叛徒。

还是依照之前图例表示各种部队的性质。将军c给副官1,2,3,4发送进攻的通知。1接到进攻的通知之后再询问2,到底接了什么命令。因为2是忠诚的,所以如实的传递自己得到是进攻A。然后再询问副官3。副官3因为是叛徒,告诉1自己得到的是撤退。这时,1一共接到3个消息,两个进攻一个撤退。按照多数原则,他就可以确定第二天可以进行进攻。如果我们按照同样的方法去分析2,他得到结果是类似的。所以决策之后,所有忠诚的副官均进行一样的命令进攻,而且在司令官为忠诚的情况下,所有副官执行和司令官一样的命令进攻。刚好符合前面定下来的原则。

接下来我们看更加复杂的状况,将军是叛徒的情况。假设将军给1,2,3号分别发送了进攻,进攻和撤退三个命令。

我们站在1的角度,接受到司令的进攻命令,然后和2交换信息得到一个进攻,再和3交换信息。得到两个进攻和一个撤退,所以可以决定执行进攻。

从2的视角出发,2接到司令官的进攻信息,从1得到进攻信息,从3得到撤退信息。所以可以执行进攻。

从3的视角出发,3从司令官那里接到撤退信息,从1得到进攻,从2得到进攻。所以可以执行进攻。

总体来看,因为司令官不是忠诚的,所以不用顾虑司令官忠诚的条理。同时123都是忠诚的,他们同时执行进攻。也符合假设。所以这种情况下,是可解的。

我们再次提升复杂度,探讨有两个叛徒的情况,即便m=2。根据公式,要想问题有解,我们必须要有七个人。n=7

情况较为复杂,就不在图上标注各位副官之间的信息交互情况,仅标注司令官给各位副官下达的命令。在描述这个情况情况之前,先强调一下这里分析需要的思路:递归。递归简单来说就是套娃,比如你照镜子的时候,再拿第二面镜子对着镜子中的自己。或者你在直播的时候,用摄像头对着自己的屏幕。这里不是专门的算法分析介绍,不再强调递归。

回到图上,我们假设司令官是忠诚的,其中5和6号副官是叛徒。他给每个副官都下达了进攻命令。

下面我们来列一个表格表述现在的状况

我们从1出发来看这个表格,看看一号副官是如何决策的。1毫无疑问接到了将军的进攻命令。但是他不可能接受到将军的命令就进攻,还是要交流,确定别人都接受到的是什么命令。

首先他要确定2接受的是什么命令。

第一重分析,他直接问V2,V2接受到了什么命令。2是忠诚的自然是说:2接受的是进攻。然后1开始问V3:V2接受的是什么命令。依次类推。因为5号和6号是叛徒,他说什么都可能,随意用无关字母小写的a,b来表表示。根据多数原则,1可以确定一件事,2号接受的确实是进攻命令。

接下来他开始确定v3到底接受的是什么命令。忠诚副官其实得到的信息分析都是类似的,我们不再重复。

我们直接开始决策V5和V6,即开始确定5号和6号得到的是什么命令。以5为例,因为2是叛徒,所以我们直接用不同的字母表示他给别人说自己得到的是什么。最终我们其实不清楚他所说的大多数命令是什么,所以用X表示,他可能是进攻也可能是撤退。

每一类的问题分析完之后,1不难得出结论,2,3,4号得到命令是进攻。至于5和6他们得到什么样的命令并不会影响最终决定。所以再分析完A的决策状况之后,他的决策就确定下来了:进攻。

有兴趣的话们可以自行填充上面的表格,也可以站在2,3,4,5,6的角度上再次进行分析。总而言之,这种状况下,拜占庭将军问题是有解的。

最终结论,1,2,3,4会选择进攻,而且忠诚的将军下发的进攻命令也会被忠诚的副官执行。

有兴趣的话,也可以推演一下将军和6号是叛徒的情况。

通过以上的分析不难看出,这个算法的复杂度相当之高。而且波兰特提出这个问题的时候是不考虑网络延迟的,所以这个方法在计算机中并不会被使用。后来又有人提出了更加高效的PBFT算法。有兴趣的话可以阅读相关的论文。

结尾

拜占庭容错问题和区块链息息相关。区块链的问题也是要解决一致性问题。简单来说,以比特币为首的区块链提出了POW算例证明。需要节点都参与解决数学题,如果率先解决数学难题,则有记账的权利。无疑增加了恶意节点的成本,你必须别其他节点做的更快才有作恶的权利。后来还有也陆续提出了POS算法,DPOS算法等。也是为了解决本文开始提到的一致性和正确性问题。希望本文可以帮大家建立对于拜占庭容错问题的基本概念。

—-

编译者/作者:scry

玩币族申明:玩币族作为开放的资讯翻译/分享平台,所提供的所有资讯仅代表作者个人观点,与玩币族平台立场无关,且不构成任何投资理财建议。文章版权归原作者所有。

LOADING...
LOADING...