EIP-3690: EOF - JUMPDEST 表

一种特殊的 EOF 区段，用于存储 `JUMPDEST` 列表，从而简化执行时间分析。

摘要

在 EOF 格式 (EIP-3540) 中引入一个区段，用于存储 JUMPDEST 的列表，在合约创建时验证此列表的正确性，并消除执行时对 JUMPDEST 分析的需求。在 EOF 合约中，不再需要 JUMPDEST 指令，并且变为无效。传统合约完全不受此更改的影响。

动机

当前存在的合约不需要验证正确性，但是每次执行时，都必须构建一个包含所有有效跳转目的地的列表。这是一个可以避免的开销，尽管开销的影响取决于客户端的实现。

通过 EIP-3540 提供的结构，可以存储和传输有效的跳转目的地表，而不是在代码中使用指定的 JUMPDEST (0x5b) 操作码。

此更改的目标是，我们在合约创建时以更多的复杂性（和处理时间）换取更少的执行时复杂性（和处理时间）。通过基准测试，我们已经确定，对于极端情况（即，故意的边缘情况），强制执行准备时间与以前相同，而对于平均情况则快约 10 倍。

最后，此更改对“initcode 分析”施加了一个隐式限制，该限制现在限于最大大小为 0xffff 的 jumpdests 区段加载。传统代码仍然容易受到攻击。

规范

此功能在启用 EIP-3540 的同一区块中引入，因此，如果每个 EOF1 兼容的字节码使用跳转，则必须具有 JUMPDEST 表。

备注： 我们依赖于由 EIP-3540 定义的 initcode、code 和 creation 的表示法，并扩展 EIP-3670 的验证规则。

EOF 容器更改

1. 引入了一个新的 EOF 区段，称为 jumpdests (section_kind = 3)。 它包含 n 个无符号整数 jumploc_i 的序列。

2. jumploc_i 值使用 无符号 LEB128 进行编码。

   description	encoding
   jumploc0	unsigned LEB128
   jumploc1	unsigned LEB128
   …
   jumplocn	unsigned LEB128

3. 跳转目的地表示作为跳转指令参数的有效代码位置集。 它们经过 delta 编码，因此必须执行部分求和才能检索绝对偏移量。

   def jumpdest(n: int, jumpdests_table: list[int]) -> int:
       return sum(jumpdests_table[:n+1])
   

验证规则

本节扩展了合约创建验证规则（如 EIP-3540 中定义）。

1. 当且仅当 code 区段包含 JUMP 或 JUMPI 操作码时，才 MUST 存在 jumpdests 区段。
2. 如果存在 jumpdests 区段，则它 MUST 直接位于 code 区段之前。 在这种情况下，有效的 EOF 字节码将具有以下形式：format, magic, version, [jumpdests_section_header], code_section_header, [data_section_header], 0, [jumpdests_section_contents], code_section_contents, [data_section_contents]。
3. jumploc 的 LEB128 编码必须有效：编码必须完整，并且不能从 jumpdests 区段中读出。 作为一个附加约束，必须使用最短的可能编码。
4. 除了第一个条目外，jumploc 的值 MUST NOT 为 0。
5. 每个 jumploc MUST 指向有效的操作码。 它们 MUST NOT 指向 PUSH 数据或代码区段之外。
6. JUMPDEST (0x5b) 指令变为未定义（注意：根据 EIP-3670 的规则，如果代码包含 JUMPDEST，则部署代码将失败）

执行

1. 执行 JUMP 或 JUMPI 指令时，跳转目的地 MUST 位于 jumpdests 表中。 否则，执行将因错误的跳转目的地而中止。 对于 JUMPI，仅在要执行跳转时才执行检查（对先前行为没有更改）。

理由

Jumpdests 区段是有界的

jumpdests 区段的长度受 EOF 最大区段大小值 0xffff 的限制。 而且，对于已部署的代码，这还受到最大字节码大小 0x6000 的限制。 然后，任何有效的 jumpdests 区段都可能不大于 0x3000。

Delta 编码

Delta 编码对于这项工作非常有效。 通过对一小组合约的快速分析，JUMPDEST 操作码彼此相对接近。 在 delta 编码中，这些值几乎从不超过 128。 结合任何形式的可变长度数量 (VLQ)，其中值 < 128 占用一个字节，单个 jumpdest 的编码占用约 1 个字节。 我们还从代码区段中删除了 JUMPDEST 操作码，因此，如果忽略极端示例，则总字节码长度保持不变。

