关于“拜占庭将军算法”byzantine generals problem

一。拜占庭将军算法的背景:
对于系统坏掉的风险,可以这样假设:我们的操作员可能会误操作、可能会被贿赂或背叛,系统本身可能就有木马程序,系统可能会被黑客或病毒占领,我们自己开发的系统可能有漏洞,我们的开发人员可能会留下后门,这些都可以导致系统坏掉。因此,在这些假设在变成可能的残酷现实中,生存技术是应真正被采用的一种信息安全技术。入侵容忍体系就是生存技术中的核心。如果我们的网络和系统学会生存,那么也就是建立起一个完善的入侵容忍体系。入侵容忍的技术在这样的假设空间中实现它的价值:个人的公开行为在一定的概率下是可预知的,系统在一定的概率下能够正确完成基本的功能。一定的概率并不是指全部,所以,可以允许有错误,因此,入侵容忍还有对纠错理论的联想:即利用纠错码可以在一个错误百出、但有信道容量的信道中准确无误地传输数据,网络系统就这样在错误中“生存”下来的,这就是我们说的入侵容忍体系,它的生存技术有两种实现方式:一是攻击响应的入侵容忍方法,它不需要重新设计系统,可通过高效的检测系统发现异常,利用资源配置系统调整系统资源,并对对错误进行修补(修补系统);二是攻击遮蔽的入侵容忍方法,它需要重新设计整个系统,并通过冗余、容错技术,门槛密码学技术及“拜占庭”技术来实现。-----------------------------------------------
二。算法介绍: “拜占庭”技术,起源于拜占廷将军问题,这是入侵容忍体系的一个基本理论问题。在1982年被提出的“拜占廷将军问题”在今天被许多学者看好,然而在商业上还没有体现其价值。特别是中国的产业界把它放在了一个被遗忘的角落。
【关于“拜占庭将军算法”byzantine generals problem】描述如下:
几个师包围着敌人的一座城市。每一个师都由它自己的司令统帅,司令之间只能通过报信者互相通信。他们必须统一行动 。
某一位或几位司令可能是叛徒,企图破坏忠诚的司令们的统一行动 。
司令们必须有一个算法,使所有忠诚的司令能够达成一致,而且少数几个叛徒不能使忠诚的司令们做出错误的计划,即判国的将军虽然可以传递了虚假消息,也不会影响爱国的将军得到正确的决策。
拜占廷将军问题就是要让爱国的将军达成一致,而不是找叛国的将军。
我们的入侵容忍体系就是这样,只要在众多服务器上得到的正确的计算结果,,那么我们就可以相信这个数据,而不需要去寻找到底谁是间谍。如果要容忍一个捣乱的服务器,在数量上究竟会需要几个服务器?“拜占廷将军”问题可以为我们解答这个问题:在进行混乱真实消息的传播中,两个将军中一个判国,另一个肯定打败仗,三个将军中如果有一个判国,则判国的将军一定有办法让两个爱国的将军不能达成一致,若再增加一个将军,既4个将军中如果只有一个判国,在不知道谁是判国者的情况下,存在一种算法使将军们达成一致,实际上就是三个爱国的将军能够达成一致,而不管判国的将军如何捣乱。既4个将军的团体能够容忍1个叛国将军。同样我们知道,当有t个判国者在捣乱而又无法找出他们的时候,存在一种算法或称做弹性协议,通过这种协议,能够保证爱国的将军达成一致。如果我们把能够容忍t个叛国者的协议叫t弹性协议,学者证明了,不存在3t个将军下的t弹性协议而一定存在3t+1或以上将军下的t弹性协议。就是说要有3t+1个或以上将军才能保证爱国的将军能够达成一致。既要想容忍t个判国者,必须保证总的将军的个数大于3t。这样看来,“拜占廷将军”问题应用于信息安全就是入侵容忍体系的重要技术基础之一。以上讲述的仅仅是“拜占廷将军”问题中简化描述,加之以叙述的形式,就是一个描述性的推理,实际上“拜占廷将军”问题程序计算的方法是很复杂的。据荆老师的介绍,作为入侵容忍体系的理论问题,它可以应用在现实中。实验室开发的CA入侵容忍资料库系统就是应用的案例。当用户查找证书的时候,如何保证得到的是最新的证书而不是过期的证书呢?如果一个服务器保留已经作废的证书欺骗你会如何呢。利用拜占廷法定数目团体系统,实验室很好地解决了这个问题。即使 t个服务器捣乱,输出旧的证书,系统利用拜占廷协议,保证用户一定能够得到最新的证书。由此看来,入侵容忍技术作为网络生存的重要技术,是保证网络和系统安全的一个新的概念和思路。网络的等级保护不仅仅是空间的,也应该是逻辑上的和技术上的。深层防御就是在不同的地方,用不同的方式,建立多条防线,保护关键网络,入侵容忍技术在这个方面就有这不俗的表现。
最后对于如何更好的开发和利用生存技术、如何建立完善入侵容忍体系的问题,荆老师神情急切,他说,这应该是当前中国信息安全最需要的。-----------------------------------------------
英文解释:这个问题是在1982年由Lamport, Shostak, Pease提出,后少人问津。为了利于对“拜占廷将军”问题原意的理解和避免曲解,把英文解释奉上: Byzantine General Problem ——The problem of reaching a consensus among distributed units if some of them give misleading answers. The original problem concerns generals plotting a coup. Some generals lie about whether they will support a particular plan and what other generals told them. What percentage of liars can a decision making algorithm tolerate and still correctly determine a consensus?
三。具体分析:
1。叛徒数大于或等于1/3,拜占庭问题不可解。
情况一:A,B,C三个司令,C是叛徒。A发消息给B,C“进攻”,C发消息给B“撤退”(因为是叛徒)。B收到两个矛盾的命令,无法作出决策。
情况二:A,B,C三个司令,A是叛徒。A发消息给B“进攻”,发消息给C“撤退”(因为是叛徒)。B。C收到不同的命令。
2.用口头信息,叛徒数少于1/3,拜占庭问题可解.
口头信息三条件
传送正确
接收者知道是谁发的
沉默(不发信息)可被检测
什么叫可解?
IC1:所有忠诚副官(B.C,指消息接受者)遵循同一命令。
IC2:若司令(A,消息)是忠诚的,所有忠诚副官遵循其命令
可以证明,多项式复杂性算法OM(m)可以解决拜占庭问题(L Lamport, R Shostak, and M Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 1982, 4(3))
如果记容忍t个叛国者的协议叫t弹性协议(即,在t弹性协议存在的情况下,可以胜利),则:
? 当n=3时,不存在1弹性协议 ? 当n>=1,不存在t>=n/3的t弹性协议
n 如果记容忍t个叛国者的协议叫t弹性协议,则: ? 当n=3时,不存在1弹性协议 ? 当n>=1,不存在t>=n/3的t弹性协议 当n>=1,不存在t>=n/3的t弹性协议 ------------------------------------ OM(m):m个叛徒 OM(0) :发送者将其命令送给每个接收者 每个接受者使用这个值,如果没有收到就认为是“撤退” nOM(m),m>0

?
?
发送者发送他的值给每个接收者
发送者发送他的值给每个接收者 如果第i个接收者获得的值是vi, 接收者i执行算法OM(m-1)发送vi给n-2个其他的接收者
第i个接收者会收到从不同n-1人发来的n-1个值, 取多数认同的值就可以
nOM(m),m>0

?
?
发送者发送他的值给每个接收者
发送者发送他的值给每个接收者 如果第i个接收者获得的值是vi, 接收者i执行算法OM(m-1)发送vi给n-2个其他的接收者
第i个接收者会收到从不同n-1人发来的n-1个值, 取多数认同的值就可以
3。用书写信息,至少两个忠诚,拜占庭问题可解
在口头信息的基础上, 书写信息又增加了两个条件
忠诚司令的签名不能伪造,内容修改可检测
任何人都可以识别司令的签名, 叛徒可以伪造叛徒司令的签名
SM(m)算法
接收者信息收到后,签上自己的名字,再送给别人
用书写信息, 只要有两个忠诚的司令, 拜占庭问题就可解
--------
可以证明,算法SM(m)可以解决m个叛徒的拜占庭问题。
SM(1):如A是叛徒。A给B发“进攻”,给C发“撤退”命令(都被A签名)。B比较从C发来的命令(“撤退”,该命令被C签名了)知A是叛徒。C比较从B发来的命令(“进攻”,该命令由B签名),知A是叛徒。
情况2:B是叛徒。A给B,C发“进攻”命令
四,来自原作者的相关翻译
http://delivery.acm.org/10.1145/360000/357176/p382-lamport.pdf?key1=357176&key2=8885096311&coll=GUIDE&dl=ACM&CFID=65103519&CFTOKEN=82710215
一支拜占庭的军队在敌人的城堡外驻扎,该军队有多个将军,他们各自控制自己的部队,并能相互之间进行通信通过messager。观察敌人后他们必须决策。但是,在这些将军中存在叛徒,会阻止将军们的意见达到一致。因此,必须有一个算法,来保证:
1。所以忠心的将军都执行同一决策。
2。以少数存在的叛徒不能使将军们作出怀的决策。
要判断什么样的决策是坏的,很难。因此,我们只讨论如何让将军们作出决策。
每个将军观察敌人,将自己的观察后的决策通知其他人。设v(i)是第i个将军的观察后的决策。每个将军以某种方法将v(1),v(2)....v(n)综合起来(可看作是一个n维函数)得到一个计划。上面的条件1,很容易实现,只有所有将军采用相同的方法来综合v(1),v(2)....v(n)的信息。条件2的满足还有更强的方法。
如果每个将军要做的决策只是进攻或撤退(attack or retreate),设v(i)是第i个将军所做的认为最好的决策。那么从v(1),v(2)....v(n)到最后的计划的映射方法,就可以是多数原则,即看attack or retreate的决策谁多,就认为是最好的。但是这种情况下,占少数的叛徒还是有机会影响最后的计划,在下面的情况下:如果忠心的将军的意见从数量差不多分成两派。在这种两种意见的支持率不相上下的情况下,无论哪种意见都难称得上是好的。
但是条件1还是有问题,因为叛徒可能给不同的将军发不同的信息。即对第i个将军而言v(k)与第j个将军的v(k)可能是不同的(如果k是叛徒的话)。
因此,对条件1还要满足:
1。每个忠心的将军要获得相同的v(1),v(2)....v(n)
2.如果第i个将军是忠心的,则他发给每个忠心的将军的信息必须被用作v(i)。
对条件1重写(1。每个忠心的将军要获得相同的v(1),v(2)....v(n)):
1a。两个忠心的将军使用相同的v(i)。
1a和2是第i个将军发送的信息的条件,在这样的限制下,我们来考虑一个将军是如何向其他将军传送消息的。可以将这个问题描述为一个司令向他的副官发命令,得到Byzantine Generals Problem.司令必须将他的命令发送个n-1个副官,并且:
IC1所有忠心的副官遵守相同的命令。
IC2如果司令是忠心的,每个忠心副官遵守他的命令。
因此,对于最初的问题(一支拜占庭的军队在敌人的城堡外驻扎。。。。),第i个将军向其他将军发送自己的决策可以看作是第i个将军发出“用v(i)作为我的决策”的命令,到可相对视为其副官的n-1个将军。

    推荐阅读