06共识算法

目录:
1.什么是共识算法?

• a.分布式系统
• b.一致性问题
• C. FLP定理与CAP定理
• d.拜占庭将军问题

2.共识算法的目的和价值
3.常用的共识算法

一、什么是共识算法?

(一)、分布式系统

1、区块链系统本质就是一一个分布式应用软件。区块链架构是一种分布式的架构。

• 其部署模式有公共链、联盟链、私有链三种，对应的是去中心化分布式系统、部分去中心化分布式系统和弱中心分布式系统。

2、分布式系统中，多个主机通过异步通信方式组成网络集群。

• 在这样的一一个异步系统中，需要主机之间进行状态复制，以保证每个主机达成一致的状态共识。 然而，异步马分<系统中，可能出现无法通信的故障主机，而主机的性能可能下降，网络可能拥塞，这些可能导致错误信息在系统内传播。因此需要在默认不可靠的异步网络中定义容错协议，以确保各主机达成安全可靠的状态共识。

3、利用区块链构造基于互联网的去中心化账本，需要解决的首要问题是如何实现不同账本节点上的账本数据的一-致性和正确性

• 这就需要借鉴已有的在分布式系统中实现状态共识的算法，确定网络中选择记账节点的机制，以及如何保障账本数据在全网中形成正确、一致的共识。

(二)、分布式系统的一致性问题

1、理想的分布式系统的一致性应该满足以下三点:

• 1.可终止性(Termination) :一 致性的结果可在有限时间内完成
• 2.共识性(Consensus):不同节点最终完成决策的结果应该相同。
• 3.合法性(Validity): 决策的结果必须是其他进程提出的提案

2、对于分布式系统，希望具备以下能力:

• 分布式系统作为一个逻辑整体，不应该返回错误的结果;
• 只要系统里的大部分机器工作正常，整个分布式系统就能有效运行，这也是分布式系统应用的一一个优点，抵抗单点故障;
• 系统的性能是可以横向扩展的，对于分布式系统来说，木桶原理不起作用;
• 分布式系统必须是异步的。每个节点按照自己的时序独立工作，没有全序的时间顺序。

3、在实际的计算机集群中，可能会存在以下问题:

• 1.节点处理事务的能力不同，网络节点数据的吞吐量有差异
• 2.节点间通讯的信道可能不安全
• 3.可能会有恶意节点出现
• 4.当异步处理能力达到高度一致时，系统的可扩展性就会变差(容不下新节点的加入)。

4、实现全网一-致性其实只需要在某个时刻达成最终一致即可。

• 生活中，即便有统- - 的命令指挥，尚且不一-定能做到整齐划一，况且在没有一个指挥员的去中心化区块链系统中;
• 互联网中，任意一个节点的状态，没有办法强力控制。节点断网、节点关闭、恶意伪装节点等都有可能;
• 实际上，对一致性的的要求并没有那么迫切，在一定约束下，可以实现最终一致性， 或者说在某个时刻系统达成一致的状态即可;
• 节点断网或宕机，没有问题，恢复后跟上，通过其他节点同步自己的数据;
• 只要整个网络绝大部分节点正常工作，整个系统总能在未来某一 个时刻达成数据状态的一致

(三)、FLP定理与CAP定理

1、FLP定理(FLP不可能性定理)

• FLP定理来源于Fischer、Lynch、 Patterson三位作者于1985年发表的论文。之后该论文毫无悬念获得了Dijkstra (狄克斯特拉)奖。
• Lynch是一位非常著名的分布式领域的女科学家，研究遍布分布式的方方面面，对分布式领域有着极其卓越的贡献，其著有《Distributed Algorithms》一书，以非常严谨而简洁的逻辑讨论了许多分布式算法。
• FLP给出了一个令人吃惊的结论:在异步通信场景，即使只有一一个进程失败，也没有任何算法能保证非失败进程达到- -致性!
• 在网络可靠、存在节点失效的异步模型系统中，不存在解决一 致性问题的确定性算法;.不要浪费时间去为异步分布式系统设计在任意场景下都能实现共识的算法;
• 在允许节点失效的情况下，异步系统无法确保一致性在 有限时间内完成。

2、CAP定理

• CAP定理最早由Eric Brewer在2000年提出猜想，后来Lynch等人进行了证明;

