ZKP5.2 PLONK IOP

PLONK IOP"/>

ZKP5.2 PLONK IOP

ZKP学习笔记

ZK-Learning MOOC课程笔记

Lecture 5: The Plonk SNARK (Dan Boneh)

5.2 Proving properties of committed polynomials

• overview
  

• Polynomial equality testing with KZG

  • KZG: determined commitment (if the function is equal, then the commitment is equal too)

    • If the c o m f = c o m g com_f = com_g comf​=comg​, the verifier can tell if f = g f=g f=g on its own???

    • but
      

      • The verifier does not have the commitment of g 1 g 2 g 3 g_1g_2g_3 g1​g2​g3​

• Important proof gadgets for univariates
  

  • The size k is much smaller than d

• The vanishing polynomial
  

  • Outside the Ω \Omega Ω, the polynomial could evaluate an arbitrary value
  • Verifiers can evaluate the vanishing polynomial very fast.

• ZeroTest
  

  • F is zero on Ω \Omega Ω: All the elements of Ω \Omega Ω are the root of the polynomial.
  • Verifier time: O(log k) and two poly queries (but can be done in one batch)
  • Prover time: dominated by the time to compute q(X) and then commit to q(X)

• Product check
  

  • Polynomial t: auxiliary polynomial
    

- Use the ZeroTest
- Proof size: two commits, five evals (can be batched). 
- Verifier time: O(logk) 
- Prover time:O(klogk)

• For rational functions
  

• Permutation check
  

• f ^ \hat{f} f^​ and g ^ \hat{g} g^​ is identical
• Embellished permutation check
  • The two vectors are permutations to each other
  • They also satisfy a prediscribed pumutation
    

• Summary of proof gadgets
  

5.3 The PLONK IOP for general circuits

• PLONK widely used in practice
  

• PLONK: a poly-IOP for a general circuit
  

  • Encoding the trace as a polynomial
    

• Step 2: proving validity of T
  

  • (4): the output of the last gate is what the verifier is expecting
  • Proving (1): T encodes the correct inputs
    

- Proving (2): every gate is evaluated correctly

  - S(X) is a selector- Pre-processing: create the commitment of S(X), it is independent to any input.

- Proving (3): the wiring is correct

  - The W is independent of the inputs- Prescribed pumutation check

• The complete Plonk Poly-IOP (and SNARK)
  

• Many extensions

  • The SNARK can easily be made into a zk-SNARK

  • Main challenge: reduce prover time
    

  • A generalization: plonkish arithmetization

    • Plonk for circuits with gates other than + and × on rows (custom gates)
      

    • More columns on the table