# How PLONK Works: Part 2

In Part 1, we have explained how to transform a computation one wants to prove using PLONK into an intermediate constraint system, which is eventually proved using a Polynomial Commitment Scheme (PCS). We have only covered one type of constraints: *gate constraints*. In this article, we cover the other type: *copy constraints*.

# Copy constraints

In Part 1, we have enforced constraints within each gate, e.g., a0 * b0 = c0. However, there are also constraints across different gates, e.g., the output of gate 0 is the left input of gate 1, thus c0 = a1. In addition, a wire can be split, e.g., a0 = b0 = b1 = a2. These constraints are called *copy constraints* to ensure wires contain same value.

# Permutation check

Let us first consider copy constraints within a single vector (i.e., a single polynomial), say, a0 = a2.

We define a permutation function ** σ**.

**(i) is the new index of the i-th element in the permuted vector. In our case, σ = (2, 1, 0, 3) as Fig. 2 shows, meaning a0 and a2 switch place.**

*σ*Color represents wire value in the figure. If permuted blocks have same color as the original blocks at the top, copy constraints are met.

# Grand product

Let us choose two random numbers *β* and *γ*. Define *f* and *g* as:

Permutation check passes if and only if the following equation holds:

The left hand side is called a *grand product*. In our concrete example, it is trivial to see the equation holds when a0 = a2, since all the terms in the numerator and denominator of the grand product cancel out.

Because *β* and *γ* are random, it is practically impossible that the grand product is 1, while the permutation check fails. That is, if a0 != a2, the equation in Fig. 4 will not hold.

## Proof

We provide an informal proof that if grand product is 1, σ(i) = j implies ai = aj. Essentially, the permutation check passes if and only if the grand product is 1.

Recall that Schwartz-Zippel lemma says if two polynomials are equal at a random evaluation point, these two polynomials are identical everywhere with overwhelming probability. Let us consider two polynomials.

Since they are equal at random *γ*, we can regard them as the same, meaning they have the same roots.

Consider two matching roots: *j*-th from P1 and *i*-th from P2.

We can apply the trick above again by defining two polynomials:

Since they are equal at random β, we can regard them as equal. That is, ai=aj when σ(i) = j. QED¹.

# Polynomial

## Roots of unity

We used vector index {0, 1, 2, …, n-1} as the domain of evaluation H when converting a vector to a target polynomial, but any domain can be used. In PLONK, the domain that is used for polynomial interpolation consists of roots of unity, due to its performance gains. The *n*-th roots of unity of a field are the field elements ω that satisfy ω*^n = 1*. *n* is the size of the vector, which is 4 in this case. H is {ω⁰, ω¹, ω², ω³ }.

## Accumulator

Let us define a vector P evaluated as the following:

It *accumulates* the grand product, since P can be rewritten recursively:

If there exists such as P(x), we know the grand product equation in Fig. 4 holds, since

Fig. 7 is equivalent to:

P(x), f(x), and g(x) can be found using interpolation on domain H {ω⁰, ω¹, ω², ω³ } as before. The following polynomial equation holds on the domain H

in which

It is again equivalent to prove the following polynomial equation

in which

We can prove it using a polynomial commitment scheme as in Part 1.

# Copy constraints across vectors

There are also copy constraints across different vectors/polynomials, e.g., a2 = b0 and a1 = c0. We can extend the previous method by merging vectors a, b, and c into a single large vector, whose size n is 12. For example, b0 has index 4 and c0 8. The permutation function σ(i) of our toy example becomes:

Fig. 3 becomes:

The remaining steps are similar to the those of enforcing copy constraints within a single vector.

# PLONK

To recap, given a program P to prove, we first convert it to an arithmetic circuit, then to a series of constraints including gates and copy constraints, which are transformed into polynomials. Finally, we use a PCS to verify polynomial identities succinctly.

These are all the high-level ideas of using PLONK to prove a computation. We omit a myriad of important optimizations which make PLONK efficient in practice, for ease of exposition. For example, the PCS can be made non-interactive using the standard Fiat-Shamir heuristic. Also testing for multiple polynomial identities can be merged into one. For more details, you can read the original paper or the references below.

# References

https://github.com/sCrypt-Inc/awesome-zero-knowledge-proofs#plonk

[1] The proof’s idea comes from here.