拜占庭将军问题学习

前几天在坛子里面看到了拜占庭算法的介绍，我也来继续挖一下：
拜占庭将军问题，是一个关于容错计算的古老又耐人寻味的问题。百度百科对它的定义：Byzantine failures又称两军问题，是由莱斯利·兰伯特提出的点对点通信中的基本问题。含义是在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。因此对一致性的研究一般假设信道是可靠的，或不存在本问题。

一、发生背景：
拜占庭帝国是5～15世纪的东罗马帝国，即现在的土耳其伊斯坦布尔。拜占庭城邦拥有巨大的财富，令它的十个邻邦垂涎已久。但是拜占庭高墙耸立，固若金汤，没有一个单独的邻邦能够成功入侵。任何单个城邦的入侵行动都会失败，而入侵者的军队也会被歼灭，使得其自身反而容易遭到其他九个城邦的入侵。这十个城邦之间也互相觊觎对方的财富并经常爆发战争。拜占庭的防御能力如此之强，十个邻邦中的至少一半同时进攻，才能攻破。也就是说，如果六个或者更多的邻邦一起进攻，他们就会成功并获得拜占庭的财富。然而，如果其中有一个或者更多邻邦发生背叛，答应一起入侵但在其他人进攻的时候又不干了，会导致只有五支或者更少的军队在同时进攻，那么所有的进攻军队都会被歼灭，并随后被其他邻邦所劫掠。
因此，这是一个由不互相信任的各个邻邦构成的分布式网络，每一方都小心行事，因为稍有不慎，就会给自己带来灾难。为了获取拜占庭的巨额财富，这些邻邦分散在拜占庭的周围，依靠士兵相互通信来协商进攻目的及进攻时间。这些邻邦将军想要攻克拜占庭，面临着一个困扰，也就是拜占庭将军问题：邻邦将军不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，将军们能否找到一种分布式协议来进行远程协商，达成统一共识机制，进而赢取拜占庭城堡攻克战役的胜利呢，这就是拜占庭将军问题。

二、解决方案：
1.口头协议，每个节点给所有的其他节点发送信息，每个节点根据自己接受到的所有信息来决定最终的对策。它的核心思想是，确保每个消息准确投递，消息接受者只知道消息的发送者身份，但却不知消息的源头，即不可回溯。
前提：1.若叛徒数为m，当且仅当将军总数n>=3m+1时才有解。
2.所有将军派信使对其它所有将军发出动作的信息，进攻命令=1, 按兵不动=0。
3.所有将军将按照收到的1或0最多的个数执行进指令。比如，收到1比0多则进攻，收到0比1多则不动。
经各种情况分析证明，不管叛将如何捣乱，忠将们都能找到一种共识机制，以此来赢取胜利，则问题可解。
缺点：消息不可回溯，并且每个节点向全节点发送大量的消息，会很容易造成网络堵塞。BTC很聪明的采用了POW工作量证明方法，而未采用此法。
2.书面协议：算法要求签名不可伪造，一旦被篡改即可发现，同时任何人都可以验证签名的可靠性。书面协议算法也不能完全解决拜占庭将军问题。因为该算法没有考虑信息传输时延、其签名体系难以实现、且签名消息记录的保存难以摆脱中心化机构。

三、区块链新思路
与已有方法相比，区块链技术将是更完美的解决方案。区块链是怎样来解决这个问题的呢，它为发送信息加入了成本，这降低了信息传递的速率，并加入了一个随机数以保证在一段时间内只有一个矿工可以进行广播。它加入的成本就是“工作量”，区块链矿工必须完成一个随机哈希算法的计算工作量才能向各城邦广播消息。
当用户向网络输入一笔交易的时候，他们使用内嵌在客户端的标准公钥加密工具来为这笔交易签名，这好比拜占庭将军问题中他们用来签名和验证消息时使用的“印章”。因此，哈希计算速率的限制，加上公钥加密，使得一个不可信网络变成了一个可信的网络，使得所有参与者可以在某些事情上达成一致。拜占庭将军问题的区块链解决方案可以推广到任何在分布式网络上缺乏信任的领域，比如说域名、投票选举或其他需要分布式协议的地方。