区块链共识算法总结 | 原力计划
做者 | 日月ton光node
责编 | 王晓曼算法
出品 | CSDN博客数据库
常见共识算法介绍
promise
在异步系统中，须要主机之间进行状态复制，以保证每一个主机达成一致的状态共识。而在异步系统中，主机之间可能出现故障，所以须要在默认不可靠的异步网络中定义容错协议，以确保各个主机达到安全可靠的状态共识。缓存
共识算法其实就是一组规则，设置一组条件，筛选出具备表明性的节点。在区块链系统中，存在不少这样的筛选方案，如在公有链中的POW、POS、DPOS等，而在不须要货币体系的许可链或私有链中，绝对信任的节点、高效的需求是公有链共识算法不能提供的，对于这样的区块链，传统的一致性共识算法成为首选，如PBFT、PAXOS、RAFT等。安全
BFT（拜占庭容错技术）
服务器
拜占庭容错技术是一类分布式计算领域的容错技术。拜占庭假设是因为硬件错误、网络拥塞或中断以及遭到恶意攻击的缘由，计算机和网络出现不可预测的行为。拜占庭容错用来处理这种异常行为，并知足所要解决问题的规范。微信
拜占庭容错系统是一个拥有n台节点的系统，整个系统对于每个请求，知足如下条件：网络
1）全部非拜占庭节点使用相同的输入信息，产生一样的结果；并发
2）若是输入的信息正确，那么全部非拜占庭节点必须接收这个信息，并计算相应的结果。
拜占庭系统广泛采用的假设条件包括：
1）拜占庭节点的行为能够是任意的，拜占庭节点之间能够共谋；
2）节点之间的错误是不相关的；
3）节点之间经过异步网络链接，网络中的消息可能丢失、乱序并延时到达，但大部分协议假设消息在有限的时间里能传达到目的地；
4）服务器之间传递的信息，第三方能够嗅探到，可是不能篡改、伪造信息的内容和验证信息的完整性。
拜占庭容错因为其理论上的可行性而缺少实用性，另外还须要额外的时钟同步机制支持，算法的复杂度也是随节点的增长而指数级增长。
PBFT（实用拜占庭容错算法）
实用拜占庭容错下降了拜占庭协议的运行复杂度，从指数级别下降到多项式级别。
PBFT是一种状态机副本复制算法，即服务做为状态机进行建模，状态机在分布式系统的不一样节点进行副本复制。PBFT要求共同维护一个状态。须要运行三类基本协议，包括一致性协议、检查点协议和视图更换协议。
一致性协议。一致性协议至少包含若干个阶段：请求（request）、序号分配（pre-prepare）和响应（reply），可能包含相互交互（prepare），序号确认（commit）等阶段。
PBFT通讯模式中，每一个客户端的请求须要通过5个阶段。因为客户端不能从服务器端得到任何服务器运行状态的信息，PBFT中主节点是否发生错误只能由服务器监测。若是服务器在一段时间内都不能完成客户端的请求，则会触发视图更换协议。
整个协议的基本过程以下：
1）客户端发送请求，激活主节点的服务操做。
2）当主节点接收请求后，启动三阶段的协议以向各从节点广播请求。
［2.1］序号分配阶段，主节点给请求赋值一个序列号n，广播序号分配消息和客户端的请求消息m，并将构造PRE-PREPARE消息给各从节点；
［2.2］交互阶段，从节点接收PRE-PREPARE消息，向其余服务节点广播PREPARE消息；
［2.3］序号确认阶段，各节点对视图内的请求和次序进行验证后，广播COMMIT消息，执行收到的客户端的请求并给客户端以响应。
3）客户端等待来自不一样节点的响应，如有m+1个响应相同，则该响应即为运算的结果。
PBFT通常适合有对强一致性有要求的私有链和联盟链，例如，在IBM主导的区块链超级帐本项目中，PBFT是一个可选的共识协议。在 Hyperledger 的Fabric项目中，共识模块被设计成可插拔的模块，支持像PBFT、Raft等共识算法。
PAXOS
在有些分布式场景下，其假设条件不须要考虑拜占庭故障，而只是处理通常的死机故障。在这种状况下，采用PAXOS等协议会更加高效。。PAXOS是一种基于消息传递且具备高度容错特性的一致性算法。
PAXOS中有三类角色Proposer、Acceptor及Learner，主要交互过程在Proposer和Acceptor之间。算法流程分为两个阶段：
一、phase1
a)proposer向网络内超过半数的acceptor发送prepare消息
b)acceptor正常状况下回复promise消息
二、phase2
a) 在有足够多acceptor回复promise消息时，proposer发送accept消息
b) 正常状况下acceptor回复accepted消息
流程图如图所示：
PAXOS协议用于微信PaxosStore中，每分钟调用PAXOS协议过程数十亿次量级。
Raft
PAXOS是Lamport设计的保持分布式系统一致性的协议。但因为PAXOS很是复杂，比较难以理解，所以后来出现了各类不一样的实现和变种。Raft是由Stanford提出的一种更易理解的一致性算法，意在取代目前广为使用的PAXOS算法。
Raft最初是一个用于管理复制日志的共识算法，它是在非拜占庭故障下达成共识的强一致协议。Raft实现共识过程以下：首先选举一个leader，leader从客户端接收记帐请求、完成记帐操做、生成区块，并复制到其余记帐节点。leader有彻底的管理记帐权利，例如，leader可以决定是否接受新的交易记录项而无需考虑其余的记帐节点，leader可能失效或与其余节点失去联系，这时，从新选出新的leader。
在Raft中，每一个节点会处于如下三种状态中的一种：
（1）follower：全部节点都以follower的状态开始。若是没收到leader消息则会变成candidate状态；
（2）candidate：会向其余节点“拉选票”，若是获得大部分的票则成为leader。这个过程就叫作Leader选举(Leader Election)；
（3）leader：全部对系统的修改都会先通过leader。每一个修改都会写一条日志(log entry)。leader收到修改请求后的过程以下：此过程叫作日志复制（Log Replication）
1）复制日志到全部follower节点
2）大部分节点响应时才提交日志
3）通知全部follower节点日志已提交
4）全部follower也提交日志
5）如今整个系统处于一致的状态
Raft阶段主要分为两个，首先是leader选举过程，而后在选举出来的leader基础上进行正常操做，好比日志复制、记帐等。
（1）leader选举
当follower在选举时间内未收到leader的消息，则转换为candidate状态。在Raft系统中：
1）任何一个服务器均可以成为候选者candidate，只要它向其余服务器follower发出选举本身的请求。
2）若是其余服务器赞成了，发出OK。若是在这个过程当中，有一个follower宕机，没有收到请求选举的要求，此时候选者能够本身选本身，只要达到N/2+1的大多数票，候选人仍是能够成为leader的。
3）这样这个候选者就成为了leader领导人，它能够向选民也就是follower发出指令，好比进行记帐。
4）之后经过心跳消息进行记帐的通知。
5）一旦这个leader崩溃了，那么follower中有一个成为候选者，并发出邀票选举。
6）follower赞成后，其成为leader，继续承担记帐等指导工做。
（2）日志复制
记帐步骤以下所示：
1）假设leader已经选出，这时客户端发出增长一个日志的要求；
2）leader要求follower听从他的指令，将这个新的日志内容追加到各自日志中；
3）大多数follower服务器将交易记录写入帐本后，确认追加成功，发出确认成功信息；
4）在下一个心跳消息中，leader会通知全部follower更新确认的项目。
对于每一个新的交易记录，重复上述过程。
在这一过程当中，若发生网络通讯故障，使得leader不能访问大多数follower了，那么leader只能正常更新它能访问的那些follower服务器。而大多数的服务器follower由于没有了leader，他们将从新选举一个候选者做为leader，而后这个leader做为表明与外界打交道，若是外界要求其添加新的交易记录，这个新的leader就按上述步骤通知大多数follower。当网络通讯恢复，原先的leader就变成follower，在失联阶段，这个老leader的任何更新都不能算确认，必须所有回滚，接收新的leader的新的更新。
POW（工做量证实）
在去中心帐本系统中，每一个加入这个系统的节点都要保存一份完整的帐本，但每一个节点却不能同时记帐，由于节点处于不一样的环境，接收不一样的信息，若是同时记帐，必然致使帐本的不一致。所以经过同时来决定那个节点拥有记帐权。
在比特币系统中，大约每10分钟进行一轮算力竞赛，竞赛的胜利者，就得到一次记帐的权力，并向其余节点同步新增帐本信息。
PoW系统的主要特征是计算的不对称性。工做端要作必定难度的工做才能得出一个结果，而验证方却很容易经过结果来检查工做端是否是作了相应的工做。该工做量的要求是，在某个字符串后面链接一个称为nonce的整数值串，对链接后的字符串进行SHA256哈希运算，若是获得的哈希结果（以十六进制的形式表示）是以若干个0开头的，则验证经过。
比特币网络中任何一个节点，若是想生成一个新的区块并写入区块链，必须解出比特币网络出的PoW问题。关键的3个要素是工做量证实函数、区块及难度值。工做量证实函数是这道题的计算方法，区块决定了这道题的输入数据，难度值决定了这道题所须要的计算量。
（1）工做量证实函数就是SHA256
比特币的区块由区块头及该区块所包含的交易列表组成。拥有80字节固定长度的区块头，就是用于比特币工做量证实的输入字符串。
（2）难度的调整是在每一个完整节点中独立自动发生的。每2016个区块，全部节点都会按统一的公式自动调整难度。若是区块产生的速率比10分钟快则增长难度，比10分钟慢则下降难度。
公式能够总结为：新难度值=旧难度值×（过去2016个区块花费时长/20160分钟）
工做量证实须要有一个目标值。比特币工做量证实的目标值（Target）的计算公式：目标值=最大目标值/难度值
其中最大目标值为一个恒定值：
0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
目标值的大小与难度值成反比。比特币工做量证实的达成就是矿工计算出来的区块哈希值必须小于目标值。
（3）POW可否解决拜占庭将军问题
比特币的POW共识算法是一种几率性的拜占庭协议（Probabilistic BA）
当不诚实的算力小于网络总算力的50%时，同时挖矿难度比较高（在大约10分钟出一个区块状况下）比特币网络达到一致性的概念会随确认区块的数目增多而呈指数型增长。但当不诚实算力具必定规模，甚至不用接近50%的时候，比特币的共识算法并不能保证正确性，也就是，不能保证大多数的区块由诚实节点来提供。
比特币的共识算法不适合于私有链和联盟链。其缘由首先是它是一个最终一致性共识算法，不是一个强一致性共识算法。第二个缘由是其共识效率低。
扩展知识：一致性
严格一致性，是在系统不发生任何故障，并且全部节点之间的通讯无需任什么时候间这种理想的条件下，才能达到。这个时候整个系统就等价于一台机器了。在现实中，是不可能达到的。
强一致性，当分布式系统中更新操做完成以后，任何多个进程或线程，访问系统都会得到最新的值。
弱一致性，是指系统并不保证后续进程或线程的访问都会返回最新的更新的值。系统在数据成功写入以后，不承诺当即能够读到最新写入的值，也不会具体承诺多久读到。可是会尽量保证在某个时间级别（秒级）以后。可让数据达到一致性状态。
最终一致性是弱一致性的特定形式。系统保证在没有后续更新的前提下，系统最终返回上一次更新操做的值。也就是说，若是通过一段时间后要求能访问到更新后的数据，则是最终一致性。
POS（权益证实）
在股权证实POS模式下，有一个名词叫币龄，每一个币天天产生1币龄，好比你持有100个币，总共持有了30天，那么，此时你的币龄就为3000，这个时候，若是你发现了一个POS区块，你的币龄就会被清空为0。你每被清空365币龄，你将会从区块中得到0.05个币的利息(假定利息可理解为年利率5%)，那么在这个案例中，利息 = 3000 * 5% / 365 = 0.41个币，这下就颇有意思了，持币有利息。
点点币（Peercoin）是首先采用权益证实的货币。，点点币的权益证实机制结合了随机化与币龄的概念，未使用至少30天的币能够参与竞争下一区块，越久和越大的币集有更大的可能去签名下一区块。一旦币的权益被用于签名一个区块，则币龄将清为零，这样必须等待至少30日才能签署另外一区块。
POS机制虽然考虑到了POW的不足，但依据权益结余来选择，会致使首富帐户的权力更大，有可能支配记帐权。股份受权证实机制（Delegated Proof of Stake，DPOS）的出现正是基于解决POW机制和POS机制的这类不足。
DPOS（委任权益证实）
比特股（Bitshare）是一类采用DPOS机制的密码货币。它的原理是，让每个持有比特股的人进行投票，由此产生101位表明 , 咱们能够将其理解为101个超级节点或者矿池，而这101个超级节点彼此的权利是彻底相等的。若是表明不能履行他们的职责（当轮到他们时，没能生成区块），他们会被除名，网络会选出新的超级节点来取代他们。
比特股引入了见证人这个概念，见证人能够生成区块，每个持有比特股的人均可以投票选举见证人。获得总赞成票数中的前N个（N一般定义为101）候选者能够当选为见证人，当选见证人的个数（N）需知足：至少一半的参与投票者相信N已经充分地去中心化。
见证人的候选名单每一个维护周期（1天）更新一次。见证人而后随机排列，每一个见证人按序有2秒的权限时间生成区块，若见证人在给定的时间片不能生成区块，区块生成权限交给下一个时间片对应的见证人。
比特股还设计了另一类竞选，表明竞选。选出的表明拥有提出改变网络参数的特权，包括交易费用、区块大小、见证人费用和区块区间。若大多数表明赞成所提出的改变，持股人有两周的审查期，这期间能够罢免表明并废止所提出的改变。这一设计确保表明技术上没有直接修改参数的权利以及全部的网络参数的改变最终需获得持股人的赞成。
Ripple
Ripple（瑞波）是一种基于互联网的开源支付协议，在Ripple的网络中，交易由客户端（应用）发起，通过追踪节点（tracking node）或验证节点（validating node）把交易广播到整个网络中。
追踪节点的主要功能是分发交易信息以及响应客户端的帐本请求。验证节点除包含追踪节点的全部功能外，还可以经过共识协议，在帐本中增长新的帐本实例数据。
Ripple的共识达成发生在验证节点之间，每一个验证节点都预先配置了一份可信任节点名单，称为UNL（Unique Node List）。在名单上的节点可对交易达成进行投票。每隔几秒，Ripple网络将进行以下共识过程：
1）每一个验证节点会不断收到从网络发送过来的交易，经过与本地帐本数据验证后，不合法的交易直接丢弃，合法的交易将汇总成交易候选集（candidate set）。交易候选集里面还包括以前共识过程没法确认而遗留下来的交易。
2）每一个验证节点把本身的交易候选集做为提案发送给其余验证节点。
3）验证节点在收到其余节点发来的提案后，若是不是来自UNL上的节点，则忽略该提案；若是是来自UNL上的节点，就会对比提案中的交易和本地的交易候选集，若是有相同的交易，该交易就得到一票。在必定时间内，当交易得到超过50%的票数时，则该交易进入下一轮。没有超过50%的交易，将留待下一次共识过程去确认。
4）验证节点把超过50%票数的交易做为提案发给其余节点，同时提升所需票数的阈值到60%，重复步骤3）、步骤4），直到阈值达到80%。
5）验证节点把通过80%UNL节点确认的交易正式写入本地的帐本数据中，称为最后关闭帐本（Last Closed Ledger），即帐本最后（最新）的状态。
在Ripple的共识算法中，参与投票节点的身份是事先知道的。该共识算法只适合于权限链（Permissionedchain）的场景。Ripple共识算法的拜占庭容错（BFT）能力为（n-1）/5，便可以容忍整个网络中20%的节点出现拜占庭错误而不影响正确的共识。
在区块链网络中，因为应用场景的不一样，所设计的目标各异，不一样的区块链系统采用了不一样的共识算法。通常来讲，在私有链和联盟链状况下，对一致性、正确性有很强的要求。通常来讲要采用强一致性的共识算法。而在公有链状况下，对一致性和正确性一般无法作到百分之百，一般采用最终一致性（Eventual Consistency）的共识算法。
共识算法的选择与应用场景高度相关，可信环境使用paxos 或者raft，带许可的联盟可以使用pbft ，非许可链能够是pow，pos，ripple共识等，根据对手方信任度分级，自由选择共识机制。
版权声明：本文为CSDN博主「日月ton光」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处连接及本声明。
原文连接：
https://blog.csdn.net/sinat_36711025/article/details/104837558
推荐阅读
老铁们在看签个到！