区块链原理与实践- 课件 第4章共识层

第4章共识层课程简介01.分布式一致性问题03.CFT类型算法详解02.共识算法概述04.BFT类算法05.新型区块链共识算法07.共识算法演进06.目前共识机制存在的问题08.思考与练习1分布式一致性问题一分布式一致性问题分布式系统的特性：①资源受限：节点间的通信需要通过网络，而网络存在带宽限制和时延，节点也无法做到瞬间响应和高吞吐。②故障的独立性：系统的任何一个模块都可能发生故障，如节点之间的网络通讯是不可靠的，随时可能发生网络故障或任意延迟；节点的处理可能是错误的，甚至节点自身随时可能宕机。③不透明性：构成分布式系统中任意节点在任意时刻的位置、性能、状态、是否故障等信息对于其它分布式系统节点来说都是不可见的、也是无法预知的。④并发：分布式系统的目的是为了更好的共享资源，允许并发的访问资源才能体现分布式系统的意义。⑤缺乏全局时钟：当多个程序协作时需要通过交换消息来协同彼此的动作，而紧密的协调经常要求这些程序对一系列动作发生时间的共识。然而，由于网络状况的复杂性，分布式系统中的节点对网络中同步时钟的准确性是很难达成共识的，即没有一个一致的全局时间的概念。一分布式一致性问题故障类型节点故障：

崩溃故障（故障停止、崩溃、故障恢复）信道故障：

遗漏故障（发送故障、信道故障、接收故障）时序故障（针对同步系统）：

崩溃故障（时钟故障（时钟漂移）、节点性能故障(进程执行)、信道性能故障（消息传递））拜占庭故障：随机故障（恶意、错误）一分布式一致性问题1.FLP不可能定理

异步系统中，不存在协议能够保证所有进程达成一致。

目前已经证明同步通信中各节点保证一致性是可以达到的，但利用算法解决异步环境的一致性问题依然十分困难。即在网络可靠，存在节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性算法。一分布式一致性问题2.CAP定理CAP定理即描述了分布式系统中关于一致性和可用性的关系：一个分布式系统最多只能同时满足（强）一致性（Consistency）、可用性（Availability）和分区容错性（基本要求）（Partitiontolerance）这三项要素中的两项。一分布式一致性问题3.BASE理论BASE理论是由三个词组组成：①BasicallyAvailable：即基本可用性，如对于存储系统来说，需要保证存取服务在大多数情况下是可用的。②SoftState：柔性状态，指为了得到更好的扩展性，是允许中间状态可见的，如NoSQL、MySQL集群的异步模型的数据复制过程。③EventualConsistency：最终一致性，也是分布式一致性模型中的一种弱一致性模型。要求停止往系统中写入数据后，过一段时间，所有节点拥有了同一份数据副本。4.拜占庭将军问题在分布式对等网络中需要遵从一致的策略来协作的成员计算机即为问题中的将军，而各成员计算机赖以进行通讯的网络链路即为信使。拜占庭将军问题描述的就是某些成员计算机或网络链路出现错误、甚至被蓄意破坏者控制的情况下成员之间存在的一致性问题。一分布式一致性问题5.区块链中的DSS猜想：DSS猜想是指，在区块链系统中，去中心化（Decentralization），安全性（Security）和可扩展性（Scalability）这三个属性，系统最多只能三选其二。1共识算法概述二共识算法概述共识算法性质：共识算法是能使网络中的各非错误节点对于交易的顺序达成共识，并总能在规定时间内对外提供输出的算法，并且要求共识算法能保持在系统在不存在全球统一的时钟、各节点可能独立出错以及网络中传送的消息并不总是可靠这三个条件下依然正常可靠的工作。尽管算法多种多样，可以根据需要采用各种策略，但大家公认的理想的共识算法应该满足的条件包括：①可终止性（Termination）：一致的结果在有限时间内能完成。②共识性（Consensus）：不同节点最终完成决策的结果应该相同。③合法性（Validity）：决策的结果必然是其它进程提出的提案。二共识算法概述共识算法分类：共识算法可以分为CFT（CrashFaultTolerance）类和BFT（ByzantineFaultTolerance）类共识算法。CFT共识算法只保证分布式系统中节点发生宕机错误时整个分布式系统的可靠性，而当系统中节点违反共识协议的时候将无法保障分布式系统的可靠性.采用BFT共识算法的分布式系统，即使系统中的节点发生了任意类型的错误，只要发生错误的节点少于一定比例，整个系统的可靠性就可以保证。二共识算法概述共识算法评价标准：①共识算法的容错性能，比如Raft只能支持节点故障错误。而在区块链中，特别公有链中，由于节点间存在利益博弈，同时又是一个非中心化的网络状态，其共识算法必须支持节点作恶的容错，所以区块链的共识算法必然是BFT算法。②共识算法终局性性能，指区块链网络对一个候选区块完成终局一致性所需要的时间，这决定了区块链系统的响应时间，对于面向用户的去中心化应用是非常重要的参数。③共识算法扩展性，指随着区块链网络节点数目与共识算法性能的相关关系，比如PBFT算法随着节点数目增加，完成一轮共识需要在网络中传播的消息数目呈平方比例增加，因此PBFT算法的天然特性无法支持大规模网络。④共识算法的网络模型性能对其容错性能和终局性能都有很大的影响。在区块链大规模网络条件下，同步共识算法要求所有节点在规定时间内响应对其他节点的消息，否则将被认为是故障节点，因此受网络波动影响较大，从而进一步导致算法容错性能的降低；而由于FLP不可能定理，异步共识算法无法给出确定的终局性性能，所以当前主流区块链共识算法都是基于半同步模型。3CFT类型算法详解三CFT类型算法详解Paxos算法：Paxos算法是一种基于消息传递且具有高度容错特性的一致性算法。Paxos算法的前提假设是不存在拜占庭将军问题，即发出的信号不会被篡改，因为Paxos算法是基于消息传递的。解决的问题就是在以上分布式环境下实现“多个进程对某个变量的取值达成一致”。Paxos算法适用于异步网络和非拜占庭的崩溃重启（Crash-Recover）失效模型，它们具有如下特点：①首先进程能够按照程序逻辑执行，并返回正确结果（不会是拜占庭式的任意错误）；②进程处理事件的速度不可预测，甚至会崩溃（Crash）；③进程崩溃之后能够重启，并接着之前的状态继续提供服务；④进程可以访问一个不受崩溃影响的持久化存储（即日志可以保存下来）；⑤消息传送速度同样不可预测，消息可能被丢失，也可能被重发，但内容不会损坏或篡改。三CFT类型算法详解Paxos算法流程：Paxos将系统中的角色分为提议者(Proposer)，决策者(Acceptor)，和最终决策学习者(Learner)，其中：①Proposer:提出提案(Proposal)。Proposal信息包括提案编号(ProposalID)和提议的值(Value)。②Acceptor：参与决策，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数Acceptors的接受，则称该Proposal被批准。③Learner：不参与决策，从Proposers/Acceptors学习最新达成一致的提案（Value）。Paxos有两种类型，一种是Single-DecreePaxos，负责决策单个Value；另一种是Multi-Paxos，负责连续决策多个Value并且保证每个节点上的顺序完全一致。下面介绍简单的只决策一个value的Paxos算法。三CFT类型算法详解Paxos算法流程：阶段一（prepare阶段）：①Proposer选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求Pareper（N）；②如果一个Acceptor收到一个编号为N的Prepare请求，如果小于它已经响应过的请求，则拒绝，不回应或回复error。若N大于该Acceptor已经响应过的所有Prepare请求的编号（maxN），那么它就会将它已经接受过（已经经过第二阶段accept的提案）的编号最大的提案作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。阶段二（accept阶段）：①如果一个Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么它就会发送一个针对[N，V]提案的Accept请求给半数以上的Acceptor。注意：V就是收到的响应中编号最大的提案的value（某个acceptor响应的它已经通过的{acceptN，acceptV}），如果响应中不包含任何提案，那么V就由Proposer自己决定。②如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接受该提案。如果N小于Acceptor之前响应的prepare请求，则拒绝，不回应或回复error，当proposer没有收到过半的回应，那么他会重新进入第一阶段，递增提案号，重新提出prepare请求。三CFT类型算法详解在Paxos算法中，采用了“过半”理念，也就是少数服从多数，这使Paxos算法具有很好的容错性。Paxos是基于消息传递的具有高度容错性的分布式一致性算法。Paxos算法引入了过半的概念使算法具有了很好的容错性，另外Paxos算法支持分布式节点角色之间的轮换，这极大避免了分布式单点的出现，因此Paxos算法既解决了无限等待问题，也解决了脑裂问题，是目前来说最优秀的分布式一致性算法。三CFT类型算法详解Raft算法：

