《区块链技术原理与实践》课件-3第3章共识算法

3共识算法如何设计去中心化交易的确认规则同济区块链研究院

0GUIDANCE引导部分区块链技术构架区块链技术构架根据共识机制，确认该区块的有效性现实生活的投票共识场景：共识算法：如何达成一致？共识算法：如何达成一致？这种筛选出最有代表性的人以及达成共识的机制，就是共识算法。目录CONTENTS01OVERVIEW概述02PROOF

OF

WORK工作量证明04DPOS股份授权证明机制03PROOF

OF

STAKE权益证明09ASSIGNMENT课后习题07课程总结06改进共识算法0508参考资料PBFTREVIEWREFERENCE实用拜占庭容错算法IMPROVEDCONSENSUSALGORITHM学习目标知识目标理解共识算法产生的原因和共识算法在区块链技术中的重要性；掌握“双花”问题、共识机制和常用共识算法的工作原理、实现步骤；熟悉共识算法的优缺点；了解改进共识算法的原理和实现方法；技能目标理解常用共识算法的代码；学习重点“双花”问题、拜占庭将军问题、PoW算法的工作原理学习难点PoW算法的工作原理

1OVERVIEW概述

3.1区块链要解决的问题1：双花问题50元50元只有50元小芳Coffee？Flower？Both？问题描述双花，也就是双重花费的意思，指同一笔钱花了两次甚至是多次。这是数字货币领域最大的难题。1解决方法如何解决数字货币重复使用这个问题？2应用价值保障交易安全33.1概述-双花问题拜占庭将军问题如何在使用不可靠通信并受到某些参与者故障或恶意威胁的情况下实现全局共识？拜占庭将军问题：研究成果问题描述将军发布进攻城堡的命令，有人撤退怎么办？采用何种策略确保部队之间行动的一致性?1解决方法所有忠诚的将军，可以达成命令行动的一致性。少数的叛徒不会导致忠诚的将军们无法达成一致性。2应用价值拜占庭问题最后取得的共识，最终目的不是为了胜利，而是为了行动的一致性。看似与区块链无关，触及到区块链网络设计核心：在成千上万节点共同运作，如何达成全局一致性?33.1区块链需要解决的问题2：拜占庭将军问题3.1概述-共识算法共识算法，针对某一提案（目标，投票等各种协作工作），大家达成一致意见的过程分布式系统集群设计中面临着一个不可回避的问题，一致性问题。引起一致性问题的根源：节点之间通讯不可靠，延迟和阻塞。节点的处理可能是错误的，甚至节点自身随时可能宕机。节点作恶。在区块链系统中，如何让每个节点通过一个规则将各自的数据保持一致是一个很核心的问题。这个问题的解决方案就是制定一套共识算法。3.1概述-共识算法本质：规则，使区块链网络达成共识的机制。每个节点都按这个规则去确认各自的数据。区块链是分布式系统，分散的节点需要就交易有效与否达成一致。意义：确保所有节点都遵守协议规则并保证所有交易都以可靠方式进行，即每个货币只能花一次——解决双花问题同时保持各个节点的正确一致性——解决拜占庭将军问题常见共识算法：见右侧

2PROOFOFWORK工作量证明PoW3.2PoW-工作量证明通过对工作的结果（考试）进行认证来证明完成了相应的工作量，是一种非常高效的方式。

工作量证明系统（或者说协议、函数），是一种应对拒绝服务攻击和其他服务滥用的经济对策。要求发起者进行一定量的运算，也就意味着需要消耗计算机一定的时间。这个概念由CynthiaDwork和MoniNaor1993年在学术论文中首次提出。工作量证明原理：