• FLP从科学，上告诉你去赌场赌博从概率上总会是输钱的;工程则告诉你，如果你愿意接受最终输钱的结果，中间说不定偶尔能小赢几笔。这就是CAP定理;

• 分布式计算系统不可能同时确保一致性、 可用性和分区容错性，这三者不可兼得。这是一个典型的不可能三角;

  • 1、一致性(consistency) :所有节点在同一时刻能够看到同样的数据，即“强一-致性”;
  • 2、可用性(availability) :确保每个请求都可以收到确定其是否成功的响应，并且是在有限的时间内;
  • 3、分区容错性(partition tolerance) :因为网络故障导致的系统分区不影响系统正常运行。

• 既然不能同时满足，只有弱化对某个特性的支持

  • 弱化一致性:对于实时的强一致性不要有太高的要求;
  • 弱化可用性:要提高性能，保持可靠，尽量避免加载不必要的模块，也就是牺牲可用性
  • 弱化分区容错性:对于分布式系统，分区容错是必然的。区块链系统，尤其是公有链，用各种共识算名見法，优先解决的就是保证整个系统的容错能力。

(四)、拜占庭将军问题

屏幕快照 2018-11-01 下午8.32.42.png 屏幕快照 2018-11-01 下午8.32.59.png

1、 去中心化的区块链技术必须要考虑拜占庭将军问题

• 分布式系统中根据有无恶意节点，分为拜占庭容错和非拜占庭容错机制;
• 在20世纪80年代出现的分布式系统共识算法，是区块链共识算法的基础。
• 经典的拜占庭容错技术(Byzantine Fault Tolerance, BFT) 是-一类分布式计算领域的容错技术。

2、拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或中断以及遭到恶意攻击等原因，计算机和网络可能出现不可预料的行为。拜占庭容错技术被设计用来处理这些异常行为，并满足所要解决的问题的规范要求。

3、拜占庭将军问题的可以描述为:一 个发送命令的将军要发送一个命令给其余n-1个将军，使得:

• IC1、所有忠诚的接收命令的将军遵守相同的命令;
• IC2、如果发送命令的将军是忠诚的，那么所有忠诚的接收命令的将军遵守所接收的命令。

4、Lamport 对拜占庭将军问题的研究表明

• 当n>3m时，即叛徒的个数m小于将军总数n的1/3时，通过口头同步通信(假设通信是可靠的)，可以构造同时满足IC1和IC2的解决方案，即将军们可以达成一致的命令 。

• 但如果通信是可认证、防篡改防伪造的(如采用PKI认证，消息签名等)，则在任意多叛徒且至少有两个忠诚将军的情况下都可以找到解决方案。

• 而在异步通信情况下，情况就没有这么乐观。

  • Fischer-Lynch-Paterson定理证明了，只要有一一个叛徒存在，拜占庭将军问题就无解。
  • 翻译成分布式计算语言，在一一个多进程异步系统中，只要有一一个进程不可靠，那么就不存在一一个协议，此协议能保证有限时间内使所有进程达成一致。
  • 由此可见，拜占庭将军问题在一一个分布式系统中，是一个非常有挑战性的问题。因为分布式系统不能依靠同步通信，否则性能和效率将非常低。因此寻找一种实用的解决拜占庭将军问题的算法一直是分布
    式计算领域中的一一个重要问题。

(五)、传统分布式一致性算法和区块链共识算法

1、一致性就是指数据要完整、要同步。

2、所谓的共识算法(或“共识机制”)，主要是为了解决分布式系统中，所有节点对于数据的一致性和有效性问题而指定的一系列规则。通过类似节点投票的方式，确保分布式系统不会因为某个节点的问题(如宕机或者恶意篡改数据)导致分布式系统的数据发生安全问题。

3、传统分布式一致性算法和区块链共识算法相同点

• 强调序列化

• 少数服从多数原则

• 分离覆盖的问题:即多节点覆盖少数节点日志，长链覆盖短链区块。

4、传统分布式一致性算法和区块链共识算法不同点

• 传统分布式一致性算法大多 不考虑拜占庭容错(Byzanetine Paxos除外)，即假设所有节点只发生宕机、网络故障等非人为问题，并不考虑恶意节点篡改数据的问题;

• 传统分布式一致性算法是面向数据库的，而区块链共识模型面向交易的，所以严格来说，传统分布式一致性算法应该处于区块链共识模型的下面一-层。

