ZK Whiteboard Sessions - Module One: What is a SNARK? by Dan Boneh

Transcript

Hello everyone, and welcome  to our short course on SNARKs. My name is Dan Boneh, and in the next few  segments we'll talk about what SNARKs are, how they are used, and how they are built. In the following segments, we'll dive into  some more real-world applications for SNARKs and real-world systems that  make use of these SNARKs. So what is a SNARK? Well, actually, a SNARK is not one of these  imaginary animals from a Lewis Carroll story. Instead, a SNARK is basically  a way to prove a statement. Okay. So SNARK stands for Succinct  Non-Interactive Arguments of Knowledge. But really, what a SNARK is, it's a short  proof that a certain statement is true.

For example, I might claim that  I know a certain message m such that the SHA-256 of m is equal to 0. Yeah. I don't want to reveal what m is to you,  but I want to prove to you that I know such an m. Well, a SNARK allows you to generate a  very short proof that's actually very, very fast to verify that I know exactly such an m. Now, the interesting thing is, if  the message m is like a huge message, let's say m is like a gigabyte-long message, the trivial proof that I know m is  simply to send the message m over to you, and then you can verify the  SHA-256 of m is equal to 0. The problem with this trivial proof, where I just send the message m over to  you, is that, A, the proof is not short.

It would be a gigabyte long if the  message happens to be a gigabyte long. And it's also not fast to verify,  because the verifier has to hash the entire message to verify that it's equal to 0. Our goal is to to build a proof  that is going to be very short. It's just going to be a few kilobytes. And not only is it going to be short,  it's going to be superfast to verify. It's going to take just a  few milliseconds to verify, and the verifier will be convinced  that I know such a message m. Now there's an extension to a SNARK  called a zero knowledge SNARK, where not only do I want to  convince the verifier that I know a message m that satisfies the property, I also want to do it without  revealing anything about the message m other than the fact that  its SHA-256 hash is equal to 0.

Okay? And this is called a zero knowledge SNARK. So it allows us to prove that certain statements are true without revealing anything  about why the statements are true. So these zero knowledge SNARKs have  many applications throughout computing, but it turns out that there are an  especially good fit for for blockchains. And in fact, on the blockchain, the zero  knowledge SNARKs have many, many applications, and so let me just give you a few of those. So the first one is basically  has to do with privacy, which allows us to do what we call private  transactions on a public blockchain. When we talk about a public blockchain, we talk about a chain where the data is actually  available for people to see on the blockchain. Anyone can verify that the  chain rules are being followed, but nobody should be able to tell  the content of the transactions.

Yeah. This is why we talk about private  transactions on a public blockchain. And examples of this are things like Tornado Cash, Zcash, IronFish that allow you to do direct  transfers of funds from one person to another without revealing who is doing the  transfers, and what the transfer amounts are. But you can even run decentralized applications on a public blockchain in a  privacy preserving manner. So, for example, Aleo is building tools that will allow you to run an entire  application such that you can -- anyone can verify that the  application is run correctly, but no one will know that what the application  code is, what the application data is, who's interacting with the application, and so on.

So we can kind of provide a  fairly strong notion of privacy, while anyone can verify that the  chain is progressing correctly and the rules of the chain are being followed. Another example of application  is -- has to do with compliance. For example, exchanges might want  to prove that they're solvent, so they have enough funds to cover  their obligations to their customers, but they'd like to do it  in a zero knowledge manner so that they can post a very short proof than  anyone can verify that the proof is valid so that the exchange is solvent. But they'd like to do that without revealing  anything about their internal operations. So without revealing how much assets they have, how many customers they have, and so on.

So we call these zero  knowledge proofs of solvency, and you can do those actually quite efficiently. Again, these proofs can be  posted on a daily basis. Anyone can verify that the  proof of solvency is correct. The proof itself is very short, and anyone  can verify that the proof is correct, and the proof itself is actually very short. Another example is private compliance. As you may know, in the US there's a requirement to record KYC information for  transactions over $10,000. And so you might want to keep  transactions under $10,000 private and transactions over $10,000 all sorts  of information will be recorded on them.

You can use these zk-SNARKs to prove that a  transaction is under $10,000 or over $10,000, using a very short proof such that  if the transaction is under $10,000, then nothing will be revealed  about the transaction data. So one can comply with privacy regulations  while keeping user data private. Yet another example, which I like,  but maybe is a bit further out, is what we call zero knowledge taxes, where if all your transactions  are recorded on a blockchain, you could imagine actually proving  that you paid the right amount of taxes by simply showing how much taxes you owe and  producing a zk-SNARK that proves that the amount that you showed is actually consistent with the  amount of transactions that you did on-chain.

So maybe one day using these zk-SNARKs will get to a world where our taxes  are paid in zero knowledge, so that we don't have to reveal all  of our finances to third parties. Finally, the last application  area I'll mention is scalability. You may have heard of rollup systems, where the idea is that a thousand transactions  are going to be processed in a batch, and then one would produce a short proof  that all these transactions are valid, and only this short proof will  be posted to the blockchain. The verifiers on-chain will just  verify that the proof is correct, without actually having to verify  a thousand transactions one by one. And again, because the proof is  succinct, it's short and fast to verify, this greatly reduces the amount of work  that on-chain verifiers have to do.

So what is a zk-SNARK? So to do that we have to give a little  bit of cryptographic background. So let's dive right into the details. So the first thing we have to explain  is what's an arithmetic circuit. Yeah. So let's fix some finite fields. So if you don't know what a  finite field is, don't worry. It's basically just a set of numbers from 0 to P minus 1 where we can do addition  and multiplication modulo p. So we'll fix some prime greater than 2. And then we will look at the  set 0 to P minus 1 using the addition and multiplication modulo p operations. This is called a prime finite field.

Now once we have a field, we can define  arithmetic circuits on top of the field. So what's an arithmetic circuit? Basically, an arithmetic circuit is  what we call a directed acyclic graph, where the internal nodes are called gates and they're labeled with an arithmetic operation,  either addition, subtraction or multiplication. And the inputs are labeled basically  with the input variables X1 to Xn. And also we give ourselves constant 1. And so here you have an example  of an arithmetic circuit. You can see the inputs are X1  and X2, here's the input 1. And the gates are labeled  plus, minus and multiplication.

And you can see that as you evaluate this circuit, the circuit basically defines a multivariate  polynomial, a polynomial in n variables X1 and X2. So really what an arithmetic circuit  is, is a polynomial in n variables, and the circuit itself gives a recipe  for evaluating this polynomial, right? Given X1 and X2, I can literally  walk through these gates and evaluate the polynomial at the given input. Now, just for convenience, we're going to refer to the size of the  circuit C as the number of gates in C. Yeah. So the size of the circuit  in our example is going to be 3. All right.

It turns out that you can capture a lot  of computation using arithmetic circuits. In fact, in some sense, all polynomial time computations can be  captured by polynomial size circuits. I won't make that precise, but let me give you a few examples  of interesting arithmetic circuits. So for example, we can talk about  the hashing arithmetic circuit where we have the hashing  circuit will take two inputs. It will take the hash value and  then a hash input m as an input, and the circuit will basically output 0  if and only if SHA-256 of m is equal to h. Otherwise it will output a non-zero value.

Okay. So one can implement such a circuit. Okay? So in fact, naively we can just  write it as h minus SHA-256. So if the hash is equal to SHA-256 of m we get 0. Otherwise we get non-zero. And it turns out that these circuits, this SHA-256 function can be implemented in an  arithmetic circuit using about 20,000 gates. Yeah. So it's not a very large circuit, and it also -- already does  something that's quite useful for us. Another example of a circuit could be  the signature verification circuit, where it takes a public key,  a message and a signature.

It would output 0 if signature -- If sigma happens to be a valid ECDSA signature  on the message m with respect to the public epk. The second concept we need is  what's called an argument system. So let's see what an argument system is. And again, we're going to  build on an arithmetic circuit. So imagine we have a circuit C  that takes two inputs x and w. x is going to be called the statements. And w is going to be called the witness. And these are not necessarily  single elements in our field. This could be -- this could  be a tuple of n elements, and a witness could be a tuple of m elements. And the circuit will output some  element in the finite field.

Okay. So what is an argument system for the circuit C. Well, again, we have our prover and our verifier. The prover is going to take as inputs  the statement x and the witness w. The verifier will only take  the statement x as input. Now what will happen is the prover's goal  is going to be to convince the verifier that there exists some witness  such that C of x,w is equal to 0. You notice the verifier doesn't know  the witness, the verifier only knows X, and yet the prover wants to convince the verifier  that there is a w that makes C of x, w equal to 0. So the way they'll do it is  maybe they'll interact with one another in sending messages back and forth.

