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.