Raft是一个用于日志复制、同步的一致性算法。它与Paxos的算法结构不同，这使得Raft相比Paxos更好理解，并且更容易构建实际的系统。为了强调可理解性，Raft将一致性算法分解为选主、日志复制和安全三个大模块。Raft算法也具有如下特征：①强leader语义：相比其他一致性算法，Raft使用增强形式的leader语义。举个例子，日志只能由leader复制给其它节点。这简化了日志复制需要的管理工作，使得Raft易于理解。②leader选择：Raft使用随机计时器来选择leader，它的实现只是在任何一致性算法中都必须实现的心跳机制上多做了一点工作，不会增加延迟和复杂性。③动态扩容：Raft使用了一个称为联合共识（jointconsensus）的新机制允许集群动态在线扩容，保障Raft的可持续服务能力。三CFT类型算法详解在Raft协议中，任何一个节点任一时刻处于以下三个状态之一：leader、follower、candidate。三CFT类型算法详解Raft将时间分解成任意长度的时间段，这里称作terms，如下图所示：

三CFT类型算法详解Raft的三个主要模块的具体工作流程详述如下：

①leader选举流程 Raft使用心跳机制来触发选举。当server启动时，初始状态都是follower。每一个server都有一个定时器，超时时间为electiontimeout，如果某server没有超时的情况下收到来自leader或者candidate的任何RPC，定时器重启，如果超时，它就开始一次选举。如果某个candidate获得了大多数人的选票，它就赢得了选举成为新leader。每个server在某个term周期内只能给最多一个人投票，按照先来先给的原则。新leader要给其他人发送心跳，阻止新选举。 在等待选票过程中，一个candidate，假设为A，可能收到它人的声称自己是leader的AppendEntriesRPC，如果对方的term号大于等于A的，那么A承认对方是leader，自己重新变成follower，否则，A拒绝该RPC，继续保持candidate状态。 在leader选举过程中还有第三种可能性就是candidate既没选举成功也没选举失败。如果多个followers同时成为candidate去拉选票，导致选票分散，任何candidate都没拿到大多数选票，这种情况下Raft使用超时机制来解决。三CFT类型算法详解②日志复制流程

一旦选举出了一个leader，它就开始负责服务客户端的请求。每个客户端的请求都包含一个要被复制状态机执行的指令。leader首先要把这个指令追加到日志中形成一个新的记录，然后通过AppendEntriesRPCs并行的把该记录发给其他servers，其他server如果发现没问题，复制成功后会给leader一个表示成功的ACK，leader收到大多数ACK后应用该日志，返回客户端执行结果。如果followers崩溃或者丢包，leader会不断重试AppendEntriesRPC。Logs按照下图组织：三CFT类型算法详解在正常情形下，leader和follower的日志肯定是一致的，所以AppendEntries一致性检查从不失败。然而，如果leader崩溃，那么它们的日志很可能出现不一致。这种不一致会随着leader或者followers的崩溃变得非常复杂。下图展示了所有日志不一致的情形：三CFT类型算法详解③安全性Raft选主和进行日志复制的操作还不足以保证不同节点能执行严格一致的指令序列，需要额外的一些安全机制。Raft的安全机制包括以下三种：选举限制提交早期terms的entries一个leader不能也认为一个早于当前term的entry如果存在大多数节点，那么也是可以commit的。下图展示了这样一种状况，一个老的log存储在大多数节点上，但是仍有可能被新leader覆盖掉，如下如所示：三CFT类型算法详解调解过期leader为了在任何异常情况下系统不出错，即满足safety属性，对leaderelection，logreplication两个子问题有诸多约束。其中leaderelection约束包括：同一任期内最多只能投一票，先来先得;选举人必须比自己知道的更多（比较term，logindex）logreplication约束；一个log被复制到大多数节点后即被确认，保证不会回滚；leader一定包含最新的committedlog，因此leader只会追加日志，不会删除覆盖日志;不同节点，某个位置上日志相同，那么这个位置之前的所有日志一定是相同的。4BFT类算法四BFT类算法

