区块链学习系列(002):拜占庭将军问题
区块链解决了在不可信信道上信息传输、价值转移的问题,而共识机制则解决了在分布式的场景下如何确保一致性的问题,区块链技术之所以能在无第三方的前提下进行价值转移,关键利用了共识机制确保了区块链正常运行。
拜占庭将军问题
比特币最经典的地方就解决了拜占庭将军问题,那么什么是拜占庭将军问题呢?
拜占庭将军问题是一个共识问题: 首先由Leslie Lamport与另外两人在1982年提出,被称为The Byzantine Generals Problem或者Byzantine Failure。核心描述是军中可能有叛徒,却要保证进攻一致,由此引申到计算领域,发展成了一种容错理论。随着比特币的出现和兴起,这个著名问题又重入大众视野。
记得念书的时候有一门密码学的课程,上面写了红蓝军的问题大致描绘出这个问题:在没有现代通讯设备的前提下,两军需要约定一个时间,同时进攻敌军才能有胜算,如果单方面进行进攻则无法击败敌军并且会遭受攻击,那么这个时候如何确保两军约定时间内进行同时进攻呢?
这样就是个死循环,因为彼此永远都无法确定对方是否已经完全接受信息并同意。另外:
通信兵可能被杀害了,也可能叛变了,甚至有可能信息传输错误了
所以从而无法完成一致性,而在分布式系统中的拜占庭将军问题归纳起来就是无法在无第三方的前提下防止信息出错、恶意攻击等问题,从而达成共识。
拜占庭问题解决办法
其实有很多办法来解决这个问题,然而却没有一种可以完美地解决的。下面的内容仅作了解即可,我们只需要知道的是为了解决分布式的一致性问题上,先辈们做了大量的工作。
早期解决办法
Lamport教授在1982年提出拜占庭问题,这个算法在保证活性和安全性(liveness & safety)的前提下提供了(n-1)/3的容错性。这个算法有很多很多的限制条件,假设条件等,而且容错性不高,不过无论如何,开了个先河,从此,就有一大堆算法去解决拜占庭容错了。
PBTF
PBFT是Practical Byzantine Fault Tolerance的缩写,意为实用拜占庭容错算法。该算法是Miguel Castro (卡斯特罗)和Barbara Liskov(利斯科夫)在1999年提出来的,解决了原始拜占庭容错算法效率不高的问题,将算法复杂度由指数级降低到多项式级,使得拜占庭容错算法在实际系统应用中变得可行。
那么比特币中由是如何解决共识问题的呢?区块链中的共识机制有哪些呢?