Backward compatible SWAPN, DUPN, EXCHANGE

Abstract

Currently, SWAP* and DUP* instructions are limited to a stack depth of 16. Introduce three new instructions, SWAPN, DUPN and EXCHANGE which lift this limitation and allow accessing the stack at higher depths.

Motivation

While the stack is 1024 items deep, easy access is only possible for the top 16 items. Supporting more local variables is possible via manually keeping them in memory or through a "stack to memory elevation" in a compiler. This can result in complex and inefficient code.

Furthermore, implementing higher level constructs, such as functions, on top of EVM will result in a list of input and output parameters as well as an instruction offset to return to.

The number of these arguments (or stack items) can easily exceed 16 and thus will require extra care from a compiler to lay them out in a way that all of them are still accessible.

Lastly, swapping items besides the 1st and Nth items in the stack is very important for compilers implementing stack scheduling algorithms (the analog of register allocation for stack machines), which try to minimize stack traffic given a set of variables and usage analysis.

Introducing SWAPN, DUPN, and EXCHANGE will provide an option to compilers to simplify accessing deep stack items.

Specification

We introduce three new instructions:

• DUPN (0xe6)
• SWAPN (0xe7)
• EXCHANGE (0xe8)

Each instruction carries one or two immediate operands. Informally, using 1-based indexing, the semantics are:

• DUPN n: The n'th stack item is duplicated at the top of the stack.
• SWAPN n: The n + 1'th stack item is swapped with the top of the stack.
• EXCHANGE n m: The n + 1'th stack item is swapped with the m + 1'th stack item.

Formally, when code[pc] is one of these opcodes, the VM executes as follows:

• DUPN:
  1. Charge 3 gas.
  2. Let x = code[pc + 1].
  3. If 90 < x < 128, halt with exceptional failure.
  4. Let n = decode_single(x).
  5. If n > len(stack), halt with exceptional failure.
  6. Push stack[top - n + 1] on the stack.
  7. Set pc = pc + 2.
• SWAPN:
  1. Charge 3 gas.
  2. Let x = code[pc + 1].
  3. If 90 < x < 128, halt with exceptional failure.
  4. Let n = decode_single(x).
  5. If n + 1 > len(stack), halt with exceptional failure.
  6. Swap stack[top - n] and stack[top].
  7. Set pc = pc + 2.
• EXCHANGE:
  1. Charge 3 gas.
  2. Let x = code[pc + 1].
  3. If 81 < x < 128, halt with exceptional failure.
  4. Let n, m = decode_pair(x).
  5. If m + 1 > len(stack), halt with exceptional failure.
  6. Swap stack[top - n] and stack[top - m].
  7. Set pc = pc + 2.

code[pc + 1] evaluates to 0 if beyond the end of the code, matching PUSH behavior.

top denotes the index of the value at the top of the stack.

JUMPDEST analysis is unchanged. In particular, if code[i] is at an instruction boundary and is one of these opcodes, and code[i + 1] is 0x5b (JUMPDEST), then code[i + 1] is a valid jump target. Note that in this case the execution of code[i] would halt at step 2 above (because x = code[i + 1] = 0x5b = 91). Disassemblers must decode such code[i] as INVALID (or INVALID_DUPN, etc.) and code[i + 1] as JUMPDEST.

The auxiliary functions decode_single and decode_pair are defined by the following Python code:

def decode_single(x: int) -> int:
    """Returns n with 17 <= n <= 235."""
    assert 0 <= x <= 90 or 128 <= x <= 255
    return (x + 145) % 256

def decode_pair(x: int) -> tuple[int, int]:
    """Returns (n, m) with 1 <= n <= 14 and n < m <= 30 - n."""
    assert 0 <= x <= 81 or 128 <= x <= 255
    k = x ^ 143
    q, r = divmod(k, 16)
    if q < r:
        return q + 1, r + 1
    else:
        return r + 1, 29 - q

Assemblers and compilers must emit a 1-byte immediate after each of these opcodes that decodes to the required n, m operands. For reference, this can be done by encode_single and encode_pair:

def encode_single(n: int) -> int:
    assert 17 <= n <= 235
    return (n + 111) % 256

def encode_pair(n: int, m: int) -> int:
    assert 1 <= n < m and n + m <= 30
    if m <= 16:
        q, r = n - 1, m - 1
    else:
        q, r = 29 - m, n - 1
    k = 16 * q + r
    return k ^ 143

Rationale

Use of an immediate operand

Allowing dynamic selection of the arguments to swap or dup could be used to prevent static analysis of the contents of the stack. Since static analysis is an important tool for security auditors we want to do what we can to make their jobs easier. Hence, the operands require an immediate operand that is not dynamic in nature.

Disallowed immediate range

A property the EVM has is that it's not possible to jump to the middle of an instruction. In order to guarantee this property, the immediate operands of PUSH* instructions are masked from jumpdest analysis so that the occurrence of 0x5b in them is not mistaken for a JUMPDEST instruction, which should be considered a valid jump target elsewhere.

The new instructions in this EIP preserve this property without changing jumpdest analysis by making it invalid for their immediates to contain 0x5b, in addition to 0x60 to 0x7f (PUSH1 to PUSH32) since those would cause the subsequent instructions to be masked.

