《区块链金融》课件 第5章 共识机制

微课视频版区块链金融第5章共识机制目录01.拜占庭将军问题02.经典共识机制03.共识机制分类及改进拜占庭将军问题PART01第5章共识机制共识，是指在分布式组网结构中，多方参与的、彼此互不信任的节点在预设机制下，节点间通过交互信息，对某些数据、行为或流程达成一致的过程。实质是一致性问题。共识机制是指定义共识过程的算法、协议或规则，包括公平选取特定的记录节点及设计合理的经济激励机制。共识机制的理论基础是拜占庭容错（ByzantineFaultTolerant，BFT）算法。区块链各节点产生的交易数据由共识机制解决记录问题。5.1拜占庭将军问题第5章共识机制共识机制发展经历：

传统的、准入环境下的分布式系统一致性；适用区块链的、开放的分布式系统共识机制。一致性问题的研究始于20世纪70年代。1978年，IBM的吉姆

格雷（JimGray）提出两阶段提交协议，以解决分布式系统中多节点事务一致性问题，但该协议在节点发生故障时会产生阻塞。戴尔

斯基恩（DaleSkeen）和迈克尔

斯通布雷克（MichaelStonebraker）提出三阶段提交协议，以解决节点故障时的阻塞问题。这两个协议无法解决节点发生故障时的异常。5.1拜占庭将军问题第5章共识机制为在分布式系统中多节点故障的情况下达成一致，产生了分布式系统共识算法的需求。1985年，迈克尔

菲舍尔（MichaelJ.Fischer）、南希

林奇（NancyA.Lynch）和迈克尔

帕特森（MichaelS.Patterson）三人发表了1篇论文，提出了重要的分布式理论——FLP不可能性定理。FLP不可能性定理指出在允许节点失效的分布式系统中，不存在一个可以解决一致性问题的确定性算法，但其定义了分布式系统达成一致的算法上限。5.1拜占庭将军问题第5章共识机制共识机制的基础源于图灵奖得主莱斯利﹒兰伯特（LeslieLamport）1982年提出的拜占庭将军问题。问题大意是：拜占庭帝国（位于现土耳其的伊斯坦布尔，是强大的东罗马帝国的首都）由于国土辽阔，多支军队驻扎在相距较远的地方，军队的将军们只能通过信使相互沟通。发生战争时，拜占庭多支军队的将军们必须达成一致，制订一个共同的行动计划，决定作战与否等问题。但是一些将军可能是叛徒，他们为了达到自身利益而发送错误信息干扰别人，而那些忠诚的将军如何在知道有叛徒的情况下达成一致。拜占庭将军问题的提出，为解决分布式系统环境下的一致性问题提供了思路。经典共识机制PART025.2.1Paxos和Raft第5章共识机制1.Paxos算法1990年，莱斯利﹒兰伯特提出了Paxos算法。算法使用两阶段提交模型，基于消息传递且具有高度容错特性，提议-批准的思想被很多共识机制采用。5.2.1Paxos和Raft第5章共识机制1.Paxos算法Paxos算法包含3个角色，功能具体如下。（1）申请人（Proposer）：Proposer提出建议，希望更新状态。（2）接收人（Acceptor）：Acceptor批准提议请求。（3）学习者（Learner）：Learner相当于存储机器，被告知最终批准的提案，并且更新，不参与投票的过程。基本流程：申请人提出建议，如果超过一半的节点支持，将结果发送所有节点确认。Paxos算法要保证系统达到共识，必须有超过1/2的正常节点存在。5.2.1Paxos和Raft第5章共识机制2.Raft算法Raft是Paxos算法的简化与改进实现。Raft算法通过日志复制实现分布式系统的一致性，算法结构和Paxos不同。Raft更易理解和应用。5.2.1Paxos和Raft第5章共识机制2.Raft算法Raft算法将节点分为3种角色：领导者（Leader）、跟随者（Follower）和候选者（Candidate），角色间可以相互转换。（1）Leader：处理客户端请求，管理日志复制以及与Follower保持心跳信息，以维持其领导者地位。（2）Follower：响应Leader的日志复制请求，响应Candidate的选举请求，初始时所有节点均为Follower。（3）Candidate：发起选举投票，Raft启动后或Leader宕机后，一个节点从Follower转为Candidate，并发起选举，成功后，由Candidate转为Leader。5.2.1Paxos和Raft第5章共识机制2.Raft算法Raft算法基本流程：（1）Leader选举。Follower自增当前任期，转为Candidate，对自己投票，并发起投票申请，等待。结果有以下几种：

