zkVM part II: the executor
In the first part of the series, we ended with a question in mind:
"Starting with any arbitrary program X, how can I create a zero-knowledge proof of X's correct execution?"
Before we can create a proof of correct execution, we must first know exactly what execution we are proving. The portion of R0VM responsible for creating a detailed audit (or log) of the program's execution is called the executor.
For a given program X, the executor executes the program from start to finish, recording the complete state of the VM at every step. It does this to generate what's known as an execution trace.
You can think of the execution trace as a spreadsheet where each row corresponds to one step of the execution. Each column represents a part of the machine state (e.g., register values, memory contents) that is being recorded. Effectively, the execution trace is a comprehensive record of the program's entire computation.
Why is this useful? The execution trace provides a complete record of the program's execution. Reminding ourselves of our ultimate goal—to generate a "proof of correct execution"—the execution trace gives us the "correct execution" part. The next step will be proving this execution is indeed correct.
To wrap up, the executor is the component of R0VM responsible for generating the execution trace for the given program.
A bonus on "Witness Generation"
I had heard of the term "witness generation" before and it sounded spooky and complicated; and it's definitely complicated but not so spooky. In ZK terminology, the "witness" is everything that the prover knows that the verifier doesn't. In our context, the verifier doesn't have direct access to the program's full execution—otherwise, we wouldn't need to generate a zero-knowledge proof. They could simply run the program themselves. For the R0VM, the witness is precisely the execution trace. Ultimately, R0VM produces a proof of the witness, verifying that each step of the execution was valid. This proof is the only thing the verifier ever sees.
Relevant links: Crate Docs for the Executor