[Video](https://www.youtube.com/watch?v=SDOmw2TL20g) ### Proving Stack 1. Check correctness of computation 2. Apply arithmetization 3. Algebraic satisfication check 4. IOP 5. Apply crypto compiler 6. Final: argument system For plonk: 1. Halo2 2. Univariate polynomials 3. Custom gates 4. Polynomial IOP 5. KZG 6. Get PLONK! For Pinocchio / groth16 1. Circom 2. R1CS 3. QAP 4. Linear PCP / IP (interactive proof; multi round PCP) 5. Pairing 6. Groth16! Modern proving systems are modular so you can pick and choose what to use each part of the stack. Groth16 is not moduluar For Marlin / Fractal - use R1CS but don't use QAP or pairings ### Pinocchio / Groth16 - Polynomial identity holds if `L(x) * R(x) - O(x) / T(x) = H(x)` - Setup: - Sample a secret point `s` in F which is retrieved from trusted setup / MPC - To evaluate a secret point, precompute commitments to `s` so you can calculate `s` without needing to know what `s` is - The SRS generated is actually commitments to L, R, O and T (vanishing poly) - Similar to KZG in that we precompute committments, but this is NOT a PCS (polynomial commitment scheme) - But since you're committing to the L, R, O and T directly, they NEED to be circuit specific vs in KZG - That is why PLONK only requires 1 universal setup and groth16 requires circuit specific setup - KZG is calculating [s], [s]^2 etc - Prove: - Linear combinations of L, R, O, H (quotient polynomial) - Verify - Pairing check (QAP divisbility check) - `e(pL, pR) - e(pO, G1) = e(pH, commitment to T)` - 3 pairings - Equivalent to `L(s) * R(s) - O(s) = H(s) * T(s)` - We use pairings in order to preserve homomorphic multiplication of 2 "encrypted" values - We introduce an `alpha-shift` pL' and compare it with pL (QAP linear combination) - Alpha is not known to prover, similar to `s` - We need alpha shift because theres no way of knowing whether the L R O H group elements from the pairing is derived from your SRS - This is to check that you used the same alpha shift (QAP coeff consistency). We use a beta shift - B(pL, pR, pO) - - PLONK pairing only checks for the evaluation polynomial, not actually checking the polynomial identity in Groth16. - PLONK in fact doesnt even need a pairing if using FRI (merkle hashes). Groth pairing is NOT separable from linear PCP ### Marlin, Spartan, Fractal - R1CS but cuts off at QAP. They instead use Polynomial IOP (e.g KZG) - PLONK uses RAP which doesnt limit the degree of gates, whereas the 3 above use R1CS (limited to quadratic degree) - The quadratic limitation is that pairings are only limited to degree 2 ### Modularity: Recursion - **Biggest takeaway from this lecture** - Modern proof systems are all modular vs groth16 - 2 categories - Recursion - Proof composition ![](https://hackmd.io/_uploads/BymAGjSs3.png) - Full recursion - Need a sublinear verifier - Plonky2 - FRI verifier inside a circuit - Recursion to shrink size of proof. Each time proof size gets smaller - Atomic accumulation - IPA (linear time verifier) - Check accumulator is updated correctly - Linear time check at the end - Split accumulation - Nova is an example - Dont need sublinear verifier - Dont need sublinear argument - This is fine bc you only fold the public computation - Non uniform IVC - Supernova ### Modularity: Proof composition - Recursive verification - STARK verified in groth16 - Linkable commit and prove - LegoSNARK - Breakdown commputation into different circuits using optimized proving system and then link them back up - note: This is what we were thinking in terms of `split and aggregate` method @Sachin