Welcome to my Cryptography Notes.
⬩
To learn is to teach - to teach is to learn, and to take notes.
⬩
Hopefully you can learn something from these notes, and please feel free to create an issue or a pull-request if you have suggestions.
⬩
Take care anon, and remember not to trust, but verify.
— erhant
Berkeley ZKP MOOC 2023 Spring
Summary of ZKP MOOC Spring 2023 lectures, which are a series of lectures given by Dr. Dan Boneh, Dr. Shafi Goldwasser, Dr. Dawn Song, Dr. Justin Thaler and Dr. Yupeng Zhang. This course covers fundamental techniques to build ZKP protocols, tools to implement ZKP for different computations, and different applications of ZKP in blockchain and other areas
There may be some repetitions among the lectures, but that is good and especially useful when you come back to skim over the notes.
Take a moment and look at that roster, it's like champions league up there. Make sure you watch the course videos on YouTube, and visit the course website.
-
Introduction & History: In the first lecture, we take a look at the starting point of all this What separates classical proof from an interactive proof, and how powerful are interactive proofs? What is zero-knowledge and how did it came to be? An excellent primer by Prof. Shafi Goldwasser.
-
Overview of Modern SNARKs: While the previous lecture was more about interactive proofs (IPs), this one is all about SNARKs. We learn what they are, and how to build them.
-
Programming ZKPs: Suppose you have an idea, and you write a program about it and you have to reduce it to some constraint system so that zero-knowledge cryptography can do it's thing. How can we do it? See this lecture for the answer.
-
SNARKs via IPs: This lecture is also about building SNARKs, with various methods! We will look at Merkle trees, Schwartz-Zippel lemma, Sum-check protocol and much more.
-
The PLONK SNARK: In this lecture we will first see KZG polynomial commitments, and then talk about useful proof-gadgets on committed polynomials. Finally, we learn PLONK.
-
Polynomial Commitments using Pairings & Discrete-log: We first look at some group theory background, then dive into KZG and Bulletproofs. A summary of pairing & d-log based polynomial commitments is also given in the end.
-
Polynomial Commitments using Error-correcting Codes: We look at error-correcting codes, Reed-Solomon Code in particular. Then, we describe a polynomial commitment scheme based on linear codes.
- Interactive Proofs
- Efficiently Verifiable Proofs (NP-Proofs)
- NP-Languages
- Zero-Knowledge Interactive Proofs
- Interactive Proofs for a Language
- What is Zero-Knowledge?
- ZK Proof of Knowledge (ZKPOK)
- Graph 3-Colorability
- Practical Applications of ZK
- Complexity Theory: Randomized Analogue to NP
- Arthur-Merlin Games & is AM = IP?
- Efficient Verification
Interactive Proofs
When we think of proofs made by Euclid, Gauss, Euler and such, we think of proofs where we are trying to show that given some axioms and declarations, you can show that some claim is true. These are classical proofs.
There is a much more powerful proof system, called interactive proofs, we must think of proofs more interactively such as:
sequenceDiagram actor P as Prover actor V as Verifier note over P, V: claim P ->> V: proof note over V: accept/reject
Efficiently Verifiable Proofs (NP-Proofs)
For efficiently verifiable proofs (aka NP-Proofs) we have the following setting:
sequenceDiagram actor P as Prover actor V as Verifier note over P, V: claim = x note over P: works hard to generate proof w note over P: unbounded time P ->> V: short proof w s.t |w| = poly in |x| note over V: find V(x, w), takes poly time in |x| note over V: accept if it is 1, reject otherwise
Let us check some example claims.
Example: is a product of 2 large primes
A trivial proof of this would be the following:
- Prover sends as a proof.
- Verifier would check for , and if true it will accept. In doing so, the Verifier learned about , which is not good for us!
Example: is a quadratic residue mod
What this means is that, such that . It turns out that finding such an is a very hard problem, as hard as factoring problem actually.
Even so, our prover is unbounded and can find such an in the end. A trivial proof for this would be:
- Prover sends as a proof.
- Verifier calculates and check if , accepts if true and rejects otherwise.
Example: Two graphs are isomorphic
Consider two graphs, as a set of edges and . We say that if there is an isomorphism that maps an edge to such that .
In layman terms, these two graphs are the same graph, but they are drawn a bit differently. Again, a trivial proof here would be to simply send the isomorphism itself to the Verifier. However, finding the proof itself is a very hard problem, although checking if it is correct is not!
NP-Languages
Definition: is an NP-language (or NP-decision problem) if there is a time verifier where:
- Completeness: true claims have short proofs, meaning that if then there is a sized witness such that .
- Soundness: false theorems have no proofs, meaning that if then there is no witness, so we have .
The main question of this course is not focused on this subject though. Instead, we are trying to see if there is another way to convince a verifier, for example considering the questions given above.
Zero-Knowledge Interactive Proofs
The main idea of ZKP, although very informally, is that a Prover "will prove that they can indeed prove the claim if they wanted to", but they are not doing that so that information is kept private.
sequenceDiagram actor P as Prover actor V as Verifier note over P: proves "I could prove it if I felt like it" P ->> V: sends a ZKP note over V: wow, ok I believe that
We need to extend our proof model to work with ZK. We will need two more ingredients:
- Interaction: rather than passively reading a proof, the verifier engages in a non-trivial interaction with the prover.
- Randomness: verifier is randomized, i.e. coin tossing is allowed as a primitive operation. Furthermore, the verifier can have an error in accepting/rejecting but with a small negligible probability.
With this, our proof model becomes as follows:
sequenceDiagram actor P as Prover actor V as Verifier note over P, V: claim x loop i = 1, 2, ... P ->> V: a_i V ->> P: q_i end note over V: accept/reject
Here, the Prover is computationally unbounded but the Verifier must be efficient, i.e. runs in probabilistic polynomial-time (PPT).
Example: Two Colors
Consider a string x="🔴🔵". We claim that there are two colors in this string. However, our verifier is color-blind! How can we prove that indeed this string has two colors?
sequenceDiagram actor P as Prover actor V as Verifier note over P, V: claim: x="🔴🔵" has 🔴 and 🔵 loop i = 1, 2, ... P ->> V: x note over V: b ← {0, 1} alt b = 1 note over V: x' := flip(x) else note over V: x' := x end V ->> P: x' alt x' = flip(x) note over P: b' := 1 else note over P: b' := 0 end P ->> V: b' note over V: if [b != b'] then reject end note over V: accept
Let us describe what happens in this interactive proof:
- The prover sends x to the verifier, say = "🔴🔵".
- The verifier tosses a coin, and flips if it is heads meaning = "🔵🔴". Otherwise, stays the same, meaning = "🔴🔵". Verifier sends this to the prover.
- Prover will then compare to , and since he can see colors, he will be able to tell whether is flipped or not. Based on this, he will say = heads or tails, depending on the flip. Prover sends to the verifier.
- Verifier looks at , and says "wow this guy can actually guess whether I got heads or tails, he must be seeing colors then!". If and does not match, she rejects.
- This interaction is repeated polynomially many times, until finally the Verifier accepts.
Let us analyze this formally. If there are 2 colors, then verifier will accept. If there is a single color only, for all provers for a single interaction. Repeating this interaction times would mean that which becomes a tiny probability for large . So, it is very unlikely that a prover can keep faking it for that many interactions.
Example: is a quadratic residue mod
Here, the claim is the language .
sequenceDiagram actor P as Prover actor V as Verifier note over P, V: claim: ∃x s.t. y ≡ x^2 (mod N) loop i = 1, 2, ... note over P: choose r where 1 ≤ r ≤ N and gcd(r,N)=1 note over P: s := r^2 mod N P ->> V: s note over V: b ← {0, 1} V ->> P: b alt b = 1 note over P: z := r * sqrt(y) mod N else note over P: z := r end note over V: if [z^2 != s * y^c mod N] then reject end note over V: accept
So basically what the prover is doing is,
- generates a random quadratic residue
- asks for the verifier to make a coin toss
- if heads , it sends
- if tails , it sends
- the verifier checks if . if not, it rejects
- after many interactions, if the verifier hasn't rejected so far, it accepts
Similar to the previous example, if the prover had not known , he would not be able to win many interactions.
So what made this whole thing possible? Let's recap:
- The statement to be proven has many possible proofs of which the prover chooses one at random.
- Each such proof is made up of exactly 2 parts: seeing either part on its own gives the verifier no knowledge; seeing both parts imply 100% correctness.
- Verifier chooses at random which of the two parts of the proof he wants the prover to give him. The ability of the prover to provide either part, convinces the verifier.
Interactive Proofs for a Language
Definition: is an interactive proof for , if is probability polynomial () time, and:
- Completeness: if then always accepts. Formally: .
- Soundness: if then for all cheating prover strategies, will not accept except with negligible probability. Formally: for such cheater provers , it holds that
- In a good scenario, we would except and where is a negligible function. However, we might also show that or equivalently: .
Definition: Class of languages IP = .
What is Zero-Knowledge?
For true statements, we want the following to be true: what the verifier could have computed before the interaction IS EQUAL TO what the verifier can compute after the interaction.
So basically, these interactions had no effect whatsoever on the computational power of the verifier! That is what zero-knowledge means. Now, let's be more formal.
sequenceDiagram actor P as Prover actor V as Verifier note over P, V: theorem T loop i = 1, 2, ... P ->> V: a_i V ->> P: q_i end note over V: accept/reject
After an interactive proof, the verifier has learned:
- that the claim/theorem is true
- a view of interactions, i.e. the transcript of answers and queries, and the coins that has tossed.
A view is formally defined as a random variable from the probability distribution over coins of and interactions with :
The Simulation Paradigm
's view gives him nothing new, if he could have simulated that view on it's own. In other words, the simulated view and real view are computationally indistinguishable!
In cryptography, we have the notion of computational indistinguishability, where there are two distributions and , and a distinguisher that tries to distinguish these two. In doing so, he will sample both distributions at random, and will try to guess from which distribution that sample is taken from. If the probability of distinguishing this sample is at most then and are indistinguishable!
That is a rather heavy paragraph, so let me give an example. A vendor is selling watches, and they have a set of real Rolex watches, and a set of fake Rolex watches. You go to the shop, and ask for a sample. The vendor secretly flips a coin,
- if heads, vendor gives you a real Rolex watch
- if tails, vendor gives you a fake Rolex watch
You try to guess whether the flip was heads or tails. If the probability that you guess correctly is at most then the set of fake Rolex watches are indistinguishable from the set of real Rolex watches! Good for the vendor 🙂
Definition: An interactive protocol is honest-verifier zero-knowledge for a language if there exists a PPT algorithm (a simulator) such that the following two probability distributions are poly-time indistinguishable:
- , here is for technical reasons and for large you can just ignore it.
A caveat about is that we allow it to run in expected-poly-time. Meaning that there may be some very unlucky cases where the algorithm takes a long time, but in expectation it is poly-time.
Also notice that this is for honest verifiers, and we would like the proof to hold for all verifiers. So, our final definition should cover all verifiers.
Definition: An interactive protocol is zero-knowledge for a language if for every PPT , there exists a PPT algorithm (a simulator) such that :
Flavors of Zero-Knowledge
Again, consider the real distribution and simulated distribution . Based on these, there are flavors of ZK:
- Computationally Indistinguishable Distributions (CZK), where the two distributions are computationally indistinguishable.
- Perfectly Identical Distributions (PZK), where the two distributions are the same.
- Statistically Close Distributions (SZK), where the two distributions are statistically close.
A Simulation for Quadratic-Residue (QR) Proof
Consider the QR proof from above, where we were able to prove with zero-knowledge that we know there exists some such that . Check that interactive proof again, what is the here? We see that the verifier learns about , it also generates some coin toss value and finally it learns .
So, . A simulator should output the same view on its own! Can we do it? Yes, in fact, we can do it perfectly!
Simulator works as follows:
- First, pick a random bit .
- Then, pick random .
- Compute .
- Output .
This is identical to what the honest verifier had viewed in the actual interactive proof. Notice that the simulator did not have to know about , but thanks to that division on 3rd step, it could produce a valid for the view.
What about an adversarial verifier, for example, one that does not pick at random? Well, we can still construct a simulator:
- First, pick a random bit .
- Then, pick random .
- Compute .
- If then output , otherwise go to step 1 and repeat!
With this setting, even if we don't know what is doing behind the scenes, we should expect that our randomly picked should match their fixed and adversarially computed . In fact, in expectation this takes 2 attempts, since it is just a coin flip!
ZK Proof of Knowledge (ZKPOK)
Notice that prover has prove not only that the claim is correct, but also that they know a square root modulo . This is more than just a proof of the claim! So, consider the language for poly-time relation .
Definition: is a proof of knowledge (POK) for if PPT knowledge extractor algorithm such that , in expected poly-time outputs such that .
Here, means that may run repeatedly on the same randomness, possibly asking different questions in every execution. This is called the Rewinding Technique.
A ZKPOK for Quadratic-Residue (QR) Proof
We have seen the ZKP for a prover that knows such that . Let's construct the Extractor for this proof.
sequenceDiagram actor P as Prover actor E as Extractor note over P, E: claim: ∃x s.t. y ≡ x^2 (mod N) note over P: choose r where 1 ≤ r ≤ N and gcd(r,N)=1 note over P: s := r^2 mod N P ->> E: s E ->> P: 1 (heads) P ->> E: z = r note over P, E: rewind P ->> E: s E ->> P: 0 (tails) P ->> E: z = rx note over E: output rx/r = x mod N
Notice the rewind there, hence the Rewinding Technique. What this trick does is that it allows us to access again! In the interactive proof, we would normally have a new random every time the prover sent us something, but here we can have access to the same again and again. As such, we were able to obtain and , and thus find via division.
Example: Graph Isomorphism
Consider the graph isomorphism problem from the examples at the beginning. The proof is similar to how it works for quadratic residues. So, the claim is that there is an isomorphism between and .
- The prover produces a random graph and sends it to verifier.
- The prover finds an isomorphism from to .
- The prover also finds an isomorphism from to .
- The verifier sends a coin toss (bit) to prover, and prover returns .
- Verifier checks if .
- These steps happen repetitively, until some poly-time later if the verifier did not reject so far, it accepts.
Notice that since then . So, the prover indeed knows . However, since both isomorphisms are never given to the verifier at the same time, the verifier can't find that isomorphism!
This ZKP is actually of flavor PZK, so the two distributions of real view and simulator view are identical! Furthermore, there is a ZKPOK that prover knowns an isomorphism from to . Formal proofs left to the reader.
Graph 3-Colorability
Do all NP Languages have ZK Interactive Proofs? Proven in [Goldwasser-Micali-Widgerson'86], the answer is YES! They show that if one-way functions exist, then every in NP has computational zero-knowledge interactive proofs. The proof will come from an NP-complete problem known as Graph 3-Colorability, hence the title of this section.
The ideas of the proof are as follows:
- Show that an NP-complete problem has a ZK interactive proof. [GMW87] showed a ZK interactive proof for (graph 3-colorability problem). For any other in NP, due to NPC reducibility. Every instance can be reduced to a graph such that if then is 3-colorable, and if then is not 3-colorable.
- Existence of one way functions imply a hiding & binding bit commitment protocol.
What is a Commitment Scheme?
In a commitment scheme, there are two functions:
- takes an input , let us think of it as a bit in , and produces a commitment . Once committed, the commitment does not reveal whether is 0 or 1.
- allows a receiver of a commitment to open it, and reveal what is in there. In this case, some bit that is either 0 or 1.
For a commitment scheme,
- Binding means that if you have committed to some , then the decommit procedure on that commitment may only reveal , not something else.
- Hiding means that from outside, you can't guess the bit with more than 1/2 probability.
An example commitment scheme would be to use a semantically secure probabilistic encryption scheme.
- where sender chooses some random and sends .
- where sender send the same random and , and receiver rejects unless .
Proving a graph is
Suppose there is a graph as in the set of vertices and set of edges, and the prover knows some coloring which is a mapping that maps a vertex to a color.
- Prover picks a random permutation of colors and the colors the graph with this permutation. It still is valid because its just different colors for the same graph. We show this as for . Then, the prover commits to each newly colored vertex by running protocol.
- Verifier selects a random edge and sends it to prover.
- Prover runs on the colors of edge points and reveals and .
- Verifier rejects if , otherwise it repeats steps 1-3 and accepts after iterations.
Now, let's look at the properties of this interactive proof:
- Completeness: if is 3-colorable, then the honest prover uses a proper 3-coloring & the verifier always accepts.
- Soundness: if is not 3-colorable, then for all it holds for (meaning that we have iterations as many as the square of number of edges) that,
- Zero-Knowledge: Easy to see informally, messy to prove formally.
Honest-Verifier Computational ZK Simulator
First, let us examine the view of this interactive proof.
- We have an edge
- We have the commitments to each vertex coloring as .
- We have the decommit of colors .
Let us show the honest-verifier CZK simulator. For the graph the simulator will choose a random edge . Then, it will pick random colors such that . For all other vertices , it will set to some fixed color, and commit to all .
The output of simulated view is:
- We have an edge
- We have the commitments to each vertex coloring .
- We have the decommit of colors .
As we can see, the views are kind of indistinguishable! They are not the same though, as the commitments to vertices other than are illegal colors, the simulation had no idea how to color the graph anyways. However, since the distinguisher can't see what is under the commitment (hiding property) they are computationally indistinguishable.
The simulator for all verifiers is also given in the lecture, but not noted here.
Practical Applications of ZK
So far, we have seen some ZK proofs of claims:
- is the product of two primes .
- is a square .
- Two graphs are isomorphic.
There are a lot more proofs in the domain of Interactive Proofs, for example see the following claims:
- Any SAT Boolean Formula has satisfying assignment.
- Given encrypted inputs , and some program , the program has output such that .
- Given encrypted inputs , and some encrypted program , the program has output such that .
These are all provable in ZK, and when you think about the last example that is pretty awesome. Let's talk a bit more general:
- You can prove properties about some message , without revealing itself but only showing or .
- You can prove relationships between messages without revealing them, such as or . In fact, you can show that there is some value that when used with a poly-time function , you have .
In general idea: you can use ZK as a tool to enforce honest behavior in protocols without revealing any information. To do that, imagine that a protocol player sends a message and along with that new message, it sends a ZKP that for some history and randomness . Furthermore, they will commit to this randomness as . This makes honest behavior with ZK possible since is in NP.
Some more real-world applications are:
- Computation Delegation
- ZK and Nuclear Disarmament
- ZK and Forensics
- ZCash: Bitcoin with Privacy and Anonymity
- ZK and Verification Dilemmas in Law
Complexity Theory: Randomized Analogue to NP
No Randomizations | With Randomizations (Coin toss) | |
---|---|---|
Efficiently Solvable | P (Polynomial time) | BPP (Bounded-error Probabilistic Polynomial time) |
Efficiently Verifiable | NP (Non-deterministic Polynomial time) | IP (Interactive Polynomial time) |
Is IP greater than NP?
The answer is YES! Let's go over an example. Suppose that you have two graphs that are NOT isomorphic. The shortest classical proof of this would be to go over all possible isomorphisms (takes time in the order of factorials!) and show that none of them work.
However, there is an efficient interactive proof!
sequenceDiagram actor P as Prover actor V as Verifier note over P, V: claim : G_0 and G_1 not isomorphic loop i = 1, 2, ..., k note over V: flip coin: b = {0, 1} note over V: pick random isomorphism γ V ->> P: H := γ(G_b) alt H isomorphic to G_0 note over P: b' = 0 else note over P: b' = 1 end P ->> V: b' note over V: reject if b' != b end note over V: accept
Here is the idea of this proof: if and are indeed isomorphic, then the prover would have no idea whether is isomorphic to or , because it would be isomorphic to both of them! So, he would have at most 1/2 chance in guessing the correct bit. After iterations, the possibility of not being rejected by the verifier becomes , which is negligible.
Also, how does prover find isomorphisms like that so easily? Well, remember that the prover is all-powerful and computationally unbounded, so they are very well allowed to find such hard stuff.
Here is what is different about this IP though; here, the Verifier is doing more than just tossing coins. Here, it actually picks a random isomorphism, and creates the graph from that!
Completeness and soundness hold for this proof; however, it is not zero-knowledge! This is because if the verifier is not honest, and it's just someone that wants to find out whether some graph is isomorphic to , they can very well find it by sending to the honest prover! Therefore, there is knowledge that is learned about depending on what the prover replies to that.
The solution to this problem is rather straightforward: have the verifier send a ZKP that they know the isomorphism , this way the reply from prover does not change the knowledge of verifier.
Arthur-Merlin Games & is AM = IP?
In the Interactive Proof's so far, the Verifier was hiding the result of coin tosses and also was able to do some extra computations, it was a PPT Verifier so it could do anything that the time allows. However, in an Arthur-Merlin game [Babai-Moran'88], the Verifier will only acts as two things:
- A public coin tosses
- A decision function
So, the prover will see in clear the result of coin tosses!
sequenceDiagram actor P as Prover (Merlin) actor V as Verifier (Arthur) note over P, V: claim "x in L" loop i = 1, 2, ..., k V ->> P: coins_i P ->> V: answer_i note over V: reject if bad end note over V: accept
The question here: is Interactive-Proofs more powerful (i.e. can prove more claims) than Arthur-Merlin Games? Is coin privacy necessary?
The answer turns out to be no, AM = IP actually [Goldwasser-Sipser'86]!
Fiat-Shamir Paradigm
You can remove the interaction in AM protocols via Fiat-Shamir Paradigm [Fiat-Shamir'87]. Let that sink in, you are literally removing the interaction from an interactive proof, more specifically, you are removing the coin tossing machine. How is that possible?
Let be a cryptographic Hash function, meaning that you can use this function as a random oracle that when you feed any string it gives you back random string of length , essentially an output of coin tosses.
The idea is the following:
- Normally, we had a Prover that sent some answer and got back from the Verifier.
- Now, the Prover will send but instead of waiting for coins by the Verifier, it will generate its own coins simply via .
What if the Prover needs coins before sending any answer? In that case, the first message of coins is posted "publicly" for all to see, and then Fiat-Shamir heuristics is applied to the rest.
However, Fiat-Shamir does not mean you can make all interactive proof's into non-interactive proofs! Yet, many specific AM protocols with an efficient prover can benefit from this heuristic.
Efficient Verification
Problem Class | Objective Idea | Classical Proofs | Interactive Proofs |
---|---|---|---|
NP | a solution | YES | YES |
Co-NP | 0 solutions | ? | YES |
#P | many solutions | ? | YES |
PSPACE | ? | YES |
It was shown by [Fortnow-Karloff-Lund-Nissan'89] and [Shamir'89], that IP can be used to prove many many more problems than what classical proofs are able to! In fact, this brought the question: what if we have something more powerful than IP, for example, what if there is a second prover?
Indeed, as shown in [Benor-Goldwasser-Kilian-Wigderson'88], you can prove a lot more with two provers! In fact, you now have unconditional PZK for NP problems. [Babai-Fortnow-Lund'91] has shown that you can even prove NEXPTIME (non-deterministic exponential time) problems with interactive proofs.
Going even further, [Reichardt-Unger-Vazirani'13] has shown that a classical verifier can verify the computation of two entangled but non-communicating polynomial time quantum algorithms. Finally, a recent work [Ji-Natarajan-Vidick-Wright-Yuen'20] has shown that with two not necessarily efficient quantum provers, and a classical verifier, you can prove all Recursively Enumerable Languages. Kind of meaning like everything; that's one bizarre result!
- SNARK
- Arithmetic Circuits
- NARK: Non-interactive Argument of Knowledge
- SNARK: Succinct NARK
- Building a SNARK
- (1) Functional Commitment Scheme
- (2) - Interactive Oracle Proof
- SNARKs in Practice
SNARK
In the previous lecture, we have discussed interactive proofs (IP) in general. Now, we will mostly be talking about non-interactive proofs, in particular SNARKs.
A SNARK stands for a succinct proof that a certain statement is true. Succinct here is meaning that the proof is "short". For example, I have a statement:
I know an such that .
In SNARK, the proof should be short and fast to verify. A trivial proof of the above statement is to simply send to the verifier. However, that proof is not short; it is as big as . Verification is also not fast, as the verifier has to hash the entire message to actually see the proof.
A SNARK can have a proof size of few KBs and verification should take at most seconds.
zk-SNARK
In the case of a zk-SNARK, the proof reveals nothing about . zk-SNARKs have many applications:
- Private transactions: Tornado Cash, ZCash, IronFish, Aleo (private dApps).
- Compliance: private proofs of solvency & compliance, zero-knowledge taxes
- Scalability: Rollup systems with validity proofs
- and a lot more commercial interest…
Why is there so much commercial interest? Well, things go back to a paper [Babai-Fortnow-Levin-Szegedy'91] where they show that a single reliable PC can monitor the operation of a herd of supercomputers running unrealiable software.
This single reliable PC is a slow and expensive computer. An example of such a machine from today is actually a L1 Blockchain!
Blockchain Applications
SNARKs and zk-SNARKs can be used in many ways within a blockchain.
- Outsourcing Computation: Even without the need of zero-knowledge, an L1-chain can quickly verify that some off-chain service has done some work correctly.
- Scaling with Proof-based Rollups (zkRollup): An off-chain service processes batch of transactions, and the L1-chain verifies a succinct proof that transactions were processed correctly.
- Bridging Blockchains (zkBridge): A source chain locks up some asset, so that it can be used in another destination chain. In doing so, it proves that indeed the asset is locked.
- Private Transactions: A ZKP that a private transaction is valid. Many examples: TornadoCash, ZCash, Ironfish, Aleo.
- Compliance: A proof that a private transaction is compliant with banking laws (e.g. Espresso), or a proof that an exchange is solvent without showing the assets (e.g. Raposa).
Non-Blockchain Applications
Blockchain is really spearheading the development in these areas, but there are many non-blockchain applications of SNARKs too. Here is one example: proving that a photo is taken at some time and at some place.
The initial attempts to this was made via C2PA, a standard of content provenance. With C2PA, the camera that captures the picture will sign its metadata with a secret key (that is assumed not to be extractable by a user). The signed metadata will ensure that the location and timestamp is valid.
However, newspapers and press that display a picture often have to apply some post-processing, such as rescaling, cropping and gray-scaling. There is actually a list of allowed operations by Associated Press. Doing any of these will break the signature, as it can be though of as tampering.
Here is the solution by [Kang-Hashimoto-Stoica-Sun'22] to this problem using zk-SNARKs: suppose that the machine that is doing the post-processing has the photo and some list of allowed operations . Denote the original photo as and as the signature. The editing software will attach a proof of claim: "I know a pair " such that:
- is a valid C2PA signature on
- is the result of applying to
- Metadata of is equal to metadata of
Et viola, you can now be sure that the processed photo is original! The proof size is less than 1KB, with verification time less than 10ms in browser. For images around 6000x4000, just a few minutes is enough to generate a proof, which is awesome.
Arithmetic Circuits
Definition: Fix a finite field for some prime . A finite field is just a set of numbers where we can do addition and multiplication in modulo . An arithmetic circuit is a DAG (directed acyclic graph) where internal nodes are labeled and inputs are labeled . The circuit defines an -variate polynomial with an evaluation recipe.
Here is an example:
flowchart LR 1((1)) --> - x2((x2)) --> - 1((1)) --> + x1((x1)) --> + x2((x2)) --> + + --> x - --> x x1 --> x x --> r(( ))
This circuit defines the operation .
For convenience, the size of the circuit refers to the number of gates, and is denoted as . In the example above, .
For example:
- You can implement a circuit that does . This outputs 0 if is the preimage of using SHA256, and something other than 0 otherwise. This circuit uses around 20K gates, which is not bad!
- You can have a that outputs 0 if is a valid ECDSA signature on with respect to .
- A theorem states that all polynomial time algorithms can be captured by polynomial sized arithmetic circuits!
Structured vs. Unstructured
There are two types of arithmetic circuits in terms of structure:
- Unstructured Circuit is a circuit with arbitrary wires.
- Structured Circuit is a circuit with repeating structure within, denoted as , and for some input and output the flow of this arithmetic circuit looks like the following:
is often called a virtual machine (VM), and every step of execution in this structure can be thought of as a single step of some processor, or like a clock cycle.
Some SNARK techniques only apply to structured circuits.
NARK: Non-interactive Argument of Knowledge
Suppose you have some public arithmetic circuit where,
- is a public statement
- is a secret witness
Denote as a preprocessing step for this circuit, which will output a pair as in public parameters prover and verifier respectively.
sequenceDiagram actor P as Prover P(pp, x, w) actor V as Verifier V(vp, x) P ->> V: proof π that C(x,w) = 0 note over V: accept or reject
Notice that the Verifier does not talk back to Prover, i.e. it does not interact with it! It just reads the generated proof and that's all, making the entire thing non-interactive.
More formally, a NARK is a triple :
- is the preprocessing setup, generating public parameters for prover and verifier
- is the prover function, generating the proof given the public prover parameters, public inputs and the secret inputs (witness).
- is the verification function, either accepting or rejecting a given proof , along with the circuit's public verifier parameters and public inputs.
A technical point to be made here is that, all of these algorithms and the adversary are assumed to have an access to a random oracle. This is most likely due to Fiat-Shamir Paradigm we have learned in the previous lecture, but we will get to more details of this later.
Requirements of a NARK
There are 2 requirements of a NARK, and an optional 3rd requirement of zero-knowledgeness:
- Completeness: If the prover does indeed knows the argued knowledge, verifier should definitely accept the proof.
- Soundness: If the verifier accepts a proof, the prover should indeed know the argued knowledge. "Knowing" something is rather interesting to capture formally, but for now let's say there is an extractor algorithm that can extract a valid from the prover.
- Zero-knowledge (optional): The view of this interaction, consisting of "reveals nothing new" of .
Trivial NARK
We can easily think of a trivial NARK, that is not zero-knowledge but has the other two properties. Simply, the proof . Yeah, just send the witness to the verifier! All the Verifier has to do next is check if , since both and were public anyways.
SNARK: Succinct NARK
We will introduce some constraints over the proof size and verification time, giving us two types of NARKs:
- succint preprocessing NARK
- strongly succinct preprocessing NARK
Let us see the first one.
A succinct preprocessing NARK is a triple :
- is the preprocessing step, generating public parameters for prover and verifier
- is the prover function, where . So, the proof length must be less than linear in the size of witness.
- is the verification function, where . Note that the verification will have to read the public inputs, so it is allowed to run in time, but it must run sub-linear in the size of circuit .
In practice, we are even more greedy than this, so we have a much better and efficient type of NARK.
A strongly succinct preprocessing NARK is a triple :
- is the preprocessing step, generating public parameters for prover and verifier
- is the prover function, where . The proof length must be logarithmic to the size of circuit, making the proof very tiny compared to the circuit!
- is the verification function, where . Again, the verification will have to read the public inputs, so it is allowed to run in time, but it will not have time to read the entire circuit, which is quite magical. This is actually what public parameter is for, it is capturing a summary of the circuit for the verifier so that is enough to run the verification.
A zk-SNARK is simply a SNARK proof that reveals nothing about the witness .
Trivial SNARK?
Let us again come back to the trivial proof, where .
- Prover sends to the verifier.
- Verifier checks if
Why can't there be a trivial SNARK? Well, there may be several reasons:
- If is long, the proof size will be too large.
- If is taking lots of time, the verifier time will be too long.
- Naturally, we might want to keep secret.
Preprocessing Setup
We said that a preprocessing setup is done for a circuit . Things are actually a bit more detailed than this, there are 3 types of setups:
- Trusted Setup per Circuit: is a randomized algorithm. The random is calculated per circuit, and must be kept secret from the prover; if a prover can learn then they can prove false statements!
- Trusted Setup & Universal (Updatable): a random is only chosen once and is independent of the circuit. The setup phase is split in two parts: .
- is a one-time setup, done in a trusted environment. must be kept secret!
- is done for each circuit, and nothing here is secret! Furthermore, is a deterministic algorithm.
- Transparent: does not use any secret data, meaning that a trusted setup is not required.
SNARKs in Practice
Notice that we had no constraints on the proof generation time. In the recent years, prover time has been reduced to be in linear time with the size of circuit , and this kind of enabled the SNARK revolution we are seeing these past few years.
We will go into details of 4 categories of SNARKs throughout the lecture, and again all of these have provers that run in linear time .
Size of proof | Verifier time | Setup | Post-Quantum? | |
---|---|---|---|---|
Groth16 | ~200 B | ~1.5 ms | Truster per Circuit | No |
Plonk / Marlin | ~400 B | ~3 ms | Universal trusted setup | No |
Bulletproofs | ~1.5 KB | ~3 sec | Transparent | No |
STARK | ~100 KB | ~10 ms | Transparent | Yes |
The approximations here are made for a circuit that is size gates. There are many more SNARKs out there, but these four are the ones we will go into detail of.
Also note that some of these SNARKs have constant sized proofs and constant time verifiers, which is kind of awesome considering that no matter what your circuit is, the proof size and verifier time will be approximately the same!
Knowledge Soundness
While describing the properties of a NARK, we mentioned soundness:
Well, what does it mean to "know" here? Informally, knows if this can be somehow extracted from the prover . The way we do that is kind of torturing the until it spits out . Let us give the formal definition now.
Formally, an argument system is (adaptively) knowledge-sound for some circuit , if for every polynomial time adversary such that:
- for some non-negligible
there is an efficient extractor that uses as a black box (oracle) such that:
- for some negligible and non-negligible .
In other words, the probability that a prover can convince the verifier for some witness must be at most negligibly different than the probability that this witness is a valid witness for the circuit . In doing so, this witness must be extractable by the efficient extractor .
Building a SNARK
There are various paradigms on building SNARKs, but the general paradigm is made up of two steps:
- A functional commitment scheme, which is a cryptographic object
- A suitable interactive oracle proof (IOP), which is an information theoretic object
(1) Functional Commitment Scheme
Well, first, what is a commitment scheme? A cryptographic commitment is like a physical-world envelope. For instance, Bob can put a data in an envelope, and when Alice receives this envelope she can be sure that Bob has committed to whatever value is in it. Alice can later reveal that value.
The commitment scheme has two algorithms:
- for some randomly chosen
The scheme must have the following properties:
- Binding: cannot produce two valid openings for
- Hiding: reveals nothing about the committed data
There is a standard construction using hash functions. Fix a hash function where
Committing to a function
Choose a family of functions . The function can be an arithmetic circuit, a C program, whatever; but what does it really mean to commit to a function? Well, consider the following interaction:
sequenceDiagram actor P as Prover actor V as Verifier note over P: f ∈ F P ->> V: com_f := commit(f, r) V ->> P: x ∈ X P ->> V: y ∈ Y, proof π note over V: Accept or Reject
Here, the proof is to show that and . Also, is a commitment to function , but we may also use the notation to indicate a commitment (think of it like in an envelope).
Formally, a functional commitment scheme for is defined by the following:
- outputs public parameters .
- is commitment to with .
- this should be a binding scheme
- optionally, it can be hiding, which is good for a zk-SNARK
- with a prover and verifier , for a given and :
- (a short proof!),
- Basically, the system is a SNARK proof wof the relations: and and .
Four Important Functional Commitments
There are 4 very important functional commitment types:
- Polynomial Commitments: Committing to a univariate polynomial where that fancy notation stands for the set of all univariate polynomials of degree at most .
- Multilinear Commitments: Committing to a multilinear polynomial in which is the set of all the multilinear polynomials in at most variables, each variable with degree at most 1. Here is an example multilinear polynomial: .
- Vector Commitments: Committing to a vector which is a vector of elements. With our commitment, we would like to be able to open any cell at a later time, such that . An example vector commitment scheme is Merkle Trees, which you may have heard of!
- Inner-Product Commitments: Committing to a vector . Opening an inner product is done as . These are also known as Linear Product Arguments.
It turns out that for these 4 functional commitments, you can obtain any of these from any other.
Polynomial Commitment Scheme (PCS)
A PCS is a functional commitment for the family .
- The prover commits to a univariate polynomial , later, they can prove that:
- for some public
- . As this is a SNARK, the proof size and verifier time should be .
- The verifier has access to .
There are some example PCSs with different mechanisms:
- Using basic elliptic curves: Bulletproofs (short proof, but verifier time is )
- Using bilinear groups: KZG'10 (trusted setup), Dory'20 (transparent)
- Using groups of unknown order: Dark'20
- Using hash functions only: based on FRI (long eval proofs)
Trivial Commitment is bad!
What would be a trivial commitment scheme for a polynomial? Well, first realize that a polynomial is just . Then, our commitment will be:
- as in simply hashing the coefficients and some random variable.
- will be done as follows:
- prover will send to the verifier
- verifier will construct from the coefficients, and check if and .
This is problematic because the proof size and verification time are linear in , but we wanted a lot smaller values, such as .
Zero Test: A Useful Observation
We will now make a really useful observation, which is an essential part of SNARKs and is really what makes SNARKs possible!
Consider some non-zero polynomial with degree at most , shown as .
- for it holds that
We know that has at most roots. is chosen at random from a size , do the probability that "hits" a root value is easy to see that .
Now suppose that and . Then, is negligible! So it is really unlikely that a randomly chosen field element will be the root for .
With this in mind, if you do get for then is identically zero with very high probability. This gives you a simple zero test for a committed polynomial!
[Schwartz-Zippel-DeMillo-Lipton] lemma states that this observation holds for multivariate polynomials too, where is treated as the total degree of . The total degree is calculated as the sum of degrees of all variables, for example has degree .
Equality Test: A Following Observation
Following the zero-test observation, we can make another observation that allows to check if two polynomials are equal.
Let . For , if then with very high probability! This comes from the observation above, where if then with very high probability.
Here is an interactive protocol that makes use of this equality test, where a prover can commit to polynomials and show that they are equal:
sequenceDiagram actor P as Prover(f, com_f, g, com_g) actor V as Verifier(com_f, com_g) note over V: r ← R (random value) V ->> P: r note over P: y ← f(r) note over P: π_f := proof that y = f(r) note over P: y' ← g(r) note over P: π_g := proof that y' = g(r) P ->> V: y, π_f, y', π_g note over V: accept if π_f, π_g are valid and y=y' note over V: reject otherwise
That's cool and all, but wait, we talked about non-interactiveness the entire lecture; why are we making an interactive protocol right now? Well, here is the only interaction that a verifier makes to the prover. It is a "public coin", just some coin-toss (or a series of tosses) given by the verifier to the prover for everyone to see.
Thanks to Fiat-Shamir Transform, we can transform interactive protocols of this nature into non-interactive proofs! More specifically, Fiat-Shamir Transform can take a "public-coin interactive protocol" which means all verifier randomness is public, and transform it into a non-interactive protocol.
To be technical, Fiat-Shamir Transform isn't safe to transform ALL interactive proofs of this nature, but it is good enough for our needs right now.
Let be a hash function. For the example above, the prover will generate and this will be used as the random challenge. Since the verifier also has access to they can generate the same during verification. That is how the interactiveness is removed!
If is modeled as a random-oracle, and is negligible (as we discussed in zero-test), then this is a SNARK. In practice, SHA256 is used for the hash function.
Is this a zk-SNARK? No, because the verifier learns the result of evaluating the polynomials at point .
(2) - Interactive Oracle Proof
The goal of an -IOP is to boost a commitment to function to become a SNARK for general circuits. For example, you could have a polynomial function family and with -IOP you can turn that into a SNARK for any circuit with size .
Definition: Let be some arithmetic circuit. Let . An -IOP is then a proof system that proves . In other words, some prover knows a witness .
- Setup: where which are oracles of functions in the function family. These oracles can be though of as function commitments, where the verifier can ask to reveal a function result at some given value, equivalent to making an oracle request. Remember that we have seen setup procedures back when we discussed SNARKs!
- Interactive Proof: Proving that .
sequenceDiagram actor P as Prover P(pp, x, w) actor V as Verifier V(vp, x) note over P, V: claim: C(x, w) = 0 loop i = 1, 2, ..., (t-1) P ->> V: oracle [f_i ∈ F] note over V: r_i ← F_p V ->> P: r_i end P ->> V: oracle [f_t ∈ F] note over V: verify^(f_{-s}, ..., f_t)(x, r_1, ..., r_(t-1))
Let's digest what is happening in this interactive proof:
- The prover starts by sending an oracle for function . In practice, this is a commitment to function which we may show as .
- The verifier samples a uniformly random field element , and sends it back to the prover.
- Steps 1 and 2 happen for rounds.
- Finally, the prover sends one last oracle , an oracle for function .
- The verifier starts the verification process. This process has access to all oracles given by the prover, as well as all the generated randomness, and public inputs as well.
The IOP must have the following properties:
- Completeness: If there exists a valid witness known by the prover, the verifier should definitely accept the proof.
- Soundness: The second property is knowledge soundness (unconditional), meaning that a malicious prover can not convince a verifier that they know a witness such that . The way to prove that is using an extractor: this extractor is given the statement and functions in clear! Why in clear? Because, the commitments to those functions were SNARKs too and the extractor can extract the functions themselves from there too. The extractor must extract the witness from this process.
- Zero-knowledge (optional): The view of this IOP "reveals nothing new" of .
Example: Polynomial IOP for claim
We will go over an example where the public input is a set, and secret witness is a set that contains or is equal to . Furthermore, is a subset of or equal to the finite field for prime . Suppose we capture this relation with a circuit such that the claim becomes:
sequenceDiagram actor P as Prover P(pp, X, W) actor V as Verifier V(vp, X) note over P: compute f(Z), g(Z) note over V: compute g(Z) note over P: q(Z) := f / g P ->> V: oracles [f], [q] note over V: r ← F_p V ->> P: r note over V: query w ← f(r) note over V: query q' ← q(r) note over V: compute x ← g(r) note over V: accept if x * q' = w
I will explain how and are computed here, let's dig in.
- Prover computes two polynomials and , a polynomial with roots in and respectively. It does that by the following:
- Verifier computes the same way, because is public.
- Prover computes a quotient polynomial , which is a polynomial that is the result of dividing by . This is only a polynomial if has all the roots that has, and that implies . That is a key point to understand in this proof. Let me give an example: and . Then, 1. 2. 3. is a valid polynomial in the finite field!
- Prover sends oracles of and to the verifier. In practice, it uses a polynomial commitment scheme and sends commitments to these functions, and .
- Verifier samples a uniform random variable from the finite field. It sends this to the prover, but the prover makes no use of it. There is a reason why it sends anyways: it is to make public! If the verifier didn't send , we would not be able to say that it is publicly known.
- Verifier queries the value of and at point , and also computes . Denote these as respectively. Note that this querying happens via the polynomial commitment scheme in practice, so behind the scenes verifier sends to the prover, the prover evaluates it and sends back the result along with a proof that it is evaluated correctly and so on, check the previous section for this.
- Verifier checks if . This is only possible if indeed, think of it like checking in this example.
Replacing the oracles with commitments, and oracle queries with commitment interactions and so on is often called "compilation step", where this Poly-IOP is "compiled" into a SNARK by adding in the PCS (poly-commitment scheme) steps.
The IOP Zoo
There are many SNARKs for general circuits.
IOP | Commitment Scheme | Examples |
---|---|---|
Poly-IOP | Poly-Commit | Sonic, Marlin, Plonk |
Multilinear-IOP | Multilinear-Commit | Spartan, Clover, Hyperplonk |
Vector-IOP | Vector-Commit (e.g Merkle) | STARK, Breakdown, Orion |
You construct the IOP, and use the relevant commitment scheme to do the commitments and queries; et viola, you have a SNARK. However, the examples we have were interactive so far, but a SNARK is non-interactive. To do that final touch, you use the Fiat-Shamir Transform (using hash functions) to make the entire thing non-interactive.
SNARKs in Practice
flowchart LR D[DSL] -- compiler --> S[SNARK-friendly format] S -- pp, vp --> B[SNARK backend prover] X[x, witness] --> B B --> proof
In practice, you wouldn't want to write the entire circuit yourself. We use DSLs (domain-specific languages) to do that for us.
Some DSL examples are:
The DSL compiles the circuits for you, and outputs a SNARK friendly format. There are several formats:
- Circuit
- R1CS (Rank-1 Constraint System)
- EVM Bytecode (yea, that is possible!)
- …
Finally, with the public parameters , the public input and witness a SNARK backend prover generates a proof.
That is the end of this lecture!
- Programming ZKPs
- Recap: ZKP for a predicate
- Arithmetic Circuits
- Tutorial: Circom - Using a HDL for R1Cs
- Tutorial: Arkworks - Using a Library
- Tutorial: ZoKrates - Compiling Programs to Circuits
- Recap: The ZKP Toolchains
Programming ZKPs
Suppose you have an idea for an application & you want to use ZK in it. What do you do?
flowchart TD subgraph this lecture idea --program--> p[program] p --compile--> c[circuit/constraint-system] end c --setup--> pp[public params] pp --prove--> zkp[ZK-proof] pp --> verify zkp --> verify verify --> out[accept/reject]
In this lecture, we will be doing the following:
- Have a big picture on ZKP programmability
- Example: Use an HDL (hardware-description language), such as Circom
- Example: Use a library, such as Arkworks
- Example: Use a programming language & compiler, such as ZoKrates
- Overview of prominent ZKP toolchains
Recap: ZKP for a predicate
Let us remember what ZKP does. Suppose you have a predicate , with some public inputs and private inputs (witness) . For example, I know a such that .
- Prover has access to .
- Verifier has access to .
- Proof will prove that holds, without revealing .
However, the key question here is: what could be? What are some other examples? In theory, can be any NP problem statement.
- is factorization of integer
- is the private key that corresponds to some public key
- is the credential for account
- is a valid transaction
However, transferring these statements into the programming side of things are a bit different.
Arithmetic Circuits
In practice, may be an "arithmetic circuit" over inputs and .
Think of Boolean Circuits that you see in electronic classes or circuit design classes, perhaps you have taken one during your undergrad studies. Well, we had AND gates, OR gates, NAND gates and such there, where the operations were happening on 1s and 0s.
In an Arithmetic Circuit, the operations happen on elements that belong to a finite field of order , shown as . Usually, is a large prime number (e.g. ~255 bits). Essentially, an Arithmetic Circuit can be represented by polynomials, for example we could have:
However, there is a much more nice way of thinking about circuits: treat them as a DAG (Directed Acyclic Graph)! In this DAG:
- Nodes (or Vertices) are inputs, gates, and constants.
- Edges are wires/connections.
Here is the circuit for the two polynomials above, visualized as a DAG:
flowchart LR w0((w_0)) --> x1[x] w0 --> x1[x] x1 --> x2[x] w0 --> x2[x] w1((w_1)) --> x3[x] w1 --> x3[x] x --> =2 x2 --> =1[=] x((x)) --> =1 x3 --> =2[=]
Rank-1 Constraint System (R1CS)
R1CS is a format for ZKP Arithmetic Circuit (AC). It is a very commonly used format. Here is how it is defined:
- is a set of field elements .
- is a set of field elements
- is made up of equations with the form where are affine combinations of variables mentioned in the above bullet points.
Let's see some examples of .
- is okay.
- is okay.
- is NOT okay! You can't have two multiplications like that here! So, what can we do? We could capture this operation with the help of an extra variable, let's say :
- is okay.
- is okay, and these two together capture the equation above.
Matrix Definition of R1CS
There is another way of looking at R1CS, using matrices. This time, we define as follows:
- is a vector of field elements.
- is a vector of field elements.
- is made up of 3 matrices:
Now, we define a vector which has elements. The rule for this system is that the following equation must hold:
Here, means the element-wise product of these.
┌───────┐┌┐ ┌───────┐┌┐ ┌───────┐┌┐
|.......||| o |.......||| = |.......||| //--> every row here corresponds to
| A |└┘ | B |└┘ | C |└┘ // some rank-1 constraint!
| | | | | |
└───────┘ └───────┘ └───────┘
Example: Writing R1CS of an AC
Consider the following AC:
flowchart LR w0((w_0)) --> m1[x] w1((w_1)) --> m1 w1 --> m2 x0((x_0)) --> a1 m1 --w_2--> a1[+] x0 --> m2[x] a1 --w_3--> = m2 --w_4--> =
Here, we have a public input and two secret inputs (witnesses) . The first thing we have to do is capture the intermediate outputs, and we do that by assigning them secret input variables; in this case these would be . Then, we simply write equations in the form as discussed before, as one equation per gate!
- (notice that left side is actually )
As simple as that.
Tutorial: Circom - Using a HDL for R1Cs
First thing to note is that Circom is NOT a Programming Language (PL), it is a Hardware Description Language (HDL).
Programming Language | Hardware Description Language | |
---|---|---|
Objects | Variables, Operations, Program & Functions | Wires, Gates, Circuit & Sub-circuits |
Actions | Mutate variables, Call functions | Connect wires, Create sub-circuits |
There are some known HDLs for Digital Circuits:
- Verilog
- SystemVerilog
- VHDL
- Chisel
Circom is not an HDL for digital circuits, it is an HDL for R1CS. Wires make the R1CS variables and gates make the R1CS constraints. In essence, Circom does 2 things:
- Sets variable values
- Creates R1CS constraints
Example:
Let's go over a basic example:
template Multiply(){
signal input x; // private, unless explicitly stated public
signal input y; // private, unless explicitly stated public
signal output z; // output is always public
z <-- x * y;
z === x * y;
// z <== x * y; would work too
}
// to start execution, a main component is required
// multiple mains can't exist in a code!
component main {public [x]} = Multiply();
// ^ explicitly state x to be public!
Let's analyze what is happening here:
- A
template
is just a circuit (or a sub-circuit if imported by some other) - A
signal
is a wire, can beinput
,output
or just some intermediate variable. <--
operation sets signal values.===
creates a constraint, which must be Rank-1. So, one side is linear and other is quadratic. You can't do things likex * x * x
because is not quadratic.- As a shorthand,
<==
does both at once in a single line instead of two lines. - You can also have
-->
and==>
which work in a similar way.
Example: where
Now a bit more complicated example.
template RepeatedSquaring(n){
signal input x; // private, unless explicitly stated public
signal output y; // output is always public
// intermediate signals
signal xs[n+1];
xs[0] <== x;
for (var i = 0; i < n; i++) {
xs[i+1] <== xs[i] * xs[i];
}
y <== xs[n];
}
// provide template value n = 1000
component main {public [x]} = RepeatedSquaring(1000);
// ^ explicitly state x to be public!
Circom has very nice capabilities as demonstrated here!
- You can have template arguments such as
n
here, that you hard-code when you are instantiating the component. - You can have arrays of signals.
- You can have variables (defined with
var
). These are different from signals, they are mutable & are evaluated at compile time. - You can have loops, such as the good ol'
for
loop. - You can also have
if
-else
statements. - You can access index
i
in an array witharr[i]
.
Example: Non-zero & Zero
template NonZero(n){
signal input in;
signal inverse;
inverse <-- 1 / n; // not ok with R1CS
1 === in * inverse; // is ok with R1CS
}
template IsZero() {
signal input a;
signal input b;
component nz = NonZero();
// check a is non-zero
nz.in <== a;
// b must be 0 for this to hold
0 == a * b;
// you could have done this much simpler as:
// 0 === b;
// but hey, this is an educational example! :)
}
component main {public [a, b]} = IsZero();
Here, NonZero
is a sub-circuit used by IsZero
. Within NonZero
, we are checking if some input is not 0. However, constraints only check for equality, we don't have something like a !=== b
. To check if something is non-zero, we can check if it has an inverse!
To do that, we do inverse <-- 1 / n
but hey, this isn't R1! Is that a problem? Well, <--
is just an assignment operator, not a constraint! So, we can do such a thing here; in fact, signal assignment without constraints are a lot more capable than constrainted assignments. The constraints itself is in the next line: 1 === in * signal
, which is R1.
Also notice that IsZero
uses NonZero
within, and it does that by instantiating the sub-circuit as nz
. You can access the signals in a circuit with .
operator, such as nz.in
.
Example: Sudoku Solution
This one is a rather large example, with quite a lot of code too. I will just take notes of the circuit, for the code itself please go to https://github.com/rdi-berkeley/zkp-course-lecture3-code/tree/main/circom.
We would like to prove that we know the solution to a sudoku puzzle.
- The public input will be the initial setting of the sudoku board, with 0 for empty cells and some integer for non-empty cells.
- The private input (witness) will be our solution, again as an array of numbers.
- Our predicate is that we know the solution to the given Sudoku setting in the public input.
The inputs will be given as 2-dimensional arrays of size . We should really like to write a generic template circuit that takes the board size as template argument.
For now, let's do an example for . What will be our constraints though? Let's list them one by one:
- The solution input should be composed of numbers in range .
- The solution input should have rows where every numbers occurs only once.
- The solution input should have columns where every numbers occurs only once.
- The solution input should have groups of cells (as in Sudoku) where every number occurs once in each group.
Here is the circuit, along with it's sub-circuits.
// Assert that two elements are not equal.
// Done via the check if in0 - in1 is non-zero.
template NonEqual() {
signal input in0;
signal input in1;
// do the inverse trick to check for zero
signal inverse;
inverse <-- 1 / (in0 - in1);
1 === (in0 - in1) * inverse;
}
// Assert that all given values are unique
template Distinct(n) {
signal input in[n];
// create a non-equal component for each pair
component neq[n][n];
for (var i = 0; i < n; i++) {
for (var j = 0; j < i; j++) {
neq[i][j] = NonEqual();
neq[i][j].in0 <== in[i];
neq[i][j].in1 <== in[j];
}
}
}
// Assert that a given number can be represented in n-bits
// Meaning that it is in range [0, 2^n).
template Bits(n) {
signal input in;
signal bits[n];
var bitsum = 0;
for (var i = 0; i < n; i++) {
bits[i] <-- (in >> i) & 1;
bits[i] * (bits[i] - 1) === 0; // ensure bit is binary
bitsum += bitsum + 2 ** i * bits[i];
}
bitsum == in;
}
// Check if a given signal is in range [1, 9]
template OneToNine() {
signal input in;
component lowerbound = Bits(4);
component upperbound = Bits(4);
lowerbound.in <== i - 1; // will work only if i >= 1
upperbound.in <== i + 6; // will work only if i <= 9
}
// Main circuit!
template Sudoku(n) {
signal input solution[n][n];
signal input puzzle[n][n];
// first, let's make sure everything is in range [1, 9]
component inRange[n][n];
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
inRange[i][j] = OneToNine();
inRange[i][j].in <== solution[i][j];
}
}
// then, let's make sure the solution agrees with the puzzle
// meaning that non-empty cells of the puzzle should equal to
// the corresponding solution value
// other values of the puzzle must be 0 (empty cell)
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
// this is valid if puzzle[i][j] == 0, OR
// puzzle[i][j] == solution[i][j]
puzzle[i][j] * (puzzle[i][j] - solution[i][j]) === 0;
}
}
// ensure all the values in a row are unique
component distinctRow[n];
for (var row = 0; row < n; row++) {
distinctRow[row] = Distinct(9);
for (var col = 0; col < n; col++) {
distinctRow[row].in[col] <== solution[row][col];
}
}
// ensure all the values in a column are unique
component distinctColumn[n];
for (var col = 0; col < n; col++) {
distinctColumn[col] = Distinct(9);
for (var row = 0; row < n; row++) {
distinctColumn[col].in[row] <== solution[row][col];
}
}
// ensure all the values in each 3x3 square is unique
// left as an exercise to the reader :)
}
component main{public[puzzle]} = Sudoku(9);
That is very cool, right?
So yea, Circom is great and it has direct control over constraints. However, using a custom language has it's own drawbacks. An alternative is to use an already known high-level language (e.g. Rust, Go) and have a library to help you write circuits in there.
Tutorial: Arkworks - Using a Library
The most important object in a library will be the constraint system. This guy will keep state about R1CS constraints and variables, and we will interact with it while we write our "circuit".
The key operations here will be:
- Creating a variable
cs.add_var(p, v) -> id;
// cs: constraint system
// p: visibility of variable
// v: assigned value
// id: variable handle
- Creating a linear combination of variables
// make an empty linear combination at first
lc := cs.zero();
// now fill it with variables
lc.add(c, id) -> lc';
// id: variable handle from before
// c: coefficient
// this correspod to the following linear combination:
// lc' := lc + c * id
- Adding a constraint
// suppose you have some linear constraints lc_A, lc_B, lc_C
cs.constraint(lc_A, lc_B, lc_C)
// adds a constraint lc_A * lc_B = lc_C
These are pretty high-level, so let's take a look at a more realistic example.
fn and(cs: ConstraintSystem, a: Var, b: Var) -> Var {
// do a simple bitwise AND on values
let result = cs.new_witness_var(|| a.value() & b.value());
// constraint: a * b = result, works like AND in booleans
self.cs.enforce_constraint(
lc!() + a,
lc!() + b,
lc!() + result,
);
result // return new result as Var
}
This is cool and all, but it has quite a bit of boilerplate, and seems very tedious & error-prone. So, we would really like a language abstraction somehow, making the library a lot more friendly.
Here is an example, where we can write the same code but apply it in a Boolean
struct and overload the and
operator.
struct Boolean { var: Var };
impl BitAnd for Boolean {
fn and(self: Boolean, other: Boolean) -> Boolean {
// do the same code above...
Boolean { var: result } // return result wrapped in Boolean
}
}
// later in code, you can do stuff like this:
let a = Boolean::new_witness(|| true);
let b = Boolean::new_witness(|| false);
There are many different libraries:
- libsnark: gadgetlib (C++)
- arkworks: r1cs-std + crypto-primitives (Rust)
- Snarky (OCaml)
- GNARK (Go)
- Bellman (Rust)
- PLONKish (Rust)
At this point in lecture, we have an Arkworks tutorial. Please see the lecture itself for that, I will be omitting this part.
Tutorial: ZoKrates - Compiling Programs to Circuits
In the Circom example, we wrote the circuit ourselves. In the Arkworks example, we used a nice high-level language but still had to explicitly specify the wiring and constraints. What if we could have a programming language, that takes in a program and compiles it to R1CS with all it's wires and constraints?
Meet ZoKrates, a tool that does what we have just described.
type F = field;
def multiplication(public F x, private F[2] ys) {
field y0 = y[0];
field y1 = y[1];
assert(x = y0 * y1);
}
def repeated_squaring<N>(field x) -> field {
field[N] mut xs;
xs[0] = x;
for u32 i in 0..n {
xs[i + 1] = xs[i] * xs[i];
}
return xs[N];
}
def main (public field x) -> field {
repeated_squaring::<1000>(x);
}
ZoKrates has quite a bit of capabilities:
- Custom types via structs
- Variables that contain values during execution/proving
- Visibility is annotated (private/public)
assert
creates constraints- Integer generics
<N>
- Arrays & array accesses
- Variables, which are mutable unlike signals
- Fixed-length loops
- If-else statements
I am omitting the example from this page, please see the lecture for the code.
Recap: The ZKP Toolchains
We have seen that there are generally 3 options:
- HDL: A language for describing circuit synthesis.
- pros: clear constraint & elegant syntax
- cons: hard to learn & limited abstraction
- Library: a library for describing circuit synthesis
- pros: clear constraint & as expressive as it's host language
- cons: need to know that language & few optimizations
- PL + Compiler: a language, compiled to a circuit
- pros: easiest to learn & elegant syntax
- cons: limited witness computation
Is NOT standalone language | Is a standalone language | |
---|---|---|
Circuit | Library (Arkworks) | HDL (Circom) |
Program | PL (ZoKrates) |
Finally, note that all of these tools essentially output an R1CS, or more specific types of it like Plonk or AIR. So, within that process, all these tools share quite a bit of common techniques. With that in mind, a library to create ZKP languages actually exists: Circ.
You can also check out https://zkp.science/ which has a great coverage of tools, as well as the development of ZK theory.
- SNARKS via IPs
- Interactive Proofs: Motivation & Model
- Trivial SNARK is not a SNARK
- Functional Commitment Schemes
- Recall: SZDL Lemma
- Low-Degree & Multilinear Extensions
- The Sum-Check Protocol
- SNARK for Circuit-Satisfiability
SNARKS via IPs
A SNARK stands for a succinct proof that a certain statement is true. Succinct here is meaning that the proof is "short". For example, I have a statement:
- I know an such that .
In SNARK, the proof should be short and fast to verify. A trivial proof of the above statement is to simply send to the verifier. However, that proof is not short; it is as big as . Verification is also not fast, as the verifier has to hash the entire message to actually see the proof.
A SNARK can have a proof size of few KBs and verification should take at most seconds.
Interactive Proofs: Motivation & Model
First, we will see what Interactive Proofs (IP)s are and how they differ from a SNARK. Then, we will look at building a SNARK using the IPs.
In an interactive proof, there are two parties: a prover and a verifier .
- solves a problem (has some claim), and tells the answer (proves the claim) to .
- Then, they start to have a conversation. 's goal is to convince that the answer is correct.
sequenceDiagram actor P as Prover actor V as Verifier note over P, V: claim x loop i = 1, 2, ... P ->> V: answer_i V ->> P: question_i end note over V: accept/reject
There are two requirements to this:
- Completeness: an honest can convince to accept.
- (Statistical) Soundness: If is dishonest, then will catch this with very high probability. In other words, it is negligibly probable that a dishonest can convince .
- Note that this must hold even if is computationally unbounded, and is actively trying to fool .
- If soundness holds only against polynomial-time , then the protocol is actually called an interactive argument, not an interactive proof.
Soundness vs. Knowledge Soundness
With that, we must make note on the different between "soundness" and "knowledge soundness". In a previous lecture by Prof. Boneh, we have talked about knowledge soundness in particular.
So, now let us think of a circuit satisfiability case. Let be some public arithmetic circuit
where is some public statement and is some secret witness. Let us look at the types of "soundness" with this example:
- Soundness: accepts
- Knowledge soundness: accepts "knows"
As we can see, knowledge soundness is "stronger" than soundness, the prover MUST know the existing witness.
However, soundness itself can be valid in some cases even when knowledge soundness has no meaning. This is usually in cases where there is no "natural" witness. For example, can claim that the output of a program given by on the public input is 42. Well, witness is not used in the program, so there is really nothing to "know" here.
The vice-versa is true too, where knowledge soundness means something but you don't really care about soundness. This is usually in cases where the soundness is trivial. For example, knows the secret key to some Bitcoin account. Well, there does exist a private key to that account for sure. In a "sound" protocol, the verifier could just say "yep, can't argue with that" and accept, without breaking soundness itself.
- SNARK's that don't have knowledge soundness are called SNARGs, they are studied too!
Public Verifiability
Interactive proofs and arguments only convince the party that is choosing/sending the random challenges, which is bad if there are many verifiers and prover must interact with each of them separately.
Thankfully, we have something called Fiat-Shamir Transform [Fiat, Shamir'87], where a public-coin protocol (an IP where randomness is public) can be made public & non-interactive! The trick is to use a random oracle model (via a hash function in practice) to generate the required randomness on your own.
So, in summary:
Interactive Proofs | SNARKs |
---|---|
Interactive | Non-Interactive |
Information Theoretically Secure (aka Statistically Secure) | Computationally Secure (?) |
Not necessarily Knowledge Sound | Knowledge Sound |
Trivial SNARK is not a SNARK
What is the trivial way to prove that you know some such that ? Well, you could just send right? This has two problems, both against the "succinctness" of a SNARK:
- could be large 🔴
- computing could take a lot of time 🔴
- actually non-interactive when you think about it 🟢
Slightly trivial SNARKs from Interactive Proofs (IPs)
Let us look at the trivial proof from an interactive proof perspective (making it slightly less trivial). Now, the prover will send to the verifier, and somehow convince that the sent satisfies .
- w could still be large 🔴
- the verification is a lot faster, verifier is not computing directly! 🟢
- interactive 🔴
Note that since is sent to the verifier, the supposedly secret witness is no more secret.
Actual SNARKs!
What actually happens in a SNARK is that, instead of sending explicitly, the prover will cryptographically commit to and send that commitment. Again, an IP is used to convince that the committed satisfies .
In doing so, the prover will reveal just enough about the committed to allow the verifier to run its checks in the interactive proof.
- commitment of is succinct 🟢
- verification is fast 🟢
- seems interactive, but can be made non-interactive using Fiat-Shamir transform. The trick there is to use a cryptographic hash function as a source of randomness 🟢
Functional Commitment Schemes
We had talked about some very important functional commitment schemes:
- Polynomial Commitments: Committing to a univariate polynomial where that fancy notation stands for the set of all univariate polynomials of degree at most .
- Multilinear Commitments: Committing to a multilinear polynomial in which is the set of all the multilinear polynomials in at most variables, each variable with degree at most 1. Here is an example multilinear polynomial: .
- Vector Commitments: Committing to a vector which is a vector of elements. With our commitment, we would like to be able to open any cell at a later time, such that . Merkle Tree is an example of vector commitment scheme.
Merkle Tree
Merkle Tree is a very famous vector commitment scheme, and we will look a bit deeper to that. Here is a vector commitment to the vector [m, y, v, e, c, t, o, r]
.
flowchart BT h2 --> h1 h3 --> h1 h4 --> h2 h5 --> h2 h6 --> h3 h7 --> h3 m --> h4 y --> h4 v --> h5 e --> h5 c --> h6 t --> h6 o --> h7 r --> h7
In this binary tree, every node is made up of the hash of its children:
- and so on…
The leaf nodes are the elements of the committed vector, m
, y
, v
, and such. The root is the commitment to this vector!
When the prover is asked to show that indeed some element of the vector exists at some position, it will provide only the necessary nodes. For example, a verifier could ask "is there really a t
at position 6?". The prover will give: c
, t
, and . The verifier will do the following:
Then, the verifier will compare the calculate to the root given as a commitment by the prover. If they match, then t
is indeed at that specific position in the committed vector! The way this cryptographically works is due to collision resistance in hash functions, more detailed explanation can be found in the video.
In summary, a Merkle Tree works as follows:
- The root is the commitment to the vector.
- The reveal a value in the commitment (which is a leaf in the tree) prover does the following:
- Send sibling hashes of all nodes on root-to-leaf path.
- Verifier checks if the hashes are consistent with the root hash.
- The size of this proof to reveal a value is hash values.
- This is a binding scheme: once the root hash is sent, the committer is bound to the committed vector.
- Opening any leaf to two different values requires finding a hash collision, assumed to be intractable.
Example: Committing to a univariate
Let us think about the [m, y, v, e, c, t, o, r]
commitment example above. Suppose that you have a polynomial so this polynomial has values defined over a very small . The degree should be small too, say something like .
To commit to this polynomial, the prover could simply commit to the following vector:
Here, is just some dummy value.
flowchart BT h2 --> h1 h3 --> h1 h4 --> h2 h5 --> h2 h6 --> h3 h7 --> h3 f0 --> h4 f1 --> h4 f2 --> h5 f3 --> h5 f4 --> h6 f5 --> h6 f6 --> h7 * --> h7
Basically, the prover committed to all evaluations of the polynomial. The verifier can ask for some specific evaluation, by asking to reveal some position in the tree (for example is at the third leaf).
Well, is this really a good method? No, it has quite huge problems actually.
- First of all, there are nodes in this tree. Evaluating that many elements for large like is a nightmare. We would instead want to have some total evaluation time proportional to the degree bound .
- Speaking of degree, notice that the verifier has no idea if indeed the committed polynomial has degree at most .
We will see ways to solve these problems within the lecture!
Recall: SZDL Lemma
In our previous lectures, we have touched upon a very important fact: for some univariate polynomial what is the probability that for some ? Well, if it is degree then it has roots, meaning that there are exactly points where evaluates to 0. How many total points are there? The answer is . So in short:
For very large and small this probability becomes negligible; meaning that you can't really come up with some random field element and find that , it is a tiny probability. Following on this "zero-test" fact, you can obtain an "equality-test" with the same reasoning:
So if you have two polynomials and they both evaluate to the same thing, chances are they are the same polynomial!
Schwarts-Zippel-Demillo-Lipton Lemma is a multi-variate generalization of this fact. Let be -variate polynomials of total degree at most . Total degree refers to the maximum sum of degrees of all variables in any term, for example has a total degree due to the first term. The lemma states that:
The reason we mention SZDL in particular is that:
- interactive proofs tend to make use of multivariate polynomials rather than univariate polynomials.
- Instead of having a univariate polynomial with a large degree , you can have a multivariate polynomial with a smaller degree which in turn reduces the proof size and makes things much more efficient.
Low-Degree & Multilinear Extensions
We now have some math to do, but do not fear; it will be quite useful!
Definition [Extension]: Given a function , a -variate polynomial over is said to extend if .
Definition [Multilinear Extension]: Any function has a unique multilinear extension (MLE) denoted .
- Multilinear means the polynomial has degree at most 1 in each variable. For example, is multilinear, but is not.
Example:
Let us think of some function defined over the domain .
Here is the multilinear extension for , shown as which is:
You can check that for it holds that . This multilinear extension is obtained using Lagrange Interpolation, we may get to that later.
Are there other extensions? Well, we have said that multilinear extension is unique, but there are other non-multilinear extensions of . For example:
also works for the inputs in , but it is a quadratic extension (total degree is 2).
Relation to Interactive Proofs
The important fact we must realize about multilinear extensions is the following: consider some functions defined over . Both of these functions have unique MLE's . The cool thing is: if there are any disagreeing inputs such that their evaluations on and are not equal, then the MLEs of these functions will disagree on almost all the points within their domain!
You might think of how the hash of an input changes drastically even if the input is changed slightly. This kind of resembles that, if the two functions have different evaluations on the set of points that they are defined on, then the MLE will have many many different evaluations on a lot of points.
The multilinear extensions "blow up & amplify" the tiny differences between , so that you can see the resulting extreme differences in the extensions .
Quick Evaluation of MLEs
Given as input all evaluations of a function , for any point there is an -time algorithm for evaluating the MLE .
The trick is using Lagrange Interpolation. For every input , define the multilinear Lagrange basis polynomial as follows:
It can be shown that you can get the evaluations of using these:
For each the result can be computed with field operations. As such, the overall algorithm for points takes time . Using dynamic programming, this can be reduced to .
The Sum-Check Protocol
We will now examine a seminal work [Lund-Fortnow-Karloff-Nissan'90], known as the sum-check protocol.
We have a verifier with oracle access to some -variate polynomial over field . The goal of this verifier is compute the quantity:
If you look closely, this sum is actually sum of all evaluations of in . In the naive method, the verifier would query each input, and find the sum in a total of queries. We will consider this to be a costly operation.
Instead, a prover will compute the sum and convince a verifier that this sum is correct. In doing so, the verifier will make only a single query to the oracle! Let's see how. Denote as prover and as verifier.
- Start: sends the claimed answer . The protocol must check that indeed:
- Round 1: sends univariate polynomial claimed to equal (H standing for honest):
This sum is basically almost , but instead of we use the variable . Since the entire thing is a sum, and is the only variable; this whole thing is a univariate polynomial.
- Round 1 Check: now checks that , basically filling in the missing sums for .
- If this check passes, then can now believe that is the correct answer so long as . Well, how can we check that ?
- Remember that if two polynomials agree at a random point, they are highly likely to be equal! So, picks a random point and checks that .
- Calculating is easy for the verifier, it's just some univariate polynomial with a not-so-high degree. However, the verifier does not know .
- Recursion into Round 2: If you look at the form of , it looks a lot like the sum . So, you can think of doing the same operations for and then do the entire thing to verify the sum .
- Recursion into Rounds 3, 4, …, : The verifier and prover keep doing this until the last round.
- Final Round (Round ): Like before, sends univariate polynomial claim to equal which is:
- Final Round Check: now checks that .
- Again, if this check passes must make sure that . However, we don't have to recurse anymore!
- Notice that is just a single query to the . So, can pick a random point and immediately query the oracle to find .
- No need for anymore rounds, just a single oracle query was enough.
Analysis
- Completeness: This holds by design, if prover sends the prescribed univariate polynomial in each round, then all of verifier's checks will pass.
- Soundness: If the prover does not send the prescribed messages, then the verifier rejects with probability at least where is the maximum degree of in any variable.
- For example, will make this probability which is tiny.
- You can prove this by induction on the number of variable , see the video for the proof.
- Cost: Total communication is field elements.
- sends messages with each being a univariate polynomial of degree at most .
- sends messages, each being a random field element.
- runtime is and runtime is , here is the time required to evaluate at one point.
Application: Counting Triangles in a Graph
To demonstrate how sum-check protocol can be applied, we will look at an interactive proof about counting triangles in a graph.
- Given Input: , representing the adjacency matrix of a graph.
- Desired Output: which counts the triangles, as if all three points are 1 (meaning that there is an edge) then the term is counted, but if there is only a single 0 there the term is ignored.
- Fastest known algorithm runs in matrix-multiplication time, currently about .
The protocol works as follows:
- Interpret the matrix matrix as if it's a function . The video has a great example showing how this works. Basically, to see what value a cell within the matrix contains, you evaluate the function with the respective inputs.
- Remember SZDL lemma, meaning that there is a unique multilinear extension for that function .
- Define the polynomial .
- Apply the sum-check protocol to to compute:
How much is the cost of this protocol?
- Total communication is .
- Verifier runtime is , which is linear in the size of matrix. This runtime is dominated by evaluating in the final round of the sum-check protocol.
- Prover runtime is .
SNARK for Circuit-Satisfiability
Let us get to the highlight of this lecture: how to use all this knowledge for circuit satisfiability? Recall that in this problem we have an arithmetic circuit over of size and output . The prover claims to know a witness such that . For simplicitly, let's take the public input to be empty.
Transcript
We will use a notion of transcript, which is defined as an assignment of a value to every gate in the circuit. A transcript is a correct transcript if it assigns the gate values obtained by evaluating the circuit on a valid witness .
Consider the circuit below:
flowchart BT a_1((a_1)) --> X1[x] a_1 --> X1[x] a_2((a_2)) --> X2[x] a_2 --> X2[x] a_3((a_3)) --> X3[x] a_3 --> X3[x] a_4((a_4)) --> X4[x] a_4 --> X4[x] X1 --> A1[+] X2 --> A1[+] X3 --> A2[+] X4 --> A2[+] A1 --> A3[+] A2 --> A3[+]
A correct transcript for this circuit yielding output 5 would be the following assignment:
flowchart BT a_1((1)) --> X1[1] a_1 --> X1 a_2((0)) --> X2[0] a_2 --> X2 a_3((2)) --> X3[4] a_3 --> X3 a_4((0)) --> X4[0] a_4 --> X4 X1 --> A1[1] X2 --> A1 X3 --> A2[4] X4 --> A2 A1 --> A3[5] A2 --> A3
Remember the trick of viewing a matrix as a function back in the "counting triangles" example? Well, we can do a similar trick for transcripts too!
A transcript can be viewed as a function . Assign each gate in a -bit label and view as a function mapping gate labels to . Basically, by giving the correct gate label to this function you can select a value at the circuit transcript, something like for the example above.
Polynomial-IOP for SNARK
Recall that our SNARK is all about proving that we know a secret witness such that for some public input and arithmetic circuit it holds that . Denote the circuit size as .
- First, we will construct the correct transcript of , which we denote as . We have talked about how this happens in the previous section.
- Prover will calculate the extension of to obtain a polynomial . This extension is the first message sent to the verifier.
- The verifier needs to verify that this is indeed true, but it will only make a few evaluations of in doing so.
We have talked about why using extensions was a good idea for this kind of proof. Remember that if there is even just a single tiny error in the transcript, the extension of this transcript will disagree on almost all points with respect to the correct transcript.
Alright then, how do we do it?
Step 1: Moving from to
First, we will construct a -variate polynomial such that: extends a correct transcript if and only if . To evaluate for any , it should suffice to evaluate at only 3 inputs.
As a sketch of the proof, define as the following:
We have two new functions here, let's just quickly introduce what they are:
- is a multilinear extension of a wiring predicate of a circuit, which returns 1 if and only if is an addition gate and it's two inputs are gates and .
- is a multilinear extension of a wiring predicate of a circuit, which returns 1 if and only if is a multiplication gate and it's two inputs are gates and .
With this definition, notice what happens:
- If then . For this to be zero, is required.
- If then . For this to be zero, is required.
- Otherwise, .
As such, if the addition and multiplications in the extension behave correctly with respect to the correct transcription , then the sum of evaluating the points on should be 0. As a further note, in structured circuits (circuits with repeating structure & wiring) the computation of and can be made a bit more efficient.
What we accomplish by doing this is the following: the original claim is that extends a correct transcript . This is quite a complicated thing to show per se, there may be many things going on with . on the other hand requires a more simpler structure, just check if the result is 0 for all the inputs.
Note that is sometimes referred to as boolean hypercube within the lecture. This is because is a boolean hypercube (specifically the corners of the hypercube can be labeled as the elements of this set) and we want to vanish over variables using this hypercube.
Step 2: Proving
So, how can the verifier check that indeed ? In doing so, verifier should only evaluate at a single point!
Using a Quotient Polynomial: Imagine for a moment that were a univariate polynomial . In that case, this would be defined over some subset and we would want to check that .
There is a well-known result in polynomials that will be very useful here: if and only if it is divisible by the vanishing polynomial for . The vanishing polynomial is defined as :
The polynomial IOP will work as follows:
- sends a polynomial such that .
- verifies this by picking a random and checking .
This approach is not really the best approach though; it has problems.
- First of all, is not univariate, it is obviously -variate.
- Having the prover find and send the quotient polynomial is expensive.
- In the final SNARK, this would mean applying polynomial commitment to additional polynomials, increasing the cost.
Well, we say that there are problems but this approach is actually used by well-known schemes: Marlin, Plonk and Groth16.
Using Sum-Check Protocol: An alternative approach for this step, which we have been foreshadowing throughout this lecture, is the sum-check protocol!
Sum-check handles multi-variate polynomials, and it doesn't require to send additional large polynomials. The sum-check we are interested in is the following:
To capture the general idea, we are working with integers instead of finite field here. When we square the result like that, the entire sum is zero if and only if is zero for all inputs.
- In the end, the verifier will only compute for some random inputs, and it suffices to compute for that.
- Outside of these evaluations, runs in time
- performs field operations given a witness .
That concludes this rather dense lecture! Don't be discouraged if you didn't understand the entire thing, I don't think any of us can really get it in a single run.
- Recall: Polynomial Commitments
- KZG Poly-commit Scheme
- Dory Poly-commit Scheme
- PCS to Commit to a Vector
- Proving Properties of Committed Polynomials
- PLONK
Recall: Polynomial Commitments
We will use polynomial commitments in this lecture, so let's quickly recall what they are!
- The prover would like to commit to some polynomial .
- An function uses evaluate some values for this polynomial, without revealing it. For example, pick some public .
- Prover will convince that and .
- Verifier will only know and a polynomial commitment , also shown as sometimes.
- The proof size for and the verifier time should both be in . Spoilers: it will turn out be constant which is really a magical thing to me.
KZG Poly-commit Scheme
In this lecture, we will use KZG [Kate-Zaverucha-Goldberg'10] polynomial commitment scheme.
Fix some finite cyclic group of order . This group basically has some generator value and the group consists of it's multiplications:
The group has addition operation defined on it, where you can add to obtain where .
Trusted Setup:
KZG starts with a trusted setup to produce public parameters. This is done as follows:
- Sample some random .
- Compute . Basically, you have group elements, each multiplied to some power of tau () and multiplied by . These computed values will be the public parameters .
- Finally and most importantly, delete . If this number is leaked and in wrong hands, they can create fake proofs! This is why the setup must take place in a trusted environment. We will actually see a better way for this setup, where multiple parties will take place in the ceremony and it suffices for only one of them to be trusted!
Commitment:
A commitment will take the public parameters along with the polynomial to be committed, and produces the commitment.
- The commitment is shown as
- Our commitment will be .
But wait, was deleted after setup so how do we obtain this? Well, think of the polynomial as follows:
Notice that for every