查看原文
其他

盘点|一文读懂11个主流共识算法, 彻底搞懂PoS,PoW,dPoW,PBFT,dBFT这些究竟是什么鬼

aholiab 区块链大本营 2018-12-16

作者 | Aholiab


在区块链的交流和学习中,「共识算法」是一个很频繁被提起的词汇,正是因为共识算法的存在,区块链的可信性才能被保证。


常见的共识算法有很多,例如PoW(Proof of Work,工作量证明)、PoS(Proof of Stake,权益证明)、DPoS(Delegate Proof of Stake,委托权益证明)、PBFT(Practical Byzantine Fault Tolerance,实用拜占庭容错算法)等。


说白了,不同的算法其实就是不同的游戏玩法。在区块链世界,共识一般都是通过特定的数学算法实现。


那么到底什么是共识算法?每天听到的这些共识算法到底是什么意思?本篇文章就为你一一梳理,相信读完之后,可以得到不少的谈资


在讲解共识算法之前,我们先来看看什么叫共识。



说人话,谈谈共识算法


所谓共识,简单理解就是指大家都达成一致的意思。其实在现实生活中,有很多需要达成共识的场景,比如开会讨论,双方或多方签订一份合作协议等。


而在区块链系统中,每个节点必须要做的事情就是让自己的账本跟其他节点的账本保持一致。如果是在传统的软件结构中,这几乎就不是问题,因为有一个中心服务器存在,也就是所谓的主库,其他的从库向主库看齐就行了。


在现实生活中,很多事情人们也都是按照这种思路来的,比如企业老板发布一个通知,员工照着做。但是区块链是一个分布式的对等网络结构,在这个结构中没有哪个节点是“老大”,一切都要商量着来。


所以在区块链系统中,如何让每个节点通过一个规则将各自的数据保持一致是一个很核心的问题,这个问题的解决方案就是制定一套共识算法。


共识算法其实就是一个规则,每个节点都按照这个规则去确认各自的数据。我们暂且抛开算法的原理,先来想一想在生活中我们会如何解决这样一个问题:假设一群人开会,这群人中没有一个领导或者说老大,大家各抒己见,那么最后如何统一出一个决定出来呢?



一般,我们一般会在某一个时间段中选出一个人,那个人负责汇总大家的内容,然后发布完整的意见,其他人投票表决,每个人都有机会来做汇总发表,最后谁的支持者多就以谁的最终意见为准。


这种思路其实就算是一种共识算法了。然而在实际过程中,如果人数不多并且数量是确定的还好处理,如果人数很多且数量也不固定,那就很难通过这种方式投票决定了,效率太低。我们需要通过一种机制筛选出最有代表性的人,在共识算法中就是筛选出具有代表性的节点


这就需要设计出一组条件,而这组条件就是我们所谈的共识算法。目前主流的共识算法有很多,接下来,营长就为大家一一科普每种共识算法的机制、特性和优劣。



1. 工作量证明(PoW,Proof of Work)


优点:自 2009 年以来得到了广泛测试,目前依然得到广泛的使用。

缺点:速度慢;耗能巨大,对环境不好;易受“规模经济”(economies of scale)的影响。

使用者:Bitcoin、Ethereum、Litecoin、Dogecoin等。

类型:有竞争共识(Competitive consensus)。


工作量证明(Proof Of Work,简称POW)应该算是最常见的共识算法之一,简单理解就是一份用来确认你做过一定量的工作的证明。监测工作的整个过程通常是极为低效的,而通过对工作的结果进行认证来证明完成了相应的工作量,则是一种非常高效的方式。比如现实生活中的毕业证、驾驶证等等,也是通过检验结果的方式(通过相关的考试)所取得的证明。


工作量证明系统(或者说协议、函数),是一种应对拒绝服务攻击和其他服务滥用的经济对策。它要求发起者进行一定量的运算,也就意味着需要消耗计算机一定的时间。这个概念由Cynthia Dwork 和Moni Naor 1993年在学术论文中首次提出。而工作量证明(POW)这个名词,则是在1999年 Markus Jakobsson 和Ari Juels的文章中才被真正提出。