通过极端示例，我们指的是在两个后续 JUMPDEST 之间的距离大于 128 的合约。 然后，此类距离的 LEB128 编码需要多个字节，并且总字节码大小将增加所使用的额外字节数。

LEB128 用于偏移量

LEB128 编码是 DWARF 和 WebAssembly 中最常用的 VLQ。

LEB128 允许通过具有值的最高有效位的零有效负载来使用任意数量的字节编码固定值。 为了确保给定值仅存在一个编码，我们还要求使用最短的可能 LEB128 编码。 WebAssembly 也需要此约束。

偏移量的大小前缀

这是另一种受 UTF-8 启发的编码选项。 好处是，以下字节数编码在第一个字节中（最高两位），因此预先知道期望的长度。

一个简单的解码器如下：

def decode(input: bytes) -> int:
    size_prefix = input[0] >> 6
    if size_prefix == 0:
        return input[0] & 0x3f
    elif size_prefix == 1:
        return (input[0] & 0x3f) << 8 | input[1]
    elif size_prefix == 2:
        return (input[0] & 0x3f) << 16 | (input[1] << 8) | input[2]
    # Do not support case 3
    assert(False)

空表

如果代码不使用跳转，则通过省略 jumpdests 区段来表示空的 JUMPDEST 表，而不是始终存在的区段，但允许为空。 这与 EIP-3540 对区段大小非零的要求一致。 此外，省略该区段可以节省 3 个字节的代码存储空间。

为什么 jumpdests 在代码之前？

始终需要 jumpdests 区段的内容才能启动 EVM 执行。 对于分块和/或默克尔化的字节码，使 jumpdests 紧随 EOF 标头之后更为有效，因此它们可以共享相同的第一个块。

代码分块/默克尔化

在代码分块中，合约代码被拆分为（固定大小的）块。 由于 jumpdest 分析的要求，必须知道给定块中第一个指令从哪里开始，以防拆分发生在 PUSH 数据中。 这通常通过保留块的第一个字节作为“第一个指令偏移量”（FIO）字段来完成。

有了此 EIP，代码分块就不需要这样的字段。 但是，必须提供 jumpdest 表（对于所有块，直到执行期间使用的最后一个跳转位置为止）。

基准测试/性能分析

我们将 jumpdests 区段加载的性能与 evmone/Baseline 解释器中的 JUMPDEST 分析进行了比较。 在这两种情况下，都构建了有效jumpdest位置的位集。

我们将 jumpdests 区段的最坏情况用作基准基线。 这是代码区段中的每个位置都是有效的 jumpdest 的情况。 也就是，字节码具有尽可能多的 jumpdest，从而使 jumpdests 区段尽可能大。 编码表示形式为 0x00, 0x01, 0x01, 0x01, ...。

这也恰好是 JUMPDEST 分析的最坏情况。

此外，我们从以太坊主网中选择了 5 个流行的合约。

对于最坏的情况，JUMPDEST 分析和 jumpdests 区段加载之间的性能差异非常小。 与内存复制（0.15 个周期/字节）相比，性能非常慢。

但是，对于最坏的情况，最大长度是不同的。 对于 JUMPDEST 分析，对于已部署的合约，这是 24576 (0x6000)，并且在 initcode 的情况下仅受 EVM 内存成本的限制（可以超过 1MB）。 对于 jumpdests 区段，对于已部署的合约，限制为 12288（已部署的字节码长度限制必须在 jumpdests 和代码区段之间平均分配）。 对于 initcode 情况，限制为 65535，因为这是 EOF 允许的最大区段大小。

对于“流行的”合约，获得的效率约为 10 倍，因为与代码区段相比，jumpdests 区段相对较小，因此要循环的字节比 JUMPDEST 分析少得多。

参考实现

我们扩展了 EIP-3670 的 validate_code() 函数：

# The same table as in EIP-3670
# 与 EIP-3670 中相同的表格
valid_opcodes = ...

# Remove JUMPDEST from the list of valid opcodes
# 从有效操作码列表中删除 JUMPDEST
valid_opcodes.remove(0x5b)

# This helper decodes a single unsigned LEB128 encoded value
# 此助手解码单个无符号 LEB128 编码的值
# This will abort on truncated (short) input
# 这将在截断（短）输入时中止
def leb128u_decode(input: bytes) -> (int, int):
  ret = 0
  shift = 0
  consumed_bytes = 0
  while True:
      # Check for truncated input
      # 检查截断的输入
      assert(consumed_bytes < len(input))
      # Only allow up to 4-byte long leb128 encodings
      # 仅允许最长 4 字节的 leb128 编码
      assert(consumed_bytes <= 3)
      input_byte = input[consumed_bytes]
      consumed_bytes += 1
      ret |= (input_byte & 0x7f) << shift
      if (input_byte & 0x80) == 0:
          # Do not allow additional leading zero bits.
          # 不允许额外的先导零位。
          assert(input_byte != 0 || consumed_bytes == 0)
          break
      shift += 7
  return (ret, consumed_bytes)

