EOF - Functions

Abstract

Introduce the ability to have several code sections in EOF-formatted (EIP-3540) bytecode, each one representing a separate subroutine/function. Two new opcodes,CALLF and RETF, are introduced to call and return from such a function. Dynamic jump instructions are disallowed.

Motivation

Currently, in the EVM everything is a dynamic jump. Languages like Solidity generate most jumps in a static manner (i.e. the destination is pushed to the stack right before, PUSHn .. JUMP). Unfortunately however this cannot be used by most EVM interpreters, because of added requirement of validation/analysis. This also restricts them from making optimisations and potentially reducing the cost of jumps.

EIP-4200 introduces static jump instructions, which remove the need for most dynamic jump use cases, but not everything can be solved with them.

This EIP aims to remove the need and disallow dynamic jumps as it offers the most important feature those are used for: calling into and returning from functions.

Furthermore, it aims to improve analysis opportunities by encoding the number of inputs and outputs for each given function, and isolating the stack of each function (i.e. a function cannot read the stack of the caller/callee).

Specification

Type Section

The type section of EOF containers must adhere to following requirements:

1. The section is a list of metadata where the metadata index in the type section corresponds to a code section index. Therefore, the type section size MUST be n * 4 bytes, where n is the number of code sections.
2. Each metadata item has 3 attributes: a uint8 inputs, a uint8 outputs, and a uint16 max_stack_increase. Note: This implies that there is a limit of 255 stack for the input and in the output. This is further restricted to 127 stack items, because the upper bit of both the input and output bytes are reserved for future use (outputs == 0x80 is already used in EOF1 to denote non-returning functions, as introduced in a separate EIP). max_stack_increase is further defined in EIP-5450.
3. The 0th code section MUST have 0 inputs and be non-returning.

Refer to EIP-3540 to see the full structure of a well-formed EOF bytecode.

New execution state in EVM

A return stack is introduced, separate from the operand stack. It is a stack of items representing execution state to return to after function execution is finished. Each item is comprised of code section index and offset in the code section (PC value).

Note: Implementations are free to choose particular encoding for a stack item. In the specification below we assume that representation is two unsigned integers: code_section_index, offset.

The return stack is limited to a maximum of 1024 items.

Additionally, EVM keeps track of the index of currently executing section - current_section_index.

New instructions

We introduce two new instructions:

1. CALLF (0xe3) - call a function
2. RETF (0xe4) - return from a function

If the code is legacy bytecode, any of these instructions results in an exceptional halt. (Note: This means no change to behaviour.)

First we define several helper values:

• type[i].inputs = type_section_contents[i * 4] - number of inputs of ith code section
• type[i].outputs = type_section_contents[i * 4 + 1] - number of outputs of ith code section
• type[i].max_stack_increase = type_section_contents[i * 4 + 2:i * 4 + 4] - maximum operand stack height increase of ith code section

If the code is valid EOF1, the following execution rules apply:

CALLF

1. Has one immediate argument,target_section_index, encoded as a 16-bit unsigned big-endian value.

2. Note: EOF validation EIP-5450 guarantees that operand stack has enough items to use as callee's inputs.

3. If operand stack size exceeds 1024 - type[target_section_index].max_stack_increase (i.e. if the called function may exceed the global stack height limit), execution results in exceptional halt. This also guarantees that the stack height after the call is within the limits.

4. If return stack already has 1024 items, execution results in exceptional halt.

5. Charges 5 gas.

6. Pops nothing and pushes nothing to operand stack.

7. Pushes to return stack an item:

   (code_section_index = current_section_index, 
   offset = PC_post_instruction)
   

   Under PC_post_instruction we mean the PC position after the entire immediate argument of CALLF.

   Note: EOF validation EIP-5450 guarantees there is always an instruction following CALLF (since terminating instruction or unconditional jump is required to be final one in the section), therefore PC_post_instruction always points to an instruction inside section bounds.

8. Sets current_section_index to target_section_index and PC to 0, and execution continues in the called section.

RETF

1. Does not have immediate arguments.
2. Note: EOF validation EIP-5450 guarantees that operand stack has exact number of items to use as outputs.
3. Charges 3 gas.
4. Pops nothing and pushes nothing to operand stack.
5. Pops an item from return stack and sets current_section_index and PC to values from this item.

Note: EOF validation requirement for 0th code section to be non-returning (non-returning sections introduced in a separate EIP) guarantees that return stack cannot be empty before RETF.

