EIP-5450: EOF栈验证

摘要

引入 EOF 代码区段的扩展验证，以确保在已验证合约的执行过程中不会发生堆栈下溢或上溢。

动机

当前的 EVM 为每条执行的指令执行若干有效性检查，例如检查指令是否被定义、堆栈上溢和下溢以及剩余的气体量是否充足。

本 EIP 通过验证不可能发生任何异常情况，最小化在运行时所需的此类检查数量，防止任何无效代码的执行和部署。

操作数堆栈的验证提供了几个好处：

• 移除了对所有指令的运行时堆栈下溢检查，
• 移除了对所有指令的运行时堆栈上溢检查，只有 CALLF 和 JUMPF 除外 (JUMPF 在单独的 EIP 中引入)，
• 确保执行以某个终止指令结束，
• 防止部署具有不可达指令的代码，从而阻止将代码区段用于数据存储。

它还有一些缺点：

• 为代码结构增加了约束（类似于 JVM、CPython 字节码、WebAssembly 等）；然而，如果这些约束被证明不利于用户，便可以以向后兼容的方式解除，
• 实现堆栈验证作为第二次验证过程是合乎自然的；然而，这并非严格要求，验证的计算和空间复杂度在任何实现变体中保持线性。

这些验证规则所创建的保证也提高了 EVM 代码的提前编译和即时编译的可行性。单遍转译过程可安全执行，并且在堆栈高度验证的基础上可应用高级堆栈/寄存器处理。尽管对主要网络验证节点的影响不大，主要受存储状态大小的约束，但这些可以显著加速见证验证及其他非主网用例。

规范

代码验证

备注： 我们依赖于 EIP-4750 中定义的 操作数堆栈 和 类型区段 的概念。

每个代码区段独立验证。

指令验证

在 EIP-3670 定义的第一个验证阶段中（并由 EIP-4200 和 EIP-4750 扩展），独立检查指令，以确保其操作码和立即数值有效。

操作数堆栈验证

在第二个验证阶段对代码执行控制流分析。

此处的 操作数堆栈高度 指的是此函数可以访问的堆栈值的数量，即不考虑调用者函数帧的值（但包括此函数的输入）。请注意，验证过程不要求实际的操作数堆栈实现，仅需跟踪其高度。

终止指令 指的是以下指令：

• 结束函数执行：RETF、JUMPF，或者
• 结束调用帧执行：STOP、RETURN、RETURNCODE、REVERT、INVALID。

注：JUMPF 和 RETURNCODE 在单独的 EIP 中引入。

前向跳转 指的是相对偏移量大于或等于 0 的任何 RJUMP/RJUMPI/RJUMPV 指令。后向跳转 指的是相对偏移量小于 0 的任何 RJUMP/RJUMPI/RJUMPV 指令，包括跳转到同一个跳转指令。

代码中的指令在对代码的线性单遍扫描中被检查。对于每条指令，记录操作数堆栈高度边界，分别为 stack_height_min 和 stack_height_max。

第一指令的记录堆栈高度边界被初始化为与匹配该代码的函数类型的输入数量相等（stack_height_min = stack_height_max = type[code_section_index].inputs）。

对于每条指令：

1. 检查 此指令是否有记录的堆栈高度边界。如果没有，这意味着它既不是先前前向跳转引用的，也不是顺序指令流的一部分，这段代码验证失败。
   • 这是验证算法的前提条件，代码生成器须以一种方式对代码基本块进行排序，使得没有基本块只通过后向跳转引用。
2. 确定该指令对操作数堆栈的影响：
   1. 检查 记录的堆栈高度边界是否满足指令要求。具体来说：
      • 对于 CALLF 指令，记录的堆栈高度下限必须至少等于被调用函数的输入数目，根据其在类型区段中定义的类型，
      • 对于 RETF 指令，记录的下限和上限必须相等，且必须恰好等于与该代码匹配的函数的输出数量，
      • 对于 JUMPF 跳入返回函数，记录的下限和上限必须恰好等于 type[current_section_index].outputs + type[target_section_index].inputs - type[target_section_index].outputs，
      • 对于 JUMPF 跳入非返回函数，记录的堆栈高度下限必须至少等于根据其类型定义数量的目标函数的输入，
      • 对于任何其他指令，记录的堆栈高度下限必须至少等于指令所需的输入数量，
      • 对于除了 RETF 和 JUMPF 以外的终止指令没有额外检查，这意味着指令结束 EVM 执行时允许堆栈中留有额外项目。
   2. 对于 CALLF 和 JUMPF 检查 可能的堆栈上溢：如果记录的堆栈高度上限大于 1024 - types[target_section_index].max_stack_height + types[target_section_index].inputs，则验证失败。
   3. 在指令执行后计算新的堆栈高度边界。上限和下限根据相同的值进行更新：
      • 在 CALLF 后，堆栈高度边界通过添加 types[target_section_index].outputs - types[target_section_index].inputs 进行调整，
      • 在任何其他非终止指令后，堆栈高度边界通过减去指令输入的数量并添加指令输出的数量进行调整，
      • 终止指令不需要更新堆栈高度边界。
3. 确定可以跟随当前指令的 successor 指令列表：
   1. 所有非终止指令和无条件跳转的下一个指令。
   2. 条件或无条件跳转的所有目标。
