最小罚没条件

上周 Yoichi 发布了一篇博文，详细介绍了正式证明我的“最小削减条件”的安全性和活性属性的过程。这是一个容错拜占庭的核心组件，在非同步条件下安全且具有加密经济安全性的一致性算法，在我的权益证明路线图中占据核心地位。在这篇文章中，我想提供更多关于这个算法的细节，它的重要性，以及它如何一般地融入权益证明研究。

Casper的一个关键目标是实现“经济最终性”，我们可以半正式地定义如下：

如果客户端有证明，那么区块 B1 是 经济上最终 的，具有加密经济安全边际 $X，如果 (i) B1 将永远成为规范链的一部分，或者 (ii) 导致 B1 被回退的那些参与者保证会按至少 $X 的金额受到经济惩罚。

想象 X ≈ 7000 万美元。基本来说，如果一个区块被最终确认，那么该区块就是链的一部分，改变这一点的成本非常高。工作量证明在这方面基本上不具备；这是权益证明的一个独特特性¹。其意图是使 51% 攻击的成本极高，因此即使是大多数验证者合作，也无法在不承受极大经济损失的情况下回滚被最终确认的区块——损失如此之大，以至于成功的攻击可能在净上 增加 基础加密货币的价格，因为市场对总币供应的减少的反应将远远比为纠正攻击而进行的紧急硬分叉的需求更加强烈（有关背后哲学的更深入概述，请参见 这里）。

在 Casper 中，通过要求验证者提交存款以参与，在协议确定他们以某种方式违反某组规则（“ 削减条件”）时没收他们的存款，从而实现经济最终性。

一个削减条件可能看起来像这样：

如果一个验证者发送消息形式的签名消息

["PREPARE", epoch, HASH1, epoch_source1]

和形式的签名消息

["PREPARE", epoch, HASH2, epoch_source2]

其中 HASH1 != HASH2 或 epoch_source1 != epoch_source2，但 epoch 值在两个消息中是相同的，那么该验证者的存款将会被 削减（即删除）。

该协议定义了一组削减条件，而诚实的验证者遵循一种协议，保证不会触发任何条件（注意：我们有时将“违反”削减条件作为“触发”的同义词；可以将削减条件视为法律，你不应该违反的法律）；在同一 epoch 中两次发送 PREPARE 消息对诚实验证者来说并不困难。

“PREPARE”和“COMMIT”是借用自传统拜占庭容错共识理论的术语。现在，只需将它们视为两种不同类型的消息；在稍后我们将介绍的协议中，可以将共识视为需要两轮达成一致，其中 PREPARE 表示第一轮，而 COMMIT 表示第二轮。

还有一个 最终条件，描述了客户端在何时可以确定某个特定哈希是最终的。这是更简单的；我们现在就直接陈述当前版本的 Casper 中唯一的最终条件。

如果对于某个特定的 epoch 编号，存在一组形式为

["COMMIT", epoch, HASH]

的签名消息，那么 HASH 是 最终的，如果将创建这些签名消息的验证者的存款合计起来，那么得到的金额将超过当前活动验证者集的总存款余额的 2/3。

简单来说，我们可以说“该哈希在某个特定 epoch 中由 2/3 的验证者提交”或“该哈希在某个特定 epoch 中有 2/3 的提交”。

削减条件需要满足两个条件：

1. 可问责的安全性：如果两个相互冲突的哈希被最终确认，那么必须可以证明至少 1/3 的验证者违反了某些削减条件。²
2. 合理的活性：除非至少 1/3 的验证者违反了某些削减条件，则必须存在一组消息，2/3 的验证者可以发送这些消息，从而在不违反某些削减条件的情况下最终确认某个新的哈希。

可问责的安全性给予我们“经济最终性”的概念：如果两个相互冲突的哈希被最终确认（即分叉），那么我们有数学证明说明大规模的验证者必定违反了某些削减条件，因此我们可以将证据提交到区块链上并对他们处以惩罚³。

合理的活性基本上意味着“算法不应当处于‘ 卡住’状态，无法最终确认任何内容”。

为了说明这两个概念的含义，我们可以考虑两个玩具算法，一个满足安全性但不满足活性，另一个满足活性但不满足安全性。

算法 1：每个验证者有且仅有一次机会发送形式为 ["COMMIT", HASH] 的消息。如果 2/3 的验证者发送针对相同哈希的 COMMIT，那么该哈希就是最终的。发送两个 COMMIT 消息违反了削减条件。

