The Byzantine Generals Problem(拜占庭将军问题)
这个问题是在1982年由Lamport, Shostak, Pease 提出 ——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?
一、拜占庭将军问题的背景
对于系统坏掉的风险,可以这样假设:我们的操作员可能会误操作、可能会被贿赂或背叛,系统本身可能就有木马程序,系统可能会被黑客或病毒占领,我们自己开发的系统可能有漏洞,我们的开发人员可能会留下后门,这些都可以导致系统坏掉。因此,在这些假设在变成可能的残酷现实中,生存技术是应真正被采用的一种信息安全技术。入侵容忍体系就是生存技术中的核心。如果我们的网络和系统学会生存,那么也就是建立起一个完善的入侵容忍体系。
入侵容忍的技术在这样的假设空间中实现它的价值:个人的公开行为在一定的概率下是可预知的,系统在一定的概率下能够正确完成基本的功能。一定的概率并不是指全部,所以,可以允许有错误,因此,入侵容忍还有对纠错理论的联想:即利用纠错码可以在一个错误百出、但有信道容量的信道中准确无误地传输数据,网络系统就这样在错误中“生存”下来的,这就是我们说的入侵容忍体系,它的生存技术有两种实现方式:一是攻击响应的入侵容忍方法,它不需要重新设计系统,可通过高效的检测系统发现异常,利用资源配置系统调整系统资源,并对对错误进行修补(修补系统);二是攻击遮蔽的入侵容忍方法,它需要重新设计整个系统,并通过冗余、容错技术,门槛密码学技术及“拜占庭”技术来实现。
二、算法介绍
“拜占庭”技术,起源于拜占廷将军问题,这是入侵容忍体系的一个基本理论问题。在1982年被提出的“拜占廷将军问题”在今天被许多学者看好,然而在商业上还没有体现其价值。特别是中国的产业界把它放在了一个被遗忘的角落。
拜占庭将军问题可以抽象成:
设计一个协议,一个司令要送一个命令给他的n-1个副官,使得
IC1. 所有忠诚的副官遵守同一个命令。
IC2. 假如司令是忠诚的,则每一个忠诚的副官遵守他送出的该命令。
约定:忠诚的将军将遵守协议,而叛徒则可能破坏协议,尽可能的干绕其它人的判断。叛徒是匿名的。而且最后不需要确定谁是叛徒。拜占廷将军问题就是要让爱国的将军达成一致,而不是找叛国的将军。
我们的入侵容忍体系就是这样,只要在众多服务器上得到的正确的计算结果,,那么我们就可以相信这个数据,而不需要去寻找到底谁是间谍。如果要容忍一个捣乱的服务器,在数量上究竟会需要几个服务器?
“拜占廷将军”问题可以为我们解答这个问题:在进行混乱真实消息的传播中,两个将军中一个判国,另一个肯定打败仗,三个将军中如果有一个判国,则判国的将军一定有办法让两个爱国的将军不能达成一致,若再增加一个将军,既4个将军中如果只有一个判国,在不知道谁是判国者的情况下,存在一种算法使将军们达成一致,实际上就是三个爱国的将军能够达成一致,而不管判国的将军如何捣乱。
也就是说4个将军的团体能够容忍1个叛国将军。同样我们知道,当有m个判国者在捣乱而又无法找出他们的时候,存在一种算法或称做弹性协议,通过这种协议,能够保证爱国的将军达成一致。如果我们把能够容忍m个叛国者的协议叫m弹性协议,学者证明了,不存在3m个将军下的m弹性协议而一定存在3m+1或以上将军下的m弹性协议。就是说要有3m+1个或以上将军才能保证爱国的将军能够达成一致。如果要想容忍m个判国者,必须保证总的将军的个数大于3m。
三、具体分析
1 叛徒数大于或等于1/3,拜占庭问题不可解。
情况一:A,B,C三个司令,C是叛徒。A发消息给B,C“进攻”,C发消息给B“撤退”(因为是叛徒)。B收到两个矛盾的命令,无法作出决策。
情况二:A,B,C三个司令,A是叛徒。A发消息给B“进攻”,发消息给C“撤退”(因为是叛徒)。B。C收到不同的命令。
2.用口头信息(Oral Message,OM),叛徒数少于1/3,拜占庭问题可解.
口头信息三条件
A1)传送正确
A2)接收者知道是谁发的
A3)沉默(不发信息)可被检测
可以证明,多项式复杂性算法OM(m)可以解决拜占庭问题.
递归设计协议OM(n, m)为
OM(n, 0)
1.司令发送命令给所有副官。
2.副官按照接收到的命令行事。
OM(n, m):
1.司令发送命令给所有副官,设副官i收到命令vi。
2.分为独立的n-1轮:对每个副官i,将其视为司令,使用协议OM(n-1, m-1)将vi发送到所有其它副官。
3.这样每个副官都收到n-1条信息,每个副官都按照出现次数更多的命令行事(如果进攻和撤退的命令一样多,则默认取撤退)。
结论:当n
3 用书写信息(Signed Message),至少两个忠诚,拜占庭问题可解
在口头信息的基础上, 书写信息又增加了两个条件
A4.1) 忠诚司令的签名不能伪造,内容修改可检测
A4.2)任何人都可以识别司令的签名, 叛徒可以伪造叛徒司令的签名
可以证明,算法SM(m)可以解决m个叛徒的拜占庭问题。
SM(m)算法
1)接收者信息收到后,签上自己的名字,再送给别人
2)用书写信息, 只要有两个忠诚的司令, 拜占庭问题就可解
SM(1):如A是叛徒。A给B发“进攻”,给C发“撤退”命令(都被A签名)。B比较从C发来的命令(“撤退”,该命令被C签名了)知A是叛徒。C比较从B发来的命令(“进攻”,该命令由B签名),知A是叛徒。
结论:当n>=m+2时,n个将军中的m个叛徒可以让将军们可以达成一致,也就是满足交互一致性IC1和IC2。此时共需要信息交换轮数m+1.
原文链接:/l58xs8.com