Exploring PlonK

Review of PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge

This note walks through the core of the PlonK protocol—specifically, the five logical rounds in which the Prover generates a proof, and the steps from a given arithmetic circuit and witness to the final proof generation, all from the Prover's perspective.

Seeing the rounds end-to-end makes clearer why each PlonK piece exists and how completeness and soundness hang together.

Before the round-by-round walkthrough, I define the two fundamental challenges that the Prover must address and examine the strategies PlonK employs to solve them. This conceptual foundation will be essential for understanding the technical flow of the five rounds that follow.

1. What Must Be Proven?

The Prover's task is to prove that they have performed some computation $C$ to obtain a specific public output $y$, using a secret input $w$ in the process (i.e., $C(w) = y$), without revealing $w$. To achieve this abstract goal, we first express the computational process $C$ as an arithmetic circuit.

Proving the validity of this circuit specifically means demonstrating that the following two core constraints are both satisfied.

Start with the arithmetic circuit. The diagram shows a simple example of the calculation (x * y) + x = z expressed as a circuit.

Loading diagram…

Two prover jobs fall out of that picture.

The circuit has two arithmetic gates. Gate 1 performs multiplication, while Gate 2 performs addition.

Data flows between these gates through what we call wires. Here, w1 through w5 are the wires, each carrying values like x and y.

For example, the values in w1 and w2—namely x and y—enter Gate 1 and are multiplied. The result x*y is then stored in wire w3.

This value enters Gate 2, where it's added to the x value from w4, producing the final result z in w5.

1.1. Gate Constraints

An arithmetic circuit consists of multiple arithmetic gates, and PlonK enables the representation of all gates within the circuit through a single unified equation:

$q_L·a + q_R·b + q_O·c + q_M·(a·b) + q_C = 0$

• $a, b$: Values of the gate's left and right input wires
• $c$: Value of the gate's output wire
• $q_L, q_R, q_O, q_M, q_C$: Selector values that define the type of gate (left input, right input, output term, multiplication term, constant term, etc.)

Let's look at Gate 1. This is a multiplication gate. PlonK expresses all types of gates through a single unified equation.

For multiplication, qM, the switch that turns on the multiplication term, is set to 1, and qO, the switch that flips the sign of the output term, is set to -1.

All other switches are turned off to 0.

Then the originally complex unified equation transforms into the simple multiplication formula you see: a1 * b1 - c1 = 0, which is a1 * b1 = c1.

In other words, the Prover must prove that multiplying Gate 1's input values truly equals the output value.

Gate 2 is an addition gate. This time qL and qR are set to 1, qO is set to -1, and substituting these gives us the addition formula a2 + b2 = c2.

The Prover must also prove that this equation holds.

For each gate, the Prover must show that all such 'gate equations' are true. This is precisely the step that ensures computational correctness.

1.2. Connection Constraints (Wiring/Copy Constraints)

Verifying that individual gate operations are correct is not sufficient—we must also ensure that the output value of one gate is accurately transmitted as the input value to the next gate. For example, if the output wire of gate 1 connects to the input wire of gate 2, we must guarantee the Connection constraint that the equation $w_3 = a_2$ holds. Additionally, we must ensure the Copy constraint where wires $w_1$ and $w_2$ that should contain the same value satisfy the equation $w_1 = w_2$.

Consequently, the Prover's second challenge is to prove that all these wires are correctly connected according to the circuit's design and that values have been accurately copied. This ensures the correctness of the computational 'flow'.

These two constraints—computational correctness at every gate and connection integrity between all wires—constitute the concrete problem the Prover faces. In the next section, we will explore PlonK's strategy for efficiently transforming these numerous constraints into manageable mathematical structures.

2. Compiling Constraints into the Language of Polynomials

Checking every gate and wire constraint one by one does not scale. PlonK's core approach is to transform all these discrete constraints into continuous mathematical objects—namely, relationships between polynomials. Through this 'compilation' process, we can solve complex problems using the powerful tools of algebra.

PlonK's strategy can be viewed as the following two transformation processes:

2.1. Polynomial Representation of Wires

All wire values in the circuit have a specific ordering. PlonK considers these wire values as evaluations at specific points according to this ordering, and interpolates them to generate three polynomials:

• $a(X)$: A polynomial encoding all left input wire values of the gates
• $b(X)$: A polynomial encoding all right input wire values of the gates
• $c(X)$: A polynomial encoding all output wire values of the gates