PoW 并非一个新理念,但是中本聪将 Pow 与加密签名、Merkle 链和 P2P 网络等已有理念结合,形成一种可用的分布式共识系统。加密货币是这样系统的首个基础和应用,因而独具创新性。


在 PoW 的工作方式中,区块链参与者(称为「矿工」)要在区块链中添加一块交易,必须解决某种「复杂但是无用」的计算问题。


本质上,这种做法可确保矿工花费了一些金钱或资源(矿机)完成工作,这表示了它们将不会损害区块链系统,因为对系统的损害也将会导致投资的损失,进而损害他们自身。


为保证运行区块时间不变,问题的复杂性会发生变化。有时,会存在多名矿工同时解决了问题。在这种情况下,每位矿工从中选取一个区块链,并以选取最长链者为获胜者。


因此,如果假定大多数矿工工作在同一个链上,那么成长最快的链将成为最长和最值得信任的链。这样,只要由矿工提交的工作有超过一半是值得信任的,那么加密货币就是安全的。



2. 权益证明(PoS,Proof of Stake)


优点:节能;攻击者代价更大;不易受“规模经济”的影响。

缺点:「无利害关系」(Nothing at stake)攻击问题。

使用者:Ethereum(即将推出)、Peercoin、Nxt。

类型:有竞争共识。


正是因为PoW算法在挖矿过程中对环境和电力的浪费极大,PoS才作为一种代替算法。


POS也称股权证明,类似于财产储存在银行,这种模式会根据你持有数字货币的量和时间,分配给你相应的利息。鉴于POW主要依赖于计算机硬件的稀缺性来防止女巫攻击,POS则主要依赖于区块链自身里的代币。在POW中,一个用户可能拿1000美元来买计算机,加入网络来挖矿产生新区块,从而得到奖励。


简单来说,就是一个根据你持有货币的量和时间,给你发利息的一个制度,在股权证明POS模式下,有一个名词叫币龄,每个币每天产生1币龄,比如你持有100个币,总共持有了30天,那么,此时你的币龄就为3000,这个时候,如果你发现了一个POS区块,你的币龄就会被清空为0。


你每被清空365币龄,你将会从区块中获得0.05个币的利息(假定利息可理解为年利率5%),那么在这个案例中,利息 = 3000 * 5% / 365 = 0.41个币,这下就很有意思了,持币有利息。


然而,一旦币的权益被用于签名一个区块,则币龄将清为零,这样必须等待至少30日才能签署另一区块。同时,为防止非常老或非常大的权益控制区块链,寻找下一区块的最大概率在90天后达到最大值,这一过程保护了网络,并随着时间逐渐生成新的币而无需消耗大量的计算能力。


权益证明必须采用某种方法定义任意区块链中的下一合法区块,依据账户结余来选择将导致中心化,例如单个首富成员可能会拥有长久的优势。为此,人们还设计了其他不同的方法来选择下一合法区块。


PoW与PoS对比



3. 延迟工作量证明(dPoW,Delayed Proof-of-Work)


优点:节能;安全性增加;可以通过非直接提供 Bitcoin(或是其它任何安全链),添加价值到其它区块链,无需付出 Bitcoin(或是其它任何安全链)交易的代价。

缺点:只有使用PoW或PoS的区块链,才能采用这种共识算法;在“公证员激活”(Notaries Active)模式下,必须校准不同节点(公证员或正常节点)的哈希率,否则哈希率间的差异会爆炸(下文将给出详细解释)。

采用者:Komodo

类型:协同型共识(Collaborative consensus)


DPoW是建立在PoB与DPoS基础上的新一代共识机制,借鉴了前辈共识机制的设计理念和运行的经验。


解释DPoW前,需要先说明什么叫PoB。