申请获得超过半数节点的投票，赢得选举，成为Leader；

其他节点赢得选举，并接收到对应的心跳，当前节点成为Follower；

选举超时，没有节点赢得选举，当前节点自增当前任期，重新选举。5.2.1Paxos和Raft第5章共识机制2.Raft算法Raft算法基本流程：（2）同步Log，并与Follower同步心跳。Leader接受客户端请求，更新日志，向所有Follower发送心跳信息，并同步日志。所有Follwer都有选举超时机制，如果在设定时间内没收到Leader的心跳信息，认为Leader失效，重新选举Leader。在Raft算法中，日志的流向只有Leader到Follower，并且Leader不能覆盖日志，日志不是最新者则不能成为Candidate。5.2.2BFT和PBFT第5章共识机制1.拜占庭容错（BFT）在拜占庭将军问题中，如果总节点数为n，恶意节点数为f，当n≥3f+1时，拜占庭将军问题有解决方法，即拜占庭容错（ByzantineFaultTolerant，BFT）算法。5.2.2BFT和PBFT第5章共识机制2.实用拜占庭容错（PBFT）1999年，米格尔﹒卡斯特罗（MiguelCastro）等对Paxos进行改进，提出了实用拜占庭容错（PracticalByzantineFaultTolerance，PBFT）共识算法。PBFT算法将BFT的计算复杂度由指数级降到了多项式级。PBFT算法基于状态机副本复制（StateMachineReplication）原理。核心思想是以一个主节点搜集全网交易，打包成区块，并对同一信息多次重复确认，从而达到全网共识。5.2.2BFT和PBFT第5章共识机制2.实用拜占庭容错（PBFT）（1）基本概念①Primary：主节点，由所有节点轮流担当，每个View选出一个新的Primary。②Replica：副本节点，提供“副本复制”服务。③Client：客户端，向Primary节点发起请求的节点。④View：视图，一个Primary节点和多个Replica节点形成一个View。⑤N：即SequenceNumber，由Primary给定的一个数字，即信息编号。⑥Checkpoint：如果N对应的信息收到超过2/3的确认，则称为一个Checkpoint状态。5.2.2BFT和PBFT第5章共识机制2.实用拜占庭容错（PBFT）（1）基本概念节点分为两种：主节点（Primary）：负责接收客户端发来的请求，并对这些请求排序，分配编号N，再向View中的副本节点广播；副本节点（Replica）：负责接收主节点和其他节点发来的消息，进行相应的验证，再执行对应的操作，最后将共识结果回复客户端。5.2.2BFT和PBFT第5章共识机制2.实用拜占庭容错（PBFT）（1）基本概念PBFT有3种协议：一致性（Agreement）协议、检查点（Checkpoint）协议及视图更换（ViewChange）协议。一致性协议确保来自客户端的每一次请求都能按照顺序执行，包含请求（Request）、预准备（Pre-Prepare）、准备（Prepare）、提交（Commit）和回复（Reply）五个阶段。5.2.2BFT和PBFT第5章共识机制2.实用拜占庭容错（PBFT）（1）基本概念PBFT有3种协议：在正常情况下，系统运行在一致性协议和检查点协议下。当主节点出错时，视图更换协议会启动，并依序将主节点用副本节点替换掉，保证系统有序执行客户端请求。在共识过程中，节点会随时记录日志。由于分布式系统无法保证每一个节点都执行了相同的请求，节点状态可能会不一致。因此，检查点协议会周期性执行，以处理日志和同步节点状态问题。5.2.2BFT和PBFT第5章共识机制2.实用拜占庭容错（PBFT）（1）基本概念PBFT是状态机副本复制算法。状态机在不同的节点复制副本。当前节点作为一个View，有一个节点是主节点，其他的节点为副本节点。主节点发生错误，以及每处理一个客户端请求后，View都会改变。在PBFT算法中，一个主节点领导的共识过程处于一个View之中，View是连续递增的整数。所有节点都可能被选为主节点，主节点通过View的编号以及节点数集合来确定。5.2.2BFT和PBFT第5章共识机制2.实用拜占庭容错（PBFT）（1）基本概念节点集合用R表示，每个节点可以编号为[0,…,|R|-1]，则|R|=3f+1，其中，f是发生故障的节点的最大个数，只要节点数不少于3f+1，实用拜占庭容错算法都可以正常运行。选取主节点：P=Vmod|R|，其中，P是主节点编号，V是视图号，当主节点失效或被副本节点推翻时，视图变更协议启动，将依照此公式选取新的主节点。5.2.2BFT和PBFT第5章共识机制2.实用拜占庭容错（PBFT）（2）PBFT算法流程PBFT算法流程包括5个阶段：