And finally the verifier is going to say, yes, I believe the statement or, no,  I don't believe the statement. Okay. So that's basically  what an argument system is. Before we get into the exact syntax  of what an argument system is, let's actually zoom in a little bit more and let's look at a particular  type of argument system called a non-interactive preprocessing argument system. Yeah. It's a bit of a mouthful,  but the concept is not difficult. So again, we have our arithmetic circuit C, and then a non-interactive preprocessing  argument system works as follows; First of all, there's some sort  of a preprocessing procedure.

We call this the setup procedure,  and we'll denote it by S. The setup procedure will preprocess the  circuit C and produce some public parameters. Yeah. So we call those Sp as parameters,  public parameters, for the prover, and Sv as public parameters for the verifier. Now the prover will take the public parameters  for the prover along with x and w as before. The verifier will take the public parameters for  the verifier along with the statement as before, and then the prover will produce a proof Pi and the verifier will simply  accept or reject this proof.

The reason this is called a  non-interactive system is because you notice the only interaction now is that the prover sends a proof to  the verifier, and that's it. The verifier and the prover don't  actually have an interactive conversation. The verifier just receives the proof and then  decides whether to accept or reject the proof. And again, the reason these are called  preprocessing argument systems is because the circuit is preprocessed ahead  of time using some algorithm C, and then once the preprocessing is done, the only interaction between the prover and the verifier is that the prover sends  this proof Pi to the verifier. So now we can define the syntax for a  preprocessing argument system more precisely.

So the argument -- The preprocessing argument system  is made up of three algorithms. The setup algorithm, the prover and the verifier. As we said, the setup algorithm outputs Sp and Sv, the prover will output a proof Pi, and the verifier only takes the statement x  and the proof Pi and says accept or reject. Okay. So I want you to remember  these three algorithms, S, P and V. They're going to come up again and again  and again throughout the entire course. Okay. So what are the properties that  an argument system needs to satisfy. Well, so let's see. So the first property is  what we call completeness.

Yeah. So this means that if the prover is honest and it really does have a statement xx and  a witness w such as C(x,w) is equal to 0, then the verifier will accept the proof  from the prover with probability 1. You can see here, this is the  proof that the prover will generate and the verifier, when it processes that  proof, will output accept with probability 1. The second property is called knowledge soundness, which says that, in fact, if the verifier  accepts the proof from the prover, this means that the prover actually knows a  witness w that makes C of x, w equal to 0. Okay. Now what does it mean to know something?

That's something that we'll  define later on in the segment. In particular, if we have a malicious  prover that doesn't know the witness w, that malicious prover will not  be able to produce a proof Pi, or rather, any proof Pi that  that malicious prover generates will cause the verifier to accept  with only negligible probability. Okay. That's kind of the goal  where we're shooting for. So those are the completeness  and soundness properties. And then there's an optional property  which is called zero knowledge which says that if you look at the proof Pi along  with everything else that the verifier knows, so the circuit, the parameters,  the statement and the proof, that reveals actually nothing about the witness w.

Okay. So in some cases, we need zero knowledge. In other cases, we don't need zero knowledge. For example, in some rollup systems,  actually there's no need for zero knowledge. The main property that many rollup systems use from SNARKs is the fact  that they are fast to verify. Short and fast to verify. The zero knowledge property is needed  more for some of the privacy applications. Okay. So now we're ready to kind of -- So now we're ready to define what a SNARK is. So a SNARK is basically a  succinct argument of knowledge. Yeah. So what is it?

It's basically a succinct  preprocessing argument system. So it has all the properties  that we talked about before, but it also has to produce a succinct proof. So what is a succinct proof. It's one where the proof itself is very short. In particular, the length of the proof can  only be logarithmic in the size of the circuit, logarithmic in the number of gates in the circuit. By the way, we allow the proof to  be linear in the security parameter. This lambda is what we call a security parameter, but let's ignore that for now. And the proof should also be very fast to verify. So what do we mean by fast to verify?

What do we mean is, again, that the time to verify  should be logarithmic in the size of the circuit. Of course, we -- The verifier at least needs  to read the statement x. So we allow the verifier to run in linear  time in the size of the statements. But the point is, it has to be  logarithmic in the size of the circuit. And again, of course, we allow it to run  in linear time in the security parameter. But actually in -- at the level  that we're having this conversation, we can actually ignore the security parameter. So no need to worry if it's  not clear what that is. So now that we see these  succinctness requirements, it should be clear why there's  a need for a preprocessing step.

