EVM Bytecode Transpilation Targets for zkVM Proving (crush, RISC-V, WASM, custom IR)

evm_transpilation_targets.md

EVM Bytecode Transpilation Targets for zkVM Proving

Problem statement

To build a faster zkEVM, we must start from EVM bytecode — not Solidity source. Any deployed contract, any bytecode, must be provable. The two approaches are:

1. Interpret — run an EVM interpreter (e.g., revm) inside a zkVM. This is what we do today. The zkVM proves the interpreter.
2. Transpile — translate EVM bytecode into a target ISA and prove that directly. The zkVM proves the translated program.

The interpreter approach has ~2-5x overhead from dispatch, stack checks, and stack I/O (see overhead analysis). Can we do better by transpiling?

The EVM as a compilation source

The EVM is a stack machine with 256-bit words. Its key properties:

• Stack: max 1024 entries, each 256 bits. Operands are pushed/popped. Only the top 16 elements are accessible (via DUP1-DUP16, SWAP1-SWAP16).
• Memory: byte-addressable, dynamically expandable, costs gas to grow.
• Storage: 256-bit key → 256-bit value, persistent, expensive.
• Control flow: JUMP/JUMPI with dynamic targets (popped from stack), validated against JUMPDEST positions in the bytecode.
• No locals, no structured control flow: unlike WASM, there are no local variables, no function calls, no block/loop/if constructs. Just raw stack + jumps.

Any transpilation target must handle: (a) the stack discipline, (b) 256-bit arithmetic, (c) dynamic jumps, (d) gas metering, (e) storage/call host interactions.

Candidate targets

1. EVM → crush (infinite-register ISA)

crush is an infinite-register ISA designed for ZK proving via powdr. It already handles WASM → crush transpilation, flattening WASM locals and operand stack into virtual registers.

The EVM stack maps directly to crush registers. Within a basic block, the stack is fully visible — each stack slot becomes a virtual register:

EVM basic block:              crush equivalent:
  PUSH1 0x05                  r0 = 5
  DUP1                        r1 = r0           ; copy (or SSA alias)
  MUL                         r2 = mul256 r0, r1
  PUSH1 0x03                  r3 = 3
  ADD                         r4 = add256 r2, r3
  JUMP                        br @target

The EVM stack is gone — it's just registers. DUP becomes a copy, SWAP becomes a rename, POP becomes a dead register.

Why this is the best fit:

• Infinite registers: no spilling. A U256 is one register, not 4 (rv64) or 8 (rv32). DUP1; MUL is 1 copy + 1 multiply, not 16 loads + 16 stores + multiply + 8 stores.
• 256-bit native ops: if crush supports add256, mul256 etc. as single instructions, the 256-bit arithmetic overhead disappears. The proof system handles them natively instead of decomposing into 64-bit limbs.
• Existing infrastructure: the WASM → crush pipeline already solves the same problem (flattening a stack machine to registers). EVM is actually simpler than WASM (no locals, no structured control flow).
• powdr backend: crush feeds directly into powdr for proof generation. No extra layer.

What needs to be built:

• EVM → crush transpiler: map each EVM opcode to crush instructions, convert stack positions to virtual registers.
• Control flow recovery: EVM JUMP/JUMPI pop the target from the stack. Static analysis can resolve most targets (they're typically PUSH; JUMP patterns). For truly dynamic jumps, emit a jump table over all JUMPDEST positions.
• Gas metering: precompute the static gas cost per basic block. Emit a single gas check at basic block entry. Dynamic gas (SLOAD, CALL, memory expansion) requires runtime gas checks at those specific instructions.
• Stack bounds: emit one depth check per basic block entry (verify the stack has enough items and won't overflow).
• Host calls: SLOAD, SSTORE, CALL, CREATE, LOG, etc. become crush syscalls / host function calls. Same as in the interpreter — these are I/O operations, not computation.

Estimated complexity: moderate. The opcode → register mapping is mechanical. The hard part is control flow recovery for dynamic jumps and correct gas accounting.

2. EVM → RISC-V (direct transpilation)

Each EVM opcode becomes a canned RISC-V instruction sequence. The EVM stack lives in a memory array, but within a basic block, register allocation avoids redundant loads/stores.

EVM basic block:              RISC-V (rv64) equivalent:
  PUSH1 0x05                  li   a0, 5; li a1, 0; li a2, 0; li a3, 0  ; 4 limbs
  DUP1                        mv   a4,a0; mv a5,a1; mv a6,a2; mv a7,a3  ; copy 4 regs
  MUL                         ; ~40 instructions (schoolbook 4x4)
  PUSH1 0x03                  li   t0, 3; li t1, 0; li t2, 0; li t3, 0
  ADD                         ; ~10 instructions (4-limb add with carry)
  JUMP                        ; load target, validate, branch

Pros:

• OpenVM and other zkVMs already prove RISC-V.
• Existing bigint extensions (OpenVM) can accelerate 256-bit ops.
• Well-understood tooling and debugging.

Cons:

• Register pressure is severe. On rv64, a U256 occupies 4 registers. With 15 usable registers, you can hold ~3 live U256 values before spilling to memory. On rv32, it's 8 registers per U256 — essentially always spilling.
• No native 256-bit ops. Every ADD/MUL is a multi-instruction sequence. Unless the zkVM has custom extensions (like OpenVM's bigint), this is expensive.
• Limited gain over interpreter. Our analysis showed the interpreter on rv64 uses 78 instructions for MUL vs ~70 compiled. The dispatch overhead is real but modest compared to the arithmetic cost. The estimated improvement is ~2x on the same ISA.

Best for: incremental improvement over the interpreter, especially if the zkVM already proves RISC-V and has 256-bit extensions.

3. EVM → WASM → crush

Two-hop: transpile EVM bytecode to WASM, then use the existing WASM → crush pipeline.

Pros:

• Reuses the existing WASM → crush transpiler.
• EVM-to-WASM transpilers have been explored (Ewasm project, various L2 experiments).

Cons:

• Loses 256-bit semantics. WASM has no 256-bit type. The EVM-to-WASM step must lower all arithmetic to i64 limbs. The WASM → crush step then sees limb arithmetic, not 256-bit ops. If crush has native 256-bit support, this hop prevents using it.
• Extra translation layer. More complexity, more places for bugs, harder to audit for correctness.
• WASM overhead. WASM has its own stack, locals, structured control flow — an unnecessary abstraction layer for something as simple as the EVM.

Verdict: not recommended. Going through WASM loses information and adds complexity for no benefit.

4. EVM → custom ZK-friendly IR

Design a new IR specifically for EVM-to-ZK compilation: 256-bit native word size, SSA form, builtins for keccak/storage/calls. This is conceptually what circuit-based zkEVMs (PSE, Scroll, Polygon) do, but expressed as an instruction set rather than a circuit.

Pros:

• Can be perfectly tailored to EVM semantics.
• Can express constraints that general-purpose ISAs can't (e.g., "this is a keccak preimage-image pair").

Cons:

• Requires building an entirely new proof system and toolchain from scratch.
• Circuit-based zkEVMs have shown this is possible but extremely complex (years of engineering).
• Fragile: every EVM upgrade (new opcodes, changed gas costs, EOF) requires IR changes.

Verdict: too much effort when crush already exists as an extensible ZK-friendly ISA.

Comparison

	crush	RISC-V	WASM→crush	Custom IR
Registers per U256	1	4 (rv64) / 8 (rv32)	1 (after crush)	1
Register spilling	None	Constant	None	None
Native 256-bit ops	Yes (if added)	No (unless extensions)	No (lost in WASM hop)	Yes
Existing infra	WASM→crush exists	OpenVM proves rv32	Both exist	Nothing
New work needed	EVM→crush transpiler	EVM→RV transpiler	EVM→WASM transpiler	Everything
Estimated speedup vs interpreter	5-10x	~2x	~5-10x (extra hop cost)	~5-10x
Complexity	Moderate	Low	Moderate	Very high

Recommendation: EVM → crush

The mapping is natural, the infrastructure exists (powdr + crush), and the wins are substantial:

1. Stack elimination: EVM stack → virtual registers. DUP/SWAP/POP become free (register ops). This alone removes ~50% of interpreter overhead.
2. Native 256-bit arithmetic: if crush instructions like mul256 are first-class, the proof system can handle them in one step instead of proving 16+ multiply instructions.
3. Batched gas metering: one check per basic block, not per opcode.
4. Batched stack bounds: one depth check per basic block entry.
5. Direct powdr integration: crush → powdr → proof, no intermediate RISC-V step.

The main engineering task is the EVM → crush transpiler, which is a ~3-step process:

1. Parse EVM bytecode → identify basic blocks (split at JUMPDEST/JUMP/JUMPI boundaries).
2. Convert each basic block → simulate the stack symbolically, assign virtual registers to each stack position, emit crush instructions.
3. Link basic blocks → resolve jump targets, emit jump tables for dynamic jumps, insert gas/stack checks at entry points.

This is conceptually similar to what etk (EVM toolkit) does for EVM disassembly/analysis, or what revmc (the revm JIT compiler) does for native compilation — but targeting crush instead of x86.