《迅雷链精品课》第十一课：区块链常用共识算法介绍

 上一节课我们学习了共识算法理论基础，今天我们继续深入学习区块链共识算法，通过这节课我们将了解工作量证明、权威证明、权威授权证明、实用拜占庭容错等相关内容。



在学习课程的时候，你也可以领取BaaS平台为期一个月的试用机会，免费使用高性能区块链服务（点击链接即可免费领取https://blockchain.xunlei.com/baas/try.html）。课程学习结合实践操作，让你迅速成为区块链大牛！



*以下为第十一课的内容~



第十一课 区块链常用共识算法介绍



1. 共识算法的分类



共识算法解决的是对某个提案（Proposal），大家达成一致意见的过程。根据要解决的问题是普通错误还是拜占庭将军问题，将共识算法分为CFT（Crash Fault Tolerance）和BFT（Byzantine Fault Tolerance）。



CFT已有一些经典的解决算法，包括Paxos、Raft及其变种等。在传统的分布式网络中，各个节点也不会因为贪图利益故意伪造信息，很多情况下是由于网络的原因而掉线或发送错误消息。因此传统分布式系统中均使用CFT类共识算法。



而BFT则是在区块链系统中常用的共识算法。根据算法采取的策略，BFT类算法可以被分为两大类，即概率一致性算法和绝对一致性算法。回顾CAP 原理，两类算法的区别在于对可用性和一致性之间的平衡：概率一致性算法保证了系统的可用性而牺牲了系统的一致性，绝对一致性算法则与之相反，保证了系统的一致性而牺牲了系统的可用性。



1.1 概率一致性算法



概率一致性算法指在不同分布式节点之间，有较大概率保证节点间数据达到一致，但仍存在一定概率使得某些节点间数据不一致。对于某一个数据点而言，数据在节点间不一致的概率会随时间的推移逐渐降低至趋近于零，从而最终达到一致性。



例如工作量证明算法（Proof of Work, PoW）、权益证明算法（Proof of Stake, PoS）和委托权益证明算法（Delegated Proof of Stake, DPoS）都属于概率一致性算法。



1.2. 绝对一致性算法



而绝对一致性算法则指在任意时间点，一旦达成对某个结果的共识就不可逆转，即共识是最终结果，节点之间的数据会保持绝对一致。例如PBFT算法为代表的确定性系列算法即为绝对一致性算法。



2. 区块链项目中常用的共识算法



传统分布式数据库主要使用Paxos和Raft算法解决分布式一致性问题，它们假定系统中每个节点都是忠诚、不作恶的，但报文可能发生丢失和延时等问题。当分布式数据库的所有节点由单一机构统一维护时，此假定成立。在去中心化的区块链网络中，节点由互不了解、互不信任的多方参与者共同提供和维护，受各种利益驱动，网络中的参与者存在欺骗、作恶的可能，因此Paxos和Raft算法不能直接用于区块链的共识。



目前被区块链项目广泛采用的算法有工作量证明(PoW)、权益证明(PoS)、股份授权证明(DPoS)、实用拜占庭容错(PBFT)等， 另外一些项目则采用2种算法的混合算法，如PoW+PoS、DPoS+PBFT等， 此外还有燃烧证明（PoB，Proof of Burn）、沉淀证明（PoD，Proof of Deposit）、能力证明（PoC，Proof of Capacity）、消逝时间证明（PoET，Proof of Elapsed Time）等新型算法。



2.1. 工作量证明（Proof-of-Work, PoW）



工作量证明（Proof-of-Work, PoW），要求工作端进行一些耗时适当的复杂运算，并且答案能被服务方快速验算，以此耗用的时间、设备与能源做为担保成本，以确保服务与资源是被真正的需求所使用。





工作量证明最常用的技术原理是哈希散列函数。由于输入哈希函数h()的任意值n，会对应到一个h(n)结果，而n只要变动一个比特，得到的结果就完全不同，所以几乎无法从h(n)反推回n，因此借由指定查找h(n)的特征(例如要求小于某个数值，即哈希值前缀要求一定数量的0，增加难度即增加前缀0的数量)，让用户进行大量的穷举运算，就可以达成工作量证明。



PoW项目案例：



