Proof of Meow: how ZK-VM works


If you have ever wondered how a ZK-VM works, below we explain it in one diagram, with an example of “Proof of Meow.” For more serious people, in the second section, we redraw this diagram to prove EVM instead of meow.

Section 1: for those who love kitties

Disclaimer: In this explanation, we use some mental models to provide intuition behind “how ZK-EVM works.” In fact, there are more details and nuances, check a series of articles by the PSE group on ZK-EVM to explore it in a more technical context.

For those who are here for Proof of Meow – let’s start.

ZK-VM stands for Zero-Knowledge Virtual Machine. It proves that the program was executed correctly.

  • “The program” is any program. In our case, “meow” is a program. The program is usually written in user-friendly languages like Solidity, Rust, Noir, etc.

  • To prove the program, it should be compiled to bytecode.

  • The compiler converts the source code (i.e., written by the developer) to bytecode (i.e., readable for the computer).

  • Bytecode looks more cryptic than high-level languages:

However, as we can see above, bytecode is just a set of instructions explaining to the Virtual Machine what to do. For example, PUSH1 says, “Put 1 byte of data into the stack”, EXP is used to perform exponentiation, and SUB stands for subtraction. So, the bytecode is literally a set of instructions that tells the VM how to execute the program step by step: do this, then do this, then do this, etc.

  • When the bytecode is compiled, it is executed inside of the VM. That is, the VM takes a list of instructions and executes them one by one. A result of this execution is called “execution trace.”

  • The execution trace contains a list of opcodes that were executed for a specific invocation of a program.

Example of execution trace:

  • Prover takes the execution trace and checks that the bytecode (of a certain instruction set) was executed correctly. Prover is a combination of hardware and software. To work as a prover, it is given a list of constraints and required data to prove them.

  • ZK-VM is a piece of software, a circuit, compiled into a set of constraints. The proof input contains program inputs and outputs. So the prover can put these specific inputs in the provided constraints and check that they result in specific outputs. A circuit is designed so that only a specific set of inputs can satisfy it. If a prover can satisfy the circuit, then it is enough to convince the verifier that the proof is valid.

  • Verifier is an algorithm that verifies the proof. It might be a smart contract (e.g., in Taiko) or a piece of software run by anyone.

Section 2: for serious people

For those not too interested in proving meow, the same intuition can be used to prove EVM. As we said at the beginning of this article, “ZK-VM proves that the program was executed correctly.” “The program” can be any program, including software that the node runs (for example, Ethereum node or Taiko node).

If we prove that the node runs the software correctly, it means that the EVM was executed correctly as well. That’s exactly how ZK-Rollups use ZK-EVMs to prove the blocks are valid in a more succinct way rather than re-executing all transactions.

Join us 💗

Explore open positions on our job board.

Follow us 🥁

Get the latest from Taiko:

Contribute 🤓

Contribute to Taiko on GitHub and earn a GitPOAP! You will also be featured as a contributor on our README. Get started with the contributing manual.

Subscribe to Taiko Labs
Receive the latest updates directly to your inbox.
Mint this entry as an NFT to add it to your collection.
This entry has been permanently stored onchain and signed by its creator.