Polkadot v1.0:分片和经济安全(3)

链得得的朋友们
链得得的朋友们

Jan 27, 2022 链得得的朋友们

摘要: 本篇是该文章的第三部分,介绍了批准检查机制 —— Polkadot 的主要欺诈检测机制。

作者:Rob Habermeier 

文章来源:PolkaWorld

本文是由 Polkadot 联合创始人 Robert 发布的关于 Polkadot v1.0 的分片和经济安全的技术文章,原文篇幅较长,PolkaWorld 将分四篇翻译和发布!本篇是该文章的第三部分,介绍了批准检查机制 —— Polkadot 的主要欺诈检测机制。

查看本文的前两部分:

第一部分:Polkadot v1.0:分片和经济安全(1)

第二部分:Polkadot v1.0:分片和经济安全(2)

批准检查和区块终结

批准检查(Approval Checking)是一种机制,即验证人随机选择检查可用的平行链区块,并将其检查的意图和结果传达给网络的其余成员。

现在,让我们将批准检查的实际过程看作一个黑匣子。我们将首先介绍一些背景知识,来了解我们希望这个协议做什么,以便稍后你能清楚为什么它要以这种方式运行。

正如我们已经了解的那样,每个验证节点都参与了 GRANDPA,即区块终结工具。GRANDPA 以轮次进行,我们可以将每个验证人在每个 GRANDPA 轮次中所做工作进行高度简化,视为以下步骤的重复:

  • 下一轮开始

  • 选择要终结的目标区块:我们希望终结的最佳区块

  • 对终结目标进行投票

  • 等待其他验证人的投票

  • 找到出现在验证人投票的至少 2/3 链中的最高公共块

  • 终结该区块

  • 回合结束

验证人在这个过程中唯一的灵活性是在第 2 步:选择要投票的区块作为其终结目标。这种选择被称为投票规则。在基本的 GRANDPA 中,每个验证人只需选择其所知的中继链里最长的分支,并提交该链的块头作为投票。但是,对于平行链共识,我们引入了新的投票规则。

GRANDPA 批准检查的投票规则规定每个验证人应该:

  1. 选择中继链最长的分支

  2. 找到该链中最高的区块 B,使得当前终结的区块和 B 之间的每个区块,仅触发对平行链区块的包含,并且验证观察到这些区块已被足够多的验证人批准。

我们把这个过程分解一下。请记住,主要目标是让网络只终结真正好的平行链区块,并且让每个验证人做尽可能少的工作,以便网络可以扩展。拆分开来看就是:

  1. 找到该链中最高的区块 B我们希望每个节点投票,选出符合其他标准的最高区块,以便尽可能快地推进终结过程。

  2. 使得当前终结的区块与 B 之间的每个区块:投票规则需要验证人对仅包含良好平行链区块的链进行投票。在 GRANDPA 中,对区块的投票被视为对其所有祖先的投票,因此即使区块 100 仅包含良好的平行链区块,区块 99 和 98 也不一定如此。因此,投票规则需要找到通过其他标准的中继链区块的最高连续链。

  3. 仅触发对平行链区块的包含回到平行链扩展的部分,这里所说的是,平行链区块已通过中继链区块中的可用性证明变得可用,并且平行链区块已添加到平行链。尚不可用的平行链区块还不算作平行链的一部分。

  4. 验证人观察到这些区块已被足够多的验证人批准这指的是我们将在下面描述的批准检查机制,这种方法让验证人不必自己检查,只需依靠别人的检查就能高度相信某个平行链区块是好的。

下面是 3 个例子,说明如何应用投票规则,来选出要终结哪些区块。

在第一个例子中,显示了连续性的特性,以及我们选择最佳链的祖先。

在第二个例子中,我们投给已终结的区块,因为这两条链都不可终结。

在第三个例子中,整条最佳链都是可终结的,因此我们选择投票给它。

最后,值得注意的是,这个投票规则是一个在每个验证人上运行的过程,并且他们都可能根据自己看到的中继链区块和批准消息,对终结目标持有不同的看法。但这很适合 GRANDPA:如果所有诚实的验证人都运行这个投票规则,那么除非 2/3 的节点都同意它可以终结,否则任何中继链区块都不能终结。

批准检查会稍微减慢区块终结速度,但只是一点点。平行链允许有大约 3 秒的执行时间,恢复数据大约需要 1 秒,扩散消息又需要几秒。在乐观的情况下,这意味着它给区块终结增加了大约 5 秒时间。这是真正的终结,背后承载 Polkadot 的全部重量。

那么,让我们深入批准检查的过程,以及节点实际都做了些什么来了解哪些平行链区块是好的,并且已经被足够多的验证人检查过了。

批准检查的特性及安全性

批准检查是验证人为每个平行链区块而运行的子协议。

每个验证人节点都在为每个中继链区块中的每个平行链区块运行批准检查过程。这个过程有几个特点:

  1. 任何特定节点上的过程要么输出“好”,要么停止。

  2. 如果平行链区块是有效的(即通过了检查),那么它最终会在诚实节点上输出“好”。

  3. 如果平行链区块无效,那么它在诚实节点上输出“好”的概率很低

请注意,无效情况下的“低概率”大约是数十亿分之一,具体取决于验证人数量和最小检查者数量等变量。这并不是密码学意义上的低概率,但却适用于加密经济学。

Polkadot 的安全论点基于 Gambler’s Ruin(赌徒破产理论)。虽然攻击者确实可以进行数十亿次尝试,来暴力破解该过程,并且最终会成功,但我们将此过程与 Slash 惩罚系统相结合,以确保每次失败的尝试,都会罚掉攻击者验证人的全部抵押。Polkadot 是一个权益证明网络,在撰写本文时,每个验证人都有大约 200 万个 DOT 的抵押。通常情况下,每次失败的尝试都会导致 10 或 20 个验证人被 slash。但即使只有 1 个验证人被 slash,攻击者的资金也明显会在攻击成功之前迅速耗尽。

我们通过批准检查的其他一些特性来实现这一点:

  • 验证人检查平行链区块的任务是保密的,直到他们自己披露为止。

  • 验证人的分配是确定性生成的。

  • 验证人在恢复执行这些检查所需的数据之前,会广播其检查平行链区块的意图。

  • 当验证人广播检查平行链区块的意图然后消失时,这会导致更多诚实的验证人开始检查。

特性 1 确保攻击者不知道要 DoS 攻击谁来阻止他们检查区块。

特性 2 确保就算攻击者幸运地“中奖了”,并且有足够多的恶意节点来说服诚实节点,使其相信已经检查了某些内容,也很可能有诚实节点会与他们一起进行检查,并且这些诚实节点将发出警报。

特性 3 确保诚实节点不会因为向恶意节点请求数据,而意外地暴露自己的检查者身份,然后在没有人注意到的情况下被对方离线。即,如果攻击者试图让检查者保持沉默,它会被其他人注意到。

特性 4 确保看似已被 DoS 的节点将被更多节点替换。批准检查就像九头蛇:如果你砍掉一个头,就会出现另外两个头。

下一节将更详细地介绍批准检查的实际工作原理。

验证人会检查什么?

这里验证人的目标是确定支持验证人是否参与了任何不当行为。这需要 3 个步骤:

  1. 下载 PoV 数据以检查区块。这是通过获取 1/3 的区块并将它们组合以形成完整数据来完成的。

  2. 确保 PoV 数据对应有效的平行链状态转换。

  3. 确保平行链区块头提交的所有输出确实与平行链区块执行的输出相匹配。

假设> 2/3的节点是诚实的,并且已经承诺拥有数据块,那么恢复可用性永远不会失败。这就是为什么仅对可用的平行链区块进行批准检查的原因。

但是,步骤 (2) 和 (3) 都可能失败。当步骤(2)失败时,表明状态转换本身就是垃圾。当步骤(3)失败时,表示状态转换成功,但中继链上记录的状态转换输出信息是错误的。

在步骤 (3) 中要注意的一个重要情况,是平行链块头包含对所有纠删码块的承诺。我们让验证人在恢复 PoV 数据后进行额外检查,即将 PoV 转换回其纠删码形式,并确保块头中的承诺与所有区块匹配。如果没有匹配,这可以避免一种攻击,攻击者可以有选择地选择哪些验证人可以恢复数据。攻击的工作方式是这样的:攻击者将数据分成很多部分,并用垃圾替换除 1/3 之外的所有部分。它将 1 个有效部分分配给诚实的验证人,并给另外 1/3 的验证人垃圾数据。恶意的 1/3 验证人保留了其余的带有可用数据的部分。这意味着有足够的验证人 (2/3 + 1) 会认为该数据有效,但如果恶意验证人拒绝回答有关其 1/3 好的部分的请求,则只有垃圾可用。检查数据的重新编码是否确实与承诺相匹配,可以彻底击败这种攻击。

