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 pullrequest 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 zeroknowledge 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 zeroknowledge 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, SchwartzZippel lemma, Sumcheck protocol and much more.

The PLONK SNARK: In this lecture we will first see KZG polynomial commitments, and then talk about useful proofgadgets on committed polynomials. Finally, we learn PLONK.

Polynomial Commitments using Pairings & Discretelog: We first look at some group theory background, then dive into KZG and Bulletproofs. A summary of pairing & dlog based polynomial commitments is also given in the end.

Polynomial Commitments using Errorcorrecting Codes: We look at errorcorrecting codes, ReedSolomon Code in particular. Then, we describe a polynomial commitment scheme based on linear codes.
 Interactive Proofs
 Efficiently Verifiable Proofs (NPProofs)
 NPLanguages
 ZeroKnowledge Interactive Proofs
 Interactive Proofs for a Language $L$
 What is ZeroKnowledge?
 ZK Proof of Knowledge (ZKPOK)
 Graph 3Colorability
 Practical Applications of ZK
 Complexity Theory: Randomized Analogue to NP
 ArthurMerlin 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 (NPProofs)
For efficiently verifiable proofs (aka NPProofs) 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: $N$ is a product of 2 large primes
A trivial proof of this would be the following:
 Prover sends $p,q$ as a proof.
 Verifier would check for $N=pq$, and if true it will accept. In doing so, the Verifier learned about $p,q$, which is not good for us!
Example: $y$ is a quadratic residue mod $N$
What this means is that, $∃x∈Z_{N}$ such that $y≡x_{2}(modN)$. It turns out that finding such an $x$ is a very hard problem, as hard as factoring problem actually.
Even so, our prover is unbounded and can find such an $x$ in the end. A trivial proof for this would be:
 Prover sends $x$ as a proof.
 Verifier calculates $x_{2}$ and check if $y≡x_{2}(modN)$, accepts if true and rejects otherwise.
Example: Two graphs are isomorphic
Consider two graphs, as a set of edges $E_{1}={(i_{1},j_{1}),(i_{2},j_{2}),…}$ and $E_{2}={(p_{1},q_{1}),(p_{2},q_{2}),…}$. We say that if there is an isomorphism $π$ that maps an edge $e_{1}∈E_{1}$ to $e_{2}∈E_{2}$ such that $∀(i,j):(i,j)∈E_{1}⟺(π(i),π(j))∈E_{2}$.
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!
NPLanguages
Definition: $L$ is an NPlanguage (or NPdecision problem) if there is a $poly(∣x∣)$ time verifier $V$ where:
 Completeness: true claims have short proofs, meaning that if $x∈L$ then there is a $poly(∣x∣)$ sized witness $w∈{0,1}_{∗}$ such that $V(x,w)=1$.
 Soundness: false theorems have no proofs, meaning that if $x∈L$ then there is no witness, so $∀w∈{0,1}_{∗}$ we have $V(x,w)=0$.
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.
ZeroKnowledge 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 nontrivial 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 polynomialtime (PPT).
Example: Two Colors
Consider a string x="🔴🔵". We claim that there are two colors in this string. However, our verifier is colorblind! 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 $x$ = "🔴🔵".
 The verifier tosses a coin, and flips $x$ if it is heads $(b=1)$ meaning $x_{′}$ = "🔵🔴". Otherwise, $x$ stays the same, meaning $x_{′}$ = "🔴🔵". Verifier sends this $x_{′}$ to the prover.
 Prover will then compare $x$ to $x_{′}$, and since he can see colors, he will be able to tell whether $x_{′}$ is flipped or not. Based on this, he will say $b_{′}$ = heads or tails, depending on the flip. Prover sends $b_{′}$ to the verifier.
 Verifier looks at $b_{′}$, and says "wow this guy can actually guess whether I got heads or tails, he must be seeing colors then!". If $b_{′}$ and $b$ 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 $Pr[Vaccepts]≤1/2$ for a single interaction. Repeating this interaction $k$ times would mean that $Pr[Vaccepts]≤1/2_{k}$ which becomes a tiny probability for large $k$. So, it is very unlikely that a prover can keep faking it for that many interactions.
Example: $y$ is a quadratic residue mod $N$
Here, the claim is the language ${(N,y):∃xs.t.y≡x_{2}(modN)}$.
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 $s$
 asks for the verifier to make a coin toss
 if heads $(b=1)$, it sends $z:=sy $
 if tails $(b=0)$, it sends $z:=s $
 the verifier checks if $z_{2}≡s×y_{c}(modN)$. 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 $x$, 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 $L$
Definition: $(P,V)$ is an interactive proof for $L$, if $V$ is probability polynomial ($∣x∣$) time, and:
 Completeness: if $x∈L$ then $V$ always accepts. Formally: $Pr[(P,V)(x)=accept]≥c$.
 Soundness: if $x∈L$ then for all cheating prover strategies, $V$ will not accept except with negligible probability. Formally: for such cheater provers $P_{∗}$, it holds that $Pr[(P_{∗},V)(x)=accept]≤s$
 In a good scenario, we would except $c=1$ and $s=negl(∣x∣)$ where $negl(λ)$ is a negligible function. However, we might also show that $c−s≥negl(∣x∣)$ or equivalently: $c−s≥1/poly(∣x∣)$.
Definition: Class of languages IP = ${Lfor which there is an interactive proof}$.
What is ZeroKnowledge?
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 zeroknowledge 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 $V$ has tossed.
A view is formally defined as a random variable from the probability distribution over coins of $V$ and interactions with $P$:
$view_{V}(P,V)[x]={(q_{1},a_{1},q_{2},a_{2},…,coin tosses ofV}$
The Simulation Paradigm
$V$'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 $D_{1}$ and $D_{2}$, 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 $1/2+negl$ then $D_{1}$ and $D_{2}$ 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 $1/2+negl$ then the set of fake Rolex watches are indistinguishable from the set of real Rolex watches! Good for the vendor 🙂
Definition: An interactive protocol $(P,V)$ is honestverifier zeroknowledge for a language $L$ if there exists a PPT algorithm $Sim$ (a simulator) such that $∀x∈L$ the following two probability distributions are polytime indistinguishable:
 $view_{V}(P,V)[x]$
 $Sim(x,1_{λ})$, here $λ$ is for technical reasons and for large $x$ you can just ignore it.
A caveat about $Sim$ is that we allow it to run in expectedpolytime. Meaning that there may be some very unlucky cases where the algorithm takes a long time, but in expectation it is polytime.
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 $(P,V)$ is zeroknowledge for a language $L$ if for every PPT $V_{∗}$, there exists a PPT algorithm $Sim$ (a simulator) such that $∀x∈L$:
$view_{V}(P,V)[x]≈Sim(x,1_{λ})$
Flavors of ZeroKnowledge
Again, consider the real distribution $view_{V}(P,V)$ and simulated distribution $Sim(x,1_{λ})$. 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 QuadraticResidue (QR) Proof
Consider the QR proof from above, where we were able to prove with zeroknowledge that we know there exists some $x$ such that $y≡x_{2}(modN)$. Check that interactive proof again, what is the $view$ here? We see that the verifier learns about $s$, it also generates some coin toss value $c$ and finally it learns $z$.
So, $view_{V}(P,V):(s,b,z)$. A simulator should output the same view on its own! Can we do it? Yes, in fact, we can do it perfectly!
Simulator $S$ works as follows:
 First, pick a random bit $b∈{0,1}$.
 Then, pick random $z∈Z_{N}$.
 Compute $s=z_{2}/y_{c}$.
 Output $(s,b,z)$.
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 $x$, but thanks to that division on 3rd step, it could produce a valid $s$ for the view.
What about an adversarial verifier, for example, one that does not pick $b$ at random? Well, we can still construct a simulator:
 First, pick a random bit $b∈{0,1}$.
 Then, pick random $z∈Z_{N}$.
 Compute $s=z_{2}/y_{c}$.
 If $V_{∗}(N,y,s)=b$ then output $(s,b,z)$, otherwise go to step 1 and repeat!
With this setting, even if we don't know what $V_{∗}$ is doing behind the scenes, we should expect that our randomly picked $b$ should match their fixed and adversarially computed $b$. 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 $N$. This is more than just a proof of the claim! So, consider the language $L_{R}={x:∃ws.t.R(x,w)=accept}$ for polytime relation $R$.
Definition: $(P,V)$ is a proof of knowledge (POK) for $L_{R}$ if $∃$ PPT knowledge extractor algorithm $E$ such that $∀x∈L$, in expected polytime $E_{P}(X)$ outputs $w$ such that $V(x,w)=accept$.
Here, $E_{P}(x)$ means that $E$ may run $P$ repeatedly on the same randomness, possibly asking different questions in every execution. This is called the Rewinding Technique.
A ZKPOK for QuadraticResidue (QR) Proof
We have seen the ZKP for a prover that knows $x$ such that $y≡x_{2}(modN)$. 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 $s$ again! In the interactive proof, we would normally have a new random $s$ every time the prover sent us something, but here we can have access to the same $s$ again and again. As such, we were able to obtain $r$ and $rx$, and thus find $x$ 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 $G_{0}$ and $G_{1}$.
 The prover produces a random graph $H$ and sends it to verifier.
 The prover finds an isomorphism $γ_{0}$ from $G_{0}$ to $H$.
 The prover also finds an isomorphism $γ_{1}$ from $G_{1}$ to $H$.
 The verifier sends a coin toss (bit) $b$ to prover, and prover returns $γ_{b}$.
 Verifier checks if $H=γ_{b}(G_{b})$.
 These steps happen repetitively, until some polytime later if the verifier did not reject so far, it accepts.
Notice that since $H=γ_{0}(G_{0})=γ_{1}(G_{1})$ then $G_{1}=γ_{1}(γ_{0}(G_{0}))$. So, the prover indeed knows $σ=γ_{1}γ_{0}$. 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 $G_{0}$ to $G_{1}$. Formal proofs left to the reader.
Graph 3Colorability
Do all NP Languages have ZK Interactive Proofs? Proven in [GoldwasserMicaliWidgerson'86], the answer is YES! They show that if oneway functions exist, then every $L$ in NP has computational zeroknowledge interactive proofs. The proof will come from an NPcomplete problem known as Graph 3Colorability, hence the title of this section.
The ideas of the proof are as follows:
 Show that an NPcomplete problem has a ZK interactive proof. [GMW87] showed a ZK interactive proof for $G3COLOR$ (graph 3colorability problem). For any other $L$ in NP, $L<_{p}G3COLOR$ due to NPC reducibility. Every instance $x$ can be reduced to a graph $G_{x}$ such that if $x∈L$ then $G_{x}$ is 3colorable, and if $x∈L$ then $G_{x}$ is not 3colorable.
 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:
 $Commit(m)$ takes an input $m$, let us think of it as a bit in ${0,1}$, and produces a commitment $c$. Once committed, the commitment does not reveal whether $m$ is 0 or 1.
 $Decommit(c)$ allows a receiver of a commitment $c$ to open it, and reveal what is in there. In this case, some bit $m$ that is either 0 or 1.
For a commitment scheme,
 Binding means that if you have committed to some $m$, then the decommit procedure on that commitment may only reveal $m$, not something else.
 Hiding means that from outside, you can't guess the bit $m$ with more than 1/2 probability.
An example commitment scheme would be to use a semantically secure probabilistic encryption scheme.
 $Commit(b)$ where sender chooses some random $r$ and sends $c:=Enc(b;r)$.
 $Decommit(c)$ where sender send the same random $r$ and $b$, and receiver rejects unless $c=Enc(b;r)$.
Proving a graph $G$ is $G3COLORABLE$
Suppose there is a graph $G=(V,E)$ as in the set of vertices and set of edges, and the prover knows some coloring $π:V→{0,1,2}$ which is a mapping that maps a vertex to a color.
 Prover picks a random permutation of colors $σ:{0,1,2}→ϕ$ 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 $ϕ(v):=σ(π(v))$ for $v∈V$. Then, the prover commits to each newly colored vertex $v$ by running $Commit(ϕ(v))$ protocol.
 Verifier selects a random edge $e=(a,b)$ and sends it to prover.
 Prover runs $Decommit$ on the colors of edge points $a,b$ and reveals $ϕ(a)$ and $ϕ(b)$.
 Verifier rejects if $ϕ(a)=ϕ(b)$, otherwise it repeats steps 13 and accepts after $k$ iterations.
Now, let's look at the properties of this interactive proof:
 Completeness: if $G$ is 3colorable, then the honest prover uses a proper 3coloring & the verifier always accepts.
 Soundness: if $G$ is not 3colorable, then for all $P_{∗}$ it holds for $k=∣E∣_{2}$ (meaning that we have iterations as many as the square of number of edges) that,
$Pr[Vaccepts]<(1−∣E∣1 )_{k}<e_{∣}E∣1 $
 ZeroKnowledge: Easy to see informally, messy to prove formally.
HonestVerifier Computational ZK Simulator
First, let us examine the view of this interactive proof.
 We have an edge $(a,b)$
 We have the commitments to each vertex coloring as $Commit(ϕ(v))$.
 We have the decommit of colors $ϕ(a),ϕ(b)$.
Let us show the honestverifier CZK simulator. For the graph $G=(V,E)$ the simulator will choose a random edge $(a,b)∈E$. Then, it will pick random colors $ϕ(a),ϕ(b)∈{0,1,2}$ such that $ϕ(a)=ϕ(b)$. For all other vertices $v$, it will set $ϕ(v)$ to some fixed color, and commit to all $ϕ(v)$.
The output of simulated view is:
 We have an edge $(a,b)$
 We have the commitments to each vertex coloring $Commit(ϕ(v))$.
 We have the decommit of colors $ϕ(a),ϕ(b)$.
As we can see, the views are kind of indistinguishable! They are not the same though, as the commitments to vertices other than $a,b$ 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:
 $N$ is the product of two primes $p,q$.
 $x$ is a square $mod$ $n$.
 Two graphs $(G_{0},G_{1})$ 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 $E(x)$, and some program $Prog$, the program has output $y$ such that $y=Prog(x)$.
 Given encrypted inputs $E(x)$, and some encrypted program $E(Prog)$, the program has output $y$ such that $y=Prog(x)$.
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 $m$, without revealing $m$ itself but only showing $Enc(m)$ or $Hash(m)$.
 You can prove relationships between messages $m_{1},m_{2}$ without revealing them, such as $m_{1}=m_{2}$ or $m_{1}=m_{2}$. In fact, you can show that there is some value $v$ that when used with a polytime function $f$, you have $v=f(m_{1},m_{2})$.
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 $m$ and along with that new message, it sends a ZKP that $m=Protocol(h,r)$ for some history $h$ and randomness $r$. Furthermore, they will commit to this randomness as $c=Commit(r)$. This makes honest behavior with ZK possible since $L={∃r:m=Protocol(h,r)andc=Commit(r)}$ is in NP.
Some more realworld 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 (Boundederror Probabilistic Polynomial time) 
Efficiently Verifiable  NP (Nondeterministic 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 $G_{0},G_{1}$ 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 $G_{0}$ and $G_{1}$ are indeed isomorphic, then the prover would have no idea whether $H$ is isomorphic to $G_{0}$ or $G_{1}$, because it would be isomorphic to both of them! So, he would have at most 1/2 chance in guessing the correct bit. After $k$ iterations, the possibility of not being rejected by the verifier becomes $1/2_{k}$, which is negligible.
Also, how does prover find isomorphisms like that so easily? Well, remember that the prover is allpowerful 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 $H$ from that!
Completeness and soundness hold for this proof; however, it is not zeroknowledge! This is because if the verifier is not honest, and it's just someone that wants to find out whether some graph $H$ is isomorphic to $G_{0}$, they can very well find it by sending $H$ to the honest prover! Therefore, there is knowledge that is learned about $H$ 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.
ArthurMerlin 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 ArthurMerlin game [BabaiMoran'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 InteractiveProofs more powerful (i.e. can prove more claims) than ArthurMerlin Games? Is coin privacy necessary?
The answer turns out to be no, AM = IP actually [GoldwasserSipser'86]!
FiatShamir Paradigm
You can remove the interaction in AM protocols via FiatShamir Paradigm [FiatShamir'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 $H:{0,1}_{∗}→{0,1}_{k}$ 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 $k$, essentially an output of $k$ coin tosses.
The idea is the following:
 Normally, we had a Prover that sent some answer $a_{i}$ and got back $coins_{i}$ from the Verifier.
 Now, the Prover will send $a_{i}$ but instead of waiting for coins by the Verifier, it will generate its own coins simply via $H(a_{i})$.
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 FiatShamir heuristics is applied to the rest.
However, FiatShamir does not mean you can make all interactive proof's into noninteractive 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 
CoNP  0 solutions  ?  YES 
#P  $k$ many solutions  ?  YES 
PSPACE  $∀∃∀∃…$  ?  YES 
It was shown by [FortnowKarloffLundNissan'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 [BenorGoldwasserKilianWigderson'88], you can prove a lot more with two provers! In fact, you now have unconditional PZK for NP problems. [BabaiFortnowLund'91] has shown that you can even prove NEXPTIME (nondeterministic exponential time) problems with interactive proofs.
Going even further, [ReichardtUngerVazirani'13] has shown that a classical verifier can verify the computation of two entangled but noncommunicating polynomial time quantum algorithms. Finally, a recent work [JiNatarajanVidickWrightYuen'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: Noninteractive Argument of Knowledge
 SNARK: Succinct NARK
 Building a SNARK
 (1) Functional Commitment Scheme
 (2) $F$  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 noninteractive 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 $m$ such that $SHA256(m)=0$.
In SNARK, the proof should be short and fast to verify. A trivial proof of the above statement is to simply send $m$ to the verifier. However, that proof is not short; it is as big as $m$. 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.
zkSNARK
In the case of a zkSNARK, the proof reveals nothing about $m$. zkSNARKs have many applications:
 Private transactions: Tornado Cash, ZCash, IronFish, Aleo (private dApps).
 Compliance: private proofs of solvency & compliance, zeroknowledge 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 [BabaiFortnowLevinSzegedy'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 zkSNARKs can be used in many ways within a blockchain.
 Outsourcing Computation: Even without the need of zeroknowledge, an L1chain can quickly verify that some offchain service has done some work correctly.
 Scaling with Proofbased Rollups (zkRollup): An offchain service processes batch of transactions, and the L1chain 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).
NonBlockchain Applications
Blockchain is really spearheading the development in these areas, but there are many nonblockchain 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 postprocessing, such as rescaling, cropping and grayscaling. 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 [KangHashimotoStoicaSun'22] to this problem using zkSNARKs: suppose that the machine that is doing the postprocessing has the photo $P$ and some list of allowed operations $Ops$. Denote the original photo as $P_{orig}$ and $s$ as the signature. The editing software will attach a proof $π$ of claim: "I know a pair $(P_{orig},s)$" such that:
 $s$ is a valid C2PA signature on $P_{orig}$
 $P$ is the result of applying $Ops$ to $P_{orig}$
 Metadata of $P$ is equal to metadata of $P_{orig}$
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 $F={0,1,…,p−1}$ for some prime $p>2$. A finite field is just a set of numbers where we can do addition and multiplication in modulo $p$. An arithmetic circuit is a DAG (directed acyclic graph) $C:F_{n}→F$ where internal nodes are labeled $+,−,×$ and inputs are labeled $1,x_{1},…,x_{n}$. The circuit defines an $n$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 $x_{1}(x_{1}+x_{2}+1)(x_{2}−1)$.
For convenience, the size of the circuit refers to the number of gates, and is denoted as $∣C∣$. In the example above, $∣C∣=3$.
For example:
 You can implement a circuit that does $C_{hash}(h,m)=(h−SHA256(m))$. This outputs 0 if $m$ is the preimage of $h$ using SHA256, and something other than 0 otherwise. This circuit uses around 20K gates, which is not bad!
 You can have a $C_{sig}(pk,m,σ)$ that outputs 0 if $σ$ is a valid ECDSA signature on $m$ with respect to $pk$.
 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 $M$, and for some input $in$ and output $out$ the flow of this arithmetic circuit looks like the following:
$in→M→M→…→M→out$
$M$ 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: Noninteractive Argument of Knowledge
Suppose you have some public arithmetic circuit $C(x,w)→F$ where,
 $x∈F_{n}$ is a public statement
 $w∈F_{m}$ is a secret witness
Denote $S(C)$ as a preprocessing step for this circuit, which will output a pair $(pp,vp)$ 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 noninteractive.
More formally, a NARK is a triple $(S,P,V)$:
 $S(C)→(pp,vp)$ is the preprocessing setup, generating public parameters for prover and verifier
 $P(pp,x,w)→π$ is the prover function, generating the proof given the public prover parameters, public inputs and the secret inputs (witness).
 $V(vp,x,π)→{0,1}$ 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 FiatShamir 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 zeroknowledgeness:
 Completeness: If the prover does indeed knows the argued knowledge, verifier should definitely accept the proof.
$∀x,w:C(x,w)=0⟹Pr[V(vp,x,P(pp,x,w))=accept]=1$
 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 $E$ that can extract a valid $w$ from the prover.
$V(vp,x,P(pp,x,w))=accept⟹Pknowsw:C(x,w)=0$
 Zeroknowledge (optional): The view of this interaction, consisting of $(C,pp,vp,x,π)$ "reveals nothing new" of $w$.
Trivial NARK
We can easily think of a trivial NARK, that is not zeroknowledge but has the other two properties. Simply, the proof $π=w$. Yeah, just send the witness to the verifier! All the Verifier has to do next is check if $C(x,w)=0$, since both $x$ and $C$ 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 $(S,P,V)$:
 $S(C)→(pp,vp)$ is the preprocessing step, generating public parameters for prover and verifier
 $P(pp,x,w)→π$ is the prover function, where $∣π∣=sublinear(∣w∣)$. So, the proof length must be less than linear in the size of witness.
 $V(vp,x,π)→{0,1}$ is the verification function, where $time(V)=O_{λ}(∣x∣,sublinear(∣C∣)$. Note that the verification will have to read the public inputs, so it is allowed to run in $∣x∣$ time, but it must run sublinear in the size of circuit $C$.
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 $(S,P,V)$:
 $S(C)→(pp,vp)$ is the preprocessing step, generating public parameters for prover and verifier
 $P(pp,x,w)→π$ is the prover function, where $∣π∣=O(g(∣C∣))$. The proof length must be logarithmic to the size of circuit, making the proof very tiny compared to the circuit!
 $V(vp,x,π)→{0,1}$ is the verification function, where $time(V)=O_{λ}(∣x∣,g(∣C∣))$. Again, the verification will have to read the public inputs, so it is allowed to run in $∣x∣$ time, but it will not have time to read the entire circuit, which is quite magical. This is actually what $vp$ public parameter is for, it is capturing a summary of the circuit for the verifier so that $g(∣C∣)$ is enough to run the verification.
A zkSNARK is simply a SNARK proof that reveals nothing about the witness $w$.
Trivial SNARK?
Let us again come back to the trivial proof, where $π=w$.
 Prover sends $w$ to the verifier.
 Verifier checks if $C(x,w)=0$
Why can't there be a trivial SNARK? Well, there may be several reasons:
 If $w$ is long, the proof size will be too large.
 If $C(x,w)$ is taking lots of time, the verifier time will be too long.
 Naturally, we might want to keep $w$ secret.
Preprocessing Setup
We said that a preprocessing setup $S(C)$ is done for a circuit $C$. Things are actually a bit more detailed than this, there are 3 types of setups:
 Trusted Setup per Circuit: $S(C;r)$ is a randomized algorithm. The random $r$ is calculated per circuit, and must be kept secret from the prover; if a prover can learn $r$ then they can prove false statements!
 Trusted Setup & Universal (Updatable): a random $r$ is only chosen once and is independent of the circuit. The setup phase is split in two parts: $S=(S_{init},S_{index})$.
 $S_{init}(λ;r)→gp$ is a onetime setup, done in a trusted environment. $r$ must be kept secret!
 $S_{index}(gp,C)→(pp,vp)$ is done for each circuit, and nothing here is secret! Furthermore, $S_{index}$ is a deterministic algorithm.
 Transparent: $S(C)$ 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 $∣C∣$, 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 $∣C∣$.
Size of proof $π$  Verifier time  Setup  PostQuantum?  

Groth16  ~200 B $O_{λ}(1)$  ~1.5 ms $O_{λ}(1)$  Truster per Circuit  No 
Plonk / Marlin  ~400 B $O_{λ}(1)$  ~3 ms $O_{λ}(1)$  Universal trusted setup  No 
Bulletproofs  ~1.5 KB $O_{λ}(g∥C∥)$  ~3 sec $O_{λ}(∥C∥)$  Transparent  No 
STARK  ~100 KB $O_{λ}(g_{2}∥C∥)$  ~10 ms $O_{λ}(g_{2}∥C∥)$  Transparent  Yes 
The approximations here are made for a circuit that is size $∣C∣≈2_{20}$ 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 $C$ is, the proof size and verifier time will be approximately the same!
Knowledge Soundness
While describing the properties of a NARK, we mentioned soundness:
$V(vp,x,P(pp,x,w))=accept⟹Pknowsw:C(x,w)=0$
Well, what does it mean to "know" here? Informally, $P$ knows $w$ if this $w$ can be somehow extracted from the prover $P$. The way we do that is kind of torturing the $P$ until it spits out $w$. Let us give the formal definition now.
Formally, an argument system $(S,P,V)$ is (adaptively) knowledgesound for some circuit $C$, if for every polynomial time adversary $A=(A_{0},A_{1})$ such that:
 $gp←S_{init}()$
 $(C,x,st)←A_{0}(gp)$
 $(pp,vp)←S_{index}(C)$
 $π←A_{1}(pp,x,st)$
 $Pr[V(vp,x,π)=accept]>β$ for some nonnegligible $β$
there is an efficient extractor $E$ that uses $A_{1}$ as a black box (oracle) such that:
 $gp←S_{init}()$
 $(C,x,st)←A_{0}(gp)$
 $(pp,vp)←S_{index}(C)$
 $w←E_{A_{1}(pp,x,st)}(gp,C,x)$
 $Pr[C(x,w)=0]>β−ϵ$ for some negligible $ϵ$ and nonnegligible $β$.
In other words, the probability that a prover can convince the verifier for some witness $w$ must be at most negligibly different than the probability that this witness $w$ is a valid witness for the circuit $C$. In doing so, this witness $w$ must be extractable by the efficient extractor $E$.
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 physicalworld 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:
 $commit(m,r)→com$ for some randomly chosen $r$
 $verify(m,com,r)→accept or reject$
The scheme must have the following properties:
 Binding: cannot produce two valid openings for $com$
 Hiding: $com$ reveals nothing about the committed data
There is a standard construction using hash functions. Fix a hash function $H:M×R→C$ where
 $commit(m,r)=H(m,r)$
 $verify(m,com,r)=accept ifcom=H(m,r)$
Committing to a function
Choose a family of functions $F={f:X→Y}$. The function $f$ 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 $f(x)=y$ and $f∈F$. Also, $com_{f}$ is a commitment to function $f$, but we may also use the notation $f $ to indicate a commitment (think of it like $f$ in an envelope).
Formally, a functional commitment scheme for $F$ is defined by the following:
 $setup(1_{λ})→gp$ outputs public parameters $gp$.
 $commit(gp,f,r)→com_{f}$ is commitment to $f∈F$ with $r∈R$.
 this should be a binding scheme
 optionally, it can be hiding, which is good for a zkSNARK
 $eval(P,V)$ with a prover $P$ and verifier $V$, for a given $com_{f}$ and $x∈X,y∈Y$:
 $P(gp,f,x,y,r)→π$ (a short proof!),
 $V(gp,com_{f},x,y,π)→accept or reject$
 Basically, the $eval$ system is a SNARK proof wof the relations: $f(x)=y$ and $f∈F$ and $commit(pp,f,r)=com_{f}$.
Four Important Functional Commitments
There are 4 very important functional commitment types:
 Polynomial Commitments: Committing to a univariate polynomial $f(X)∈F_{p}[X]$ where that fancy notation stands for the set of all univariate polynomials of degree at most $d$.
 Multilinear Commitments: Committing to a multilinear polynomial in $F_{p}[X_{1},…,X_{k}]$ which is the set of all the multilinear polynomials in at most $k$ variables, each variable with degree at most 1. Here is an example multilinear polynomial: $f(x_{1},…,x_{7})=x_{1}x_{3}+x_{1}x_{4}x_{5}+x_{7}$.
 Vector Commitments: Committing to a vector $u=(u_{1},…,u_{d})∈F_{p}$ which is a vector of $d$ elements. With our commitment, we would like to be able to open any cell at a later time, such that $f_{u}(i)=u_{i}$. An example vector commitment scheme is Merkle Trees, which you may have heard of!
 InnerProduct Commitments: Committing to a vector $u∈F_{p}$. Opening an inner product is done as $f_{u}(v)=(u,v)$. 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 $F=F_{p}[X]$.
 The prover commits to a univariate polynomial $f∈F_{p}[X]$, later, they can prove that:
 $v=f(u)$ for some public $u,v∈F_{p}$
 $deg(f)≤d$. As this is a SNARK, the proof size and verifier time should be $O_{λ}(gd)$.
 The verifier has access to $(d,com_{f},u,v)$.
There are some example PCSs with different mechanisms:
 Using basic elliptic curves: Bulletproofs (short proof, but verifier time is $O(d)$)
 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 $f=∑_{i=0}a_{i}x_{i}$. Then, our commitment will be:
 $commit(f,r)=H((a_{0},a_{1},…,a_{d}),r)$ as in simply hashing the coefficients and some random variable.
 $eval$ will be done as follows:
 prover will send $π=((a_{0},a_{1},…,a_{d}),r)$ to the verifier
 verifier will construct $f$ from the coefficients, and check if $f(u)=v$ and $H((a_{0},a_{1},…,a_{d}),r)=com_{f}$.
This is problematic because the proof size and verification time are linear in $d$, but we wanted a lot smaller values, such as $gd$.
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 nonzero polynomial with degree at most $d$, shown as $f∈F_{p}[X]$.
 for $r←F_{p}$ it holds that $Pr[f(r)=0]≤d/p$
We know that $f$ has at most $d$ roots. $r$ is chosen at random from a size $p$, do the probability that $r$ "hits" a root value is easy to see that $d/p$.
Now suppose that $p≈2_{256}$ and $d≤2_{40}$. Then, $d/p$ is negligible! So it is really unlikely that a randomly chosen field element will be the root for $f$.
With this in mind, if you do get $f(r)=0$ for $r←F_{p}$ then $f$ is identically zero with very high probability. This gives you a simple zero test for a committed polynomial!
[SchwartzZippelDeMilloLipton] lemma states that this observation holds for multivariate polynomials too, where $d$ is treated as the total degree of $f$. The total degree is calculated as the sum of degrees of all variables, for example $f(x,y)=x_{2}+y_{3}$ has degree $5=3+2$.
Equality Test: A Following Observation
Following the zerotest observation, we can make another observation that allows to check if two polynomials are equal.
Let $f,g∈F_{p}[X]$. For $r←F_{p}$, if $f(r)=g(r)$ then $f=g$ with very high probability! This comes from the observation above, where if $f(r)−g(r)=0$ then $f−g=0$ 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 noninteractiveness the entire lecture; why are we making an interactive protocol right now? Well, $r$ here is the only interaction that a verifier makes to the prover. It is a "public coin", just some cointoss (or a series of tosses) given by the verifier to the prover for everyone to see.
Thanks to FiatShamir Transform, we can transform interactive protocols of this nature into noninteractive proofs! More specifically, FiatShamir Transform can take a "publiccoin interactive protocol" which means all verifier randomness is public, and transform it into a noninteractive protocol.
To be technical, FiatShamir Transform isn't safe to transform ALL interactive proofs of this nature, but it is good enough for our needs right now.
Let $H:M→R$ be a hash function. For the example above, the prover will generate $r:=H(com_{f},com_{g})$ and this will be used as the random challenge. Since the verifier also has access to $com_{f},com_{g}$ they can generate the same $r$ during verification. That is how the interactiveness is removed!
If $H$ is modeled as a randomoracle, and $d/p$ is negligible (as we discussed in zerotest), then this is a SNARK. In practice, SHA256 is used for the hash function.
Is this a zkSNARK? No, because the verifier learns the result of evaluating the polynomials at point $r$.
(2) $F$  Interactive Oracle Proof
The goal of an $F$IOP is to boost a commitment to function $f∈F$ to become a SNARK for general circuits. For example, you could have a polynomial function family $F=F_{p}[X]$ and with $F$IOP you can turn that into a SNARK for any circuit with size $∣C∣<d$.
Definition: Let $C(x,w)$ be some arithmetic circuit. Let $x∈F_{p}$. An $F$IOP is then a proof system that proves $∃w:C(x,w)=0$. In other words, some prover knows a witness $w$.
 Setup: $S(C)→(pp,vp)$ where $vp=(f_{0} ,f_{−1} ,…,f_{−s} )$ 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 $C(x,w)=0$.
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, ..., (t1) 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_(t1))
Let's digest what is happening in this interactive proof:
 The prover starts by sending an oracle for function $f_{1}$. In practice, this is a commitment to function $f_{1}$ which we may show as $f_{1} $.
 The verifier samples a uniformly random field element $r_{1}$, and sends it back to the prover.
 Steps 1 and 2 happen for $t−1$ rounds.
 Finally, the prover sends one last oracle $f_{t} $, an oracle for function $f_{t}$.
 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 $x$ 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.
$∃w:C(x,w)=1⟹Pr[Vaccepts]=1$
 Soundness: The second property is knowledge soundness (unconditional), meaning that a malicious prover can not convince a verifier that they know a witness $w$ such that $C(x,w)=0$. The way to prove that is using an extractor: this extractor is given the statement $x$ and functions $f_{1},f_{2},…,f_{t}$ 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 $w$ from this process.
 Zeroknowledge (optional): The view of this IOP "reveals nothing new" of $w$.
Example: Polynomial IOP for claim $X⊆W⊆F_{p}$
We will go over an example where the public input $X$ is a set, and secret witness $W$ is a set that contains or is equal to $X$. Furthermore, $W$ is a subset of or equal to the finite field for prime $p$. Suppose we capture this relation with a circuit $C$ such that the claim becomes:
$C(X,W)=0⟺X⊆W⊆F_{p}$
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 $f(Z)$ and $g(Z)$ are computed here, let's dig in.
 Prover computes two polynomials $f$ and $g$, a polynomial with roots in $W$ and $X$ respectively. It does that by the following:
 $f(Z)=∏_{w∈W}(Z−w)$
 $g(Z)=∏_{x∈X}(Z−x)$
 Verifier computes $g(Z)$ the same way, because $X$ is public.
 Prover computes a quotient polynomial $q(Z)=f/g∈F_{p}[X]$, which is a polynomial that is the result of dividing $f$ by $g$. This is only a polynomial if $g$ has all the roots that $f$ has, and that implies $X⊆W$. That is a key point to understand in this proof. Let me give an example: $X={1,2}$ and $W={1,2,4}$. Then, 1. $f(Z)=(Z−1)(Z−2)(Z−4)$ 2. $g(Z)=(Z−1)(Z−2)$ 3. $q(Z)=f/g=(Z−4)$ is a valid polynomial in the finite field!
 Prover sends oracles of $f$ and $q$ to the verifier. In practice, it uses a polynomial commitment scheme and sends commitments to these functions, $f $ and $q $.
 Verifier samples a uniform random variable $r$ 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 $r$ anyways: it is to make $r$ public! If the verifier didn't send $r$, we would not be able to say that it is publicly known.
 Verifier queries the value of $f $ and $q $ at point $r$, and also computes $g(r)$. Denote these as $w,q_{′},x$ respectively. Note that this querying happens via the polynomial commitment scheme in practice, so behind the scenes verifier sends $r$ 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 $x×q_{′}=w$. This is only possible if $q(Z)=f/g$ indeed, think of it like checking $f×q=g$ in this example.
Replacing the oracles with commitments, and oracle queries with commitment interactions and so on is often called "compilation step", where this PolyIOP is "compiled" into a SNARK by adding in the PCS (polycommitment scheme) steps.
The IOP Zoo
There are many SNARKs for general circuits.
IOP  Commitment Scheme  Examples 

PolyIOP  PolyCommit  Sonic, Marlin, Plonk 
MultilinearIOP  MultilinearCommit  Spartan, Clover, Hyperplonk 
VectorIOP  VectorCommit (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 noninteractive. To do that final touch, you use the FiatShamir Transform (using hash functions) to make the entire thing noninteractive.
SNARKs in Practice
flowchart LR D[DSL]  compiler > S[SNARKfriendly 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 (domainspecific 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 (Rank1 Constraint System)
 EVM Bytecode (yea, that is possible!)
 …
Finally, with the public parameters $pp,vp$, the public input $x$ and witness $w$ 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/constraintsystem] end c setup> pp[public params] pp prove> zkp[ZKproof] 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 (hardwaredescription 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 $x$ and private inputs (witness) $w$. For example, $ϕ=$ I know a $w$ such that $x=SHA256(w)$.
 Prover has access to $ϕ,x,w$.
 Verifier has access to $ϕ,x$.
 Proof $π$ will prove that $ϕ(x,w)$ holds, without revealing $w$.
However, the key question here is: what could $ϕ$ be? What are some other examples? In theory, $ϕ$ can be any NP problem statement.
 $w$ is factorization of integer $x$
 $w$ is the private key that corresponds to some public key $x$
 $w$ is the credential for account $x$
 $w$ 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 $x$ and $w$.
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 $p$, shown as $Z_{p}$. Usually, $p$ is a large prime number (e.g. ~255 bits). Essentially, an Arithmetic Circuit can be represented by polynomials, for example we could have:
 $w_{0}×w_{0}×w_{0}=x$
 $w_{1}×w_{1}=x$
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[=]
Rank1 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:
 $x$ is a set of field elements $x_{1},x_{2},…,x_{l}$.
 $w$ is a set of field elements $w_{1},w_{2},…,w_{m−l−1}$
 $ϕ$ is made up of $n$ equations with the form $α×β=γ$ where $α,β,γ$ are affine combinations of variables mentioned in the above bullet points.
Let's see some examples of $α×β=γ$.
 $w_{2}×(w_{3}−w_{2}−1)=x_{1}$ is okay.
 $w_{2}×w_{2}=w_{2}$ is okay.
 $w_{2}×w_{2}×w_{2}=x_{1}$ 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 $w_{4}$:
 $w_{2}×w_{2}=w_{4}$ is okay.
 $w_{2}×w_{4}=x_{1}$ 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:
 $x∈Z_{p}$ is a vector of $l$ field elements.
 $w∈Z_{p}$ is a vector of $m−l−1$ field elements.
 $ϕ$ is made up of 3 matrices: $A,B,C∈Z_{p}$
Now, we define a vector $z=(1∣∣x∣∣w)∈Z_{p}$ which has $m$ elements. The rule for this system is that the following equation must hold:
$Az∘Bz=Cz$
Here, $∘$ means the elementwise product of these.
┌───────┐┌┐ ┌───────┐┌┐ ┌───────┐┌┐
....... o ....... = ....... //> every row here corresponds to
 A └┘  B └┘  C └┘ // some rank1 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 $x_{0}$ and two secret inputs (witnesses) $w_{0},w_{1}$. 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 $w_{2},w_{3},w_{4}$. Then, we simply write equations in the form $α×β=γ$ as discussed before, as one equation per gate!
 $w_{0}×w_{1}=w_{2}$
 $w_{3}=w_{2}+x_{0}$ (notice that left side is actually $w_{3}×1$)
 $w_{1}×x_{0}=w_{4}$
 $w_{3}=w_{4}$
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 & Subcircuits 
Actions  Mutate variables, Call functions  Connect wires, Create subcircuits 
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: $z=x×y$
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 subcircuit 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 Rank1. So, one side is linear and other is quadratic. You can't do things likex * x * x
because $x_{3}$ 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: $y=f_{n}(x)$ where $f(x)=x_{2}$
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 hardcode 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: Nonzero & 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 nonzero
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 subcircuit 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 nonzero, 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 subcircuit 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/rdiberkeley/zkpcourselecture3code/tree/main/circom.
We would like to prove that we know the solution to a sudoku puzzle.
 The public input $x$ will be the initial setting of the sudoku board, with 0 for empty cells and some integer $1≤i≤9$ for nonempty cells.
 The private input $w$ (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 2dimensional arrays of size $n×n$. We should really like to write a generic template circuit that takes the board size $n$ as template argument.
For now, let's do an example for $n=9$. What will be our constraints though? Let's list them one by one:
 The solution input should be composed of numbers in range $[1,9]$.
 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 $3×3$ groups of cells (as in Sudoku) where every number occurs once in each group.
Here is the circuit, along with it's subcircuits.
// Assert that two elements are not equal.
// Done via the check if in0  in1 is nonzero.
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 nonequal 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 nbits
// 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 nonempty 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 highlevel 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 highlevel, 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 & errorprone. 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: r1csstd + cryptoprimitives (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 highlevel 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
 Fixedlength loops
 Ifelse 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
 LowDegree & Multilinear Extensions
 The SumCheck Protocol
 SNARK for CircuitSatisfiability
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 $m$ such that $SHA256(m)=0$.
In SNARK, the proof should be short and fast to verify. A trivial proof of the above statement is to simply send $m$ to the verifier. However, that proof is not short; it is as big as $m$. 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 $P$ and a verifier $V$.
 $P$ solves a problem (has some claim), and tells the answer (proves the claim) to $V$.
 Then, they start to have a conversation. $P$'s goal is to convince $V$ 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 $P$ can convince $V$ to accept.
 (Statistical) Soundness: If $P$ is dishonest, then $V$ will catch this with very high probability. In other words, it is negligibly probable that a dishonest $P$ can convince $V$.
 Note that this must hold even if $P$ is computationally unbounded, and is actively trying to fool $V$.
 If soundness holds only against polynomialtime $P$, 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 $C$ be some public arithmetic circuit
$C(x,w)→F$
where $x∈F_{n}$ is some public statement and $w∈F_{m}$ is some secret witness. Let us look at the types of "soundness" with this example:
 Soundness: $V$ accepts $⟹∃w:C(x,w)=0$
 Knowledge soundness: $V$ accepts $⟹P$ "knows" $∃w:C(x,w)=0$
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, $P$ can claim that the output of a program given by $V$ on the public input $x$ is 42. Well, witness is not used in the program, so there is really nothing to "know" here.
The viceversa 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, $P$ 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 FiatShamir Transform [Fiat, Shamir'87], where a publiccoin protocol (an IP where randomness is public) can be made public & noninteractive! 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  NonInteractive 
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 $w$ such that $C(x,w)=0$? Well, you could just send $w$ right? This has two problems, both against the "succinctness" of a SNARK:
 $w$ could be large 🔴
 computing $C(x,w)$ could take a lot of time 🔴
 actually noninteractive 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 $w$ to the verifier, and somehow convince that the sent $w$ satisfies $C(x,w)=0$.
 w could still be large 🔴
 the verification is a lot faster, verifier is not computing $C(x,w)$ directly! 🟢
 interactive 🔴
Note that since $w$ 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 $w$ explicitly, the prover will cryptographically commit to $w$ and send that commitment. Again, an IP is used to convince that the committed $w$ satisfies $C(x,w)=0$.
In doing so, the prover will reveal just enough about the committed $w$ to allow the verifier to run its checks in the interactive proof.
 commitment of $w$ is succinct 🟢
 verification is fast 🟢
 seems interactive, but can be made noninteractive using FiatShamir 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 $f(X)∈F_{p}[X]$ where that fancy notation stands for the set of all univariate polynomials of degree at most $d$.
 Multilinear Commitments: Committing to a multilinear polynomial in $F_{p}[X_{1},…,X_{k}]$ which is the set of all the multilinear polynomials in at most $k$ variables, each variable with degree at most 1. Here is an example multilinear polynomial: $f(x_{1},…,x_{7})=x_{1}x_{3}+x_{1}x_{4}x_{5}+x_{7}$.
 Vector Commitments: Committing to a vector $u=(u_{1},…,u_{d})∈F_{p}$ which is a vector of $d$ elements. With our commitment, we would like to be able to open any cell at a later time, such that $f_{u}(i)=u_{i}$. 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:
 $h_{1}=H(h_{2},h_{3})$
 $h_{2}=H(h_{4},h_{5})$
 and so on…
The leaf nodes are the elements of the committed vector, m
, y
, v
, and such. The root $h_{1}$ 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
, $h_{7}$ and $h_{2}$. The verifier will do the following:
 $h_{6}=H(c,t)$
 $h_{3}=H(h_{6},h_{7})$
 $h_{1}=H(h_{2},h_{3})$
Then, the verifier will compare the calculate $h_{1}$ 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 roottoleaf path.
 Verifier checks if the hashes are consistent with the root hash.
 The size of this proof to reveal a value is $O(gn)$ 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 $f(x)∈F_{n}[X]$
Let us think about the [m, y, v, e, c, t, o, r]
commitment example above. Suppose that you have a polynomial $f(x)∈F_{7}[X]$ so this polynomial has values defined over a very small $n=7$. The degree should be small too, say something like $d=3$.
To commit to this polynomial, the prover could simply commit to the following vector:
$[f(0),f(1),f(2),f(3),f(4),f(5),f(6),∗]$
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 $f(3)$ is at the third leaf).
Well, is this really a good method? No, it has quite huge problems actually.
 First of all, there are $∣F_{n}∣$ nodes in this tree. Evaluating that many elements for large $n$ like $2_{128}$ is a nightmare. We would instead want to have some total evaluation time proportional to the degree bound $d$.
 Speaking of degree, notice that the verifier has no idea if indeed the committed polynomial has degree at most $d$.
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 $f∈F_{p}[X]$ what is the probability that $f(r)=0$ for some $r∈F_{p}$? Well, if it is degree $d$ then it has $d$ roots, meaning that there are exactly $d$ points where $f$ evaluates to 0. How many total points are there? The answer is $∣F_{p}∣$. So in short:
$r∈F_{p}Pr [f(r)=0]≤∣F_{p}∣d $
For very large $p$ and small $d$ this probability becomes negligible; meaning that you can't really come up with some random field element $r$ and find that $f(r)=0$, it is a tiny probability. Following on this "zerotest" fact, you can obtain an "equalitytest" with the same reasoning:
$r∈F_{p}Pr [f(r)=q(r)]≤∣F_{p}∣d $
So if you have two polynomials $f,q$ and they both evaluate to the same thing, chances are they are the same polynomial!
SchwartsZippelDemilloLipton Lemma is a multivariate generalization of this fact. Let $f=q$ be $l$variate polynomials of total degree at most $d$. Total degree refers to the maximum sum of degrees of all variables in any term, for example $x_{1}x_{2}+x_{1}x_{2}$ has a total degree $3=2+1$ due to the first term. The lemma states that:
$r∈F_{p}Pr [f(r)=q(r)]≤∣F_{p}∣d $
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 $d$, you can have a multivariate polynomial with a smaller degree $d$ which in turn reduces the proof size and makes things much more efficient.
LowDegree & Multilinear Extensions
We now have some math to do, but do not fear; it will be quite useful!
Definition [Extension]: Given a function $f:{0,1}_{l}→F$, a $l$variate polynomial $g$ over $F$ is said to extend $f$ if $∀x∈{0,1}_{l}:f(x)=g(x)$.
Definition [Multilinear Extension]: Any function $f:{0,1}_{l}→F$ has a unique multilinear extension (MLE) denoted $f~ :F_{l}→F$.
 Multilinear means the polynomial has degree at most 1 in each variable. For example, $(1−x_{1})(1−x_{2})$ is multilinear, but $x_{1}x_{2}$ is not.
Example: $f:{0,1}_{2}→F$
Let us think of some function $f$ defined over the domain ${(0,0),(0,1),(1,0),(1,1)}$.
 $f(0,0)=1$
 $f(0,1)=2$
 $f(1,0)=8$
 $f(1,1)=10$
Here is the multilinear extension for $f$, shown as $f~ :F_{2}→F$ which is:
$f~ (x_{1},x_{2})=(1−x_{1})(1−x_{2})+2(1−x_{1})x_{2}+8x_{1}(1−x_{2})+10x_{1}x_{2}$
You can check that for $(x_{1},x_{2})∈{0,1}_{2}$ it holds that $f(x_{1},x_{2})=f~ (x_{1},x_{2})$. 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 nonmultilinear extensions of $f$. For example:
$g(x_{1},x_{2})=−x_{1}+x_{1}x_{2}+8x_{1}+x_{2}+1$
also works for the inputs in ${0,1}_{2}$, 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 $f,g$ defined over ${0,1}_{l}$. Both of these functions have unique MLE's $f ,g $. The cool thing is: if there are any disagreeing inputs such that their evaluations on $f$ and $g$ are not equal, then the MLEs of these functions $f ,g $ 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 $f,g$, so that you can see the resulting extreme differences in the extensions $f ,g $.
Quick Evaluation of MLEs
Given as input all $2_{l}$ evaluations of a function $f:{0,1}_{l}→F$, for any point $r∈F_{l}$ there is an $O(2_{l})$time algorithm for evaluating the MLE $f~ (r)$.
The trick is using Lagrange Interpolation. For every input $w=(w_{1},w_{2},…,w_{l})∈{0,1}_{l}$, define the multilinear Lagrange basis polynomial as follows:
$δ~_{w}(r)=i=1∏l (r_{i}w_{i}+(1−r_{i})(1−w_{i}))$
It can be shown that you can get the evaluations of $f~ (r)$ using these:
$f (r)=w∈{0,1}_{l}∑ f(w)×δ_{w}(r)$
For each $w∈{0,1}_{l}$ the result $δ~_{w}(r)$ can be computed with $O(l)$ field operations. As such, the overall algorithm for $2_{l}$ points takes time $O(l2_{l})$. Using dynamic programming, this can be reduced to $O(2_{l})$.
The SumCheck Protocol
We will now examine a seminal work [LundFortnowKarloffNissan'90], known as the sumcheck protocol.
We have a verifier $V$ with oracle access to some $l$variate polynomial $g$ over field $F$. The goal of this verifier is compute the quantity:
$b_{1}∈{0,1}∑ b_{2}∈{0,1}∑ …b_{l}∈{0,1}∑ g(b_{1},b_{2},…,b_{l})$
If you look closely, this sum is actually sum of all evaluations of $b∈{0,1}_{l}$ in $g$. In the naive method, the verifier would query each input, and find the sum in a total of $2_{l}$ 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 $P$ as prover and $V$ as verifier.
 Start: $P$ sends the claimed answer $C_{1}$. The protocol must check that indeed:
$C_{1}=b_{1}∈{0,1}∑ b_{2}∈{0,1}∑ …b_{l}∈{0,1}∑ g(b_{1},b_{2},…,b_{l})$
 Round 1: $P$ sends univariate polynomial $s_{1}(X_{1})$ claimed to equal $H_{1}(X_{1})$ (H standing for honest):
$H_{1}(X_{1})=b_{2}∈{0,1}∑ b_{3}∈{0,1}∑ …b_{l}∈{0,1}∑ g(X_{1},b_{2},…,b_{l})$
This sum is basically almost $C_{1}$, but instead of $b_{1}∈{0,1}$ we use the variable $X_{1}$. Since the entire thing is a sum, and $X_{1}$ is the only variable; this whole thing is a univariate polynomial.
 Round 1 Check: $V$ now checks that $C_{1}=s_{1}(0)+s_{1}(1)$, basically filling in the missing sums for $b_{1}∈{0,1}$.
 If this check passes, then $V$ can now believe that $C_{1}$ is the correct answer so long as $s_{1}=H_{1}$. Well, how can we check that $s_{1}=H_{1}$?
 Remember that if two polynomials agree at a random point, they are highly likely to be equal! So, $V$ picks a random point $r_{1}∈F$ and checks that $s_{1}(r_{1})=H_{1}(r_{1})$.
 Calculating $s_{1}(r_{1})$ is easy for the verifier, it's just some univariate polynomial with a notsohigh degree. However, the verifier does not know $H_{1}$.
 Recursion into Round 2: If you look at the form of $H_{1}$, it looks a lot like the sum $C_{1}$. So, you can think of doing the same operations for $C_{2}=H_{1}(r_{1})$ and then do the entire thing to verify the sum $C_{2}$.
$C_{2}=H_{1}(r_{1})=b_{2}∈{0,1}∑ b_{3}∈{0,1}∑ …b_{l}∈{0,1}∑ g(r_{1},b_{2},b_{3},…,b_{l})$
 Recursion into Rounds 3, 4, …, $l$: The verifier and prover keep doing this until the last round.
 Final Round (Round $l$): Like before, $P$ sends univariate polynomial $s_{l}(X_{l})$ claim to equal $H_{l}(X_{l})$ which is:
$H_{l}=g(r_{1},r_{2},…,r_{l−1},X_{l})$
 Final Round Check: $V$ now checks that $s_{l−1}(r_{l−1})=s_{l}(0)+s_{l}(1)$.
 Again, if this check passes $V$ must make sure that $s_{l}=H_{l}$. However, we don't have to recurse anymore!
 Notice that $H_{l}$ is just a single query to the $g$. So, $V$ can pick a random point $r_{l}∈F$ and immediately query the oracle to find $s_{l}(r_{l})=g(r_{1},r_{2},…,r_{l})$.
 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 $1−∣F∣l×d $ where $d$ is the maximum degree of $g$ in any variable.
 For example, $∣F∣≈2_{128},d=3,l=60$ will make this probability $2_{−120}$ which is tiny.
 You can prove this by induction on the number of variable $l$, see the video for the proof.
 Cost: Total communication is $O(dl)$ field elements.
 $P$ sends $l$ messages with each being a univariate polynomial of degree at most $d$.
 $V$ sends $l−1$ messages, each being a random field element.
 $P$ runtime is $O(d×2_{l}×eval)$ and $V$ runtime is $O(dl+eval)$, here $eval$ is the time required to evaluate $g$ at one point.
Application: Counting Triangles in a Graph
To demonstrate how sumcheck protocol can be applied, we will look at an interactive proof about counting triangles in a graph.
 Given Input: $A∈{0,1}_{n×n}$, representing the adjacency matrix of a graph.
 Desired Output: $∑_{(i,j,k)∈n×n×n}A_{ij}A_{jk}A_{ik}$ 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 matrixmultiplication time, currently about $n_{2.37}$.
The protocol works as follows:
 Interpret the matrix $n×n$ matrix as if it's a function $A:{0,1}_{logn}×{0,1}_{logn}→F$. 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 $A$ with the respective inputs.
 Remember SZDL lemma, meaning that there is a unique multilinear extension $A~$ for that function $A$.
 Define the polynomial $g(X,Y,Z)=A(X,Y)A(Y,Z)A~(X,Z)$.
 Apply the sumcheck protocol to $g$ to compute:
$a∈{0,1}_{logn}∑ b∈{0,1}_{logn}∑ c∈{0,1}_{logn}∑ g(a,b,c)$
How much is the cost of this protocol?
 Total communication is $O(gn)$.
 Verifier runtime is $O(n_{2})$, which is linear in the size of matrix. This runtime is dominated by evaluating $g(r_{1},r_{2},r_{3})$ in the final round of the sumcheck protocol.
 Prover runtime is $O(n_{3})$.
SNARK for CircuitSatisfiability
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 $C$ over $F$ of size $S$ and output $y$. The prover $P$ claims to know a witness $w$ such that $C(x,w)=y$. For simplicitly, let's take the public input $x$ 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 $T$ is a correct transcript if it assigns the gate values obtained by evaluating the circuit $C$ on a valid witness $w$.
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 $T$ can be viewed as a function $T:{0,1}_{logS}→F$. Assign each gate in $C$ a $gS$bit label and view $T$ as a function mapping gate labels to $F$. Basically, by giving the correct gate label to this function you can select a value at the circuit transcript, something like $T(0,0,0,0)=1$ for the example above.
PolynomialIOP for SNARK
Recall that our SNARK is all about proving that we know a secret witness $w$ such that for some public input $x$ and arithmetic circuit $C$ it holds that $C(x,w)=0$. Denote the circuit size as $S=∣C∣$.
 First, we will construct the correct transcript of $C(x,w)$, which we denote as $T:{0,1}_{logS}→F$. We have talked about how this happens in the previous section.
 Prover $P$ will calculate the extension of $T$ to obtain a polynomial $h:F_{logS}→F$. This extension $h$ is the first message sent to the verifier.
$∀x∈{0,1}_{logS}:h(x)=T(x)$
 The verifier $V$ needs to verify that this is indeed true, but it will only make a few evaluations of $h$ 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 $h$ to $g_{h}$
First, we will construct a $(3gS)$variate polynomial $g_{h}$ such that: $h$ extends a correct transcript $T$ if and only if $∀(a,b,c)∈{0,1}_{3logS}:g_{h}(a,b,c)=0$. To evaluate $g_{h}(r)$ for any $r∈F$, it should suffice to evaluate $h$ at only 3 inputs.
As a sketch of the proof, define $g_{h}(a,b,c)$ as the following:
$add(a,b,c)(h(a)−(h(b)+h(c))+mult(a,b,c)(h(a)−(h(b)h(c)))$
We have two new functions here, let's just quickly introduce what they are:
 $add~(a,b,c)$ is a multilinear extension of a wiring predicate of a circuit, which returns 1 if and only if $a$ is an addition gate and it's two inputs are gates $b$ and $c$.
 $mult~(a,b,c)$ is a multilinear extension of a wiring predicate of a circuit, which returns 1 if and only if $a$ is a multiplication gate and it's two inputs are gates $b$ and $c$.
With this definition, notice what happens:
 If $add~(a,b,c)=1$ then $g_{h}(a,b,c)=h(a)−(h(b)+h(c))$. For this to be zero, $h(a)=h(b)+h(c)$ is required.
 If $mult~(a,b,c)=1$ then $g_{h}(a,b,c)=h(a)−h(b)h(c)$. For this to be zero, $h(a)=h(b)h(c)$ is required.
 Otherwise, $g_{h}(a,b,c)=0$.
As such, if the addition and multiplications in the extension $h$ behave correctly with respect to the correct transcription $T$, then the sum of evaluating the points on $g_{h}(a,b,c)$ should be 0. As a further note, in structured circuits (circuits with repeating structure & wiring) the computation of $add$ and $mult$ can be made a bit more efficient.
What we accomplish by doing this is the following: the original claim is that $h$ extends a correct transcript $T$. This is quite a complicated thing to show per se, there may be many things going on with $h$. $g_{h}$ on the other hand requires a more simpler structure, just check if the result is 0 for all the inputs.
Note that ${0,1}_{3logS}$ is sometimes referred to as boolean hypercube within the lecture. This is because ${0,1}_{3}$ is a boolean hypercube (specifically the corners of the hypercube can be labeled as the elements of this set) and we want $g_{h}$ to vanish over $gS$ variables using this hypercube.
Step 2: Proving $g_{h}$
So, how can the verifier check that indeed $∀(a,b,c)∈{0,1}_{3logS}:g_{h}(a,b,c)=0$? In doing so, verifier should only evaluate $g_{h}$ at a single point!
Using a Quotient Polynomial: Imagine for a moment that $g_{h}$ were a univariate polynomial $g_{h}(X)$. In that case, this would be defined over some subset $H⊆F$ and we would want to check that $∀x∈H:g_{h}(x)=0$.
There is a wellknown result in polynomials that will be very useful here: $∀x∈H:g_{h}(x)=0$ if and only if it is divisible by the vanishing polynomial for $H$. The vanishing polynomial is defined as $Z_{H}$:
$Z_{H}(x)=a∈H∏ (x−a)$
The polynomial IOP will work as follows:
 $P$ sends a polynomial $q$ such that $g_{h}(X)=q(X)×Z_{H}(X)$.
 $V$ verifies this by picking a random $r∈H$ and checking $g_{h}(r)=q(r)×Z_{H}(r)$.
This approach is not really the best approach though; it has problems.
 First of all, $g_{h}$ is not univariate, it is obviously $(3gS)$variate.
 Having the prover find and send the quotient polynomial $q$ 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 wellknown schemes: Marlin, Plonk and Groth16.
Using SumCheck Protocol: An alternative approach for this step, which we have been foreshadowing throughout this lecture, is the sumcheck protocol!
Sumcheck handles multivariate polynomials, and it doesn't require $P$ to send additional large polynomials. The sumcheck we are interested in is the following:
$0=a∈{0,1}_{logS}∑ b∈{0,1}_{logS}∑ b∈{0,1}_{logS}∑ g_{h}(a,b,c)_{2}$
To capture the general idea, we are working with integers $Z$ instead of finite field $F$ here. When we square the result like that, the entire sum is zero if and only if $g_{h}(a,b,c)$ is zero for all inputs.
 In the end, the verifier will only compute $g_{h}(r_{1},r_{2},r_{3})$ for some random inputs, and it suffices to compute $h(r_{1}),h(r_{2}),h(r_{3})$ for that.
 Outside of these evaluations, $V$ runs in time $O(gS)$
 $P$ performs $O(S)$ field operations given a witness $w$.
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 Polycommit Scheme
 Dory Polycommit 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 $f∈F_{p}[X]$.
 An $eval$ function uses evaluate some values for this polynomial, without revealing it. For example, pick some public $u,v∈F_{p}$.
 Prover will convince that $f(u)=v$ and $deg(f)≤d$.
 Verifier will only know $d,u,v$ and a polynomial commitment $com_{f}$, also shown as $f $ sometimes.
 The proof size for $eval$ and the verifier time should both be in $O_{λ}(gd)$. Spoilers: it will turn out be constant $O(1)$ which is really a magical thing to me.
KZG Polycommit Scheme
In this lecture, we will use KZG [KateZaveruchaGoldberg'10] polynomial commitment scheme.
Fix some finite cyclic group $G$ of order $p$. This group basically has some generator value $G$ and the group consists of it's multiplications:
$G={0,G,2G,3G,…,(p−1)G}$
The group has addition operation defined on it, where you can add $aG+bG$ to obtain $cG$ where $a+b≡c(modp)$.
Trusted Setup: $setup(λ)→gp$
KZG starts with a trusted setup $setup(λ)→gp$ to produce public parameters. This is done as follows:
 Sample some random $τ∈F_{p}$.
 Compute $∀i∈[d]:H_{i}=τ_{i}G$. Basically, you have $d+1$ group elements, each multiplied to some power of tau ($τ$) and multiplied by $G$. These computed values will be the public parameters $gp$.
$gp=(H_{0}=G,H_{1}=τG,H_{2}=τ_{2}G,…,H_{d}=τ_{d}G)∈G_{d+1}$
 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: $commit(gp,f)→com_{f}$
A commitment will take the public parameters $gp$ along with the polynomial $f$ to be committed, and produces the commitment.
 The commitment is shown as $commit(gp,f)→com_{f}$
 Our commitment will be $com_{f}=f(τ)G∈G$.
But wait, $τ$ was deleted after setup so how do we obtain this? Well, think of the polynomial $f$ as follows:
$f(X)=f_{0}+f_{1}X+f_{2}X_{2}+…+f_{d}X_{d}$
Notice that for every $X$