PoW共识算法最初在比特币系统中提出和应用。比特币系统在挖矿的过程中设定每个区块的出块时间期望为10分钟，根据实际出块的时间，会定期调整区块的目标难度，保证了在算力变化时，系统也能稳定运行。为了保证比特币系统能稳定地发展并不断产生区块，比特币的协议中人为地设置了这个10分钟规律，这使得系统中的所有节点可以利用这10分钟的时间，来完成接收，打包，见证的工作，同时将产生的交易在整个网络里进行广播。



比特币将区块间隔设计为10分钟，其实是在更快速的交易确认和更低的分叉概率间作出的妥协。尽管如此，分叉也不可避免，例如当有两名矿工A和B在几乎在相同的时间内，各自都算得了工作量证明解，便立即传播自己的区块到网络中，这样导致网络中一部分节点跟随A的区块，另一部分节点会跟随B的区块，两部分网络数据产生了不一致，即分叉。



比特币的策略是，在产生分叉后，两个分叉的网络各自继续挖矿，由于算力不一样，一段时间后，两个分叉的链的长度就会不一致，当网络上的节点收到两个分叉广播过来的区块后，就选择包含最多区块的那个链(最长链，也即难度最大链)为主链，这样，较短的分叉上的工作就会停止，这样每个人就会都在同一个顺序的这样上工作了。尽管在一段时间内会出现不一致，但保证最终能达成一致。



同时比特币由于分叉问题的存在，为防止出现双重支付问题，约定每个交易需要至少有5个验证过的区块在其后面得到验证才能算作确认，也就是说比特币的共识机制认为等待6个确认的情况下，分叉切换的概率就足够低了(例如按一个节点1%的算力来计算，6个区块后被长度被赶超的概率是100的6次方分之1)。



以太坊是另一个这类协议的典型，其设置的的出块时间期望仅为15秒。以太坊的出块速度较比特币的10分钟大幅缩短，这使得以太坊系统在产出速度上有更高的效率，交易在全网广播所费的时间更短，但也正因为网络传播慢的问题，形成了许多孤立区块。



总结PoW共识算法思路，其实是放宽对最终一致性确认的需求，约定好大家都选择已知最长的链进行确认，PoW系统的最终确认是概率意义上的，是被强制推迟的。这样的好处是，即便有人试图恶意破坏，也会付出很大的经济代价（付出超过系统一半的算力）。 



PoW共识算法存在的问题：



1) 算力竞争的设计导致了集中化的矿池：尽管PoW的目的是为了保证系统可以去中心化的运行，然而系统运行到现在，却事实上形成中心化程度很高的几个大矿池。已知的几个矿池垄断了世界上90%以上的算力，这可能导致大矿池破坏整个网络的行为。



2) 算力竞争的设计导致了大量的能源消耗，对环境不好：PoW系统需要产生大量的能源消耗：比特币挖矿比159个国家消耗的能源还多；目前77.7%的全球比特币网络算力仍在中国境内；受益于内蒙古和四川两地充沛的电力资源，中国拥有世界上最多的比特币矿场。比特币消耗的大量电力一直都是其被诟病的关键问题。



3) 业务处理性能低下：尽管投入了大量的能源支持系统的运行，但这些能源消耗绝大部分是用于工作量证明中的hash运算，而不是用于处理交易，处理交易业务的性能非常低，例如比特币每秒只能进行大约7笔交易；以太坊每秒也只有几十笔，近些年多次出现交易拥堵、交易费用猛增的情况。



4) 交易确认时间长：由于PoW是概率一致性算法，而非绝对一致性算法。在产生分叉后，两个分叉的网络各自继续挖矿，经过一段时间后选择包含最多区块的那个链(最长链)为主链，例如比特币中的一个交易等待6个区块才能认为安全不被回滚，按出块间隔10分钟来算，交易安全确认的时间在1小时以上。



2.2. 权益证明（Proof of Stake, PoS）



权益证明（Proof of Stake - POS）， 所有持有该区块链电子货币的使用者都可通过一个特殊交易将他们的电子货币锁定存入一个资金库，之后他们就可以成为验证者。算法通过固定时间协调所有节点参与投票，根据某种规则（例如持代币数量、或提供存储空间大小等）判断每个节点的权重，最后选取权重最高的节点作为检查。



POS相对于PoW的好处包括：



1) PoW需要花费大量的电力资源，POS的好处首先当然是去除了大量的算力竞争。

