Plonkathon
Flying Nobita
by Flying Nobita
4 min read

Categories

I finally got a chance to try out the exercises from Plonkathon by 0xPARC, an educational implementation of PLONK. It follows closesly to the paper which is what makes it such a good resource to reinforce one’s learning (or to start learning) on PLONK.

I’ve made some notes in the relevant sections in the repo.

Here’re some notes I’ve taken which:

Variables Structure & Examples

## Round 1

Program(["e public", "c <== a * b", "e <== c * d"], 8)

witness: {None: 0, 'a': 3, 'b': 4, 'c': 12, 'd': 5, 'e': 60}

self.group_order = 8

program.constraints = 3

program.wires(): [Wire(L='e', R=None, O=None),
                  Wire(L='a', R='b', O='c'),
                  Wire(L='c', R='d', O='e')]

A_values: [60, 3, 12]
B_values: [None, 4, 5]
C_values: [None, 12, 60]

self.pk.QL = [1, 0, 0, 0, 0, 0, 0, 0]
self.pk.QR = [0, 0, 0, 0, 0, 0, 0, 0]
self.pk.QM = [0, 21888242871839275222246405745257275088548364400416034343698204186575808495616, 21888242871839275222246405745257275088548364400416034343698204186575808495616, 0, 0, 0, 0, 0]
self.pk.QO = [0, 1, 1, 0, 0, 0, 0, 0]
self.PI = [21888242871839275222246405745257275088548364400416034343698204186575808495557, 0, 0, 0, 0, 0, 0, 0]
self.pk.QC = [0, 0, 0, 0, 0, 0, 0, 0]

Variables Mapping

Notations

\([ \ ]_1\): commitment to Group 1

Paper Codebase In Proof / Round Outputs Function Appears Description
\(n\) group_order     PR1  
\(n\) program.constraints     PR1  
\(\omega_iL_i(X)\) list_a   A_values + padding PR1 Scalar values of witness wire LEFT values
\(\omega_{n+i}L_i(X)\) list_b   B_values + padding PR1 Scalar values of witness wire RIGHT values
\(\omega_{2n+i}L_i(X)\) list_c   C_values + padding PR1 Scalar values of witness wire OUTPUT values
\(a(X)\) self.A   Polynomial(list_a, Basis.LAGRANGE) PR1 LEFT wire polynomials in Lagrange Basis
\(b(X)\) self.B   Polynomial(list_b, Basis.LAGRANGE) PR1 RIGHT wire polynomials in Lagrange Basis
\(c(X)\) self.C   Polynomial(list_c, Basis.LAGRANGE) PR1 OUTPUT wire polynomials in Lagrange Basis
\([a]_1\) a_1 Y setup.commit(self.A) PR1 Commitment of \(a\)
\([b]_1\) b_1 Y setup.commit(self.A) PR1 Commitment of \(b\)
\([c]_1\) c_1 Y setup.commit(self.A) PR1 Commitment of \(c\)
\(q_M(X)\) QM     PR1, PR3 multiplication selector polynomial
\(q_L(X)\) QL     PR1, PR3 left selector polynomial
\(q_R(X)\) QR     PR1, PR3 right selector polynomial
\(q_O(X)\) QO     PR1, PR3 output selector polynomial
\(q_C(X)\) QC     PR1, PR3 constants selector polynomial
\(S_{\sigma1}(X)\) S1     PR1, PR3 1st permutation polynomial
\(S_{\sigma2}(X)\) S2     PR1, PR3 2nd permutation polynomial
\(S_{\sigma3}(X)\) S3     PR1, PR3 3rd permutation polynomial
\([z]_1\) z_1 Y setup.commit(self.Z) PR2 Commitment of \(z\)
\(z(X)\) self.Z   Polynomial(Z_values, Basis.LAGRANGE) PR2 Permutation Grand Product polynomial in Lagrange Basis
\(\omega^j\) roots_of_unity   Scalar.roots_of_unity(group_order) PR2  
\(k_1\omega^j\) 2 * roots_of_unity     PR2  
\(k_2\omega^j\) 3 * roots_of_unity     PR2  
  roots_of_unity_by_4   Scalar.roots_of_unity(4 * group_order) PR3  