PoB(Proof of Burn)叫做焚烧证明机制,是一种通过焚烧自己手中的代币来表决谁拥有对网络的领导地位的承诺。焚烧代币的数量越多,能获得网络领导地位的概率越高。PoB是分布式共识的一种方法,也是工作量证明机制的替代方法。它也可以用来引导一种加密货币。



在基于DPoW的区块链中,矿工挖矿所获得的不再是奖励的代币,而是可以焚烧的“wood”——燃木。矿工使用自己的算力,通过哈希算法,最终证明自己的工作量之后,获取对应的wood,wood不可交易。当wood积攒到一定量之后,可以前往燃烧场地燃烧wood。


通过一组算法计算后,燃烧较多wood的人或者BP或者一组BP可以获取下个事件段出块的权利,成功出块后获取奖励(代币)。由于一个时间段内可能会有多人燃烧wood,下一个时间段出块的概率由自己燃烧wood数量决定。焚烧的越多,下一段时间可以获得出块权利的概率越高。


这样可以让算力和出矿权利达到一个平衡。不一定非要庞大算力的矿工、矿池才能成为区块生产者。小矿工也有春天,只要辛勤劳动,积攒一定数量的wood,也能出块。保证效率,人人参与,最平民化的参与方式保证了去中心化的理念,避免拥有算力的组织或者持币大户把持网络。


dPoW 系统中有两种类型的节点:公证人节点和正常节点。64 个公证人节点是由 dPoW 区块链的权益持有者(stakeholder)选举产生的,它们可从 dPoW 区块链向所附加的 PoW 区块链添加经公证确认的块。一旦添加了一个块,该块的哈希值将被添加到由 33 个公证人节点签署的 Bitcoin 交易中,并创建一个哈希到 Bitcoin 区块链的 dPow 块记录。该记录已被网络中的大多数公证人节点公证。


为避免公证人节点间在挖矿上产生战争,进而降低网络的效率,Komodo 设计了一种采用轮询机制的挖矿方法,该方法具有两种运行模式。


在“无公证人”(No Notary)模式下,支持所有网络节点参与挖矿,这类似于传统 PoW 共识机制。而在“公证人激活”(Notaries Active)模式下,网络公证人使用一种显著降低的网络难度率挖矿。“公证人激活”模式下,允许每位公证人使用其当前的难度挖掘一个区块,而其它公证人节点必须采用 10 倍难度挖矿,所有正常节点使用公证人节点难度的 100 倍挖矿。



4. 授权 PoS(DPoS,Delegated Proof-of-Stake)


优点:节能;快速;高流量博客网站 Steemit 就使用了它。EOS 的块时间是 0.5 秒。

缺点:略为中心化;拥有高权益的参与者可投票使自己成为一名验证者(这是近期已在 EOS 中出现的问题)。

采用者:BitShares、Steemit、EOS、Lisk、Ark。

类型:协同型共识


DPoS机制,又叫做「股份授权证明机制」和「受托人机制」,是2014年4月由Bitshares 的首席开发者 Dan Larimer(BM)提出的。


它的原理是让每一个持有比特股的人进行投票,由此产生101位代表 , 我们可以将其理解为101个超级节点或者矿池,而这101个超级节点彼此的权利是完全相等的


从某种角度来看,DPOS有点像是议会制度或人民代表大会制度。如果代表不能履行他们的职责(当轮到他们时,没能生成区块),他们会被除名,网络会选出新的超级节点来取代他们。DPOS的出现最主要还是因为矿机的产生,大量的算力在不了解也不关心比特币的人身上,类似演唱会的黄牛,大量囤票而丝毫不关心演唱会的内容。


DPoS的伪代码实现


为了方便理解,可以再举个例子。想象有这样一家公司:公司员工总数有1000人,每个人都持有数额不等的公司股份。每隔一段时间,员工可以把手里的票投向自己最认可的10个人来领导公司,其中每个员工的票权和他手里持有的股份数成正比。等所有人投完票以后,得票率最高的10个人成为公司的领导。


如果有领导能力不胜任或做了不利于公司的事,那员工可以撤销对改领导的投票,让他的得票率无法进入前10名,从而退出管理层。这就是对DPoS(Delegated Proof of Stake)共识机制的一个形象描述。