For example, $a(X)$ is constructed to have the left input value of the $i$-th gate at the specific point $\omega^{i-1}$. Through this process, we can view the entire state of the circuit as being compressed into three concise polynomials.

2.2. Permutation Argument for Wiring

The most unique aspect is how copy constraints are handled. Instead of direct equations like "the value of wire A equals the value of wire B," PlonK adopts the following perspective:

The diagram below illustrates the permutation concept, showing how a set of wire values $(w_1, w_2, w_3, w_4)$ undergoes permutation $\sigma$ to become $(w_4, w_3, w_2, w_1)$, with only their positions changed.

Loading diagram…

"Wire values throughout the entire circuit merely exchange positions with each other; no new values are created or destroyed."

This means that a specific permutation relationship exists between wire indices in the circuit, and when values are moved according to this permutation, they must remain unchanged. The Prover's task transforms into defining a single permutation $\sigma$ that satisfies these complex connection relationships and proving that their constructed wire polynomials $a(X), b(X), c(X)$ respect this permutation $\sigma$. This proof is handled through an efficient technique called the "Grand Product Argument" using just one additional polynomial $z(X)$.

After that compilation step, the Prover's job is no longer a pile of discrete checks. They must prove that the polynomials they have constructed ($a, b, c, z$, etc.) satisfy specific polynomial identities.

In the following sections, we will step through the five concrete rounds that the Prover performs to achieve this goal.

3. Prover: 5-Step Proof Generation Process

The Prover builds the final proof $\pi_{SNARK}$ in five rounds. Each round involves responding to challenges received from the Verifier (or through the Fiat-Shamir Heuristic) and constructing the necessary proof components for the subsequent rounds.

Round 1: Wire Polynomial Construction and Commitment

Loading diagram…

The Prover begins by transforming all known wire values (witness) into a mathematically tractable form. The goal of this phase is to compress the circuit's entire execution state into three polynomials and secretly commit to them before the Verifier.

Procedure

Using the circuit's wire values $w_1, w_2, ..., w_{3n}$ corresponding to left inputs, right inputs, and outputs, the Prover constructs the following three wire polynomials $a(X), b(X), c(X)$:

$a(X) = (b_1X + b_2)Z_H(X) + \sum_{i=1}^{n} w_i L_i(X)$ $b(X) = (b_3X + b_4)Z_H(X) + \sum_{i=1}^{n} w_{n+i} L_i(X)$ $c(X) = (b_5X + b_6)Z_H(X) + \sum_{i=1}^{n} w_{2n+i} L_i(X)$

• $\sum_{i=1}^{n} w_i L_i(X)$

  • This component forms the polynomial's core content. The Lagrange basis polynomial $L_i(X)$ has the property of being 1 at the $i$-th point $\omega^{i-1}$ of the multiplicative subgroup $H$ and 0 at all other points in $H$. Thanks to this property, $a(X)$ takes exactly the values $w_1, w_2, ...$ in order at each point of $H$. This is the process of encoding wire values as polynomial evaluations.

• $(b_1X + b_2)Z_H(X)$ (Blinding)

  • This term serves as a blinding factor to ensure zero-knowledge. The values $b_1, b_2$ are random scalars known only to the Prover, and the vanishing polynomial $Z_H(X)$ equals zero at all points in $H$ where constraints will be checked. Therefore, this term randomizes the polynomial values outside $H$ without affecting constraint verification on $H$, preventing the Prover's secret wire values $w_i$ from being exposed through other polynomial evaluations.

Why This Design?

This phase serves two purposes. First, it represents the circuit's extensive wire values as three concise mathematical objects (polynomials), facilitating subsequent algebraic manipulations. Second, through a polynomial commitment scheme, the Prover commits to these values so they cannot be changed later, while simultaneously preventing information leakage through blinding.

Output: Components of the Complete Proof

The Prover performs KZG commitments on each of these three constructed polynomials, computing three group elements $[a]_1, [b]_1, [c]_1$. This constitutes the first piece of evidence the Prover generates and forms the foundation for all subsequent processes. With this, the Prover has effectively declared: "I will now make claims about these three polynomials, and I absolutely will not change their contents."

Round 2: Permutation constraints Proof and Commitment

While Round 1 represented the circuit's state as polynomials, Round 2 proves that the wiring between these states are correct. The goal of this phase is to compress numerous individual copy constraints into a single polynomial relationship, demonstrating that the circuit's wires have been implemented according to design.

Loading diagram…

Procedure

Using the polynomials $a(X), b(X), c(X)$ generated in Round 1 and the circuit's permutation information $\sigma$, the Prover constructs the grand product polynomial $z(X)$. This polynomial is constructed using random challenges $\beta$ and $\gamma$ generated through the Fiat-Shamir Heuristic.

$z(X)$ must satisfy the following recursive relationship at all points in $H$:

• Initial condition: $z(1) = 1$
• Recursive relation: $z(X\omega) = z(X) \cdot$ $\frac{(a(X) + \beta S_{ID_1}(X) + \gamma)(b(X) + \beta S_{ID_2}(X) + \gamma)(c(X) + \beta S_{ID_3}(X) + \gamma)}{(a(X) + \beta S_{\sigma_1}(X) + \gamma)(b(X) + \beta S_{\sigma_2}(X) + \gamma)(c(X) + \beta S_{\sigma_3}(X) + \gamma)}$

Here we use $S_{ID}(X)$ to denote the identity permutation for clarity.

The core idea of this recursive relation is as follows:

• Numerator $f(X)$: Terms that combine each wire value with its 'original position' information. $S_{ID_1}(X), S_{ID_2}(X), S_{ID_3}(X)$ are identity permutation polynomials representing the original position indices of the $a, b, c$ wires respectively.

• Denominator $g(X)$: Terms that combine each wire value with its 'post-permutation position' information. $S_{\sigma_1}(X), S_{\sigma_2}(X), S_{\sigma_3}(X)$ are polynomials encoding the actual permutation $\sigma$, representing the position indices after wire values have been connected and moved.

• $\beta$, $\gamma$: These random challenges prevent the Prover from cheating on the permutation relationship and strongly bind each wire value to its position information.

The following shows the decomposition by type for better understanding—this is the method for constructing the unique polynomial that simultaneously satisfies both rules above:

$z(X) = \underbrace{(b_7X^2 + b_8X + b_9)Z_H(X)}_{\text{Part 1}} + \underbrace{L_1(X)}_{\text{Part 2}} + \underbrace{\sum_{i=1}^{n-1} \left( L_{i+1}(X) \prod_{j=1}^{i} \frac{f(\omega^{j-1})}{g(\omega^{j-1})} \right)}_{\text{Part 3}}$

(Here $f(X)$ and $g(X)$ refer to the polynomials corresponding to the numerator and denominator of the recursive relation above.)

The Prover actually constructs the polynomial $z(X)$ satisfying these conditions using the Lagrange basis. This structure ensures that when elements of $H$ $(1, \omega, \omega^2, ...)$ are substituted for $X$, $z(X)$ takes exactly the step-by-step results of the cumulative product. It also includes a blinding term $(b_7X^2 + ...)Z_H(X)$ for zero-knowledge.

If the wire connections are correct (i.e., the permutation relationship holds), the set of values composing the numerator and the set composing the denominator will be exactly identical, differing only in order. Consequently, the cumulative product starts at $z(1)=1$ and ultimately returns to $z(\omega^n) = z(1) = 1$. The polynomial $z(X)$ encodes precisely this cumulative product process.

What happens if all wire connections are correct?

The complete set of values in the numerator and the complete set of values in the denominator are exactly identical, differing only in order. For example, if the numerator contains (value A, value B, value C), then the denominator contains something like (value C, value A, value B)—the same values just rearranged. Therefore, as we continue multiplying these fractions, all terms eventually cancel each other out. The Prover sets the start of this cumulative product as z(1) = 1.

If even a single connection is incorrect, the balance of this cumulative product breaks and the final value cannot equal 1.

Why This Design?

The purpose of this phase is to transform the circuit's most complex and unwieldy aspect—the connection constraints—into a single algebraically verifiable object $z(X)$. Instead of verifying millions of individual equality constraints $(c_1 = a_3, ...)$, we now only need to check whether a single polynomial $z(X)$ follows specific rules (starting and ending at 1, satisfying the recursive relation). This is a key idea for reducing the protocol's complexity.

Output: Components of the Complete Proof

The Prover performs a KZG commitment on the constructed permutation polynomial $z(X)$, computing the group element $[z]_1$. This constitutes the Prover's second piece of evidence. The Prover has now cryptographically committed to the claim: "The wire values I presented in Round 1 satisfy all permutation relationships specified in the circuit's wiring."

Round 3: Compressing All Constraints and the Quotient Polynomial

In the previous two rounds, the Prover represented and committed to the circuit's state ($a, b, c$) and wiring relationships ($z$) as polynomials. The goal of Round 3 is to compress into a single concise proof that all these polynomials actually comply with all of PlonK's rules.

Loading diagram…

Procedure

The Prover receives a new random challenge $\alpha$ through the Fiat-Shamir Heuristic. Using this $\alpha$, they combine all circuit constraints into a single polynomial and divide it by the vanishing polynomial $Z_H(X)$. The result is the quotient polynomial $t(X)$.

The core equation representing this relationship is:

$t(X)Z_H(X) =$ $(a(X)b(X)q_M(X) + a(X)q_L(X) + \dots + q_C(X) + PI(X))$ $+ α \cdot \Big( (a(X)+\beta S_{ID_1}(X)+\gamma)(b(X)+\beta S_{ID_2}(X)+\gamma)(c(X)+\beta S_{ID_3}(X)+\gamma) \cdot z(X) \Big)$ $- α \cdot \Big( (a(X)+\beta S_{\sigma_1}(X)+\gamma)(b(X)+\beta S_{\sigma_2}(X)+\gamma)(c(X)+\beta S_{\sigma_3}(X)+\gamma) \cdot z(X\omega) \Big)$ $+ α^2 \cdot \Big( (z(X)-1)L_1(X) \Big)$

Breaking this equation down by parts:

$t(X)Z_H(X) = \underbrace{(a(X)b(X)q_M(X) + a(X)q_L(X) + \dots + PI(X))}_{\text{Part 1: Gate constraints}}$ $+ α \cdot \Bigg( \underbrace{(a(X)+\dots) \dots (c(X)+\dots) \cdot z(X)}_{\text{Part 2a: Permutation relation (numerator)}} - \underbrace{(a(X)+\dots) \dots (c(X)+\dots) \cdot z(X\omega)}_{\text{Part 2b: Permutation relation (denominator)}} \Bigg)$ $+ α^2 \cdot \underbrace{\Big( (z(X)-1)L_1(X) \Big)}_{\text{Part 3: Permutation start constraint}}$

• First Part (Gate Constraints): This is PlonK's gate equation. If all computations were performed correctly at every gate, this polynomial should equal zero at all points in $H$. $PI(X)$ is the term handling public inputs, which includes adding the constant term $q_C(X)$.

• Second and Third Parts (Permutation Constraints): This section transforms the recursive relation from Round 2, $z(X\omega) = z(X) \cdot f(X)/g(X)$, into the form $f(X)z(X) - g(X)z(X\omega) = 0$.

  • Part 2a: Corresponds to the product of the permutation argument's numerator $f(X)$ and $z(X)$. Here, $S_{ID_1}(X), S_{ID_2}(X), S_{ID_3}(X)$ are identity permutation polynomials encoding the 'original positions' of the $a, b, c$ wires respectively.
  • Part 2b: Corresponds to the product of the permutation argument's denominator $g(X)$ and $z(X\omega)$. Here, $S_{\sigma_1}(X), S_{\sigma_2}(X), S_{\sigma_3}(X)$ are the actual permutation polynomials encoding the 'post-movement positions' of the wires.
  • $α$ multiplies the entire permutation constraint (Part 2a - Part 2b) with random weight $α$ to separate it from the gate constraints (Part 1), and this equation must hold over $H$.

• Third Part (Permutation Start Constraint): This enforces the constraint that $z(X)$ starts at 1 ($z(1)=1$). Since $L_1(X)$ equals 1 only at $X=1$ and 0 at all other points in $H$, this term extends the constraint $z(1)-1=0$ across all of $H$.

• $α$, $α^2$ (Random Weights): These random weights safely bind different types of constraints (gates, permutation rules, permutation start) into a single polynomial. Without $α$, different constraints might accidentally cancel each other out, creating opportunities for the Prover to cheat. To prevent this, each constraint is assigned an independent weight.

If we simply add without α, a malicious Prover could cleverly manipulate different constraints so that, for example, the 'gate constraint' deviates by +5 while the 'permutation constraint' deviates by -5, making the sum coincidentally equal to zero through trickery. The random value α serves as a firewall that makes such 'accidental cancellations' impossible. Until the Verifier reveals α, it becomes impossible to design such deceptions.