在这里，有一个非常明显的证明，表明该算法是安全的：如果 HASH1 和 HASH2 都被最终确认，那么这意味着每个哈希都有 2/3 的提交，因此必定有 1/3 的重叠，所以 1/3 的验证者会被削减。但它并不具备合理的活性：如果 1/2 提交 A 而 1/2 提交 B（这一情况是完全可能偶然发生的），那么 1/6 的验证者必须自愿削减以最终确认一个哈希。

安全性证明

但我们可能会卡住

算法 2：每个验证者有且仅有一次机会发送形式为 ["COMMIT", HASH, epoch] 的消息。如果 2/3 的验证者发送针对相同哈希且 epoch 相同的 COMMIT，那么该哈希就是最终的。发送两个不同哈希的 COMMIT 消息但在同一 epoch 中，则违反了削减条件。

这解决了上一个算法中的问题，因为如果在一个 epoch 中我们得到 50/50 的情况，那么我们可以简单地在下一个 epoch 中再试一次。但这引入了一个安全缺陷：在不同的 epoch 中可能会有两个不同的哈希被最终确认！

不再安全。

事实证明，能够同时获得这两者，但这并不简单，并且需要 4 个削减条件，加上 1000 行代码，Yoichi 需要 正式证明它确实有效。

削减条件如下：

[COMMIT_REQ] 如果一个验证者发送形式为

["COMMIT", epoch, HASH]

的签名消息，那么除非对于某个特定值 epoch_source，满足 -1 <= epoch_source < epoch，不然形式为

["PREPARE", epoch, HASH, epoch_source]

的消息必须已由 2/3 的验证者签名并广播，否则该验证者的存款会被削减。

用简单的语言来说，发送一个提交消息需要看到 2/3 的准备消息。

[PREPARE_REQ] 如果一个验证者发送形式为

["PREPARE", epoch, HASH, epoch_source]

的签名消息，且 epoch_source != -1，那么除非对于某个特定值 epoch_source_source，满足 -1 <= epoch_source_source < epoch_source，不然形式为

["PREPARE", epoch_source, ANCESTOR_HASH, epoch_source_source]

的消息，且 ANCESTOR_HASH 是 HASH 的 （epoch - epoch_source） 级祖先，已经被 2/3 的验证者签名并广播，否则该验证者的存款将会被削减。

如果你在某个 epoch 中做一个准备，指向某个特定的前一个 epoch，则需要在该 epoch 中看到 2/3 的准备，并且这些准备必须指向相同的前一个 epoch（例如，2/3 的准备在第 41 个 epoch 指向第 35 个 epoch 没问题，第 41 个 epoch 中一半指向第 35 个，一半指向第 37 个就不行；在第 41 个 epoch 中 5/6 的准备，其中 4/5 指向第 35 个，这也是可以的，因为 4/5 的 5/6 是 2/3，你可以忽略其他 1/6）。

通过“n 级祖先”，我们指的是在区块链哈希链意义上的祖先，例如以太坊区块 3017225 是以太坊区块 3017240 的第十五级祖先。请注意，每个区块只能有一个父级，因此对于每个特定值 n 只能有一个 n 级祖先。

[PREPARE_COMMIT_CONSISTENCY] 如果一个验证者发送形式为

["COMMIT", epoch1, HASH1]

然后发送一个形式为 ["PREPARE", epoch2, HASH2, epoch_source] 的消息，其中 epoch_source < epoch1 < epoch2，则无论 HASH1 ?= HASH2，该验证者都会被削减。

如果你在某个 epoch 中进行一个提交，那么你显然在该 epoch 中看到了 2/3 的准备，因此未来所做的任何准备都应当更好地引用该 epoch 或更晚的某个 epoch。

[NO_DBL_PREPARE] 如果一个验证者发送形式为

["PREPARE", epoch, HASH1, epoch_source1]

和形式为 ["PREPARE", epoch, HASH2, epoch_source2]

的签名消息，其中 HASH1 != HASH2 或 epoch_source1 != epoch_source2，但两条消息中 epoch 值相同，则该验证者被削减。

在同一 epoch 中不能进行两次准备。

通过这四个削减条件，结果表明可问责的安全性和合理的活性都成立。

请注意，使用上述规则，两个 不同 的哈希可以最终确认——如果这两个哈希都是同一历史的一部分，那么它们都可以得到最终确认，事实上，一个不断增长的链，其中越来越多的哈希在链的最后被最终确认，正是我们所 想要的。

左侧：不同的哈希可以根据这些规则被最终确认，但只要它们是同一链的一部分，那么这就符合预期。右侧：不属于同一历史的哈希是 冲突的；有证据表明，上述四个削减条件阻止两个冲突的哈希被最终确认，除非至少 1/3 的验证者被削减。

