how-plonk-works-part-2-min

How PLONK works: Part 2

This post was first published on Medium.

Copy Constraints

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

How PLONK works Part 2 figure 1 illustration
Figure 1

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.

How PLONK works Part 2 figure 2 illustration
Figure 2

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:

How PLONK works Part 2 figure 3 illustration
Figure 3

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

How PLONK works Part 2 figure 4 illustration
Figure 4

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.

How PLONK works Part 2 figure 5 illustration
Figure 5

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.

How PLONK works Part 2 figure 6 illustration

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.

How PLONK works Part 2 figure 7 illustration

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

How PLONK works Part 2 figure 8 illustration

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

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 = 1n 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:

How PLONK works Part 2 figure 9 illustration
Figure 6

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

How PLONK works Part 2 figure 10 illustration
Figure 7

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

How PLONK works Part 2 figure 11 illustration
Figure 8

Fig. 7 is equivalent to:

How PLONK works Part 2 figure 12 illustration
Figure 9

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

How PLONK works Part 2 figure 13 illustration

in which

How PLONK works Part 2 figure 14 illustration

It is again equivalent to prove the following polynomial equation

How PLONK works Part 2 figure 15 illustration

in which

How PLONK works Part 2 figure 16 illustration

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:

permutation function table

Fig. 3 becomes:

How PLONK works Part 2 figure 18 illustration

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

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

Watch: The BSV Global Blockchain Convention presentation, Smart Contracts and Computation on BSV

New to Bitcoin? Check out CoinGeek’s Bitcoin for Beginners section, the ultimate resource guide to learn more about Bitcoin—as originally envisioned by Satoshi Nakamoto—and blockchain.

[id^="_form"]
[id^="_form"]
[id$="_submit"]
[id$="_submit"]
[^;]
[^;]
[?&]
[?&]
[^&#]
[^&#]
[(d+)]
[(d+)]
[elem.name]
[elem.name]
[+_a-z0-9-'&=]
[+_a-z0-9-'&=]
[+_a-z0-9-']
[+_a-z0-9-']
[a-z0-9-]
[a-z0-9-]
[a-z]
[a-z]
[el.name]
[el.name]
[id^="_form"]
[id^="_form"]
[id$="_submit"]
[id$="_submit"]
[^;]
[^;]
[?&]
[?&]
[^&#]
[^&#]
[(d+)]
[(d+)]
[elem.name]
[elem.name]
[+_a-z0-9-'&=]
[+_a-z0-9-'&=]
[+_a-z0-9-']
[+_a-z0-9-']
[a-z0-9-]
[a-z0-9-]
[a-z]
[a-z]
[el.name]
[el.name]