BFT类算法是可以允许拜占庭错误的一致性算法，这类算法也是在区块链系统中常用的共识算法。根据算法采取的策略，BFT类算法可以被分为两大类，即概率一致性算法和绝对一致性算法：概率一致性算法指在不同分布式节点之间，有较大概率保证节点间数据达到一致，但仍存在一定概率使得某些节点间数据不一致。对于某一个数据点而言，数据在节点间不一致的概率会随时间的推移逐渐降低至趋近于零，从而最终达到一致性。例如工作量证明算法（ProofofWork，PoW）、权益证明算法（ProofofStake，PoS）和委托权益证明算法（DelegatedProofofStake，DPoS）都属于概率一致性算法。绝对一致性算法指在任意时间点，一旦达成对某个结果的共识就不可逆转，即共识是最终结果，节点之间的数据会保持绝对一致。以PBFT算法为代表的确定性系列算法即为绝对一致性算法。四BFT类算法

POW算法

工作量证明（ProofofWork，POW）算法起源于哈希现金（HASHCASH），最初被用于抵抗电子邮件的拒绝服务攻击及垃圾邮件网关滥用。

PoW共识机制是一种简单粗暴的共识算法，它不要求高质量的P2P网络资源，它可以为公链提供稳定有效的记账者筛选机制。同时它也面临了挖矿中心化严重的问题，这也促使人们研究出了新的共识机制。

中本聪共识有四个组成部分：工作量证明、选择出块人、时间戳服务器以及激励机制。通过这些机制，只要网络上算力的50%以上没有协同起来去攻击网络，那么共识就是可以达成的。四BFT类算法

POW算法工作流程

四BFT类算法

POW算法优缺点PoW优点：①完全去中心化；②节点自由进出；③算法容易实现以及破坏系统花费的成本巨大。PoW缺点：①对节点的性能和网络环境要求高；②资源浪费，效率低下；③矿场的出现违背了去中心的初衷;④不能确保最终一致性；⑤大量矿工因收益降低离开网络可能导致网络瘫痪。 四BFT类算法

POS算法

权益证明机制（ProofofStake，POS）于2012年被首次提出，是针对工作量证明机制存在的不足而设计出来的一种改进型共识机制。权益证明机制的原理是：要求用户证明自己拥有一定数量的数字货币的所有权，即“权益”。

POS中最重要的一个概念是币龄，币龄定义为交易的货币数量乘以该货币在钱包中储存的时间。通俗来讲，比如你有100个币，在某个地址上9天没有动，那么产生的币龄就是900，如果你把这个地址上这100币转移到任意地址，包括你自己的地址，那么900个币龄就在转移过程中被花费了，你的币数量虽然还是100个，但是币龄变更为0。币龄在数据链上就可以取到，任何人都可以验证。区块链共识机制的第一步就是随机筛选一个记账者，PoW是通过计算能力来获得记账权，计算能力越强，获得记账权的概率越大。PoS则将此处的计算能力更换为财产证明，就是节点所拥有的币龄越多，获得的记账的概率就越大。这有点像公司的股权结构，股权占比大的合伙人话语权越重。四BFT类算法

POS算法工作流程

四BFT类算法

POS的实例Csaper协议Csaper协议为了解决因无成本利益挖矿问题，从而导致分叉。Csaper的具体实现机制如下：①验证者押下一定比例的他们拥有的以太币作为保证金；②然后，他们将开始验证区块。也就是说，当他们发现一个可以他们认为可以被加到链上的区块的时候，他们将以通过押下赌注来验证它；③如果该区块被加到链上，然后验证者们将得到一个跟他们的赌注成比例的奖励；④但是，如果一个验证者采用一种恶意的方式行动、试图做“无利害关系”的事，他们将立即遭到惩罚，他们所有的权益都会被砍掉。四BFT类算法

DPoS算法

委托权益证明(DelegatedProofofStake，DPOS)是一个强大而灵活且具备高鲁棒性的共识协议。DPOS利用利益相关方批准投票的权力以公平和民主的方式解决共识问题。DPoS机制遵从如下几条基本原则：①持股人依据所持股份行使表决权，而不是依赖挖矿竞争记账权；②最大化持股人的盈利。③最小化维护网络安全的费用。④最大化网络的效能。⑤最小化运行网络的成本，如带宽、CPU等。四BFT类算法

DPOS算法优缺点①DPoS机制相比于PoS大幅缩小参与验证和记账节点的数量，可以达到秒级的共识验证；②在一定程度上解决拒绝服务攻击和潜在作恶节点联合作恶问题；③但是，DPoS机制还是依赖于代币，然而很多商业应用是不需要代币存在的；④另外，DPoS并没有解决首富作恶的问题。 四BFT类算法

实用拜占庭容错协议在借鉴了分布式系统的状态机复制和分布式一致算法quorum的基础上设计了三阶段协议来解决一致性问题，同时引入了优化项，算法的复杂度由原来的指数级降低为多项式级别。PBFT算法本质上是一个状态机复制算法，能够用于实现带有状态和特定操作的任意确定性状态复制服务，它的目的是让所有的可信节点执行相同的序列。此外，PBFT算法使用安全的哈希函数对消息做摘要、使用公私钥对消息进行签名和验签、同时增加了消息验证码，保证了消息的完整性和不可篡改性。在作恶节点总数不超过系统节点总数的1/3的情况下，PBFT算法能够保证系统的安全性和活性。PBFT算法主要包含三类基本协议：①三阶段协议：解决如何达成共识；②检查点协议：类似于操作系统的还原点，主要用于垃圾回收；③视图变更协议：用于解决主节点失效下不工作的情况。

四BFT类算法

三阶段协议三阶段协议是PBFT算法的核心流程，用于解决系统的一致性问题，保证所有可信节点在给定状态和参数组的条件下，按照相同的顺序执行完请求后能够取得相同的状态。pre-prepare阶段：四BFT类算法

三阶段协议prepare阶段：四BFT类算法

三阶段协议commit阶段：四BFT类算法

检查点协议PBFT通过三阶段协议来对请求达成共识，但是各个阶段产生的消息如果不进行垃圾回收的话，系统的存储资源将会不堪重负。为此，PBFT算法设计了检查点协议来丢弃本地的消息日志文件中的旧消息。四BFT类算法

视图变更协议PBFT算法可以通过视图变更协议来允许系统在主节点出故障的情况下仍能够正常运转，从而保证了系统的活性。视图变更协议实际上是通过超时机制触发的，通过超时机制可以避免主节点不工作时副节点无限期等待客户端请求被执行的情况。a.维持计时器：副节点会针对视图v维持一个计时器。当在收到主节点发送过来的一个有效的请求而且没有执行的时候，如果是针对当前视图的计时器还没有启动的话，那么节点会启动一个新的计时器。如果节点还在执行其他请求的话，那么节点会重置该请求的计时器。如果节点不再等待执行该请求的时候，会停止视图v的计时器。四BFT类算法

视图变更协议b.请求视图变更四BFT类算法

视图变更协议c.切换到新视图5新型区块链共识算法五新型区块链共识算法

Algorand算法针对BFT算法在区块链的去中心化、可扩展性和安全存在的问题，Algorand算法被提出。下面我们来说说Algorand算法的几个特点：①为了避免委员会暴露之后被攻击者攻击，Algorand要求所有委员会节点在这一轮投票完便失效，下一轮的委员会成员会重新选择。②这个权重还决定了节点被当选为委员会成员的概率，权重越大的节点，其被选中的概率越大。五新型区块链共识算法

Algorand算法交易流程五新型区块链共识算法

DAG共识DAG算法可以细分为两类：一个是将区块组织成DAG，如conflux共识；另外一个是不保留区块的概念，而是直接将交易组织成DAG，如物联网区块链平台IOTA的tangle算法。DAG共识的一个难点是如何对区块或者交易进行排序，下面我们会分别介绍基于交易和区块的DAG共识机制是如何解决交易排序的问题的。五新型区块链共识算法

DAG区块共识Conflux共识是DAG共识的一种，它们都是将区块组织成有向无环图DAG，都是基于比特币共识来解决POW问题来产生区块的。五新型区块链共识算法

DAG交易共识Tangle是应用于物联网IOT的共识算法，目的是想解决传统的区块链中需要交易手续费问题，因为IOT世界中发生的大多数是小额支付，如果直接采用以比特币为代表的区块链解决方案的话，每笔小额支付交易的手续费明显高于交易的转账金额，那么这个明显是不合理的。但是去掉手续费的话，区块的产生就会出现问题，因为没有手续费，矿工创建区块就没有利益所得。五新型区块链共识算法

基于可信硬件的共识算法PoET（逝去时间证明）的工作机制如下：网络中的每位参与节点都必须等待一个随机选取的时期，首个完成设定等待时间的节点将获得一个新区块。区块链网络中的每个节点会生成一个随机的等待时间，并休眠一个设定的时间。最先醒来的节点，即具有最短等待时间的节点，唤醒并向区块链提交一个新区块，然后广播必要的信息到整个对等网络中。同一过程将会重复，以发现下一个区块。TrustZone在概念上将SoC的硬件和软件资源划分为安全（SecureWorld）和非安全（NormalWorld）两个世界，所有需要保密的操作在安全世界执行（如指纹识别、密码处理、数据加解密、安全认证等），其余操作在非安全世界执行（如用户操作系统、各种应用程序等），安全世界和非安全世界通过一个名为MonitorMode的模式进行转换，如图所示6目前共识机制存在的问题六目前共识机制存在的问题

1.安全性证明不完备共识机制在安全性建模时需要考虑网络时序性、节点数量拓展、在线离线切换、算力或权益的动态分布、共识难度变更、区块链增长速率等多变量因素。2.安全性假设不可靠现代密码体制的安全性评估依赖计算复杂性理论，常用可证明安全理论将密码体制的安全性归约到某个公开的数学困难问题上，如椭圆曲线上的离散对数问题。然而，采用PoW和PoS的共识机制的安全性假设并不依赖计算困难问题，而是依赖所有的诚实节点所拥有的算力或者权益占多数这类看似合理的假设。这些安全性假设在实际应用中很容易被打破。3.一致性不稳定如何保证共识机制可以持续稳定地实现一致性是目前共识层的研究重点。一致性是衡量共识机制安全性强弱的重要性质。这些合法交易的交易双方造成利益损失。六目前共识机制存在的问题

4.扩展性差可扩展性是区块链共识机制研究关注的重要属性，是区块链可用性必不可少的一部分。目前，如何提高区块链共识机制的可扩展性仍然是一个主流研究方向。5.初始化难问题大量研究关注共识机制实现一致性的过程，往往忽略了区块链的初始化问题，即如何在P2P网络中保证创世块的安全生成。区块链的初始化直接关系到后续共识机制的执行过程是否安全可靠，是保证共识机制稳定可靠的前提。区块链一直面临初始化困难的问题。6.重构困难问题共识机制赋予了区块链不可篡改性，提升了系统的可信度，但是也增加了