5. 实用拜占庭容错算法(PBFT:Practical Byzantine Fault Tolerance)


优点:高速、可扩展。

缺点:通常用于私有网络和许可网络。

采用者:Hyperledger Fabric、Stellar、Ripple、Dispatch


在解释这种算法之前,我们先来看看分布式计算中的经典问题——拜占庭将军问题


拜占庭将军问题是Leslie Lamport在10世纪80年代提出的一个假想问题。拜占庭是东罗马帝国的首都,由于当时拜占庭罗马帝国国土辽阔,每支军队的驻地分隔很远,将军们只能靠信使传递消息。发生战争时将军们必须制订统一的行动计划



然而,这些将军中有叛徒,叛徒希望通过影响统一行动计划的制定与传播,破坏忠诚的将军们一致的行动计划。因此,将军们必须有一个预定的方法协议,使所有忠诚的将军够达成一致。而且少数几个叛徒不能使忠诚的将军做出错误的计划。也就是说,拜占庭将军问题的实质就是要寻找一个方法,使得将军们在一个有版徒的非信任环境中建立对战斗计划的共识


在分布式系统中,特别是在区块链网络环境中,也和拜占庭将军的环境类似,有运行正常的服务器(类似忠诚的拜占庭将军),还有故障的服务器,有破坏者的服务器(类似叛变的拜占庭将军)。共识算法的核心是在正常的节点间形成对网络状态的共识。


实用拜占庭容错(PBFT,Practical Byzantine Fault Tolerance)是首个提出的该问题解决方案,当前已被 Hyperledger Fabric 采用。PBFT 使用了较少(少于 20 个,之后会稍有增加)的预选定将军数,因此运行非常高效。它的优点是高交易通量和吞吐量,但是不足之处在于是中心化的,并用于许可网络


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


  • 所有非拜占庭节点使用相同的输入信息,产生同样的结果;

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


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


  • 安全性——任何已经完成的请求都不会被更改,它可以在以后请求看到;

  • 活性——可以接受并且执行非拜占庭客户端的请求,不会被任何因素影响而导致非拜占庭客户端的请求不能执行。

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

1) 拜占庭节点的行为可以是任意的,拜占庭节点之间可以共谋; 

2) 节点之间的错误是不相关的; 

3) 节点之间通过异步网络连接,网络中的消息可能丢失、乱序、延时到达; 

4) 服务器之间传递的信息,第三方可以知晓 ,但是不能窜改、伪造信息的内容和验证信息的完整性;


简化的PBFT的协议通信模式


此外,PBFT是一种状态机副本复制算法,即服务作为状态机进行建模,状态机在分布式系统的不同节点进行副本复制。每个状态机的副本都保存了服务的状态,同时也实现了服务的操作。将所有的副本组成的集合使用大写字母R表示,使用0到|R|-1的整数表示每一个副本。假设|R|=3f+1,这里f是有可能失效的副本的最大个数。尽管可以存在多于3f+1个副本,但是额外的副本除了降低性能之外不能提高可靠性。



6. 授权拜占庭容错算法(dBFT,Delegated Byzantine Fault Tolerance)


优点:快速;可扩展。

缺点:每个人都争相成为根链。其中可能存在多个根链。

采用者:Neo。


同样是为了解决拜占庭将军问题,「授权拜占庭容错」机制,是一种在NEO区块链内部实现的保证容错的共识算法。


在这个机制当中,存在两个参与者,一个是专业记账的“记账节点”,一个是系统当中的普通用户


普通用户基于持有权益的比例来投票决定记账节点,当需要通过一项共识时,在这些记账节点中随机推选出一名发言人拟定方案,然后由其他记账节点根据拜占庭容错算法,即少数服从多数的原则进行表态,如果超过66%的节点表示同意发言人方案,则共识达成;否则,重新推选发言人,重复投票过程。


