# EXPLORING PLONK
*Review PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge*
The author aims to explain 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.
By understanding this process, we can grasp the fundamental reasons why each component of PlonK is necessary and how they combine to ensure the protocol's completeness and soundness.
Before diving into the detailed analysis, I will first 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.
Let me now explain the most fundamental concept in the PlonK protocol—the 'arithmetic circuit'. The diagram on screen shows a simple example of the calculation `(x * y) + x = z` expressed as a circuit.
```mermaid
graph TD
subgraph "Arithmetic Circuit"
direction LR
G1[Gate 1: Multiplication]
G2[Gate 2: Addition]
subgraph "Wires & Values"
w1["w1 (x)"]
w2["w2 (y)"]
w3["w3 (x*y)"]
w4["w4 (x)"]
w5["w5 ((x*y)+x)"]
end
w1 -- "a1 = x" --> G1
w2 -- "b1 = y" --> G1
G1 -- "c1 = x*y" --> w3
w3 -- "a2 = x*y" --> G2
w4 -- "b2 = x" --> G2
G2 -- "c2 = z" --> w5
end
classDef Gate_Constraints fill:#e6ffed,stroke:#333,stroke-width:2px;
classDef Wiring_Constraints fill:#ffefd5,stroke:#333,stroke-width:2px;
class G1,G2,w1,w2,w3,w4,w5 Gate;
class C1,C2 Gate_Constraints;
class W1,W2 Wiring_Constraints;
```
Through this illustration, we'll explore the two core missions that the PlonK Prover must accomplish.
First, let's look at the overall structure of the circuit. This circuit consists of **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`.
This is the computational flow.
### 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.
In conclusion, for each gate in the circuit, 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
You might have realized that handling gate constraints and connection constraints individually would be highly inefficient. 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.
```mermaid
graph LR
subgraph "Before Permutation"
A["w1: (value: 10)"]
B["w2: (value: 12)"]
C["w3: (value: 120)"]
D["w4: (value: 10)"]
end
subgraph "After Permutation (σ)"
A_p["w4: (value: 10)"]
B_p["w3: (value: 120)"]
C_p["w2: (value: 12)"]
D_p["w1: (value: 10)"]
end
A -- "σ(1) = 4" --> A_p
B -- "σ(2) = 3" --> B_p
C -- "σ(3) = 2" --> C_p
D -- "σ(4) = 1" --> D_p
linkStyle 0 stroke:#ff6347,stroke-width:2px,stroke-dasharray: 5 5;
linkStyle 1 stroke:#3cb371,stroke-width:2px,stroke-dasharray: 5 5;
linkStyle 2 stroke:#4682b4,stroke-width:2px,stroke-dasharray: 5 5;
linkStyle 3 stroke:#9370db,stroke-width:2px,stroke-dasharray: 5 5;
```
> "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)$.
---
Through the strategies outlined above, it has become clear that the Prover must now do more than simply compute discrete values—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**
We will now explain the five concrete rounds that the Prover performs to generate the final proof $\pi_{SNARK}$. 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**
```mermaid
sequenceDiagram
participant P as Prover
participant V as Verifier
rect rgb(255, 228, 225)
note over P: Prover's Secret Work<br/>1. Construct polynomials a(X), b(X), c(X) using witness (w_i) and random values (b_i).
P->>P: Calculate a(X), b(X), c(X)
note over P: 2. Commit the KZG.
P->>P: Calculate [a]₁, [b]₁, [c]₁
end
P-->>V: Proof #1: [a]₁, [b]₁, [c]₁
rect rgb(224, 255, 255)
note over V: Verifier's Work<br/>1. Receive and save commitments.
V->>V: Receive [a]₁, [b]₁, [c]₁
note over V: 2. Prepare for the next challenge with the data received.
V->>V: Generate random challenges β, γ
end
V-->>P: challenges: β, γ
note over P,V: Round 1 ends, ready for Round 2
```
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.
```mermaid
sequenceDiagram
participant P as Prover
participant V as Verifier
note over P,V: (After receiving β and γ sent by Verifier in Round 1)
rect rgb(255, 228, 225)
note over P: Prover's Secret Work<br/>1. Challenge Using β, γ and polynomials a, b, c,<br/> construct a cumulative product polynomial z(X).
P->>P: z(X) Calculate (Grand Product Argument)
note over P: 2. Commit the z(X) polynomial to KZG.
P->>P: Calculate [z]₁
end
P-->>V: Proof #2: [z]₁
rect rgb(224, 255, 255)
note over V: Verifier's Work<br/>1. Receive and store permutation commitments.
V->>V: Receive [z]₁
note over V: 2. Prepare for the next challenge with all commitments ([a],[b],[c],[z]).
V->>V: Random Challenge α Generation
end
V-->>P: Challenge: α
note over P,V: Round 2 ends, ready for Round 3
```
**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**.
```mermaid
sequenceDiagram
participant P as Prover
participant V as Verifier
note over P,V: (After receiving α sent by Verifier in Round 2)
rect rgb(255, 228, 225)
note over P: Prover's Secret Work<br/>1. Combine challenge α and all polynomials (a,b,c,z,q,...) to create a constraint polynomial.
P->>P: Calculate Constraint Polynomial
note over P: 2. Divide the constraint polynomial by Z_H(X) to calculate the quotient polynomial t(X).
P->>P: t(X) = (Constraints) / Z_H(X)
note over P: 3. Divide t(X) into three pieces and commit them.
P->>P: Calculate [t_{low}]₁, [t_{mid}]₁, [t_{high}]₁
end
P-->>V: Proof #3: [t_{low}]₁, [t_{mid}]₁, [t_{high}]₁
rect rgb(224, 255, 255)
note over V: Verifier's Work<br/>1. Receive and store the share commitment.
V->>V: Receive [t_{low}]₁, [t_{mid}]₁, [t_{high}]₁
note over V: 2. Prepare a challenge to verify all claims (commitments) at one point.
V->>V: Generate random evaluation point challenge ζ
end
V-->>P: challenge: ζ
note over P,V: Round 3 ends, ready for Round 4
```
**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.
```mermaid
sequenceDiagram
participant P as Prover
participant V as Verifier
note over P,V: (Received ζ sent by Verifier in Round 3)
rect rgb(255, 228, 225)
note over P: Prover's Secret Work<br/>1. Evaluate all necessary polynomials at challenge ζ and its neighbors ζω.
P->>P: Calculate ā = a(ζ), b̄ = b(ζ), ..., z̄_ω = z(ζω)
end
P-->>V: Proof #4: ā, b̄, c̄, S̄_σ1, S̄_σ2, z̄_ω
rect rgb(224, 255, 255)
note over V: Verifier's Work<br/>1. Receive all evaluation values.
V->>V: Receive ā, b̄, c̄, ...
note over V: 2. Prepare a challenge for 'Batch Opening' to check if these evaluation values are real.
V->>V: Random challenge v, u generation
end
V-->>P: Challenge: v, u
note over P,V: Round 4 ends, ready for Round 5
```
**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.
```mermaid
sequenceDiagram
participant P as Prover
participant V as Verifier
note over P,V: (Received v, u sent by Verifier in Round 4)
rect rgb(255, 228, 225)
note over P: Prover's Secret Work<br/>1. Prepare batch opening using challenge v, u and all polynomials and evaluation values.
P->>P: Constructing a linear polynomial r(X) etc.
note over P: 2. We group all the evaluation claims together and perform division, and compute the unpacked proof polynomials W_ζ and W_ζω.
P->>P: Calculate W_ζ(X), W_ζω(X)
note over P: 3. Commit the open proof polynomials to KZG.
P->>P: Calculate [W_ζ]₁, [W_ζω]₁
end
P-->>V: Proof #5: [W_ζ]₁, [W_ζω]₁
rect rgb(224, 255, 255)
note over V: Verifier's Work<br/>1. Receive final proof of opening.
V->>V: Receive [W_ζ]₁, [W_ζω]₁
note over V: 2. Using all the info received so far (Proofs #1-5), compute a single final verification formula.
V->>V: Final pairing equation verification.
end
V-->>V: Accept or Reject
note over P,V: Terminate all protocols.
```
**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](https://eprint.iacr.org/2019/953.pdf)
Sign in with Wallet
Connect another wallet