客户端需要做一定难度的工作得出一个结果，验证方很容易通过结果来检查出客户端是不是做了相应的工作。这种方案的一个核心特征是不对称性：工作对于请求方是适中的，对于验证方则是易于验证的。3.2PoW-工作原理问题想获得雅思证书怎么办？解决方法努力学习英语，参加培训和考试难点及价值必须通过努力学习，达到考分要求。在区块链中，PoW是一种运作机制。强制要求财富获取方式只能是通过劳动，也就是算力运算——挖矿。3.2什么是PoW-应用案例1问题游戏想要通关，怎么办？解决方法打怪升级难点及价值游戏角色要升级必须通过不断打怪战斗获取经验，这个游戏的升级机制就是PoW3.2什么是PoW-应用案例2在区块链中，PoW是一种运作机制。强制要求财富获取方式只能是通过劳动，也就是算力运算——挖矿。问题面对群发的垃圾邮件怎么办？解决方法要求在发邮件之前先做一些运算，这些运算是有成本的。难点及价值对于发一两封邮件的来说不算什么，但是对于那些以发邮件为盈利的来说就是一道难以逾越的坎了，这样的方式起到了很好的效果。3.2什么是PoW-应用案例3在区块链中，PoW是一种运作机制。强制要求财富获取方式只能是通过劳动，也就是算力运算——挖矿。问题比特币如何避免双花问题？解决方法时间戳技术、数字签名等等难点及价值51%算力攻击？如何击破？诚实节点占据51%的算力以上才能维护网络安全。在区块链中，PoW是一种运作机制。强制要求财富获取方式只能是通过劳动，也就是算力运算——挖矿。3.2PoW-应用案例1记账：把交易记录、交易时间、账本序号、以及上一个Hash值等信息计算Hash打包的过程。（计算存储消耗资源）挖矿：记账过程称为挖矿奖励：完成记账的节点（PoW）可以获得系统给与的一定数量的比特币奖励问题：大家争相记账会引起记账不一致的问题PoW：解决不一致问题规则：一段时间内（10分钟左右，具体时间会与密码学难题难度相互影响）只有一人可以记账成功通过解决密码学难题（即PoW）竞争获得唯一记账权其他节点复制记账结果比特币使用SHA-256（SecureHashAlgorithm）确定区块的哈希区块链是一个基于密码学安全的分布式账本，是一个方便验证，不可篡改的账本。3.2PoW-基本概念3.2PoW-几个基本概念难度：计算符合给定目标的一个HASH值的困难程度（对应一定量的哈希次数）算力：对应哈希频率，通过哈希运算找到一个解nonce，使得块hash小于目标HASH值。hash/s或者H/s难度调整：保证系统稳定的每过10分钟产出一个块，难度调整的时间大概是2周难度公式：

当前难度D=最大目标值（长度256bit，是难度为1的目标值，即2^224）/当前目标值(长度256bit)

最大目标值是一个常数：0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF假设当前难度D，算力P，当前目标值C，发现新区块的平均时间T发现新区块的平均时间T找到新区块的哈希次数D，P和T之间的关系C=2^224/D2^256/C=2^32DP=2^32D/T3.2PoW-共识步骤当前目标值挖矿：不断接入新的Block延续BlockChain的过程。3.2PoW-51%攻击

链的长度与工作量成正比，所有的节点均信任最长的链。攻击者利用主链选择原理，对某些交易实现双重支付攻击，有一定概率可以获得成功。攻击者无法盗取他人比特币，也无法篡改他人交易记录，但是却可以对某些交易进行双重支付的攻击。算力越大，获取记账权利的几率越大，当攻击者占有的算力超过51%时，一定可以成功，51%攻击。现在基本不大可能，对GPU的要求会是天文数字。3.2PoW-记账流程与工作原理某个节点提供合理的BlockHash值。PoW通过验证获得记账资格选择BestChain选择Best链至主链获得奖励3.2PoW-总结优点应用广泛节点自由进出完全去中心化缺点速度慢、耗能巨大匿名、免监管算力中心化，有51%的安全隐患使用者Bitcoin、Ethereum、Litecoin、Dogecoin等。类型有竞争共识（Competitiveconsensus）

3PROOFOFSTAKE

权益证明PoS3.3PoS-权益证明PoW中让每个人互相竞争挖矿是很浪费的。权益证明通过选举的形式，其中任意节点被随机选择来验证下一个区块。PoS中没有矿工，但是有验证者(validator)。不让人们挖新区块而是铸造新区块。验证者非随机选择，要成为验证者，节点需要在网络中存入一定数量的货币作为权益，可以将这理解为保证金。假设Bob在网络中存入100美元Alice存入1000美元，那么Alice比Bob有高于10倍的几率选为验证者。因为这偏袒有钱的一方，似乎不太公平，但事实上这比起工作量证明更公平。为什么？股权越多，机会越大。为了防止在这个过程中网络不会偏向最富有的节点，选择过程中有一些特殊的步骤：“随机区块选择”“币龄选择”

