Intro

In wave 1, we mainly follow the Plonk video series and read two articles for better understanding:

• https://www.cryptologie.net/article/527/understanding-plonk/
• https://www.cryptologie.net/article/610/plonks-permutation-the-definitive-explanation/

Video 1-6 cover fundamentals for absolute beginners in SNARK, I watched them for reviewing but won’t take detailed notes. You should know those concepts very well if you know Groth16:

• Arithmetic circuits and R1CS → my notes
• Plonkish arithmetization: Similar to R1CS but only allows addition OR mulitplication per row, in other words, additions don’t come in for free. This allows further optimization such as custom gates (will discuss this in my future halo2 articles)
• Lagrange Interpolation and Schwartz-Zippel Lemma → my notes

✅ Part 7: A sketch protocol with our polynomial

How does PLONK work? Part 7: A sketch protocol with our polynomial

In the previous video, we have done Lagrange Interpolation to transform Plonkish arithmetic circuits into polynomials:

$$ f(x) = L(x) \cdot q_L(x) + R(x) \cdot q_R(x) + O(x) \cdot q_O(x) + q_C(x) + L(x) \cdot R(x) \cdot q_M(x) $$

• $q_L(x)$: selector polynomial for addition gate, left entry
• $q_R(x)$: selector polynomial for addition gate, right entry
• $q_O(x)$: selector polynomial for output entry
• $q_C(x)$: selector polynomial for constant term
• $q_M(x)$: selector polynomial for multiplication gate

<aside> 💡 The $f(x) = 0$ in the screenshot above means that $f(x)$ evaluates to 0 at $x = 1$ and $x = 2$.

</aside>

Next we design an interactive proof protocol: