I agree that IVC (Incrementally Verifiable Computation) is what we want and a ZKVM is a particular instance of IVC
where z_0 is the initial state and z_n is the final state, and the tuple (C,V) is the instruction/opcode executed. In our state machine we want to prove that for each state transition F, z_i = F^{(i)}(z_o).
This particular diagram is from Nova, a recent folding scheme. All other descriptions of IVC (from Valiant08 to Halo2) are very similar conceptually (they embed the verifier circuit V in the circuit C) and progress has been made in the direction of removing the cost of computing each step in the chain via an accumulator or otherwise and generally delaying the work of the verifier to the last step. Folding schemes are a type of recursive schemes that allow us to create non-monolithic SNARKs. They are efficient schemes that realise IVC by avoiding creating a SNARK at each of these intermediary steps.
However, IVC (understood as a single function that gets executed repeatedly) is not enough to realise our goal. In a ZKVM with multiple instructions, this would mean that the size of each instruction is linear to the size of all instructions. In other words, how do we choose which instruction to execute next efficiently? Similarly, how do we make sure that branching doesn’t blow up the size of the circuit? How can we avoid embedding every single branch in the circuit?
Fortunately, SuperNova introduced/popularised the concept of Non-uniform IVC (NIVC). This means that instead of one step function F you have a bunch of step functions \{F_i\} and you choose one. The size of the circuit and cost of computation are linear to only that F_i that gets executed.
\phi is a function that takes past information (\omega_{i-1}, z_{i-1}) to select next index i and thus execute C_i.
This is exactly what we need for our goal and in fact, the branching problem of ZKVMs was the main motivating factor for this feature, as explained in this slide about the “Limitations of State-of-the-Arts” by the Protostar authors (another folding scheme).
Basically, NIVC allows us to select the opcode/branch at runtime and the circuit to be proportional only to the size of the selected opcode or branch.
What work has been done in this regard?
In Nova, you have to embed all of the circuits for every opcode or branch in the recursive circuit. I believe this situation is similar to Halo2, i.e. neither of these can do NIVC.
Both Protostar (and its continuation work Protogalaxy) and SuperNova (and its continuation work HyperNova) realise Non-uniform IVC, and thus our purpose. As mentioned in previous posts, Jolt/Lasso also suits our goal. They all provide an “a la carte” cost profile, i.e. you pay only for what is executed.
Protostar has the advantage to be Plonk friendly and it was conceived with that goal in mind (as seen in the slide above), which may be easily adaptable to Halo2. It also realises Non-uniform PCD, which proves circuits in a DAG, instead of sequentially as IVC does. This may be an avenue to explore.