PoS的具体实现有很多版本：点点币、黑币、未来币、瑞迪币，它们都推动了PoS机制的发展。PoS也称股权证明，类似于财产储存在银行，这种模式会根据你持有数字货币的量和时间，分配给你相应的利息。鉴于PoW主要依赖于计算机硬件的稀缺性来防止女巫攻击，PoS则主要依赖于区块链自身里的代币。在PoS中，一个用户可能拿1000美元来买计算机，加入网络来挖矿产生新区块，从而得到奖励。核心概念：币龄=持有数量*持有时间特殊的交易：利息币，即持有人可以消耗币龄获得利息，同时获得为网络产生区块、以及PoS造币的优先权。交易费：每记一次帐，币天数即被销毁，因此不能被重复使用。PoS机制的区块链产品，每个节点都可以创建区块，并按照个人的持股比例获得“利息”。

3.3PoS-基本概念3.3PoW-局限性PoW挖矿的基本原理是找到一个nonce值，使得新区块头的哈希值小于某个指定的值，即区块头结构中的“难度目标”

：proofHash(block_header)<目标值注：只要计算结果哈希值小于目标值即可，简化来看就是前导0的个数。PoW下所有矿工的目标值是一样的。3.3PoS-实现原理基于权益证明共识的区块链系统中，参与者的角色是验证者Validator，他们只需要投资系统的代币并在特定时间内验证自己是否为下一区块创造者，即可完成下一区块的创建。下一区块创造者是以某种确定的方式来选择，被选中的验证者将合适的交易打包成块并发布到区块链上。验证者被选中为下一区块创造者的概率与其所拥有的系统中代币的数量成正比例，简单来说即拥有300个代币的验证者被选中为下一区块创造者的概率是即拥有100个代币验证者的3倍。3.3PoS-点点币实例点点币的PoS证明计算公式为：

proofhash<币龄x目标值因此，每个参与者产生区块的难度目标值各不相同,参与者的币龄越大,难度目标越大，生成区块的几率也就越大。例如：

当前全网的目标是4369，A矿工的输入的币龄是15，那么A矿工的目标值为65535，若完整的哈希长度假设是8位，目标值转换为0x0000FFFFH。

同理，B矿工比较有钱，其币龄是240，那么B矿工的目标值就是0x000FFFFFH，即如下：A矿工：proofHash(block_header)<0x0000FFFFB矿工：proofHash(block_header)<0x000FFFFF

相比A矿工的目标值，B得目标值左侧少了一个零。所以B矿工获得记账权的概率肯定要比A高。PoS使得权益大的用户能够更好的保证自己的权益。我们该如何相信网络中的其他验证者?----根据权益如果验证者通过了欺诈性交易，他们将失去一部分权益。只要权益高于验证者所获得的交易费，我们就可以信任他们能够很好的完成工作。否则，他们失去的钱比能获得的还多。这是金钱方面的动力，只要权益比所有交易费要高，这就是可行的。如果节点不再是验证者，他的权益以及获得的交易费将在一定时间后返还给他。不会马上返还，因为若发现你的区块存在欺诈时，网络会对你进行惩罚。

3.3PoS-权益与要求证明人执行一定量的计算工作不同，权益证明要求证明人提供一定数量加密货币的所有权。权益证明机制运作是，当我们需要创造一个新区块时，矿工们就需要创建一个“币权”交易。交易会按照我们事先设定的比例把一些币发送给矿工（有点像银行利息）。3.3PoS-权益证明问题如何获取话语权，如何解决PoW中存在的问题解决方法把持币量的多少，来看作拥有股权、股份的多少。使用铸币而非去挖币。解决了PoW的效率难题。价值意义增加共识速度（约每5秒产生一个区块），不需要大量能耗去挖矿。避免51%攻击。3.3PoS-点点币应用原理3.3PoS-与PoW的对比PoW与PoS共识机制对比矿工的工作量决定了他挖出区块并获得奖励的可能性矿工的挖矿能力取决于他拥有多少代币矿工的工作量决定了他挖出区块并获得奖励的可能性在PoS共识机制中，51%攻击几乎不可能发生，因为发生的成本及其昂贵随着时间的推移，矿工可获得的比特币越来越少，减少的激励会降低51%攻击发生的可能性在PoS社区内，节点之间联系相对不紧密，实际上更加去中心化PoW社区内节点之间的联系十分紧密，随着时间的推移，很大概率会走向极端中心化优点节能；攻击者代价更大；不易受“规模经济”的影响。缺点「无成本利益」(Nothingatstake)攻击问题。使用者Peercoin（点点币）、Nxt（未来币）、Blackcoin（黑币）类型有竞争共识3.3PoS-总结