所以说,dBFT机制实际使用了一种迭代共识的方法来保证系统达成一致决定。然而,这种机制的缺点在于,当系统中有超过三分之一的记账节点停止工作时,整个区块链网络将无法提供正常的服务;当超过三分之一的节点联合作恶时,区块链将有可能发生分叉。



7. 权威证明(PoA,Proof-of-Authority)


优点:节能、快速。

缺点:略为中心化;虽然可用于公有区块链,但是通常用于私有区块链和许可区块链。

使用者:POA.Network、Ethereum Kovan testnet、VeChain。

类型:协同型共识。


基于 PoA 的网络、事务和区块,是由一些经认可的账户认证的,这些被认可的账户称为“验证者”(Validator)。验证者运行的软件,支持验证者将交易(transaction)置于区块中。该过程是自动的,无需验证者持续监控计算机,但需要维护计算机(权威节点)不妥协(uncompromised)。


验证者必须满足以下三个条件:

  • 其身份必须在链上得到正式验证,信息可在公有可用域中交叉验证;

  • 其资格必须难以获得,这样所得到的验证块的权利才弥足珍贵(例如,潜在的验证者需要获得公证书);

  • 建立权威的检查和程序必须完全统一。


使用 PoA,每个个体都具有变成验证者的权利,因此存在一旦获取就保持验证者位置的动机。通过对身份附加一个声誉,可以鼓励验证者去维护交易的过程。因为验证者并不希望让自己获得负面声誉,这会使其失去来之不易的验证者地位。



8. 所用时间证明(PoET,Proof of Elapsed Time)


优点:参与代价低;更多人可轻易加入,进而达到去中心化;对于所有参与者而言,更易于验证领导者是通过合法选举产生的;控制领导者选举过程的代价,是与从中获得的价值成正比的。

缺点:尽管 PoET 的代价低,但是必须要使用特定的硬件;不适用于公有区块链。

采用者:HyperLedger Sawtooth

类型:有竞争共识


PoET 共识机制算法通常用于许可区块链网络,它可决定网络中获得区块者的挖矿权利。许可区块链网络需要任何预期参与者在加入前验证身份。根据公平彩票系统的原则,每个节点具有同等的可能成为胜出者。PoET 机制赋予大量可能的网络参与者以平等胜出的机会。


PoET 的工作机制如下:网络中的每位参与节点都必须等待一个随机选取的时期,首个完成设定等待时间的节点将获得一个新区块。区块链网络中的每个节点会生成一个随机的等待时间,并休眠一个设定的时间。最先醒来的节点,即具有最短等待时间的节点,唤醒并向区块链提交一个新区块,然后广播必要的信息到整个对等网络中。同一过程将会重复,以发现下一个区块。


在 PoET 网络共识机制中,需要确保两个重要因素。

第一,参与节点在本质上会自然地选取一个随机的时间,而非某一个参与者为胜出而刻意选取了较短的时间。

第二,胜出者的确完成了等待时间。


PoET 理念是由著名的芯片制造巨头 Intel 于 2016 年早期提出的。Intel 为解决“随机领导者选举”的计算问题,实现了一个可用的高科技工具。


这种内在机制允许应用在受保护的环境中执行受信任的代码,它确保了上面提出的两个要求得到满足,即随机选择所有参与节点的等待时间,以及胜出参与者真正完成了等待时间。


PoET 通过控制代价实现了共识过程,该代价依然是与从过程中获得的价值成正比。这是保证加密货币经济持续繁荣的一个关键需求。



9. 权益流通证明(PoSV,Proof of Stake Velocity)


采用者:Reddcoin


PoSV 是作为 PoW 和 PoS 的一种替代方法而提出的,其目的是提高 P2P 网络的安全性,进而用于确认 Reddcoin 交易。Reddcoin 是一种加密货币,专为加速数字化时代的社交交互而提出的。


PoSV 在设计上鼓励所有者(权益)和活动(流通),直接对应于 Reddcoin 作为真实货币的两个主要功能,即存储价值和交换中介。Reddcoin 也可在异构社交场景中作为计量单位使用。



