Polkadot的区块最终确定性祖父协议GRANDPA：简介

祖父协议(GRANDPA)（基于GHOST的递归祖先派生前缀协议）在混合共识区块链中提供近乎即时的、异步的，负责任安全的最终确定性。在良好的网络条件下，我们几乎可以立即确定区块。在网络分区的情况下，当它们解析时, 我们可以一次性完成数以百万计的区块。一次完成的区块数与网络开销无关。本文是探讨Polkadot共识和最终确定性(finality)的一系列文章中的第一篇。任何花费足够时间研究区块链的人都会遇到，，甚至还有“”的概念。这些概念在理解区块链真正起作用时往往是一个很大的障碍。那么让我们从共识的入门开始吧。关于区块链共识的一个常见误解是它产生了有效的交易历史。实际上，任何人都可以在自己的计算机上进行一系列有效的交易。困难的部分是让每个人都同意使用有效的交易历史。这是需要的地方。经典的提供两个主要属性：安全性和活跃性。是确保诚实参与者不同意两个相互冲突的事物（在这种情况下是块）的属性(PS：保证决议结果是对的，无歧义的，不会出现错误情况)。是确保诚实参与者最终达成一致意见的属性(PS：保证决议过程能在有限时间内完成)。在区块链的背景下，安全与最终确定性是一回事。也就是说，一旦块完成，(canonical chain)将来总是包含该块。在区块链中，活跃意味着链条不断增长，而且有效交易最终将被包含并最终确定。所有共识算法仅在某些假设下提供这些安全性和活跃性。这些假设通常用系统中来表示拜占庭 - 有多少比例的参与者离线甚至是恶意行为。还有网络设定：传递消息需要多长时间，消息是否可以无序接收甚至丢弃。网络设定通常分为以下几类：

同步：消息始终在发送的某个时间T内传送，所有参与者都知道。

部分同步：存在一些已知的全局稳定时间（GST），在此之前消息可以被任意延迟，之后消息在T内传递。

异步：消息最后传递。

重要的是要注意，消息可以以不同的顺序传递给不同的参与者。这些网络设定也决定了拜占庭参与者的最大可能比例。当网络是或时，它必须。为了说明这是为什么，假设⅓节点是恶意的，并且需要绝对多数（> =⅔）才能达成共识。然后，恶意节点可以将剩余的1/3节点分成两组：A和B。恶意节点然后可以参与两个不同的绝大多数群组，包括A和B，导致安全违规。只有当A和B之间的通信延迟的时间长于达到的时间时，才有可能实现这种情况，这可能是和网络模型中的情况。

两组良好节点不能相互通信，但坏节点可以与两个组进行通信，并且每个组都以不同方式达成共识。如果只需要2/3的选票，这可能会导致安全违规。

应用于区块链时，请注意不会立即达到区块安全性。例如，在工作证明(POW)中，安全是技术上永远不会达到。相反，达到的安全性是概率性的，并且通过“共同前缀”属性进行竞争，该属性指出，如果每个诚实的一方忽略了他们链中的最后一个k块，那么他们在他们的链上达成一致的概率是压倒性的（足够多的选择k）。工作量证明和其他概率安全协议也有一点需要注意，即它们不提供，这意味着足够大的网络分叉或攻击可能导致混乱故障。

这里有很多链，但它们都有一个共同的前缀。POW共识确保了这一概率，而GRANDPA确保了这一确定性。

在中，我们要求参与者不要破坏安全属性和回撤已经达成一致的区块。与许多基于简单的设定的共识算法相反，我们实际上需要更强大的东西：负责任的安全性(accountable safety)。考虑一个安全的共识协议，除非⅓或更多的参与者行为不端。只要少于参与者的行为不端，那么一切都很好。但如果他们这样做，我们希望能够证明他们做到了。这是负责任的安全：如果他们行为不端，参与者可能会被追究责任（即有一些保证金被烧毁）。在负责任的安全性下，我们对有了更好的定义：除非系统中至少有1/3的股权被销毁，否则无法恢复区块。

负责任的安全：尽管恶意验证者(validators)分叉了网络，但是可以检测到他们的不当行为，并且可以在分叉的两侧削减(slash)他们的权益(stake)。不存在行为不当的节点侥幸逃脱的有效未来状态。

