主流共识算法

共识算法是指在分布式场景中,多个节点为了达成相同的数据状态而运行的一种分布式算法。

一、引言

自人类社会产生以来,人们就一直从事着各种各样的贸易活动,货币体系在整个贸易活动中占据着重要的角色,人类经历了从以物易物到贝壳等稀有制品,再到银本位和金本位,最后到今天的法币体系。与一开始的以物易物相比,显然实物货币体系可以极大的提高贸易的效率。而法币与之前的实物货币又有什么区别?当今社会为什么采用法币呢?主要是国家为了控制本国的经济,集中货币发行和使用权,因此法本位与之前的货币相比,法币根本不具有稀有属性,只要国家政府愿意,所有的政府都可以随意的印制钞票,但是同时需要承担带来的通货膨胀等风险。法币依赖的基本是国家政府的公信力,当一个国家的经济越稳定,越富有,黄金储量越充足,这个国家的法币也越为普及和让人信服。而当今国际贸易的繁荣和国际社会的不稳定,法币这些缺陷也被逐渐放大,比如国际贸易每次都需要兑换成对方的法币才能实现贸易买卖,而兑换的过程会产生大量的金钱损耗,比如经济的困难和战争使得美国任意的印制美元,人们手里的美元价值在降低,美国政府窃取了人们的财富,同时也导致美元的公信力下降。因此世界需要一种能够产生共识,大家都认可的,具有稀有性的,能够稳定发展的货币。在2008年,中本聪提出了区块链的想法,实现了数字货币比特币。区块链采用了点对点协议,并基于共识协议来使得各个节点之间的决策达成一致,形成共识。区块链技术因其具备去中心化、信息的不可篡改和不可伪造性以及开放性等特征,在金融、政府办公、防伪溯源、征信以及知识产权等领域有着非常广泛的应用场景。虽然比特币在2008年提出,但是共识协议早在上个世纪七十年代就已经被提出:“一系列的机器能不能达成一致,怎么达成一致。”这个问题被称为共识。共识算法是指在分布式场景中,多个节点为了达成相同的数据状态而运行的一种分布式算法。

二、算法介绍

在分布式场景中,可能出现网络丢包、时钟漂移、节点宕机、节点作恶等等故障情况,共识算法需要能够容忍这些错误,保证多个节点取得相同的数据状态。

因此根据可容忍的故障类型的不同,可以将共识算法分为两类:

  • 容忍宕机错误类算法(crash

fault tolerant consensus algorithm),可以容忍网络丢包、时钟漂移、部分节点宕机这种节点为良性的错误。常见算法有 Paxos、Raft。

  • 容忍拜占庭错误类算法(byzantine

fault tolerant consensus algorithm),可以容忍部分节点任意类型错误,包括节点作恶的情况。常见算法有 PBFT、工作量证明(PoW)、权益证明(PoS)等。

也根据使用场景的不同,又可将共识算法分为公链共识联盟链共识两类。

下列对常用的几类算法做出详细介绍:

2.1 工作量证明(PoW

在比特币中,共识就是只有记账权的人才有资格修改账本,而账本的内容具有一致性。在比特币提出的时候,采用了工作证明的共识算法,此概念最早由Cynthia Dwork和Moni Naor于1993年的学术论文提出,工作证明是一种在区块链网络中达成共识机制的主流算法,也是各种加密货币(如比特币和以太坊)的基础共识模型,它描述了这样一种系统:该系统需要付出相当大的努力来挖掘新的区块,以防止恶意使用计算能力、和对系统进行其他可能的攻任何击,例如拒绝服务攻击和其他服务滥用,如通过使服务请求者做一些要求高的工作来发送垃圾邮件。在区块链网络中,PoW 共识机制要求各个挖矿节点要先通过大量计算来证明它们完成并提交的工作,然后它们才有资格接收将包含块的新事务添加到区块链,在工作证明中,谁的计算能力越高,或者说谁的工作量越大,谁就能拥有记账权,被添加到下一个区块。

工作量证明最常用的技术原理是哈希函数。由于输入哈希函数h的任意值n,会对应到一个h(n)结果,而n只要变动一个位元,就会引起雪崩效应,所以几乎无法从h(n)反推回n,因此借由指定查找h(n)的特征,让用户进行大量的穷举运算,就可以达成工作量证明。比特币采用的哈希加密算法为SHA-256,破解该加密算法SHA-256只能通过蛮力求解,几乎是不可能的事情,需要计算几十年。除非量子计算机的出现,在量子计算机的算力面前可能几个小时就解决了,但是以目前来看完全不必担心,其一量子计算机目前的发展完全不足以使其得到实际的普及和应用,在这之间的很长一段时间现有的体系都会发挥应有的作用。其加密算法同时也会得到优化。因此完全可以认为工作量证明是十分可靠的。

PoW算法主要优点有:

  1. 稳定可靠。
  2. 由于要获得多数节点承认,那攻击者必须投入超过总体一半的运算量(51%攻击),才能保证篡改结果。这使得攻击成功的成本变得非常高昂,难以实现。某种程度上是公平的,你投入越多的算力,你获得打包权的几率也等比增加。

主要缺点有:

  1. 非常浪费能源。投入在一种加密货币上的能源,可能会超过一个小型国家的总使用量。
  2. 由于加密货币在世界上已成为一种投资标的,所以技术人员开发出了由ASIC组成的特制计算设备(矿机),垄断算力。这与加密货币的去中心化思想背道而驰。

2.2 延工作量证明(dPoW)

延时工作量证明(dPoW)是由科莫多(Komodo)项目所设计的一种安全机制。基本上来说,它是工作量证明(PoW)共识算法的修改版本,它利用比特币区块链的哈希算力来增强网络安全性。通过使用延时工作量证明(dPoW),Komodo开发人员不仅能够保护自己的网络,还能够保护未来加入Komodo生态系统的任何第三方区块链。实际上,dPoW可以用于保护任何使用UTXO模型开发的独立区块链项目

dPoW 是一种混合共识方法,dPow的原理是允许一个区块链利用第二个区块链的哈希算力(Hashing Power)所提供的安全。该机制是通过一组公证员节点(Notary Node)实现的。公证员节点实现将第一个区块链的数据添加到第二个区块链中。进而,第二个区块链请求在两个区块链间达成妥协,弱化第一个区块链的安全。。

dPoW的主要优点有:

  1. 节能
  2. 安全性增加,dPoW可以通过非直接提供比特币,添加价值到其他区块链,无需付出比特币交易的代价

主要缺点有:

  1. 只有使用PoW或者PoS的区块链,才能使用这种共识算法,在公证员激活的模式下,必须校准不同节点的哈希率,否则哈希率间的差异会爆炸

2.3 权益证明(PoS

工作量证明Pow通过算力挖矿获取工作量的证明,获取区块奖励,激励矿工参与维护。而Pow带来的问题最主要的是能耗问题,光比特币的挖矿能耗接近一个国家的耗电量。通过挖矿比拼的是设备的数量,其实也就是拼钱。因此为什么不直接拼钱来分成奖励呢,省下了不必要的挖矿过程。因此基于这个理论,提出权益证明。

权益证明的原理是指通过自己手上的份额来进行算力的统计,权益的份额代表算力的占比,权益持有者都可以投票决定决策的实施与否。

显然PoS 是作为 Pow 的替代技术提出的,意在解决 PoW 的一些内在问题。PoS 没有使用传统挖矿方法,而是用户必须具有系统中的一些权益因此,如果用户拥有多少占比的权益那么该用户挖掘下一个区块的可能性就是多少占比。对于工作量证明,它的优点有

  1. 节约能耗无需挖矿
  2. 闭环。基于工作量的机制不是一个闭环,足够的法币可以对发动任意区块链加密货币发动攻击。即使占有的货币为0,但是可以通过购买设备来进行51攻击,尤其对于小币种,这种外部的攻击使得这些币种很容易被扼杀在摇篮里。而基于权益证明共识机制的加密货币,发动攻击需要购入这种货币,也就是攻击的资源必须来自于内部,而这一点攻击难度就极具提升,大量的买入势必导致价格的快速拉升,币种开发者可以及时做出应对,也可以选择赚钱跑路。
  3. 不易受经济规模的影响

主要缺点有“无利害关系“(Nothing at stake)”攻击问题。这种对多个区块历史(forks)投票的方式不会让区块生成器有任何损失,进而阻碍了达成共识。在 PoS 中,你可以在区块链的双方押注资产(“无厉害关系”问题)。而在 PoW 中,你不能从链的两个方向同时挖矿,因为这难以实现。

2.4 委托权益证明(DPoS

委托权益证明机制(DPoS)算法是PoS算法的改进。DPoS算法中使用见证人机制(witness)解决了中心化的问题。总共有N个见证人对区块进行签名。DPoS消除了交易需要等待一定数量区块被非信任节点验证的时间消耗。通过减少确认的要求,DPoS算法大大提高了交易的速度。通过信任少量的诚信节点,可以去除区块签名过程中不必要的步骤。DPoS的区块可以比PoW或者PoS容纳更多的交易数量,从而使加密数字货币的交易速度接近像Visa和Mastercard这样的中心化清算系统。

委托权益证明的原理是:

  1. 首先设立一个评审委员会,全球所有节点都可以报名参加,报名的前提是交纳保证金,通过审核的最为满足条件的前N个节点将作为候选节点,
  2. 进入下一轮,也就是竞选阶段。这些候选节点会将会各种演说游说其他的持币人,让他们给自己投票,这里可能场外会给投票人某些好处。
  3. 最终投票总数前m名的候选节点成为公链的代理人,负责出块。每次出块时,系统会随机顺序挑选指定某个代理人出块。每次选举出来的代理人都有任期,任期期间如果被监管发现某些作恶行为将会被追责和卸任。

委托权益证明的主要优点有:

  1. 节能。
  2. 快速。比如使用了该算法的EOS 的块时间是 0.5 秒。

主要缺点有:

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

2.5 实用拜占庭容错算法(PBFT

拜占庭容错算法是主流的共识算法之一,它起源于莱斯利·兰波特在其论文中描述的拜占庭将军问题:

一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题,将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果,因此各位将军必须通过投票来达成一致策略,即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向,他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军,这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

首个提出的该问题解决方案称为“实用拜占庭容错”(PBFT),PBFT刚开始是在MIT的Miguel 和 Barbara Liskov在1999年的学术论文中提出的,他们的本意是为设计一个低延迟存储系统设计系统,将算法复杂度由指数级降低到多项式级,使得拜占庭容错算法在实际系统应用中变得可行,主要是为了应用于不需要大交易量但需要处理许多事件的数字资产平台,每个节点都可以发布公钥,这是被允许的。节点将签名所有通过节点的消息,以验证其准确性。当得到一定数量的签名想用,此交易就被认定为有效

PBFT算法的运作原理为:

  1. 取一个副本作为主节点,其他的副本作为备份
  2. 用户端向主节点发送使用服务操作的请求
  3. 主节点通过广播将请求发送给其他副本
  4. 所有副本执行请求并将结果发回用户端
  5. 用户端需要等待F+1个不同副本节点发回相同的结果,作为整个操作的最终结果。

PBFT算法的主要优点有:

高性能的运算,将算法复杂度由指数级降低到多项式级,使得拜占庭容错算法在实际系统应用中变得可行。

主要缺点有:

  1. 计算效率依赖于参与协议的节点数量,不适用于节点数量过大的区块链系统,扩展性差。
  2. 系统节点是固定的,无法应对公有链的开放环境,只适用于联盟链或私有链环境。
  3. PBFT算法要求总节点数n>=3f+1(其中,f代表作恶节点数)。系统的失效节点数量不得超过全网节点的1/3,容错率相对较低。

其他算法

除了上述的共识算法外,还有许多基于上述理论进行优化改进的许多算法,在这里简单介绍一下:

  1. Solana采用历史证明(PoHistory,Proof of History)共识算法。其基本理念是不相信交易中的时间戳,而是证明交易在某个事件之前或之后的某个时刻发生。
  2. HyperLedger Sawtooth采用的所用时间证明(PoET,Proof of Elapsed Time)共识算法。PoET 共识机制算法通常用于许可区块链网络,它可决定网络中获得区块者的挖矿权利。许可区块链网络需要任何预期参与者在加入前验证身份。根据公平彩票系统的原则,每个节点具有同等的可能成为胜出者。PoET 机制赋予大量可能的网络参与者以平等胜出的机会。PoET 的工作机制如下:网络中的每位参与节点都必须等待一个随机选取的时期,首个完成设定等待时间的节点将获得一个新区块。区块链网络中的每个节点会生成一个随机的等待时间,并休眠一个设定的时间。最先醒来的节点,即具有最短等待时间的节点,唤醒并向区块链提交一个新区块,然后广播必要的信息到整个对等网络中。同一过程将会重复,以发现下一个区块。
  3. NEM采用的重要性证明(PoImportance,Proof of Importance)共识算法。NEM 共识网络不仅依赖于代币的数量,而且依赖于生成系统行动得到回报的可能性。区块收益机率是各种因素之一,此外还包括不好的名声(受控于不同的框架设计目的)、差额,以及从该处做出和得到的交易数量。它也被称为“重要性计算”(Importance Calculation),因为它可为“有用的”系统成员提供更全面的图像。
  4. IPFS Private Cluster、Quorum采用的RAFT共识算法。dRaft 是一种是设计用于替代 Paxos 的共识算法。它的本意就是通过实现逻辑分离,比 Paxos 更易于理解。但是它也可以通过形式化证明是安全的,并提供了一些额外的特性。Raft 提供一种在计算系统集群中实现分布状态机的通用方式,确保了集群中的每个节点在同一组状态转移上取得一致。它具有一系列的开源参考实现,包括 Go、C++、Java、Scala 等语言的完全声明实现。
  5. Neo采用的授权拜占庭容错算法,简称 dBFT,是一种支持通过代理投票实现大规模参与共识的拜占庭容错共识算法。在 Neo 中,令牌持有者可以通过投票选取其支持的 bookkeeper。之后,选定的 bookkeeper 组采用 BFT 算法达成共识,并生成新区块。Neo 网络中的投票是实时的,而非因人而异的。dBFT 可为具有个共识节点的共识系统提供容错。这种容错也涵盖了安全性和可用性、不受将军和拜占庭错误影响,并且适合任何网络环境。dBFT 具有很好的最终性(finality),这意味着一旦最终确认,区块将不可分叉,交易将不可再撤销或是回滚。

四、 讨论和对比分析

无论是在现实生活中,还是计算机世界里,共识算法达成共识都需要解决两个基本的问题:

首先,如何提出一个待共识的提案?如通过令牌传递、随机选取、权重比较、求解难题等;其次,如何让多个节点对该提案达成共识(同意或拒绝),如投票、规则验证等。理论上,如果分布式系统中各节点都能以十分“理想”的性能(瞬间响应、超高吞吐)稳定运行,节点之间通信瞬时送达(如量子纠缠),则实现共识过程并不十分困难,简单地通过广播进行瞬时投票和应答即可。

可惜的是,现实中这样的“理想”系统并不存在。不同节点之间通信存在延迟(光速物理限制、通信处理延迟),并且任意环节都可能存在故障(系统规模越大,发生故障可能性越高)。如通信网络会发生中断、节点会发生故障、甚至存在被入侵的节点故意伪造消息,破坏正常的共识过程。

此外,任何处理都需要成本,共识也是如此。当存在一定信任前提(如接入节点都经过验证、节点性能稳定、安全保障很高)时,达成共识相对容易,共识性能也较高;反之在不可信的场景下,达成共识很难,需要付出较大成本(如时间、经济、安全等)。

因此共识算法的设计通常需要考虑如何达成共识,算法的优劣决定于达成共识的速度、安全性以及达成共识的性能消耗。比如PoW算法,通常性能消耗较大,而DPoW考虑了采用其他区块通过计算得到的安全来减少性能消耗,PoS则通过权益证明避免计算来避免性能的消耗,同时也加快出快的速度,但不可避免的引入部分中心化的问题。而PBFT算法具有高性能的运算,但是容错率较低。

五、结论

区块链是一种突破性的技术,加密货币的普及,由信息的广泛传递转为价值广泛传递,区块链技术将在各个行业都得到适当的应用与实践。在上述讨论中,本文综述了共识算法在区块链中的应用,以及主流的共识算法:工作量证明算法、延时工作量证明算法、权益证明算法、委托权益证明算法、拜占庭容错算法的分析和对比。没有哪一种算法是完美适用于任何场景的,在速度,安全性和成本上总是会存在折中方案的处理,各有优劣。未来更多的是朝着混合方法的趋势进行发展。

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2022-05-31 16:33
  • 阅读 ( 1101 )
  • 学分 ( 40 )
  • 分类:共识

0 条评论

请先 登录 后评论
Responsibility
Responsibility

全栈

3 篇文章, 41 学分