类别:区块链 / 日期:2021-07-21 / 浏览:1013

原文题目:《什么是共识?(理论篇)》

做者:端豪

共识算法,能够理解为是为了实现散布式一致性协议而产生的一系列流程与规则。当散布在差别地区的节点都根据那套规则停止协商交互之后,最末总能就某个/某些问题得到一致的决策,从而实现散布式系统中差别节点的一致性。

起源

早期的计算机应用大都是单体架构,即单个处置器就可以承接所有的计算使命、读写使命等,那时候的计算机只需要负责将本身收到的使命按序施行、提交并返回即可,因而在阿谁期间,研究人员的次要研究内容是若何将单核处置器的性能优化到极致。然而,跟着互联网的呈现与开展,数据量呈现发作式增长,单靠一个处置器已经无法满足常规的营业需求,散布式系统架构横空出生避世。

散布式系统简单来说就是一系列处置器/节点通过动静交互的形式协同处置一系列的事务,从而到达横向扩展性能、提拔灾备属性的效果。为了可以到达横向扩展,需要所有节点共享不异的数据副本,天然而然地也就处理了单点毛病的问题。散布式系统极大提拔了单体架构的性能上限,但也不成制止地引入了散布式一致性问题。散布式一致性问题指的是:

在散布式系统中,当某些节点呈现异常时,若何包管整个系统对外的表示仍然一致。

那里需要存眷3个词语,即“某些”、“异常”以及“一致”。

一致:散布式一致性大致分为强一致性、弱一致性、最末一致性,因为各个分类涉及的细节较多,本文不做过多赘述。异常:在散布式系统中,差别节点凡是散布在差别的地区,因而统一时间差别节点的形态可能不受控。节点可能呈现一些良性错误,例如宕机、收集延迟/断开等;也可能呈现一些歹意错误,例如伪造动静、向差别节点发送差别的投票等。良性错误凡是是因为机器/收集毛病招致的节点暂时不在线,通过报酬介入是能够恢复到宕机之前的形态的,因而不会对整个系统的平安性形成威胁;而歹意错误也就是我们凡是所说的拜占庭错误,则可能因为某些节点的歹意攻击招致整个集群呈现不成预估的瓦解。某些:为了应对上述两种差别类型的错误(非拜占庭错误与拜占庭错误),我们需要设想差别的协议来处理/容忍有限量的错误。凡是来说,非拜占庭容错的共识算法可以容忍不超越1/2的节点呈现良性错误;拜占庭容错的共识算法可以容忍不超越1/3的节点呈现良性/歹意错误。

散布式系统的一致性问题早在上世纪七八十年代就起头了研究,奠基了十分扎实的理论根底,不外在后来相当长的一段时间内理论研究几乎停滞。曲到近年来,区块链系统的呈现又促进了散布式一致性问题研究的兴旺开展。本文将别离介绍散布式范畴内一些十分重要的模子假设/定理/理论等。随后,将从传统散布式一致性算法与典型区块链共识算法的角度分析共识算法的开展过程。

收集模子

散布式系统成立在许多通过收集毗连或者其他体例停止动静通信的节点之上,而收集通信的不确定性会限造共识算法的设想。通信模子定义了差别动静延迟关于散布式系统的限造才能。总的来说,一共存在三品种型的通信模子,别离是同步模子、异步模子与部门同步模子。

(1) 同步模子(Synchronous model)

在同步模子中,所有节点之间的动静通信都存在一个已知的延迟上界,而且差别节点处置事务的相对速度差值有一个已知上界。同步模子是一个十分抱负的通信模子,在现实生活中几乎不成见,但是在散布式系统的理论研究中却阐扬着及其重要的感化,许多早期的散布式一致性算法都是在同步收集假设下设想的。

(2) 异步模子(Asynchronous model)

在异步模子中,上述的假设上界都不存在,因而异步模子比力契合现实的互联网情况。异步与同步比拟,是一种更通用的情况。一个适用于异步系统的算法,也能被用于同步系统,但是反过来其实不成立。在异步模子中设想一个准确的共识算法已经被证明是不成能的。

(3) 部门同步模子(Partial Synchronous model)

部门同步模子是界于同步模子与异步模子之间的一种通信模子,于1988年由Dwork, Lynch等人在论文[1]中提出。该模子中假设存在一个全局不变时钟GST(Global Stabilization Time),在GST之前整个系统可能处于异步形态,但是在GST之后,整个系统能够恢复到同步形态。部门同步模子的时序假设比力贴合现实世界中对共识算法的需求,即共识老是能够在同步形态下完成,然而一旦收集呈现问题,共识可能会进入一段时间的阻塞,曲至收集恢复一般。

拜占庭将军问题

1982年,Leslie Lamport、Robert Shostak和Marshall Pease三位科学家颁发了一篇论文[2],提出了出名的拜占庭将军问题。拜占庭将军问题初次假设了散布式系统中存在歹意节点的情况,并给出了在同步收集模子下的解法(固然在此之前,同步模子与异步模子还没有明白的定义)。在拜占庭将军问题中,节点不行会呈现宕机或者断网等良性错误,还有可能呈现肆意情况的拜占庭错误,例如硬件或者软件毛病招致的节点不按法式逻辑运行,以至于节点法式被人歹意把持等等。总之,拜占庭错误愈加切近于现实生活中面对的毛病模子,同时它也是散布式系统中最难处理的毛病模子。

按照能否容忍拜占庭错误,我们能够将共识算法分为两类:

CFT类共识算法:仅可以容忍宕机、收集延迟/断开等良性错误的共识算法BFT类共识算法:除了可以容忍上述错误,还可以容忍肆意类型的歹意攻击的共识算法FLP不成能定理

1985年,Fischer、Lynch和Patterson三位科学家颁发了论文[3],提出了出名的FLP不成能定理。做为散布式系管辖域内最重要的定理之一,它给出了一个十分重要结论:在一个异步通信收集中,只要存在一个毛病节点,那么就不存在一种完美的共识算法能够准确的末行。

FLP的呈现,从理论的角度告诉人们能够不消再想方设法地去设想一个异步收集中始末可以达成一致的共识算法。因而,后续的共识算法设想中凡是会在某些方面做出妥协,例如收集假设不再是异步模子而是选择部门同步模子,即允许存在必然时间的异步收集形态,该期间无法达成共识,但是只要收集恢复到同步形态,就能够立即完成共识,如许固然关于系统的活性有必然的影响,但是只要可以包管系统的平安性,仍然是一个可承受的共识算法。

CAP理论

2000年,加州大学伯克利分校的Eric Brewer传授在ACM PODC会议上提出CAP料想。2年后,麻省理工学院的Seth Gilbert和Nancy Lynch从理论上证了然CAP。尔后,CAP理论正式成为散布式范畴的公认定理:一个散布式系统最多只能同时满足如下三种特征中的两种:

一致性(Consistency)可用性(Availability)分区容错性(Partition tolerance)

在散布式系统尤其是区块链系统中,营造一个高可用以至永久不会出错的收集情况需要付出昂扬的代价。因而一般来说,区块链系统必需满足分区容错性那一特量。那么关于区块链系统来说,就只能在一致性与可用性之间做出权衡与让步。例如大型公链系统中有成千上万的节点运行在世界的各个角落中,因而几乎不成能设想出一个强一致的共识算法包管所有节点同时对外供给一致的读写办事。PoW算法是通过牺牲强一致性,退而求其次地满足最末一致性、可用性与分区容错性。虽然PoW收集随时有分叉的可能性,即已经上链的区块有可能被回退掉,但是跟着时间的推移,靠前的区块得到越来越多确实认,那么其被回退的可能性就越来越低,以致于到达一种几乎不成能被回退的最末一致性。在此期间,每一个节点都能够一般的对外供给读写办事。

总结

通过前人的研究,我们已经可以大致理解了一个共识算法可以准确运转的前提:即在一个传统的散布式系统中,一个适用的共识算法需要可以平安地运行在部门同步收集模子中。其实,早期散布式一致性算法的研究大都集中在非拜占庭的部门同步收集模子情况下,例如典范的Paxos、ViewStamped Replication、ZAB等。曲到PBFT算法的提出,才呈现了第一个可适用的拜占庭容错共识算法原型。上述那些算法自己已经可以十分好地处理一致性的问题,因而在相当长的一段时间内,都没有新型共识算法被提出。但是近年来,跟着人们关于共识算法可理解性、易实现性、吞吐量等要求的不竭进步,涌现出了十分多优良的共识算法,例如CFT类的RAFT、BFT类的HotStuff等。

在区块链系统或者说比特币呈现之前,已经有十分多的应用从单数据中心单数据库形式改变成了多地多中心的散布式数据库形式,然而此类的应用凡是仍是摆设在统一个机构/公司内部办事器上。与此差别的是,在区块链如许一个承载着价值传输的散布式系统上,节点可能散布在全球各地,而且不受任何单一的机构/组织控造,因而区块链共识算法必需要考虑到歹意节点的存在,包管区块链上的价值不会被歹意节点把持,即区块链共识算法是需要容忍拜占庭错误的。而为了可以应对拜占庭攻击,差别的区块链系统走上了差别的道路。

在公有链中,常见的选择是通过工做量证明算法(PoW)来避免拜占庭攻击,因为每次合作出块权都需要处理一个十分复杂的数学难题,因而在那第一步就已经阻挠了绝大大都的攻击者;其次,每一个新构造出来的区块都必需颠末其他矿工节点的验证,因而不成能在区块中包罗不法/反复的交易;而若是想要伪造一条包罗不法交易的链,除非攻击者掌握全世界范畴内超越50%的算力,那显然是不成能的,即使存在如许一条链,一旦被发现有不法交易存在一定会招致该链诺言的下降从而招致巨量的丧失,那关于攻击者来说显然也是不合算的。最末,上述的规则会引导所有测验考试出块的节点都到一条“准确的最长链”上合作,因为如许做才是利益更大化的选择。

在联盟链中,常见的选择是通过理论完整的BFT共识算法来避免拜占庭攻击。因为联盟链的共识节点凡是由参与方机构办理,因而准入门槛自己就比力高;其次,联盟链中的共识缺乏经济鼓励,因而需要通过更强的理论来停止约束。然而完全根据一个共识算法的原型来实现的话,照旧会存在一些问题。例如,传统PBFT算法中主节点是固定的,若是可以控造主节点,即使不让它打包不法交易,也能够控造它偏向性地打包某些账户的交易,从而招致其他账户的交易被阻塞而无法上链。因而,在应用BFT共识算法的过程中,还需要为区块链特征加上一些特殊的功用,例如选择不成预测的主节点,为节点加上诺言值从而通过诺言值来选择主节点等。

  • 随机文章

  • 热门文章

 可能感兴趣的文章

最近发表