通常，提供的共识协议需要传递大量消息，以满足所有协议的要求。通常，需要在参与者之间发送的消息数量与协商一致协议中的参与者不成比例。这使得在每个块上执行这种协议的成本很高，正如在即时最终确定性协议类中所做的那样。因此，将与它们的分离通常是有益的。这种方法导致了区块链共识的双重方法：链增长系统 (chain growth system)和最终确定性配件 (finality gadget)。让最终确定性配件一次完成多个块有利于，因为它减少了必须在网络上的共识参与者之间传递的消息数量。这种混合模型可以使链的增长速度与Ouroboros (Ps: Ada的共识算法)或Aurand (Ps: 允许随机选择验证人出块，而不需要 2/3 成员的共识)等概率安全共识一样快，同时也提供与相同的安全保证。这就是我们在Polkadot中使用这种混合共识系统的原因。

活跃度(liveness)：我们可以持续扩展最终区块的那条链的属性

由于不会产生区块，我们需要另一种方式来考虑，我们之前将活跃度定义为共识过程输出某些内容的属性。相反，我们将最终确定性配件的活跃度属性视为依赖于的某些属性。这意味着，只要向链添加区块的方法以特定方式执行，最终确定性配件将始终具有新的事物去最终确定。这是一个非常强大的属性，因为它意味着我们总是能够向链中添加不可逆的事务。Polkadot使用基于上述描述的共识模型，这是一种混合模型，将区块生产与这些区块的最终确定分离开来。我们的目标是使区块生产层快速且具有概率安全性(probabilistically safe)。最终确定性配件应该是异步安全的，应该提供负责任的安全性，并且应该能够一次完成许多区块。我们发明了（基于GHOST的递归祖先派生前缀协议），这是一个提供了这些东西或更多的最终确定性配件。GRANDPA背后的关键想法是将区块链结构整合到共识算法中。一个直觉告诉我们，考虑一个区块有效意味着考虑该区块的父块有效，以此类推。以下是该算法的简化解释：我们允许参与者对他们认为有效的最高区块进行投票，而不是对单个区块进行投票，算法将该投票传递给该区块的所有祖先区块。然后，然后算法确定最佳区块>⅔绝对多数的选票，并产生。最终确定性证明是通过获得绝对多数投票，并将他们捆绑在一起形成一个单一的信息来构建的。签名聚合(Signature aggregation)可用于使其更小。

祖父协议GRANDPA计算出了链中有2/3以上的节点是哪些区块，并最终确定它们。它还可以为不同的节点不同的权重。这些权重可以由协议中记录的数量决定。在这个图中区块C、B和A被最终确定。

由于这种寻找绝大多数认为有效的最高共同祖先的策略，祖父协议GRANDPA也具体：它可以确定一个新区块，而不管上次区块确定之后已经经过了多少区块。如果网络延迟很低，GRANDPA几乎可以立即完成区块，并且当从很长网络分区恢复时，GRANDPA可以一次完成数百万个区块，而不会产生任何消息开销。找到所有参与者都能同意的区块链的公共前缀的操作被转换成快速找到公共前缀的投票过程。祖父协议GRANDPA的投票发生在，并且最终确定性没有在链上注册。然而，GRANDPA参与者被锁定在链上，并且相互矛盾的最终确定性证据将导致“模棱两可”或双重投票的参与者被发现和惩罚。发现哪些参与者双重投票的过程将在未来的文章中描述，并且包括链下的挑战 - 响应方式(Ps: 是零知识证明的方式)，只要最多2/3的参与者是恶意的，该过程就成功。GRANDPA只有在历史参与者受到惩罚的情况下才是安全的，因此属于“弱主观性”安全模式，参与者必须经历相当长的撤回期（可能是几个月）才能解锁他们的股权和获得回报。这只是祖父协议GRANDPA的预告篇。接下来的文章将深入探讨其内部运作，GRANDPA如何提供负责任的安全性，活跃度，处理动态验证集，基准性能等等。Rust的第一个实现正在https://github.com/paritytech/finality-afg详细描述了这个配件的文档在这里：https://github.com/w3f/consensus/blob/master/pdf/grandpa.pdf敬请期待更多的信息！了解有关Polkadot的更多信息：

[资源清单](https://github.com/w3f/Web3-wiki/wiki/Polkadot)

[白皮书](https://polkadot.network/PolkaDotPaper.pdf)

[Lightpaper](https://polkadot.network/Polkadot-lightpaper.pdf)

加入Polkadot社区：

[Riot](https://riot.im/app/#/room/#polkadot-watercooler:matrix.org)

[Twitter](https://twitter.com/polkadotnetwork)

[Reddit](https://www.reddit.com/r/dot/)

原文：Robert Habermeier翻译：姜富耀 | 0xThreeBody

Polkadot∣官方授权