共识机制大阅兵

简单讲两句

最近熊市漫漫，看盘的心情反正是没了 :cry: ，正好趁这个大好时间好好学习下区块链底层算法，毕竟现在又到了需要充值信仰的年代。那么说到区块链，共识机制一定是绕不开的话题。区块链解决了在不可信环境下传输可信数据的难题，实现了价值传输，而共识机制解决了分布式网络的一致性问题，也就是网络中所有节点就某个提案（Proposal）或某一状态达成一致共识。区块链能在众多不稳定节点中达到某一平衡状态，没有一个可靠的共识机制是难以想象的，从技术角度来看，密码学和共识算法是区块链项目的两大技术基础。

定义

在分布式系统中，互不信任的节点一起工作，根据某种规则达成信任关系并保障系统整体一致性和持续性，这种规则可以抽象成共识过程。具体到区块链，共识机制是区块链节点就区块信息达成全网一致共识的机制，即就如何选择记账人达成共识。

L5RP2.md.jpg

回顾过去

分布式系统中如何保证集群中所有节点中的数据完全相同并且能够对某个提案达成一致是分布式系统正常工作的核心问题。一个理想的分布式系统一致性应满足以下三点：

• 可终止性：一致性的结果需要在有限的时间内达成
• 共识性：不同节点最终完成决策的结果应该是相同的
• 合法性：决策的结果必须来自其他节点提出的提案

根据20世纪末发布的几个分布式系统重要定理：

• CAP定理：在异步的网络模型中，所有的节点由于没有时钟仅仅能根据接收到的消息作出判断，这是完全不能同时保证一致性、可用性和分区容错性，每一个系统只能在这三种特性中选择两种。
• FLP不可能定理：在网络可靠并且存在节点失效的异步模型系统中，不存在一个可以解决一致性问题的确定性算法。

我们应该客观的认识到，在现实情况中网络延迟一定存在，没有办法在分布式系统中做到强一致性的同时保证可用性，不过可以降低对一致性的要求，在与可用性之间做出权衡，目前主流的分布式系统都选择最终一致性。那么何为最终一致性，即允许多个节点的状态出现冲突，但所有能沟通的节点能在有限时间内解决冲突恢复到一支状态。这里有2个重要条件：节点之间可以正常通信；冲突需要在有限时间内解决。只有这两个条件满足，才能达到最终一致性。

传统的分布式系统面临的问题：节点数量的增加和减少，以及节点失效故障宕机等问题；节点之间网络通信可能存在干扰甚至阻断，运行速度也存在差异。针对这些问题，目前已经有了 Paxos 和 Raft 等共识算法能够很好的解决传统分布式系统领域一致性问题。当我们应到意识到，在区块链网络中，例如比特币网络，节点不仅存在失效问题，还存在作恶的可能，即节点可能会故意发送错误数据。这里我们就要引入拜占庭容将军问题，拜占庭将军模型则是分布式领域中最复杂严格的容错模型，它允许节点作恶，即节点可以选择不响应甚至故意发送错误数据。在过去一直没有人能很好的解决这一问题，直到中本聪发明了比特币，巧妙地引入经济学激励机制从非计算机的角度天才般地给出了全新的解决方案，自此区块链系统中的共识算法机制开始引起了大众的关注，下面小编整理了目前常见的共识算法一一介绍。

L9sXB.md.png

分类

• POW（Proof Of Work）

  工作量证明，矿工在处理交易数据的同时不断进行哈希计算，直到得到一个前23位为0的哈希值即为nonce，这个过程就是在解决一个有一定难度但是可行的计算问题，但是验证答案的过程对于其他节点而言是非常容易地，也就是一个不容易解答但是容易验证的问题，这种问题通常需要消耗一定量的计算力，矿工通过算力比拼竞争区块记账权和代币奖励。POW算法能够使分布式系统达到拜占庭容错，是一种简单粗暴消耗资源但是能较大程度保证系统去中心化（不考虑矿池算力集中的问题），POW算法目前的确认时间较长，且没有最终一致性。

  例子：BTC，LTC

  L5oTz.md.png

• POS（Proof Of Stake）

  权益证明，基本思想是让网络中拥有越多权益的节点有机会在更短时间内做更多的决定，因为权益持有人更倾向于维护网络利益且害怕作恶后被惩罚。PoS的实现方式很多，比较典型的是引入“币龄”概念的方式，即用币龄来计算权益，每个代币持有一天记为一个币天，完成一次记账后清空一定的币天。POS算法不需要消耗大量资源，并在一定程度上缩短了确认时间，不过依然没有最终一致性。

  例子：PeerCoin，Qtum

  L955H.md.png

• DPOS（Delegated Proof Of Stake）

  委托权益证明，基于POS发展而来，POS算法对于小股东而言除了能得到股份带来的收益以外几乎很难有什么作为。DPOS能够让每个节点选出可以代表自己利益的节点参与到记账权的争夺中，即类似于董事会的投票机制，选举出n个记账节点，后续提案由这些被选中的节点轮流处理。DPoS理论上不要求选出的代表个体本身是权益所有人，看起来更民主，更开放。网络参与者做为选民有机会选出自己的代表，来给自己的利益代言。如果选出的代表不作为（轮到自己记账时不记账），或者作恶，可以把他们踢掉，如有必要进行惩罚（选民们也有可能被惩罚）。总结来说，DPOS机制减少了记账节点的规模，属于若中心化，但同时也大大提高了效率。

  例子：BitShares，Steem，EOS

  L99MN.md.png