二、共识算法的目的和价值

(一)、共识算法的目的
1、利用区块链构造基于互联网的去中心化账本，需要解决的首要问题是如何实现不同账本节点上的账本数据的一致性和正确性。

• 这就需要借鉴传统的分布式系统中的一-致性算法，确定网络中选择记账节点的机制，以及如何保障账本数据的一致性和正确性。

2、区块链解决了在不可信信道上传输可信信息、价值转移的问题，而共识机制解决了区块链如何在分布式场景下达成一致性的问题。

• 区块链的伟大之处就是它的共识机制在去中心化的思想上解决了节点间互相信任的问题。。区块链能在众多节点达到一种较为平衡的状态也是因为共识机制。
• 密码学占据了区块链的半壁江山，属于区块链的骨骼，而共识机制是保障区块链系统不断运行下去的关键，是区块链的灵魂。
  干餐

(二)、引入新的共识机制
1、当分布式的思想被提出来时，人们就开始根据FLP定理和CAP定理设计共识算法。
2、FLP定理规定:“在网络可靠、存在节点失效的异步模型系统中，不存在解决一致性问题的确定性算法”

• 把FLP的设定放松一些，寻求有解的方案
• 由社会学和博弈论得到启发，引入了新机制
  • 激励机制
    在拜占庭将军问题中给忠诚将军奖励。背叛景军发现背叛行为没有收益，消除其背叛动机;
    引入博弈论概念，认为每一-一个节点的行为是由激励机制决定的;
    引入社会学概念，认为理性的人都是逐利的，每个节点都有最大化自己利益的倾向，如果激励机制设置得当，大部分节点都会遵守规则，成为公正的节点。
  • 随机性
    ”在传统的中心化系统中，决定下一步行动由权威大的将军做决定。在去中心化的系统中，提出在所有将军中，随机指定一名将军做决定。这就是决定谁有记账权。
    “根据每个节点的计算力来决定。谁的算力强，谁可获得记账权，在拜占庭将军问题中就是指挥权。这就是比特币系统中用的PoW共识机制。
    根据每个节点具有的资源来决定。谁投入的资源多，谁就可以获得记账权。这就是PoS共识机制

(三)、共识算法的假设条件

1、在实际情况下，根据不同的假设条件，有很多不同的共识算法被设计出来。这些算法各有优势和局限。算法的假设条件有以下几种情况:

• 1)故障模型:非拜占庭故障/拜占庭故障。
• 2)通信类型:同步/异步。
• 3)通信网络连接:节点间直连数。
• 4)信息发送者身份:实名/匿名。
• 5)通信通道稳定性:通道可靠/不可靠。。
• 6)消息认证性:认证消息/非认证消息。

2、在区块链网络中，由于应用场景的不同，所设计的目标各异，不同的区块链系统采用了不同的共识算法。

• 一般来说，在私有链和联盟链情况下，对一致性、正确性有很强的要求。一般来说要采用强一致性的共识算法。

• 对于不需要货币体系的许可链或者私有链而言，绝对信任的节点以及高效的需求对于上述共识算法来说并不能够提供，因此对于这样的区块链，传统的一致性算法成为首选。PBFT (拜占庭容错)、Paxos、 Raft。

• 而在公有链情况下，对一-致性和正确性通常没法做到百分之百，通常采用最终一致性(EventualConsistency)的共识算法。

(四)、共识算法及其代表产品(包括新的共识算法+传统的一致性算法)

1、PoW

• 比特币
• 莱特币
• 以太坊前3个阶段

2、PoS

• 以太坊第4个阶段

3、DPoS

• BitShare

4、PBFT

• Hyperledger Fabric (联盟链的代表)

5、Paxos

• ZooKeeper
• ZooKeeper是一一个分布式的，开放源码的分布式应用程序协调服务，是Google的Chubby-一个开源的实现，是Hadoop和Hbase的重要组件。它是一一个为分布式应用提供一致性 服务的软件，提供的功能包括:配置
  维护、域名服务、分布式同步、组服务等。

6、Raft

• ETCD

三、常用共识算法

一般比特币、莱特币使用pow算法 ，开发鼓励使用pos算法，联盟链PBFT 、私有链Paxos或者Raft算法。

