Long-term L1 execution layer proposal: replace the EVM with RISC-V

Magicians Primordial Soup
,
124

Compilation is clearly beneficial for direct (CPU/GPU) execution.

For ZKP, it’s more tricky. SNARKs do not prove the program execution directly, but rather prove knowledge of the program execution trace (on some input).
Let’s assume f(x) is our program, x is some input to the program, w is the program execution trace (in some form). There is also some circuit C(x, w, y) to check the trace validity, i.e. C(x, w, f(x)) should output true for valid traces.
A SNARK prover typically proves satisfiability of such circuit (and that it knows the w witness), which is existentially quantified (due to the additional parameter w) and (in case of proving program execution) uniform (inputs/traces of different lengths are served by the same circuit).

So, it’s drastically different from the direct execution. The difference is critical for performance, as you can transform evaluation (sub)problems to circuit satisfiability (sub)problems, which might be much cheaper to prove (e.g. for proving 1 / a operation one has to provide some b and check that a * b == 1, while calculating the inverse directly will require proving much more intermediate steps).

Moreover, since the execution trace is available to prover it can select a cheaper implementation option, depending on the concrete trace content. E.g. a value can be u256 in general, but a particular occurrence can fit byte, so its properties/operations can be proved using less steps than the full u256 value.

So, the ability to inspect the trace can largely compensate absence of compilation. Static analyses/optimizations can still benefit ZKP (a call site can be recognized statically as monomorphic, so one can skip proving branch decisions). However, such optimizations are not that trivial to implement in practice:

  • one need to withstand “JIT bombs” attacks
  • one should prove somehow that such optimizations preserve semantics

With that said, I generally agree that compilation is the right direction. However, in the case of ZK proving of EVM code execution it’s not really clear whether compilation worth implementing given the associated costs. The EVM+EOF would definitely help here (e.g. static analysis, separate validation).

125

Compilation is of course useful in it’s own right. What I’m trying do here though is avoid the apparently high overheads of proving a program on an EVM interpreter written in RISC-V rather than proving a program written in RISV-V. Or even better, directly prove EVM programs.

2 Likes
126

This is the best option IMO.
It’s strange that Vitalik didn’t even consider it.

127

Makes sense. I take it that compiling from Rust you would see the same difficulties?

128

CPU-oriented code generation/optimization makes it more difficult to apply ZKP-oriented optimizations. So, with Rust → RISC-V approach to ZKP, one wants to rollback CPU-specific decisions, which can be difficult.

EVM bytecode retains more high-level info, so it’s better in that respect. EVM+EOF is even better here. YUL should be more or less the same. YUL with finer grained type info should be better.

One exception here is that RISC-V code operates with 32bit (64bit) values vs 256bit in case of EVM. So it retains stricter value bounds. It’s not a huge advantage since ZKP prover can inspec traces on the fly.

However, in case of (ZKP proving of) Rust smart-contracts one can start from IR like MLIR, or translate to LLZK.

129

OK. There is a trade-off - EOF’s structured functions - like Wasm’s, make linear-time interprocedural optimization difficult-to-impossible. I think the worst case is a quadratic, though one static analyst told me there are analyses that dynamic jumps render exponential or even undecidable.

1 Like
130

Thanks. We are getting pretty far past my understanding of ZK. But my overall take remains that RISC-V probably has some advantages, but they don’t begin to outweigh the cost of replacing the EVM (and its large and growing ecosystem) with a different one.

1 Like
132

long live ethererum …

133

Well, we are discussing problems that users do not really have.

There is absolutely no need to “prove” blockchain using ZK. It is a solution in search of a problem.

Blockchain is proven by re-executing the same code on zillions of nodes.

Bitcoin has done it from the beginning. ZK is just inferior, slow and complex. There is no need to modify EVM to make slow and complex ZK run just a little faster.