Pragmatic stack manipulation tools

Abstract

Add SWAP17-SWAP24, DUP17 - DUP24, SWAPN, DUPN, and EXCHANGE instructions. The arbitrary depth operations must be preceded by PUSH1 instructions defining operands.

Motivation

Due to the nature of some compilers, deeper stack access is a desirable VM feature. Previous attempts either required code versioning, like the EVM Object Format (EOF), or caused the behavior of some deployed contracts to change, due to the interpretation of new immediates.

This is a pragmatic approach to introducing the desired functionality. It reuses instruction semantics that have been historically agreed on, instead of new, complex encodings and containers.

Specification

Let top - N be the Nth most recently pushed value on the stack, and top - 0 be the most recent.

If any of the following instructions reference a stack element beyond the current length of the stack, causing a stack underflow, abort with an exceptional halt.

Constant SWAPXX and DUPXX

Add the following new instructions:

• SWAP17, SWAP18, ..., SWAP24: 0xb0, 0xb1, ..., 0xb7.
• DUP17, DUP18, ..., DUP24: 0xb8, 0xba, ..., 0xbf.

Let SWAPXX and DUPXX refer to the static instructions defined above. XX is defined as the stack element they are referencing.

The operation SWAPXX swaps the top element with the top-XX element. The operation DUPXX duplicates the top-XX element and pushes the copy to the top of the stack.

SWAPN and DUPN

Add the following new instructions:

• SWAPN: 0xc0.
• DUPN: 0xc1.

Both operations take a single argument from the stack, N. This argument must be provided by a PUSH1 operation immediately preceding the SWAPN and DUPN instructions. Failure to follow this calling convention will result in an out-of-gas error. If N is zero, fail with out-of-gas error.

SWAPN pops N from the stack and swaps the new top stack element with the top-N stack element.

DUPN pops N from the stack and push on a copy of the top-N-1 stack element.

EXCHANGE

Add the following new instruction:

• EXCHANGE: 0xc2.

The EXCHANGE instruction takes a single argument from the stack X and deconstructs it into two operands, N and M. N is X >> 4 and M is X & 0x0F. The argument X must be provided by a PUSH2 operation immediately preceding the EXCHANGE instruction. Failure to follow this calling convention will result in an out-of-gas error. If either N or M are zero, fail with out-of-gas error.

EXCHANGE pops X from the stack and will swap the stack element at index N-1 with the stack element at M-1.

Gas costs

All operations cost 3 gas. Preceding push operations are charged separately according to the gas schedule.

Rationale

Constant and Dynamic SWAPs and DUPs

The main trade off between using the constant SWAPXX or DUPXX instructions versus the dynamic SWAPN or DUPN instructions is that the dynamic instructions require an additional two bytes in the form of a preceding PUSH1 operation, whereas the constant versions require no additional bytes.

One indexed EXCHANGE

Since SWAP1 and DUP1 operate on the top of the stack, it seems fitting that EXCHANGE(1, 2) operate on the top and top-1.

Backwards Compatibility

No backward compatibility issues found.

Test Cases

TODO

Security Considerations

When verifying the preceding PUSH operations, client implementers must ensure that the preceding bytes are not part of a longer segment of push data (e.g. 0x6301026001b0 should error). This can be done efficiently by checking if pc-2 is a valid jump destination. If it is, then the PUSH instruction will have been executed as expected.

Copyright

Copyright and related rights waived via CC0.