精华内容
下载资源
问答
  • 共识算法

    2019-10-17 09:29:17
    本套课程带你认识常用的共识算法及其代码实现; 课程简介 在区块链网络中,谁获得记账权是通过全网节点间所达成的共识来决定的; 共识算法即这种“共识”的算法/代码体现; 共识算法解决了拜占庭将军问题,即让一群...
  • 区块链中常用共识算法总结

    万次阅读 2017-09-18 19:15:21
    本文是对区块链技术中涉及的共识算法的学习总结整理。 其中PBFT是联盟链常用共识算法,Raft是私有链常用的共识算法,而PoW(比特币采用)是公有链常用的共识算法......

    本文是对区块链技术中涉及的共识算法的学习总结整理。 其中PBFT是联盟链常用共识算法,Raft是私有链常用的共识算法,而PoW(比特币采用)是公有链常用的共识算法。

    建议对区块链的学习,要分成是公有链还是联盟链,这两种链中一般采用的共识算法是有较大不同的,P2P网络等也有较大的不同。传统的共识算法一般不适用于公有链,而一定程度上适用于联盟链。

    实用拜占庭容错系统PBFT(联盟链中常用)

    拜占庭容错技术(Byzantine Fault Tolerance,BFT)是一类分布式计算领域的容错技术,是一种解决分布式系统容错问题的通用方案。实用拜占庭容错系统(Practical Byzantine Fault Tolerance,PBFT)使拜占庭协议的运行复杂度从指数级别降低到多项式级别,使拜占庭协议在分布式系统中应用成为可能。

    拜占庭容错系统

    拜占庭容错系统是指:在一个拥有nnn台节点的系统,整个系统,对每个请求满足如下条件:

    • 所有非拜占庭节点使用相同的输入信息,产生同样的结果;
    • 如果输入的信息正确,那么所有非拜占庭节点必须接收这个信息,并计算相应的结果。

    与此同时,在拜占庭系统的实际运行过程中一般假设系统中拜占庭节点不超过mmm台,并且对每个请求满足2个指标:

    • 安全性——任何已经完成的请求都不会被更改,它可以在以后请求看到;
    • 活性——可以接受并且执行非拜占庭客户端的请求,不会被任何因素影响而导致非拜占庭客户端的请求不能执行。

    拜占庭系统目前普遍采用的假设条件包括:

    1. 拜占庭节点的行为可以是任意的,拜占庭节点之间可以共谋;
    2. 节点之间的错误是不相关的;
    3. 节点之间通过异步网络连接,网络中的消息可能丢失、乱序、延时到达;
    4. 服务器之间传递的信息,第三方可以知晓 ,但是不能窜改、伪造信息的内容和验证信息的完整性;

    发生故障的节点称为拜占庭节点;正常的节点为非拜占庭节点。

    状态机拜占庭系统

    状态机拜占庭系统的特点

    状态机拜占庭系统的特点是整个系统共同维护一个状态,所有节点采取一致的行动,一般包括 3 种协议:一致性协议检查点协议视图更换协议。系统正常运行在一致性协议和检查点协议下,视图更换协议则是只有在主节点出错或者运行缓慢的情况下才会启动,负责维系系统继续执行客户端请求的能力。

    状态机拜占庭系统的核心协议

    一、一致性协议
    一致性协议的目标是使来自客户端的请求在每个服务器上都按照一个确定的顺序执行。在协议中,一般有一个服务器被称作主节点,负责将客户端的请求排序;其余的服务器称作从节点,按照主节点提供的顺序执行请求。所有的服务器都在相同的配置信息下工作,这个配置信息称作view,每更换一次主节点,view就会随之变化。

    一致性协议至少包含3个阶段:发送请求、序号分配和返回结果。根据协议设计的不同,可能包含相互交互、序号确认等阶段。

    一致性协议解决一致性的方法主要有:
    1)服务器之间两两交互,服务器通过将自己获得的信息传递给其他的服务器;
    2)由客户端收集服务器的信息,将收集的信息制作成证明文件再发送给服务器。对于一个包含3m+13m+13m+1台服务器的拜占庭系统,需要收集到2m+12m+12m+1台服务器发送的一致信息,才能保证达成一致的非拜占庭服务器数量大于拜占庭服务器数量。

    引申思考:采用PBFT共识算法的区块链系统节点数量的下限和上限?

    二、检查点协议
    拜占庭系统每执行一个请求,服务器需要记录日志。如果日志得不到及时的清理,就会导致系统资源被大量的日志所占用,影响系统性能及可用性。另一方面,由于拜占庭服务器的存在,一致性协议并不能保证每一台服务器都执行了相同的请求,所以,不同服务器状态可能不一致。例如,某些服务器可能由于网络延时导致从某个序号开始,之后的请求都没有执行。因此,拜占庭系统中设置周期性的检查点协议,将系统中的服务器同步到某一个相同的状态。因此,周期性的检查点协议可以定期地处理日志,节约资源,同时及时纠正服务器状态。

    处理日志主要解决的问题就是区分那些日志可以清理,那些日志仍然需要保留。如果一个请求已经被m+1m+1m+1台非拜占庭服务器执行,并且某一服务器iii能够向其他的服务器证明这一点,那么iii就可以将关于这个请求的日志删除。目前,协议普遍采用的方式是服务器每执行一定数量的请求,就将自己的状态发送给所有服务器并且执行一个该协议,如果某台服务器接收到2m+12m+12m+1台服务器的状态,那么其中一致的部分就是至少有m+1m+1m+1非拜占庭服务器经历过的状态,因此,这部分的日志就可以删除,同时将自己状态更新只较新状态。

    三、视图更换
    在一致性协议里,已经知道主节点在整个系统中拥有序号分配,请求转发等核心能力,支配着这个系统的运行行为。然而一旦主节点自身发生错误,就可能导致从节点接收到具有相同序号的不同请求,或者同一个请求被分配多个序号等问题,这将直接导致请求不能被正确执行。视图更换协议的作用就是在主节点不能继续履行职责时,将其用一个从节点替换掉,并且保证已经被非拜占庭服务器执行的请求不会被篡改。

    视图更换协议一般有两种触发方式:
    1)只由服务器触发,这一类触发方式中,判断服务器一致性是否达成的工作是由服务器自身负责,客户端不能从请求的整个执行过程中获得服务器运行状况的信息;
    2)客户端触发,这一类触发方式中,客户端一般负责判断服务器是否达成一致,如果不达成一致,那么就能判断服务器运行出现问题,如果是主节点的问题就会要求服务器更换主节点。

    视图更换协议需要解决的问题是如何保证已经被非拜占庭服务器执行的请求不被更改。由于系统达成一致性之后至少有m+1m+1m+1台非拜占庭服务器执行了请求,所以目前采用的方法是:由新的主节点收集至少2m+12m+12m+1台服务器的状态信息,这些状态信息中一定包含所有执行过的请求;然后,新主节点将这些状态信息发送给所有的服务器,服务器按照相同的原则将在上一个主节点完成的请求同步一遍.同步之后,所有的节点都处于相同的状态,这时就可以开始执行新的请求。

    实用拜占庭容错系统PBFT详解

    实用拜占庭容错系统(Practical Byzantine Fault Tolerance,PBFT),是一类状态机拜占庭系统。

    PBFT的一致性协议如下:PBFT系统通常假设故障节点数为mmm个,而整个服务节点数为3m+13m+13m+1个。每一个客户端的请求需要经过5个阶段,通过采用两次两两交互的方式在服务器达成一致之后再执行客户端的请求。由于客户端不能从服务器端获取任何服务器运行的状态信息,PBFT中主节点是否发生错误只能由服务器监测。如果服务器在一段时间内都不能完成客户端的请求,则会触发视图更换协议。
    这里写图片描述

    上图显示了一个简化的PBFT的协议通信模式,其中CCC为客户端,N0N_0N0~N3N_3N3表示服务节点,特别的,N0N_0N0为主节点,N3N_3N3为故障节点。整个协议的基本过程如下:
    1)客户端发送请求,激活主节点的服务操作;
    2)当主节点接收请求后,启动三阶段的协议以向各从节点广播请求;

    1. 序号分配阶段,主节点给请求赋值一个序号nnn,广播序号分配消息和客户端的请求消息mmm,并将构造pre-prepare消息给各从节点;
    2. 交互阶段,从节点接收pre-prepare消息,向其他服务节点广播prepare消息;
    3. 序号确认阶段,各节点对视图内的请求和次序进行验证后,广播commit消息,执行收到的客户端的请求并给客户端响应。

    3)客户端等待来自不同节点的响应,若有m+1m+1m+1个响应相同,则该响应即为运算的结果;

    Raft

    Raft是在非拜占庭故障下达成共识的强一致协议在区块链系统中,使用Raft实现记账共识的过程可以描述如下:首先选举一个leader,接着赋予leader完全的权利管理记账。leader从客户端接收记账请求,完成记账操作,生成区块,并复制到其他记账节点。有了leader简化了记账操作的管理。如果leader失效或与其他节点失去联系,这时,系统就会选出新的leader。

    Raft基础

    一个Raft集群通常包含5个服务器,允许系统有2个故障服务器。每个服务器处于3个状态之一:leader、follower或candidate。正常操作状态下,仅有一个leader,其他的服务器均为follower。follower是被动的,不会对自身发出的请求而是对来自leader和candidate的请求做出响应。leader处理所有的客户端请求(若客户端联系follower,则该follower将转发给leader)。candidate状态用来选举leader。

    Raft阶段主要分为两个,首先是leader选举过程,然后在选举出来的leader基础上进行正常操作,比如日志复制、记账等。

    leader选举

    当follower在选举超时时间内未收到leader的心跳消息,则转换为candidate状态。为了避免选举冲突,这个超时时间是一个150~300ms之间的随机数。

    一般而言,在Raft系统中:
    1)任何一个服务器都可以成为一个候选者candidate,它向其他服务器follower发出要求选举自己的请求。
    2)其他服务器同意了,发出OK。如果在这个过程中,有一个follower宕机,没有收到请求选举的要求,此时候选者可以自己选自己,只要达到N/2+1N/2+1N/2+1的大多数票,候选人还是可以成为leader。
    3)这样这个候选者就成为了leader领导人,它可以向follower发出指令,比如进行记账。
    4)以后可以通过心跳进行记账的通知。
    5)一旦这个leader崩溃了,那么follower中有一个成为候选者,并发出邀票选举。
    6)follower同意后,其成为leader,继续承担记账等指导工作。
    在这里插入图片描述

    记账过程

    Raft的记账过程按以下步骤完成:
    1)假设leader领导人已经选出,这时客户端发出增加一个日志的要求;
    2)leader要求follower遵从他的指令,都将这个新的日志内容追加到他们各自日志中;
    3)大多数follower服务器将交易记录写入账本后,确认追加成功,发出确认成功消息;
    4)在下一个心跳中,leader会通知所有follower更新确认的项目。
    对于每个新的交易记录,重复上述过程。

    如果在这一过程中,发生了网络通信故障,使得leader不能访问大多数follower,那么leader只能正常更新它能访问的那些follower服务器。而大多数的服务器follower因为没有了leader,它们将重新选举一个候选者作为leader,然后这个leader作为代表与外界打交道,如果外界要求其添加新的交易记录,这个新的leader就按上述步骤通知大多数follower,如果这时网络故障修复了,那么原先的leader就变成follower,在失联阶段,这个老leader的任何更新都不能算确认,都回滚,接收新的leader的新更新。

    如果想更直观的理解Raft协议,可以看动画演示
    论文原文:In Search of an Understandable Consensus Algorithm
    学习参考:The Raft Consensus Algorithm

    PoW

    PoW的原理可参看这篇博文哈希算法及在区块链中的应用中哈希函数难题友好性这一节,理解了难题友好性,就基本理解了PoW机制的原理。结合比特币去理解PoW。比特币PoW的过程,就是将不同的nonce值作为输入,尝试进行SHA256哈希运算,找出满足给定数量前导0的哈希值的过程。要求的前导0的个数越多,代表难度越大。比特币节点求解工作量证明问题的步骤归纳如下:

    1)生成铸币交易,并与其他所有准备打包进区块的交易组成交易列表,通过Merkle树算法生成Merkle跟哈希;
    2)把Merkle根哈希及其他相关字段组装成区块头,将区块头的80字节数据作为工作量证明的输入;
    3)不停地变更区块头中的随机数nonce,并对每次变更后的区块头做双重SHA256运算,将结果值与当前网络的目标难度做比对,如果满足难度条件,则解题成功,工作量证明完成。

    参考资料:
    拜占庭共识算法之PBFT
    Raft动画演示
    The Raft Consensus Algorithm

    展开全文
  • 课程目标 本套课程带你认识常用的共识算法及其代码实现; 课程简介 在区块链网络中,谁获得记账权是通过全网节点间所达成的共识来决定的;  共识算法即这种“共识”的算法/代码体现;  共识算法解决了...
  • 什么是共识算法

    万次阅读 多人点赞 2019-04-05 10:28:26
    本文尝试从源头开始,告诉大家区块链共识算法的来龙去脉。包含以下三部分: 什么是共识算法 著名的共识设计理论 经典的共识算法设计 什么是共识算法 背景 分布式系统集群设计中面临着一个不可回避的问题,一致...

    本文尝试从源头开始,告诉大家区块链共识算法的来龙去脉。包含以下三部分:

    什么是共识算法

    著名的共识设计理论

    经典的共识算法设计


    什么是共识算法

    背景

    分布式系统集群设计中面临着一个不可回避的问题,一致性问题

    对于系统中的多个服务节点,给定一系列操作,如何试图使全局对局部处理结果达成某种程度的一致?

    这个一致性问题大致有如下的场景:

    节点之间通讯不可靠的,延迟和阻塞

    节点的处理可能是错误的,甚至节点自身随时可能宕机

    节点作恶

    举例说明,就比如有两家电影院同时售卖总量一定的电影票,在这样的场景下,要如何设计方式来保证两家电影院协调同步不出现超卖或者错卖的问题呢?

    共识算法,就是解决对某一提案(目标,投票等各种协作工作),大家达成一致意见的过程

    比如上述的买票问题,就可以有如下的设计:

    1.每次卖票打电话给其他电影院,确认当前票数

    2.协商售卖时间,比如一三五A卖,二四六B卖

    3.成立个第三方存票机构,它统一发票

    通过以上的设计,可以看出一个很重要的解决一致性算法的解决思路,即:

    将可能引发不一致的并行操作进行串行化,就是现在计算机系统里处理分布式一致性问题基础思路和唯一秘诀

     


    著名的共识设计理论

    FLP 不可能性原理  共识算法的理论下限

    提出该定理的论文是由 Fischer, Lynch 和 Patterson 三位作者于 1985 年发表,该论文后来获得了 Dijkstra(就是发明最短路径算法的那位)奖。

    FLP 原理认为对于允许节点失效情况下,纯粹异步系统无法确保一致性在有限时间内完成。

    三人三房间投票例子

    三个人在不同房间,进行投票(投票结果是 0 或者 1)。三个人彼此可以通过电话进行沟通,但经常会有人时不时地睡着。比如某个时候,A 投票 0,B 投票 1,C 收到了两人的投票,然后 C 睡着了。A 和 B 则永远无法在有限时间内获知最终的结果。如果可以重新投票,则类似情形每次在取得结果前发生

    带入到计算机领域就是说,即便在网络通信可靠情况下,一个可扩展的分布式系统的共识问题的下限是无解。即可靠性的下限是0%

    CAP  分布式系统领域的重要原理

    CAP 原理最早由 Eric Brewer 在 2000 年,ACM 组织的一个研讨会上提出猜想,后来 Lynch 等人进行了证明

    • C(一致性):所有的节点上的数据时刻保持同步,即数据一致

    • A(可用性):每个请求都能在一定时间内接受到一个响应,即低延迟

    • P(分区容错):当系统发生分区时仍然可以运行的

    定理:任何分布式系统只可同时满足二点,没法三者兼顾。即数据一致,响应及时,可分区执行不可能同时满足。

    举个例子:

    一个分布式网路上,某一个节点有一组依赖数据A,当网络无延迟,无阻塞时,依赖于X的操作可正常进行。但网络无延迟阻塞在现实世界中是没法100%保证的,那么当网络异常时,必然会产生分布式系统的分区和孤岛,那当一个执行操作在A分区之外时,如果要保证P,即当系统发生分区时仍可运行,就需要在分布式系统中多个节点有X的备份数据,以应对分区情况。则这时候就需要在C,A之间做出选择。

    假如选择C,即要保证数据在分布式网络中的一致性,那么就需要在X每次改动时,需要将全网节点的X数据同步刷新成最新的状态,那么在等待数据刷新完成之前,分布式系统是不可响应X的依赖操作的,即A的功能缺失

    假如选择A,即要突出低延迟的实时响应。那么在响应的时候,可能全节点的X数据并没有同步到最新的状态,则会导致C的缺失。

    上面看上去有些绕,那么你只要记住这句话,

    CAP原理在分布式网络系统的应用讨论,其实就是讨论在允许网络发生故障的系统中,该选择一致性还是可靠性?

    如果系统重视一致性,那么可以基于ACID原则做系统设计

    即 Atomicity(原子性)、Consistency(一致性)、Isolation(隔离性)、Durability(持久性)。

    ACID 原则描述了对分布式数据库的一致性需求,同时付出了可用性的代价。

    • Atomicity:每次操作是原子的,要么成功,要么不执行;

    • Consistency:数据库的状态是一致的,无中间状态;

    • Isolation:各种操作彼此互相不影响;

    • Durability:状态的改变是持久的,不会失效

    相应的有一个BASE原则,(Basic Availiability,Soft state,Eventually Consistency)则强调了可用性。

     


    经典的共识算法设计

    业内,针对节点异常的情况,会有两种分类

    1.故障的,不响应的节点,成为非拜占庭错误

    2.恶意响应的节点,称为非拜占庭错误

    Paxos 最早的共识算法  非拜占庭算法的代表

    Paxos有三种角色:

    • proposer:提出一个提案,等待大家批准为结案。客户端担任该角色;

    • acceptor:负责对提案进行投票。往往是服务端担任该角色;

    • learner:被告知结案结果,并与之统一,不参与投票过程。即普通节点

    系统运行由proposer驱动,当合法提案在一定时间内收到1/2以上投票后达成共识。

    因此,可得出无法达成共识的条件:

    1.proposer故障

    2.二分之一以上acceptor故障

    拜占庭问题与BFT(Byzantine Fault Tolerant) 算法

    Leslie Lamport 1982 年提出用来解释一致性问题的一个虚构模型。

    拜占庭是古代东罗马帝国的首都,由于地域宽广,守卫边境的多个将军(系统中的多个节点)需要通过信使来传递消息,达成某些一致的决定。但由于将军中可能存在叛徒(系统中节点出错),这些叛徒将努力向不同的将军发送不同的消息,试图会干扰一致性的达成。

    拜占庭问题即为在此情况下,如何让忠诚的将军们能达成行动的一致。

    对于拜占庭问题来说,假如将军总数为 N,叛变将军数为 F,则当N>=3F+1 时,问题才有解,即叛变的将军不超过1/3时,存在有效的算法,如BFT,不论叛变者如何折腾,忠诚的将军们总能达成一致的结果。

    这是一个数学论证的结论,有兴趣的同学可以自行推导。

    PBFT  一种高效拜占庭容错共识算法

    PBFT是Practical Byzantine Fault Tolerance的缩写,意为实用拜占庭容错算法。该算法是Miguel Castro 和Barbara Liskov(2008年图灵奖得主)在1999年提出来的,解决了原始拜占庭容错算法效率不高的问题。

    他的核心思想是:对于每一个收到命令的将军,都要去询问其他人,他们收到的命令是什么。

    如上图,假设命令由A将军分发,假如A是作恶异常,分发给B,C,D的操作分别是1,2,3.意图扰乱共识。拜占庭容错算法上设计实现是,当B,C,D收到命令后,相互之间也会沟通从A收到的命令是否一致,从而达到识破干扰的目的。其容错的极限值就是N>=3F+1

    PBFT 在区块链上的实现

    区块链的节点分为记账节点和普通节点两个角色

    记账节点负责向全网提供记账服务,并维护全局账本,每过一段时间从记账节点中选一个议长,进行命令的分发,其他记账节点则作为议员进行验证

    将军就是记账节点,拥有全局账本,并验证交易的有效性,过互相传达验证结果,在f<=(n-1)/3的前提下,可以保证能达到全局的一致性

    共识的一般流程如下:

    1.任一节点接收到发送者签名的交易数据请求后,向全网广播

    2.所有记账节点均独立监听全网的交易数据,并记录在内存

    3.议长在经过t后发送共识请求提案request

    4.议员在收到提案后,进行相关验证,发送响应response

    5.任意节点在限定时间内收到至少F+1个response后,共识达成,把交易记录入区块并发布给全网,如果超时,则更换视图和议长

    6.任意节点在收到完整区块后,把包含的交易从内存中删除

    开始下一个共识循环

    区块产生间隔t,    记账节点n,  可容错节点数f, 视图编号v,  区块高度h, 议长编号p,  议员编号i 

    p=(h-v)%n 

     


    未来的发展

    POW算法建立了比特币帝国,具有划时代的意义。但其能耗和速度问题却是制约区块链普及的两大难以解决的问题。

    目前POS算法是一大趋势,以太坊的Casper,EOS的DPos等都是借鉴了上述前人的设计理念做的基于应用场景的优化改造,但万变不离其宗,我和大家一样,需要不断的学习和思考,没准,能有发明出自己的共识算法的一天呢。



     

     

    展开全文
  • 密码学与共识算法

    2019-12-10 13:53:03
    本节为密码学与共识算法,主要讲解go中的加密算法和共识算法,如dpos、pos等。
  • 共识算法是区块链系统维护数据一致性的核心机制。本文深入调研并分析了具有代表性的共识算法及其演化历程;基于共识过程提出共识算法的分类模型,并对各类型中代表性的共识算法进行详细分析;最后从去中心化、可扩展...
  • Raft算法是一切以领导者为主,在分布式系统中,就一系列值达成共识与日志的一致。是一种强领导者模型,领导者的性能决定了整个集群的性能。它是现今最常用的一种分布式共识算法
  • 区块链基础:共识算法

    千人学习 2018-11-28 15:28:53
    在区块链网络中,谁获得记账权是... 共识算法即这种“共识”的算法/代码体现; 共识算法解决了拜占庭将军问题,即让一群人在彼此不信任的情况下还能在一起自动协调工作; 本套课程带你认识常用的共识算法及其代码实现;
  • DPOS共识算法白皮书

    2018-04-22 14:28:01
    DPOS共识算法白皮书,即石墨烯技术,第三代共识算法,依然有缺点(DPOS共识算法--缺失的白皮书 英文 )
  • 区块链的共识算法

    2021-01-20 13:17:36
    区块链的共识算法 前一阵子在准备很难的一门数学考试,基本上花费了一两周的时间去复习,也没怎么去准备项目方面的东西。。。 然后在这几周内碰到了几个有意思的问题或者事情,在这里想把他们写出来。 区块链的一些...
  • RBFT共识算法

    热门讨论 2021-05-17 14:28:46
    Hyperchain平台支持可插拔的共识机制,可以针对区块链的不同应用场景提供不同的共识算法,当前版本已经实现了PBFT算法的改良算法:高鲁棒拜占庭容错算法RBFT(Robust Byzantine Fault Tolerance)

    传统的PBFT算法无法动态的添加和删除结点,高鲁棒拜占庭容错算法RBFT(Robust Byzantine Tolerance)算法实现了该功能。

    在RBFT算法中,有几个变量我们需要知道:f,N,quorum

    • N ; 代表结点的数量。
    • f :代表PBFT中最多能容忍的错误的结点
    •  
    • quorum:达到共识需要的结点数量

    因此在PBFT算法中,为了能够容忍f个错误,需要的结点数量是3f+13f+1

    在RBFT算法中,有一个主节点和多个从结点,其中主节点是通过选举产生的,负责对客户端发来的交易进行打包处理,而从节点很简单,进行共识认证以及主结点的选取。

    1. 概述

    共识机制是保证区块链中所有共识节点(即验证节点:validating peer, VP)按照相同顺序执行交易、写入账本的基础,而记账节点(即非验证节点:non-validating peer, NVP)只需要从其所连接的共识节点中同步账本信息,因此无需参与共识。

    Hyperchain平台支持可插拔的共识机制,可以针对区块链的不同应用场景提供不同的共识算法,当前版本已经实现了PBFT算法的改良算法:高鲁棒拜占庭容错算法RBFT(Robust Byzantine Fault Tolerance),其算法构思来源于多篇论文(尤其是Aardvark),后续将陆续支持RAFT等共识算法。

    客户端发送交易到Hyperchain平台,API层解析出交易后转发给共识模块,共识模块接收并缓存交易到本地的交易池(TxPool)中,交易池承担着缓存交易与打包区块的作用,因此是作为共识模块的子模块实现的。另外,共识模块还需要维护一个共识的数据库,用于存储算法所需的变量以便宕机后的自主恢复,例如RBFT算法需要维护视图,PrePrepare,Prepare,Commit等共识信息。

    image0

    2. RBFT相关变量

    在一个由N个节点(N>=4)组成的共识网络中,RBFT最多能容忍f个节点的拜占庭错误,其中:

    而能够保证达成共识的节点个数为:

    3. RBFT常规流程

    RBFT的常规流程保证了区块链各共识节点以相同的顺序处理来自客户端的交易。RBFT同PBFT的容错能力相同,需要至少3f+1个节点才能容忍f个拜占庭错误。下图为最少集群节点数下的共识流程,其N=4,f=1。图中的Primary1为共识节点动态选举出来的主节点,负责对客户端发来的交易进行排序打包,Replica2,3,4为从节点。所有节点执行交易的逻辑相同并能够在主节点失效时参与新主节点的选举。

    常规流程

    RBFT共识保留了PBFT原有的三阶段处理流程(PrePrepare、Prepare、Commit)的同时增加了重要的交易验证(validate)环节,在保证对交易执行顺序达成共识的同时也保证了对区块验证结果的共识。

    RBFT常规流程在原生的PBFT算法中穿插了交易验证环节,主节点将交易打包成块后先行验证,并将验证结果包含到PrePrepare消息中进行全网广播,这样PrePrepare消息中既包含了排好序的交易信息也包含了区块验证结果。从节点在收到主节点的PrePrepare消息后先检查消息的合法性,检查通过后广播Prepare消息表明本节点同意主节点的排序结果;在收到(quorum-1)个Prepare消息后从节点才会开始验证区块,并将验证结果与主节点的验证结果进行比对,比对结果一致则广播Commit表明本节点同意主节点的验证结果,否则直接发起ViewChange表明本节点认为主节点有异常行为。RBFT常规流程具体分为如下几个步骤:

    1. 交易转发阶段:客户端将交易发送到区块链中的任意节点(包括共识节点与记账节点),其中记账节点在收到交易后会主动转发给与其相连的共识节点;而共识节点在收到客户端的交易后将其广播给其他共识节点,这样所有共识节点的交易池中都会维护一份完整的交易列表;
    2. PrePrepare阶段:主节点按照如下策略进行打包:用户可以根据需求自定义打包的超时时间(batch timeout)与打包的最大区块大小(batch size),主节点在超时时间内收集到了足够多(超过最大区块大小个数)的交易或者超时时间到达后仍未收集到足够多的交易都会触发主节点的打包事件。主节点将交易按照接收的时间顺序打包成块,并进行验证,计算执行结果,最后将定序好的交易信息连同验证结果等写入PrePrepare消息中广播给所有共识节点,开始三阶段处理流程;
    3. Prepare阶段:从节点在收到主节点的PrePrepare消息后,首先进行消息合法性检查,检查当前的视图与区块号等信息,检查通过后向共识节点广播Prepare消息;
    4. Commit阶段:从节点在收到(quorum-1)个Prepare消息以及相应的PrePrepare消息后进行验证,并将验证结果与主节点写入PrePrepare消息中的验证结果进行比对,比对结果一致则广播Commit表明本节点同意主节点的验证结果,否则直接发起ViewChange表明本节点认为主节点存在异常行为,需要切换主节点;
    5. 写入账本:所有共识节点在收到quorum个Commit消息后将执行结果写入本地账本。

    Hyperchain通过在共识模块中加入验证机制,可以保证从节点对主节点的每一次排序打包的结果进行校验,尽早地发现主节点的拜占庭行为,提升了系统的稳定性。

    检查点

    为了防止运行过程中产生过多的消息缓存,共识节点需要定时清理一些无用的消息缓存。RBFT通过引入PBFT算法中的检查点(checkpoint)机制进行垃圾回收并将检查点的大小K固定设置为10。节点在写入到K的整数倍个区块后达到一个检查点,并广播该检查点的信息,待收集到其他(quorum-1)个共识节点相同的检查信息后就达到了一个稳定检查点(stable checkpoint),随后即可清理该检查点之前的一些消息缓存,保证了运行过程中消息缓存不会无限制地增长。

    交易池

    交易池是共识节点用于缓存交易的场所,交易池的存在一方面限制了客户端发送交易的频率,另一方面也减少了主节点的带宽压力。首先,通过限制交易池的缓存大小,Hyperchain平台可以在交易池达到限制大小后拒绝接收来自客户端的交易,这样,在合理评估机器性能的情况下,通过合理设置交易缓存大小,可以最大限度地利用机器性能而又不至于出现异常。其次,共识节点在接收到来自客户端的交易后先将其存到自己的交易池中,随后向全网其他共识节点广播该条交易,保证了所有共识节点都维护了一份完整的交易列表;主节点在打包后只需要将交易哈希列表放到PrePrepare消息中进行广播即可,而不用将完整的交易列表打包进行广播,大大减轻了主节点的出口带宽压力。如果从节点在验证之前发现缺少了某些交易,也只需要向主节点索取缺少的那些交易而不用索取整个区块里面所有的交易。

    4. RBFT视图变更

    RBFT视图变更能够解决主节点成为拜占庭节点的问题。在RBFT算法中,参与共识的节点可根据角色分为主节点和从节点。主节点最重要的功能是将收到的交易按照一定策略打包成块,为交易定序,并让所有节点按照此顺序执行。然而,如果主节点发生宕机、系统错误或者被攻占(即成为拜占庭节点),从节点需要及时发现主节点异常并选举产生新的主节点。这将是所有BFT类算法为满足稳定性必须要解决的问题。

    视图

    在RBFT与PBFT中,都引入了视图(View)概念,即每次更换一个主节点的同时都会切换视图。目前RBFT采用轮换的方式切换主节点,并且view从0开始只增不减。当前的view和总节点数量N决定了主节点id:

    可检测到的拜占庭行为

    目前RBFT能够检测到的主节点的拜占庭行为主要有2种场景:

    1. 主节点停止工作,不再发送任何消息;
    2. 主节点发送错误的消息。

    对于场景一,RBFT由nullRequest机制保证,行为正确的主节点会在没有交易发生时,向所有从节点定时发送nullRequest来维持正常连接。如果从节点在规定时间内没有收到nullRequest,则会触发ViewChange流程选举新的主节点。

    对于场景二,从节点会对主节点发出的消息进行验证,如上一节中提到的包含在PrePrepare消息中的验证结果,如果从节点验证不通过的话,会直接发起ViewChange流程选举新的主节点。

    此外,RBFT还提供了可配置的ViewChangePeriod选项。用户可以根据需要设置此选项,每写入一定数量区块后进行主动的ViewChange轮换主节点,一来能够缓解主节点作为打包节点的额外压力,二来也使所有参与共识的节点都能承担一定的打包工作,保证了公平性。

    视图变更流程

    上图中,Primary 1为拜占庭节点,需要进行ViewChange。在RBFT中的ViewChange流程如下:

    1. 从节点在检测到主节点有异常情况(没有按时收到nullRequest消息)或者接收到来自其他f+1个节点的ViewChange消息之后会向全网广播ViewChange消息,自身view从v更改为v+1;
    2. 新视图中主节点收到N-f 个ViewChange消息后,根据收到的ViewChange消息计算出新视图中主节点开始执行的checkpoint和接下来要处理的交易包,封装进NewView消息并广播,发起VcReset;
    3. 从节点接收到NewView消息之后进行消息的验证和对比,如果通过验证,进行VcReset,如果不通过,发送ViewChange消息,进行又一轮ViewChange;
    4. 所有节点完成VcReset之后向全网广播FinishVcReset;
    5. 每个节点在收到N-f个FinishVcReset消息之后,开始处理确定的checkpoint后的交易,完成整个ViewChange流程。

    由于共识模块与执行模块之间是异步通信的,而ViewChange之后执行模块可能存在一些无用的validate缓存,因此共识模块需要在ViewChange完成之前通知执行模块清除无用的缓存,RBFT通过VcReset事件主动通知执行模块清除缓存,并在清理完成之后才能完成ViewChange。

    5. RBFT自主恢复

    区块链网络在运行过程中由于网络抖动、突然断电、磁盘故障等原因,可能会导致部分节点的执行速度落后于大多数节点。在这种场景下,节点需要能够做到自动恢复才能继续参与后续的共识流程。为了解决这类数据恢复的问题,RBFT算法提供了一种动态数据自动恢复的机制(recovery),recovery通过主动索取现有共识网络中所有节点的视图、最新区块等信息来更新自身的存储状态,最终同步至整个系统的最新状态。在节点启动、节点重启或者节点落后的时候,节点将会自动进入recovery,同步至整个系统的最新状态。

    自主恢复流程

    上图中,Replica 4为落后节点,需要进行recovery。此节点在RBFT中的自动恢复流程如下:

    1. Replica 4 首先广播NegotiateView消息,获取当前其余节点的视图信息;
    2. 其余三个节点向Replica 4发送NegotiateViewResponse,返回当前视图信息。
    3. Replica 4 收到quorum个NegotiateViewResponse消息后,更新本节点的视图;
    4. Replica 4 广播RecoveryInit消息到其余节点,通知其他节点本节点需要进行自动恢复,请求其余节点的检查点信息和最新区块信息;
    5. 正常运行节点在收到RecoveryInit消息之后,发送RecoveryResponse,将自身的检查点信息以及最新区块信息返回给Replica 4节点;
    6. Replica 4节点在收到quorum个RecoveryResponse消息后,开始尝试从这些response中寻找一个全网共识的最高的检查点,随后将自身的状态更新到该检查点;
    7. Replica 4节点向正常运行节点索要检查点之后的PQC数据,最终同步至全网最新的状态。

    6. RBFT节点增删

    在联盟链场景下,由于联盟的扩展或者某些成员的退出,需要联盟链支持成员的动态进出服务,而传统的PBFT算法不支持节点的动态增删。RBFT为了能够更加方便地控制联盟成员的准入和准出,添加了保持集群非停机的情况下动态增删节点的功能。

    新增节点流程

    上图中,Replica 5为待新增的节点。RBFT节点的动态新增节点流程如下:

    1. 新增节点Replica 5通过读取配置文件信息,主动向现有节点发起连接,确认所有节点连接成功后更新自身的路由表,并发起recovery;
    2. 现有节点接收到Replica 5的连接请求后确认同意该节点加入,然后向全网广播AddNode消息,表明自己同意该新节点加入整个共识网络;
    3. 当现有节点收到N条(N为现有区块链共识网络中节点总数)AddNode消息后,更新自身的路由表,随后开始回应新增节点的共识消息请求(在此之前,新增节点的所有共识消息是不予处理的);
    4. Replica 5完成recovery之后,向全网现有节点广播ReadyForN请求;
    5. 现有节点在收到ReadyForN请求后,重新计算新增节点加入之后的N,view等信息,随后将其与PQC消息封装到AgreeUpdateN消息中,进行全网广播;
    6. Replica 5加入后的共识网络会产生一个新的主节点,该主节点在收到N-f个AgreeUpdateN消息后,以新的主节点的身份发送UpdateN消息;
    7. 全网所有节点在收到UpdateN消息之后确认消息的正确性,进行VCReset;
    8. 每个节点完成VCReset后,全网广播FinishUpdate消息;
    9. 节点在收到N-f个FinishUpdate消息后,处理后续请求,完成新增节点流程。
    展开全文
  • 课程目标 本套课程带你认识常用的共识算法及其代码实现 课程简介 @课程收益:  掌握劳动量证明(PoW)算法及其实现;  课程配套学习资料,建议学员学习过程中跟着视频教程实操,可理解更加深入。技术问题...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,837
精华内容 1,534
关键字:

共识算法