2) 不需要通过不停地发行新币来激励矿工参与算力竞赛。避免了不可知的通胀风险。3) 提出了利用博弈论来避免区块链网络产生中心化的大型参与者的新的方法。PoW的算力竞争设计模式导致了算力越来越向大矿池集中，这可能导致大矿池破坏整个网络的行为。

4) PoS还可以使51%攻击变的异常昂贵。恶意参与者将存在保证金被罚没的风险。



PoS项目案例：



最初的一版PoS由Peercoin设计实现。用户要产出block必须满足以下条件：

hash(stake_modifier, current_time, UTXO) < coin(UTXO) * age(UTXO) * difficulty



具体解释如下



1) 用户在每一秒时间（current_time），遍历自己所有的UTXO，代入上述公式中，看是否能满足不等式条件；如果满足，就把相应的UTXO记录在block中，并发布block。

2) stake_modifier是对前一个block中部分字段hash后的值，加入这一项是为了防止用户提前预知自己何时有权挖矿

3) difficulty会根据近期的block产出时间动态调整，保证block产出时间间隔稳定

4) 由于每秒只需要完成和自己UTXO数量相等的hash计算，所以需要的算力较低

5) 从不等式可以看出，持有的UTXO越多、UTXO中token数额越大（coin(UTXO)）、UTXO持有时间越长（age(UTXO)，或称之为币龄），不等式越容易成立，越容易进行挖矿



该版本的PoS面临着如下的问题：



1) 因为构造新的block没有算力成本，所以当区块链出现fork的时候，用户有可能会倾向于同时在多个branch一起挖矿来获得潜在更高的收益，这样制造了大量的分支，破坏了一致性。

2) 出现了攒币龄的现象，即关闭节点，直到age(UTXO)足够大的时候再启动节点挖矿，从而节省电力，这样引起了在线节点数太少系统脆弱的问题。

3) 可以攒够足够的币龄后，保证自己有足够的UTXO能够连续生产block，从而发动double-spend攻击。



Blackcoin在Peercoin的基础上进行了修改，从而缓解了上述问题，主要改动有：



1) 去掉了不等式公式右边的age(UTXO)，从而解决了问题3中攒币龄然后进行double-spend的现象；但是block奖励还是使用了币龄，因此并不能完全解决问题2中节点关闭的现象。

2) 优化了stake_modifier的计算逻辑，让用户提前预知自己有权挖矿时间的难度更大了。



PoS机制虽然考虑了PoW的不足，但也有缺点：



1） 依据权益结余来选择，会导致首富账户的权力更大，有可能支配记账权。

2） PoS的一致问题：PoS的挖矿过程，与PoW的问题类似，是全网所有节点共同参与的，每一时刻都有成千上万个节点同时去争取产出下一个block，因此会时有发生区块链分叉的问题。由于分叉的存在，block的产出时间间隔不能太短。各区块链通过动态调整的挖矿难度，将block时间间隔稳定在自己期望的水平。出块时间长，伴随而来的则是交易确认时间长和交易处理性能低。



2.3. 权益授权证明(DPoS)



股份授权证明机制（Delegated Proof of Stake，DPoS），是对PoW、PoS不足的提出的。DPoS 算法将成千上万个 PoS 节点，通过某种机制（例如持有代币的数量）选举出若干节点， 在这几之间进行投票选举（一些实现中甚至会以令牌环的方式进行轮询，进一步减少投票开销）出每次的检查点（出块）节点，而不用在网络中全部节点之间进行选择。



DPoS项目案例：

EOS前身石墨烯框架及bitshares（比特股）项目提出的DPOS方案，其步骤简述如下:



1）持有token的用户可以对候选的block producer进行投票；

2）得票最高的n个用户被选为代表，在下一个周期中负责产出block，目前n=21；

3）打乱代表的顺序后，各代表开始依次生产block。每个代表都有自己固定的时间区间，需要在自己的区间中完成block的生产发布。目前这个区间是3秒，即在正常情况下每3秒产出一个block；

4）每个代表在生产block的时候，需要找当时唯一的最长链进行生产，不能在其他分支上进行生产。



通过上述方法，保证了较短的block生产时间，且因为给每个生产者设置了固定的时间区间，则block的产出不会因为某个候选节点的延迟而延迟。



EOS最初使用的是DPoS算法，后来为了缩短出块时间，改成BFT-DPoS算法。



DPoS共识算法存在的问题：