如果步骤 (2) 或 (3) 中的任何一个失败,检查者将提出争议并将区块升级到所有验证人以执行相同的检查。稍后我们将了解争议问题,并探讨它究竟意味着什么。

何时检查

了解批准检查系统的关键见解之一,是每个验证人都被分配检查每个平行链区块,但问题是何时检查。如果验证人在自己的检查时间之前发现平行链区块已获得批准,那么他们根本不检查并继续前进。

从 Unix Epoch 开始,时间被划分为 0.5 秒的离散刻度。0.5 秒的选择是基于小消息通过 gossip 网络传播的预期时间。

验证人打算检查平行链区块的时间是在表示在 delay tranche(延迟批次)中的,这与平行链区块相关。delay tranche 的范围从 0 到 MAX_TRANCHES,并且对应节点意识到平行链区块变得可用后的刻度数。节点对 tranche 0 对应哪个刻度的看法略有不同。MAX_TRANCHES 是一个协议参数,它确定检查每个平行链区块需要多长时间。将它设置得太小意味着我们可能会选择比我们需要的数量更多的检查者,从而浪费精力。设置太大意味着检查平行链区块需要很长时间。作为参考,在撰写本文时,该参数在 Polkadot 和 Kusama 上设置为 89。

刻度是时间的离散度量,基于从 Unix Epoch 开始的半秒增量。

Delay tranche 是相对于产生中继链区块的刻度的偏移量。

Tranche 0 是特殊的,因为 tranche 0 中的预期检查者数量被设计为大致等于 MIN_CHECKERS,这是一个协议参数,它指定了一个平行链区块被批准检查程序认定为“已批准”前的最小检查数。

作为平行链区块支持组之一的验证人不允许参与批准检查,因为他们的检查是多余的。所有其他验证人在本地运行 VRF 计算,以确定他们要检查的 delay tranche。

任务、批准和未出现

验证人在批准检查中会发送两种消息:任务(Assignment)批准(Approval)。分配用于传达检查平行链区块的意图和资格,并且批准消息表明平行链块已通过所有检查。

每个验证人使用 VRF 和平行链 ID 和中继链块 BABE 凭证作为输入,立即生成一个任务来检查平行链块。验证人将其任务保密,直到需要表明为止。每个任务都唯一且确定地与关联一个延迟部分,延迟部分表示当验证人被分配检查平行链区块时的延迟部分。

VRF 很重要,因为它意味着接收者可以验证任务,并且任务的验证人对分配给他们的延迟部分没有影响。验证人确实会通过更复杂的攻击产生一些间接影响,这些攻击涉及在 BABE 随机性良好时故意分叉中继链,但我将把它留到另一篇文章中来讨论。

批准是一条简单的消息,由发布的验证人签名,表明平行链区块已通过检查。

当验证人开始检查平行链区块时,它所做的第一件事就是将其分配给其他验证人。这会通知其他验证人等待相应的批准消息。验证人完成检查后,会发出一条批准消息。如果批准消息不在 NO_SHOW_DURATION 内,则其他节点认为初始验证人未出现(no-show)。未出现旨在表明对手观察到验证人检查平行链区块的意图,并试图让他们沉默。NO_SHOW_DURATION 是一个协议参数,目前在 Polkadot 上设置为 12 秒。

下图显示了 3 种情况:未出现、已完成的任务、延迟完成。最后一种情况尤其重要,因为它展示了验证人如何“起死回生”,也就是即使在被认为没有出现的情况下也能让其批准算数。

获得批准:调度和批准状态机

批准检查协议的最后一部分,将详细说明用于批准平行链区块的状态机

每个验证人节点都为每个包含的(可用的)平行链区块维护一个批准状态。由于网络中的时间和异步性,验证人的状态版本可能会有所不同。状态会让我们回答以下问题:

  1. 平行链区块是否获得批准?

  2. 与 tranche T 的分配是否对应?

  3. 在没有其他输入的情况下,问题 (1) 或 (2) 的答案可能发生变化的下一个时间点是什么时候?