In particular, you realize the verifier  doesn't even have time to read the circuit C. The verifier can only operate  in time logarithmic in C, and so it can't possibly read the circuit. But if it can't read the circuit, then how is it going to verify that the  prover really has a satisfying witness. And so really what's happening here is that  the setup procedure, the preprocessing step, what it does is it creates a very  short summary of the circuit. So in fact, Sv is going to be a very short  string that the verifier can actually read, it has actually time to read that string, and that's necessary because the verifier  simply can't read the circuit on its own.

So the setup procedure is summarizing  the circuit for the verifier. And it's really quite remarkable that we can  summarize a circuit using so little information. Using only logarithmic data  in the size of the circuit. And that's already enough for the  verifier to verify that the prover has a satisfying assignment for the circuit. Okay. So this is the purpose of the setup procedure to summarize the  circuit for the verifier. So now, as we said, a SNARK is a succinct  proof system that is complete knowledge sound and succinct in a zk-SNARK is basically a  SNARK that in addition, is also zero knowledge.

Okay. So now we kind of  understand what a SNARK is. We can go back to our trivial,  to the trivial argument system, where the prover simply sends the  witness in the clear to the verifier, and the verifier accepts  if C of x,w is equal to 0. This is the trivial, trivial argument system. This argument system is clearly  complete and knowledge sound, but it doesn't satisfy many of  the properties that we want. First of all, the witness might need to be secret, and here the prover actually  reveals the witness to the verifier. So this argument system is  definitely not zero knowledge.

Second of all, the witness  might actually be quite large, as in our example of a hash function  where the input was actually -- the witness was actually a gigabyte long. We want a very short proof, not  something that's as long as the witness. And finally, the verifier has  to compute the entire circuit. The verifier has to compute  the C(x,w) is equal to 0. But computing C(x,w) might be difficult. Of course, it takes linear time in the size of C, whereas we want a verifier that only runs  in logarithmic time in the size of C. So we want something that's much, much faster. So the trivial system fails  on many different accounts, and the question is how to actually build SNARKs  that do satisfy our succinctness properties and possibly our zero knowledge property, and we're going to see exactly how that works.

So again, just to kind of show you  how remarkable these SNARKs are, let's go back to our first example, where  we wanted to prove that we know this SHA -- We know a witness w1 to wn such that  SHA-256 of this witness is equal to x. So here the statement that's  given to the verifier is x. Yeah. In our earlier, example  X was just equal to 0. But x could be anything. The witness is w1 to wn, and so the prover has both  the statement and the witness, and it's able to produce a proof that the  verifier will accept if the proof is valid, and the remarkable thing is that the proof  is only logarithmic in the size of n.

Yeah. Logarithmic in the size of the witness. And also the verifier's time is only  logarithmic in the size of the witness. This looks like impossible. How can the verifier possibly be convinced that  the prover knows a witness of size, a gigabyte, without actually looking at the witness, and  with only doing logarithmic amount of work? This seems impossible, and yet we're going to show  you exactly how that's done. So now that we understand what a SNARK is, let's dive a little bit deeper  into this setup procedure. Okay. So the setup procedure actually  is a typically a randomized algorithm, which means that it takes as input the circuit C, but it also takes a bunch of  random bits as it's doing its work.

And then it outputs this Sp and Sv, the parameters for the prover and  the parameters for the verifier. Now, there are three types of setup  procedures that we like to talk about. The first one is what we call  a trusted setup per circuit. That means that when the  setup procedure is running and it's using these random bits, the random  bits have to be kept secret from the prover, otherwise the prover -- if the prover  actually knows what these random bits are, that would allow the prover  to prove false statements, which would be quite terrible because that would  lead to loss of funds in a blockchain application. The reason we say that this is a  trusted setup or circuit is because for every circuit, you have to rerun the  setup procedure using new random bits, and all those random bits  would have to be kept secret.

So if you want to preprocess one circuit, you'd  have to run this and keep the random bit secret. If you want to process another circuit, you  have to run this and keep those new random bits secrets and so on and so forth. Yeah. So there's a lot of secrets floating around, and it's very important that those random  bits are destroyed once algorithm S is done. Otherwise, again the prover will  be able to prove false statements. So a better setup procedure is what we call, still  trusted, but we call it a universal procedure where basically the the secret random  bits r are chosen once and for all, and they're independent of the circuit C.

So really we can think of the setup  procedure as broken down into two algorithms. Yeah. There's the initialization procedure, and then there's what we  call the indexing procedure. Yeah. So the initialization procedure  will use these random bits r to generate some public parameters which will denote by pp. But this is a one-time process. Once this initialization procedure  runs, we throw away the random bits r, and we never need to generate  secret randomness ever again. And then there's an indexing procedure that  uses these public parameters in the circuit C and generates -- and it generates Sp and Sv.

But the point is this indexing  procedure is a deterministic procedure. So there's no secret data  that needs to be kept secret. This is something that anyone can run,  anyone can verify that it was done correctly, once the public parameters have been generated. Okay. So the point of a universal setup is that we  have the dangerous secret part is only run once. And then for as many circuits as  we want, we can generate Sp and Sv. And that's just a deterministic  procedure that anyone can run and verify that Sp and Sv were generated correctly. Yeah. So this is what we call  trusted but universal setup.

It turns out, it's also updatable, but maybe  I won't talk about the updating property here. And then finally, the best thing we can  hope for is that we have a transparent setup where actually the setup procedure only uses  the circuit and doesn't require any secret data. So there's no secret random bits that have to  be destroyed after the setup procedure is done, anyone can run the setup procedure and verify  that Sp and Sv were generated correctly. Okay. So clearly as we go down this list,  we get into better and better setups in the sense that we don't have to  worry about random bits are leaking and allowing the prover to prove false statements.

So in a transparent setup, if a prover proves a  statement and the verifier accepts that proof, there is no risk that the statement  is false because perhaps the random bits leaked when they weren't supposed to leak. So there has been tremendous progress in  building SNARKs over the last couple of years. Here, I made a short table of some of  the SNARKs that are used in practice. This is actually a very partial list. There's a ton of work on  SNARKs in the last few years, so forgive me if your favorite  SNARK is not in the table. One of the most widely used  SNARKs is called Groth16. This is a SNARK with a constant size proof.

The proof is only 3 group elements,  no matter the size of the circuit. This comes out to about 200  bytes, which is very short. The size of the provers parameters  is linear in the size of the circuit, which means that for a large  circuit this can be quite large. Say for a circuit with a million gates, the prover  parameters will be several tens of megabytes. However, the verifier parameters are quite short, they're only about a hundred bytes, and this is very important  for on-chain verification. A smart contract that needs to  verify SNARK proofs only needs to store about 100 bytes of parameters  embedded in the smart contract code.

Verification time is also constant time. You can see it's very fast, about 3 milliseconds, no matter the size of the circuit. The downside of Groth16 is that  it requires a trusted setup, and this trusted setup has  to be rerun for each circuit. Every time we change our circuit,  we have to rerun the trusted setup and make sure that the random bits  used during setup are destroyed. In advance, from 2019 are  the Plonk and Marlin SNARKs. These are two different SNARKs  with similar capabilities. The proof in both of these proof systems  is constant size about 400 bytes, so only slightly bigger than  Groth16, but still very short.

The prover parameters and verifier  parameters are similar in size to Groth16, and verification time is also constant,  although slightly worse than in Groth16. All of these are quite remarkable, where verification time is independent of  the size of the circuit and quite fast. The benefit of Plonk and Marlin is that  although they require a trusted setup, the trusted setup only needs to be run once. You run the trusted setup and  throw away the random bits, and then anyone can generate the prover  and verifier parameters, Sp and Sv, for their favorite circuits using a  deterministic verifiable procedure.

So the question that remained  after these very beautiful ideas, is how to build an efficient  SNARK without a trusted setup. We, in fact, have many such SNARKs,  and I list three of them here. One example is Bulletproofs that is a  transparent SNARK that produces short proofs. However, Bulletproof has verification time  that is linear in the size of the circuit, so Bulletproofs is technically  not a SNARK by our definition. Remember, we wanted verification time to  be logarithmic in the size of the circuit. However, verification time is still  quite fast for reasonably sized circuits. What's appealing about Bulletproofs  is that the algebra needed to run the prover and verifier is very similar to  the algebra needed for Schnorr signatures, and this is appealing in systems that  already rely on Schnorr signatures.

Our next example of a transparent  SNARK is called a STARK, which is not exactly a SNARK, but  also produces logarithmic size proofs. Although the proofs, as you can see, tend to be somewhat larger than in other  proof systems on the order of 80 Kilobytes. STARKs, again, are very fast  to generate and to verify, and an important benefit of  STARKs is that they are based on simple collision-resistant hash functions, which makes them secure against  quantum computers, which is wonderful. STARKs are also implemented commercially,  and they're actually quite widely used. Finally, I'll mention another transparent SNARK  called DARK that also has very short proofs.

DARK is not that widely used at the moment, because it is based on an algebraic  structure called a class group, and this algebraic structure  is not very widely implemented. But DARK is still a very elegant system. So maybe this is something that  we'll see more use of in the future. Now, many other SNARK systems have  been developed in the last few years. These three dots here capture  quite a lot of exciting work. We'll provide a reading list at  the end of the course in case you want to read more about the  latest developments in the space, including other types of SNARK systems. The last thing I want to point out about  these SNARKs is that in all of them, the prover has to do work that is nearly  linear in the size of the circuit.

Clearly, the prover has to do at least  linear work in the size of the circuit, because the prover has to read  the circuit and evaluate it. The point here is that the time to generate  a proof is almost linear in the size of C. In early SNARK systems, the prover's time  was quadratic in the size of the circuit, which meant that these systems were  impractical for large circuits. For example, if the circuit  had a million gates in it, it would be impossible to produce a proof, because running the prover  would simply take too long. In all modern SNARK systems, the prover runs in  nearly linear time in the size of the circuit, and this is absolutely crucial for  scaling the prover to large circuits.

In fact, I'll tell you that  much of the recent work on SNARKs is about further reducing the prover time and also reducing the memory requirements that  the prover needs as it's generating the proof. So now that we understand what SNARKs are, and we  kind of see the different SNARK systems out there, let's talk a little bit about how SNARKs  are actually used in the real world. So if you're going to use a SNARK  in your own software environment, typically you will use a domain-specific language to write out the statements  that you want to verify. So let's say you want to verify  some complicated signatures and hash functions and whatever  statements about transactions, all of that will be captured -- in principle,  will be captured in an arithmetic circuit.

But writing down arithmetic circuits is  actually quite difficult for developers. So instead, what developers will do is they will write a program in what's called  a in a domain-specific language. And there have been many such  programing languages developed, like Circom and ZoKrates and  Leo and Zinc and Cairo and Noir. And in fact there's a framework  now called CirC that if you want to build your own DSL for one reason or another, you can use the CirC framework  and very quickly build a custom DSL language for writing things that  will later be proved using a SNARK. So once you write your program  in whatever language you choose, that program will get compiled  basically into a SNARK-friendly format.

So this could be an arithmetic circuit,  although there are other types of formats. For example, we'll later talk about  Rank One Constraint System, R1CS. This is a very common format  that SNARK systems can ingest. There are other formats like  like AIR or Plonk with custom gates or Polynomial Identity Languages. So there are other SNARK-friendly formats that SNARK systems can actually  use to generate proofs for. Once we've compiled our program  to a SNARK-friendly format, the next thing we do is we generate the  parameters for the SNARK, so the Sp and Sv, and then basically we feed this  into a SNARK backend proving system.

This would be an implementation of one of the  provers from the table on the previous slide. The prover would take the statement x  and the witness as witness as input, and produce a proof Pi that's succinct. So the proof itself is going to be  very short, maybe just a few kilobytes, and the verifier can verify  that proof very quickly. As I said, the prover runs in linear  time in the size of the circuit, but the circuits or the SNARK-friendly  formats tend to be quite large. And as a result, even though  you run in linear time, generating the proof is actually  quite a heavy computation.

It can take -- depending on the size of the program, it can take a few seconds to a few  minutes, possibly even a few hours. And, but eventually you'll end up with a very short proof that anyone can  verify very, very quickly. So now that we understand what SNARK systems are, the last thing I want to do in this segment is actually walk you through  more formal definitions of what does it mean for something to be sound, or what does it mean for  something to be zero knowledge. So let's start with knowledge soundness. Okay? That's an easier definition to explain. And so, our goal is to say that if the  verifier accepts a proof from the prover, that necessarily means that the prover knows  a witness such that C(x,w) is equal to 0.

So what does it mean for the prover to know w? Well, this sounds like a philosophical question. What does it mean for somebody  to know something at all? Well, in a cryptographic setting, we say  that the prover knows w if the value w, if the witness can actually  be extracted from the prover. And as a silly way to think about this, we're actually going to extract  the witness from the prover by sort of torturing the prover  until it gives us the witness. So what does it mean to torture an algorithm? Well, let's define this more precisely. So formally, we say that a SNARK system, S, P, V, is knowledge sound for a particular  circuit C if the following condition holds. Yeah. So we're going to look at an adversary,  a polynomial time adversary called A, and this adversary is going  to masquerade as the prover,