请求（Request）

预准备（Pre-Prepare）

准备（Prepare）

提交（Commit）

回复（Reply）5.2.2BFT和PBFT第5章共识机制2.实用拜占庭容错（PBFT）（2）PBFT算法流程PBFT算法流程包括5个阶段：

请求（Request）

预准备（Pre-Prepare）

准备（Prepare）

提交（Commit）

回复（Reply）图5-1PBFT算法流程5.2.2BFT和PBFT第5章共识机制2.实用拜占庭容错（PBFT）（2）PBFT算法流程①Request客户端C向主节点P发送请求信息m，格式为<Request，o，t，c>。o：请求执行的具体操作；t：请求时客户端添加的时间戳，以保证请求的唯一性；c：客户端标识。Request：包含信息内容m，以及信息摘要D(m)。客户端对请求进行签名。5.2.2BFT和PBFT第5章共识机制2.实用拜占庭容错（PBFT）（2）PBFT算法流程②Pre-Prepare主节点P收到客户端C的请求m。首先验证签名是否正确，若正确，则为信息m分配一个编号N，编号N用于对客户端请求进行排序，然后向所有副本节点广播一条<<Pre-Prepare,V,N,D>,m>预准备信息。其中，V为视图编号；D为消息摘要；m为客户端信息。预准备信息需要主节点签名，N在一个区间[h，H]内。5.2.2BFT和PBFT第5章共识机制2.实用拜占庭容错（PBFT）（2）PBFT算法流程③Prepare副本节点收到主节点的Pre-Prepare信息后，验证：主节点Pre-Prepare信息签名是否正确、当前副本节点是否收过同一视图（View）且编号为N但签名不同的Pre-Prepare信息、消息摘要是否一致、N∈[h,H]。若通过，副本节点向所有节点广播一条Prepare信息，格式为<Prepare,V,N,D,i>,V,N,D的含义与Pre-Prepare信息相同，i是当前副本节点编号。副本节点i对Prepare信息签名，将Pre-Prepare和Prepare信息写入Log中。5.2.2BFT和PBFT第5章共识机制2.实用拜占庭容错（PBFT）（2）PBFT算法流程④Commit节点完成Prepare后，进入Commit阶段。主、副节点收到Prepare信息后，验证：副本节点Prepare信息签名是否正确、当前副本节点是否已接收到同一View下编号为N的信息、D是否和当前已接收Pre-Prepare中的D相同、N∈[h,H]。若通过，如果副本节点i收到了2f+1个验证通过的Prepare信息，则向所有节点广播一条提交信息，格式为<Commit,V,N,D,i>，V,N,D,i的含义与上述Prepare信息相同。副本节点i对<Commit,i>进行签名。将Commit信息写入Log中。5.2.2BFT和PBFT第5章共识机制2.实用拜占庭容错（PBFT）（2）PBFT算法流程⑤Reply主、副节点收到Commit信息，验证：副本节点Commit的信息签名是否正确、当前副本节点是否已经接收同一View下编号为N的信息、消息摘要是否一致、N∈[h,H]。若通过，如副本节点i收到了2f+1个验证通过的Commit信息，说明达成共识，运行客户端的请求操作o，并回复信息给客户端，格式为<Reply,V,t,c,i,r>，r是请求结果，客户端如收到f+1个相同的Reply消息，证明客户端发起的请求已达成共识，否则客户端需要判断是否重新发送请求给主节点。5.2.2BFT和PBFT第5章共识机制2.实用拜占庭容错（PBFT）（3）特点PBFT机制的特点是共识快、出块快。适合于节点数量不多的联盟链和私有链。PBFT在联盟链中使用较多。5.2.3工作量证明第5章共识机制比特币的共识机制是工作量证明（ProofofWork，PoW）。PoW共识过程实际就是求解数学题的过程。节点基于自身的计算能力求解一个计算复杂但验证容易的数学题，最快得出结果的节点证明自身工作量最大。计算过程只能通过遍历随机数重复计算获得，节点求解随机数的快慢与其计算能力相关，因此相当于通过计算速度判断计算能力，从而证明工作量强度。5.2.3工作量证明第5章共识机制1.算法表述Input:preHash,txs,DOutput:Block1:nNonce←12:while(H(preHash,txs,nNonce)＞D):3:nNonce←nNonce+14:broadcast(＜preHash,txs,nNonce＞)5:end5.2.3工作量证明第5章共识机制2.共识流程（1）新交易广播系统中产生的每一笔新交易都会向全网广播，每一个节点都将收到的交易信息写入一个新区块中。（2）构造Merkle树节点根据收到的所有有效交易构造Merkle树。5.2.3工作量证明第5章共识机制2.共识流程（3）选举记录节点，并生成区块节点在区块头中添加一个随机数nNonce，通过穷举法找到一个nNonce的值，使Hash(Hash(nVersion+hashPrevBlock+hashMerkleRoot+nTime+nBits+nNonce))≤Target，最先求解nNonce的节点成为记录节点，构造区块并广播。Target表示目标难度，目标难度每隔一定的时间调整一次，使出块时间恒定。5.2.3工作量证明第5章共识机制3.优缺点优点：去中心化系统中达成共识。缺点：

