Plonkathon

I finally got a chance to try out the exercises from Plonkathon by 0xPARC, an educational implementation of PLONK. The exercises closely follow the paper, which is what makes them such a good resource for reinforcing one’s learning (or starting to learn) on PLONK.

I’ve made some notes in the relevant sections in the repo. Here are 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 }_i{L}_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_{\sigma 1}(X)$	S1			PR1, PR3	1st permutation polynomial
$S_{\sigma 2}(X)$	S2			PR1, PR3	2nd permutation polynomial
$S_{\sigma 3}(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_{1}X$	two_X		roots_of_unity_by_4_poly * self.fft_cofactor * 2	PR3
$k_{2}X$	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_{\sigma 1}(X)$	S1_big		self.fft_expand(self.pk.S1)	PR3	1st permutation polynomial in coset extended Lagrange Basis
$S_{\sigma 2}(X)$	S2_big		self.fft_expand(self.pk.S2)	PR3	2nd permutation polynomial in coset extended Lagrange Basis
$S_{\sigma 3}(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}}_{\sigma 1}=S_{\sigma 1}(\zeta )$	s1_eval	Y	self.S1.barycentric_eval(self.zeta)	PR4	S1 evaluated at $zeta$
${\bar{s}}_{\sigma 2}=S_{\sigma 1}(\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)$