拜占庭将军问题.md

今天聊聊拜占庭将军问题！

来源

　　拜占庭将军问题，首先由Leslie Lamport与另外两人在1982年提出很简单的故事模型，却困扰了计算机科学家们数十年。
　　拜占庭帝国即中世纪的土耳其，拥有巨大的财富，周围10个邻邦垂诞已久但拜占庭高墙耸立，固若金汤，没有一个单独的邻邦能够成功入侵。任何单个邻邦入侵的都会失败，同时也有可能自身被其他9个邻邦入侵。拜占庭帝国防御能力如此之强，至少要有十个邻邦中的一半以上同时进攻，才有可能攻破。然而，如果其中的一个或者几个邻邦本身答应好一起进攻，但实际过程出现背叛，那么入侵者可能都会被歼灭。 于是每一方都小心行事，不敢轻易相信邻国。这就是拜占庭将军问题。 　　在拜占庭问题里，各邻国最重要的事情是：所有将军如何能过达成共识去攻打拜占庭帝国。达成共识并非坐下来开个会那么简单，有的将军心机深不可测，口是心非，如果有叛徒，可能会出现各种问题：

1. 叛徒可能欺骗某些将军自己将采取进攻行动。
2. 叛徒可能怂恿其他将军行动。
3. 叛徒可能迷惑其他将军，使他们接受不一致的信息，从而感到迷惑。

　　针对拜占庭问题的深入研究，科学家们得出一个结论：如果叛徒的数量大于或等于1/3，拜占庭问题不可解。
解释过程可以用一个副官模型来解释：
假设只有3个人，A、B、C，三人中如果其中一个是叛徒。当A发出进攻命令时，B如果是叛徒，他可能告诉C，他收到的是“撤退”的命令。 这时C收到一个“进攻”，一个“撤退”，于是C被信息迷惑，而无所适从。 如果A是叛徒。他告诉B“进攻”，告诉C“撤退”。 当C告诉B，他收到“撤退”命令时，B由于收到了司令“进攻”的命令，而无法与C保持一致。 正由于上述原因，在只有三个角色的系统中，只要有一个是叛徒，即叛徒数等于1/3，拜占庭问题便不可解。当然，只要叛徒数小于1/3，问题还是可解的。

互联网的拜占庭

　　互联网的存在，首先降低了信息的流通成本。 每个将军配一台电脑，就解决了”书面协议“中骑马通讯造成时间延迟的问题。 如果10个将军中的几个同时发起消息，势必会造成系统的混乱，造成各说各的攻击时间方案，行动难以一致。 谁都可以发起进攻的信息，但由谁来发出呢？

比特币的办法

　　比特币的发明者中本聪想到这么一个方法,中本聪巧妙地在个系统加入了发送信息的成本，即：一段时间内只有一个节点可以传播信息。它加入的成本就是“工作量” 节点必须完成一个计算工作才能向各城邦传播消息，当然，谁第一个完成工作，谁才能传播消息。当某个节点发出统一进攻的消息后，各个节点收到发起者的消息必须签名盖章，确认各自的身份。 中本聪在这里引用现代加密技术为这个信息签名。这种加密技术——非对称加密完全可以解决古代难以解决的签名问题： 消息传送的私密性；能够确认身份；签名不可伪造、篡改。
　　非对称加密算法的加密和解密使用不同的两个密钥.这两个密钥就是我们经常听到的"公开密钥"(公钥)和"私有密钥"(私钥）。公钥和私钥一般成对出现, 如果消息使用公钥加密,那么需要该公钥对应的私钥才能解密; 同样，如果消息使用私钥加密,那么需要该私钥对应的公钥才能解密。
　　非对称加密的作用是:保护消息内容, 并且让消息接收方确定发送方的身份。 比如，将军A想给将军B发送消息，为防止消息泄露，将军A只需要使用B的公钥对信息加密，而B的公钥是公开的，B只需要用只有他自己只的私钥解密即可。 将军B想要在信件上声明自己的身份，他可以自己写一段“签名文本”，并用私钥签名，并广播出去，所有人可以根据B的公钥来验证该签名，确定的B的身份。 由此，一个不可信的分布式网络变成了一个可信的网络，所有的参与者可以在某件事在达成一致。

简化版拜占庭将军问题Raft。

　　另外简化版拜占庭将军问题的还有解决方案：Raft 共识算法。 不少区块链项目都运用到了Raft公司算法，拜占庭将军问题是分布式领域最复杂、最严格的容错模型。 所以将拜占庭将军问题根据常见的工作上的问题进行简化：假设将军中没有叛军，信使的信息可靠但有可能被暗杀的情况下，将军们如何达成一致性决定？
　　对于这个简化后的问题，有许多解决方案，第一个被证明的共识算法是 Paxos，由拜占庭将军问题的作者 Leslie Lamport 在1990年提出最初以论文难懂而出名，后来这哥们在2001重新发了一篇简单版的论文 Paxos Made Simple，然而还是挺难懂的。 因为 Paxos 难懂，难实现，所以斯坦福大学的教授在2014年发表了新的分布式协议 Raft。与 Paxos 相比，Raft 有着基本相同运行效率，但是更容易理解，也更容易被用在系统开发上。 我们还是用拜占庭将军的为例来帮助理解 Raft。 假设将军中没有叛军，信使的信息可靠但有可能被暗杀的情况下，将军们如何达成一致性决定？ Raft 的解决方案大概可以理解成 先在所有将军中选出一个大将军所有的决定由大将军来做。

选举环节：比如说现在一共有3个将军 A, B, C，每个将军都有一个随机时间的倒计时器，倒计时一结束这个将军就会把自己当成大将军候选人，然后派信使去问其他几个将军，能不能选我为总将军？ 假设现在将军A倒计时结束了，他派信使传递选举投票的信息给将军B和C，如果将军B和C还没把自己当成候选人（倒计时还没有结束）并且没有把选举票投给其他，他们把票投给将军A，信使在回到将军A时，将军A知道自己收到了足够的票数，成为了大将军。 在这之后，是否要进攻就由大将军决定，然后派信使去通知另外两个将军 如果在一段时间后还没有收到回复（可能信使被暗杀），那就再重派一个信使，直到收到回复。

结语

故事先讲到这里，本次没有许多技术方面的术语，非技术的朋友也可以大概能理解 Raft 的原理.欢迎star&交流

Dream 2019/12/14