Code Validation

In addition to container format validation rules above, we extend code section validation rules (as defined in EIP-3670).

1. Code validation rules of EIP-3670 are applied to every code section.
2. Code section is invalid in case an immediate argument of any CALLF is greater than or equal to the total number of code sections.
3. RJUMP, RJUMPI and RJUMPV immediate argument value (jump destination relative offset) validation:
   1. Code section is invalid in case offset points to a position outside of section bounds.
   2. Code section is invalid in case offset points to one of two bytes directly following CALLF instruction.
4. No unreachable code sections are allowed, i.e. every code section can be reached from the 0th code section with a series of CALLF / JUMPF (JUMPF introduced in a separate EIP) instructions (0th code section is always reachable).

Disallowed instructions

Dynamic jump instructions JUMP (0x56) and JUMPI (0x57) are invalid and their opcodes are undefined.

JUMPDEST (0x5b) instruction is renamed to NOP ("no operation") without the change in behaviour: it pops nothing and pushes nothing to operand stack and has no other effects except for PC increment and charging 1 gas.

PC (0x58) instruction becomes invalid and its opcode is undefined.

Note: This change implies that JUMPDEST analysis is no longer required for EOF code.

Execution

1. Execution starts at the first byte of the 0th code section, and PC is set to 0.
2. Return stack is initialized empty.
3. Stack underflow check is not performed anymore. Note: EOF validation EIP-5450 guarantees that it cannot happen at run-time.
4. Stack overflow check is not performed anymore, except during CALLF as specified above.

Rationale

RETF in the top frame ends execution vs exceptionally halts vs is not allowed during validation

Alternative logic for RETF in the top frame could be to allow it during code validation and make it either:

• end execution if the return stack is emptied by the RETF or
• exceptionally halt if the return stack is empty before the RETF.

This has been superseded with the validation rule of top frame (0th code section) being non-returning (non-returning sections introduced in a separate EIP), because validating non-returning status of functions is valuable by itself for other reasons. Therefore all considerations of runtime behavior of RETF in the top frame were obsoleted.

"Minimal" function type

Let's consider a trivial function with single instruction RETF. Such function have the "minimal" type of inputs = 0, outputs = 0. However, any other type like inputs = k, outputs = k is also valid for such function. It has been considered to enforce usage of the "minimal" type for all functions. This requires additional validation rule that checks if any instruction in the function accesses the bottom stack operand. This rule can be obeyed by compilers, but causes quite significant annoyance. On the other hand, it provides close to zero benefits for the EVM implementations. In the end, it has been decided that this is not enforced.

Code section limit and instruction size

The number of code sections is limited to 1024. This requires 2-byte immediate for CALLF and leaves room for increasing the limit in the future. The 256 limit (1-byte immediate) was discussed and concerns were raised that it might not be sufficient.

NOP instruction

Instead of deprecating JUMPDEST we repurpose it as NOP instruction, because JUMPDEST effectively was a "no-operation" instruction and was already used as such in various contexts. It can be useful for some off-chain tooling, e.g. benchmarking EVM implementations (performance of NOP instruction is performance of EVM interpreter loop), as a padding to force code alignment, as a placeholder in dynamic code composition.

Deprecating JUMPDEST analysis

The purpose of JUMPDEST analysis was to find in code the valid JUMPDEST bytes that do not happen to be inside PUSH immediate data. Only dynamic jump instructions (JUMP, JUMPI) required destination to be JUMPDEST instruction. Relative static jumps (RJUMP, RJUMPI and RJUMPV) do not have this requirement and are validated once at deploy-time during EOF instructions validation. Therefore, without dynamic jump instructions, JUMPDEST analysis is not required.

Backwards Compatibility

This change poses no risk to backwards compatibility, as it is introduced only for EOF1 contracts, for which deploying undefined instructions is not allowed, therefore there are no existing contracts using these instructions. The new instructions are not introduced for legacy bytecode (code which is not EOF formatted).

The new execution state and multi-section control flow pose no risk to backwards compatibility, because it is a generalization of executing a single code section. Executing existing contracts (both legacy and EOF1) has no user-observable changes.

Security Considerations

The gas cost of introduced instructions reflects the need to manipulate return stack entries and jumping to proper code section offset in memory when interpreting the bytecode.

These new instructions need to be carefully considered during implementation of the EOF container validation algorithm.

Copyright

Copyright and related rights waived via CC0.