A SNARK (Succinct Non-Interactive Argument of Knowledge) is a cryptographic proof system that enables a prover to convince a verifier that a statement is true without revealing any information about the underlying data, with proofs being extremely short (logarithmic in circuit size) and verification taking only milliseconds regardless of circuit complexity. SNARKs achieve this through preprocessing of arithmetic circuits, which are directed acyclic graphs representing computational statements as polynomials. The system relies on three key algorithms: a setup procedure that generates public parameters, a prover algorithm that creates the succinct proof, and a verifier algorithm that checks proof validity. Zero-knowledge variants additionally ensure the proof reveals nothing about the witness beyond what the verifier already knows. SNARKs have transformative applications in blockchain technology including private transactions, compliance verification, and scalability solutions like zk-Rollups.
ZK Whiteboard Sessions: What Is a SNARK? | Dan Boneh | Module 1
Added: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.
Up Next
zk-SNARKs Math Foundations: Polynomials, Pairings, and More
@taipeieth
666 views•2021-08-25
Torrent File Format & Bencoding: A Technical Deep Dive
@AsliEngineering
12.5K views•2022-08-08
Operational Security Essentials: A Guide for Hacktivists (OPSEC)
@hitbsecconf
157.4K views•2012-11-26
Understanding Ethereum: A Comprehensive Beginner's Overview
@99Bitcoins
3.1M views•2018-06-26
Related Study Plans & Knowledge Roadmaps
Structured learning paths in Blockchain & Crypto