• DAG（Directed Acycli Graph）

  有向无环图，DAG共识算法的诞生是为了解决区块链的效率问题，通过DAG拓扑结构存储交易区块，支持网络中并行打包出块，提高交易容纳量。之后DAG不断演化逐渐形成了 blockless 的发展方向。从数据结构来看，DAG模式是一种典型的Gossip算法，即本质上为异步通讯，带来的最大的问题是一致性不可控，并且网络传输数据量会随着节点的增加而大幅增加。DAG算法支持交易快速确认，低廉交易手续费，同时也剔除了矿工角色。但是目前来看安全性低于POW等机制，容易形成中心化，例如IOTA依赖validator，字节雪球则需要见证人节点。

  例子：IOTA，Byteball（字节雪球）

  L9Bg9.md.png

• PBFT（Practical Byzantine Fault Tolerance）

  实用拜占庭容错算法，基于BFT算法放松了部分约束条件来解决拜占庭问题。这是一种基于消息传递的一致性算法，算法经过三个阶段达成一致性，这些阶段可能因为失败而重复进行。PBFT算法在保证灵活性和安全性的前提下最大允许 (n-1)/3 的容错性，信息在节点之间互相交换后，各节点列出所有得到的信息最后以大多数的结果作为解决方法。PBFT这种通过投票达成共识的算法可以很好得解决包括分叉的问题同时提升网络效率，但由于PBFT机制要求一个封闭的集群环境，两两节点需要进行通信，因此并不适合公链场景，全网通信量也是吃不消的，事实上超过100个节点，拜占庭容错算法已经不适用了。所以，PBFT算法非常适用于联盟链或者私有链等中小规模环境。并且，POW，POS等算法都无法脱离token的存在，而PBFT并不依赖于此，共识效率高可以应用于高频交易场景。当然了，PBFT缺陷也非常明显，当有1/3或以上记账节点停止工作后，整个系统将无法运转。

  例子：布萌区块链

  L9Deu.md.png

• DBFT（Delegated BFT）

  授权拜占庭容错算法，基于权益选择记账人，然后记账人之间通过拜占庭容错算法达成共识。相比于PBFT，DBFT改良了不少特性：优化的记账节点，记账由多节点协同完成，每个区块都有最终性不会分叉。当然PBFT的缺点也依然存在，即1/3及以上节点宕机后整个系统无法继续提供服务。

  例子：NEO

  L9XSq.md.jpg

• POA（Proof Of Authority）

  权威证明，使用一组所谓的“权限”允许人们在区块链上创建新的节点并确保全网安全。在POA机制中，验证者是整个共识机制的关键，验证者必须具有已知且获得验证的身份。验证者通过放置这个身份来获得担保网络的权利，从而换取区块奖励。若是验证者在整个过程中有恶意行为，或与其他验证者勾结。那通过链上管理可以移除和替换恶意行为者。现有的法律反欺诈保障会被用于整个网络的参与者免受验证者的恶意行为。POA算法出块效率高，不需要挖矿消耗大量资源，整个网络验证者互相监督，随时可以投票加入新的验证者或者剔出不合格验证者。

  例子：唯链，TomoChain

  L9zTe.md.png

• RPCA（Ripple Protocol consensus algorithm）

  瑞波共识机制RPCA是一个类似PBFT的共识机制，属于节点投票的共识机制。初始特殊节点形成后，后续接入新节点需要51%原特殊节点同意，因此该机制从一开始就是中心化的。

  例子：Ripple

  L9VJd.md.png

• Paxos

  Paxos 是一类能够解决分布式一致性问题的协议，它能够让分布式网络中的节点在出现错误时仍然保持一致。Paxos 可以在没有恶意节点的前提下保证系统中节点的一致性，也是第一个被证明完备的共识算法，适用于传统的分布式系统

• Raft

  Raft算法是对Paxos算法的一种简单实现，包括三个角色：leader，candiate，follower。Raft机制可以理解成全网选出一个记账者，如果它稳定运行没有挂掉，就由这个节点记账，全网无条件接受他的记账结果，相信他是诚实的，假如这个节点挂掉了，那么大家是可以通过超时或网络探测感知，然后快速启动一轮投票，来选出一个新的记账节点，然后继续无条件的等它记账，这样就达成了容错性。这在信任度较高，机构组成简单的的联盟链或者一个机构内的私有链里，是比PBFT更加高效的一种做法，因为不需要多步的反复确认，受网络影响的可能性也小很多。总的来说，Raft算法强调可用性和最终一致性，效率非常高，但是防欺诈性一般只能事后检查。

总结

共识算法的发展和演化其实非常类似人类社会的不同阶段，研究共识算法，不仅需要计算机背景，更依赖深刻理解经济学，社会学，博弈论等多元化知识。人类社会制度尚不存在完美的方案，共识算法的完善之路更加漫漫。

---

更多优质项目敬请关注公众号 BlockGeeks

mark