Inside the EVM Interpreter TODO
Concept
The EVM interpreter is a loop that reads bytecode one opcode at a time via a program counter and executes it as a stack machine. JUMP and JUMPI destinations must be a JUMPDEST opcode, and a byte position that happens to match that value inside a PUSH instruction's immediate data is not a valid destination. So implementations do a single linear scan of the code, skipping over each PUSH's data length, to build a valid-JUMPDEST bitmap up front, letting every jump be checked in O(1). Memory starts at zero and expands only in 32-byte words, and the expansion cost is the sum of a linear term and a quadratic term in the word count, so costs rise steeply the more you use. Cost is charged cumulatively based on "the highest offset reached so far," so re-writing an already-expanded region incurs no further expansion cost.
The quadratic term in the memory cost makes large calldata copies or big array processing much more expensive than expected, and not knowing the JUMPDEST rule leads to wrong assumptions in assembly or code-inspection logic.
Code & Formula
# EVM 인터프리터 내부 — PUSH 데이터를 건너뛰며 JUMPDEST 비트맵을 만들고, 메모리 확장 비용의 2차 항을 계산한다.
PUSH1, JUMPDEST, JUMP = 0x60, 0x5B, 0x56
# 단순화된 바이트코드: PUSH1 0x5B(=JUMPDEST와 같은 바이트값이지만 데이터!), PUSH1 5, JUMP, JUMPDEST, STOP
bytecode = [PUSH1, 0x5B, PUSH1, 0x05, JUMP, JUMPDEST, 0x00]
def build_jumpdest_bitmap(code):
valid = [False] * len(code)
pc = 0
while pc < len(code):
op = code[pc]
if op == JUMPDEST:
valid[pc] = True
pc += 1
elif PUSH1 <= op <= PUSH1 + 31: # PUSHn: 즉시 데이터 n바이트를 건너뜀
n = op - PUSH1 + 1
pc += 1 + n # 데이터 안의 0x5B는 목적지로 안 침
else:
pc += 1
return valid
valid = build_jumpdest_bitmap(bytecode)
print("바이트코드:", [hex(b) for b in bytecode])
print("유효 JUMPDEST 위치:", [i for i, v in enumerate(valid) if v])
print("pc=1(0x5B, PUSH1의 데이터 바이트)이 무효인 이유: PUSH1 뒤 1바이트라 건너뜀 ->", not valid[1])
def memory_expansion_cost(words):
# 옐로페이퍼 근사: 3*words + words^2 / 512 (선형 항 + 2차 항)
return 3 * words + (words * words) // 512
prev_words = 0
for target_words in (1, 10, 100, 1000, 10000):
total_now = memory_expansion_cost(target_words)
marginal = total_now - memory_expansion_cost(prev_words)
print(f"words={target_words:>6}: 누적비용={total_now:>10}, 이전 대비 한계비용={marginal:>10}")
prev_words = target_words
docs/code/algorithms/algorithms-27.py
Exercise
Compile a simple Solidity function, manually trace the bytecode to build the JUMPDEST bitmap, and measure the actual gas-usage difference between two versions that use different memory-expansion sizes to confirm the quadratic term.
Practical Connection
In Verex's settlement and order-processing contracts, just changing the memory-usage pattern can shift gas significantly, so this cost curve needs to be understood when designing an on-chain cost ceiling.
Where it lands in Jayverse
- Verex: add a gas-snapshot ceiling test. Beyond the existing cost-ceiling awareness, add a Foundry gas-snapshot test on settlement and order-processing functions that fails the build if memory-word count crosses a set ceiling, catching the quadratic cost before mainnet.
- DeFi: audit inline assembly for JUMPDEST assumptions. If jayverse-defi's liquid-staking contracts use computed jumps, treat the JUMPDEST-bitmap scan as a code-review checklist item, since a wrong assumption there corrupts control flow silently rather than reverting.
- Bridge/Token: flag large-calldata-copy paths in the relayer. Lock-and-mint calldata handling is exactly the shape that pays the memory-expansion quadratic penalty most; review those functions specifically for the cost curve, not just the happy-path gas estimate.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| happen to | 우연히 ~하다, 공교롭게 ~하다 · 의도치 않게 특정 조건과 일치할 때. "a byte position that happens to match that value" |
| linear scan | 선형 스캔(처음부터 끝까지 한 번 훑기) · 바이트코드를 순서대로 한 번 훑는 방식을 가리킬 때. "implementations do a single linear scan of the code" |
| up front | 미리, 사전에 · 실행 전에 필요한 작업을 먼저 해둘 때. "to build a valid-JUMPDEST bitmap up front" |
| cumulatively | 누적으로 · 비용이 이전까지 쓴 양을 합산해 계산될 때. "Cost is charged cumulatively based on" |
| rise steeply | 가파르게 오르다 · 비용이 완만하지 않고 급격히 증가할 때. "so costs rise steeply the more you use" |
| incur | (비용을) 발생시키다, 물게 되다 · 특정 동작이 추가 비용을 유발할 때. "incurs no further expansion cost" |
| lead to wrong assumptions | 잘못된 가정으로 이어지다 · 규칙을 모르면 코드 분석에서 착오가 생길 때. "leads to wrong assumptions in assembly or code-inspection logic" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.