Polkadot共识四部曲

作者:Joe Petrowski  时间:2020-01-01  分类:波卡(Polkadot)新闻  
Polkadot共识第1部分:简介

  本系列文章将讨论Polkadot的安全和共识。在第1节深入介绍Polkadot如何创建和保护区块之前,定义一些术语。

  

  共识算法帮助计算机网络像一台计算机一样运作。实际上,这意味着网络中的几乎所有计算机都必须同意某个初始状态,然后对初始状态的确定性操作日志达成共识,最终达成相同的状态。

  虽然区块链给共识算法带来了一些有趣工具,但协调问题不是如今才有的问题。最早追溯到航天,由于太空比较荒凉,卫星或高空飞机上的计算机可能会出现不一致。试想一下,你手上有一个飞行计算机网络,想知道飞机的前进方向。无论询问网络中的哪台计算机都没有关系,因为你始终会得到相同的响应。

  这与区块链有何联系?我们同样希望计算机网络就某些值达成共识。这个值可以是帐户余额,表决结果或智能合约的执行结果。

  实际上,之前的一些共识算法类似于区块链。早在2001年的一场演讲中,麻省理工学院的教授芭芭拉·里斯科夫(Barbara Liskov)谈论了批量交易是如何提高实际拜占庭容错(PBFT)性能的,当时还没有比特币。

  “想象一个非常忙碌的主站(primary),一个接一个的请求令它应接不暇,但这个主站实际上并没有为每个请求启动协议,反而是,它收集一批请求,并针对其中一组请求执行一个协议...因为没有必要每个人都给客户端发送回复。如果其中一位发送回复摘要便足以,因为已足以使客户端知道是否是一致的答复。”

  PBFT提供了一组规则,就状态更改达成共识,甚至是就一批状态更改达成共识。

  打破区块链共识

  在区块链这样的分布式系统,需要回答下述几个问题:

  1.谁可以提出下一次更改?

  2.哪一组更改为最终更改?

  3.如果有人打破规则会怎样?

  尽早区分上面三个问题,因为许多区块链共识都是统一的。例如工作量证明,根据证明来筛选合适的区块归属者;最长链决定最终链条;计算证明的成本作为违反规则的惩罚。在波卡,上面三个问题都是孤立解答的。

  非区块链系统仍然需要解答这三个问题。例如,假设所有计算机都运行相同的软件。在大多数情况下,这是没问题的。例如波音公司制造了一架飞机,则可以假设他们对飞机上的所有计算机进行了编程。

  但是,在公共网络中,我们无法做出这样的假设。区块链利用经济学简化了一些网络假设,所有共识系统都存在“良好”和“作恶”行为。区块链的内置经济属性能奖励良好行为,惩罚作恶行为。PoS网络利用经济作为直接手段,确保达成共识。

  区块链系统中的安全性是衡量打破共识的难度。权威证明(proof of authority),安全性是掌控权威的难度。在工作量证明中,安全性是获得和运作大量哈希算力,创建比网络更长链的成本。在权益证明中,安全性是抵押价值和风险价值。

  Parity技术和Web3基金会成员开发实现了一个算法库来解决共识和安全性问题。在本系列文章中,开始,我们将先介绍最终性算法GRANDPA,因为所有区块生产算法都必须遵守最终性(头等仓注:finality,最终性指就区块最终状态达成共识)。之后,我们将讨论区块生产引擎BABE,以及如何将区块添加到链中。最后,我们将讨论如何使用经济学来保护GRANDPA和BABE。

  Polkadot共识第2部分:GRANDPA

  在序文当中,我讲到了一种共识算法可以帮助计算机网络回答三个问题。GRANDPA便是解决第二个问题。

  

  在序文当中,我讲到了一种共识算法可以帮助计算机网络回答三个问题。

  GRANDPA便是解决第二个问题。

  1.谁可以提出下一次更改?

  2.哪一组更改为最终更改?

  3.如果有人打破规则会怎样?

  GRANDPA是Polkadot一款决定区块最终性的工具,作用是选出权威链。换句话说,GRANDPA决定哪条链为最终链。它不会自行生产区块,而是,GRANDPA验证人从另一个区块生产模块(我们将在第3部分中讨论)中导入区块。

  分离区块生产和安全性的好处之一,除了可以有优良的工程设计外,GRANDPA对导入的区块没有很多限制。GRANDPA仅要求区块生产系统生产的区块是安全的,遵循GRANDPA的分叉规则,并且区块头必须具有指向其父区块的指针,确保轻客户端可以跟上链条的进度即可。

  GRANDPA协议

  GRANDPA与其他拜占庭式容错算法不同之处在于,验证人是对区块链投票,而不是对区块进行投票。GRANDPA间接地应用投票,GRANDPA算法寻找有足够选票,且足以认定为最终区块的最高区块号。在寻找区块的过程中,一轮可以确定好几个最终区块。

  最后一部分很重要,因为它消除了妨碍其他区块链终结性小工具的瓶颈。与其他PBFT衍生协议一样,GRANDPA的复杂度为O(n²)。也就是说,如果将节点数增加一倍,发送的消息数会增加四倍。共识系统将区块生产与最终性流程分离,使你可以给每个区块发送消息。通过将区块生产隔离在另一个模块中,生产区块的效率变高了(BABE为O(n)),并在一轮中可以最终确认其中的好几个区块。让我们来看一个示例,检查Kusama节点中的以下日志消息:

  

  发现在一轮中,GRANDPA最终确定了三个区块(664,254至664,256)。

  

  上图日志消息显示了GRANDPA如何在一轮中确定多个区块。左侧的深灰色方块是先前最终确定的区块,验证人(右侧的灰色椭圆图形)给新一轮区块生产发送选票。其中三个区块获得了多数选票,被最终确定。

  GRANDPA轮

  选民执行以下流程来确定新区块:

  1.被指定为“主”节点的节点广播它认为继上一轮后,这一轮可以被最终确定的最高区块。

  2.等待网络延迟后,每个验证人会为自己认为应该是最高的区块广播一个“预投票”。如果绝大多数验证人是诚实的,则将有最多广播数的区块添加到区块链上。新链会比上一次最终确定的链长出几个区块。

  3.每个验证人根据预投票集,计算出将得到最终确定的最高区块。如果预投票集延长了上条最终确认的区块链,则每个验证人都将对这条链投递“预提交”。

  4.每个验证人等待接收足够数量的预提交,在新确定的链上提交消息。

  与其他拜占庭容错算法(例如PBFT和Hotstuff)相比,细微且重要的一点区别是,在关键路径上没有视图变化。尽管每轮的最高区块发生更改,但视图更改只在异步网络情况下,开启新一轮,因此在部分同步网络中,即使在没有分配最高区块的情况下,协议也会不断更新。

  如果协议中有2/3以上的预投票或预提交来自验证人,协议的步骤就完成了。为了确定最终性,必须限制验证人集的投票数。与以概率来确定最终区块的链不同,这种链有无数验证人集。GRANDPA协议并没有定义选择选民集的方法逻辑(参加第4部分)。

  GRANDPA支持加权投票。例如,你可以在自己的链上应用GRANDPA协议,这样验证人如果有更多的stake,就能获得更多投票。但在Polkadot中,所有验证人的加权投票都是均等的。这种均等加权经济策略,可以防止少数节点获得较大的网络份额。

  安全责任:当发生问题时谁来负责?

  GRANDPA具有一项称作“安全责任(accountable safety)”的功能,让验证人对违反安全性的行为负责。当两个区块在不同的链上被最终确认时,会产生安全冲突。安全责任就扮演类似一场事故调查的作用。

  首先,两条相互矛盾的链是如何达成最终性的?拜占庭共识系统始终基于以下条件:拥有容错验证人的最大数量是总验证人数量的一部分(在波卡当中占比1/3)。如果让两条相互矛盾的链达成最终性,验证人集不能满足“容错验证人的最大数量是总验证人数量的一部分”这一要求;至少1/3的验证人对这两条链都进行投票。

  

  在此示例中,有10位验证人,这意味着3是系统可以承受的最大容错验证人数(f =(10-1)/ 3)。有了4位容错验证人(红色)在一个网络分区,每组诚实的验证人(蓝色)可以认定不同的区块具有最终性。

  在两个相互冲突的链上进行投票的行为称为equivocating(相互矛盾)。公认的一个事实是equivocating是对拜占庭容错系统的冒犯。在GRANDPA系统中,我们可以检测出equivocating。

  首先,我们先询问节点,为什么投票给第二个区块(认为第2个区块具有最终性),却不投给第一个区块。所有的诚实验证人(大多数认为第2个区块具有最终性)都需要在第二轮用一组预投票或预提交来回答第一个问题。

  如果没问题,接着我们会提问第二个问题:你看到过第1轮的哪些投票?我们实质上是在要求他们告发其他验证人,并透露他们从对等节点那里获得的所有投票。结合两个问题,就能找出为两条冲突链投票的验证人。在假定的情况下,他们将受到重罚,但这是区块链工作的逻辑,共识不是这种逻辑。

  如果出现安全错误,网络必须执行硬分叉选出最终链。有了安全责任功能,Polkadot可以确保对发起攻击的验证人进行惩罚,并踢出验证人集。

  GRANDPA如何验证可用性和有效性?

  还记得上面提到的日志消息吗?注意一点,最终区块落后最佳区块后面两个区块。实际上,这种滞后保证区块生产和最终性有所区分。

  

  包括Polkadot在内的区块链互操作性系统都存在数据可用性问题。想象一位整理者提交一个区块给验证人,但是其他平行链整理者都没有看到这个区块。如果提交区块的整理者离线了怎么办?验证人有责任在一段时间内存储完整的区块,以便任何平行链整理者都可以请求区块。

  验证人应该先执行区块,再给区块投票,但我们想确保他们这样做。Polkadot中有许多名叫“渔民”的节点,它们的作用是执行区块并报告任何验证程序异常的行为,例如提议将无效的平行链区块打包进中继链。

  绝不希望出现的情况是:最终确定的是一个无效区块,或者最终确认的区块排序器无法重构。通过保留落后链尖端几个区块的最终性,可以让渔民来验证区块的正确性,并质疑验证人区块的可用性。

  我们一直在讨论如何确定规范链,但是这些链选项有哪些来源?这就是需要BABE的地方。请参阅本系列文章第3部分。

  要了解更多关于Polkadot的共识和经济学,请访问https://wiki.polkadot.network/docs/en/

  扫码添加管理微信,邀请你加入

  Polkadot社区群

  