(一)、PoW算法(Proof-of-Work, 工作量证明机制)

  1、工作量证明(Proof Of Work, 简称PoW)， 简单理解就是一-份证明，用来确认你做过一定量的工作。

  。在比特币白皮书里，中本聪提出“工作量证明”机制，就是PoW机制。。通俗讲:比特币的工作量证明，就是我们俗称“挖矿”所做的主要工作。

  .工作量证明是矿工在处理交易数据(对数据进行哈希)的同时不断的进行哈希计算，求得一一个nonce 黄金数。当全网有一~位矿工哈希出nonce时，他就会把自己打包的区块公布出去，其他节点收到区块验证区块后就会-致性认为这个区块接到了区块链.上，就继续进行下一个区块的打包和哈希计算。

  。在这个过程中，中本聪通过算力的比拼这种简单暴力的方法把区块链系统的健壮性提升到极致，就算全网只剩下一个节点运行，这个区块链系统还是会继续运行下去。

  。PoW也充分提高了区块链系统的安全性，依靠51%攻击理论去破坏区块链系统是只有政府或者疯子才会采取的方法。

  2、PoW的优点

  . 1.完全去中心化，节点自由进出，避免了建立和维护中心化信用机构的成本。

  。2.只要网络破坏者的算力不超过网络总算力的50%，网络的交易状态就能达成一致。破坏系统花费的成本巨大

  3、PoW的缺点

  .1.目前比特币挖矿造成大量的资源浪费;

  .2.挖矿的激励机制也造成矿池算力的高度集中，背离了当初去中心化设计的初衷;。3.更大的问题是PoW机制的共识达成的周期较长，每秒只能最多做7笔交易。

(二)、PoS算法 (Proof-of-Stake，股权证明机制)

  1、PoS:也称股权证明，类似于财产储存在银行，这种模式会根据你持有数字货币的量和时间，分配给你相应的利息。

  . PoS是一种在公链中的共识算法，可作为PoW算法的一种替换。如果简单的把PoW当作比力量大小的话，PoS就是比耐力多少。

  。PoW是保证比特币、以太坊和许多其它区块链安全的一种机制，但是PoW算法在挖矿过程中因破坏环境和浪费电力而受到指责。所以PoS试图通过以一种不同的机制取代挖矿的概念，从而解决这些问题。。PoS是根据钱包里面货币的多少以及货币在钱包里存在的天数来合成一一个单位(币天)。

  。它根据币天的关系对计算机进行哈希计算降低了难度，降低了计算机的门槛，但是对计算机还是有一定要求的，它把钱包和区块链系统的一致性绑定在一起。

  。谁的钱包里币天的数值越大谁拥有记账权的概率就越大。但是它和PoW机制一-样解决问题的思想也导致了它与PoW拥有一样的缺点，也是牺牲了-部分的共识(同样分叉)，而且需要等待多个确认。. PoS机制可以被描述成一种虚 拟挖矿。

  。在PoW中，一个用户可能拿1000美元来买矿机，加入网络来挖矿产生新区块，从而得到奖励。而在PoS中，用户可以拿1000美元购买等价值的代币，把这些代币当作押金放入PoS机制中，这样用户就有机

  会产生新块而得到奖励。  王路县。在PoW中，如果用户花费2000美元购买硬件设备，当然会获得两倍算力来挖矿，从而获得两倍奖励。


  2、同样，在PoS机制中投入两倍的代币作为押金，就有两倍大的机会获得产生新区块的权利。


  2、PoS的优点

  - 对节点性能要求低，缩短了共识达成的时间(网络环境好的话可实现毫秒级) ;降低了PoW机制的资源浪费。


  3、PoS的缺点

  。1.破坏者对网络攻击的成本低，网络的安全性有待验证;

  。2.拥有代币数量大的节点获得记账权的几率更大，会使得网络的共识受少数富裕账户支配，从而失去公正性;

  。3.没有最终一 致性。 

(三)、DPoS算法(Delegated Proof of Stake，股份授权证明机制/代理股权证明机制)

1、DPoS是基于PoS衍生出的更专业的解决方案，他是类似于董事会的投票机制

• 选举出n个记账节点，在节点中提案者提交的提案被这些记账节点投票决定谁是正确的。
• 比特股(BitShare) 和steem采用的DPoS机制是持股者投票选出一 定数量的见证人，每个见证人按序有两秒的权限时间生成区块，若见证人在给定的时间片不能生成区块，区块生成权限交给下一个时间片对应的见证人。
• 持股人可以随时通过投票更换这些见证人。DPoS的这种设计使得区块的生成更为快速，也更加节能。

2、DPoS优点

• 1.大幅缩小参与验证和记账节点的数量，可以达到秒级的共识验证。
• 2.减少记账节点规模，属于弱中心化，效率提高。

3、DPoS缺点

• 1.选举固定数量的见证人作为记账候选人有可能不适合于完全去中心化的场景。牺牲了去中心化的概念，丕适合公有链。
• 2.在网络节点数少的场景，选举的见证人的代表性也不强。

(四)、PBFT算法(Pracical Byzantine Fault Tolerance ，实用的拜占庭容错机制)

• 1、PBFT是第一个得到广泛应用的BFT算法，在1999年 由Castro和Liskov提出;

早期BFT由于性能太低不能在实际系统中运作，而PBFT解决了原始拜占庭容错算法效率不高的问题，将算法复杂度降低，使得其能在实际系统应用中可行;

在PBFT算法中，每个副本有三个状态: pre-prepare、 prepare、 comited; 消息也有三种: pre-prepare、prepare、 comited。

PBFT是一 种基于消息传递的一致性算法，算法经过三个阶段达成一致性，这些阶段可能因为失败而重复进行。

2、PBFT的优点

• 共识的时间延迟大约在2-5秒，基本达到商用实时处理的要求;
• 共识效率高，可实现高频交易量的需求;
• 非常适合联盟链的应用场景，因此成为目前使用最多的联盟链共识算法。

3、PBFT的缺点

• 当系统只剩下33%的节点运行时，系统会停止运行;
• PBFT算法在共有链中不适合。

(五)、Paxos算法

1、Paxos解决的是非拜占庭将军问题

  .分布式系统中根据有无恶意节点，分为拜占庭容错和非拜占庭容错机制;

  . Paxos解决的仅仅是指分布式系统中的节点存在故障，但是不存在恶意节点;

  .1998年Lamport提出Paxos算法， 后续又增加了多个改进版本的Paxos,行成了Paxos算法家族;

  . Paxos是一种基于消息传递且具有高度容错特性的一致性算法。 但是Paxos家族共同的特点是不易于工程实现。

2、Paxos被用于分布式系统中典型的例子就是Zookeeper,他是第一个被 证明的共识算法，其原理基于两阶段提交并扩展。

3、Paxos算法中将节点分为三种类型:

  . proposer:提出一一个提案，等待大家批准为结案。往往是客户端担任该角色. acceptor: 负责对提案进行投票。往往是服务端担任该角色

  learner:被告知结案结果，并与之统一，不参与投票过程。可能为客户端或服务端

  .基本过程包括proposer提出提案，先争取大多数acceptor的支持，超过一 半支持时，则发送结案结果给所有人进行确认。一个潜在的问题是proposer在此过程中出现故障，可以通过超时机制来解决。极为凑巧的情况下，每次新的一轮提案的proposer都恰好故障，系统则永远无法达成一致(概率很小)。. Paxos能保证在超过50%的正常节点存在时，系统能达成共识。

4、Paxos协议用于微信PaxosStore中，每分钟调用Paxos协议过程数十亿次量级。

(六)、Raft算法

1、Raft算法是对Paxos算法的一种简单实现。

  .Raft, 中文是救生艇的意思;

  .由于Paxos太难懂，也太难以实现，Raft算法应运而生;

  .2013年底，由斯坦福大学的Diego Ongaro和John Ousterhout发布;Raft与Paxos比， Raft更适合用来学习以及做工程实现; 

  . Raft使 用的是Log进行同步，并且将服务器分为三种角色: Leader (领导者)、Candiate (候选人)和Follower (追随者)， 相互可以互相转换。

• Raft从大的角度看，分为两个过程:

  .1、Leader选举:每个candidate随机经过一 定时间都会提出选举方案，最近阶段中得票最多者被选为leader

  .2、同步log: Leader会找到系统中log最新的记录，与Follower进行Heartbeats同步，强制所有的Follower来刷新到这个记录，这里的log指的是各种事件的发生记录

2、Raft的优点:

  .不需要代币也可以工作，实现秒级共识验证。

3、Raft的缺点:

  .去中心化程度不如Bitcoin; 

  .更适合多方参与的多中心商业模式。