MODULE THREE
Building a SNARK (Part II):
In the third module of our introductory series, we construct a polynomial IOP by displaying algebraic ideas, such as Plonk. This is the third of three modules by Dan Boneh – Professor of Computer Science and Electrical Engineering at Stanford University.
What you’ll learn:
- Simple zero test for a committed polynomial
- Simple quality test for two committed polynomials
- Converting execution for circuit to computation trace
- Encoding computation trace as polynomial
- Four things the polynomial needs to commit to the verifier:
- P encodes correct inputs
- Every gate is evaluated correctly
- The wiring is implemented correctly
- The output of last gate is 0
Reading list consists of material from Module One and Module Two plus the following papers:
Recursive SNARKs:
- Nova: aggregating multiple SNARK proofs into one.
- Halo2: proving large statements using an accumulation scheme.
- Recursive zk-SNARKs from any additive polynomial commitment scheme: paper.
Specific proofs:
- Plookup: efficient table lookup — proving that the range of one committed polynomial is contained in the range of another. See also an efficient variant of Plonk for a circuit with table lookup gates.
- Caulk: a fast batch table lookup proof.
ZK Whiteboard Sessions is an educational series on all things zero knowledge. Produced by ZK Hack and powered by Polygon – we’ll be releasing a new module every week!
Get notified on latest module upload by signing up below.