Plonkathon

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
$ω_{i} L_{i} (X)$	`list_a`		`A_values + padding`	PR1	Scalar values of witness wire LEFT values
$ω_{n + i} L_{i} (X)$	`list_b`		`B_values + padding`	PR1	Scalar values of witness wire RIGHT values
$ω_{2 n + 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_{σ 1} (X)$	`S1`			PR1, PR3	1st permutation polynomial
$S_{σ 2} (X)$	`S2`			PR1, PR3	2nd permutation polynomial
$S_{σ 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
$ω^{j}$	`roots_of_unity`		`Scalar.roots_of_unity(group_order)`	PR2
$k_{1} ω^{j}$	`2 * roots_of_unity`			PR2
$k_{2} ω^{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
$P I (X)$	`PI_big`		`self.fft_expand(self.PI)`	PR3	Public Inputs in coset extended Lagrange basis
$Q L (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 ω)$	`Z_shifted_big`		`Z_big.shift(4)`	PR3	Shifted Permutation Grand Product polynomial in coset extended Lagrange basis
$S_{σ 1} (X)$	`S1_big`		`self.fft_expand(self.pk.S1)`	PR3	1st permutation polynomial in coset extended Lagrange Basis
$S_{σ 2} (X)$	`S2_big`		`self.fft_expand(self.pk.S2)`	PR3	2nd permutation polynomial in coset extended Lagrange Basis
$S_{σ 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_{l o} (X)$	`self.T1`		`Polynomial(QUOT_big_coeffs.values[:group_order], Basis.MONOMIAL).fft()`	PR3	$t (X)$ where: degree < n
$t_{m i d} (X)$	`self.T2`		`Polynomial(QUOT_big_coeffs.values[group_order : 2 * group_order], Basis.MONOMIAL).fft()`	PR3	$t (X)$ where: n <= degree < 2n
$t_{h i g h} (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_{l o}]_{1}$	`t_lo_1`	Y	`setup.commit(self.T1)`	PR3	Commitment of $t_{l o} (X)$
$[t_{m i d}]_{1}$	`t_mid_1`	Y	`setup.commit(self.T2)`	PR3	Commitment of $t_{m i d} (X)$
$[t_{h i}]_{1}$	`t_hi_1`	Y	`setup.commit(self.T3)`	PR3	Commitment of $t_{h i} (X)$
$\bar{a} = a (ζ)$	`a_eval`	Y	`self.A.barycentric_eval(self.zeta)`	PR4	A evaluated at $z e t a$
$\bar{b} = a (ζ)$	`b_eval`	Y	`self.B.barycentric_eval(self.zeta)`	PR4	B evaluated at $z e t a$
$\bar{c} = a (ζ)$	`c_eval`	Y	`self.C.barycentric_eval(self.zeta)`	PR4	C evaluated at $z e t a$
${\bar{s}}_{σ 1} = S_{σ 1} (ζ)$	`s1_eval`	Y	`self.S1.barycentric_eval(self.zeta)`	PR4	S1 evaluated at $z e t a$
${\bar{s}}_{σ 2} = S_{σ 1} (ζ)$	`s2_eval`	Y	`self.S2.barycentric_eval(self.zeta)`	PR4	S2 evaluated at $z e t a$
$ω$	`root_of_unity`		`Scalar.root_of_unity(self.group_order)`	PR4	1st root of unity
${\bar{z}}_{ω} = z_{(} ζ ω)$	`z_shifted_eval`	Y	`self.Z.barycentric_eval(self.zeta * root_of_unity)`	PR4	S2 evaluated at $z e t a$
$Z_{H} (ζ) = ζ^{n} - 1$	`Z_H_eval`		`zeta ** group_order - 1`	PR5	Zero polynomial evaluation at Zeta
$L_{1} (ζ)$	`L_1_eval`		`Z_H_eval / (group_order * (zeta - 1))`	PR5	Lagrange polynomial evaluation at Zeta
$W_{ζ} (X)$	`W_z`		`Polynomial(W_z_coeffs[:group_order], Basis.MONOMIAL).fft()`	PR5
$W_{ζ ω} (X)$	`W_zw`		`Polynomial(W_zw_coeffs[:group_order], Basis.MONOMIAL).fft()`	PR5	Proof of
$[W_{ζ}]_{1}$	`W_z_1`	Y	`setup.commit(W_z)`	PR5	Commitment of $W_{ζ} (X)$
$[W_{ζ ω}]_{1}$	`W_zw_1`	Y	`setup.commit(W_zw)`	PR5	Commitment of $W_{ζ ω} (X)$

Categories

Variables Structure & Examples

Variables Mapping

Notations