EIP-2315: EVM 的简单子程序
用于高效、安全和静态子程序的两个操作码。
| Authors | Greg Colvin (@gcolvin), Martin Holst Swende (@holiman), Brooklyn Zelenka (@expede), John Max Skaller <skaller@internode.on.net> |
|---|---|
| Created | 2019-10-17 |
| Discussion Link | https://ethereum-magicians.org/t/eip-2315-simple-subroutines-for-the-evm/3941 |
| Requires | EIP-3540, EIP-3670, EIP-4200 |
Table of Contents
摘要
此提案提供了一个_完整_、高效、_安全_和_静态_的控制流工具。
它引入了两个新的操作码来支持从子程序的调用和返回：
RJUMPSUB relative_offset– 相对于子程序的跳转RETURNSUB– 在最近的RJUMPSUB之后返回到PC。
它依赖于 EIP-4200 提出的两个新操作码来支持静态跳转：
RJUMP relative_offset— 相对于PC + relative_offset的跳转RJUMPI relative_offset— 有条件的相对跳转
它弃用了 JUMP 和 JUMPI，允许有效的代码支持流式传输、单程和其他近乎线性的编译器。
与 EIP-3540 和 EIP-3670 结合使用，它可以确保在初始化时，有效的代码不会执行无效指令或跳转到无效位置，不会发生堆栈下溢，将为子程序维护一致的输入和输出数量，并且在没有递归的情况下将具有有界的堆栈高度。
这是满足这些要求的最简单的提案之一。
动机
完整的控制流工具。
跳转、条件跳转和子程序是由 Alan Turing 于 1945 年提出的，作为组织代码逻辑和设计其自动计算引擎的内存晶体的一种手段：
我们希望能够安排指令序列在各个点上分开，根据迄今为止的计算结果以不同的方式继续… 我们还希望能够安排将操作分解为辅助操作… 要开始辅助操作，我们只需要记录下我们停止主操作的位置，然后应用辅助操作的第一条指令。 当辅助操作结束时，我们查找注释并继续进行主操作。
— Alan Turing — 在 B.E. Carpenter, R.W. Doran, “另一台图灵机”。《计算机杂志》，第 20 卷，第 3 期，1977 年 1 月。
用更现代的术语来说，我们有指令序列、跳转和条件跳转，它们将序列划分为块、子程序调用以及要返回的地址堆栈。 细节有所不同，但类似的工具已经在过去 75 年中在一长串重要的机器上证明了它们的价值，包括我们已经编程或实现的大部分机器——包括 Burroughs 5000、CDC 7600、IBM 360、DEC PDP-11 和 VAX、Motorola 68000、Sun SPARC 和 Intel x86 等物理机器，以及 Scheme、Forth、Pascal、Java、Wasm 等的虚拟机。
与这些机器不同，以太坊虚拟机_不提供_子程序操作。 相反，它们必须使用动态 JUMP 指令来合成，该指令在堆栈上获取其目标。 此外，EVM _仅_提供动态跳转，阻碍了我们需要的静态分析。
高效的控制流。
可以手动编写，从高级语言编译，在部署时验证，由虚拟机解释以及编译为机器代码。
静态跳转、条件跳转和子程序在空间和时间上都足够高效，历史经验表明，我们将在下面的 EVM 中展示。
安全的控制流。
EVM 对安全性有异常高的要求。 许多智能合约不仅控制着数量过多的有价值的以太币，而且一旦放置在区块链上，任何缺陷对攻击者都是可见的，并且无法修复。 我们建议在初始化时静态验证代码上的重要安全约束。
静态控制流。
EVM 的动态跳转会导致两个主要问题。 首先，用动态跳转合成静态跳转和子程序的需要浪费了空间，并且通过不必要地复杂的代码浪费了 Gas，我们将在下面展示。
更糟糕的是，可以动态分支到代码中任何目标的跳转可能会在遍历控制流时导致二次“路径爆炸”。 对于以太坊来说，这是一种拒绝服务漏洞，它阻止我们在初始化时验证 EVM 代码的安全使用以及将 EVM 代码编译为机器代码。
我们_需要_静态控制流来验证程序安全性并将 EVM 字节码编译为机器代码——在时间和空间上与代码大小呈线性关系。
规范
操作码
RJUMPSUB (0x5f) relative_offset
将控制权转移到子程序。
- 从
PC处的立即数据中解码relative_offset。 - 将当前
PC + 3推送到return stack。 - 将
PC设置为PC + relative_offset。
relative_offset 相对于当前 PC。 该偏移量编码为双字节、二进制补码有符号整数，以 MSB 优先的方式存储。
Gas 成本是_low_。
RETURNSUB (0x5e)
将控制权返回给子程序的调用者。
- 将
return stack弹出到PC。
Gas 成本是_verylow_。
注意：
- 从
return stack弹出的值不需要验证，因为它们只能由RJUMPSUB和RETURNSUB更改。 - 上面的描述根据
return stack阐述了这些指令的语义。 但是return stack的实际状态对于 EVM 代码来说不是可观察的，也不是协议的关键共识。（例如，节点实现者可以编写RJUMPSUB以不可观察地将PC推送到return stack上，而不是PC + 1，只要RETURNSUB可以观察地将控制权返回到PC + 3位置，这是允许的。）
有效性
_执行_在黄皮书中定义为 EVM 状态中的一系列更改。 有效代码的条件由状态更改保留。 在运行时，如果指令的执行会违反条件，则执行处于异常停止状态。 黄皮书定义了六种这样的状态。
- Gas 不足
- 超过 1024 个堆栈项
- 静态调用期间的状态修改
- 堆栈项目不足
- 无效的跳转目标
- 无效指令
我们希望认为 EVM 代码是有效的，前提是程序的任何执行都不会导致异常停止状态。 实际上，我们必须在运行时测试前三个条件。 我们不知道会有多少 Gas，我们不知道递归可能会有多深，即使对于非递归程序，堆栈深度的分析也很重要，而且我们不知道调用是否是静态调用。 所有剩余的条件都必须静态验证，时间和空间与代码大小准线性相关。
有效代码的静态约束
- 每条指令必须有效：
JUMP和JUMPI指令无效。
- 每次跳转必须有效：
RJUMP、RJUMPI或RJUMPSUB指令不得寻址立即数据或代码段之外的地址。
- 堆栈必须有效：
data stack上的项目数必须始终为正数。return stack上的项目数必须始终为正数。
- 数据堆栈必须一致对齐：
- 数据堆栈的高度是
- 当前
stack pointer和进入当前子程序时的stack pointer之间的绝对差值。
- 当前
- 对于通过给定
PC的每个可到达路径，它必须相同 - 不得超过 1024。
- 数据堆栈的高度是
理由
这是一个纯粹的语义规范，除了作为操作码和立即数据的序列之外，没有对代码部分的语法施加任何约束——子程序不是字节码的连续序列，它是字节码的控制流图的子图。 EVM 是一个简单的状态机。 我们只承诺有效的代码不会，可以这么说，卡住机器的齿轮。
通过避免语法约束，我们可以进行优化，例如尾调用消除、多入口子程序、将“冷”代码移出内联以及其他减少冗余并将“热”代码保留在缓存中的方法。 由于我们希望支持将 EVM 代码进行单程编译为机器代码，因此至关重要的是，EVM 代码应尽可能提前进行优化。
验证
我们不通过语法来强制执行约束，而是通过验证来强制执行它们。
对有效代码的约束涵盖了我们可以验证的所有异常停止状态，并允许以与代码大小准线性相关的时间和空间来验证和编译代码。
RJUMP、RJUMPI 和 RJUMPSUB 指令将其 relative_offset 作为立即参数，该参数在运行时无法更改。 所有跳转都具有恒定的目标意味着所有跳转目标都可以在初始化时进行验证，而不是在运行时进行验证。 动态跳转可以分支到代码中的任何目标，因此在遍历控制流图时可能会出现可利用的二次“路径爆炸”。 弃用 JUMP 和 JUMPI 可以防止这种情况。
要求一致对齐的 data stack
- 防止堆栈下溢
- 确保对子程序的所有调用都具有相同数量的输入和相同数量的输出，并且
- 确保在没有递归的情况下堆栈高度是有界的。
要求一致对齐的 data stack 还允许一些遍历控制流图的算法（包括代码验证和编译）在连接处中断循环，从而再次防止二次路径爆炸。 当遍历到达先前访问过的 PC 时，它要么位于循环的开始处，要么位于函数的入口处。 由于该 PC 处的堆栈高度是恒定的，因此我们知道循环不会增长堆栈，并且子程序的参数数量将始终相同——可能不需要再次遍历该路径。
注意：JVM 和 Wasm 出于类似的原因强制执行类似的约束。
替代设计
子程序工具主要有几种设计，这里考虑其中两种。 其他的大多不适用于 EVM，例如 Wheeler Jump —— 一种将返回地址写入被调用子程序的自修改代码。
1. 将返回地址保存在专用的返回堆栈中。 图灵的设计经常被堆栈机器使用，包括用于 Forth、Java、Wasm 等的机器。 数据堆栈用于计算，专用堆栈用于返回地址。 单个指令足以调用例程，另一个指令用于从例程返回。
2. 将返回地址保存在数据堆栈中。 这种设计经常被寄存器机器使用，包括来自 CDC、IBM、DEC、Intel 和 ARM 的机器。 寄存器主要用于计算，堆栈维护返回地址、参数和局部变量的调用帧。 在 EVM 上，没有用于计算的寄存器，因此将堆栈用于这两个目的可能会导致我们在下面看到的这种效率低下。 Pascal p 代码确实使用了这种设计，但它是具有专用寄存器的复杂调用约定的一部分。
我们更喜欢专用的返回堆栈。
- 它保持了计算和控制流之间的清晰分离：
- 数据堆栈没有易受攻击的返回地址，并且
- 无法覆盖返回堆栈。
- 它可以提高效率：
- 它使用本机算术而不是 256 位 EVM 指令来处理返回地址，
- 不占用
data stack插槽来处理返回地址，并且 - 需要在堆栈上较少移动 256 位数据。
效率
我们在此说明与使用 JUMP 相比，如何使用子程序指令来降低普通和优化子程序调用的复杂性和 Gas 成本。
简单子程序调用
考虑一下一个相当小的子程序的这些示例，包括调用它的代码。
子程序调用，使用 RJUMPSUB：
SQUARE:
dup1 ; 3 gas
mul ; 5 gas
returnsub ; 3 gas
CALL_SQUARE:
push 0x02 ; 3 gas
rjumpsub SQUARE ; 5 gas
总 Gas：19
子程序调用，使用 JUMP：
SQUARE:
jumpdest ; 1 gas
swap1 ; 3 gas
dup1 ; 3 gas
mul ; 5 gas
swap1 ; 3 gas
jump ; 8 gas
CALL_SQUARE:
jumpdest ; 1 gas
push 0x02 ; 3 gas
push RTN_CALL: ; 3 gas
push SQUARE ; 3 gas
jump ; 8 gas
RTN_CALL:
jumpdest ; 1 gas
总计：41 Gas。
使用 RJUMPSUB 与 JUMP 相比，节省了_41 - 19 = 22 Gas_ — 提高了 54%。
尾调用优化
当然，在这种情况下，我们可以优化尾调用，以便从 SQUARE 返回实际上是从 TEST_SQUARE 返回。
尾调用优化，使用 RJUMPSUB 和 RETURNSUB：
dup1 ; 3 gas
mul ; 5 gas
returnsub ; 3 gas
CALL_SQUARE:
push 0x02 ; 3 gas
rjump SQUARE ; 3 gas
总计：17 Gas
尾调用优化，使用 JUMP：
SQUARE:
jumpdest ; 1 gas
swap1 ; 3 gas
dup1 ; 3 gas
mul ; 5 gas
swap2 ; 3 gas
jump ; 8 gas
CALL_SQUARE:
jumpdest ; 1 gas
push 0x02 ; 3 gas
push SQUARE ; 3 gas
jump ; 8 gas
总计：38 Gas
使用 RJUMPSUB 与 JUMP 相比，节省了 38 - 17 = 21 Gas — 提高了 55%。
效率注意事项
我们可以看到，这些指令提供了比使用 JUMP 更简单、更节省 Gas 的子程序机制——在我们的示例中，它们将 Gas 使用量减少了大约一半。
显然，对于已分解为较小子程序的程序，这种效率的好处更大。 有多小？ 使用 RJUMPSUB 和 RETURNSUB 将代码包装在子程序中只需花费_8 Gas_，而使用 JUMP、PUSH 和 SWAP 则需要花费_30 Gas_，如上所述。
成本
RJUMPSUB 的 low 成本与 JUMP 的 mid 成本相比是合理的，因为只需要解码 PC 的立即两字节目标并将返回地址推送到 return stack 上，所有这些都使用本机算术，而不是使用带有模拟 256 位指令的数据堆栈。
RETURNSUB 的 verylow 成本是合理的，因为它只需要将 return stack 弹出到 PC 中。 需要进行基准测试才能确定成本是否平衡良好。
向后兼容性
这些更改会影响现有 EVM 代码的语义：会被解释为有效跳转目标的字节现在可能会被解释为立即数据。 由于此提案依赖于以太坊对象格式来发出更改信号，因此这不是一个实际问题。
测试用例
简单例程
这应该跳转到一个子程序，然后返回并停止。
字节码：0x5f0003005e（RJUMPSUB 3, RETURNSUB, STOP）
| Pc | Op | Cost | Stack | RStack |
|---|---|---|---|---|
| 0 | RJUMPSUB | 5 | [] | [] |
| 2 | STOP | 0 | [] | [] |
| 3 | RETURNSUB | 3 | [] | [] |
输出：0x
消耗的 Gas：10
两层子程序
这应该可以正常执行，进入两个深度的子程序
字节码：0x5f00045F00025200（RJUMPSUB 4, RJUMPSUB 2, RETURNSUB, RETURNSUB, STOP）
| Pc | Op | Cost | Stack | RStack |
|---|---|---|---|---|
| 0 | RJUMPSUB | 5 | [] | [] |
| 3 | RJUMPSUB | 5 | [] | [] |
| 4 | RETURNSUB | 5 | [] | [] |
| 5 | RETURNSUB | 5 | [] | [] |
| 6 | STOP | 0 | [] | [] |
消耗的 Gas：20
失败 1：无效跳转
这应该会失败，因为给定的位置在代码范围之外。
字节码：0X5fff（RJUMPSUB -1）
| Pc | Op | Cost | Stack | RStack |
|---|---|---|---|---|
| 0 | RJUMPSUB | 10 | [] | [] |
Error: at pc=0, op=RJUMPSUB: invalid jump destination
错误：在 pc=0，op=RJUMPSUB: 无效的跳转目标
失败 2：浅 return stack
由于浅 return_stack，这应该在第一个操作码处失败
字节码：0x5e（RETURNSUB）
| Pc | Op | Cost | Stack | RStack |
|---|---|---|---|---|
| 0 | RETURNSUB | 5 | [] | [] |
Error: at pc=0, op=RETURNSUB: invalid retsub
错误：在 pc=0，op=RETURNSUB: 无效的 retsub
代码结尾处的子程序
在此示例中，RJUMPSUB 位于代码的最后一个字节上。 当子程序返回时，它应该到达字节码_之后_的“虚拟停止”，而不是因错误退出
字节码：0x5c00045e5fffff（RJUMP 4, RETURNSUB, RJUMPSUB -1）
| Pc | Op | Cost | Stack | RStack |
|---|---|---|---|---|
| 0 | RJUMP | 5 | [] | [] |
| 3 | RETURNSUB | 5 | [] | [] |
| 4 | RJUMPSUB | 5 | [] | [] |
| 7 | STOP | 0 | [] | [] |
消耗的 Gas：15
参考实现
以下是用于预测代码有效性的算法的伪 Python 实现。 等效的算法必须在初始化时运行。
此算法对程序执行符号执行，该执行递归地遍历 code，模拟其控制流和堆栈使用情况，并检查是否违反了上述规则。
它在程序的控制流图中以 O(vertices + edges) 的时间运行，其中边表示控制流，顶点表示 basic blocks —— 因此该算法花费的时间与 code 的大小成正比。 它维护一个用于条件跳转的延续堆栈，其大小最多与 code 的大小成正比。
验证函数
** 注意：已知此函数不完整且不正确。 **
为简单起见，我们假设已经完成了所有 jumpdest 分析和先前验证，包括 EIP-3540、EIP-3670 和 EIP-4200，因此 EOF 标头和部分格式良好，并且没有无效的指令或跳转。 实际上，所有验证过程都可以折叠成单个循环而无需递归。
我们还假设一些辅助函数。
is_valid(opcode)如果 opcode 有效则返回 true。is_terminator(opcode)如果 opcode 是终止符则返回 true。is_valid_jumpdest(pc)如果pc是有效的跳转目标则返回 true。immediate_data(pc)返回pc处指令的立即数据。immediate_size(opcode)返回 opcode 的立即数据的大小。removed_items(opcode)返回opcode从data_stack中删除的项目数。added_items(opcode)返回opcode添加到data_stack的项目数。
# 如果代码有效则返回 true
def validate_code(code: bytes, pc: int, sp: int, bp: int) -> boolean:
continuations = []
do
while pc < len(code):
opcode = code[pc]
if !is_valid(opcode):
return false
if is_terminator(opcode):
return true
# check stack height and return if we have been here before
# 检查堆栈高度，如果之前来过这里则返回
stack_height = sp - bp
if stack_height > 1024
return false
if pos in stack_heights:
if stack_height != stack_heights[pos]:
return false
return true
else:
stack_heights[pos] = stack_height
if opcode == RJUMP:
# reset pc to destination of jump
# 将 pc 重置为跳转的目标
jumpdest = immediate_data(pc)
pc += jumpdest
if !is_valid_jumpdest(pc)
return false
elif opcode == RJUMPI:
jumpdest = pc + immediate_data(pc)
if !is_valid_jumpdest(pc)
return false
# continue true side of conditional later
# 稍后继续条件的真侧
continations.push((jumpdest, sp, bp))
# continue false side of conditional now
# 现在继续条件的假侧
elif opcode == RJUMPSUB:
# will enter subroutine at destination
# 将在目标处进入子程序
bp = sp
# push return address and reset pc to destination
# 推送返回地址并将 pc 重置为目标
jumpdest = pc + immediate_data(pc)
if !is_valid_jumpdest(pc)
return false
push(return_stack, pc + 3)
pc = jumpdest
continue
elif opcode == RETURNSUB:
# will return to subroutine at destination
# 将返回到目标处的子程序
bp = sp
# pop return address and check for preceding call
# 弹出返回地址并检查前面的调用
pc = pop(return_stack)
if code[pc - 3] != RJUMPSUB:
return false
# apply instructions to stack
# 将指令应用于堆栈
sp -= removed_items(opcode)
if sp < 0
return false
sp += added_items(opcode)
# Skip opcode and immediate data
# 跳过操作码和立即数据
pc += 1 + immediate_size(opcode)
while (pc, sp, bp) = continuations.pop()
return true
安全注意事项
这些更改引入了新的流控制指令。 它们没有引入任何新的安全考虑因素。 此 EIP 旨在通过验证部署在区块链上的 EVM 代码的更高安全级别来提高安全性。 验证算法在时间和空间上必须是准线性的，而不是拒绝服务漏洞。 此处的算法对字节码进行一次线性时间传递，并使用一个延续堆栈，该堆栈不能超过代码中 RJUMPI 指令的数量。
版权
通过 CC0 放宽版权及相关权利。
Citation
Please cite this document as:
Greg Colvin (@gcolvin), Martin Holst Swende (@holiman), Brooklyn Zelenka (@expede), John Max Skaller <skaller@internode.on.net>, "EIP-2315: EVM 的简单子程序 [DRAFT]," Ethereum Improvement Proposals, no. 2315, October 2019. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-2315.