拜占庭将军问题
拜占庭将军问题，首先是由Leslie Lamport与另外两人在1982年提出，故事的模型非常简单，却困扰了计算机科学家们数十年，可以说拜占庭将军问题是计算机分布式系统里的一个比较棘手的问题。
故事大概是这么说的：
拜占庭帝国指的是中世纪的土耳其，拜占庭帝国拥有巨大的财富
周围有10个邻邦对拜占庭垂涎已久，但拜占庭高墙耸立，固若金汤，没有任何一个单独的邻邦能够成功入侵。
任何单个邻邦入侵的都会失败，同时也有可能自身被其他9个邻邦同时入侵。
拜占庭帝国防御能力如此之强，至少要有十个邻邦中的一半以上同时进攻，才有可能攻破。
大家可能会想，这个还不简单，只要5个以上邻邦达成一致一起入侵，干掉拜占庭帝国岂不是很容易。
然而，大家有没有想过一个问题，如果其中的一个或者几个邻邦本身答应好一起进攻，但实际过程出现背叛，那么其余入侵者都会被歼灭。于是每一方都小心行事，不敢轻易相信邻国。
这就是拜占庭将军问题
在拜占庭问题里，各邻国最重要的事情是：所有将军如何能过达成共识去攻打拜占庭帝国。
达成共识并非坐下来开个会那么简单，有的将军心机深不可测，口是心非，如果有叛徒，可能会出现各种各样的问题，比如：叛徒可能欺骗某些将军自己将采取进攻行动，结果最后却没有行动。或者叛徒可能怂恿其他将军行动。再或者叛徒可能迷惑其他将军，使他们接受不一致的信息，从而让对方困惑到底要不要进攻，导致无法行动。科学家们做过深入的分析和研究，最后的结论是只要叛徒的数量大于等于1/3，那么任务就会失败。
那这个问题怎么解决呢，起初科学家提出了两种解决方案：
- 第一个方案是口头信息协议，也就是每个邻邦的将军们派人用口信传达消息，口头协议的算法很简单，如果其中一个邻邦发消息出去是进攻还上撤退，信息会传到所有其他邻邦，然后每个邻邦收到信息同样也是将信息传递给其余所有邻邦，每个邻邦都是信息的转达者，一轮下来，每个节点手上都会有10个信息（进攻或者撤退），有叛徒的话，那信息可能有进攻或者不进攻的不一致消息。每个人相当于手里有一本消息的账本，该到底怎么决策呢？如果有一半以上的人说进攻，那么采取进攻行动就是能成功的，所以这时即便有叛徒，只要听大部分人的，少数服从多数来行动就没什么大问题。但是这种口头协议的算法也存在明显的缺点，口头协议并不会告知消息的上一个来源是谁，也就是消息不可追根溯源，出现信息不一致也很难找到叛徒在哪里。
- 第二个方案是书面信息协议，既然上面说的消息无法追溯根源，那就用写信，信上还要带上将军的签名，比如每个国家都向其他所有国家写信，约定几月几日几点几分一起攻打拜占庭，收到信的国家如果同意就签字盖章，这些方式相比口头信息，消息都是有记录的，有了叛徒也能会找出来。但是在现实中也面临几个问题，首先中世纪的邻邦之间沟通只能靠信使骑马，将军们互不信任，也不可能亲自聚在一起开会，物理距离导致信息传输延迟。真正可信的签名体系难以实现。签名造假的问题也没法避免。签名消息记录的保存难以摆脱中心化的机构。另外，倘若每个国家都各自向其他9个国家派出信使，在这个网络层面即需要90次的传输才能完成一轮信息交流，但是每个国家可能回馈不同的进攻时间，在这种异步通信的条件下，要能协商一致是个大问题。
这就是一个由互不信任的各个邻邦国家所构成的分布式网络，要获得最大的利益，又必须一起努力才能完成，如何达成一致的共识，变成了一个难题。
莱斯利·兰伯特提出了“拜占庭将军问题”，但真正解决这个难题的是中本聪。
终极解决方案：区块链技术
互联网的存在，首先降低了信息的流通成本。每个将军配一台电脑，就解决了”书面协议“中骑马通讯造成时间延迟的问题。如果10个将军中的几个同时发起消息，势必会造成系统的混乱，造成各说各的攻击时间方案，行动难以一致。谁都可以发起进攻的信息，但由谁来发出呢？
中本聪巧妙地在系统加入了发送信息的成本，即：一段时间内只有一个节点可以传播信息。
它加入的成本就是”工作量“——节点必须完成一个计算工作才能向各城邦传播消息，当然，谁第一个完成工作，谁才能传播消息。当某个节点发出统一进攻的消息后，各个节点收到发起者的消息必须签名盖章，确认各自的身份。中本聪在这里引用现代加密技术为这个信息签名。
加密技术
这种加密技术——非对称加密完全可以解决古代难以解决的签名问题：
消息传送的私密性
能够确认身份
签名不可伪造、篡改
- 非对称加密算法的加密和解密使用不同的两个密钥
- 这两个密钥就是我们经常听到的”公开密钥”(公钥)和”私有密钥”(私钥)
- 公钥和私钥一般成对出现, 如果消息使用公钥加密,那么需要该公钥对应的私钥才能解密
- 同样，如果消息使用私钥加密,那么需要该私钥对应的公钥才能解密.
非对称加密的作用是:保护消息内容, 并且让消息接收方确定发送方的身份。
比如，将军A想给将军B发送消息
为防止消息泄露，将军A只需要使用B的公钥对信息加密
而B的公钥是公开的，B只需要用只有他自己的私钥解密即可。
将军B想要在信件上声明自己的身份，他可以自己写一段”签名文本“，
并用私钥签名，并广播出去，所有人可以根据B的公钥来验证该签名，确定的B的身份。
由此，一个不可信的分布式网络变成了一个可信的网络，所有的参与者可以在某件事在达成一致。
POW
写到这里，同时终于明白了工作量证明（Proof Of Work）的意义。有人说挖矿浪费了巨大的社会资源，但建立信任的成本可不是0，挖矿是维护比特币网络可靠性的最好办法。
如何保证公平?
在拜占庭的系统里，加入工作量证明，其实就是简单粗暴地引入了一个条件：大家都别忙着发起消息，都来做个题，看谁最聪明，谁就有资格第一个发起消息。这个题必须是绝对公平的，中本聪在设计比特币时，它采用了一种工作量证明机制叫哈希现金，在一个交易块这要找到一个随机数，计算机只能用穷举法来找到这个随机数，可以说能不能找到全靠运气，所以对于各个节点来说，只有随机才是真正的公平，实现随机的最好办法是使用数学，所有的将军在寻找共识的过程，借助了大家都认可的数学逻辑。
如何保证时效性?
如果不同的将军先后解出了题，各自先后向这个网络发布消息，于是各个节点都会收到来自不同节点发起的进攻或者不进攻的消息，那怎么办的？只有时间最早的发起者才是有效的。中本聪巧妙的设计了一个时间戳的东西，为每个将军在解好题的时间（出块时间）盖上时间印章。
如何进行工作证明?
将军们那又凭什么要一起做工作量证明呢？中本聪也完全可以设置一个奖励机制，比特币的奖励机制是每打包一个块，目前是奖励6.25个比特币，当然，拜占庭将军问题的奖励机制可以是瓜分拜占庭获得的利益。
如何处理背叛问题?
对了，如果有出现背叛怎么办？在这个分布式网络里，每个将军都有一份实时与其他将军同步的消息账本。 账本里有每个将军的签名都是可以验证身份的。如果有哪些消息不一致，可以知道消息不一致的是哪些将军。 尽管有消息不一致的，只要超过半数同意进攻，少数服从多数，共识达成。
由此，在一个分布式的系统中，尽管有坏人，坏人可以做任意事情（不受protocol限制），比如不响应、发送错误信息、对不同节点发送不同决定、不同错误节点联合起来干坏事等等。但是，只要大多数人是好人，就完全有可能去中心化地实现共识（Consensus）。到这里也可以知道了，基于互联网的区块链技术，它克服了口头协议与书面协议的种种缺点，使用消息加密技术、以及公平的工作量证明机制，创建了一组所有将军都认可的协议，这套协议的出现，拜占庭将军问题也就完美的得到了解决。
作者：涅槃快乐是金
链接：https://www.jianshu.com/p/7ee07c334419
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
网友评论