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)
- put the program as public input, downside: as the program become bigger,
- bootload: use the hash of the program , and verify the program is hashed to the public value
- 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