资源浪费；

交易确认时间过长；

算力需求会产生联合挖矿联盟（矿池），对去中心化形成威胁。5.2.4权益证明第5章共识机制2011年，昆腾

梅凯尼克（QuantumMechanic）提出权益证明（ProofofStake，PoS）共识机制，并在点点币（Peercoin）中得以实现。PoS由系统中具有最高权益的节点获得记账权。权益体现为节点对特定数量货币的所有权，称为币龄或币天数（Coindays）。币龄是拥有的货币数量乘以拥有时间段，即Coinage=Coins

Age。5.2.4权益证明第5章共识机制1.算法表述Input:preHash,txs,D,accountBalance,lastTransactionTimeOutput:Block1:nNonce←12:coins←accountBalance3:age←currentTime-lastTransactionTime4:while(H(preHash,txs,nNonce)＞Coins*Age*D):5:nNonce←nNonce+16:broadcast(＜preHash,txs,nNonce＞)7:end5.2.4权益证明第5章共识机制2.共识流程（1）选举记录节点用户质押持有的代币获取币龄，挖矿需满足不等式：Hash≤Coinage

Target。Hash表示区块哈希值，Coinage为币龄，Target为目标值。（2）生成区块记录节点收集系统中的所有有效交易打包进区块，然后在系统内广播新区块。（3）验证区块并更新区块链验证节点对新区块进行验证，若验证成功，则将其添加到区块链末端，更新区块链，开启下一轮共识；否则直接将其丢弃，并重新选举记录节点。5.2.4权益证明第5章共识机制3.优缺点（1）优点一定程度上解决了PoW共识机制算力浪费的问题（2）缺点可能会导致某些账户的权利很大；会造成严重的贫富不均；对新节点不够友好。5.2.5委托权益证明第5章共识机制委托权益证明（DelegatedProofofStake，DPoS）共识机制是对PoS的改进。由比特股（Bitshares）项目提出。DPoS核心思想是系统中持有权益的节点投票选举代表，获得票数最多且愿意的前N个节点将成为代表，再由这些选举出的代表轮流承担区块记账权、生成新区块。管理思路类似“董事会”制度。5.2.5委托权益证明第5章共识机制1.见证人制度代表是DPoS机制的重要角色。每个节点可将自己持有的权益转化为选票，选举信任的节点当代表。权益越多，选票权重越高。获得选票最多的前N个节点当选为代表（也称见证人，Witnesses）。见证人的名单每经过一个固定周期都将重新选举更换一次。节点选取见证人时，可根据见证人出块的错误率来实现正确的选择，如果见证人的在线率比较低，会影响其下一次被选举。网络中见证人数量不足时，可通过投票选出一组新的见证人。见证人有生产区块的权利，负责对交易进行见证，并验证交易的签名和时间戳。5.2.5委托权益证明第5章共识机制2.区块生成见证人负责区块的生成和验证。在规定时间内，见证人随机排列并按照顺序轮流产生区块。每经过一轮出块，系统都将对出块顺序进行重新整合。生成的区块超过51%的权益投票通过，则认为区块生成成功。当见证人生成区块出错时，只要未得到51%的权益投票通过认可，那么该区块将会在下一个时间段由其他的见证人生成。见证人每生成一个区块，将从区块的交易中获得一定的交易手续费。5.2.5委托权益证明第5章共识机制2.区块生成在DPoS共识机制中，链接规则仍然是最长链。新区块链接到最长链上，其他见证人验证区块。当发生网络故障时，可能会出现链分叉的情况。网络连通后，诚实节点看到一个最长的有效链，会从当前分叉切换到最长链。5.2.5委托权益证明第5章共识机制3.DPoS共识流程共识过程分为见证人选举、见证人出块、区块验证三个阶段。（1）选举见证人权益持有节点投票选举见证人，见证人每24小时更新一次，需要100%在线。例如，Bitshares（比特股）可以有任意数量的见证人；EOS（EnterpriseOperationSystem）每轮见证人的数量设置为21，票数最多的前20人自动当选见证人，剩余1人随机选出。5.2.5委托权益证明第5章共识机制3.DPoS共识流程共识过程分为见证人选举、见证人出块、区块验证三个阶段。（2）生成区块见证人生成区块并对区块签名、添加时间戳，将新区块广播到系统中。如果见证人在规定时间段内没有生成区块，则该时间段将被跳过，生成区块的权力交给下一轮的见证人。Bitshares每2秒产生一个区块；EOS每3秒产生一个区块。5.2.5委托权益证明第5章共识机制3.DPoS共识流程共识过程分为见证人选举、见证人出块、区块验证三个阶段。（3）区块验证其他见证人负责验证新产生区块的合法性，并将之链接到最长有效链。Bitshare中投票权益超过51%就可上链；EOS中半数以上的见证人验证通过就可上链。5.2.5委托权益证明第5章共识机制4.优缺点达成共识速度快于PoW和PoS，效率更高。DPoS共识机制能够实现秒级验证。对系统的任何更改都需要大于51%权益者的同意。参与度不够，见证人会集中在全网持有大量选票的节点，或将失去去中心化特性。5.2.6瑞波协议第5章共识机制2014年，大卫

施瓦茨（DavidSchwartz）等提出瑞波协议共识算法（RippleProtocolConsensusAlgorithm，RPCA）。瑞波共识机制类似董事会，要增加新成员，必须有51%以上成员投票通过。RPCA将失效节点数量控制在1/5以内，可以在秒级达成共识，解决了高延迟问题，在只需最小化信任和最小连通性的网络环境中实现了低延迟、高鲁棒性的分布式节点共识。RPCA共识机制是Ripple协议的支撑技术，效率高，是共识机制的技术突破。共识机制分类及改进PART035.3.1共识机制分类第5章共识机制

根据共识算法容错类型的不同，分为：非拜占庭容错（CrashFaultTolerance，CFT）类；拜占庭容错（ByzantineFaulttolerant，BFT）类。主流的CFT共识算法主要有Paxos和Raft共识算法；BFT类主要有PoW、PoS、DPoS、PBFT、dBFT及RPCA等。

根据区块链共识机制的技术路线及研究方向，分为：单一共识机制及其改进；混合共识机制；其他共识机制。5.3.2共识机制改进第5章共识机制1.PoW/PoS及其改进PoW或PoS的本质都是全网节点竞争记账权，对区块链的性能有极大影响。基于PoW的改进算法分为：链上拓展式的改进PoW共识机制，包括Bitcoin-NG、Byzcoin、GHOST等；链下拓展式的改进PoW共识算法，包括闪电网络、分片共识技术等。5.3.2共识机制改进第5章共识机制1.PoW/PoS及其改进Bitcoin-NG改进了区块结构，分为关键区块和微区块，系统每10分钟产生一个关键区块，每10秒产生一个微区块。挖矿可以在关键区块上进行，也可以在微区块上进行。Bitcoin-NG将记账权的选举和交易确认分成两步。首先，节点通过PoW机制竞争记账权，获得记账权的节点，通过产生微区块来确认交易，直到下一个记录节点产生。Bitcoin-NG算法利用两个节点记账的间隙产生多个包含交易的微区块，实现交易确认，提高了每轮共识中的交易确认数量。5.3.2共识机制改进第5章共识机制1.PoW/PoS及其改进Conflux共识算法也是一种链上拓展式的共识机制，基于PoW和有向无环图（DirectedAcyclicGraph，DAG）实现。设计思想是在不放弃所有分叉的前提下，在区块生成阶段仍然采用PoW共识机制，然后用DAG图对区块排序。Conflux共识算法的交易处理能力达到6400笔/s。5.3.2共识机制改进第5章共识机制1.PoW/PoS及其改进区块链共识算法（ProofofWorkandStake，PoWaS）基于PoW和PoS改进。PoWaS在以下方面有所改进：（1）降低难度值。通过降低难度并限制最大难度值节省算力。（2）设置币龄上限。设置了有效持币时间和币龄上限，防止币龄无限增长而带来的富者恒富的问题。（3）引入信用值。引入信用值，为节点赋予可以升降的信用度量。（4）引入pStake值。通过计算随机数花费时长、币龄和信用值得到一个pStake值，pStake值最大的节点获得记账权。5.3.2共识机制改进第5章共识机制1.PoW/PoS及其改进行动证明（ProofofActivity，PoAc）机制结合了PoW和PoS的优势。该机制的基本流程类似PoW，节点完成工作量证明后构造一个符合难度要求的区块头部，将头部发送给其他校验节点进行校验。校验节点的选取与权益相关，由最后一个校验节点将交易数据加入区块中，并发布区块，完成区块的生成。5.3.2共识机制改进第5章共识机制1.PoW/PoS及其改进以上各种基于PoW或PoS改进的共识算法，本质上都是全网节点参与记账权竞争的方式，并未改善系统中存在的交易吞吐量低、系统可扩展性不足的问题。5.3.2共识机制改进第5章共识机制2.PBFT及其改进基于Gossip协议的拜占庭共识算法（Gossipprotocol-basedByzantineConsensusalgorithm，GBC）在提高系统容错性、系统扩展性、系统稳定性等方面具有一定优势。基于投票机制的拜占庭容错（VotingPracticalByzantineFaultTolerance，VPBFT）共识算法较好地解决了区块链中现有的PBFT共识机制、基于动态授权的拜占庭容错（DynamicauthorizedByzantineFaultTolerance，DDBFT）共识机制及联盟拜占庭容错（ConsortiumByzantineFaultTolerance，CBFT）共识机制中普遍存在的高耗能、低效率等问题。5.3.2共识机制改进第5章共识机制3.基于密码学的共识机制基于密码学的共识算法，如：采用聚合签名降低通信复杂度的Byzcoin；采用可验证随机函数（VerifiableRandomFunction，VRF)的Algorand；利用门限签名实现异步共识的HoneyBadgerBFT。5.3.2共识机制改进第5章共识机制3.基于密码学的共识机制Algorand算法通过密码学的方法确定下一个区块的生产者，降低了链分叉的概率。Algorand由于扩展性较好、链分叉概率低而在公有链中使用。H-Algorand机制是在多块Algorand（Mult