Under the hood of zkSNARKs — PLONK protocol: part 6
Final article in PLONK series. Here we will implement Prover and the Verifier. In the previous article we coded trusted setup, gate and permutations polynomials, now we are ready to start generating proof.
The Prover
In the PLONK protocol, the prover is required to complete five rounds in a specified order. This process results in the creation of a proof comprising 9 Elliptic Curve Points and 6 Finite Field values.
Final implementations also can be found here:
Round 1
In Round 1, we need to compute wire polynomials, using the same technique employed for gate polynomials in the previous article. This technique involves converting vectors into polynomials via Lagrange interpolation. Additionally, it’s necessary to ‘blind’ the wire polynomials. For each of a, b, and c, we must generate blinding polynomials (such as b1x + b2, etc.). The use of blinding polynomials is based on a straightforward rationale. We utilize the KZG commitment scheme at the core, where each polynomial’s evaluation at a random value zeta reveals some information about the polynomial, contradicting the principles of zero-knowledge proofs. Hence, for our newly generated polynomials, we incorporate these blinding polynomials. Blinding polynomials are multiplied by the Vanishing polynomial Zh to generate correct polynomial commitments [a], [b], and [c]. Since evaluations occur over the roots of unity, Zh yields 0, making the blinding factor negligible. However, when the polynomials are evaluated at the random value zeta in round 4, the blinding polynomials will significantly affect the results.
random_b = [Fp.Random() for i in range(0, 9)]
# blinding polynomials
bA = galois.Poly(random_b[:2], field=Fp)
bB = galois.Poly(random_b[2:4], field=Fp)
bC = galois.Poly(random_b[4:6], field=Fp)
# wire polynomials
_A = to_poly(roots, a, Fp)
_B = to_poly(roots, b, Fp)
_C = to_poly(roots, c, Fp)
# Wire polynomials with blinding factor
A = _A + bA*Zh
B = _B + bB*Zh
C = _C + bC*Zh
# gate constraints polynomial
# g(x) = a(x)*ql(x) + b(x)*qr(x) + a(x)*b(x)*qm(x) + qc(x) + c(x)*qo(x)
G = A*QL + B*QR + A*B*QM + QC + C*QO
for i in range(0, len(roots)):
assert G(roots[i]) == 0, f"G({roots[i]}) != 0"
assert G % Zh == 0, f"G(x) % Zh(x) != 0"
# commitments [a], [b], [c]
round1 = [A(tau), B(tau), C(tau)]In Part 3, we discussed how to constrain gate polynomials, so the introduction of polynomial G should not be surprising to the reader. Instead of sending a commitment to G, we transmit three commitments because the Q polynomials are also known to the verifier, enabling them to easily reconstruct the commitment to G. Also, G polynomial used to verify if it is constrained correctly — it should equal zero at all roots of unity, indicating that it can be divided by Zh without a remainder. If this assertion fails, it implies that there was an error in the construction of the polynomial.
Round 2
Beta (β) and gamma (γ) are the first random values generated from a transcript in Round 1 ([a], [b], [c]). In Part 5, I mentioned the Fiat-Shamir heuristic as a mechanism for obtaining random values. Part 4 is dedicated entirely to the permutation polynomial z(x). The blinding polynomials in this context serve the same purpose as they did in Round 1.
beta = numbers_to_hash(round1 + [0], Fp)
gamma = numbers_to_hash(round1 + [1], Fp)
_F = (A + I1 * beta + gamma) * (B + I2 * beta + gamma) * (C + I3 * beta + gamma)
_G = (A + S1 * beta + gamma) * (B + S2 * beta + gamma) * (C + S3 * beta + gamma)
acc_eval = [Fp(1)]
for i in range(0, n):
acc_eval.append(
acc_eval[-1] * (_F(roots[i]) / _G(roots[i]))
)
assert acc_eval.pop() == Fp(1)
ACC = galois.lagrange_poly(roots, Fp(acc_eval))
bZ = galois.Poly(random_b[6:9], field=Fp)
Z = bZ * Zh + ACC
assert Z(roots[0]) == 1
assert Z(roots[-1]) == 1
round2 = [Z(tau)]Round 3
In Round 3, we encounter a substantial computational phase. The primary task involves calculating the polynomial t(x), pivotal for proving the entire statement. Let’s break this down:
- The first line involves the polynomial G from Round 1, divided by Zh(x) — the vanishing polynomials. This division aims to demonstrate that G equals 0 at every evaluation point (roots of unity). Therefore, if G(x)/Zh(x) divides without remainder, it indicates that the prover can provide a correct polynomial commitment for G.
- Line #4, featuring L1(x), equals 1 for the first element in the roots of unity and 0 for the others. The permutation check formula, detailed in Part 4, begins from
acc0=1. This necessitates addressing it in the t(x) polynomial. - The two middle polynomials can be simplified to f’(X)z(X) — g’(X)z(ωX) = 0 or, equivalently, f’(X)z(X) = g’(X)z(ωX). This simplification is to validate that the permutations are correct.
- The role of the α value is crucial. Instead of proving that multiple different polynomials are zero at the roots of unity, the protocol combines them as linearly independent terms. This allows their validation together for all these polynomials, as elaborated in Part 1.
- Splitting the t(X) polynomial into three parts is a protocol trade-off. To calculate the commitment to t(X), the prover would typically require more time compared to other polynomials due to its higher degree. Additionally, this also necessitates a larger size for the trusted setup.
def shift_poly(poly: galois.Poly, omega: Fp):
coeffs = poly.coeffs[::-1]
coeffs = [c * omega**i for i, c in enumerate(coeffs)]
return galois.Poly(coeffs[::-1], field=poly.field)
alpha = numbers_to_hash(round1 + round2, Fp)
Zomega = shift_poly(Z, omega=omega)
L1 = galois.lagrange_poly(roots, Fp([1] + [Fp(0)] * (n - 1)))
for i, r in enumerate(roots):
# make sure L1 equal 1 at root[0] and 0 for the rest
assert L1(r) == (Fp(1) if i == 0 else Fp(0))
T0 = G
assert T0 % Zh == 0, f"T0(x) % Zh(x) != 0"
T1 = (_F * Z - _G * Zomega) * alpha
assert T1 % Zh == 0, f"T1(x) % Zh(x) != 0"
T2 = (Z - galois.Poly([1], field=Fp)) * L1 * alpha**2
assert T2 % Zh == 0, f"T2(x) % Zh(x) != 0"
T = (T0 + T1 + T2)
assert T % Zh == 0, f"T(x) % Zh(x) != 0"
for r in roots:
assert T(r) == 0, f"T({r}) != 0"
T = T // Zh
t_coeffs = T.coeffs[::-1]
Tl = galois.Poly(t_coeffs[:n][::-1], field=Fp)
Tm = galois.Poly(t_coeffs[n:2*(n)][::-1], field=Fp)
Th = galois.Poly(t_coeffs[2*(n):][::-1], field=Fp)
X_n = galois.Poly.Degrees([n, 0], coeffs=[1, 0], field=Fp)
X_2n = galois.Poly.Degrees([2*(n), 0], coeffs=[1, 0], field=Fp)
# make sure that T was split correctly
# T = TL + X^n * TM + X^2n * TH
assert T == (Tl + X_n * Tm + X_2n * Th)
assert T.degree == 3 * n + 5
b10 = Fp.Random()
b11 = Fp.Random()
Tl = Tl + b10 * X_n
Tm = Tm - b10 + b11 * X_n
Th = Th - b11
assert T == (Tl + X_n * Tm + X_2n * Th)
round3 = [Tl(tau), Tm(tau), Th(tau)]Round 4
This round is the simplest The prover now needs to evaluate polynomials at a specific random point, zeta.
zeta = numbers_to_hash(round1 + round2 + round3, Fp)
a_zeta = A(zeta)
b_zeta = B(zeta)
c_zeta = C(zeta)
s1_zeta = S1(zeta)
s2_zeta = S2(zeta)
z_omega_zeta = Zomega(zeta)
round4 = [a_zeta, b_zeta, c_zeta, s1_zeta, s2_zeta, z_omega_zeta]Round 5
In Round 5 of the PLONK protocol, we focus on constructing the linearization polynomial r(X). The PLONK paper, on page 18, introduces an optimization technique titled ‘Reducing the number of field elements in the proof.’ This technique is applied to the r(X) polynomials. Let’s consider an example:
- The verifier aims to check the identity h1(X) · h2(X) − h3(X) ≡ 0. Typically, the prover would send the values of h1, h2, and h3 evaluated at a random point r, and the verifier would then check if h1(r) · h2(r) − h3(r) equals 0. In this scenario, the prover sends three field elements.
- However, the prover could simply send a single value c = h1(r), and the verifier can then verify if a new polynomial L(X) = c · h2(X) − h3(X) equals zero at the same point. Here, L(X) is referred to as the linearization polynomial.
- In the context of KZG, we can express this as computing [L] = c · [h2] − [h3]. This approach effectively reduces the number of field elements required in the proof.
The next two W polynomials function as openings in the KZG polynomial commitment scheme. They are composed with other polynomials that we aim to prove. To ensure their linear independence, we use the value ‘v’, which is employed for batching multiple polynomials into one, as detailed in Part 1.
v = numbers_to_hash(round1 + round2 + round3 + round4, Fp)
R = (QM * a_zeta * b_zeta +
QL * a_zeta +
QR * b_zeta +
QO * c_zeta +
QC)
R += (Z *
(a_zeta + beta * zeta + gamma) *
(b_zeta + beta * zeta * k1 + gamma) *
(c_zeta + beta * zeta * k2 + gamma) * alpha)
R -= (z_omega_zeta *
(a_zeta + beta * s1_zeta + gamma) *
(b_zeta + beta * s2_zeta + gamma) *
(c_zeta + beta * S3 + gamma) * alpha)
R += (Z - Fp(1)) * L1(zeta) * alpha**2
R -= Zh(zeta) * (Tl + zeta**n * Tm + zeta**(2*n) * Th)
X_minus_zeta = galois.Poly([1, -zeta], field=Fp)
Wzeta = R + \
(A - a_zeta) * v + \
(B - b_zeta) * v**2 + \
(C - c_zeta) * v**3 + \
(S1 - s1_zeta) * v**4 + \
(S2 - s2_zeta) * v**5
assert Wzeta % X_minus_zeta == 0, f"Wzeta(x) % X - zeta != 0"
Wzeta = Wzeta // X_minus_zeta
X_minus_omega_zeta = galois.Poly([1, -(omega*zeta)], field=Fp)
Womega_zeta = (Z - z_omega_zeta)
assert Womega_zeta % X_minus_omega_zeta == 0, f"Womega_zeta(x) % X - ω*zeta != 0"
Womega_zeta = Womega_zeta // X_minus_omega_zeta
round5 = [Wzeta(tau), Womega_zeta(tau)]
u = numbers_to_hash(round1 + round2 + round3 + round4 + round5, Fp)Finally the proof consists of 9 points and 6 field elements:
Verifier
Firstly, what the verifier needs to do with the proof is to check whether all 9 points are indeed on the elliptic curve, and whether the 6 elements are valid field elements. While I am not entirely certain of the reason for this, it might be related to mitigating the possibility of a weak curve attack. A weak curve attack in cryptography refers to a method of compromising elliptic curve cryptography (ECC) by exploiting weaknesses in the chosen elliptic curve. Therefore, an attacker might attempt to use points from a weaker curve to breach the protocol.
# Values provided by the prover (round 1 to 5) is a proof.
a_exp = round1[0]
b_exp = round1[1]
c_exp = round1[2]
z_exp = round2[0]
tl_exp = round3[0]
tm_exp = round3[1]
th_exp = round3[2]
# Note: verifier has to verify that the following values are in the correct Fp field
a_zeta, b_zeta, c_zeta, s1_zeta, s2_zeta, z_omega_zeta = round4
w_zeta_exp = round5[0]
w_omega_zeta_exp = round5[1]
# Note: verifier has to verify that the following values are on the curve
if encrypted:
validate_point(qm_exp)
validate_point(ql_exp)
validate_point(qr_exp)
validate_point(qo_exp)
validate_point(qc_exp)
validate_point(qpi_exp)
validate_point(z_exp)
validate_point(s1_exp)
validate_point(s2_exp)
validate_point(s3_exp)
validate_point(tl_exp)
validate_point(tm_exp)
validate_point(th_exp)
validate_point(a_exp)
validate_point(b_exp)
validate_point(c_exp)
validate_point(w_zeta_exp)
validate_point(w_omega_zeta_exp)Next, the verifier must calculate the challenges β, γ, α, zeta, v, and u using the elements provided in the proof.
beta = numbers_to_hash(round1 + [0], Fp)
gamma = numbers_to_hash(round1 + [1], Fp)
alpha = numbers_to_hash(round1 + round2, Fp)
zeta = numbers_to_hash(round1 + round2 + round3, Fp)
v = numbers_to_hash(round1 + round2 + round3 + round4, Fp)
u = numbers_to_hash(round1 + round2 + round3 + round4 + round5, Fp)All following steps are done according to paper:
# evaluate vanishing and L1 polynomial ar zeta
Zh_z = Zh(zeta)
L1_z = L1(zeta)
# PI_z = PI(z) - for public input
# Compute constant part of r polynomials,
# r0 = PI_z - L1_z ...
r0 = (- L1_z * alpha**2 -
(a_zeta + beta * s1_zeta + gamma) *
(b_zeta + beta * s2_zeta + gamma) *
(c_zeta + gamma) * z_omega_zeta * alpha)
# Compute first part of batched polynomial commitment
D_exp = (qm_exp * a_zeta * b_zeta +
ql_exp * a_zeta +
qr_exp * b_zeta +
qo_exp * c_zeta +
qc_exp)
D_exp += (z_exp * (
(a_zeta + beta * zeta + gamma) *
(b_zeta + beta * zeta * k1 + gamma) *
(c_zeta + beta * zeta * k2 + gamma) * alpha
+ L1_z * alpha**2 + u))
D_exp -= (s3_exp *
(a_zeta + beta * s1_zeta + gamma) *
(b_zeta + beta * s2_zeta + gamma) *
alpha * beta * z_omega_zeta)
D_exp -= ((tl_exp +
tm_exp * zeta**n +
th_exp * zeta**(2*n)) *
Zh_z)
F_exp = (D_exp +
a_exp * v +
b_exp * v**2 +
c_exp * v**3 +
s1_exp * v**4 +
s2_exp * v**5)
E_exp = (-r0 +
v * a_zeta +
v**2 * b_zeta +
v**3 * c_zeta +
v**4 * s1_zeta +
v**5 * s2_zeta +
u * z_omega_zeta)
if encrypted:
E_exp = G1 * E_exp
e1 = w_zeta_exp + w_omega_zeta_exp * u
e2 = (w_zeta_exp * zeta + w_omega_zeta_exp * (u * zeta * omega) +
F_exp + (E_exp * Fp(p-1)))
if encrypted:
pairing1 = tau.tau2.pair(e1)
pairing2 = G2.pair(e2)
print(f"pairing1 = {pairing1}")
print(f"pairing2 = {pairing2}")
assert pairing1 == pairing2, f"pairing1 != pairing2"
else:
print("\n\n--- e1, e2 ---")
print(f"e1 = {e1 * tau}")
print(f"e2 = {e2}")
assert e1 * tau == e2UPD: The article was originally written without considering public input. The final script has now been updated to include one parameter based on public feedback.