批准状态可以通过 3 种方式更新:通过接收新任务、通过接收新批准或通过时间推进。

验证人会一直运行状态机,直到问题 (1) 的答案为“是”。在每条输入之后,他们会使用问题 (2) 来检查他们的任务是否对应,从而来确定他们是否应该开始自己检查平行链区块。问题 (3) 仅用于优化目的:节点通常并行运行数千个这些状态机(每个未终结的平行链区块一个),并且在每个刻度都轮询所有这些状态机的话效率就太低了。

这是每个验证人运行的逻辑,直到平行链区块被批准

该状态实际包含了两部分:

  1. 所有收到的任务,按 tranche 排序,并用第一次观察到的刻度进行注释。

  2. 所有收到的批准。

验证人在开始检查之前不会在状态中包含自己的任务。在产生批准后,验证人会将其包含在状态中。

这是状态的可视化表示;它是一个中立的对象,可以根据收到的任务、经过的时间以及获得的批准来回答问题。

批准状态中最重要的操作之一是确定要计算哪些任务。我们将 delay tranche 整体看待。任务总是与来自同一 delay tranche 的所有其他任务捆绑在一起。节点永远不会只算 delay tranche 中的某个任务,而不算它知道的同一 delay tranche 里的所有其他任务。

任务处于以下三种状态之一:

  1. 待定:该任务没有相应的批准,但它是最近才下达的任务。

  2. 已完成:任务有相应的批准。

  3. 未出现:该任务没有相应的批准,并且它不是最近下达的任务。

未出现的任务需要由至少一笔非空档 tranche 覆盖。也就是说,每个未出现任务都需要被至少一个任务覆盖,但期望不止一个(基于参数化)。

通过以下程序确定有多少 tranche:

  1. 从 tranche 0 开始算,直到其至少包含 MIN_CHECKERS 个任务。

  2. 每个非空的 tranche,抵消一个未出现。如果这些非空 tranche 中还有更多未出现,则重复步骤 2。

  3. 如果完成了所有非“未出现”的任务,则平行链区块被批准。换句话说,如果有任何任务仍在等待中,那么平行链区块就不会被批准。

如果某个时候你用完了可取的 tranche(最大值是协议设定的参数),则该区块不会被批准。在该协议的实际使用的版本中,对于不取用“未来”的tranche,以及步骤 2 的每次迭代的漂移时间,还有一些进一步的限制。

此流程图捕获了每个验证人运行的,用来确定平行链区块是否被批准的逻辑。需要注意的是,这仅基于验证人实际看到的任务和批准。可能还有一些任务存在,从而改变计数过程的结果。但如果运行该过程的验证人还未收到这些任务,则无法考虑它们。

如何对收到的任务和批准进行计数和解释

此过程的关键点是,如果有足够的早期任务,则根本不计算后期 tranche 的任务,并且在秘密情况下消失的节点将被替换掉。

以下是批准计数程序结果的 4 个例子:

每当验证人运行此批准计数程序,并发现需要更多任务时,它会检查是否应该触发自己的任务并开始检查。验证人会在以下情况下触发其任务:

  1. 验证人尚未触发其任务。

  2. 任务的 tranche 与状态有关:要么它是状态已经考虑的 tranche 的一部分,要么计数程序取完了 tranche,而且任务不在未来。

总结

批准检查协议是 Polkadot 的主要欺诈检测机制。在任何东西到达此阶段之前,我们已确保检查所需的数据是可用的。这种机制导致每个平行链区块的要么被批准要么被升级。并且该机制的设计,让试图消灭前来检查的验证人的 DoS 攻击者,反而被更多的检查者所取代。

批准检查是一条九头蛇。它旨在吃掉攻击者并在另一端将其吐出。它将它们发送到一个我们称之为争议(dipute)的系统:争议是 Polkadot 的共识法院。

链得得仅提供相关信息展示,不构成任何投资建议
本文系作者 链得得的朋友们 授权链得得发表,并经链得得编辑,转载请注明出处、作者和本文链接

更多精彩内容,关注链得得微信号(ID:ChainDD),或者下载链得得App

分享到:

相关推荐

    评论(0

    Oh! no

    您是否确认要删除该条评论吗?

    分享到微信