共识算法|拜占庭将军问题的深入思考 2018|blockchain

拜占庭将军问题的经典解决方案最好的描述资料 http://www.8btc.com/baizhantingjiangjun
注：论文中的拜占庭将军问题的两个方法只是解决拜占庭问题的手段之一，等价于PBFT也是解决拜占庭问题的手段之一。
PBFT是Practical Byzantine Fault Tolerance的缩写，意为实用拜占庭容错算法。该算法是Miguel Castro (卡斯特罗)和Barbara Liskov（利斯科夫）在1999年提出来的，解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。
经典方案中的1/3的容错率区块链的解决方案比如PoW为什么可以突破1/3这个阈值而达到1/2，主要是因为经典的解决方案都利用了投票的方式。
下面简单证明，为什么投票方式的阈值是1/3：

从接收端的角度，n个节点里面可能有f个恶意节点出不回应。这种情况下客户端必须要在有回应的 n-f 个消息中进行判断。但由于系统是异步的，即这f个不回应的消息可能都不是恶意的节点，只是因为延迟等问题。也即在n-f个回应中，可能还有f个消息是恶意节点发出的。为了能在这n-f个回应中通过多数决得出正确的结果，必须要求 n-2f>f，即n>3f。

经典解决方案的缺陷

节点之间要相互认识
因为节点之间要相互交互，带宽占用达到 O(n2)O ( n 2 ) 的规模，这就是Hyperledger基本达到百级的节点就不能用的主要原因。

区块链的解决方案（PoW）看了PoW真的有很深的触动，真正的创新不是繁杂的推导和证明，大道至简。
PoW采用的方法是专制的方式，不用投票，不用两两交互，谁赢了这个游戏，谁说了算，使得系统达到了一致性。
【共识算法|拜占庭将军问题的深入思考】如果诚实节点占据多于50%的算力，从概率的角度看，诚实节点总会赢得游戏。从社会学的角度看，设计了coinbase的奖励，所以掌握了51%的人，为了经济利益也会去维护这个系统。