Why This Design?

The key idea of this phase is to transform the complex problem of "simultaneous satisfaction of numerous constraints" into the single problem of "one polynomial divides another polynomial."

If the Prover has honestly followed all rules, the combined polynomial constructed above will equal zero at all points in $H$, and therefore must divide perfectly by the vanishing polynomial $Z_H(X)$. As a result, the quotient $t(X)$ becomes a clean polynomial. If even one rule is violated, the division produces a remainder, causing $t(X)$ to become a rational expression rather than a polynomial, which would cause the subsequent commitment process to fail.

In conclusion, the Prover's successful presentation of the 'quotient polynomial' $t(X)$ itself serves as strong evidence that all previous constraints have been satisfied.

Output: Components of the Complete Proof

Since the quotient polynomial $t(X)$ typically has very high degree, the Prover splits it into three lower-degree polynomials $t_{low}(X), t_{mid}(X), t_{high}(X)$. They then perform KZG commitments on each of these three pieces, computing the group elements $[t_{low}]_1, [t_{mid}]_1, [t_{high}]_1$. This constitutes the Prover's third piece of evidence. The Prover has now effectively claimed: "All the polynomials I have presented satisfy all of PlonK's game rules."

Round 4: Polynomial Evaluation at Random Points

Up to this point, the Prover has formulated their claims as multiple polynomials ($a, b, c, z, t$) and cryptographically committed to them. The Verifier must verify that these polynomials satisfy specific identities, but cannot receive and check the entire polynomials. To solve this problem, PlonK leverages the Schwartz-Zippel Lemma (If two different curves (polynomials) exist, the probability that these two curves meet at a randomly chosen point is nearly zero (Negligible function)... Therefore, instead of comparing entire polynomials, the concept is that it's sufficient to randomly select one point and check whether the values are equal only at that checkpoint).

That is, instead of checking the entire identity, we only verify whether the equation holds at one randomly selected point.

The goal of Round 4 is to compute and reveal all necessary polynomial evaluations at this random point.

Loading diagram…

Procedure

The Prover generates a new random challenge $\zeta$ from all previous information through the Fiat-Shamir Heuristic. This $\zeta$ is the random evaluation point at which all polynomials will be evaluated.

The Prover evaluates their polynomials at $\zeta$ and its "neighbor" point $\zeta\omega$, computing the following values:

• $\bar{a} = a(\zeta)$
• $\bar{b} = b(\zeta)$
• $\bar{c} = c(\zeta)$
• $\bar{s}_{\sigma 1} = S_{\sigma 1}(\zeta)$
• $\bar{s}_{\sigma 2} = S_{\sigma 2}(\zeta)$
• $\bar{z}_{\omega} = z(\zeta\omega)$

These values will serve as the ingredients for the Verifier to directly construct the final identity in the subsequent verification phase.

Why This Design?

This phase achieves the proof's succinctness. Instead of sending entire polynomials that could have millions of coefficients, the Prover only needs to reveal a few numbers—the evaluations at specific points.

According to the Schwartz-Zippel Lemma, if two different polynomials exist, the probability that they coincidentally have the same value at a randomly chosen point $\zeta$ is negligibly small. Therefore, by confirming that all constraints hold at the single point $\zeta$, the Verifier can be confident with very high probability that the original polynomial identities themselves are correct. The evaluation at $\zeta\omega$ is necessary because the permutation constraint identity from Round 3 includes the relationship between $z(X)$ and $z(X\omega)$.

Output: Components of the Complete Proof

The Prover reveals the set of all computed evaluation values $(\bar{a}, \bar{b}, \bar{c}, \bar{s}_{\sigma 1}, \bar{s}_{\sigma 2}, \bar{z}_{\omega})$. These values are plain field elements, neither encrypted nor committed. This constitutes the Prover's fourth bundle of evidence, providing public information that enables the Verifier to directly compute the final verification equation. The remaining round will prove that these revealed values are indeed the genuine evaluations of the polynomials committed to in Rounds 1-3.

Round 5: Constructing the Batched Opening Proof

In Round 4, the Prover revealed evaluation values for multiple polynomials. However, the Verifier still cannot know whether these values are actual evaluations of the polynomials committed to in Rounds 1-3. The goal of Round 5 is to batch all these evaluation claims into a single efficient proof, ultimately demonstrating the validity of the revealed values.

Loading diagram…

Procedure

The Prover generates two new random challenges, $v$ and $u$, through the Fiat-Shamir Heuristic. $v$ serves to batch evaluations at the same point ($\zeta$), while $u$ batches evaluations at different points ($\zeta$ and $\zeta\omega$).

Using these challenges, the Prover constructs two opening proof polynomials, $W_\zeta(X)$ and $W_{\zeta\omega}(X)$:

1. Batched opening proof at point $\zeta$, $W_\zeta(X)$: $W_{\zeta}(X) = \frac{1}{X - \zeta} \left( r(X) + v(a(X) - \bar{a}) + v^2(b(X) - \bar{b}) + v^3(c(X) - \bar{c}) + v^4(S_{\sigma_1}(X) - \bar{s}_{\sigma_1}) + v^5(S_{\sigma_2}(X) - \bar{s}_{\sigma_2}) \right)$

(Part separation): $W_{\zeta}(X) = \frac{1}{X - \zeta} \Bigg( \underbrace{r(X)}_{\text{Part 1}} + \underbrace{v(a(X) - \bar{a}) + v^2(b(X) - \bar{b}) + \dots + v^5(S_{\sigma_2}(X) - \bar{s}_{\sigma_2})}_{\text{Part 2}} \Bigg)$

2. Opening proof at point $\zeta\omega$, $W_{\zeta\omega}(X)$: $W_{\zeta\omega}(X) = \frac{z(X) - \bar{z}_{\omega}}{X - \zeta\omega}$

• (Part 1) Linearization polynomial $r(X)$: This polynomial is the result of "linearizing" the complex identity related to $t(X)$ from Round 3 with respect to $\zeta$. That is, it treats the evaluation values at $\zeta$ ($\bar{a}, \bar{b}, ...$) as constants. $r(X)$ verifies consistency between the $t_{low}, t_{mid}, t_{high}$ committed in Round 3 and the evaluation values revealed in Round 4.
• (Part 2) Terms batched with $v$: This combines all evaluation claims at point $\zeta$, such as $a(\zeta)=\bar{a}$, $b(\zeta)=\bar{b}$, etc., into a single polynomial using powers of the random weight $v$.
• Division by $(X - \zeta)$: If all claims are true, the polynomial inside the parentheses should equal zero when $X=\zeta$. Therefore, it divides perfectly by $(X-\zeta)$, and the quotient is precisely $W_\zeta(X)$.

Why This Design?

This phase maximizes the protocol's efficiency by leveraging batching techniques for KZG polynomial commitments. Instead of opening individual evaluation claims one by one, the random challenges $v$ and $u$ transform all claims into a single polynomial identity problem.

As a result, the Verifier can verify all of the Prover's claims at once with just one final pairing equation, without needing to perform multiple expensive pairing operations. This makes the Verifier's computation constant regardless of the number of claims, enabling PlonK's fast verification speed—a crucial optimization technique.

Output: Components of the Complete Proof

The Prover finally performs KZG commitments on the two opening proof polynomials $W_\zeta(X)$ and $W_{\zeta\omega}(X)$, computing the group elements $[W_\zeta]_1$ and $[W_{\zeta\omega}]_1$. These constitute the Prover's final pieces of evidence.

Now, gathering all components generated from Rounds 1 through 5 (commitments, evaluation values, opening proofs), the final proof $\pi_{SNARK}$ is complete and transmitted to the Verifier.

4. Verifier: Single-Pass Verification

The final proof $\pi_{SNARK}$ generated by the Prover consists of a batched structure containing multiple commitments, evaluation values, and opening proofs. The Verifier's task is to use this proof to verify that the Prover actually performed valid computations—without the Prover's secret information (witness) and in a highly efficient manner.

The PlonK Verifier does not trace back through the Prover's process. Instead, it constructs a single final equation that can verify everything at once, and simply checks whether this equation holds.

Procedure

The Verifier receives the proof $\pi_{SNARK}$ and public inputs $(w_i)_{i\in[\ell]}$, and performs verification through the following steps:

1. Proof Validity Check and Challenge Recovery

• Verifies that the group elements and field elements contained in the received $\pi_{SNARK}$ are in the correct format.
• Using the same method as the Prover, sequentially hashes the public information and each part of the proof to recover all random challenges $\beta, \gamma, \alpha, \zeta, v, u$.

2. Vanishing and Lagrange Polynomial Evaluation

• Evaluates the vanishing polynomial $Z_H(X)$ at $\zeta$: $Z_H(\zeta) = \zeta^n - 1$.
• Evaluates the first Lagrange polynomial $L_1(X)$ at $\zeta$: $L_1(\zeta)$.
• Evaluates the public input polynomial $PI(X)$ at $\zeta$: $PI(\zeta) = \sum_{i\in[\ell]} w_i L_i(\zeta)$.

3. Computing the Linearization Polynomial $r(X)$ Evaluation $r(\zeta)$

• Instead of constructing $r(X)$ directly, computes its evaluation value $r(\zeta)$ directly:

$r(\zeta) = \bar{a}\bar{b}q_M(\zeta) + \bar{a}q_L(\zeta) + \bar{b}q_R(\zeta) + \bar{c}q_O(\zeta) + PI(\zeta) + q_C(\zeta)$ $+ \alpha \cdot ( (\bar{a}+\beta\zeta+\gamma)(\bar{b}+\beta k_1\zeta+\gamma)(\bar{c}+\beta k_2\zeta+\gamma) \cdot \bar{z}_{\omega} )$ $- \alpha \cdot ( (\bar{a}+\beta\bar{s}_{\sigma_1}+\gamma)(\bar{b}+\beta\bar{s}_{\sigma_2}+\gamma)(\bar{c}+\beta S_{\sigma_3}(\zeta)+\gamma) \cdot \bar{z}_{\omega} )$ (This term is used in computing the constant term $r_0$) $+ \alpha^2 \cdot ( (z(\zeta)\text{ term not using }\bar{z}_{\omega}) \cdot L_1(\zeta) )$ (This part is replaced by $r_0$ computation) $- Z_H(\zeta) \cdot (\bar{t}_{lo} + \zeta^n \bar{t}_{mid} + \zeta^{2n} \bar{t}_{hi})$ (Actually processed in commitment form)

• The Verifier separates $r(X)$ into constant term $r_0$ and non-constant term $r'(X)$ for efficiency, computing the constant term $r_0$ separately...

4. Constructing Batched Polynomial Commitments

• The Verifier batches all polynomials opened by the Prover in Round 5 into a single commitment. This process compresses multiple opening verifications into one:

$[D]_1 = \text{Non-constant part of } [r]_1 + u \cdot [z]_1$ $[F]_1 = [D]_1 + v \cdot [a]_1 + v^2 \cdot [b]_1 + v^3 \cdot [c]_1 + v^4 \cdot [s_{\sigma_1}]_1 + v^5 \cdot [s_{\sigma_2}]_1$

• $[D]_1$: Commitment combining the non-constant part of $r(X)$ and $z(X)$ with challenge $u$.
• $[F]_1$: Final combined commitment batching $[D]_1$ together with all polynomial commitments evaluated at $\zeta$ using challenge $v$.

5. Constructing Batched Evaluation Values

• Similarly, all evaluation values are batched into a single field element:

$[E]_1 = (-r_0 + v\bar{a} + v^2\bar{b} + v^3\bar{c} + v^4\bar{s}_{\sigma_1} + v^5\bar{s}_{\sigma_2} + u\bar{z}_{\omega}) \cdot [1]_1$

6. Final Pairing Equation Verification

• Finally, the Verifier combines everything to check a single pairing equation. This equation verifies that the batched KZG opening proof is valid:

$e([W_\zeta]_1 + u[W_{\zeta\omega}]_1, [x]_2) = e(\zeta[W_\zeta]_1 + u\zeta\omega[W_{\zeta\omega}]_1 + [F]_1 - [E]_1, [1]_2)$

Why This Design?

The entire Verifier process is focused on efficiency:

• Succinctness: The Verifier performs no operations proportional to the circuit size n. All computations depend only on the proof size, which is near-constant time.
• Non-interactive: Verification can be completed using only the submitted proof, without needing to interact with the Prover.
• Batching: Multiple KZG opening proofs are compressed and verified with just two pairing operations. This is the key optimization enabling PlonK's fast verification speed.

If this final pairing equation holds, the Verifier can be confident with very high probability that all claims submitted by the Prover (gate constraints, permutation constraints, validity of evaluation values) are correct. If even a single value has been tampered with, the balance of this carefully designed equation will be broken. Thus, the Verifier can trust the validity of the computation without knowing any of the Prover's secret information.

5. References

Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge