作者| sun and moon ton light统筹编辑|王小曼制作| CSDN博客
在异步系统中，需要在主机之间进行状态复制，以确保每个主机在状态上达成一致。在异步系统中，主机之间可能会发生故障，因此需要在默认的不可靠异步网络中定义容错协议，以确保所有主机达到安全可靠的状态共识。共识算法实际上是一套规则，一套条件，筛选有代表性的节点。在车链系统中,有很多这样的过滤方案,比如在公共场合链中的POW,POS, DPOS,等等,如果没有授权链或私人的货币体系链,节点的绝对信任,高效的需求链算法无法提供公众的共识,对于这样的车链,成为首选的一致性算法,传统的共识,比如PBFT PAXOS,筏等。
拜占庭容错技术是分布式计算中的一种容错技术。拜占庭式的假设是，由于硬件错误、网络拥塞或中断以及恶意攻击，计算机和网络的行为是不可预测的。拜占庭的容错是用来处理这种异常行为和满足规范，要处理。拜占庭容错系统是一个有n个节点的系统。对于每个请求，整个系统都满足以下条件:1)所有非拜占庭节点使用相同的输入信息产生相同的结果;2)如果输入信息正确，所有非拜占庭节点必须接收该信息并计算相应的结果。拜占廷系统常用的假设有:1)拜占廷节点的行为可以是任意的，拜占廷节点之间可以相互勾结;2)节点间误差无关;3)节点通过异步网络连接，网络中的消息可能丢失、乱序、迟到。然而，大多数协议都假定消息可以在有限的时间内传递到目的地。4)第三方可以嗅出服务器之间传递的信息，但不能篡改、伪造信息内容或验证信息的完整性。拜占廷容错由于其理论上的可行性而不实际，它还需要额外的时钟同步机制的支持。算法的复杂度随节点数的增加呈指数增长。
实用的拜占庭容错算法将拜占庭协议的运行复杂度从指数级降低到多项式级。PBFT是一种状态机复制算法，其中将服务建模为在分布式系统的不同节点上复制副本的状态机。PBFT要求联合维护一个状态。您需要运行三个基本协议，包括一致性协议、检查点协议和视图替换协议。一致性协议。一致性协议至少包括几个阶段:请求、预先准备和应答。它可能包括准备、提交等阶段。在PBFT通信模式下，每个客户端的请求经过五个阶段。由于客户端无法从服务器端获得关于服务器运行状态的任何信息，因此服务器只能监控PBFT中的主节点是否有错误。如果服务器在一段时间内不能完成客户端的请求，视图更改协议将被触发。整个协议的基本流程如下:1)客户端发送请求激活主节点的服务操作。2)主节点收到请求后，启动三级协议将请求广播到各个从节点。[2.1]在序列号分配阶段，主节点向请求分配序列号n，广播序列号分配消息和客户端请求消息m，并向每个从节点构造一条预准备消息。[2.2]在交互阶段，从节点接收预准备消息，并将准备消息广播给其他服务节点;[2.3]在序数确认阶段，每个节点在视图中验证请求和订单后，广播提交消息，执行从客户端收到的请求，并将响应发送给客户端。3)客户端等待来自不同节点的响应。如果有m+1个相同的响应，则响应是操作的结果。
PBFT通常适用于要求高度一致性的私有和附属连锁企业。例如，在ibm领导的区块链超级账本项目中，PBFT是一个可选的一致协议。在Hyperledger Fabric项目中，协商一致模块被设计为可插入模块，支持协商一致算法，如PBFT和Raft。
在一些分布式场景中，PAXOS假设它不需要考虑错综复杂的故障，而只需要处理一般的崩溃故障。在这种情况下，像PAXOS这样的协议会更有效率。PAXOS是一种基于消息传递的一致性算法，具有很高的容错能力。PAXOS有三种角色类:提出者、接受者和学习者，主要是提出者和接受者之间的互动。一个提议者向网络中超过一半的接受者发送一个准备消息。B)申请人发送一个接受消息当有足够的承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人承兑人接受人，接受人，接受人，接受人，接受人，接受人，接受人，接受人，接受人，接受人
流程图如下图所示:
PAXOS协议在微信PaxosStore中使用，PAXOS协议进程以每分钟数十亿个数量级的速度调用。
RaftPAXOS是Lamport设计的一种协议，用于维护分布式系统的一致性。但是由于PAXOS是如此复杂和难以理解，各种实现和变体已经出现。Raft是由Stanford提出的一种更易于理解的一致性算法，它旨在取代广泛使用的PAXOS算法。Raft最初是一种用于管理复制日志的协商一致算法，对于非拜占庭式故障，它是一种强大的协商一致协议。筏的共识实现过程如下:第一，选出一个领导者。leader接收客户端记账请求，完成记账操作，生成块，并复制到其他记账节点。领导拥有完整的管理和记账权。例如，leader可以决定是否接受新的交易记录，而不需要考虑其他的记账节点。leader可能会失败或与其他节点失去联系。在Raft中，每个节点都处于以下三种状态之一:(1)follower:所有节点都以follower开始。如果没有收到领袖消息，它将成为候选状态。(2)候选节点:到其他节点;票在;如果他们得到大部分的票，他们将成为领先者。这个过程被称为领导人选举;(3) leader:系统的所有修改都要先经过leader。每个更改都要写入一个日志条目。Leader收到变更请求流程如下:这个过程称为日志复制(日志复制)1)2)大部分的日志复制到所有追随者节点响应通知所有追随者提交日志3)节点日志提交4)所有的追随者也提交日志5)现在整个系统的统一筏主要分为两个阶段,第一个是领袖选举过程,然后在此基础上的民选领导人的正常运行,如日志复制、计费,等(1)领袖选举当追随者在选举时间内没有收到任何来自领导者的消息时，追随者将被转换为候选人状态。在Raft系统中:1)任何服务器都可以成为候选候选，只要它发送一个请求给其他服务器的关注者来选择自己。2)如果其他服务器同意，发出OK。如果在这一过程中有一名追随者倒下了，并且没有收到选举请求，那么候选人可以选择自己。只要达到N/2+1的多数票，候选人仍然可以成为领先者。3)这样，候选人就成为了领导者，他可以给选民，也就是追随者下达指令，比如记账。4)以后通过心跳消息计费通知。5)一旦领袖垮台，其中一名追随者将成为候选人，并发出选举的请柬。6)得到follower的认可，成为leader，继续负责记账和其他指导工作。(2)日志复制和核算步骤如下:1)假设leader已被选中，客户端发出添加日志的请求;2) leader让follower按照他的指示添加新的日志内容到相应的日志中;3)大部分关注者服务器将交易记录写入账簿后，确认新增成功并发送确认信息;4)在下一条心跳消息中，leader会通知所有关注者更新并确认项目。对每个新事务重复此过程。在此过程中，如果发生网络通信故障，导致leader无法访问大部分follower，则leader只能对其正常访问的follower服务器进行更新。因为服务器的follower大部分都没有leader，所以他们会重新选举一个候选人来做他们的leader，然后leader就会作为一个代表去处理外面的世界。如果外界要求增加新的交易记录，新的leader会按照上面的步骤通知大部分关注者。当网络通信恢复时，原来的领导者将成为追随者。在丢失联系阶段，不能确认旧领导人的任何更新，必须回滚以接收新领导人的新更新。
工作负载证明(POW)在去中心化会计系统中，加入系统的每个节点都需要保存一个完整的会计账簿，但是每个节点不能同时保存账簿，因为节点处于不同的环境，接收的信息也不同。如果他们同时记账，账户就会不一致。通过同时确定哪个节点拥有开票权。在比特币系统中，每隔10分钟左右就会举行一次权力争夺，获胜方有权保留账户，并将新账户信息同步到其他节点。PoW系统的主要特点是计算的不对称性。工作方需要做一些比较困难的工作才能得到结果，但是验证者可以很容易的检查工作方是否做了相应的工作。这个工作负载的要求是在一个字符串之后连接一个名为nonce的整数值字符串，对连接后的字符串执行SHA256哈希操作，并验证得到的哈希结果(以十六进制形式表示)是否以几个零开头。如果比特币网络中的任何节点想要生成一个新的块并将其写入到区块链，则必须解决比特币网络引起的PoW问题。这三个关键元素是工作负载证明函数、块和难度值。工作负载证明函数是该问题的计算方法，分块决定了该问题的输入数据，难度值决定了该问题所需的计算量。(1)工作负载证明功能:SHA256比特币块由块头和块中包含的交易列表组成。block header是一个固定长度为80字节的输入字符串，用于证明比特币的工作负载。
(2)难度调整在每个完整节点独立自动进行。对于每个2016块，所有节点都会根据统一的公式自动调整难度。如果生成块的速度超过10分钟，则会变得更加困难;如果生成的速度低于10分钟，那么它的难度就会降低。公式可以总结为:新难度值=旧难度值次数;(过去的2016块需要时间/20160分钟)工作负载证明需要有一个目标值。硬币的工作证明了目标(目标)公式:目标值=最大目标/难度恒定值的最大目标:0 x00000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff与目标值的大小和难度成反比。比特币工作负载证明，矿工计算的块的哈希值必须小于目标值。(3)POW可以解决这个问题在拜占庭将军硬币POW共识算法是一种概率拜占庭协议(概率)当不诚实的工作力小于50%的网络管理,同时挖矿难度较高(约10分钟的块)硬币网络实现一致性的概念将随增加的数量确认块类指数增长。但当不诚实的规模较大时，甚至不接近50%，比特币的共识算法并不保证正确性，即不保证大部分块将由诚实节点提供。比特币的共识算法不适用于私人和关联链。第一个原因是它是一个最终的一致算法，而不是一个强一致算法。第二个原因是，共识是低效的。扩大知识:一致性
当系统不发生故障并且所有节点在任何时候都不需要通信时，就可以实现严格的一致性。整个系统现在相当于一台机器。在现实中，这是不可能实现的。强一致性，当分布式系统中的更新操作完成时，任何多个进程或线程都将访问系统以获取最新的值。弱一致性意味着系统不保证后续进程或线程访问将返回最新更新的值。系统不承诺在成功写入数据后立即读取最新的写入值，也不承诺读取数据的时间。但是，它会尝试确保它是在一定的时间之后(第二级)。您可以使数据达到一致的状态。最终一致性是弱一致性的一种特殊形式。系统保证最终返回最后一次更新操作的值，而不进行后续更新。换句话说，如果更新后的数据需要在一段时间之后才能访问，这就是最终的一致性。
在股权凭证的POS模式下，有一个术语叫货币时代。每种货币每天都有一个货币年龄。例如，如果你持有100枚硬币总共30天，那么你的货币年龄将是3000。每次你取出365个硬币，你将从该区块获得0.05个硬币的利息(假设利率可以理解为每年5%)，所以在这种情况下，利息= 3000 * 5% / 365 = 0.41个硬币，这是非常有趣的。皮尔币是第一个采用公平证明的货币。peERCoin的公平证明机制结合了随机化和硬币时代的概念。已经至少30天没有使用过的硬币可以参加下一个街区的比赛。更长的和更大的硬币组有更大的可能性签署下一个块。一旦对货币的兴趣用于签署一个块，货币年龄被清除为零，您必须至少等待30天才能签署另一个块。虽然POS机制考虑到了POW的不足，但是基于利益平衡的选择会导致最富有的人的账户拥有更大的权力，这可能会主导记账权。授权分享机制(授权获得凭证、DPOS)的出现，正是基于解决这种短缺的POW和POS机制。
位共享是一种使用DPOS机制的加密货币。其思想是，每个持有位股票的人都有一个产生101个代表的投票权，我们可以把它看作是101个超级节点或池，它们彼此拥有完全相同的权利。如果委托未能履行其职责(当轮到它们时，也未能生成块)，它们就会被移除，而网络会选择一个新的超级节点来替换它们。Bitstocks引入了witness的概念，它可以生成block，每个拥有Bitstocks的人都可以为witness投票。第一个N个候选人(N通常定义为101个)的同意投票可以被选为证人，而被选为证人的人数(N)必须是:至少有一半的参与选民认为N已经被充分去中心化。每个维护周期(1天)更新一次候选证人名单。然后将证人随机排列，每个证人有2秒的许可时间来按顺序生成块。如果证人无法在给定的时间片中生成块，则将块生成权限授予与下一个时间片对应的证人。比特币设计了另一种活动——代表竞赛。当选代表有权提议更改网络参数，包括交易成本、块大小、见证费和块区间。如果大多数代表同意提议的变更，股东有两周的审查期，在此期间他们可以召回代表并废除提议的变更。这种设计确保代表在技术上没有直接修改参数的权利，并且对网络参数的所有修改最终都需要股东的批准。
RippleRipple (RippleRipple)是一种基于Internet的开源支付协议。在Ripple网络中，事务由客户机(应用程序)发起，事务通过跟踪节点或验证节点广播到整个网络。跟踪节点的主要功能是分发交易信息和响应客户端分类账请求。除了包含跟踪节点的所有功能之外，验证节点还可以通过一致协议向分类账添加新的分类账实例数据。
在验证节点之间产生波纹共识，每个节点都预先配置了一个名为UNL(惟一节点列表)的受信任节点列表。列表中的节点可以对事务的完成进行投票。每隔几秒，Ripple网络就会遵循以下共识流程:1)每个验证节点将持续接收来自网络的事务。与本地账本数据核对后，将非法交易直接丢弃，并将合法交易汇总为候选集。交易候选集还包括协商一致过程确认失败后剩余的交易。2)每个验证节点将自己的一组事务候选作为提案发送给其他验证节点。3)验证节点收到其他节点的提案后，如果不是来自UNL上的节点，则忽略该提案;如果它来自于UNL上的一个节点，建议的事务将与本地事务候选集进行比较，如果有相同的事务，事务将获得一张选票。当协议在给定的时间内获得超过50%的选票时，就进入下一轮投票。不超过50%的交易将在下一次协商一致过程中得到确认。4)验证节点将投票超过50%的事务作为提案发送给其他节点，同时将所需投票的阈值提高到60%。重复步骤3)和4)，直到阈值达到80%。5)验证节点将经过80% UNL节点确认的交易正式写入本地分类帐数据，称为最后一个关闭分类帐，即分类帐的最后(最近)状态。
在Ripple的协商一致算法中，投票节点的身份是预先知道的。这种一致算法只适用于许可链场景。Ripple consensus算法的拜占庭容错(BFT)能力为(n-1) /5，这意味着它可以容忍整个网络中20%的节点出现拜占庭错误，而不会影响正确的consensus。在区块链网络中，由于应用场景的不同，设计目标也不同，不同的区块链系统采用不同的一致性算法。一般来说，在私有链和联盟链的情况下，对一致性和正确性有很强的要求。一般而言，应采用一致性较强的一致算法。而在公开案例链中，一致性和正确性通常不可能是百分之百的，通常采用最终一致性(final Consistency)共识算法。协商一致算法的选择与应用场景高度相关。可信环境使用paxos或raft，授权联盟可以使用PBFT，非授权链可以pow、pos、ripple consensus等。协商一致机制可以根据对立各方之间的信任程度自由选择。
版权声明:本文为CSDN博客“阳光月亮”原创文章。它遵循CC 4.0 by-sa的版权协议。请附上原稿和此声明的链接，以便重印。
原始链接:https://blog.csdn.net/sinat_36711025/article/details/104837558
文章标题：块链共识算法总结
文章链接：https://www.btchangqing.cn/27142.html
更新时间：2020年05月27日
本站大部分内容均收集于网络，若内容若侵犯到您的权益，请联系我们，我们将第一时间处理。