1) 以EOS为代表的DPoS算法设计成由少数节点代替多数节点进行共识，其实是牺牲了区块链去中心化的特性，以此来换取共识效率的提升。

2) EOS的21个超级节点并不是21个不同实体，节点之间可能存在内在联系的共谋。

3) 超级节点竞选争议。由于网络无法解决女巫攻击问题，1人1票的民主投票制会被1代币1票制度所取代，导致“富豪统治”的结果；而相对不富裕的、拥有投票权较少的投资者则会对投票这件事漠不关心；超级节点可以花钱买选民们的投票；超级节点之间被鼓励互相串通，这样他们就可以改变他们与选民分享奖励的比例。

4) DPoS允许不超过节点总数三分之一的恶意或故障节点可能创建少数分叉。在这种情况下，少数分叉每9秒只能产生一个块，而多数分叉每9秒可以产生两个块。这样，诚实的2/3多数将永远比少数（的链）更长。



2.4. 实用拜占庭容错(PBFT)



PBFT是一个三阶段的共识算法，其主要流程如下图，我们会在后面的章节详细的介绍该算法。





PBFT算法的简易步骤：



1) 取一个副本作为主节点（图中0），其他的副本作为备份；

2) 用户（图中C）向主节点发送消息请求；

3) 主节点通过广播将请求发送给其他节点（图中1、2、3）；

4) 所有节点执行请求并将结果发回用户端；

5) 用户端需要等待f+1个不同副本节点发回相同的结果，即可作为整个操作的最终结果。



PBFT项目案例：



Hyperledger Fabric推荐并实现的就是PBFT共识算法。



PBFT不仅具备强一致性的特性，而且提供了较高的共识效率，比较适合对一致性和性能要求较高的区块链项目，但由于PBFT需要两两节点需要进行通信，通信量是O(n^2)（通过优化可以减少通信量），在公有链这种全球性的大环境下，节点数量和网络环境不可控，无法达成这种巨大的通信量。但对于联盟链和私有链，节点数量并不是很多，采用PBFT效率更高结果也更好，因此PBFT在联盟链和私有链的区块链项目中使用较为广泛。这也是Fabric项目采用PBFT算法的原因。



PBFT共识算法存在的问题：



1) 通信量是O(n^2)，不适用于节点数量和网络环境不可控的公有链项目。

2) PBFT是强一致性算法，在可用性上作了让步，当有1/3或以上记账人停止工作后，系统将无法提供服务。



2.5. PoW + PoS 



共识机制目前已经成为了区块链系统性能的关键瓶颈。单一的共识算法均存在各种问题，例如PoW算法存在消耗大量计算资源及性能低下的问题；PoS或DPoS存在囤币、“富豪统治”问题；而有着完善理论证明的PBFT算法面临着广播带来的网络开销过大的问题。融合多种共识算法优势的想法正受到越来越广泛的关注。



例如以太坊社区提出的正在研发中的共识协议名为Casper，是一个覆盖在已存在的以太坊PoW提议机制上的PoS，Casper融合了PoW和PoS两种算法。



Casper的基本思路是，任何人抵押足够多的以太币到系统中就可以成为矿工参与到挖矿过程。共识算法要求所有的矿工诚实工作，如果一个矿工有意破坏，不遵守协议，系统就会对矿工做出惩罚：没收之前抵押的以太币。有人把Casper这样的挖矿机制称为“虚拟挖矿”，比特币的矿工要参与挖矿需要先购买矿机，Casper则要先抵押以太币到系统中；比特币的矿工如果不按规则挖矿，则会损失电费以及可能的挖矿收益，而Casper中，不守规则的惩罚更为严重，除了失去挖矿收益，还要销毁“矿机”：抵押的以太币会被系统没收！



Casper的应用逻辑存在于智能合约的内部。要想在Casper中成为验证者，必须要有ETH并且要将ETH存储到Casper智能合约中作为杠杆的权益。在Casper第一次迭代中区块提议的机制会被保留：它依然使用Nakamoto PoW共识，矿工可以创建区块。不过为了最终化区块，Casper的PoS覆盖掌握控制权，并且拥有自己的验证者在PoW矿工之后进行投票。



3. 小结



本节我们介绍了一些区块链项目常用的共识算法。后续课程我们将更详细的分析PoW和PBFT的共识流程及其实现细节。