4. 对于每个 successor 指令：
   1. 检查 指令是否在代码中存在（即执行必须不会“跌出”代码）。
   2. 如果 successors 是通过向前跳转或从前一指令的顺序流达到的：
      1. 如果该指令没有记录堆栈高度边界（首次访问），那么记录该指令堆栈高度边界为 2.3 中计算的值。
      2. 否则，该指令已被访问（通过先前看到的前向跳转）。更新该指令的记录堆栈高度边界，使其包含在 2.3 中计算的边界，即 target_stack_min = min(target_stack_min, current_stack_min) 和 target_stack_max = max(target_stack_max, current_stack_max)，其中 (target_stack_min, target_stack_max) 为 successor 边界，(current_stack_min, current_stack_max) 为 2.3 中计算的边界。
   3. 如果 successor 是通过后向跳转达到的，检查 记录的堆栈高度边界是否等于 2.3 中计算的值。如果不相等，验证失败，即我们看到后向跳转到不同的堆栈高度。

在所有指令都被访问后，确定函数的最大操作数堆栈高度：

1. 计算最大堆栈高度为所有记录的堆栈高度上限的最大值。
2. 检查 最大堆栈高度是否不超过 1023 (0x3FF)。
3. 检查 最大堆栈高度是否匹配类型区段中相应代码区段的 max_stack_height。

此过程的计算和空间复杂度为 O(len(code))。每条指令最多被访问一次。

执行

鉴于部署时验证的保证，EVM 实现不再要求对每条执行指令进行运行时堆栈下溢或上溢检查。唯一的例外是 CALLF 和 JUMPF 对整个被调用函数进行操作数堆栈上溢检查。

原因

验证代码的特性

任何根据操作数堆栈验证的代码区段具有以下特性：

1. 没有不可达指令
2. 没有仅通过后向跳转可达的指令
3. 操作数堆栈下溢不会发生。
4. 操作数堆栈上溢只可能发生在 CALLF 或 JUMPF 指令中。
5. 不同堆栈高度下执行的多个前向跳转指令可能指向同一指令；对目标基本块的堆栈在所有可能的高度下进行验证。
6. 任何后向跳转指令只能指向在相等堆栈高度下执行的指令；这一点防止了部署具有无限堆栈推入或弹出的循环。
7. 代码区段的最后一条指令要么是终止指令，要么是 RJUMP。

仅在 CALLF/JUMPF 中进行堆栈上溢检查

在本 EIP 中，我们提供了一种更高效的 EVM 变体，其中堆栈上溢检查仅在 CALLF 和 JUMPF 指令中执行，使用被调用函数的 max_stack_height 信息。这减少了 EVM 程序的灵活性，因为 max_stack_height 对应于函数中最坏情况的控制流路径。

不可达代码

操作数堆栈验证算法拒绝任何具有不可达指令的代码。这一检查可以非常便宜地执行。它防止了退化代码的部署。此外，它还使指令验证与操作数堆栈验证的合并成为单遍的可能性。

终止时清空堆栈

目前要求在 RETF 指令之后操作数堆栈是空的（只是当前函数上下文下）。否则，RETF 语义会变得更加复杂。对于具有 n 函数输出和 s 为 RETF 时的堆栈高度，EVM 必须清除 s-n 个非栈顶项目，并将 n 个栈项目移动到已擦除项目的位置。此类操作的成本可能相对较低，但不是恒定的。 然而，取消此要求并按上面所述修改 RETF 语义是向后兼容的，且能在未来轻松引入。

更严格的堆栈验证

最初提出了另一种堆栈验证的变体，其中没有对代码区段进行线性扫描，而是通过一种广度优先搜索的方式检查每条跳转指令的目标，跟踪每个访问指令的堆栈高度，并检查对特定指令的每条可能代码路径的堆栈高度是否保持不变。

这一变体的优点在于算法相对简单（我们不需要跟踪堆栈高度边界，仅需为每个指令跟踪一个堆栈高度值），并且没有额外的基本块排序要求。然而编译器团队反对此类严格的堆栈高度要求。编译器常用的一个模式就是从不同的堆栈高度跳到终止帮助程序（以 RETURN 或 REVERT 结束的代码块）。例如一系列 assert 语句，每个都会编译为对一个共享的终止帮助程序的 RJUMPI 跳转。强制要求堆栈恒定意味着在跳转到此类帮助程序之前，必须弹出堆栈上的额外项目，这明显增加了代码大小和消耗的气体，会违背将这些常见终止序列提取到帮助程序中的目的。

基本块的排序

堆栈验证算法的前提是以一种方式对代码基本块进行排序，使得没有基本块仅通过后向跳转引用。

这使得能够在对代码区段的单遍扫描中检查每条指令成为可能。对代码区段的前向遍历允许算法“扩展”每个前向跳转目标的堆栈高度边界，并保持复杂度线性。试图在广度优先搜索的方式下扫描代码的同时扩展跳转目标的堆栈边界，要求在堆栈高度边界扩展后重新检查整个代码路径，这将导致二次复杂性。

向后兼容性

此更改需要“网络升级”，因为它修改了共识规则。

它对向后兼容性没有风险，因为仅为 EOF1 合约引入，因此不允许部署未定义指令，因此没有现有合约使用这些指令。对于遗留字节码（非 EOF 格式的代码）不会引入新指令。

安全考虑

需要讨论。

版权

通过 CC0 放弃版权及相关权利。

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