zkVM

how to build zkVM:

What is zkVM?

zkVM is a circuit that knows how to execute a program, and generate a proof.

when we talk about a circuit, not in zkVM contest, the circuit is equivalent to the computation program. someone has the knowledge of zero knowledge proof can write the circuit, optimize it and have a particular verifier to verify the proof.

while a zkVM, the circuit is the zkVM itself, it take a program as input, and it knows how to transfer it to a circuit and execute it. and there is a universal verifier for zkVM, instead for a specific program. The user doesn’t need to have knowledge of zero knowledge, he can just write a program, put into zkVM, zkVM interpolate it to circuit, and run it, generates a proof for the execution.

for example, the input program can be a solidity smart contract, zkVM decode it, zkVM has some memory to process it.

another example, use circuit to present a loop, then the circuit should prepare the maximum loops even though most of the execution might do not use it. while zkVM can do it customize, the loops number can be tailed to the actually execution when the zkVM interpolate the program.

Building blocks

CPU

machine computation: execution (trace) states, transfer from one to the next.

TF: transition function

as long as TF accepts, the go next

RAM

lookup argument to connect the execution trace of cpu and trace in RAM

check lookup argument

Bitwise operation, hashing

when dealing with operations on different filed, need to consider range check (extra cost), to be more efficient, there will be specialized circuit to do it. to do bitwise operations. also the hashing (zk friendly, rescue, posiden)

check RISC-V ZK friendly instruction set(cario, myden), wasm, evm

this part of the video is very good

  • Summary of general zkVM design model (21:34)
  • Design considerations for zk VMs (23:42)

MIDEN

Building blocks

how to initialize the program (decoder)
  1. put the program as public input, downside: as the program become bigger,
  2. bootload: use the hash of the program , and verify the program is hashed to the public value
  3. MAST: merkle tree hash, selective reveal things to the verifier
Stack based, register base, memory machine (cario)
range check
chiplist (all specialized circuit): hasher, bitwiser, memory, padding

Decoder

how to translate program sudo code to a MAST

program sudo code: push pop,… then if, else, while loop

benefits: the prover can only use the input that actually executed: the split part, only one route is used, the other one can be removed, so the whole loop might be useless, save a lot.

Bitwise argument

randomized air with preprocessing rap

check this

https://hackmd.io/@aztec-network/plonk-arithmetiization-air

Leave a Reply

Your email address will not be published. Required fields are marked *