After some thought about it, here’s what I think:
- I agree with @lopeetall that recursion, or at least something morally close to it, is necessary to get most of the efficiency benefits
- The benefit of avoiding unnecessary branching paths depends a lot on the application. Cryptographic applications often don’t need much branching (indeed, it’s undesirable) and so it’s not been necessary for applications up until now. But of course, it could be that useful applications with lots of branching simply have been impractical without something like this.
- I don’t think the “interpreter” style of VM is necessary at all here, and it’s possible to achieve the stated goals without it. Indeed the word “zkVM” is now heavily overloaded, making things a bit murky.
If the primary goal is to allow efficient branching, then I think it’s not worth moving many parts of the execution model into the circuit, in particular the (I guess common) approach of having a circuit compute some steps or cycles of the VM by interpreting opcodes. I can understand why this approach is sometimes necessary (indeed, why VMs in general are useful) but I think it’s entirely tangential to the goal here.
Rather, when the zk-program has been compiled to an IR, the IR can be partitioned at every possible branch-point (or possibly more often) and each segment of the partition hardcoded into a circuit. Then a circuit on the other side of the cycle can ensure that each segment is computed with the correct sequence of VM states, and ensure that the correct sequence of segments is accumulated. Since the “instruction trace” of each segment is perfectly known at compile time, the resulting circuits don’t need to compute anything extra.