# This helper parses the jumpdest table into a list of relative offsets
# 此助手将 jumpdest 表解析为相对偏移量列表
# This will abort on truncated (short) input
# 这将在截断（短）输入时中止
def parse_table(input: bytes) -> list[int]:
  jumpdests = []
  pos = 0
  while pos < len(input):
      value, consumed_bytes = leb128u_decode(input[pos:])
      jumpdests.append(value)
      pos += consumed_bytes
  return jumpdests

# This helper translates the delta offsets into absolute ones
# 此助手将 delta 偏移量转换为绝对偏移量
# This will abort on invalid 0-value entries
# 这将中止无效的 0 值条目
def process_jumpdests(delta: list[int]) -> list[int]:
    jumpdests = []
    partial_sum = 0
    first = True
    for d in delta:
        if first:
            first = False
        else:
            assert(d != 0)
        partial_sum += d
        jumpdests.append(partial_sum)
    return jumpdests

# Fails with assertion on invalid code
# 如果代码无效，则断言失败
# Expects list of absolute jumpdest offsets
# 期望绝对 jumpdest 偏移量的列表
def validate_code(code: bytes, jumpdests: list[int]):
    pos = 0
    while pos < len(code):
        # Ensure the opcode is valid
        # 确保操作码有效
        opcode = code[pos]
        pos += 1
        assert(opcode in valid_opcodes)

        # Remove touched offset
        # 删除已触摸的偏移量
        try:
            jumpdests.remove(pos)
        except ValueError:
            pass

        # Skip pushdata
        # 跳过 pushdata
        if opcode >= 0x60 and opcode <= 0x7f:
            pos += opcode - 0x60 + 1

    # Ensure last PUSH doesn't go over code end
    # 确保最后一个 PUSH 不会超出代码结尾
    assert(pos == len(code))

    # The table is invalid if there are untouched locations
    # 如果存在未触摸的位置，则该表无效
    assert(len(jumpdests) == 0)

测试用例

有效字节码

• 没有 jumpdest
• 每个字节都是一个 jumpdest
• 遥远的 jumpdest（相距 0x7f 和 0x3f01 字节）
• 最大数量的 jumpdest
  • 1 字节偏移量编码：最大大小 (64K) 的 initcode，每个字节都有 jumpdest - 表格包含 65536 个 1 字节偏移量，第一个是 0x00，所有其他都等于 0x01
  • 2 字节偏移量编码：以 0x80 (128) 字节分隔的最大大小的 inicode - 表格包含 512 个偏移量，第一个是 0x7f (127)，所有其他都等于 0x8001
  • 3 字节偏移量编码：以 0x4000 (16384) 字节分隔的最大大小的 inicode - 表格包含 4 个偏移量：0xFF7F (16383)、0x808001、0x808001、0x808001

无效字节码

• 空的 jumpdest 区段
• 多个 jumpdest 区段
• 代码区段后的 jumpdest 区段
• 数据区段后的 jumpdest 区段
• 表格中的最终 jumploc 被截断（不是有效的 LEB128）
• 具有额外 0 的 LEB128 编码（非最小编码）
• 指向 PUSH 数据的 Jumpdest 位置
• jumpdest 位置超出代码区段范围
  • 指向数据区段
  • 指向 jumpdest 区段
  • 指向容器范围之外
• 重复的 jumpdest 位置（表格中除第一个偏移量以外的 0 个增量）
• 包含 JUMP 但没有 jumpdest 表的代码
• 包含 JUMPI 但没有 jumpdest 表的代码
• 包含 jumpdest 表但没有 JUMP/JUMPI 的代码
• 包含 JUMPDEST 的代码

向后兼容性

此更改不会对向后兼容性构成任何风险，因为它与 EIP-3540 同时引入。 JUMPDEST 表的要求不涵盖传统字节码。

安全考虑事项

作者未发现此更改带来的任何安全或 DoS 风险。

版权

在 CC0 下放弃版权及相关权利。

Citation

Please cite this document as:

Alex Beregszaszi (@axic), Paweł Bylica (@chfast), Andrei Maiboroda (@gumb0), "EIP-3690: EOF - JUMPDEST 表 [DRAFT]," Ethereum Improvement Proposals, no. 3690, June 2021. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-3690.