and it's trying to prove a statement even though  it doesn't know the witness for that statement. Okay? So the way this  adversary works is as follows. So as usual, we run our setup  procedure to generate Sp and Sv. Now we run the first part of the adversary. So we break the adversary into two parts. We'll call them A0 and A1. This is for convenience. We'll see why in just a second. The first part of the adversary will take  Sp as input and produce a statement x that the adversary wants to forge a proof for. A0 will also output a state  that we will give to A1. Now A1 is the second half of the adversary.

It's like we're splitting the adversary's  brain into two parts, A0 and A1. A1 will take the state from A0 along  with the statement x that A0 produced, and then we'll produce a proof Pi that  we will then give to the verifier. Yeah. And so we'll say that this  adversary is successful if the verifier actually accepts the proof from the  prover with some non-negligible probability. Yeah. So even if the adversary  is able to successfully convince the verifier with probability one over a million, we'll say we're already saying  that the proof system is broken.

Okay. So again suppose we have an adversary that  is able to produce a proof for a statement x. The adversary chose the statement x, and it's able to produce a proof for  the statement that the verifier will accept with probability at least one in a million. Then we say that S, P, V is knowledge sound if  for such an adversary there exists an extractor E, and the extractor E works as follows. So this extractor is going to try and  extract a witness from the adversary. So again, we're going to run our setup procedure, we're going to run A0, so  that the adversary chooses the statement x where it forges the proof Pi.

And now the extractor, what's  interesting about the extractor is it's only giving the statement x for  which the proof will be generated. And then it's allowed to  interact with adversary A1, the one that actually generates  the proof, as an oracle. Yes, it's allowed to basically send it messages, it's allowed to mess with its  environment in a certain way. And after this extractor  interacts with this adversary A1, it's able to actually extract  the witness from this adversary. Okay? And again, the point would be that this  witness is a valid witness for the circuit. So C(x,w) really is equal to 0.

And again, that should hold with  probability of one over a million, maybe slightly less than one over a million,  but about probability one over a million. So again, what this definition says is, if the adversary was able to  produce a proof for the statement x, then there's an extractor that  interacts with the adversary and is able to extract a witness, a  valid witness with the same success probability that the adversary  had in fooling the verifier. So this is what it means for a  proof system to be knowledge sound. Yeah. If you can convince the verifier,  then we can extract the witness from you with roughly the same probability that  you were able to convince the verifier.

So now let's turn to proving zero knowledge. And to prove zero knowledge, actually, I  have to start with a very simple example. So the classic simplest  example for a zero-knowledge proof system is the game Where's Waldo? Right? So Where's Waldo? This character is called Waldo. The Where's Waldo game is where you're given  a large picture with lots of people in it, and your job is to find Waldo. Yeah. So you start to look around and you realize, ah, Waldo is right here in  the center of the picture. Now, imagine you wanted to prove to someone that you know where Waldo is without  revealing to them where Waldo is.

So you want to prove to them in zero  knowledge that you know where Waldo is. So here's a very simple proof system. You walk into a room, you have nothing on you, and the verifier will basically  hand you this picture, and the verifier will give you some scissors. Yeah. You will basically find  Waldo inside of the picture, and you will cut out the picture  of Waldo from this larger picture. Then you will destroy -- you  destroy the larger picture. You'll rip it up so that  nothing is recoverable from it, and then you will hand the  picture of Waldo to the verifier.

The verifier basically, what does it know? It sees -- it gave you the picture and  you gave it back a picture of Waldo. The only way you could have done that -- Because you have nothing, the  only way you could have done that is if you found Waldo in the  picture that the verifier gave you. Now why is this a zero-knowledge proof? The reason is that the verifier  already knows what Waldo looks like. So if the verifier wanted to, it could  print a picture of Waldo on its own. So in some sense, the information that you gave the verifier doesn't tell the verifier  anything that it didn't already know. It already knows what Waldo looks like, and as a result, the picture of Waldo that you gave it didn't teach the verifier  anything that it didn't already know.

And this idea is exactly the idea  behind the definition of zero knowledge, in that the proof should reveal nothing to the  verifier beyond what the verifier already knew. Okay. So that's what we're trying to capture. And so the question is how to capture it. So again, we have our SNARK system, S, P, V. We'll say that S, P, V is zero  knowledge if for every statement x, the proof Pi should reveal nothing about the witness w beyond what the verifier  already knew about this witness. So the verifier supposedly knows that w exists,  but nothing else should be revealed about w.