现在，让我们把事情结合起来。有一组活跃验证者（任何人都可以通过提交存款自由参与，经过一段延迟，任何参与者可以离开，随后在更长的延迟后提取资金），这些验证者有权签署并发送形式为：

["PREPARE", epoch, HASH, epoch_source]

["COMMIT", epoch, HASH]

如果在某个特定的 epoch 中有足够的 COMMIT 消息针对某个 HASH，那么该 HASH 就被最终确认。哈希彼此相链，每个哈希都指向某个前一个哈希，并且我们希望随着时间的推移，看到链上不断增长的哈希，新的哈希在链中的最终确认。我们为验证者发送这些 PREPARE 和 COMMIT 消息提供经济奖励，以确保在最终确认实际发生时，足够多的消息及时发送。

一般来说，你可以取任何容错拜占庭共识算法⁴，它具有 PBFT 的“在同步情况下活跃，在异步情况下安全”的特性，并将其转换为一组给你可问责的安全性和合理的活性的削减条件；上面的条件受到 PBFT 和 Tendermint 的启发，但也可以有其他出发点产生不同的结果。

请注意，合理的活性与实际活性并不是同一件事；合理的活性意味着我们理论上总能确认一些东西，但也可能一直不幸而最终确认不到任何东西。为了解决这个问题，我们需要制定一个 提议机制，并确保该提议机制具备其实际上可以帮助我们实现活性的属性。

提议机制是提出哈希的机制，其他设备使用 PREPARE 和 COMMIT 消息来尝试最终确认。这一机制在某些时刻可能会出现故障；保证即使提议机制出现故障的情况下，也没有安全失效，协议可以在提议机制不再故障后确认一些东西，这是削减条件的工作。

在许多传统的容错拜占庭共识算法中，提议机制和算法的其余部分密切相关；在 PBFT 中，每个视图（大致相当于一个 epoch）分配给一个单一的验证者，该验证者可以自由提出他们想要的任何东西。验证者可能表现不当，提出空白，提出无效哈希或提出多个哈希，但 PBFT 机器的其他部分确保这些行为并非致命，算法最终转移到下一个 epoch。在这里，我们实际上可以将我们的削减条件与许多不同类型的提议机制结合，只要它们满足一些条件即可。

首先，提议机制必须为 每个 epoch 提出 一个哈希，并且它必须是一个有效的哈希（有效性条件可以非常复杂；在以太坊的情况下，它涉及执行和验证整个以太坊状态转换函数的执行，以及验证数据可用性）。

第二，哈希必须形成链；也就是说，为 epoch N 提交的哈希必须有一个为 epoch N-1 提交的父级，二级祖先必须为 epoch N-2 提交，依此类推。

第三，这些哈希必须是削减条件不阻止验证者最终确认的哈希。这一点更微妙。考虑这样一种情况，在 epoch 0 提议机制提出哈希 HASH0，然后在 epoch 1 提议机制提出哈希 HASH1（HASH0 的直接子项），但是出于某种原因，这两个哈希都没有达到足够的准备以获得任何提交。然后，提议机制（由于某种暂时故障）为 epoch 0 提出了另一个哈希 HASH0'，而这个哈希获得了 2/3 的准备和 1/2 的提交。

现在，提议机制有两个选择。一种可能性是它可以提议 HASH2（HASH1 的直接子项），然后提议 HASH3（HASH2 的直接子项），依此类推。然而，削减条件确保在没有 1/6 的验证者被削减的情况下，这些哈希都无法获得提交。另一种且正确的可能性是它应该提出 HASH1'（HASH0' 的直接子项），预期该哈希可能永远无法最终确认，因为可能它的竞争者 HASH1 已经获得了超过 1/3 的准备，从而 HASH1' 无法获得所需的 2/3，然后提议 HASH2'（HASH1' 的直接子项）。HASH2' 是可以被确认的，然后该机制可以继续提议新哈希，每个哈希都是前一个哈希的子项。

一些人可能会立刻想到：我们能否使用传统的工作量证明区块链，按最长链规则作为提议机制？每隔 100 个区块可以是一个检查点，区块 N * 100 的哈希成为 epoch N 的提议。但这本身并没有保证能工作，因为在上面的情况下，提议机制将尝试提议 HASH2 而不是 HASH1'，因此它永远不会最终确认任何哈希（这并不完全是我们所说的“卡住”，因为走出这种局面不需要任何人被削减，但确实需要使矿工勾结以挖掘包含 HASH0' 的链，即使包含 HASH1 的链在工作量证明的意义上更“长”）。然而，我们可以使用传统的工作量证明区块链与 修改过的分叉选择规则。