10. 恒星共识(Stellar Consensus)


优点:去中心化控制;低延迟;灵活的信任机制;渐进安全(Asymptotic security)。

采用者:Stellar


恒星共识基于联邦拜占庭共识(FBA)。恒星共识协议(SCP,Stellar Consensus Protocol)提供了一种不依赖闭合系统实现准确记录金融交易而达成共识的方法。


SCP 具有一组可验证的安全属性,这些属性根据如何安全地保持活力而做了优化。一旦出现分区或不当行为节点,它将会终止网络过程,直至达成共识。SCP 同时具备四种属性:去中心控制、低延迟、灵活信任机制和渐进安全。



11. 活动证明(PoActivity,Proof Of Activity)


使用者:Decred


为避免出现恶性通货膨胀(当大量货币充斥系统时就会发生),比特币将只生成两千一百万枚。这意味着,在某些时候,比特币区块奖励补贴将终止,比特币矿工将只能收取交易费用。


一些人猜测这可能会导致由“公地悲剧(Tragedy of the commons)”所引发的安全问题,人们出于自身利益考虑行事并破坏系统。因此,人们提出了 PoActivity 作为一种替代 Bitcoin 的激励结构。


PoActivity 是一种结合了 PoW 和 PoS 的混合方法。在 PoActivity 中,挖矿一开始使用的是传统的 PoW,矿工们争相解决加密难题。根据实现,挖掘的区块不包含任何交易,它们更像模板。因此,胜出的区块将只包含头部信息,以及矿工的奖励地址。


此时,系统将切换到 PoS。PoActivity 根据头部信息选择一组随机验证者对新区块签名。如果一位验证者所拥有的系统中代币越多,那么该验证者被选中的可能性也会越大。一旦所有验证者已签名,那么模板就会变成一个完整的区块。


如果在完成区块时,某些选定的验证者是不可用的,那么就选择下一个胜出区块,并选择一组新的验证者,依此类推,直到区块收到到正确数量的签名。费用由矿工和在区块上签名的验证者分摊。


对 PoActivity 的批评包括挖掘区块耗能过高(与PoW一样),以及无法阻止验证者做双重签名。


以上就是目前主流的共识算法。 


如果跳出开发者的角度,更多结合政治与经济的思考方式在里面,或许还会出现更多的共识算法,如结合类似PPP概念的共识方式,不仅能达到对恶意者的惩罚性质,还能达到最高效节约算力的目的也说不定。


至于说算法的选择,营长想提醒大家:没有最好的算法,只有最适合自己的算法。共识算法的选择与应用场景高度相关,可信环境使用Paxos 或者RAFT,带许可的联盟可使用PBFT ,非许可链可以是PoW,PoS,Ripple共识等。根据根据自己的实际需求选择共识算法,才是最优解。


营长为大家整理了这么多,喜欢就转起来吧~





参考文献:

大白话谈谈所谓的共识算法/币圈新贵

三十种共识算法,应用计算核心/终结者ASDF

区块链共识算法-POW/wycandyy

共识机制3.0时代来临 | DPoW达到效率与去中心化的新平衡点/Celeschain

[区块链]共识算法(POW,POS,DPOS,PBFT)介绍和心得/乐扣老师lekkoliu 

区块链中常用共识算法总结/已不再是少年

什么是NEO的dBFT共识机制?/华尔街见闻

A Hitchhiker’s Guide to Consensus Algorithms/Zane Witherspoon

Consensus Algorithms: The Root Of The Blockchain Technology/HASIB ANWAR



区块链大本营菜单更新提醒

New菜单升级啦,一键直通CSDN会员服务。

你关心的开发问题,这里都有答案。

搜索:开发疑难/资源一键查找,搜遍CSDN全站;

会员购买:专属VIP购买,免积分下载/免广告/获免费课程;

下载APP:安装CSDN APP,CSDN资源随身带;

个人中心:掌上CSDN个人助手,专属您的个人空间。


推荐阅读


    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存