拜占庭将军问题


含义
拜占庭将军问题(Byzantine failures),又称两军问题,1982年在莱斯利·兰波特研究分布式对等网络通信容错问题的论文中提出。在分布式系统的通讯过程中,可能会出现一些局部问题导致计算机发送错误信息,破坏系统一致性。因此,拜占庭将军问题本质上是关于点对点通信中的共识问题。

起源
拜占庭将军问题起源于中世纪时期,由于拜占庭国土辽阔,军队之间通信只能依靠信差传递上层的作战信息。如果有叛徒故意错传上层领导作战信息,会导致作战方案不一致,从而出现“拜占庭将军问题”。为解决这个问题,出现了两种解决方案:一是以口头协议的方式互相派信差传递消息,采用少数服从多数的决策方式达成共识,但如果存在叛徒很难分辨;二是以书面协议的方式派信差传递带有专属签章的书面信息,每个军队都要附议,但传递速度过慢,签章可能丢失。由于两种方案都只能解决一部分问题,而且达成共识所需要花费的时间和资源过大,所以都不受用。

互联网中的拜占庭将军问题
互联网中的拜占庭将军问题是指在信道传输的过程中,部分节点可能会由于工作量过大或遭到某些恶意攻击而导致难以实现信息同步。1999年,Miguel Castro和Barbara Liskov提出了拜占庭容错算法,认为:如果系统中有 2/3 的节点是正常工作的,可以保证系统的一致性和正确性。后来中本聪提出比特币工作量证明机制和非对称加密算法,又为拜占庭将军问题提供了一种新的解决方法。

拜占庭容错算法
假设有n个将军,t个叛徒。当 n=3,t=1,此时A、B、C三人中有一人是叛徒。若A发出【进攻】命令,但叛徒B告诉C【撤退】,这时候C就无法做出判断;若叛徒B向A发出【进攻】命令,向C发出【撤退】命令,此时A、C就无法保持一致,因此当叛徒数大于或等于1/3时,拜占庭问题无法解决。
同理,假设网络节点总数为N,恶意节点数为T,只有当 N>=3T+1,即网络中的正常节点数至少有(2/3)N时,问题才能被解决,从而保证信息的一致性。在网络通信可靠的情况下,拜占庭容错算法可以在一定程度上解决节点故障问题,使系统达成共识

工作量证明(PoW)机制
假设将军A首先发出【进攻】命令并附上自己的签章,其他将军接收后,如果也打算进攻,就会在将军A的命令后面跟上【进攻】命令以及自己的签章。如果A发出【进攻】命令后却没执行,其他将军就可判断A是叛徒,并借此来分辨信息正误。
同理,多个参与节点会通过一系列工作得出一个结果,第一个得出结果的节点会进行全网广播。如果该结果正确,则其他节点会把结果添加到自己的账本中,为争取到下一笔交易的记账权做好计算准备。
黑客必须拥有超过51%的算力才能够破坏网络安全或发布虚假区块,这种做法的花费远大于收益。因此,使用该机制能够降低虚假信息出现的可能性,使系统能够更快达成共识

非对称加密算法
非对称加密算法的加密和解密需要两个不同的秘钥——公钥私钥,两者一般成对出现。如果A想给B发消息,那么A需用B公开的公钥对信息加密,B则需用自己的私钥对信息解密。如果B想表明自己的身份,可以私钥签名写一段“签名文本”并进行广播,其他人可以根据B的公钥验证他的身份。
由于身份和签名是不可伪造的,非对称加密算法保证了传输过程的私密性和签名不完全可信问题。