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:
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)\) |