The alternative, changing jumpdest analysis to introduce new masked opcodes, would create a backwards incompatibility if done without bytecode versioning (EOF). Consider the bytecode sequence e6 5b that decodes to INVALID JUMPDEST prior to this EIP, and thus contains a valid jump target. If an instruction DUPN x were introduced with encoding e6 {x} (opcode immediately followed by operand), and jumpdest analysis changed to mask the operand to e6, the same bytecode sequence e6 5b would then decode to DUPN 0x5b. As a result of the upgrade, e6 would become an invalid jump target, breaking contracts that include this sequence. The opposite can happen with push opcodes, for example, e6 60 5b would transform from INVALID PUSH1 0x5b to DUPN 0x60 JUMPDEST, creating a new valid jump target. Furthermore, this may have a cascading effect on arbitrarily many subsequent instructions.

Since the EVM doesn't offer a dedicated section for data, arbitrary data may be embedded in code and serve as immutable data storage accessed via CODECOPY. Therefore, we must assume that arbitrary byte sequences may be found in contracts that have been deployed or are included in transactions yet to be published on chain.

This EIP is designed to uphold the following backwards compatibility guarantee: every possible execution trace on a given bytecode that does not attempt to execute an undefined opcode must continue to produce the same effect after the introduction of an instruction. No new JUMPDESTs must be created in a given bytecode by the introduction of an instruction and none may be removed.

This encoding can be reused in future instructions with immediate operands, although it is not necessary if the range of the operand naturally does not include the bytes 0x5b (JUMPDEST) or 0x60 (PUSH1) to 0x7f (PUSH32), in which case masking is not necessary.

EXCHANGE immediate

A previous formulation of EXCHANGE allowed swapping stack elements only if they were within some distance. As a result, it would be possible to swap the elements at indices 30 and 29, but not possible to move an element from index 30 to 2 with a single instruction. The current formulation prioritizes the latter, on the assumption that it is more valuable to move elements closer to the top of the stack than it is to rearrange elements deeper in the stack.

In addition, the exact formulation was chosen to make decode_pair a simple function using only basic arithmetic, bitwise operations (division by 16), and few branches. A small trade-off in the number of addressable pairs was made to reduce the number of necessary branches; this implies some of the immediate range is not allocated, and it could be used to add a dozen more addressable pairs at the cost of more decoding complexity, potentially in a future network upgrade.

Finally, note that the operands in the assembly instruction EXCHANGE n m appear "off by one", i.e. it operates on the stack elements at depths n + 1 and m + 1. These offsets were chosen to match the SWAP and SWAPN opcodes such that EXCHANGE n m has an effect equivalent to the sequence SWAP{n} SWAP{m} SWAP{n}.

Size of immediate operand

For DUPN and SWAPN a 16-bit size was considered to accommodate the full stack space of 1024 items, however:

1. that would require an additional restriction/check (n < 1024)
2. the 256 depth is a large improvement over the current 16 and the overhead of an extra byte would make it less useful

Similarly for EXCHANGE, the proposed scheme allows addressing of 30 items.

Gas cost

The gas cost for these operations is the same as for existing DUP* and SWAP* instructions, because they are just implemented as pointer swaps and immediate decoding is negligible.

EXCHANGE vs SWAPN

As mentioned before, EXCHANGE is important to compilers implementing stack scheduling algorithms. Specifically, in the case that a stack item is scheduled to be consumed deeper in the stack (for instance, the 3rd item in the stack needs to be moved into 2nd position in order to be consumed by the next operation), that currently takes three instructions, SWAP2 SWAP3 SWAP2. However, in the EVM implementation, the implementation is just a pointer swap, so it could be implemented in a single instruction at no extra runtime cost to the client.

Backwards Compatibility

This has no effect on contracts that would never attempt to execute the opcodes allocated by this EIP. The jump targets of existing contracts are preserved.

Test Cases

Assembly/Disassembly

• e680 is [DUPN 17]
• e7db is [SWAPN 108]
• e6805b is [DUPN 17, JUMPDEST]
• e75b is [INVALID_SWAPN, JUMPDEST]
• e6605b is [INVALID_DUPN, PUSH1 0x5b]
• e7610000 is [INVALID_SWAPN, PUSH2 0x0000]
• e65f is [INVALID_DUPN, PUSH0]
• e89d is [EXCHANGE 2 3]
• e82f is [EXCHANGE 1 19]
• e850 is [EXCHANGE 14 16]
• e851 is [EXCHANGE 14 15]
• e852 is [INVALID_EXCHANGE, MSTORE]

Execution

• 60016000808080808080808080808080808080e680 results in 18 stack items, the top of the stack valued 1, the bottom of the stack valued 1, the rest valued 0
• 600160008080808080808080808080808080806002e780 results in 18 stack items, the top of the stack valued 1, the bottom of the stack valued 2, the rest valued 0
• 600260008080808080600160008080808080808080e8 at the end of code results in 17 stack items, the bottom of the stack valued 1, the 10th stack item from the top valued 2, the rest valued 0
• 600060016002e88e results in 3 stack items, from top to bottom: [2, 0, 1]
• 600080808080808080808080808080808080808080808080808080808060016002e88f results in 30 stack items, the top of the stack valued 2, the bottom of the stack valued 1, the rest valued 0
• e75b reverts
• 600456e65b executes successfully (PUSH 04 JUMP INVALID_DUPN JUMPDEST)
• 60008080e88e15 results in 3 stack items, the top of the stack valued 1, the rest valued 0
• e852 reverts
• 6000808080808080808080808080808080e680 results in exceptional halt

Security Considerations

The authors are not aware of any additional risks introduced here. The EVM stack is fixed at 1024 items and most implementations keep that in memory at all times. This change will increase the number of stack items accessible via single instruction.

Copyright

Copyright and related rights waived via CC0.