And the question is again, what  does it mean to reveal nothing? And so we'll define that more precisely. First of all, let's give an informal definition  for what does it mean to reveal nothing. Well basically we'll say that Pi reveals nothing about w if the if the verifier can  actually generate Pi by itself. Right? So what does it mean that  you learned nothing from Pi? Well, what it means is you could  have generated Pi on your own. So you don't really need the prover to do it, and therefore you didn't learn  anything from the prover. So we'll say that S, P, V is zero knowledge  if there is an efficient algorithm, this algorithm is called a simulator.

And the simulator basically will just take  the circuit and the statement as input, yeah. And it will produce Sp, Sv and more importantly it will  produce the proof Pi on its own. And the point is that this proof  Pi that the simulator generates looks like the real Pi that the  real prover would have generated. So again, you notice because the  simulator can generate this proof Pi, just given the statement without  knowledge of the witness, this means that the verifier didn't  learn anything about the witness, it could have just run the simulator on its own and produce the proof Pi  that it got from the prover.

Yeah. So the simulator basically proves  that Pi reveals nothing about the witness. So let's see this a bit more precisely. And by the way, here, I should say  I'm giving a simplified version of the definition just to get the main point across. There are lots of nuances in the definition of  a zero knowledge, especially for a SNARK system, which we won't get into here, but I hope the intuition for what the  definition captures will be very clear. Okay. So let's see again. So we'll say that S, P, V is a zero-knowledge  proof system for the circuit C. And so, we'll say that it's zero knowledge  if there's an efficient simulator, Sim, such that for all x for which there exists a w, yeah, so we're only trying to prove  zero knowledge for statements x for which there really does exist a witness  w that makes the circuit evaluate to 0.

Let's see. So we say that the distribution of  everything that the verifier sees, the verifier sees the circuit, it sees the parameters, it sees the  statement and it sees the proof. Yeah. For everything that  the circuit sees where the parameters are generated by the setup procedure, the proof is generated by the by the real prover. Everything that the verifier sees can actually  be simulated by a simulator algorithm Sim. Okay? So the simulator basically will  produce exactly the same outputs, except that here, the simulator is only  given the circuit and the statement x.

So look at what just happened. Basically the simulator produced exactly  the same outputs as the real prover. No one can tell this five tuple  apart from this five tuple. And as a result, this means that you can  generate the proof just given the statement x. So this might look a little fishy because now it looks like the simulator can  basically generate fake proofs, right? It's able to generate a proof Pi  without actually knowing the witness. So why does this not violate the  knowledge soundness property? And the reason is because the simulator  actually has more power than the actual prover.

You notice that the simulator, in this  case, is able to choose Sp and Sv, whereas the actual prover is given Sp. So the simulator actually has a bit  more power than the real prover. That's what enables it to generate the  proof Pi without knowledge of the witness. The prover doesn't have this power, and so the only way it can generate the  proof Pi is if it knows the witness w. Now I should say that there are many  other ways to define zero knowledge, and in reality we would define zero  knowledge a little bit differently, but the simulator always has to have some  capability that the prover doesn't have, and that's what allows it to simulate the proof  without actually knowledge of the witness.

Okay. So this brings us to  the end of our first segment. Let's quickly review what we talked about. So we talked about a zk-SNARK for a circuit C. We said that for a public statement X,  the prover will output a short proof that convinces the verifier that it knows the  witness such that C(x,w) is equal to 0. The proof has to be very short. It has to be very fast to verify. Short and fast means logarithmic  in the size of the circuit. We briefly mentioned that this is  good for private payments and for running applications privately on the blockchain. We also mentioned that this is  good for private compliance.

For example, if you need to  comply with financial regulations, but you want to do that without  revealing any sensitive user information. It's also very, very useful for Layer 2  scalability in systems like zkRollups, which we will talk about in much  greater detail later in this course. And it turns out that SNARKs are useful  for many other blockchain applications where you might think about  how to run a DAO privately. So how do we keep the  membership of the DAO private? How do we keep the assets of the DAO private, so that they're only no known to the DAO  manager, but not known to anybody else? It turns out zk-SNARKs play  an important role there too.

We can talk about how to do private governance. So how do we run governance votes for a project in  a way that each individual votes are kept private? Again, zk-SNARKs are useful  in that environment as well. So there are many, many  applications for zk-SNARKs. Some of them are being explored today, some  of them will be explored in the future. And so lots and lots to talk about here. There's a lot of research going on in this Space,  lots of new applications cropping up every day, and lots of new SNARK proof systems popping up. So this is a very active area, it's  a lot of fun to work in this space, and I can't wait to see what will  be invented in the coming years.

Okay. So I'll stop here. And in the next segment we're going to talk  about how to actually build a zk-SNARK.