4DELEGATEDPROOFOFSTAKE股份授权证明机制DPoS3.4DPoS-引入算法股份授权证明机制DPoS是一种新的保障加密货币网络安全的算法。它在尝试解决比特币采用的PoW以及点点币采用的PoS问题的同时，通过引入“受托人”这个角色，实施科技式的民主以抵消中心化所带来的负面效应。3.4DPoS-基本原理DPoS是由社区中选举出来的受托人（得票数排行前101位）来创建区块的。为了成为正式受托人，用户要去社区拉票，以获得足够多用户的信任。用户根据自己持有的加密货币数量占总量的百分比来投票。DPoS机制类似于股份制公司，普通股民进不了董事会，要投票选举代表（受托人）来代替他们做决策。持股人永远掌控大局，能够获得超过1%选票的人都可以成为受托人，受托人组成“董事会”，轮流签署区块。给持股人一把可以开启他们所持股份对应的表决权的钥匙，而不是给他们一把能挖矿的铲子。最大化持股人的盈利。最小化维护网络安全的费用。最大化网络的效能。最小化运行网络的成本(带宽、CPU等)。DPoS机制董事会决策,是一种代议制共识,通过投票机制将所有用户的权利集中到少数人手中,形成一种有约束的中心化,这种中心化大大加快了交易的确认速度,确认时间缩短到秒级,将加密货币技术带到了一个新的层次.但与现实情况类似的是,权利一旦集中到少数人手中,我们就不得不提防这群人是否会为了自身利益损害公正.该模式可以每30秒产生一个新区块，并且在正常的网络条件下区块链分叉的可能性极其小，即使发生也可以在几分钟内得到解决。3.4DPoS-基本原理

5PRACTICALBYZANTINEFAULTTOLERANCE实用拜占庭容错算法PBFT3.5PBFT-引入算法在分布式系统中，理论条件下，系统易达成一致。硬件故障、网络原因、显式作恶，破坏一致性。拜占庭将军问题被认为是容错性问题中的难题。解决方案拜占庭容错技术：在某种不可信的环境中达成一致。Castro和Liskov在1999年提出的PBFT是第一个得到广泛应用的BFT算法。3.4PBFT-基本原理PBFT的一致性协议如图所示，每一个客户端的请求需要5个阶段才能完成。其通过采用两次两两交互的方式，在服务器达成一致之后再执行客户端的请求。由于客户端不能从服务器端获得任何服务器运行状态的信息，因此PBFT协议中主节点是否发生错误只能由服务器监测。如果服务器在一段时间内都不能完成客户端的请求，则会触发视图更换协议（即节点切换）。

3.4PBFT-基本原理1）Request：请求端节点C发送请求到其他任意一节点，假定发送到节点0。2）Pre-Prepare：节点0收到C的请求后进行广播，广播至节点1、2和3。3）Prepare：节点1-3被要求收到广播处理完后，再次广播。节点1传播至0、2、3；2传至0、1、3，节点3故障无法广播。4）Commit：节点0-3在Prepare阶段，如果收到2f+1以上数量相同的请求，则进入Commit阶段，开始广播Commit请求。5）Reply：节点0、1、2、3在Commit阶段，如果收到2f+1以上数量的相同请求，就对C进行反馈。在PBFT中，如果满足N≥3f+1，其中N为总节点数，f为有故障的节点总数，那么最终的一致性是可以达成的。

C为发送请求节点0到3为服务节点3为故障节点几种共识算法的比较PoW按劳取酬（算力x时长）多劳多得

PoS根据币龄发放利息多持有多得DPoS选举代表做决策PoS的升级版PBFT联盟链的共识算法应对节点故障和传输错误