\(X\) X   roots_of_unity_by_4_poly * self.fft_cofactor PR3  
\(k_1X\) two_X   roots_of_unity_by_4_poly * self.fft_cofactor * 2 PR3  
\(k_2X\) three_X   roots_of_unity_by_4_poly * self.fft_cofactor * 3 PR3  
\(a(X)\) A_big   self.fft_expand(self.A) PR3 A in coset extended Lagrange basis
\(b(X)\) B_big   self.fft_expand(self.B) PR3 B in coset extended Lagrange basis
\(c(X)\) C_big   self.fft_expand(self.C) PR3 C in coset extended Lagrange basis
\(PI(X)\) PI_big   self.fft_expand(self.PI) PR3 Public Inputs in coset extended Lagrange basis
\(QL(X), ...\) QL_big   self.fft_expand(self.pk.QL) PR3 Selector polynomials QL, QR, QM, QO, QC in coset extended Lagrange basis
\(z(X)\) Z_big   self.fft_expand(self.Z) PR3 Permutation Grand Product polynomial in coset extended Lagrange basis
\(Z(X\omega)\) Z_shifted_big   Z_big.shift(4) PR3 Shifted Permutation Grand Product polynomial in coset extended Lagrange basis
\(S_{\sigma1}(X)\) S1_big   self.fft_expand(self.pk.S1) PR3 1st permutation polynomial in coset extended Lagrange Basis
\(S_{\sigma2}(X)\) S2_big   self.fft_expand(self.pk.S2) PR3 2nd permutation polynomial in coset extended Lagrange Basis
\(S_{\sigma3}(X)\) S3_big   self.fft_expand(self.pk.S3) PR3 3rd permutation polynomial in coset extended Lagrange Basis
\(Z_H(X)\) Z_H   Polynomial(
[((self.fft_cofactor * x) ** group_order - 1)
for x in roots_of_unity_by_4],
Basis.LAGRANGE)
PR3 \(Z_H = X^N - 1\) in evaluation form in coset extended Lagrange basis
\(L_1(X)\) L0   Polynomial([1] + [0] * (group_order - 1), Basis.LAGRANGE) PR3 Lagrange basis polynomial:
\(L_1(x) = 1\) for \(x=1\)
\(L_1(x) = 0\) for any other \(x\)
  QUOT_big_coeffs   self.expanded_evals_to_coeffs(QUOT_big) PR3  
\(t_{lo}(X)\) self.T1   Polynomial(QUOT_big_coeffs.values[:group_order], Basis.MONOMIAL).fft() PR3 \(t(X)\) where: degree < n
\(t_{mid}(X)\) self.T2   Polynomial(QUOT_big_coeffs.values[group_order : 2 * group_order], Basis.MONOMIAL).fft() PR3 \(t(X)\) where: n <= degree < 2n
\(t_{high}(X)\) self.T3   Polynomial(QUOT_big_coeffs.values[2 * group_order : 3 * group_order], Basis.MONOMIAL).fft() PR3 \(t(X)\) where: 2n <= degree < 3n
\([t_{lo}]_1\) t_lo_1 Y setup.commit(self.T1) PR3 Commitment of \(t_{lo}(X)\)
\([t_{mid}]_1\) t_mid_1 Y setup.commit(self.T2) PR3 Commitment of \(t_{mid}(X)\)
\([t_{hi}]_1\) t_hi_1 Y setup.commit(self.T3) PR3 Commitment of \(t_{hi}(X)\)
\(\bar{a} = a(\zeta)\) a_eval Y self.A.barycentric_eval(self.zeta) PR4 A evaluated at \(zeta\)
\(\bar{b} = a(\zeta)\) b_eval Y self.B.barycentric_eval(self.zeta) PR4 B evaluated at \(zeta\)
\(\bar{c} = a(\zeta)\) c_eval Y self.C.barycentric_eval(self.zeta) PR4 C evaluated at \(zeta\)
\(\bar{s}_{\sigma1} = S_{\sigma1}(\zeta)\) s1_eval Y self.S1.barycentric_eval(self.zeta) PR4 S1 evaluated at \(zeta\)
\(\bar{s}_{\sigma2} = S_{\sigma1}(\zeta)\) s2_eval Y self.S2.barycentric_eval(self.zeta) PR4 S2 evaluated at \(zeta\)
\(\omega\) root_of_unity   Scalar.root_of_unity(self.group_order) PR4 1st root of unity
\(\bar{z}_{\omega} = z_(\zeta\omega)\) z_shifted_eval Y self.Z.barycentric_eval(self.zeta * root_of_unity) PR4 S2 evaluated at \(zeta\)
\(Z_H(\zeta) = \zeta^n - 1\) Z_H_eval   zeta ** group_order - 1 PR5 Zero polynomial evaluation at Zeta
\(L_1(\zeta)\) L_1_eval   Z_H_eval / (group_order * (zeta - 1)) PR5 Lagrange polynomial evaluation at Zeta
\(W_\zeta(X)\) W_z   Polynomial(W_z_coeffs[:group_order], Basis.MONOMIAL).fft() PR5  
\(W_{\zeta\omega}(X)\) W_zw   Polynomial(W_zw_coeffs[:group_order], Basis.MONOMIAL).fft() PR5 Proof of
\([W_{\zeta}]_1\) W_z_1 Y setup.commit(W_z) PR5 Commitment of \(W_{\zeta}(X)\)
\([W_{\zeta\omega}]_1\) W_zw_1 Y setup.commit(W_zw) PR5 Commitment of \(W_{\zeta\omega}(X)\)