ZK Whiteboard Sessions - Module Three: Building a SNARK, pt 2 by Dan Boneh

Transcript

Welcome back everyone. In this segment, we're going to  finish our construction of a SNARK. In particular, I want to show you all the beautiful algebraic ideas that  go into constructing a SNARK. First, let's just quickly review where we were. As usual, we fix our computing  model to be an arithmetic circuit. So all computations will be  expressed as an arithmetic circuit. Remember, an arithmetic circuit involves  additions and multiplication gates, modulo p. This is not the only computing  model that's possible but it's convenient for us today,  so we'll use arithmetic circuits. Again, we're going to be  using an arithmetic circuit that takes this input, a statement x, a witness w, and outputs an element in a finite field Fp.

The first thing that a preprocessing argument  does, is it will preprocess the circuit and output parameters for  the prover and the verifier. Then later on, when the prover  receives a statement and a witness, the verifier receives a statement x. The prover can produce a proof that it knows  a witness w, such that C(x,w) is equal to 0, and the verifier will either  accept or reject that proof. And for this to be a SNARK,  the proof has to be very short, meaning logarithmic in the size of the circuit, and the verifier's work to verify  the proof should be very low, meaning logarithmic in the size of the circuit, although the verifier is allowed to work in  linear time in the size of the statement x, because the verifier at least  has to read the statement x.

Okay. So in the last segment,  we looked at one particular paradigm for building a SNARK,  which combines two components. Now, there are other paradigms  for constructing a SNARK, it's just that this paradigm is the easiest  to explain, so we'll stick with this one. So the paradigm basically builds a SNARK  by combining two different components. The first component is what we call  a functional commitment scheme, and the second component is what we  call an interactive oracle proof. The functional commitment scheme is where  all the difficult cryptography happens, and the interactive oracle proof is more  of an information theoretical component whose security does not depend  on any complexity assumptions.

We combine these two together and we  obtain a SNARK for general circuits. Now, in our presentation today, we're going to  look at a particular instance of this paradigm where the functional commitment scheme is actually what we call a polynomial  commitment scheme or a PCS. And if we're going to be committing  to univariate polynomials, the corresponding interactive oracle proof is what we call a polynomial interactive  oracle proof, or a poly-IOP, which is basically an interactive oracle  proofs that's designed to work with a PCS. We combine these two together  and we end up with a SNARK. Now in the last segment, we saw a  number of polynomial commitment schemes, so let me quickly remind you what  a polynomial commitment scheme is.

Basically, it allows the prover to commit to a polynomial of degree at most  d over this finite field Fp. This is a univariate polynomial. So the prover commits to this  polynomial f, and later on, the prover can open the polynomial at any point u. In other words, the verifier can  send over a u, and the prover can prove that at the point u, the committed  function satisfies f of u is equal to v. Now, recall that this proof  by itself needs to be a SNARK, which means that the proof size  and the time to verify the proof should be most logarithmic in  the degree of the polynomial.

So, again, the polynomial can be of  degree 1 billion, huge degree polynomial, the commitment to the polynomial  is going to be very short. The proof that the polynomial evaluates to  v at the point u is going to be very short and the time to verify this proof  is also going to be very short. Namely, at most logarithmic in  the degree of the polynomial. Now in the last segment, we saw  several polynomial commitment schemes. We mentioned that the KZG one is the  one that's most widely used in practice, but there are other ones that  have different properties. Once we have a PCS, we can combine it with  a polynomial IOP to actually obtain a SNARK. So what is a polynomial IOP?

A polynomial IOP basically is  a way to prove that in fact, the prover knows a witness w  such that C(x,w) is equal to 0, but the polynomial IOP works  in a very particular way. The way it works is basically, again, it preprocesses the circuit C  to generate proof or parameters. At the same time, it also  generates verifier parameters. However, now the verifier parameters are going to  be simply commitments to a number of polynomials. And so, the only thing that Sv contains  are commitments to polynomials. In this case, there are S plus 1  polynomials that are committed to. Remember, this is what I mean by a polynomial in  a box that denotes a commitments to a polynomial, so the verifiers parameters basically contain  S plus 1 committed polynomials, and that's it.

Then when the prover wants to prove that it  knows a witness for a particular statement x, the proof again, proceeds in a very specific way, meaning that the prover sends  a commitment to a polynomial, the verifier in response samples a  random element of the finite field, sends this random element to the to the prover, the prover sends a commitment to another  polynomial, and this continues on and on, until the verifier finally samples its  last random element from the finite field, the prover sends its last  commitment to a polynomial, and then finally the verifier runs  this verify procedure, which is allowed to query the committed functions  at any point of the verifier's choosing.

Okay. So, for any point that the verifier wants, the verifier can say, please open one  of these functions at the given point, and the prover will provide the verifier with  the value of that function at that point. So this is what a polynomial IOP is. In the last lecture we described what the  security properties of a polynomial IOP are, and they mirror the security properties for  a preprocessing argument system in general, namely, it needs to be complete,  it needs to be knowledge sound, and optionally it needs to be zero knowledge. So again, in the last segment, we explain how  you can combine a PCS with a polynomial IOP, and as long as a polynomial IOP only  commits to a small number of polynomials, and the verifier only makes a few  queries to the committed polynomials, the end result actually is a SNARK.

What we didn't do in the last lecture  is construct an actual polynomial IOP, and this is our goal for this lecture. So what I want to do is show  you beautiful algebraic ideas that go into constructing a polynomial IOP. There are many polynomial IOPs out there. We'll do this using one example  of polynomial IOP called Plonk. And again, I want you to remember  that a polynomial IOP like Plonk, plus a polynomial commitment  scheme implies a SNARK. In particular, Plonk can also be  extended to give us a zk-SNARK. Okay. So let's dive right in  and construct our polynomial.

The first thing we're going to  do is develop a few gadgets, that are going to help us to  construct the polynomial IOP. So let's start with a very useful observation. This is almost a trivial observation,  but it turns out that this one simple observation underlies basically  all of the SNARKs out there. So imagine we're looking at a polynomial  f, which has degree at most d, and we are guaranteed that this  polynomial is not the zero polynomial. Now, suppose we sample a random  element from the finite field, and we ask how likely is  that f of r is equal to 0? In other words, how likely is it that  r is a root of this polynomial f?

Maybe I'll pause for a second and let you see if you can come up with a bound  for this probability yourself. Well, let's work it out together. We know that because the polynomial f has degree  at most d, and it's a non-zero polynomial, we know that it has at most d roots. Again, the fundamental fact we're using, is that a non-zero polynomial of  degree d, can have at most d roots. Well, since r is chosen at  random from a set of size p, the probability that r hits one of  these d roots is at most d over p.

The probability that f of r is  equal to 0 is at most d over p. Now, let's suppose that p is actually relatively  large, so something like a 256-bit prime, and let's suppose that the degree  of the polynomial is not too big. Let's say it's at most 2 to the 40,  which is something like a trillion. Let’s say that the degree  d is bounded by a trillion. Then in fact, d over d we can  view it as a negligible number. And what that means is that if in fact  we choose a random r in the field, and it so happens that f of r is equal to 0, well, it's negligible likely to happen  if f is not the zero polynomial.

Therefore, we can deduce that  f is the zero polynomial. So again, what this means is when we  choose a random element in the field, if f of r happens to be 0, we can conclude  from this that with very high probability, f is in fact the zero polynomial. It's identically zero everywhere. This gives us a very simple way to test if  a committed polynomial happens to be zero. Right? If we have a committed polynomial, we  don't know if it's a zero polynomial or not. What we can do is we can choose a  random point in the finite field, ask the prover to open the  polynomial at that one single point.

If we get zero we can conclude that  this is very likely the zero polynomial. If we got non-zero, then of course  this is not the zero polynomial. Yeah. So this gives us a very simple test  to test if a committed polynomial is the zero polynomial by only opening the  polynomial at a single random point. So this is a very important trick. In fact, this trick is literally used in  all the SNARK constructions out there, and this is actually fundamentally the reason  why we're able to build such efficient SNARKs. Now, what's interesting is, in fact, even though  I stated this fact for univariate polynomials, it's really quite fascinating, but this fact  actually also holds for multivariate polynomials.

This is what's called the  Schwartz-Zippel-DeMillo-Lipton lemma, that says that even for a multivariate  polynomial, this condition holds, if you have a polynomial in k variables and  you choose a k tuple from the finite field, the probability that f of r is  equal to zero is at most d over p, where d is the total degree of the polynomial. This, by the way, is a very  interesting exercise to prove, it's not a very difficult proof. I'll tell you that you prove this fact  by induction on the number of variables. Basically, if there's only one variable, then this fact basically reduces to the  condition star that we already know.

And for more variables, we prove that the theorem  holds by induction on the number of variables. This is a good exercise to try and do, so I encourage you to try and  work out the proof of this Schwartz-Zippel-DeMillo-Lipton lemma by yourself. We won't need this lemma  for the rest of the section, but I just wanted to state it  because it's such a beautiful fact, but we will be sticking to univariate  polynomials and this condition star. We have a very simple polynomial way to test,  if a committed polynomial is identically zero. Let's put this fact to use and  derive a related observation. We're going polynomial to stay with the  settings where p is a very large prime, d is is bounded by 2 to the 40, so the d over p is a negligible value.

Now I claim that we get another  interesting test that we can use. Namely, if f and g happened to be  polynomials of degree at most d, again, these are committed  polynomials of degree at most d. Suppose we choose a random element in  the finite field, a random element r, and it so happens that f of r is equal to g of r. So the two polynomials happen  to agree at the random point r, we can conclude from this  that in fact f is equal to g. So if I give you two committed polynomials  and they happen to agree at a random point, that means that with very high  probability the two committed polynomials actually are equal to one another.

Why is that true? Well, let's see. We can derive it from the  fact on the previous slide. If f of r is equal to g(r), that means  that f of r minus g(r) is equal to 0. Which means that the polynomial f minus g  happens to be zero at the random point r. But we said in the previous slide, if f minus  g happens to be zero at the random point r, that means that with very high probability, the polynomial f minus g is the zero  polynomial, is identically zero. But if f minus g is the zero polynomial, that basically means that f is equal  to g with very high probability.

So again, we get a very simple test of  equality for two committed polynomials. Basically, if the prover commits to two  polynomials and the verifier wants to test if those two polynomials are equal to one another, the verifier will ask the prover to open  those polynomials at a random point r, and if their values happen to agree, then the verifier can conclude that in fact,  the two polynomials are equal to one another. All right. So we're going to  put these observations to use again and again and again throughout  this lecture, so let's get started. The first thing we're going to do  is derive a couple of more useful gadgets before I can actually  show you the polynomial IOP.

So to do that, the first thing we have to do  is define a certain subset, which I'll call H. This is a very useful subset  that comes up in almost all of the SNARKs that deal with univariate polynomials. The subset is basically generated by what  we call a primitive k-th root of unity. We'll say that omega is a primitive k-th root  of unity if omega to the k is equal to 1, but no smaller power of omega is equal to 1. Which means that if we look at all the  powers of omega, we obtain a set of size k, which is a subset of the field Fp.

Okay. I'm going to call the  subset, I'm going to call it H. For those of you who remember your group  theory, you'll recognize that H is a subgroup, but that's not so important here. We basically are going to  use H as a subset of size k. Okay. So let's choose some  polynomial f of bound degree d, and let b and c be some  element in our finite field. Now, there are three tasks that the  verifier might ask the prover to do. It turns out that for all three tasks, there  are very efficient poly-IOPs that achieve them. What are these three tasks?

So let's imagine that the prover  committed to the polynomial f, and now the verifier wants the  prover to convince it that the polynomial f satisfies one  of these three conditions. So let's see. So the first condition is  what's called a zero-test, which means that f is  identically zero on the set H. Now, f doesn't have to be the zero polynomial,  it could be non-zero outside of the set H. But what the verifier wants to be convinced is that the committed polynomial f is in  fact identically zero on the set H. We call that a zero-test, and we're going to  use the zero-test again, and again, and again.

This is a very important test to prove that  f is identically zero just on the set H. Another task that the verifier might ask the  prover to do is what's called a sum-check. So sum-check basically means that  the verifier wants to know that the sum of the values f of a, as a  ranges over the set H is equal to b. In this case, the verifier, again has the  committed polynomial f, it has the value b, and it wants the prover to convince it that  the sum of f(a) over H is actually equal to b. Okay. This is called a sum-check.

Similarly, there's a product  check where the verifier has the committed polynomial f and the scalar c, and it wants to be convinced that the product of  f of a over the set H is equal to this scalar c. These are three tasks that the verifier might ask  the approver to do for the committed polynomial f. It turns out that all three tasks  have very efficient polynomial IOPs. So all these three tasks are  quite easy to produce a SNARK for, where the proof is going to be very  short and the verifier can very, very quickly verify that the proof actually holds.

I'm going to show you how the zero-test works  because that's the simplest of the three, and we're going to be using the  zero-test over and over again. If you want to see how the product-check works, for example, the polynomial  IOP for that is in the slides, but I'm not going to go over them in the lecture. You can check out the lecture slides to  see how the product-check actually works. And the sum-check basically works the same way. But for now, let's look at  how the zero-test works. It's actually a very, very cute idea that allows the prover to prove that f is  identically zero on the set H, even though f might not be  identically zero everywhere.

So let's see how this works. So again, the verifier here  has a committed polynomial f. We want to prove that it's zero on  this set H that we wrote up here. The lemma that makes this possible  is the following fact, which is -- Again, this is not a difficult fact to prove. I encourage you to think about why lemma  is true. It uses just basic algebra. And the fact is the following, that  f is in fact zero on the set H, if and only if the following condition holds, namely the polynomial f is divisible  by the polynomial x to the k minus 1. Okay. So if f is divisible by x to the  k minus 1, then f must be zero on H.

And conversely, if f is zero on H, F  must be divisible by x to the k minus 1. So this should give you some ideas for  how the zero-test is going to work. So let's see what the prover will do. So the first thing that the prover does  is it computes the quotient polynomial, which is f divided by x to the k minus 1. Remember that if the committed polynomial f is in fact zero on the set H, then f is  divisible by x to the k minus 1, and therefore indeed q will be a polynomial. The prover will compute this quotient polynomial, and what the prover will do, is it will send a commitment to the  quotient polynomial q to the verifier.

What the verifier will do next is it will  choose a random element in the finite field and ask the prover to open the polynomial  q and the polynomial f at the point r. Remember, the verifier has a commitment  to f and has a commitment to q, it's going to ask the prover to open  both polynomials at the point r. As a result, the verifier  will learn q(r) and f(r). Now what the verifier will do, is it will check if  f of r is equal to q(r) times r to the k minus 1. Now what does this mean? Suppose this equality actually holds, what this means is that the polynomial on the left is equal to the polynomial on the right  at a random point r in the finite field.

But by what we just said, if two polynomials agree  at a random point with very high probability, the polynomials are actually equal to one another. So the verifier can conclude  that with high probability, the committed polynomial f is actually  equal to q times x to the k minus 1. But by our lemma if f is equal to  q times x to the k minus 1, this means that f is in fact zero on the set H. And so the verifier can accept  f as a zero polynomial on H. Otherwise the verifier will reject. Okay, so basically, this is  how the zero-test on H works.

And the theorem, which basically we  talked through its proof, says that, this protocol is complete if in fact, f is zero  on the set H, the verifier will accept the proof and its sound in the sense  that if f is not zero on H, the verifier will reject the  proof with very high probability. And basically, the error probability is d over P,  so we have to assume that d over p is negligible, so that if f is not zero on H, then the  verifier will reject with high probability. Let's look at the size of the  proof and the verifiers time. First of all, the size of the proof is  basically one commitment to the polynomial q and two opening proofs, one for q and one for f.

So the proof itself is very short, containing  one commitment and two opening proofs. One thing to notice is that the only  thing that a verifier does in this proof, is it just sends to the prover a  random element in a finite field. And as a result, we can apply  the Fiat–Shamir heuristic to this interactive proof to make  it into a non-interactive proof. Right? So in fact, the zero-test can easily be made into a non-interactive proof  using the Fiat–Shamir transform. So the size of the proof is actually quite short. What's the running time for the verifier? Well, all the verifier has to do  is verify two PCS openings and then computes the value r to the k minus 1.

Okay? So, computing the value r to the  k minus 1 takes log k field operations. And so the running time for  the verifier is basically log k field operations plus two evaluation verifies. By the way, it turns out that this, using the batching techniques  that we talked about last time, it turns out we can batch these  two openings into a single opening. So really the verifier just has  to verify one evaluation opening, and in fact, there's only one evaluation opening  that the prover has sent to the verifier. So that's the idea behind the zero-test.

It's a very cute idea that lets the  prover convince the verifier that the committed polynomial is zero on the set H. And what's cute about this is that the  only thing the verifier does is just ask the prover to open the polynomial q  and the polynomial f at a random point r. I should actually point out that it's  very important that the verifier sends r to the prover after the prover  committed to the polynomial q. If somehow the prover learned r before  it committed to the polynomial q, the prover will simply generate a bogus q that  happens to satisfy this condition at the point r.

And then the verifier might believe that f is  zero on H, even though that's not really true. Okay. So, it's very important that r is  chosen after the prover is committed to q, so that the prover cannot change its mind about  q after it sees the value of r from the verifier. Okay. So this is how we do a  zero-test on H, and as I mentioned, the sum-check and the product-check  are also described in the slides. If you want to see how they work, just look at the  slides, but I'll leave it at this for the gadgets. Okay. So now let's switch gears and talk about  the actual polynomial IOP that's called Plonk. So our goal is to construct a  polynomial IOP for a circuit C.

So we're going to do this in a number of steps. So first of all, let's look  at a particular circuit, just as an example, that will  serve as our running example. So the circuit actually has two  statement inputs, x1 and x2, and it has one witness input w1, and then it  has three gates, gate 0, gate 1, and gate 2. The first two gates are addition gates.  The last gate is the multiplication gates. So this circuit computes this function  over here, and we'd like to prove that for a public statement x, the prover has a  witness w, such that C of x,w is equal to 0. So let's look at a particular example.

Let's say the input is 5, 6, and 1. We can evaluate gate number 0, we can evaluate  gate number 1, then we can evaluate gate number 2, and the output of the circuit is going  to be 77, given the input 5, 6, and 1. The first thing we want to do is we  want to convert this execution of the circuit into what's called a computation trace. So what is a computation trace? It's basically a table that lists the inputs, so here are the inputs, 5, 6, and 1. And then for every gate, it lists the left input,  the right input, and the output of the gate. For every gate, there are three values  listed in the computation trace.

