This is the fourth week of the zkEVM Bootcamp by Encode.
Interactive Oracle Proofs
The verifier gets oracle access to the prover message. There are different choices:
- Any polynomial IOP + IPA/Bulletproofs polynomial commitment. I.e. Halo2-ZCash
- Any polynomial IOP + FRI PCS. I.e. STARKS, Fractal. Aurora…
- Linear-PCP based: i.e. Groth16, proofs are very small, but we have to have a trusted setup for each circuit and it’s not post-quantum
- Constant-round polynomial IOP + KZG: i.e. ;arlin-KZG, Plonk-KZG
Polygon Proof Composition
- Composition: compose proofs of different types to take advantage of the different types of proving systems
- Recursion: converting a STARK proof into a Verifier circuit and then converting a Verifier circuit into a STARK proof
- Aggregation: a type of proof composition in which multiple valid proofs can be collated and proved to be valid by using one proof
SNARK
A SNARK is composed of:
- a probabilistic proof such as an IOP (information theoretic)
- a commitment scheme (cryptographic)
Arithmetisation
- turning our program (DSL) into typically a number of polynomials which the verifier can check succintly.
Polynomial checking
- we can express the constraints as: L:= ci· Li, R: ci · Ri
- P: = L · R – O (all of the lefts times all of the rights minus the outputs)
- The verifier then defines a target polynomial to represent all the constaints we have V(x):= (x-1) · (x -2)… This will be zero at the points that correspond to our gates. The polynomial P, having all the constraints information would be a some multiple of this if it is also zero at those points.
- To be zero at those points L · R – O must equate to zero, which will only happen if our constraints are met.