Polkadot共识第3部分:BABE

  本文为Polkadot共识系列文章的第3部分。有关简介的内容,请参见第1部分,有关GRANDPA 的讨论,请参见第2部分。

  

  区块链扩展盲分配(BABE)是一种区块生成机制,其灵感来自另一种PoS协议Ouroboros Praos。由于它可提供概率确定性,因此它可以单独使用,也可以与GRANDPA这样的确定性小工具结合使用。

  BABE是一种基于slot(插槽)的算法。它把时间划分成若干个epoch(纪元),每个epoch再划分成若干个slot。在Polkadot中,每个slot的持续时间为6秒,这也是我们的目标出块时间。BABE将选择一个(或多个)区块创建者在每个slot中创建区块。

  

  BABE的时间被划分成若干epoch。每个epoch又包含若干个slot。向这些slot分配区块创建者的其中一种方法就是通过简单轮流制。然而在循环模式中,攻击者总是能知道下一位创建者是谁,并可以使用该信息来协调发起攻击。而在理想情况下,应没人能够知晓该slot的创建者是谁,除非该创建者提供证据证明。

  每个slot可以有主创建者和次创建者(或叫“slot领导者”)。slot主领导者是随机分配的。但由于函数是随机的,所以有时会出现有些slot没有领导者的情况。为了确保一致的出块时间,BABE使用循环系统来分配slot次领导者。

  Slot主领导者

  主领导者的分配基于可验证随机函数(VRF)的评估。关于区块链随机数的说法天花乱坠,简而言之,许多应用程序都依赖于随机数的生成,但是当所有链上操作都必须是确定的且可验证的时,就很难认定每个人都认可的随机性(而不是为了使生成器受益而进行的游戏)。

  VRF会生成伪随机数及其正确生成的证明。其他VRF都将一些参数(包括私钥)作为输入。而我们的VRF则将epoch随机种子(事先通过所有节点认可)、slot编码和创建者私钥作为输入。由于节点不会拥有相同的私钥,所以每个节点都可以为每个slot生成唯一的伪随机值。

  每个创建者要对每个epoch中每个slot的VRF进行评估。对于每个输出低于某个商定阈值的slot,验证者有权在该slot中创建区块。由于slot分配过程是随机的,因此可能会出现有些slot没有主领导者,或有些slot有多个主领导者的情况。接下来再说说如何处理这一问题。

  

  BABE中的VRF以epoch随机性、slot编码和验证者私钥作为输入,并为epoch中的每个slot输出一个值。当区块创建者的输出低于网络阈值时,它将生成一个区块作为该slot的主要区块领导者。

  Slot次领导者

  为了处理空slot的问题,BABE使用了循环后退方式。每个slot都有次领导者。如果主领导者没有在slot开始时站出来,那么就由次领导者创建区块。这种后退方式将确保每个slot都有一个区块创建者,并有助于确保一致的出块时间。

  将BABE与GRANDPA相结合

  到目前为止,我们已经有可确定最终链的GRANDPA,以及可创建新块的BABE。由于单个slot可以有多个领导者,因此BABE的某些链也会产生分叉。

  选择最佳延伸链的第一条规则很简单:BABE必须建立在由GRANDPA最终确定的那条链上。这是使用GRANDPA的要求之一。

  使用GRANDPA的第二个更微妙要求是,区块生成算法必须能够选择“最佳”链。此属性使得BABE具有概率确定性(因此,你可以在不使用GRANDPA的情况下使用它)。

  BABE中的最佳链就是由主领导者创建最多区块的那条链。

  

  选择最佳链的BABE分叉选择规则示例

  在BABE中,分叉十分常见。正如GRANPA一文所述,区块生成是O(n),这意味着创建者只需向所有人广播其区块,而不需要每个人都互发消息(就好比GRANDPA)。因此,并非每个人都对未最终确定的链看法一致(如图中黄色块)。

  该系统使我们能够高效生成区块,并使GRANDPA进行最终确定。

  那该依据谁的时钟?

  我们根据时间分配slot,但我们没有单一的时间观念。每台计算机都有自己的时钟。我们不能使用中心化时间服务(称为NTP服务器),因为这会造成单点攻击。攻击者可以向NTP服务器发起攻击,可能切断它也可能夺取它的控制权,以达到更不道德的行为,比如向不同的节点发送不同的时间。

  可以想象以下场景,我收到你发来的信息,说现在是“8:42:00。”而我的时钟显示是8:42:03。那么有三种可能:

  1.我们的时钟是同步的,网络传递你的消息只花了3秒钟。

  2.实际上网络传递你的消息花了1秒钟。我们的时钟差了2秒钟。

  3.你在骗我,你的时钟并不是这个时间。

  

  现在假设我的时钟显示我8:41:59时收到了此信息。假如我相信你没有说谎,那么我就知道我们的时钟不同步,我必须把我的时钟往前调一点。但我仍然不知道通过网络传输需要花费多少时间,我也就不知道我们到底有多不同步。

  而BABE则使用相对时间将slot编码与一台计算机的时钟对齐。当某节点收到一个区块时,它将检查接收时间和与该区块相关的slot编码。然后,它会将slot编码添加到每个区块上,并使用其数据中的中值来预测未来slot。请记住,验证者会预先知道要为其创建的slot编码,因此他们可以对此进行检查。

  

  BABE中的区块创建者使用区块接收时间来创建网络时间视图。他们根据slot时间将接收时间映射到未来,以确定何时应创建并发起一个区块。

  到目前为止,我们已经讨论了链是如何产生的(BABE)以及它们如何被最终确定(GRANDPA)。我们要解决的下一个问题是,如何使人们以正确的方式运行这些协议?本系列的最后一部分将讨论运行时如何为运行BABE和GRANDPA提供激励,以及发生错误时会有什么惩罚。