You can see for gate 0, the inputs  are 5, 6, and the output is 11. For gate 1, the inputs are 6  and 1, and the output is 7. For gate 2, the inputs are 11  and 7, and the output is 77. Okay. So that's called a  computation trace of the circuit, and basically, given the inputs to the circuit, we can write out the computation  trace for the circuit. The output of the circuit, by the way, is basically the output of  the last gate in the circuit. So now that we have a computation trace, it turns out we can forget about the circuit  and only focus on the computation trace. Okay. That's the only thing  that's going to matter for us.

And what we'll want to do is prove that  the computation trace is valid and that the output actually is 0, because we'd  like to prove that C(x,w) is equal to 0. In our example, the output is not zero, so this would not be an accepting  computation in our model. Okay. So let's see. So how do we encode the  computation trace as a polynomial? Well, first I need some notation. Let's say that the size of C is  the total number of gates in C, and let's say that the size of I is the  total number of inputs to the circuit. And I'm going to split I into the  statement inputs and the witness inputs. So the sum of the statement inputs plus the  witness inputs is actually the total inputs I.

So in our example, we had two  statement inputs and one witness input, and there were a total of  three inputs to the circuit. Now, let's define d to be 3(C) plus I. 3(C) plus I is basically the number  of entries in the computation trace. Right? Every gate has three  values associated with it. So that contributes 3(C) elements  to the computation trace, and the inputs is of size I, so the total number of elements in  the computation trace is 3(C) plus I. In our example, you can see that d is equal to 12. There are 12 elements in the computation trace.

And similarly, we're going to define our set H to be the set of powers of omega  up to the power of d minus 1. Okay. So this is just a notation  that we'll use from now on, and what we'd like to do is encode the  entire computation trace as a polynomial. So how do we do that? So what the prover will do is it's  going to interpolate a polynomial P that's going to encode the  entire computation trace. Okay. And let's see how to do that. So how do we interpolate a polynomial  P that encodes the computation trace? Well, okay. So let's see.

What we'll do is interpolate a polynomial  P, the degree is going to be at most d, and this polynomial is going to slowly encode  all the elements in the computation trace. So we're going to start with the inputs,  and what we're going to do is we're going to use then a few negative powers  of omega to encode all the inputs. So P evaluated at three negative powers of  omega will encode the input to the polynomials. So in particular, P at the  point omega to the minus j will encode input number j to the polynomial. In our case, there are three inputs, so we'll use three negative powers  of omega to encode the input.

In addition, P is going to encode all the  internal wires in the computation trace. And the way we're going to do that as follows. We're going to look at gate number l. Yeah. So we're going to label the gates  from 0 to c minus 1 in our case 0, 1, 2. And what we'll do is require the  polynomial P at the point omega to the 3l, to evaluate to the left input of gate number l, at the point 3l plus 1 to evaluate to the  right input and to the point omega to 3l plus 2 to evaluate to the output of the gate. And so, for every value of l that these three constraints in the polynomial encode  one gate in the computation trace.

In particular, I wrote out all these  constraints for our example computation trace, so you can see here is the encoding of the inputs. I had omega minus 1, omega minus 2, omega minus 3. Here is the encoding of the first gate. Here's the encoding of the second gate. You know, the left, the right, and the output. And here's the encoding of the third gate, and the output, of course, is the output  of the last gate, which happens to be 77. So there are 12 constraints on this polynomial. And if you put 12 constraints on a polynomial, that means that there's a polynomial degree at  most 11 that satisfies all these constraints. So the prover is actually going to construct  this polynomial P from the computation trace.

Right? The prover has the computation  trace from the evaluation of the circuit. The prover has the input x and the witness w, it  computes the computation trace for the circuit and is going to interpolate the polynomial P  that encodes the computation trace in this way. So how does it actually  interpolate the polynomial? It turns out there are quite  efficient ways to do this. In particular, we can use  the fast Fourier transform to actually construct the coefficients  of the polynomial P in time d log d. Okay. So almost in linear time, we can actually compute this polynomial P  that encodes the entire computation trace.

Okay. What do we need to do next? The next thing we need to do is to prove that  in fact, P encodes a valid computation trace. So what the prover will do is it will  commit to the polynomial P to the verifier, and now it needs to prove  four things to the verifier. So let's see. So, what are these four things? First of all, it has to prove that  P correctly encodes the inputs. Yeah. So the input x is actually encoded  on a few negative powers of omega. Next, it has to prove to the verifier that every gate in the computation  trace is evaluated correctly. If it's an addition gate, it does an addition.

If it's a multiplication gate,  it does a multiplication. Next, it has to prove that the  wiring is implemented correctly. Now, what do we mean by the wiring? If you look at the computation trace, you  notice that some values appear multiple times. For example, the second input happens to  also be the right input to gate number 0, and it happens to be the  left input to gate number 1. The prover will have to prove that all  these values are actually the same. So this captures the fact that the second input  was shipped to gate number 0 and to gate number 1. Similarly, you can see the output of gate number  0 happens to be the left input of gate number 2.

So we have to prove that these two values,  this 11 here, and this 11 here is the same. So the prover we'll have to prove all these -- that all the wiring in the computation  trace is implemented correctly. And finally, the prover has to prove  that the output of the last gate is 0, so that in fact, C of x,w is equal to 0. This fourth condition is  actually quite easy to prove. What the prover will simply do is just open the polynomial P at the point  omega to the 3(C) minus 1. And as you may remember, this actually  encodes the output of the final gate, and so the prover will open  the polynomial at this point, and the verifier can verify  that it in fact evaluates to 0.

We still have to show how the prover will  prove bullets 1, 2 and 3 to the verifier. So let's do this one at a time. The first thing the prover  has to prove to the verifier, is that the committed polynomial  P encodes the correct inputs. So the way they do this is, remember both the  prover and the verifier have the statement x, so what they will both do is they'll  interpolate a certain polynomial v and this polynomial is going to  encode the x inputs to the circuit. In particular, for every j for 1 to  the number of inputs, we'll make it so that v at the point omega minus j will  evaluate to the j-th input to the circuit.

In our example, I just wrote  down the three constraints. v to the omega minus 1 is the first input, v to  the omega minus 2 is the second input and so on. So in our case, in our example, v  would be a quadratic polynomial. Now what's interesting is that  constructing the polynomial v takes time that's proportional  to the size of the input x. And remember the verifier is allowed  to run in linear time in the size of x. So the verifier actually has enough  time to construct this polynomial v. Next what they'll do, is they'll prove that the polynomial P and the polynomial  v agree on all the input points. Okay? Let's define H inp  to be all the input points.

So you can see omega to the minus 1, omega  to the minus 2 up to omega to the minus x, Right? These are the points that  encode the inputs to the circuit, and the prover will prove that  the computation trace P encodes the correct inputs basically by proving  that P minus v is 0 on the set H inp. Yeah. And this is basically  done using a zero-test. So the prover will use a zero-test to prove to  the verifier that P minus v is 0 on the set H inp, and that will convince the verifier that  indeed P encodes the inputs correctly.

Okay. We're done with proving that  P correctly encodes the inputs. The next thing the prover  has to convince the verifier, is that the computation trace P  correctly encodes all the gates. Okay. So how do we do that? So again, in our example, we have three gates. There are two addition gates  and one multiplication. What the prover will do is it will  compute a certain polynomial S. We call this a selector polynomial,  which is why we denote it by S. Its degree is at most d. And this polynomial has C  constraints applied to it.

Basically, for every l between 0 and  C minus 1, this selector polynomial at the point omega to the 3l will be equal  to 1, if the l-th gate is an addition gate. And it'll be 0, if the l-th  gate is a multiplication gate. In some sense, the selector polynomial  encodes all the gates in the circuit. So again, in our example, we have the  first two gates are addition gates. So at omega to the 0 and omega  cube, the polynomial values to one, and omega to the 6 is a multiplication  gate, so the polynomial will evaluate to 0. Okay? In our case, the selector  polynomial will be a quadratic polynomial.

And by the way, notice that the selector  polynomial depends only on the circuit. It doesn't depend on the input. And in fact, the selector polynomial will  be computed during the preprocessing phase. Because this is a function of  the circuit, not of the inputs. Okay. So now that we have the selector  polynomial, what is the prover going to do? Well, so there's this important  observation that will show us that the selector polynomial can  be used to convince the verifier that all the gates were evaluated correctly. In particular, let's define the set H gates, which contains all the powers of  omega that are divisible by 3.

Okay. So omega cubed, omega  to the 6, omega to the 9. You remember these are the points where  the selector polynomial is defined Now, let's look at the following  complicated looking polynomial. This is actually not that complicated,  but it just looks a little complicated. What this polynomial does is, let's see,  for every y in H gates, it looks at P(y). Remember P at a power that's zero [?] mult  three encodes the left inputs to gate number y. Then P of omega y, this is  increasing the power of omega by 1, this encodes the right inputs  to gate number y in the circuit.

And P of omega squared y encodes the  output of gate number y to the circuit. And what it says here is basically that if gate number y happens to be an addition  gate, then S of y is equal to 1, And so -- let's see. We're multiplying the sum by 1 and  we're multiplying the product by 0. So what this says is that P of y plus P of  omega y is equal to P of omega squared y, which means left input plus  right input is equal to output. Similarly, when S of y is equal to 0,  which means it's a multiplication gate, then the left term goes away  because S of y is equal to 0, the right term will be multiplied by 1.

So we have the P of y times P of omega  y is equal to P of omega squared y. So again, left input times  right input is equal to output. So you notice that the selector  polynomial basically enforces that at gates that represent addition gates, the left input plus right  input is equal to the output. And then gates that correspond  to multiplication gates, the left input times the right  input is equal to the output. So the selector polynomial  ensures that every gate, be it an addition gate or multiplication gate, is correctly encoded in the computation  trace that's committed to by P.

Okay? So that's the idea. So we built this polynomial that's going  to be satisfied at this entire set, which we're going to call H sub gates. So now what the system will do is actually we'll place a commitment to the selector  polynomial in verifiers parameters. And what the prover and verifier will do,  is they will go through a zero-test to prove that this complicated looking polynomial is  in fact equal to zero on the set H gates. So you notice that proving that all  the gates were evaluated correctly is another zero-test on a somewhat  complicated looking polynomial, but it is just a zero-test on the set H gates.

Okay? So that's how the prover will convince the verifier that all the gates  were evaluated correctly. The last thing the prover needs to do is convince  the verifier that the wiring was done correctly. And this is actually the hardest thing to do. Okay? What does it mean that  the wiring was done correctly? We already said, for example, that  the second input is given as the correct input to gate number 0, and gate number 1. For example, you can see that the output of gate number 0 is the input of gate  number 2, and so on and so forth. So here I wrote all the wiring  constraints that the circuit has. Yeah. So this corresponds to the fact that  the 6 is provided as inputs to both gates.

This corresponds to the fact that the first input is given as the left inputs to the  first gate and so on and so forth. Right? So we can kind of write all these  equalities as the wiring constraints, and now somehow the prover has  to convince the verifier there, all these wiring constraints are actually  satisfied by the committed polynomial P. So the way the prover is going to do that  is by constructing a certain polynomial, which we call the wiring polynomial. What does this wiring polynomial do? It's actually a function  from the set H onto itself. And what this wiring polynomial does is sort of it implements a rotation of  each one of these equalities.

So what it will do is it will map  omega to the minus 2 to omega to the 1. It'll map omega to the 1 to omega cubed. It'll map omega cubed to omega to the minus 2. So you notice what this does  is it implements a rotation of the tuple omega minus 2, omega 1, omega cubed. Yeah. So that's what this polynomial will do. And will do this for every  one of the wiring constraints, it basically will implement a  rotation of this wiring constraints. Now, I have to admit, this probably takes  a little bit of time to let it sink in, but the lemma that makes this relevant is  the fact that if for every y in the set H, it so happens the P of y is  equal to P of the rotation of y, then in fact this implies that all  the wiring constraints are satisfied.

So actually, I'm the first to admit that you  probably need to stare at this for a little bit of time to kind of understand  how these wiring constraints work and why this rotation actually ensures  that the wiring constraints are satisfied. But I'm going to let you stare  at this at your own time. For now, we'll take this lemma as a given  that to verify the wiring constraints, there's a certain wiring  polynomial that's computed. And what the prover has to prove is that P of y is equal to P of W of y at all  the points y in the set H. One thing that I want to point out is that  this wiring polynomial, again, is a polynomial that only depends on the circuit.

It does not depend on the  statement x, and as a result, this polynomial W can actually be  computed during the setup time. Okay? So in fact, the setup  algorithm is going to give the verifier a commitment to this polynomial W, and then the prover will have  to prove that P satisfies this equality with respect to  the committed polynomial W. Well, unfortunately there's a problem. The degree of the polynomial W is d, and  similarly the degree of the polynomial P is d. If we compose a polynomial degree d  with another polynomial of degree d, we end up with a polynomial of degree d squared.

Okay. And so, if we did this test as stated here, this would actually force the prover to  deal with polynomials of degree d squared, which would mean that the prover would run in  quadratic time in the degree of the polynomial, which remember is quadratic time  in the size of the circuits. We don't want that. We want the prover to run in linear time or at  most n log n time in the size of the circuit. Yeah. If we did the test naively, it would  require the prover to run in quadratic time. So actually, the way around this is one  of the most clever tricks inside of Plonk. And so, what Plonk does is it has a very  cute trick to use a product-check over the set H to verify this equality  using only polynomials of degree d.

This trick is called a Plonk permutation trick. I actually wrote down how  it works on this slide here, but I don't think I have time to go  through the details of how it works. If you want to see for yourself how it works, you can just walk through the steps and  convince yourself that this will actually verify that P of y is equal to P of W(Y)  using only polynomials of linear degree. So basically, this is how the  prover will convince the verifier that the wiring constraints are satisfied as well. So now basically we're done. So let's kind of summarize how  the Plonk polynomial IOP works.

First of all, the setup procedure, what it  will do is it will preprocess the circuit and commits to the selector polynomial that  selects which gates are addition gates, and which gates are multiplication gates, as well as the wiring polynomial that's  used to verify the wiring constraints. So this is all done in a preprocessing step, and the verifier has commitments  to both of these polynomials. Now when the prover has a statement x  and witness w that it wants to prove, what it will do is it will  build the polynomial P that encodes the computation trace of the circuit C. It will send the commitment to  this polynomial, to the verifier, and then it will convince the verifier  of the four facts that we just saw.

Right? So all of these are  basically proved using zero-tests. It will prove that this polynomial is  identically zero on the set H gates, it'll prove that this polynomial is  identically zero on the input set. It will prove that this complicated polynomial  here is identically zero and the entire set H, this prove the gate constraints, the  input constraints, the wiring constraints, and finally it will prove that the output  of the circuit is in fact equal to 0. Okay. So there are three zero-tests and one  evaluation test in this entire procedure, and that convinces the verifier that P is in  fact a commitment to a valued computation trace, and consequently, this convinces  the verifier that the prover has

a valid witness, such that C of x,w is equal to 0. And that's basically it. That's how Plonk polynomial IOP works. So, finally, there's a theorem  that says that the Plonk polynomial IOP is complete and knowledge sound. This theorem is not very difficult to prove. Basically, all it says is if  you give me the polynomial P, because we prove that the polynomial P  represents a valid computation trace, by looking at the polynomial P, you  can extract the prover's witness. This is where the knowledge soundness comes from. Okay. So we have our polynomial  IOP, and one thing that I -- again, I want to stress is that you notice the verifier's parameters are just  two polynomial commitments.

And what's interesting is these two  commitments can be computed with no secrets. They're just a simple preprocessing of the circuit C, anyone can verify that  they were computed correctly. Now what's important to remember is we  can match up this polynomial IOP with any polynomial commitment scheme of our choice. In particular, if we match up Plonk with a  PCS that does not require a trusted setup, we'll end up with a SNARK that does not require a  trusted setup, because the PCS setup is untrusted, and you see very clearly here that  the setup for Plonk is also untrusted. Anyone can compute the selector polynomial  and the wiring polynomial commit to them, and there are no secrets at all  involved in these commitments.

And the verifier will use these commitments when it verifies that the polynomial P is a  commitment to a valid computation trace. Okay. So this completes our discussion of Plonk. Now it turns out this polynomial  IOP in fact is quite powerful. It has many extensions. And so first of all, we'll say  that because it only requires three zero-tests, plus one evaluation proof, that the resulting SNARK is actually  quite short, it's around 400 bytes. And verifying this SNARK  proof also is really fast.

It just takes a constant number of operations. And so verifying this proof  takes around six milliseconds. So it's a very short proof,  relatively fast to verify. The only downside of Plonk is that  the Plonk prover has to compute the polynomial P that encodes the  computation trace explicitly. As we said, that could be  done in almost linear time. However, it also requires about linear memory. And as a result, when the circuit is huge, computing this polynomial IOP can  require quite a lot of memory, and that actually makes it somewhat difficult to  use Plonk as we described for very large circuits.

And, in fact, there are many  variations and optimizations of Plonk to actually make it  work better for large circuits. Now another interesting extension of Plonk is when you think about how we  proved the gate constraints, we encoded the addition and  multiplication gates into the complicated polynomial that was  used to verify the gate constraints. Well, it turns out that we can encode other gates beyond additional multiplication  into that complicated polynomial, and that would allow us to do proofs for circuits that have more exotic gates than  just additions and multiplications.

So sometimes these are called  circuits with custom gates, and in fact, Plonk handles very easily circuits with custom gates that do more than  just addition and multiplication. And that's quite an important  optimization for Plonk. In particular, there's a very  cute trick called PLOOKUP. I encourage you to look it up. It's a very, very, very elegant polynomial IOP that allows you to introduce gates  that do what are called lookup tables. What this allows you to do is actually prove  that many intermediate steps encountered during the circuit evaluation actually are  members of certain predefined lookup tables. And this PLOOKUP is quite an important  thing in various applications of SNARKs, including various rollups, as well as key EVMs,  which we'll talk about later on in this course.

Finally, I'll mention that even  though we described Plonk as a SNARK, there's an extension to Plonk  that makes it into a zk-SNARK. Again, I would point you to the  paper for seeing how to do that. So as we said, Plonk has wonderful proof size,  it's very short, the verifier is quite fast. The only downside is that the  prover time and more importantly, the prover memory requirements  are actually quite large. And there's quite a lot of research  into building better SNARKs that have faster provers with smaller memory requirements. And again, in the readings, we'll  point to some more recent work that gives SNARKs that are more friendly to the prover.

Okay. So this brings us to  the end of this lecture. I hope you enjoyed these three lectures, and you  now get a sense of how these SNARKs actually work. And so, I will stop here and I hope  you enjoy the rest of this course. Amd thank you very much.