听过拜占庭将军问题，有听过拜占庭容错算法吗？
区块链是去中心的网络，关于保证众多节点达成
共识
，相信很多人都听过“拜占庭将军问题”。今天肖恩就跟大家来讲讲“拜占庭将军问题”。
什么是拜占庭将军问题
古代有一个城邦，名为拜占庭，有10支军队想要攻占该城邦。该城邦防御系统强大，单支军队进攻，必定会失败。需要同时一半以上的军队进攻，才能取胜。军队与军队之间要保持通信，确保攻城方案（进攻或撤退）的一致才能保证胜利。但是，这里可能出现军队叛变的情况，导致决定一同进攻的军队数量少于一半，那么该进攻就会失败。
如何保证所有的将军达成共识，一同进攻拜占庭城邦，就是拜占庭将军问题。要解决这个问题，还需要做到“即使存在着叛变军队，忠诚军队的进攻也不能受到影响”。
如何解决拜占庭将军问题
肖恩先抛出答案，要保证超过2/3的军队是忠诚的。
举个简单的例子，假如现在有3支军队，分别是A、B、C，其中A将军和C将军是忠诚的，B将军是叛军。在这个例子中忠诚军队的占比是2/3。假设A广播进攻的信息，B和C均收收到A这一信息。叛军B则向A发送进攻的信息，但是向C发送撤退的信息。这个时候C收到两个信息，分别是进攻和撤退，这两个信息的数量还是一致。这样一来，C就很难下判断，到底是进攻还是撤退。总体来说，没办法实现所有军队达成共识。
但是若有第四支军队D，该军队也是忠诚的。这个时候忠诚军队的占比就是3/4，大于2/3。D向C发送进攻的消息，C收到2个进攻的信息，一个撤退的信息，在2>1的情况下，C就可以下定判断进攻。
忠诚军队占比要超过2/3，这也意味着军队的总数量要大于4。类比到分布式网络，要保证网络中的节点达成一致，就是要保证所有节点中忠诚节点占比要大于2/3。
以上提到的是拜占庭将军解决方案的原理，但要真正确保超过2/3的共识，若从头开始就通过点对点的方式去确认，那么工程量会很大。例如，10个将军都向9个将军发布信息，那么将会由90个信息在传送，每个攻城的时间、方案均不一样。确认反复，所需时间很长。
拜占庭容错算法
为了解决拜占庭问题，拜占庭容错算法早在 1982就在Leslie Lamport 的论文《The Byzantine Generals Problem》中提出，之后各大学者一直不断致力于完善拜占庭容错算法的问题，其中较为出名的就论实用拜占庭容错算法(PBFT)。
今天肖恩就带大家来说说实用拜占庭容错算法。主要的运作流程如下：
1. 通过轮换或随机算法确定主节点，主节点具有率先广播信息的权限。
2. 主节点将信息广播给网络中的其他节点，其他节点在收到主节点的信息后，先验证主节点是不是确定解决问题，节点就在该消息中附上自己的ID，并广播给其他节点。自身进入准备状态，并接受来自其他节点对于主节点的验证信息（是否进入准备状态）。
所有的节点验证完主节点的信息后均在彼此之间互相广播，以确认信息一致性。这个互相广播的过程用的就是非对称性签名，以确保信息的来源。
3.进入准备状态的节点超过2/3，主节点的信息则获得网络共识。
这个过程，我们可以理解为在几位将军中选取一位领导将军，他来率先发布攻城计划，其他的将军在收到他的计划后，分别确认战术的真实性与可行性，再在所有军队中达成共识，从而确定一致的攻城计划。
再继PBFT后，拜占庭容错还有着各种不一样的解决方案，如比特币中用的就是工作量证明机制来解决。主要是借助工作量证明机制来确定提出提案的主节点，进而避免多节点广播信息带来的混乱。
关注肖恩说链，读懂区块链，抢占财富先机。
-End-
▼
- 发表于:
- 原文链接：https://kuaibao.qq.com/s/20190218G128V700?refer=cp_1026
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
