ZK Whiteboard Sessions - Module Two: Building a SNARK, pt 1 by Dan Boneh

Transcript

Okay. Welcome back everyone. In this segment and the next, we're going  to see how to actually build a SNARK. By the end of these two segments, you will see all  the components that are needed to build a SNARK. So first, let's quickly review what  we discussed in the last lecture. And you remember that the first thing we  had to do was define a computing model. And the computing model that we use here  is going to be an arithmetic circuit. Yeah. Just remember that an arithmetic circuit is a circuit that's made up of addition  and multiplication gates modulo P. And the arithmetic circuit outputs  an element in a finite field FP, which is a set of numbers 0 to P minus 1  with addition and multiplication modulo P.

Now the arithmetic circuit takes an  input, a statement x and a witness w, and as we said, outputs an element  in the finite field F sub P. Now, in a preprocessing argument system, the first  thing that happens is we preprocess the circuit C. So we have this setup algorithm that  takes a description of the circuit C as inputs and outputs these public parameters, they are parameters for the prover and  they are parameters for the verifier, then the prover and the  verifier both takes some inputs, and what the prover will do is it will  produce some sort of a proof Pi that says, I know some witness w that  makes C of x,w equal to 0.

Yeah. And the verifier then decides either to accept or reject this proof  just using the statement x. Again, recall the verifier has the  statement x but not the witness, whereas the prover has both x and the witness. Now in the last segment we saw a number of  examples of what the circuit C could do. Just as an example of a circuit C, you can think of a circuit that proves knowledge of  a hash preimage of the statement x. That is, the circuit C proves  that the hash of w is equal to x, and the verifier of course  knows x, but doesn't know w, and yet the proof will convince the  verifier that the prover knows w such that the hash of w is equal to x.

Yeah. That's just one example of a circuit C. If the hash of w is equal to x, the circuit will  output 0, otherwise it will output non-zero. And again, the proof will convince the verifier that the prover knows a w such  that hash of w is equal to x. There are many other circuits one can consider, for example, circuits that  might verify signatures, and many other things that the prover  might want to prove to the verifier. So again, just reviewing the syntax  for a preprocessing argument system, remember that a preprocessing argument  system is made up of three algorithms, the setup algorithm, the prover  algorithm, and the verification algorithm.

The setup algorithm, as we  said, outputs Sp and Sv. The prover will take x and the  witness and produce a proof Pi and the verifier will take x and the  proof and either accept or reject. We outlined a number of  requirements for an argument system. The first requirement is that  the proof system be complete, meaning that the honest prover will always  produce a proof that the verifier will accept. The second property is what  we call knowledge soundness, which means that if the prover is able to  produce a proof that the verifier accepts, that means that the prover must know some  witness w such that C of x,w is equal to 0.

We saw last time how to  define this more precisely, using an extractor that's able to extract the witness w from a prover that's  able to convince the verifier. And just as an example, again, if we look at  the circuit that says I know a preimage of x, I know a value w such that H of w is equal  to x, and maybe w is in a certain interval, that would be an example circuit C, and if the prover is able to convince  the verifier that it knows such a w, there must exist an extractor that  can extract this w from the prover. And optionally, we might want the  proof system to also be zero knowledge, which means that the proof, along with x and  Sv should reveal nothing about the witness w.

So these are the three high level requirements  we wanted for a preprocessing argument system. And then to make a SNARK, we we have  two more succinctness requirements. The first requirement is that the proof be short, meaning that the length of the proof Pi should be  at most logarithmic in the size of the circuit C, and the proof should also be fast to verify, meaning that the time to verify the proof should be at most again logarithmic  in the size of the circuit C. Of course we allow -- We need to allow the verifier  to read the statement x. So we allow the verifier to run in linear  time in the size of the statement x. Now you notice this, I use this  notation O sub lambda here.

Lambda is always going to be  used as a security parameter. You can think of lambda as  typically set to be 128. But asymptotically, we allow  lambda to be another parameter, and really, the size of the proof and  the time for the verifier also needs to be polynomial in the security parameter lambda. But we are mostly going to  ignore the dependence on lambda, which is why we put it as a  subscript and primarily focus on the dependence on the size of the circuit C and the length of the statement x. Now you notice, because the verifier runs  in time logarithmic in the size of C, the verifier can run -- cannot read the circuit C, but it has to be able to verify  that C of x,w is equal to 0.

So someone must have had to read the circuit C. And this is why we do the preprocessing step. The preprocessing step basically  reads the entire circuit C and produces a short summary of  the circuit for the verifier. Yeah. So Sv typically will be very, very short. And as we said, kind of summarizes  the circuit C for the verifier. Okay. So now let's switch gears and dive  right in into how to build an efficient SNARK. So what's interesting is that there is a very  general paradigm for building efficient SNARKs. This is not the only paradigm. There are other paradigms for building SNARKs, but here I want to specifically focus on  one very general paradigm for doing that.

And so, the way we build the SNARK is by  actually combining two very general concepts. The first concept is what's called  a functional commitment scheme, which we'll define in just a minute. And the second concept is what's  called an interactive oracle proof. Yeah. So the interactive oracle proof, an IOP, is going to be compatible with  the functional commitment scheme. Again, we are going to define these  two concepts in just a minute. We are going to put these two things together  and out will come a SNARK for general circuits. So let’s see exactly what  each of these concepts mean.

We’ll start with functional commitments, and then  we’ll describe what are interactive oracle proofs. But I do want you to remember that the SNARKs  that we will be constructing in these two segments follow this general paradigm of putting together a commitment scheme along with  an interactive oracle proof and those together give us the SNARK. What’s interesting is that most of the  cryptography happens in the commitment scheme but this is where all the  cryptographic assumptions come up. Whereas the interactive oracle proof is  more of an information theoretic object and we can prove its security without making  any complexity assumptions whatsoever. So in some sense, we are combining a cryptographic  object with an information theoretic object and that’s what gives us a SNARK.

Okay. So let’s dive right in and  explain each concept in turn. We’ll start with functional commitment scheme. So first, let's review what  is a cryptographic commitment. So a cryptographic commitment basically  emulates a physical world envelope. So imagine Bob wants to  commit to some data to Alice. What Bob will do is he will put his data in an  envelope and send the envelope over to Alice. Alice doesn't see what the data is, but she knows  that at this point, Bob is committed to the data because it's in the envelope and  Alice is the one holding the envelope. Later, Bob can open the envelope  and reveal the data to Alice, and Alice is assured that the  data that was revealed is in fact the data that Bob committed to ahead of time.

This concept is implemented by two algorithms,  which we call the commit and verify algorithms. The commit algorithm is run by the committer Bob, and the verify algorithm is  run by the receiver Alice. So the commit algorithm will commit to  some message m using some random value r. So Bob will choose a random value r and commit  to the message m using this randomness r and this commit algorithm will  output a short commitment string. It's actually quite important to remember  that the commitment string is short, no matter how large the message is. So the message itself could be  gigabytes and gigabytes of data.

The commitment string is going to be very  short, typically something like 32 bytes. Later on, Bob can open the commitments  to Alice by revealing m and r. Alice would then run the verify algorithm, giving it m the commitment, and r and the  verify algorithm will say accept or reject. A commitment scheme has to  satisfy two basic properties. The first one is called the binding property, which means that after Bob commits to some data,  he can only open the commitment in one way. And the way we capture that is by saying  that Bob cannot produce a commitment, along with two different valid  openings of that commitment.

So that's the binding property of the commitment. And the hiding property of the commitment says that the commitment itself reveals  nothing about the committed data to Alice. Yeah. So even though Alice  received the commitment, she learns absolutely nothing  about the committed data. And many of you might know that  there is a standard construction for commitment schemes using hash functions. In particular, we're going to use a hash function  that takes a message and some random string and maps it to the commitment space. And basically the commitment function  is defined as a hash of m, r. Remember that m is the data  and r is the randomness, and that's how we produce  the short commitment string.

And the way we verify the  opening of the commitment, is basically, Alice will just rehash m and r and verify that she got  the commitment string back. And one can show that for  a suitable hash function H, this is in fact a hiding and  binding commitment scheme. So that's how we commit to data. But in our case we actually  want to commit to a function. So what does it mean to commit to a function. So first we're going to fix some  function family from a set X to a set Y. And the committer will be committing to  some function in this function family. Now I'm going to change the name  of the committer to the prover, because typically the prover  will be committing to a function.

And I'm going to change the name  of the receiver to the verifier, because the verifier is the one who's going  to be verifying openings of these commitments. So let's see what does it  mean to commit to a function. So here the prover has some  function in the function family. And he wants to commit to this function, and so he'll commit to the function using a short  commitment string which will denote by com sub f, and the verifier will store this commitment. Later on, the verifier is going to say, hey prover, can you please open the function  you just committed to at the point x. What the prover will do is of course, it  will compute f of x, which will denote by y, and it will produce a short proof  that proves that f of x is equal to y, and that the committed function  is in fact in the function family.

And the verifier will verify this  proof and either accept or reject. So you notice that what's happening here is that  the prover committed to a certain function f, and later on, the verifier can ask the prover to open the function at one particular  point x in the domain of the function. The prover can then convince the verifier  that, in fact, the committed function f satisfies f of x is equal to y where the verifier knows both x and y. So this is what it means to commit to a function. The prover commits to a function and then later  opens the function at one particular point. So let's see the syntax for  this in a bit more detail.

So first of all, for a functional  commitment scheme for a function family F, first of all we run a setup algorithm  that generates some public parameters. This is a one-time operation that we  just run at the beginning of time, and never again. Then the prover can commit to the  function f by running a commit algorithm. This produces a short commitment string com sub f, and that's a commitment to the  function f in the function family. And this commitment should be a  binding commitment to the function f. So once the prover commits to the function, the prover can no longer change its  mind about what the function is. And the commitment scheme should  optionally also be hiding, which means that the commitment should  reveal nothing about the committed function.

As we will see, if we're building a SNARK,  we typically just need a binding commitment. It does not need to be hiding, but if we're building a zero-knowledge SNARK, often we might need a commitment  that's both binding and hiding. But for a SNARK, a binding  commitment is sufficient. Now, the important component of a functional  commitment is the evaluation protocol. So the evaluation protocol is between,  again, the prover and the verifier, where here the verifier has  a commitment to a function f and it has some values x and y in the  domain and the range of the function. What the prover will do is it  will take as input f, x, y, and the randomness for the  commitment produce a short proof Pi.

The verifier will take the commitment  to the function x, y and the proof, and will either accept or reject the proof. So what are we proving here? So this eval system is itself going to  be a SNARK for the following relation. What this proof Pi proves is that, in fact,  the function f at the point x evaluates to y that the function f is in  fact in the function family, and that in fact, if we commit  to f using the randomness r, we obtain the commitment string com sub f. So the witness for this relation is the description of the function  f along with the randomness r and the statement here, the public statement here  is the commitment string and the values x and y.

So this is what a functional  commitment allows us to do. It basically allows the prover  to commit to a function, and then later on, the prover can  produce a succinct proof that the committed function satisfies f of x is equal to y. And again the security properties should be that  the commitment is binding and optionally hiding, and that the eval protocol is in fact a  SNARK for the relation described here. And I'll briefly mention that the  fact that the eval system is a SNARK means that there's an extractor that will extract  the witness f and r from a successful prover. So now that we know what does  it mean to commit to a function, there are three very important examples of  function families that we might want to commit to.

So the first example is what we  call a polynomial commitment scheme. So what is a polynomial commitment scheme. Here we set the function family to be the set of all univariate polynomials  over Fp of degree at most d. Yeah. This is what this notation means. It's the set of all univariate  polynomials of degree at most d. The prover can commit to some  function in this finite set. And of course, later on, the  prover can be asked to reveal the value of this committed  polynomial at some point x. The second example I'll mention is  what's called a multilinear commitment. So in a multilinear commitment, the  function family is set to be all the multilinear polynomials in at most k variables.

So what is a multilinear polynomial? It's basically a polynomial that's at  most linear in each one of its variables. Yeah. So here's an example. You notice that this polynomial is  linear in each one of the variables. None of the variables are squared or cubed. All the variables have degree at most 1. And again, the goal is to enable the prover to  commit to a function in this function family, and later on, the prover should be able to  open the function at a particular point. The third example I'll mention is what's  called a linear commitment scheme. So in a linear commitment commitment scheme, the set of functions is the  set of all linear functions, which means that the prover will commit to some  function that's parameterized by some vector v, and the function itself is defined  as the inner product of v and u, which is what we wrote over here.

So, it turns out that different SNARK  systems use different commitment schemes. Some of them use polynomial commitments, some use multilinear commitments, some use linear commitments. And depending on which commitment scheme we use, we end up with a different type of SNARK system. What's interesting is that these commitment  schemes are equivalent to one another, in the sense that they can each  be constructed from the other. However, what I want to say  here is that in some sense, there's a strict ordering between these  commitments in terms of generality. And what I mean by that is that a  multilinear commitment is somewhat more general than a polynomial commitment, in the sense that if I give  you a multilinear commitment, it's actually very easy to build  a polynomial commitment from it.

And I'm going to leave it as an  exercise for you to think about. Again, if I give you a  multilinear commitment scheme, your goal is to build a polynomial  commitment scheme from it. And you can do that directly and  actually very, very efficiently. So I'll leave it as an exercise for  you to think about how to do that. This is a good homework problem. And similarly, given a linear commitment, we  can build a multilinear commitment from it. This is actually not difficult to see. And again, I will leave  that as a homework exercise. So these different commitment schemes  lead to different types of SNARKs. The SNARK that we want to construct here is  going to be based on polynomial commitments. So from here on, we're just going  to focus on polynomial commitments.

Okay. So let's talk about a  polynomial commitment scheme. I'm going to abbreviate that as a PCS. And again, just to remind you,  a PCS is basically a functional commitment scheme for the function family of  univariate polynomials of degree at most d. What this means is again, the prover will commit  to a univariate polynomial of degree at most d, and later the prover can prove  to us that the committed function f at the point u evaluates to v  for some public values u and v. Now what's important again is  that this is a SNARK proof, which means that it's going to be very short. The proof has to be  logarithmic in the degree of d, and verifying the proof should also take  time at most logarithmic in the degree of d.

So we want to commit to a huge degree polynomial. The polynomial could have degree 1 billion. We'd like to commit to it  using a very short string. And later on, we want to be able to  open this polynomial at a given point U and the verifier should be able to verify that the polynomial was opened  correctly in time it most log d. And this is all going to be done using a proof  that's at most logarithmic in the degree, which again means that we're  presenting the verifier with very short proofs that are very fast to verify. So we have many examples of  polynomial commitment schemes. So for example using basic elliptic curves  where the discrete log problem is hard, this is the same algebraic structure  that's used for Schnorr signatures.

We can build a PCS from the Bulletproofs system. It turns out this is not exactly a PCS. The proofs -- the evaluation  proofs will be very short, but verifying the evaluation proof will take linear time in d as opposed  to logarithmic time in d. So this is not exactly a PCS, but it does  produce very short evaluation proofs. And it's done based on a very  simple algebraic structure, the same one that you use to  construct Schnorr signatures. Another example can be built from bilinear groups. These are elliptic curves with additional  algebraic structure called the bilinear map. And there are in fact a number of  PCS constructed from bilinear groups.

The most famous one is what's called the KZG'10. We'll talk about this one more in just a minute. This one requires a trusted setup,  as we'll see in just a second. If we want to get rid of a trusted setup, there's  another PCS from bilinear group calls called Dory. And Dory basically is, again, a very efficient  PCS that eliminates the need for a trusted setup. We also have PCS from what are  called groups of unknown order. These are related to the RSA assumption, and the PCS that comes from  such assumptions is called Dark. And we will link to all these papers  in the supplementary reading materials in case you want to see how all of them work.

Finally, there is a PCS that's built from hash  functions only using a mechanism called FRI. FRI is also the building block for the STARK  system, and it can also be used to build the PCS. So as you can see, there are many, many ways  to construct a polynomial commitment scheme. In this segment, I'll focus on the KZG commitment scheme because this is the  simplest one to describe, and it's actually the one  that's most commonly used. So let's see how KZG works. So the KZG system is due to  Kate-Zaverucha-Goldberg back in 2010. This is why it's called KZG,  named after the authors. And it operates in a cyclic  group of prime order p.

So a cyclic group has a  generator which will denote by G, and the group elements basically consist  of G, G plus G, which will denote by 2 G, G plus G plus G, which will denote by 3 G,  and so on and so forth up until p minus 1 G. Yeah. And p times G is going to be equal to 0. So if you're not familiar with what a cyclic  group here is, it's not the end of the world, just think of it as a set of p elements  where any two elements can be added. So for example, I can take  4 times G and 9 times G, add those elements together and what I'll  end up with is the element 13 times G.

So this gives us a set of p elements where any two elements in the set can be added to  obtain another element in the set. Okay. So let's see how the KZG system works. So first of all, we have to describe the setup  algorithm that generates the public parameters. So the way the setup algorithm works is, first, we sample some secret  element alpha in the finite field. And then the public parameters are  actually going to be very simple. It's just going to be the generator, it's the first element of the public parameters. The second element of the public  parameters is going to be alpha times G. Then alpha squared times G all the  way up to alpha to the d times G.

Remember d is the bound and the degree of  the polynomial that we want to commit to. So this gives us a tuple of d plus 1 elements. So really the public parameters consist  of d plus 1 elements in the group. So that's how we generate the public parameters. And the important next step is whoever runs the setup algorithm has to delete this  secret alpha and forget it forever. And this is actually why this is a trusted setup. We have to trust whoever ran the setup  algorithm to delete this value alpha. If the value alpha is not deleted, if  anybody learns what this value alpha is, they can actually create false proofs, meaning  that they can commit to a certain polynomial and then convince the verifier  that the polynomial evaluates to the wrong value at a particular point.

And that will break all of  our SNARK constructions. So we really have to assume that whoever  runs the setup deletes the value alpha, otherwise the verifier could be  convinced that wrong things are correct. So that's the setup procedure, we  generate this tuple of elements. So now let's see how the prover will commit  to a particular polynomial of degree d. All we'll do is we'll take the polynomial that we  want to commit to, evaluate it at the point alpha, yes. So f of alpha is an  element in the finite field. We multiply that by G, and that  will give us a group element, and that's going to be our commitment.

So our commitment is a single  element in the group that we chose. So again, I want to stress, this is kind of remarkable that we can  take a polynomial of degree 1 billion and commit to this entire huge polynomial  using a single element in the group G, which is a very, very short commitment. Usually, this commitment  string will be under 64 bytes. So we're committing to a degree billion polynomial  using a commitment string that's at most 64 bytes. Now you should be asking, well, how  does the prover actually compute this? To compute f of alpha, you need to know alpha.

But didn't I just say that alpha has to be  deleted so that nobody knows what alpha is? So how does the prover actually  compute f of alpha times G? And the answer is this is basically  where we use the public parameters. So what the prover will do is  it will take the polynomial f and write it as a sum of powers of  X, which is what a polynomial is. And the way it will compute f of alpha times G is, it will just use the values  in the public parameters. So in fact, the commitment string is  going to be equal to f of 0 times H0 plus f of 1 times H1 plus f of two  times H2 up to f of d times Hd. Now, if you expand this out just a little  bit, let's just plug in the values for H of 0.

Recall H of 0 is equal to G, H  of 1 is equal to alpha times G, H of 2 is equal to alpha squared times G. You notice that we get this summation down here, and if we take G out of the parentheses we get f of alpha times G, which is in fact  the commitment to the polynomial f. So you notice that, computing  the commitment using the public parameters can be done without knowledge of alpha, and that gives us the  commitment f of alpha times G. So we see that basically using a  linear number of group operations, the prover can commit to a polynomial f.

One thing that I want to point  out is that this commitment scheme is actually binding, but not hiding. In fact, you notice there's no randomness  that was used during the commitment process. And this is exactly because, all we're  building here is a binding commitment. But in fact, this is not a hiding  commitment, in the sense that the commitment string might actually leak  some information about the polynomial f, but for our purposes, if we're building a SNARK,  it turns out a binding commitment is sufficient, we actually don't need a hiding commitment. Nevertheless, I'll say that there's  quite a simple extension of KZG, which makes it into a hiding commitment, but I won't describe that here.

The next thing we have to do is  look at the evaluation procedure. So how do we prove to the  verifier that the committed polynomial f satisfies f of u is equal to v. So again, the verifier here has  the commitment to the polynomial f. It has these values u and v,  and it wants to be convinced that the committed polynomial f  satisfies f of u is equal to v. So how do we do this? Well, we do that using the following observation. So first of all, observe that if f of u is equal to v, that means that u must  be a root of the polynomial f minus v. Right? If we evaluate this polynomial f  hat at the point f minus v, we'll get 0.

So, u must be a root of this polynomial f hat. Now what does it mean that u is  a root of the polynomial f hat? If you think back to your  high school algebra days, you remember that if a polynomial  f hat has a root at the point u, that means that f hat is divisible  by the linear polynomial x minus u. Okay. So what does it mean  that x minus u divides f hat? What it means is there exists  some quotient polynomial, q, such that q times x minus u is equal to  f hat, namely is equal to f(x) minus v. Okay? So this formula here is the critical formula that we're going to use to  do the evaluation proof.

Right? I'll say it again. The quotient polynomial, q, times the linear polynomial x minus u is  equal to the polynomial f of x minus v. And in fact, this quotient polynomial, q,  exists if and only if f of u is equal to v. So this will give you an idea for  how to do the evaluation proof. What the prover is going to do is it's going  to compute the quotient polynomial q of x, it's going to compute the commitments  to the quotient polynomial. So it's going to compute the  commitments string com sub q. And it's going to send this commitment  string over to the verifier. And the commitment to the  to the quotient polynomial q is going to function as our evaluation proof.

What's amazing here is that the  evaluation proof is again constant size. It's a single element in the group G. So we can commit to a polynomial of degree  1 billion using a single group element, and then we can open the  polynomial at a single point, again, using a proof that's  only a single group element. This is kind of quite remarkable  for a commitment scheme. How does the verifier verify this proof Pi? Well, what the verifier will do, is it's basically  going to check that the two commitments line up. So it will take the commitment to the quotient  polynomial q and multiply it by alpha minus u. Now if you think about this for just one second, you'll see that alpha minus u times com q actually is exactly the commitment to the  polynomial q times x minus u.

Okay? So on the left-hand side her, we computed -- The verifier computed the commitment to the polynomial that's on the  left side of this equality. And the right side, the verifier  computes takes the commitment of f subtracts v times the generator, and again, if you think about this for a minute, you'll see that this is exactly the  commitment to the polynomial f of x minus v. So on the left-hand side, the verifier constructed the commitment  to the left-hand side polynomial here and the right-hand side the verifier constructed the commitment to the  polynomial on the right-hand side. And if these two commitments are equal to one  another, that means that this equality must hold.

This follows from the binding  property of the commitment scheme. So the verifier will accept  basically if this equality holds. So, again, what's amazing here is  that the verifier is doing only constant amount of work to verify this condition. No matter what the degree of the  polynomial is, it could be in the billions, verifying that the polynomial  evaluates to v at the point u only takes constant work for the verifier. So again, some of you might be  wondering, well, wait a minute, I said that nobody knows what the value  of alpha is. This value is deleted. So how is the verifier  computing alpha times com q?

And the answer is actually that, this is actually done using an additional  algebraic structure called a pairing, which I'm not going to describe here. What the pairing does, is it basically allows the verifier to check that this condition holds  without actually knowing what alpha is. The only thing the verifier needs to know  is the generator G for this step over here, and the value H1, which allows it to do this  comparison without actually knowing what alpha is. So what's interesting here  is that the verifier only needs two elements from the public parameters. Yeah, just G and H1.

It doesn't need a huge public parameter string. It only needs these two elements G and H1. So this is really important in  a blockchain application because if we want to implement an on-chain verifier,  the contract, the smart contract that's going to run the verification algorithm  only needs to be told what G and H1 is and that's going to be stored in the  code that implements the verifier. And as a result, the code that verifies  these proofs actually is not large at all. It only contains these two points, and that's enough to verify that  the opening was done correctly. So this is the key idea of the KZG  commitment that makes it so useful in building SNARKs and in blockchain applications.

One thing I'll say is that, computing the  quotient polynomial when d is very large, when the degree of the polynomial is large, can  be actually somewhat computationally expensive, and in fact, much of the work  that provers that use this PCS do, in fact, goes into computing this polynomial q and computing the commitments to this polynomial. So the lingering question in your mind  should be, well, why is this PCS secure? Why is it binding? And why is the evaluation proof of SNARK? So it turns out that can be proved, but  I'm not going to describe that today. Again, you can look at a supplementary reading material if you want to see how  to prove that this PCS is secure.

I will say that proving that the KZG PCS is secure  relies on fairly strong cryptographic assumptions. Now, this KZG system has been used so extensively, That there are many generalizations of it. I wanted to mention that, in fact, KZG can be generalized to  committing to k-variate polynomials, not just univariate polynomials. The one difference is when  committing to a k-variate polynomial, the evaluation proof actually  has k group elements in it, as opposed to a single group element when  committing to a univariate polynomial. That's one generalization.

The other generalization I want to  mention is what's called a batch proof. And again, this is a very  important trick to remember. It comes up all the time in the SNARK space. And so, a batch proof basically allows the prover to open many polynomials  at many points all at once. So imagine the verifier actually  has a bunch of commitments, let's say commitments to n polynomials, and the prover wants to prove  that each of these polynomials evaluates to a certain values at certain points. So there are n polynomials, and we want to  open each of them at m different points. Naively, this will take n  times m KZG evaluation proofs.

So n times m group elements. But it turns out using these batch proofs,  it's actually possible to prove all these facts using a proof that only takes  either one or two group elements. So we can take like n times m evaluation proofs, and sort of batch them into a single very short proof that contains only  one or two group elements. Okay. So again, I want to emphasize  this is a very important trick that's used to shrink SNARK  proofs and comes up all the time. So that's our description of  the KZG commitment scheme. However, I did want to remind you  that KZG requires a trusted setup.

Remember, whoever runs the setup algorithm has to  delete alpha at the end of the setup procedure, and also the public parameter size is linear in  the degree of the polynomial we want to commit to. If the polynomials we're committing  to are in the billions, we are going to end up with public parameters  that are actually quite large. So the Dory commitment scheme actually  solves many of these problems. First of all, it has transparent setup. So there's no secret randomness  in the setup procedure. In fact, there is no setup procedure. Anybody can run the setup  procedure for themselves. So there are no public parameters, and there are no secrets that are needed  for generating those public parameters.

The commitments string is still a  single group element, just like in KZG. The evaluation proof and evaluation  time is a little bit worse than KZG. Remember in KZG, the evaluation proof  and verification time were constant. Evaluation proof was one group  element and verification time was a constant number of group operations. In Dory, this is replaced by logarithmic proof size and logarithmic verification  time, which is still quite good. So I just wanted to mention that Dory  exists as a possible replacement for KZG. Proof size and verification  time is not as good as KZG, But the benefit is that we eliminate the trusted setup and the public parameters that  are generated by the trusted setup.

Okay. So that's all I wanted to  say about polynomial commitments. And now we can switch gears and talk about the  second component that's needed to build the SNARK. Remember, we have our polynomial commitments, we're going to combine that using what we call a polynomial interactive oracle  proof or a polynomial IOP. And these two things together will  give us a SNARK for general circuits. So let's define what is a  polynomial interactive oracle proof. So again we're going to fix our computing  model to be arithmetic circuits. Circuits that have addition  and multiplication gates mod P and that take a statement and a witness as input.

And let's look at a particular statement x. So a polynomial IOP is basically a proof system to prove that the prover knows w  such that C(x,w) is equal to 0, but the proof works in a very specific way. And so, the first step of the proof system  is, again, to preprocess the circuit C? So we have our setup algorithm  that will preprocess the circuit C, and outputs parameters for the prover. It's also going to output  parameters for the verifier, but the parameters for the  verifier is a bunch of polynomials. Okay. So here I denote these polynomials f of 0, f  of minus 1, f of minus 2, and so on and so forth. It's convenient to index them by negative  values as we'll see in just a second.

Now Sv only contains commitments  to these polynomials, which is why we write the polynomials in a box. Yeah. So a commitment to a polynomial  we'll denote by a polynomial in a box. And here basically, Sv just contains  a commitment to S plus 1 polynomials. So that's the first step of the poly IOP. Later, when a statement x  and a witness w are chosen, the prover will convince the  verifier that it knows a w using the following interactive procedure. First, the prover will send a commitment  to some polynomial to the verifier, the verifier will choose some random value r1 in  the field Fp and send this r1 back to the prover.

Remember that this arrow means choose  an element at random from the set Fp. Then the prover will send the  commitment to another polynomial. The verifier will send will choose a random r2 and  send that to the prover, and so on and so forth, until finally the prover  commits to its last polynomial, and finally the verifier is going to run some verification procedure that  takes as input the statement x and all these random values  that the verifier generated, along with the ability to query the set of  polynomials at any points of its choosing. We have here commitments to the polynomials in Sv, and commitments to the polynomials that  were generated during the proof itself, and the verifier can basically ask the prover to open any of these polynomials at any  points of the verifier’s choosing.

And so, based on all this data, the verifier  will decide to either accept or reject the proof. So again, I want to emphasize that  what happens in a polynomial IOP is that the verifier sends a bunch  of random values to the prover, the prover correspondingly  commits to a bunch of polynomials, and then later on, the verifier can ask the prover  to open these polynomials at a number of points, and based on that, it decides  whether to accept or reject. Now, you might be wondering what is the point for  the verifier to send random values to the prover? The prover could just generate  random values on its own, but the point is that these  random values are chosen after the prover commits to certain polynomials.

Yeah. You notice, for example, r2 is only chosen and sent to the prover  after the prover commits to f1 and f2. At the time that the prover committed to  f1 and f2 it does not know what r2 is, and that's very important to prevent the  prover from proving a false statement. Okay. So that's syntactically  how a polynomial IOP works. And as usual, we want the polynomial  IOP to satisfy a number of properties. It has to be complete, which  means that the verifier will always accept the interaction with a valid prover. It has to be knowledge sound, which means that if a prover P star is able to convince  the verifier with some probability, there's an extractor that will  extract the witness from the prover.

And you notice here, the extractor  will basically use the statement as well as all the polynomials  that the prover committed to, to be able to do its extraction process. And optionally, for trying to construct a zk-SNARK, then we would want the the  polynomial IOP to be zero knowledge, meaning that all the values that were sent to the verifier reveal nothing  about the prover's witness. Okay. And now we can see sort of what  the resulting SNARK will look like. So we'll parameterize the polynomial  IOP by two values, t and q. t will be the number of polynomials that the prover will commit to  during the interactive phase, and q will be the number of  evaluation queries during the verifier procedure at the end of the proof.

This is basically the number of points at which  the prover has to open the committed polynomials. And what's interesting is that usually  t and q are actually quite small. That is, the prover only has to  commit to like three polynomials and then open them at three points, and that's it. So typically, as we'll see, we can build polynomial IOPs where  t and q are really quite small. And now you can sort of see  what the SNARK looks like. The prover will basically sends t  polynomial commitments to the verifier. Later on, the verifier will open  these polynomials at q points. And then the verifier will decide  whether to accept or reject.

Now, you're probably wondering what I  just described in the polynomial IOP is an interactive process between  the prover and the verifier, whereas a SNARK is supposed to be non-interactive. So how do we convert this interactive  process into a non-interactive process? Well, we can do that using a general  transformation called a Fiat-Shamir transform that makes interactive proofs of this  nature into non-interactive proofs. So the Fiat-Shamir transformation is a general  way to convert this type of interactive protocol, where the verifier just contributes public  randomness into a non-interactive protocol.

So we will convert the interactive process into a non-interactive process using  this Fiat-Shamir transformation. And now you can see kind of the parameters of  the final SNARK that we're going to end up with, where the proof itself is going to contain t  polynomial commitments plus q evaluation proofs. The verifier's time is going to be dominated  by verifying these q evaluation proofs, and the prover's time is going to be dominated by the time to compute t commitments  and to generate q evaluation proofs. And since generally t and q are really small, you can see that the verifier's  time is basically constant, meaning it's independent of the  size of the circuit being proved, and the length of the proof is also constant, again, independent of the size  of the circuit being proved.

So now the only thing left to do is  basically to construct a polynomial IOP. And that's exactly what we're  going to do in the next section. So by the end of the next segment you'll  see how these polynomial IOPs work, and then combining a polynomial IOP with a polynomial commitment scheme  like KZG will give us a SNARK. All right. So I'll see you in the next segment. Bye everyone.