6IMPROVEDCONSENSUSALGORITHM改进共识算法3.6.1基于PoW的改进算法3.6.2基于PoS的改进算法3.6.3其他共识算法的改进3.6改进的共识算法3.6改进的共识算法-基于PoW的改进PoW缺陷：块间隔时间长，块容量有限，交易确定速度慢，吞吐量7tps，必须扩容。Bitcoin-NG：康奈尔大学提出的一种扩容方案，选择最长最重的链。区块分两种：核心块（keyblock，有重量）和微区块（microblock，无重量）。使用了一种分成激励模式矿工们对区块的操作分成两个阶段:选举领导者和打包交易。bitcoin-ng复用了bitcoin的PoW算法，但是PoW只是用来选leader，leader可以写入一个keyblock以及多个microblock,这些block间隔时间非常短。一个Leader负责写入的这个范围叫做一个epoch。

3.6改进的共识算法-基于PoS的改进VRF（VerifiableRandomFunction，可验证随机函数），通过VRF随机抽取节点，用BFT算法生成区块。Algorand是2012年图灵奖获得者SilvioMicali（MITAI实验室）主导研发的一种加密货币方案。该方案通过密码学抽签算法实现了拜占庭共识算法的大规模扩展，从而适用于公链数字货币体系。Algorand是权益证明(POS)的一个升级，彻底消除区块链分叉的可能性，可以在一小段时间内确认交易，Algorand的核心使用称为BA⋆的拜占庭协议，同时扩展到许多用户。即使一些用户是恶意的，网络被临时分区，Algorand也确保用户从未对已确认的交易有不同意见。在Algorand的BA⋆协议中，除了私钥之外，用户不会保留任何私有状态。Algorand/abs/1607.01341

论文原文

HQ算法比如PoI（账户重要度证明）ZyzzyvaPoP（账户参与度证明）3.6改进的共识算法-其他共识算法的改进

7REVIEW课程总结3.3PoS3.5PBFT3.2PoW3.4DPoS3.7本章主要内容3.1共识机制3.6共识算法的改进快速复习如无题目，可暂时留白选择题：PoW是比特币区块链和以太坊拜占庭大都会区块链所使用的__________。交易确认共识协议激励功能信任功能共识协议的哪一种方法在区块链开发人员中引起了广泛争议：RoundRobinProofofStakeProofofIncentiveProofofAge快速复习选择题：1.ThealgorithmforconsensusintheBitcoinblockchainiscalled_____protocol.A.ProofofElapsedTimeB.ProofofWorthC.ProofofStakeD.ProofofWork2.Validation,Verification,ImmutableRecording,and_____leadtoTrustandSecurity.

A.CoinsB.AlgorithmsC.ConsensusD.Tokens3.WhointroducedthedigitalonlinecryptocurrencyknownasBitcoin?A.NickSzaboB.HalFinneyC.WeiDaiD.SatoshiNakamoto4.AblockinaBlockchainhasaheaderand_______________.A.TransactionsB.InputsC.DigitalLedgerD.Bitcoins5.Proofofworkisthe__________usedbyBitcoinblockchainandEthereumByzantiumMetropolisblockchain.A.TransactionconfirmationB.ConsensusProtocolC.IncentivefunctionD.Trustfunction快速复习选择题：6.WhatisamajorproblemwithProofOfWork?A.ItisdifficulttoimplementB.

ItisCPU-intensiveandconsumesenormousamountofpower.C.MultipleminershavetoberewardedD.Itisunreliable7.WhichofthefollowingisusedinsolvingaPOWpuzzle?A.EncryptingB.HashingC.FragmentingD.Sharding8.InPracticalByzantineFaultTolerance,___.A.amasternodeselectsthenextnodethataddsthenextblockB.thenodeselectaleaderandthatleaderaddsthenextblockC.thenodewithmostcoinsischosenforaddingthenextblock9.Whatisthesizeofthebitcoinblocksince2010?A.2MBB.1KBC.1MBD.1GB快速复习判断题：1.Transactionconfirmationisindependentlyperformedbyallminernodes.TrueorFalse?2.Inapublicblockchain,aparticipantcanjoinandleavetheblockchainwhentheywish.TrueorFalse?3.Bitcoinenableacentralizedsystemforexchangeofvalue.

TrueorFalse?4.Doublespendingisreusingdigitalassetsintentionally