This article describes how to efficiently calculate gas and check stack requirements for Ethereum Virtual Machine (EVM) instructions.
Let’s start by defining some basic and universal instructions’ parameters.
Base gas cost.
This is the static gas cost of instructions. Some instructions may have additional cost depending on their operand values and/or the environment — these have to be handled individually during the instruction execution. The final cost is never lower than the base cost.
Stack height requirement.
This is the minimum stack height (number of items on the stack) required prior to the instruction execution.
Stack height change.
This is the difference in stack height before and after the instruction execution. Can be negative if the instruction pops more items than pushes.
Examples:
| opcode | base gas cost | stack height requirement | stack height change |
|---|---|---|---|
| ADD | 3 | 2 | -1 |
| EXP | 50 | 2 | -1 |
| DUP4 | 3 | 4 | 1 |
| SWAP1 | 3 | 2 | 0 |
| ADDRESS | 2 | 0 | 1 |
| CALL | 700 | 7 | -6 |
A basic instruction block is a sequence of “straight-line” instructions without jumps and jumpdests in the middle. Jumpdests are only allowed at the entry, jumps at the exit. Basic blocks are nodes in the control flow graph. See Basic Block in Wikipedia.
In EVM there are simple rules to identify basic instruction block boundaries:
JUMPDEST instruction.JUMP,JUMPI,STOP,RETURN,REVERT,SELFDESTRUCT.A basic instruction block is the shortest sequence of instructions such that a basic block starts before the first instruction and ends after the last.
In some cases multiple of the above rules can apply to a single basic instruction block boundary.
The algorithm for calculating gas and checking stack requirements pre-computes the values for basic instruction blocks, and during execution the checks are done only once per instruction block.
For a basic block we need to collect the following information:
This is done as follows:
class Instruction:
base_gas_cost = 0
stack_required = 0
stack_change = 0
class BasicBlock:
base_gas_cost = 0
stack_required = 0
stack_max_growth = 0
def collect_basic_block_requirements(basic_block):
stack_change = 0
for instruction in basic_block:
basic_block.base_gas_cost += instruction.base_gas_cost
current_stack_required = instruction.stack_required - stack_change
basic_block.stack_required = max(basic_block.stack_required, current_stack_required)
stack_change += instruction.stack_change
basic_block.stack_max_growth = max(basic_block.stack_max_growth, stack_change)
During execution, before executing an instruction that starts a basic block, the basic block requirements must be checked.
class ExecutionState:
gas_left = 0
stack = []
def check_basic_block_requirements(state, basic_block):
state.gas_left -= basic_block.base_gas_cost
if state.gas_left < 0:
raise OutOfGas()
if len(state.stack) < basic_block.stack_required:
raise StackUnderflow()
if len(state.stack) + basic_block.stack_max_growth > 1024:
raise StackOverflow()
Because requirements for a whole basic block are checked up front, the instructions that have observable external effects might not be executed, although they would be executed if the gas counting had been done per instruction. This is not a consensus issue because the execution terminates with a “hard” exception anyway (and all effects are reverted) but might produce unexpected traces or terminate with a different exception type.
In EVMJIT additional instructions that begin a basic block are GASand any of the call
instructions. This is because these instructions need to know the precise gas left counter value.
However, in evmone this problem has been solved without additional blocks splitting
by attaching the correction value to the mentioned instructions.
Undefined instructions have base gas cost 0 and no stack requirements.