【阅读时间】10min 3183 words
【阅读内容】什么是拜占庭问题，以及它和区块链的关系，现代区块链技术中常见的共识算法总结
首先，这个问题属于计算机科学领域。解决这个问题才是区块链最大的价值所在，因为这个问题一直是分布式系统的重要难题之一
这个问题的定义者是图灵奖获得者，Lamport大神，分布式系统的关键性奠基人之一。有面包店算法，拜占庭将军问题，Paxos算法等著名成果
9个将军带领9支军队，打一场攻城战役。假设每个将军都能独立根据眼前战况做出两种判断：进攻或撤退，要求（或者最终目的是）如何让这9个将军的命令是一致的（一致性，即共识）？要么一起进攻，要么一起撤退（每个将军之间也是互不信任的，也有消灭对方的动机）
最简单的策略即：投票（上图中的红色箭头和绿色箭头为每个将军做出的判断），超过半数支持某个决定，那么所有9个将军一定执行这个决定。如上图，5个将军决定进攻，4个将军决定撤退，那么所有将军都会下令：进攻！
这种策略需要每个将军把自己的判断通过一种途径（途中灰色箭头）传递到所有其他将军处。相对的，每个将军只有在收到了所有投票结果后，才会下令。如上面的例子，所有将军得到投票：4进攻5撤退，才下令撤退
这个投票策略的最大问题：假设出现了叛徒，如上图所示，会出现两种情况
此时总结一下，拜占庭问题的问题到底是什么：
根据相关的研究，得出一个【一般性的结论】：如果叛徒的数量大于或等于三分之一 ，那么拜占庭问题不可解，这个三分之一也被称为拜占庭容错，三模冗余是完全无法容错的（也就是说无解，不可能保持一致性）
解释方法使用副官模型即可
推广到计算机系统内，【将军】类比为【计算机】，而计算机因为物理或被感染等其他原因造成的【运行异常】就是【叛徒】，其实整个问题也是为了保证分布式系统的一致性和可用性
在区块链之前，有两种解决方案：口头协议（又称为拜占庭容错算法）和书面协议
通常来说，大多数分布式系统使用的是书面协议确保一致性，中心机构背书。其中有实用拜占庭容错算法（PBFT）最为有名
这个算法说起来也不难理解，他的核心思想是：对于每一个收到命令的将军，都要去询问其他人，他们收到的命令是什么。也就是说利用不断的信息交换让可行的节点确认哪一个记录选择是正确的，即发现其中的背叛者
采用PBFT方法，本质上就是利用通信次数换取信用。每个命令的执行都需要节点间两两交互去核验消息，通信代价是非常高的。通常采用PBFT算法，节点间的通信复杂度是节点数的平方级的
还是用上面的将军的例子来举例，但为了方便我们把问题的定义稍作修改
【问题定义】总共4个将军，有1个是叛徒，每个将军需要在自己的战斗计划中添加一行内容 <什么时间>进攻
【目标】只需要3个将军达成一致在同一时间进攻，就可以攻占城市，否则进攻者全军覆没。最终目标还是统一一个一致的战斗计划，并按照计划同时实施（在去中心化系统中，即【记录】的一致性）
【方法】对于每一个收到命令的将军，都要去询问其他人，他们收到的命令是什么。在判断不出判断者的情况，执行更多的那个命令
【可视化直观】
其中每个将军投降下方的数字就是收到的攻击事件列表，在该规则下，可以看到能保证，当叛徒数量小于1/3维护系统的一致性，即无论是什么情况，都可以防止不一致的决定被执行（至少也是按兵不动，并且很容易定位叛徒是谁）
注意，在这种仅有4个节点的情况下看似复用信道和传递消息的数量不多。但随着结点的增加，时间复杂度和信道使用量级是节点数的平方。大规模网络基本瘫痪，效率太低
我们知道，区块链最强的地方就在于它的一致性（了解区块链原理，可移步另一篇博客 一文看懂区块链：一步一步发明比特币），同时这正是拜占庭问题的核心
我们先假设你已经完全了解了比特币区块链的运行原理，那么我们一步一步建立一个场景看一看区块链是如何解决拜占庭将军问题？
我们先假设信道一定是可靠的，传令兵死亡之类的事情我们不考虑，毕竟在一个非常复杂的网络中，还可以通过多条的方式连接任意两个节点，可靠性还是值得相信。主要破坏一致性的还是心怀不轨的【间谍】，或者总结为：如何防止【间谍】对整体决策（进攻还是撤退）进行破坏？
我们按照区块链模型构造一个下图所示的系统
每个将军本地都存储一份【记录】：记录所有将军的决定，比如“1：1”代表1号将军决定进攻
然后构造以下协议内容：
在这个案例中，抛弃了代币的设定，因为不存在交易行为，而是由国王出资（保证战争不被间谍影响，我认为国王应该愿意出这笔钱）。在拜占庭时期，因为没有网络，构造上述这样的系统，是完全不可能的。而现在网络链路速度，效率越来越高，让区块链解决一致性问题得以解决
这里就引出了现在区块链的核心问题：应用场景与代价博弈。你要解决的痛点，到底值不值得这样的花费呢？无论是算力消耗，还是资源消耗，亦或是类似于上述案例中的国王出资（区块链代币价值为负数？），都是一种【代价】。完全的信任是不存在的，只有当造假（走捷径获得利润）的成本远远高于得到的利润，才能取得信任（一致性）
必须强调，在传统的拜占庭问题构造的情景中，只能是一个例子，这个应用情景是完全没有没有必要使用区块链来解决的！
互联网技术的存在，让传输过程中，基本没有延迟（或说延迟很小可以基本忽略），解决了通讯延迟的问题
区块链使用链型数据结构 + 算力互相制约使得作假的成本随着时间的加长呈指数上升，解决了一致性问题。当然非对称秘钥部分的密码学，解决了身份确认问题
至少这个系统解决的问题不仅仅是金融领域，去中心化银行系统的问题所在，交易，其实只是其中很小的一部分
因为技术还在不断发展，可能有其他的算法被建立，但是只要谈到共识这个问题，核心一定是【中心化】和【去中心化】的权衡（Trade-off），而对应的就是效率，可以这么说，一致（信任）是需要成本的，这是本源法则，和线性向量空间的定义处在同一个层级
中本聪很厉害的地方就在于，之前的分布式一致性算法（PBFT）对大体谅节点系统的支持非常差，效率上来说，基本和无法实现是等等同的
下面的思维导图展示了现在基本的区块链共识算法总结
即这篇文章前面提到的拜占庭容错。在此基础上，发展出的Paxos是理论上的高效算法，很难实现。而Raft是由Google牵头开发一个Paxos理论实现版本
【去中心化】【大规模节点无法支持】【效率低】
其中有两个比较有名的【RPCA Ripple共识】【DPOS 股权代理人共识】，在规则和协议上稍有不同，但是核心的Idea还是使用类似人大代表选举的制度来保证新区块的产生不会由同一个人控制，即代表轮流挖矿
NEO使用的是【DBFT】，投票的拜占庭容错算法，算是结合了几个算法的优势和思路，也很有想法！容错能力和PBFT一样，但是效率更高，信道使用冗余更低
【半中心化】【大规模节点支持】【效率高】
最早的共识算法，使用算力来资源消耗来实现共识，详细方法见一步一步发明比特币
为了对抗ASIC矿机等专业化HASH算力硬件，也有一些PoW引入了内存HASH等禁止ASIC算力的方法。但是万变不离其中，最终还是归一化到一个【每Hash Rate/法币花费】博弈和平衡中
【PoC Proof of Capacity】容量证明，挖到区块和你的硬盘空间正相关
【去中心化】【大规模检点支持】【效率低】【资源消耗高】
新建区块和你拥有的币的数量呈正相关，类似于利息的激励方式，可以参看权益证明
更多的【PoA Proof of Activity】活动证明，是一种Pow+PoS混合共识方式，基本被证明不靠谱了，提及一下
【去中心化】【大规模节点支持】【效率中】
【PoET Proof of Elapsed Time】消逝时间证明：Intel使用HyperLedger建立的锯齿（Sawtooth）项目使用。在一种收信任的执行环境下保证随机的选择用户来生产区块，间隔时间提前约定。很奇怪的Idea，只适合于联盟链
欢迎各位读者留言提示更多的不同共识算法，讨论交流，共同进步！
【完】
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。