分叉选择规则是一个函数，由客户端进行评估，该函数将生产的区块和其他消息集合作为输入，并输出客户端所认为的“规范链”。“最长有效链胜利”是一个简单的分叉选择规则，适合 PoW；Zohar 和 Sompolinsky 的 GHOST 是一个更复杂的例子。我们可以定义一个分叉选择规则，允许一个区块链作为共识算法的提议机制并具备上述属性，具体如下：

1. 以 HEAD 作为创世块开始。
2. 查找有效的 HEAD 的后代，该后代具有 2/3 的准备和最大的提交数量。
3. 将 HEAD 设置为该后代，并返回第二步。
4. 当第二步无法再发现具有 2/3 准备和任意提交的后代时，使用区块链的基础分叉选择规则（最长链、GHOST 等）来找到顶端。

请注意，在我们上面的示例中，这将最终有利于 HASH0' 而非 HASH1，因此它具备所需的预期效果。还要注意，如果存在一条最终确认的链，则始终会选择该最终确认的链。

上述削减规则确保了一种特定类型的故障是非常昂贵的：最终性退回分叉。然而，还有其他类型的故障未被涵盖；特别是最终确认一个无效哈希，以及确认一个代表某些数据不可用的链的哈希。目前，已知的解决此问题而不牺牲绝对加密经济安全性的最简便方法是作为全节点——下载并验证所有区块，以便可以简单地忽略无效哈希。因此，确定给定哈希是否最终的过程是两步的：(i) 检查 2/3 的提交，(ii) 检查到该哈希的链是否有效。

为了使最终性对轻客户端有效，有两种方法。第一种是添加另一种消息类型，节点可以发送（称之为 ["ATTEST", HASH, epoch]），该消息会产生以下效果：如果该消息被提交到一个链上，而给定的哈希实际上是该 epoch 的哈希，则验证者将获得小额奖励，但如果不是，则他们将支付大额罚款。因此，验证者只会在确实确信给定哈希是客户端看到的规范链的一部分，并且将永远如此时发送此消息（在他们亲自完全验证区块链至该哈希并检查其是否具有 2/3 的提交后，验证者执行此行动可能是一个好的时机）。

第二种方法是为轻客户端提供各种加密经济技术，这将使他们能够在一些弱诚实少数假设的帮助下非常高效地验证数据的可用性和有效性；这可能涉及讽刺编码和交互验证的组合。这里的研究类似于正在进行的分片研究，二者之间存在紧密的联系——上述第一种方法要求验证者自身为全节点，而第二种方法则不需要，分片的最终目标就是创建一个没有人是全节点的区块链。预计在这一主题上将会发表更多博文。

特别感谢 Yoichi Hirai、River Keefer 和 Ed 进行审阅。

笔记：

1. 一些人可能认为工作量证明具有经济最终性，其安全边际为 R * k，其中 R 是区块奖励，k 是正在回退的区块数量，但这并不是真的，如果你成功进行 51% 攻击，那么你会因你的工作获得区块奖励——进行 51% 攻击的 预算_ 要求确实大致是 R * k，但如果你成功，成本 为零。_
2. 1/3 的比例来自传统的拜占庭容错理论，并选择该比例以最大化故障容忍度的总水平。一般而言，你可以用任何值 t > 1/2 替换本文中提及的削减条件的 2/3，随后你可以从活性角度计算故障容忍度的程度为 1-t（因为如果超过 1-t 离线，则不能达到 t），而从安全性角度计算的故障容忍度程度为 2t-1（如果 t 最终确认 A 且 t 最终确认 B，总的 2t > 1，因此至少有 2t-1 的重复）。t = 2/3 最大化了二者中的最小值（1-t = 1/3, 2t - 1 = 1/3）；你也可以尝试 t = 3/5（活性：2/5 的故障容忍度，安全性：1/5）或 t = 3/4（活性：1/4，安全性：1/2）。还要注意，t < 1/2 的值在与公开信息中多少节点很可能离线的背景下也是有意义的，但处理这些情况，以及“主观最终性阈值”的更广泛概念，都是另一个深刻而有趣的话题。
3. 除非存款已经被提取；但是这种情况（“长距离攻击”）也是另一个文章的话题，不过这次它是 一篇发表于两年前的文章。_
4. 至少，只要它仅使用哈希和签名作为密码学。如果它使用门限签名，那么就更为复杂，因为 2/3 的恶意节点的联盟可以伪造任何其他参与者的签名。

• 原文链接： medium.com/@VitalikButer...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～