Polkadot共识第4部分:安全性

  这是Polkadot共识系列的第4部分。有关简介请参见第1 部分,有关GRANDPA的讨论参见第2 部分,有关BABE的讨论参见第3部分。

  

  到目前为止,我们已经讨论过BABE是如何创建区块链候选者和GRANDPA如何最终确定它们。我们知道我们需要超过三分之二的验证者来正确遵循协议。但是,到底有多少验证者呢?他们是如何被选择的呢?他们为什么要遵守规则?

  选举周期

  为了让验证者知道一个区块具有超过三分之二的协议,GRANDPA 需要知道总共有多少个验证者。该链的治理流程设置(并可以更改)数量,目标是至少有 1000 个验证者在Polkadot中运行BABE和GRANDPA。

  一旦我们知道了集合中有多少验证者,我们将举行一次选举来决定谁将成为验证者。就像 BABE 将时间拆分为周期一样,GRANDPA也将时间拆分为各个周期。在每个周期结束时,都会奖励过去的周期,并为下一个周期进行选举。周期长约 24 小时。

  Polkadot使用提名权益证明(Npos)来选举验证者,并使用Phragmen的方法来进行选举。简介部分讨论了PoS网络中的安全性与风险价值有关。用户通过锁定资金(称为staking)来表明其参与网络安全的意图。

  虽然验证者的数量是有限的,但是可以通过staking参与网络安全的人员的数量却不是。如果你不是验证者,你仍然可以通过提名参与。提名者质押(stake)他们的代币,然后选择 16 个值得信赖的验证者作为自己的代表。提名者能享受他们所支持的验证者的收益,同时也会连带受到惩罚。

  Polkadot的一个功能性目标是形成一个均匀质押的验证者集。奖励是根据绩效来支付的,因此提名者如果支持一些较小的验证者,将有概率可以获得更高的回报率。

  我们使用Phragmen 's方法优化了这种质押分配。在选举之前,有一个希望成为验证者的帐户列表。每个验证者都有一个潜在提名者列表。Phragmen的方法将首先通过找出最具价值的组合来选择赢家。一旦它知道了提名集,它将以这种方式来申请提名,这种方式会使提名集得到最均衡的质押。这样的结果将为网络带来最高的安全性,并为提名人带来最大的回报。

  奖励

  奖励是人们在网络上运行验证者的主要激励因素。正如在第2部分和第3部分中所讨论的,验证者运行BABE和GRANDPA协议来创建和完成Polkadot区块链。

  与其他PoS协议不同,Polkadot会根据验证者活动而不是根据每个验证者的质押金来确定奖励。验证者根据它们的活动累积积分。积分分配主要根据有效性声明和常规链中生成的区块。还有一些积分是为没有在常规链中终止区块而发出的。

  当大家明确了一个周期内总积分的量后,也只有到一个周期结束之后才能转换为相应的代币价值。在一个周期内奖励分配是根据验证者所拥有的积分在总周期积分内的占比。之后再将奖励分配给每个验证者的提名者。

  遵循奖励制度相对容易。通过运行标准客户端和拥有高可用性网络体系结构,验证者将能够正确地遵循协议并获得积分。

  规则和惩罚

  奖励提供了质押的理由,但网络必须确保质押者遵守规则,削减代币(Slashing)是对不遵守规则者的惩罚。网络的安全性要求对企图攻击者的惩罚要大到足以防止攻击的发生。

  违规的范围从明显的懒散到彻头彻尾的欺骗,验证者最基本的要求是在线可用。验证者通过创建区块或向网络发送消息来证明它的可用性。因为每个系统都可以在合理的范围内经历周期性的停机,因脱机而被惩罚的概率非常低。但是,只要验证者正确地处理它们的基础结构配置,停机就应该是一种罕见的事件,而且停机时间足够小的话,是很容易恢复的。

  更严重的违规行为被认为是模棱两可。在BABE和GRANDPA中都可能发生模棱两可的情况。在BABE中,模棱两可在同一个槽位(slot)中生成两个区块。在GRANDPA中,则会为同一回合中相互冲突的两条链发送预投票或预传递信息。模棱两可往往伴随着严重的惩罚。如果有过多模棱两可验证者,则不可能选择单个规范的链。

  有些行为可能会被削减(slashed)100%的质押金。这些操作将在极端情况下使用,例如对与已结束的链冲突的进行预投票或预提交。网络认为这种行为是一种攻击,因为它试图逆转已确定的区块。

  超线性削减(Slashing)

  你可能已经注意到奖励与质押无关,所以如果你有足够的代币来运行两个验证程序,你的奖励可能会加倍。

  这种行为是值得被鼓励的。我们希望单个实体(无论是大量代币持有者还是作为服务提供者的公司)运行多个验证程序。对于阻止某些实体获得大量质押并运行验证程序,Polkadot是无能为力的。为了防止单个实体获得过多的权力,Polkadot可以让他们在尝试做破坏时增加其风险值。

  Polkadot使用超线性削减机制。随着实质犯罪的验证者的数量增加,代币削减的百分比也跟着增加。如果单个验证者模棱两可,则可能是由于基础设施设置不佳所致。然而,如果 30%的验证者在一回合中模棱两可,则更有可能是协同攻击,所以惩罚力度也会跟着加大。

  

  随着更多验证者的模棱两可,惩罚严厉的程度越来越高。当超过 33%的验证人模棱两可时(此事件将使网络中断),违规者将被代币惩罚力度将至 100%。

  当单个实体向网络添加更多验证程序时,它将必须确保验证程序不依赖于彼此或任何集中式的服务。

  共享安全

  POS网络中的安全性是依赖于经济学,因此世界上只能存在有限数量的安全性,因为根据经济学定义,经济价值是有限的。由于单链扩展问题带来了区块链数量增加,其经济价值和安全性分散在多条链上,每条链的价值都更加分散,使得每个链都比之前更脆弱。

  在共享执行环境中执行的智能合约(如以太坊虚拟机)可以在无信任的情况下进行交互。使用Polkadot,可以将逻辑接口从区块链中的单个执行环境移动到区块链的逻辑本身。

  但是,当考虑如何在打破信任界限的同时使链进行交互时,必须意识到信任不是来自在同一环境中执行。信任来自在相同的经济和国家过渡保证下运作。

  Polkadot引入了一个共享的安全模型,这样链就可以与其他链进行交互,同时充分认识到其他链与自己的链具有相同的安全保障。基于桥的解决方案——每个链都处理自己的安全性——迫使接收者信任发送者。Polkadot 的安全模型为跨链消息传递提供了必要的安全保证,而不必去确认信息发送链自身的安全状况。

  中继链区块通常由平行链的有效性证明组成,这意味着当中继链验证平行链的状态转换并在最终的中继链中包含证明时,平行链的块也是最终的。要还原平行链的区块,攻击者必须还原整个 Polkadot 系统,包括增加每个单独的平行链和安全化竞争。

  这种通过在中继链中共享状态来共享安全性的系统,甚至不需要平行链提供自己的安全性和验证者社区的安全性。Polkadot的中继链提供了这种经济保障,因此Polkadot生态系统中的链可以专注于发展其应用的逻辑。

  

版权信息
作者:Joe Petrowski
来源:Polkadot社区

关于我们

联系我们

作者进驻

公众号

Copyright © 2013 比特巴 www.btb8.com
只为您提供客观公正有用的比特币 区块链 加密数字货币新闻、技术教程、行情分析、行业人物资讯
手机版