Welcome to my Cryptography Notes.

⬩

To learn is to teach - to teach is to learn, and to take notes.

⬩

Hopefully you can learn something from these notes, and please feel free to create an issue or a pull-request if you have suggestions.

⬩

Take care anon, and remember not to trust, but verify.

— erhant

Berkeley ZKP MOOC 2023 Spring

Summary of ZKP MOOC Spring 2023 lectures, which are a series of lectures given by Dr. Dan Boneh, Dr. Shafi Goldwasser, Dr. Dawn Song, Dr. Justin Thaler and Dr. Yupeng Zhang. This course covers fundamental techniques to build ZKP protocols, tools to implement ZKP for different computations, and different applications of ZKP in blockchain and other areas

There may be some repetitions among the lectures, but that is good and especially useful when you come back to skim over the notes.

Take a moment and look at that roster, it's like champions league up there. Make sure you watch the course videos on YouTube, and visit the course website.

1. Introduction & History: In the first lecture, we take a look at the starting point of all this What separates classical proof from an interactive proof, and how powerful are interactive proofs? What is zero-knowledge and how did it came to be? An excellent primer by Prof. Shafi Goldwasser.
   

2. 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.
   

3. Programming ZKPs: Suppose you have an idea, and you write a program about it and you have to reduce it to some constraint system so that zero-knowledge cryptography can do it's thing. How can we do it? See this lecture for the answer.
   

4. SNARKs via IPs: This lecture is also about building SNARKs, with various methods! We will look at Merkle trees, Schwartz-Zippel lemma, Sum-check protocol and much more.
   

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

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

7. Polynomial Commitments using Error-correcting Codes: We look at error-correcting codes, Reed-Solomon Code in particular. Then, we describe a polynomial commitment scheme based on linear codes.
   

• Interactive Proofs
• Efficiently Verifiable Proofs (NP-Proofs)
  • Example: $N$ is a product of 2 large primes
  • Example: $y$ is a quadratic residue mod $N$
  • Example: Two graphs are isomorphic
• NP-Languages
• Zero-Knowledge Interactive Proofs
  • Example: Two Colors
  • Example: $y$ is a quadratic residue mod $N$
• Interactive Proofs for a Language $\mathcal{L}$
• What is Zero-Knowledge?
  • The Simulation Paradigm
  • Flavors of Zero-Knowledge
  • A Simulation for Quadratic-Residue (QR) Proof
• ZK Proof of Knowledge (ZKPOK)
  • A ZKPOK for Quadratic-Residue (QR) Proof
  • Example: Graph Isomorphism
• Graph 3-Colorability
  • What is a Commitment Scheme?
  • Proving a graph $G$ is $\text{G3-COLORABLE}$
    • Honest-Verifier Computational ZK Simulator
• Practical Applications of ZK
• Complexity Theory: Randomized Analogue to NP
  • Is IP greater than NP?
• Arthur-Merlin Games & is AM = IP?
  • Fiat-Shamir Paradigm
• Efficient Verification

Interactive Proofs

When we think of proofs made by Euclid, Gauss, Euler and such, we think of proofs where we are trying to show that given some axioms and declarations, you can show that some claim is true. These are classical proofs.

There is a much more powerful proof system, called interactive proofs, we must think of proofs more interactively such as:

sequenceDiagram
	actor P as Prover
	actor V as Verifier

	note over P, V: claim
	P ->> V: proof
	note over V: accept/reject

Efficiently Verifiable Proofs (NP-Proofs)

For efficiently verifiable proofs (aka NP-Proofs) we have the following setting:

sequenceDiagram
	actor P as Prover
	actor V as Verifier

	note over P, V: claim = x
	note over P: works hard to generate proof w
  note over P: unbounded time
	P ->> V: short proof w s.t |w| = poly in |x|
	note over V: find V(x, w), takes poly time in |x|
	note over V: accept if it is 1, reject otherwise

Let us check some example claims.

Example: $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, $\exists x\in {\mathbb{Z}}_N^{\ast }$ such that $y\equiv x^2(\mathrm{mod}N)$. 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\equiv x^2(\mathrm{mod}N)$, 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),\dots \}$ and $E_2=\{(p_1,q_1),(p_2,q_2),\dots \}$. We say that if there is an isomorphism $\pi$ that maps an edge $e_1\in E_1$ to $e_2\in E_2$ such that $\forall (i,j):(i,j)\in E_1⟺(\pi (i),\pi (j))\in 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!

NP-Languages

Definition: $\mathcal{L}$ is an NP-language (or NP-decision problem) if there is a $poly(|x|)$ time verifier $V$ where:

• Completeness: true claims have short proofs, meaning that if $x\in \mathcal{L}$ then there is a $poly(|x|)$ sized witness $w\in \{0,1{\}}^{\ast }$ such that $V(x,w)=1$.
• Soundness: false theorems have no proofs, meaning that if $x\notin \mathcal{L}$ then there is no witness, so $\forall w\in \{0,1{\}}^{\ast }$ 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.

Zero-Knowledge Interactive Proofs

The main idea of ZKP, although very informally, is that a Prover "will prove that they can indeed prove the claim if they wanted to", but they are not doing that so that information is kept private.

sequenceDiagram
	actor P as Prover
	actor V as Verifier

	note over P: proves "I could prove it if I felt like it"
  P ->> V: sends a ZKP
	note over V: wow, ok I believe that

We need to extend our proof model to work with ZK. We will need two more ingredients:

• Interaction: rather than passively reading a proof, the verifier engages in a non-trivial interaction with the prover.
• Randomness: verifier is randomized, i.e. coin tossing is allowed as a primitive operation. Furthermore, the verifier can have an error in accepting/rejecting but with a small negligible probability.

With this, our proof model becomes as follows:

sequenceDiagram
	actor P as Prover
	actor V as Verifier

	note over P, V: claim x
	loop i = 1, 2, ...
		P ->> V: a_i
		V ->> P: q_i
	end
	note over V: accept/reject

Here, the Prover is computationally unbounded but the Verifier must be efficient, i.e. runs in probabilistic polynomial-time (PPT).

Example: Two Colors

Consider a string x="🔴🔵". We claim that there are two colors in this string. However, our verifier is color-blind! How can we prove that indeed this string has two colors?

sequenceDiagram
	actor P as Prover
	actor V as Verifier

	note over P, V: claim: x="🔴🔵" has 🔴 and 🔵
	loop i = 1, 2, ...
		P ->> V: x
		note over V: b ← {0, 1}
		alt b = 1
			note over V: x' := flip(x)
		else
			note over V: x' := x
		end
		V ->> P: x'
		alt x' = flip(x)
			note over P: b' := 1
		else
			note over P: b' := 0
		end
		P ->> V: b'
		note over V: if [b != b'] then reject
	end
	note over V: accept

Let us describe what happens in this interactive proof:

• The prover sends x to the verifier, say $x$ = "🔴🔵".
• The verifier tosses a coin, and flips $x$ if it is heads $(b=1)$ meaning $x^{\prime }$ = "🔵🔴". Otherwise, $x$ stays the same, meaning $x^{\prime }$ = "🔴🔵". Verifier sends this $x^{\prime }$ to the prover.
• Prover will then compare $x$ to $x^{\prime }$, and since he can see colors, he will be able to tell whether $x^{\prime }$ is flipped or not. Based on this, he will say $b^{\prime }$ = heads or tails, depending on the flip. Prover sends $b^{\prime }$ to the verifier.
• Verifier looks at $b^{\prime }$, and says "wow this guy can actually guess whether I got heads or tails, he must be seeing colors then!". If $b^{\prime }$ 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 $\mathrm{Pr}[V\text{ accepts}]\le 1/2$ for a single interaction. Repeating this interaction $k$ times would mean that $\mathrm{Pr}[V\text{ accepts}]\le 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):\exists x\text{ s.t. }y\equiv x^2(\mathrm{mod}N)\}$.

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:=\sqrt{sy}$
  • if tails $(b=0)$, it sends $z:=\sqrt{s}$
• the verifier checks if $z^2\equiv s\times y^c(\mathrm{mod}N)$. 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 $\mathcal{L}$

Definition: $(P,V)$ is an interactive proof for $\mathcal{L}$, if $V$ is probability polynomial ($|x|$) time, and:

• Completeness: if $x\in \mathcal{L}$ then $V$ always accepts. Formally: $\mathrm{Pr}[(P,V)(x)=\text{ accept}]\ge c$.
• Soundness: if $x\notin \mathcal{L}$ then for all cheating prover strategies, $V$ will not accept except with negligible probability. Formally: for such cheater provers $P^{\ast }$, it holds that $\mathrm{Pr}[(P^{\ast },V)(x)=\text{ accept}]\le s$
• In a good scenario, we would except $c=1$ and $s=negl(|x|)$ where $negl(\lambda )$ is a negligible function. However, we might also show that $c-s\ge negl(|x|)$ or equivalently: $c-s\ge 1/poly(|x|)$.

Definition: Class of languages IP = $\{\mathcal{L}\text{ for which there is an interactive proof}\}$.

What is Zero-Knowledge?

For true statements, we want the following to be true: what the verifier could have computed before the interaction IS EQUAL TO what the verifier can compute after the interaction.

So basically, these interactions had no effect whatsoever on the computational power of the verifier! That is what zero-knowledge means. Now, let's be more formal.

sequenceDiagram
	actor P as Prover
	actor V as Verifier

	note over P, V: theorem T
	loop i = 1, 2, ...
		P ->> V: a_i
		V ->> P: q_i
	end
	note over V: accept/reject

After an interactive proof, the verifier has learned:

• that the claim/theorem is true
• a view of interactions, i.e. the transcript of answers and queries, and the coins that $V$ has tossed.

A view is formally defined as a random variable from the probability distribution over coins of $V$ and interactions with $P$:

$${\text{view}}_V(P,V)[x]=\{(q_1,a_1,q_2,a_2,\dots ,\text{ coin tosses of }V\}$$

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+\text{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+\text{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 honest-verifier zero-knowledge for a language $\mathcal{L}$ if there exists a PPT algorithm $\text{Sim}$ (a simulator) such that $\forall x\in \mathcal{L}$ the following two probability distributions are poly-time indistinguishable:

• ${\text{view}}_V(P,V)[x]$
• $\text{Sim}(x,1^{\lambda })$, here $\lambda$ is for technical reasons and for large $x$ you can just ignore it.

A caveat about $\text{Sim}$ is that we allow it to run in expected-poly-time. Meaning that there may be some very unlucky cases where the algorithm takes a long time, but in expectation it is poly-time.

Also notice that this is for honest verifiers, and we would like the proof to hold for all verifiers. So, our final definition should cover all verifiers.

Definition: An interactive protocol $(P,V)$ is zero-knowledge for a language $\mathcal{L}$ if for every PPT $V^{\ast }$, there exists a PPT algorithm $\text{Sim}$ (a simulator) such that $\forall x\in \mathcal{L}$:

$${\text{view}}_V(P,V)[x]\approx \text{Sim}(x,1^{\lambda })$$

Flavors of Zero-Knowledge

Again, consider the real distribution ${\text{view}}_V(P,V)$ and simulated distribution $\text{Sim}(x,1^{\lambda })$. Based on these, there are flavors of ZK:

• Computationally Indistinguishable Distributions (CZK), where the two distributions are computationally indistinguishable.
• Perfectly Identical Distributions (PZK), where the two distributions are the same.
• Statistically Close Distributions (SZK), where the two distributions are statistically close.

A Simulation for Quadratic-Residue (QR) Proof

Consider the QR proof from above, where we were able to prove with zero-knowledge that we know there exists some $x$ such that $y\equiv x^2(\mathrm{mod}N)$. Check that interactive proof again, what is the $\text{view}$ here? We see that the verifier learns about $s$, it also generates some coin toss value $c$ and finally it learns $z$.

So, ${\text{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:

1. First, pick a random bit $b\in \{0,1\}$.
2. Then, pick random $z\in {\mathbb{Z}}_N^{\ast }$.
3. Compute $s=z^2/y^c$.
4. 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:

1. First, pick a random bit $b\in \{0,1\}$.
2. Then, pick random $z\in {\mathbb{Z}}_N^{\ast }$.
3. Compute $s=z^2/y^c$.
4. If $V^{\ast }(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^{\ast }$ 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 ${\mathcal{L}}_R=\{x:\exists w\text{ s.t. }R(x,w)=\text{ accept}\}$ for poly-time relation $R$.

Definition: $(P,V)$ is a proof of knowledge (POK) for ${\mathcal{L}}_R$ if $\exists$ PPT knowledge extractor algorithm $E$ such that $\forall x\in \mathcal{L}$, in expected poly-time $E^P(X)$ outputs $w$ such that $V(x,w)=\text{ 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 Quadratic-Residue (QR) Proof

We have seen the ZKP for a prover that knows $x$ such that $y\equiv x^2(\mathrm{mod}N)$. 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 $\sigma$ between $G_0$ and $G_1$.

• The prover produces a random graph $H$ and sends it to verifier.
• The prover finds an isomorphism ${\gamma }_0$ from $G_0$ to $H$.
• The prover also finds an isomorphism ${\gamma }_1$ from $G_1$ to $H$.
• The verifier sends a coin toss (bit) $b$ to prover, and prover returns ${\gamma }_b$.
• Verifier checks if $H={\gamma }_b(G_b)$.
• These steps happen repetitively, until some poly-time later if the verifier did not reject so far, it accepts.

Notice that since $H={\gamma }_0(G_0)={\gamma }_1(G_1)$ then $G_1={\gamma }_1^{-1}({\gamma }_0(G_0))$. So, the prover indeed knows $\sigma ={\gamma }_1^{-1}{\gamma }_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 3-Colorability

Do all NP Languages have ZK Interactive Proofs? Proven in [Goldwasser-Micali-Widgerson'86], the answer is YES! They show that if one-way functions exist, then every $\mathcal{L}$ in NP has computational zero-knowledge interactive proofs. The proof will come from an NP-complete problem known as Graph 3-Colorability, hence the title of this section.

The ideas of the proof are as follows:

1. Show that an NP-complete problem has a ZK interactive proof. [GMW87] showed a ZK interactive proof for $\text{G3-COLOR}$ (graph 3-colorability problem). For any other $\mathcal{L}$ in NP, $\mathcal{L}{<}_p\text{G3-COLOR}$ due to NPC reducibility. Every instance $x$ can be reduced to a graph $G_x$ such that if $x\in \mathcal{L}$ then $G_x$ is 3-colorable, and if $x\notin \mathcal{L}$ then $G_x$ is not 3-colorable.
2. 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:

• $\text{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.
• $\text{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.

• $\text{Commit}(b)$ where sender chooses some random $r$ and sends $c:=Enc(b;r)$.
• $\text{Decommit}(c)$ where sender send the same random $r$ and $b$, and receiver rejects unless $c=Enc(b;r)$.

Proving a graph $G$ is $\text{G3-COLORABLE}$

Suppose there is a graph $G=(V,E)$ as in the set of vertices and set of edges, and the prover knows some coloring $\pi :V\to \{0,1,2\}$ which is a mapping that maps a vertex to a color.

1. Prover picks a random permutation of colors $\sigma :\{0,1,2\}\to \varphi$ 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 $\varphi (v):=\sigma (\pi (v))$ for $v\in V$. Then, the prover commits to each newly colored vertex $v$ by running $\text{Commit}(\varphi (v))$ protocol.
2. Verifier selects a random edge $e=(a,b)$ and sends it to prover.
3. Prover runs $\text{Decommit}$ on the colors of edge points $a,b$ and reveals $\varphi (a)$ and $\varphi (b)$.
4. Verifier rejects if $\varphi (a)=\varphi (b)$, otherwise it repeats steps 1-3 and accepts after $k$ iterations.

Now, let's look at the properties of this interactive proof:

• Completeness: if $G$ is 3-colorable, then the honest prover uses a proper 3-coloring & the verifier always accepts.
• Soundness: if $G$ is not 3-colorable, then for all $P^{\ast }$ it holds for $k=|E{|}^2$ (meaning that we have iterations as many as the square of number of edges) that,

$$\mathrm{Pr}[V\text{ accepts}]<{\left(1-\frac{1}{|E|}\right)}^k<\frac{1}{e^{|}E|}$$

• Zero-Knowledge: Easy to see informally, messy to prove formally.

Honest-Verifier Computational ZK Simulator

First, let us examine the view of this interactive proof.

• We have an edge $(a,b)$
• We have the commitments to each vertex coloring as $\text{Commit}(\varphi (v))$.
• We have the decommit of colors $\varphi (a),\varphi (b)$.

Let us show the honest-verifier CZK simulator. For the graph $G=(V,E)$ the simulator will choose a random edge $(a,b)\in E$. Then, it will pick random colors $\varphi (a),\varphi (b)\in \{0,1,2\}$ such that $\varphi (a)\ne \varphi (b)$. For all other vertices $v$, it will set $\varphi (v)$ to some fixed color, and commit to all $\varphi (v)$.

The output of simulated view is:

• We have an edge $(a,b)$
• We have the commitments to each vertex coloring $\text{Commit}(\varphi (v))$.
• We have the decommit of colors $\varphi (a),\varphi (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 $\mathrm{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 $\text{Prog}$, the program has output $y$ such that $y=\text{Prog}(x)$.
• Given encrypted inputs $E(x)$, and some encrypted program $E(\text{Prog})$, the program has output $y$ such that $y=\text{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\ne m_2$. In fact, you can show that there is some value $v$ that when used with a poly-time 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=\text{Protocol}(h,r)$ for some history $h$ and randomness $r$. Furthermore, they will commit to this randomness as $c=\text{Commit}(r)$. This makes honest behavior with ZK possible since $\mathcal{L}=\{\exists r:m=\text{Protocol}(h,r)\text{ and }c=\text{Commit}(r)\}$ is in NP.

Some more real-world applications are:

• Computation Delegation
• ZK and Nuclear Disarmament
• ZK and Forensics
• ZCash: Bitcoin with Privacy and Anonymity
• ZK and Verification Dilemmas in Law

Complexity Theory: Randomized Analogue to NP

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 all-powerful and computationally unbounded, so they are very well allowed to find such hard stuff.

Here is what is different about this IP though; here, the Verifier is doing more than just tossing coins. Here, it actually picks a random isomorphism, and creates the graph $H$ from that!

Completeness and soundness hold for this proof; however, it is not zero-knowledge! This is because if the verifier is not honest, and it's just someone that wants to find out whether some graph $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 $\gamma$, this way the reply from prover does not change the knowledge of verifier.

Arthur-Merlin Games & is AM = IP?

In the Interactive Proof's so far, the Verifier was hiding the result of coin tosses and also was able to do some extra computations, it was a PPT Verifier so it could do anything that the time allows. However, in an Arthur-Merlin game [Babai-Moran'88], the Verifier will only acts as two things:

• A public coin tosses
• A decision function

So, the prover will see in clear the result of coin tosses!

sequenceDiagram
	actor P as Prover (Merlin)
	actor V as Verifier (Arthur)

	note over P, V: claim "x in L"
	loop i = 1, 2, ..., k
	V ->> P: coins_i
	P ->> V: answer_i
	note over V: reject if bad
	end
	note over V: accept

The question here: is Interactive-Proofs more powerful (i.e. can prove more claims) than Arthur-Merlin Games? Is coin privacy necessary?

The answer turns out to be no, AM = IP actually [Goldwasser-Sipser'86]!

Fiat-Shamir Paradigm

You can remove the interaction in AM protocols via Fiat-Shamir Paradigm [Fiat-Shamir'87]. Let that sink in, you are literally removing the interaction from an interactive proof, more specifically, you are removing the coin tossing machine. How is that possible?

Let $H:\{0,1{\}}^{\ast }\to \{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 $coin{s}_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 Fiat-Shamir heuristics is applied to the rest.

However, Fiat-Shamir does not mean you can make all interactive proof's into non-interactive proofs! Yet, many specific AM protocols with an efficient prover can benefit from this heuristic.

Efficient Verification

It was shown by [Fortnow-Karloff-Lund-Nissan'89] and [Shamir'89], that IP can be used to prove many many more problems than what classical proofs are able to! In fact, this brought the question: what if we have something more powerful than IP, for example, what if there is a second prover?

Indeed, as shown in [Benor-Goldwasser-Kilian-Wigderson'88], you can prove a lot more with two provers! In fact, you now have unconditional PZK for NP problems. [Babai-Fortnow-Lund'91] has shown that you can even prove NEXPTIME (non-deterministic exponential time) problems with interactive proofs.

Going even further, [Reichardt-Unger-Vazirani'13] has shown that a classical verifier can verify the computation of two entangled but non-communicating polynomial time quantum algorithms. Finally, a recent work [Ji-Natarajan-Vidick-Wright-Yuen'20] has shown that with two not necessarily efficient quantum provers, and a classical verifier, you can prove all Recursively Enumerable Languages. Kind of meaning like everything; that's one bizarre result!

• SNARK
  • zk-SNARK
  • Blockchain Applications
  • Non-Blockchain Applications
• Arithmetic Circuits
  • Structured vs. Unstructured
• NARK: Non-interactive Argument of Knowledge
  • Requirements of a NARK
  • Trivial NARK
• SNARK: Succinct NARK
  • Trivial SNARK?
  • Preprocessing Setup
  • SNARKs in Practice
  • Knowledge Soundness
• Building a SNARK
• (1) Functional Commitment Scheme
  • Committing to a function
    • Four Important Functional Commitments
  • Polynomial Commitment Scheme (PCS)
    • Trivial Commitment is bad!
    • Zero Test: A Useful Observation
    • Equality Test: A Following Observation
• (2) $\mathcal{F}$ - Interactive Oracle Proof
  • Example: Polynomial IOP for claim $X\subseteq W\subseteq {\mathbb{F}}_p$
  • The IOP Zoo
• SNARKs in Practice

SNARK

In the previous lecture, we have discussed interactive proofs (IP) in general. Now, we will mostly be talking about non-interactive proofs, in particular SNARKs.

A SNARK stands for a succinct proof that a certain statement is true. Succinct here is meaning that the proof is "short". For example, I have a statement:

I know an $m$ such that $\text{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.

zk-SNARK

In the case of a zk-SNARK, the proof reveals nothing about $m$. zk-SNARKs have many applications:

• Private transactions: Tornado Cash, ZCash, IronFish, Aleo (private dApps).
• Compliance: private proofs of solvency & compliance, zero-knowledge taxes
• Scalability: Rollup systems with validity proofs
• and a lot more commercial interest…

Why is there so much commercial interest? Well, things go back to a paper [Babai-Fortnow-Levin-Szegedy'91] where they show that a single reliable PC can monitor the operation of a herd of supercomputers running unrealiable software.

This single reliable PC is a slow and expensive computer. An example of such a machine from today is actually a L1 Blockchain!

Blockchain Applications

SNARKs and zk-SNARKs can be used in many ways within a blockchain.

• Outsourcing Computation: Even without the need of zero-knowledge, an L1-chain can quickly verify that some off-chain service has done some work correctly.
• Scaling with Proof-based Rollups (zkRollup): An off-chain service processes batch of transactions, and the L1-chain verifies a succinct proof that transactions were processed correctly.
• Bridging Blockchains (zkBridge): A source chain locks up some asset, so that it can be used in another destination chain. In doing so, it proves that indeed the asset is locked.
• Private Transactions: A ZKP that a private transaction is valid. Many examples: TornadoCash, ZCash, Ironfish, Aleo.
• Compliance: A proof that a private transaction is compliant with banking laws (e.g. Espresso), or a proof that an exchange is solvent without showing the assets (e.g. Raposa).

Non-Blockchain Applications

Blockchain is really spearheading the development in these areas, but there are many non-blockchain applications of SNARKs too. Here is one example: proving that a photo is taken at some time and at some place.

The initial attempts to this was made via C2PA, a standard of content provenance. With C2PA, the camera that captures the picture will sign its metadata with a secret key (that is assumed not to be extractable by a user). The signed metadata will ensure that the location and timestamp is valid.

However, newspapers and press that display a picture often have to apply some post-processing, such as rescaling, cropping and gray-scaling. There is actually a list of allowed operations by Associated Press. Doing any of these will break the signature, as it can be though of as tampering.

Here is the solution by [Kang-Hashimoto-Stoica-Sun'22] to this problem using zk-SNARKs: suppose that the machine that is doing the post-processing has the photo $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 $\pi$ 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 $\mathbb{F}=\{0,1,\dots ,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:{\mathbb{F}}^n\to \mathbb{F}$ where internal nodes are labeled $+,-,\times$ and inputs are labeled $1,x_1,\dots ,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_{\text{hash}}(h,m)=(h-\text{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_{\text{sig}}(pk,m,\sigma )$ that outputs 0 if $\sigma$ 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\to M\to M\to \dots \to M\to 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: Non-interactive Argument of Knowledge

Suppose you have some public arithmetic circuit $C(x,w)\to \mathbb{F}$ where,

• $x\in {\mathbb{F}}^n$ is a public statement
• $w\in {\mathbb{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 non-interactive.

More formally, a NARK is a triple $(S,P,V)$:

• $S(C)\to (pp,vp)$ is the preprocessing setup, generating public parameters for prover and verifier
• $P(pp,x,w)\to \pi$ is the prover function, generating the proof given the public prover parameters, public inputs and the secret inputs (witness).
• $V(vp,x,\pi )\to \{0,1\}$ is the verification function, either accepting or rejecting a given proof $\pi$, along with the circuit's public verifier parameters and public inputs.

A technical point to be made here is that, all of these algorithms and the adversary are assumed to have an access to a random oracle. This is most likely due to Fiat-Shamir Paradigm we have learned in the previous lecture, but we will get to more details of this later.

Requirements of a NARK

There are 2 requirements of a NARK, and an optional 3rd requirement of zero-knowledgeness:

• Completeness: If the prover does indeed knows the argued knowledge, verifier should definitely accept the proof.

$$\forall x,w:C(x,w)=0⟹\mathrm{Pr}[V(vp,x,P(pp,x,w))=\text{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))=\text{accept}⟹P\text{ knows }w:C(x,w)=0$$

• Zero-knowledge (optional): The view of this interaction, consisting of $(C,pp,vp,x,\pi )$ "reveals nothing new" of $w$.

Trivial NARK

We can easily think of a trivial NARK, that is not zero-knowledge but has the other two properties. Simply, the proof $\pi =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)\to (pp,vp)$ is the preprocessing step, generating public parameters for prover and verifier
• $P(pp,x,w)\to \pi$ is the prover function, where $|\pi |=\text{sublinear}(|w|)$. So, the proof length must be less than linear in the size of witness.
• $V(vp,x,\pi )\to \{0,1\}$ is the verification function, where $\text{time}(V)={\mathcal{O}}_{\lambda }(|x|,\text{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 sub-linear 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)\to (pp,vp)$ is the preprocessing step, generating public parameters for prover and verifier
• $P(pp,x,w)\to \pi$ is the prover function, where $|\pi |=\mathcal{O}(\log (|C|))$. The proof length must be logarithmic to the size of circuit, making the proof very tiny compared to the circuit!
• $V(vp,x,\pi )\to \{0,1\}$ is the verification function, where $\text{time}(V)={\mathcal{O}}_{\lambda }(|x|,\log (|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 $\log (|C|)$ is enough to run the verification.

A zk-SNARK is simply a SNARK proof that reveals nothing about the witness $w$.

Trivial SNARK?

Let us again come back to the trivial proof, where $\pi =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:

1. 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!
2. 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})$.
   1. $S_{init}(\lambda ;r)\to gp$ is a one-time setup, done in a trusted environment. $r$ must be kept secret!
   2. $S_{index}(gp,C)\to (pp,vp)$ is done for each circuit, and nothing here is secret! Furthermore, $S_{index}$ is a deterministic algorithm.
3. 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|$.

The approximations here are made for a circuit that is size $|C|\approx 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))=\text{accept}⟹P\text{ knows }w: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) knowledge-sound for some circuit $C$, if for every polynomial time adversary $A=(A_0,A_1)$ such that:

• $gp\leftarrow S_{init}()$
• $(C,x,st)\leftarrow A_0(gp)$
• $(pp,vp)\leftarrow S_{index}(C)$
• $\pi \leftarrow A_1(pp,x,st)$
• $\mathrm{Pr}[V(vp,x,\pi )=\text{accept}]>\beta$ for some non-negligible $\beta$

there is an efficient extractor $E$ that uses $A_1$ as a black box (oracle) such that:

• $gp\leftarrow S_{init}()$
• $(C,x,st)\leftarrow A_0(gp)$
• $(pp,vp)\leftarrow S_{index}(C)$
• $w\leftarrow E^{A_1(pp,x,st)}(gp,C,x)$
• $\mathrm{Pr}[C(x,w)=0]>\beta -ϵ$ for some negligible $ϵ$ and non-negligible $\beta$.

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:

1. A functional commitment scheme, which is a cryptographic object
2. A suitable interactive oracle proof (IOP), which is an information theoretic object

(1) Functional Commitment Scheme

Well, first, what is a commitment scheme? A cryptographic commitment is like a physical-world envelope. For instance, Bob can put a data in an envelope, and when Alice receives this envelope she can be sure that Bob has committed to whatever value is in it. Alice can later reveal that value.

The commitment scheme has two algorithms:

• $commit(m,r)\to com$ for some randomly chosen $r$
• $verify(m,com,r)\to \text{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:\mathcal{M}\times \mathcal{R}\to C$ where

• $commit(m,r)=H(m,r)$
• $verify(m,com,r)=\text{accept if }com=H(m,r)$

Committing to a function

Choose a family of functions $\mathcal{F}=\{f:X\to 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 $\pi$ is to show that $f(x)=y$ and $f\in \mathcal{F}$. Also, $co{m}_f$ is a commitment to function $f$, but we may also use the notation $\boxed{f}$ to indicate a commitment (think of it like $f$ in an envelope).

Formally, a functional commitment scheme for $\mathcal{F}$ is defined by the following:

• $setup(1^{\lambda })\to gp$ outputs public parameters $gp$.
• $commit(gp,f,r)\to co{m}_f$ is commitment to $f\in \mathcal{F}$ with $r\in \mathcal{R}$.
  • this should be a binding scheme
  • optionally, it can be hiding, which is good for a zk-SNARK
• $eval(P,V)$ with a prover $P$ and verifier $V$, for a given $co{m}_f$ and $x\in X,y\in Y$:
  • $P(gp,f,x,y,r)\to \pi$ (a short proof!),
  • $V(gp,co{m}_f,x,y,\pi )\to \text{accept or reject}$
  • Basically, the $eval$ system is a SNARK proof wof the relations: $f(x)=y$ and $f\in \mathcal{F}$ and $commit(pp,f,r)=co{m}_f$.

Four Important Functional Commitments

There are 4 very important functional commitment types:

• Polynomial Commitments: Committing to a univariate polynomial $f(X)\in {\mathbb{F}}_p^{(\le d)}[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 ${\mathbb{F}}_p^{(\le 1)}[X_1,\dots ,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,\dots ,x_7)=x_1{x}_3+x_1{x}_4{x}_5+x_7$.
• Vector Commitments: Committing to a vector $\vec{u}=(u_1,\dots ,u_d)\in {\mathbb{F}}_p^d$ 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_{\vec{u}}(i)=u_i$. An example vector commitment scheme is Merkle Trees, which you may have heard of!
• Inner-Product Commitments: Committing to a vector $\vec{u}\in {\mathbb{F}}_p^d$. Opening an inner product is done as $f_{\vec{u}}(\vec{v})=(\vec{u},\vec{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 $\mathcal{F}={\mathbb{F}}_p^{(\le d)}[X]$.

• The prover commits to a univariate polynomial $f\in {\mathbb{F}}_p^{(\le d)}[X]$, later, they can prove that:
  • $v=f(u)$ for some public $u,v\in {\mathbb{F}}_p$
  • $\text{deg}(f)\le d$. As this is a SNARK, the proof size and verifier time should be ${\mathcal{O}}_{\lambda }(\log d)$.
• The verifier has access to $(d,co{m}_f,u,v)$.

There are some example PCSs with different mechanisms:

• Using basic elliptic curves: Bulletproofs (short proof, but verifier time is $\mathcal{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={\sum }_{i=0}^d{a}_i{x}^i$. Then, our commitment will be:

• $commit(f,r)=H((a_0,a_1,\dots ,a_d),r)$ as in simply hashing the coefficients and some random variable.
• $eval$ will be done as follows:
  • prover will send $\pi =((a_0,a_1,\dots ,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,\dots ,a_d),r)=co{m}_f$.

This is problematic because the proof size and verification time are linear in $d$, but we wanted a lot smaller values, such as $\log d$.

Zero Test: A Useful Observation

We will now make a really useful observation, which is an essential part of SNARKs and is really what makes SNARKs possible!

Consider some non-zero polynomial with degree at most $d$, shown as $f\in {\mathbb{F}}_p^{(\le d)}[X]$.

• for $r\leftarrow {\mathbb{F}}_p$ it holds that $\mathrm{Pr}[f(r)=0]\le 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\approx 2^{256}$ and $d\le 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\leftarrow {\mathbb{F}}_p$ then $f$ is identically zero with very high probability. This gives you a simple zero test for a committed polynomial!

[Schwartz-Zippel-DeMillo-Lipton] lemma states that this observation holds for multivariate polynomials too, where $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 zero-test observation, we can make another observation that allows to check if two polynomials are equal.

Let $f,g\in {\mathbb{F}}_p^{(\le d)}[X]$. For $r\leftarrow {\mathbb{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 non-interactiveness 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 coin-toss (or a series of tosses) given by the verifier to the prover for everyone to see.

Thanks to Fiat-Shamir Transform, we can transform interactive protocols of this nature into non-interactive proofs! More specifically, Fiat-Shamir Transform can take a "public-coin interactive protocol" which means all verifier randomness is public, and transform it into a non-interactive protocol.

To be technical, Fiat-Shamir Transform isn't safe to transform ALL interactive proofs of this nature, but it is good enough for our needs right now.

Let $H:M\to R$ be a hash function. For the example above, the prover will generate $r:=H(co{m}_f,co{m}_g)$ and this will be used as the random challenge. Since the verifier also has access to $co{m}_f,co{m}_g$ they can generate the same $r$ during verification. That is how the interactiveness is removed!

If $H$ is modeled as a random-oracle, and $d/p$ is negligible (as we discussed in zero-test), then this is a SNARK. In practice, SHA256 is used for the hash function.

Is this a zk-SNARK? No, because the verifier learns the result of evaluating the polynomials at point $r$.

(2) $\mathcal{F}$ - Interactive Oracle Proof

The goal of an $\mathcal{F}$-IOP is to boost a commitment to function $f\in \mathcal{F}$ to become a SNARK for general circuits. For example, you could have a polynomial function family $\mathcal{F}={\mathbb{F}}_p^{(\le d)}[X]$ and with $\mathcal{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\in {\mathbb{F}}_p^n$. An $\mathcal{F}$-IOP is then a proof system that proves $\exists w:C(x,w)=0$. In other words, some prover knows a witness $w$.

• Setup: $S(C)\to (pp,vp)$ where $vp=(\boxed{f_0},\boxed{f_{-1}},\dots ,\boxed{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, ..., (t-1)
	P ->> V: oracle [f_i ∈ F]
	note over V: r_i ← F_p
	V ->> P: r_i
	end

	P ->> V: oracle [f_t ∈ F]
	note over V: verify^(f_{-s}, ..., f_t)(x, r_1, ..., r_(t-1))

Let's digest what is happening in this interactive proof:

1. 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 $\boxed{f_1}$.
2. The verifier samples a uniformly random field element $r_1$, and sends it back to the prover.
3. Steps 1 and 2 happen for $t-1$ rounds.
4. Finally, the prover sends one last oracle $\boxed{f_t}$, an oracle for function $f_t$.
5. 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.

$$\exists w:C(x,w)=1⟹\mathrm{Pr}[V\text{ accepts}]=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,\dots ,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.
• Zero-knowledge (optional): The view of this IOP "reveals nothing new" of $w$.

Example: Polynomial IOP for claim $X\subseteq W\subseteq {\mathbb{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\subseteq W\subseteq {\mathbb{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.

1. Prover computes two polynomials $f$ and $g$, a polynomial with roots in $W$ and $X$ respectively. It does that by the following:
   1. $f(Z)={\prod }_{w\in W}(Z-w)$
   2. $g(Z)={\prod }_{x\in X}(Z-x)$
2. Verifier computes $g(Z)$ the same way, because $X$ is public.
3. Prover computes a quotient polynomial $q(Z)=f/g\in {\mathbb{F}}_p^{(\le d)}[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\subseteq 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!
4. Prover sends oracles of $f$ and $q$ to the verifier. In practice, it uses a polynomial commitment scheme and sends commitments to these functions, $\boxed{f}$ and $\boxed{q}$.
5. 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.
6. Verifier queries the value of $\boxed{f}$ and $\boxed{q}$ at point $r$, and also computes $g(r)$. Denote these as $w,q^{\prime },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.
7. Verifier checks if $x\times q^{\prime }=w$. This is only possible if $q(Z)=f/g$ indeed, think of it like checking $f\times 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 Poly-IOP is "compiled" into a SNARK by adding in the PCS (poly-commitment scheme) steps.

The IOP Zoo

There are many SNARKs for general circuits.

You construct the IOP, and use the relevant commitment scheme to do the commitments and queries; et viola, you have a SNARK. However, the examples we have were interactive so far, but a SNARK is non-interactive. To do that final touch, you use the Fiat-Shamir Transform (using hash functions) to make the entire thing non-interactive.

SNARKs in Practice

flowchart LR
	D[DSL] -- compiler --> S[SNARK-friendly format]
	S -- pp, vp --> B[SNARK backend prover]
	X[x, witness] --> B
	B --> proof

In practice, you wouldn't want to write the entire circuit yourself. We use DSLs (domain-specific languages) to do that for us.

Some DSL examples are:

• Circom
• ZoKrates for Ethereum
• Leo for Aleo
• Zinc for zkSync
• Cairo for StarkNet
• Noir
• GNARK
• …

The DSL compiles the circuits for you, and outputs a SNARK friendly format. There are several formats:

• Circuit
• R1CS (Rank-1 Constraint System)
• EVM Bytecode (yea, that is possible!)
• …

Finally, with the public parameters $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 $\varphi$
• Arithmetic Circuits
  • Rank-1 Constraint System (R1CS)
  • Matrix Definition of R1CS
  • Example: Writing R1CS of an AC
• Tutorial: Circom - Using a HDL for R1Cs
  • Example: $z=x\times y$
  • Example: $y=f^n(x)$ where $f(x)=x^2$
  • Example: Non-zero & Zero
  • Example: Sudoku Solution
• Tutorial: Arkworks - Using a Library
• Tutorial: ZoKrates - Compiling Programs to Circuits
• Recap: The ZKP Toolchains

Programming ZKPs

Suppose you have an idea for an application & you want to use ZK in it. What do you do?

flowchart TD
	subgraph this lecture
	idea --program--> p[program]
	p --compile--> c[circuit/constraint-system]
	end
	c --setup--> pp[public params]
	pp --prove--> zkp[ZK-proof]
	pp --> verify
	zkp --> verify
	verify --> out[accept/reject]

In this lecture, we will be doing the following:

1. Have a big picture on ZKP programmability
2. Example: Use an HDL (hardware-description language), such as Circom
3. Example: Use a library, such as Arkworks
4. Example: Use a programming language & compiler, such as ZoKrates
5. Overview of prominent ZKP toolchains

Recap: ZKP for a predicate $\varphi$

Let us remember what ZKP does. Suppose you have a predicate $\varphi$, with some public inputs $x$ and private inputs (witness) $w$. For example, $\varphi =$ I know a $w$ such that $x=\text{SHA256}(w)$.

• Prover has access to $\varphi ,x,w$.
• Verifier has access to $\varphi ,x$.
• Proof $\pi$ will prove that $\varphi (x,w)$ holds, without revealing $w$.

However, the key question here is: what could $\varphi$ be? What are some other examples? In theory, $\varphi$ 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, $\varphi$ 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 ${\mathbb{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\times w_0\times w_0=x$
• $w_1\times 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[=]

Rank-1 Constraint System (R1CS)

R1CS is a format for ZKP Arithmetic Circuit (AC). It is a very commonly used format. Here is how it is defined:

• $x$ is a set of field elements $x_1,x_2,\dots ,x_l$.
• $w$ is a set of field elements $w_1,w_2,\dots ,w_{m-l-1}$
• $\varphi$ is made up of $n$ equations with the form $\alpha \times \beta =\gamma$ where $\alpha ,\beta ,\gamma$ are affine combinations of variables mentioned in the above bullet points.

Let's see some examples of $\alpha \times \beta =\gamma$.

• $w_2\times (w_3-w_2-1)=x_1$ is okay.
• $w_2\times w_2=w_2$ is okay.
• $w_2\times w_2\times 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\times w_2=w_4$ is okay.
  • $w_2\times 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\in {\mathbb{Z}}_p^l$ is a vector of $l$ field elements.
• $w\in {\mathbb{Z}}_p^{m-l-1}$ is a vector of $m-l-1$ field elements.
• $\varphi$ is made up of 3 matrices: $A,B,C\in {\mathbb{Z}}_p^{n\times m}$

Now, we define a vector $z=(1||x||w)\in {\mathbb{Z}}_p^m$ which has $m$ elements. The rule for this system is that the following equation must hold:

$$Az\circ Bz=Cz$$

Here, $\circ$ means the element-wise product of these.

┌───────┐┌┐   ┌───────┐┌┐   ┌───────┐┌┐
|.......||| o |.......||| = |.......||| //--> every row here corresponds to
|   A   |└┘   |   B   |└┘   |   C   |└┘ // some rank-1 constraint!
|       |     |       |     |       |
└───────┘     └───────┘     └───────┘

Example: Writing R1CS of an AC

Consider the following AC:

flowchart LR
	w0((w_0)) --> m1[x]
	w1((w_1)) --> m1
	w1 --> m2
	x0((x_0)) --> a1
	m1 --w_2--> a1[+]
	x0 --> m2[x]
	a1 --w_3--> =
	m2 --w_4--> =

Here, we have a public input $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 $\alpha \times \beta =\gamma$ as discussed before, as one equation per gate!

• $w_0\times w_1=w_2$
• $w_3=w_2+x_0$ (notice that left side is actually $w_3\times 1$)
• $w_1\times 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).

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:

1. Sets variable values
2. Creates R1CS constraints

Example: $z=x\times 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 sub-circuit if imported by some other)
• A signal is a wire, can be input, output or just some intermediate variable.
• <-- operation sets signal values.
• === creates a constraint, which must be Rank-1. So, one side is linear and other is quadratic. You can't do things like x * 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 hard-code when you are instantiating the component.
• You can have arrays of signals.
• You can have variables (defined with var). These are different from signals, they are mutable & are evaluated at compile time.
• You can have loops, such as the good ol' for loop.
• You can also have if - else statements.
• You can access index i in an array with arr[i].

Example: Non-zero & Zero

template NonZero(n){
	signal input in;
	signal inverse;

	inverse <-- 1 / n; // not ok with R1CS
	1 === in * inverse; // is ok with R1CS
}

template IsZero() {
	signal input a;
	signal input b;

	component nz = NonZero();

	// check a is non-zero
	nz.in <== a;

	// b must be 0 for this to hold
	0 == a * b;

	// you could have done this much simpler as:
	// 0 === b;
	// but hey, this is an educational example! :)
}

component main {public [a, b]} = IsZero();

Here, NonZero is a sub-circuit used by IsZero. Within NonZero, we are checking if some input is not 0. However, constraints only check for equality, we don't have something like a !=== b. To check if something is non-zero, we can check if it has an inverse!

To do that, we do inverse <-- 1 / n but hey, this isn't R1! Is that a problem? Well, <-- is just an assignment operator, not a constraint! So, we can do such a thing here; in fact, signal assignment without constraints are a lot more capable than constrainted assignments. The constraints itself is in the next line: 1 === in * signal, which is R1.

Also notice that IsZero uses NonZero within, and it does that by instantiating the sub-circuit as nz. You can access the signals in a circuit with . operator, such as nz.in.

Example: Sudoku Solution

This one is a rather large example, with quite a lot of code too. I will just take notes of the circuit, for the code itself please go to https://github.com/rdi-berkeley/zkp-course-lecture3-code/tree/main/circom.

We would like to prove that we know the solution to a sudoku puzzle.

• The public input $x$ will be the initial setting of the sudoku board, with 0 for empty cells and some integer $1\le i\le 9$ for non-empty cells.
• The private input $w$ (witness) will be our solution, again as an array of numbers.
• Our predicate $\varphi$ is that we know the solution to the given Sudoku setting in the public input.

The inputs will be given as 2-dimensional arrays of size $n\times 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\times 3$ groups of cells (as in Sudoku) where every number occurs once in each group.

Here is the circuit, along with it's sub-circuits.

// Assert that two elements are not equal.
// Done via the check if in0 - in1 is non-zero.
template NonEqual() {
	signal input in0;
  signal input in1;

  // do the inverse trick to check for zero
  signal inverse;
	inverse <-- 1 / (in0 - in1);
	1 === (in0 - in1) * inverse;
}

// Assert that all given values are unique
template Distinct(n) {
  signal input in[n];

  // create a non-equal component for each pair
  component neq[n][n];
  for (var i = 0; i < n; i++) {
		for (var j = 0; j < i; j++) {
			neq[i][j] = NonEqual();
			neq[i][j].in0 <== in[i];
			neq[i][j].in1 <== in[j];
		}
	}
}

// Assert that a given number can be represented in n-bits
// Meaning that it is in range [0, 2^n).
template Bits(n) {
	signal input in;

	signal bits[n];
	var bitsum = 0;
  for (var i = 0; i < n; i++) {
		bits[i] <-- (in >> i) & 1;
    bits[i] * (bits[i] - 1) === 0; // ensure bit is binary
    bitsum += bitsum + 2 ** i * bits[i];
	}
  bitsum == in;
}

// Check if a given signal is in range [1, 9]
template OneToNine() {
  signal input in;
  component lowerbound = Bits(4);
  component upperbound = Bits(4);
  lowerbound.in <== i - 1; // will work only if i >= 1
  upperbound.in <== i + 6; // will work only if i <= 9
}

// Main circuit!
template Sudoku(n) {
  signal input solution[n][n];
  signal input puzzle[n][n];

	// first, let's make sure everything is in range [1, 9]
	component inRange[n][n];
  for (var i = 0; i < n; i++) {
		for (var j = 0; j < n; j++) {
			inRange[i][j] = OneToNine();
			inRange[i][j].in <== solution[i][j];
		}
	}

  // then, let's make sure the solution agrees with the puzzle
	// meaning that non-empty cells of the puzzle should equal to
  // the corresponding solution value
  // other values of the puzzle must be 0 (empty cell)
  for (var i = 0; i < n; i++) {
		for (var j = 0; j < n; j++) {
      // this is valid if puzzle[i][j] == 0, OR
			// puzzle[i][j] == solution[i][j]
			puzzle[i][j] * (puzzle[i][j] - solution[i][j]) === 0;
		}
	}

  // ensure all the values in a row are unique
  component distinctRow[n];
	for (var row = 0; row < n; row++) {
		distinctRow[row] = Distinct(9);
		for (var col = 0; col < n; col++) {
			distinctRow[row].in[col] <== solution[row][col];
		}
	}

	// ensure all the values in a column are unique
  component distinctColumn[n];
	for (var col = 0; col < n; col++) {
		distinctColumn[col] = Distinct(9);
		for (var row = 0; row < n; row++) {
			distinctColumn[col].in[row] <== solution[row][col];
		}
	}

  // ensure all the values in each 3x3 square is unique
  // left as an exercise to the reader :)
}

component main{public[puzzle]} = Sudoku(9);

That is very cool, right?

So yea, Circom is great and it has direct control over constraints. However, using a custom language has it's own drawbacks. An alternative is to use an already known high-level language (e.g. Rust, Go) and have a library to help you write circuits in there.

Tutorial: Arkworks - Using a Library

The most important object in a library will be the constraint system. This guy will keep state about R1CS constraints and variables, and we will interact with it while we write our "circuit".

The key operations here will be:

• Creating a variable

cs.add_var(p, v) -> id;
// cs: constraint system
// p:  visibility of variable
// v:  assigned value
// id: variable handle

• Creating a linear combination of variables

// make an empty linear combination at first
lc := cs.zero();
// now fill it with variables
lc.add(c, id) -> lc';
// id: variable handle from before
// c:  coefficient
// this correspod to the following linear combination:
//   lc' := lc + c * id

• Adding a constraint

// suppose you have some linear constraints lc_A, lc_B, lc_C
cs.constraint(lc_A, lc_B, lc_C)
// adds a constraint lc_A * lc_B = lc_C

These are pretty high-level, so let's take a look at a more realistic example.

fn and(cs: ConstraintSystem, a: Var, b: Var) -> Var {
  // do a simple bitwise AND on values
	let result = cs.new_witness_var(|| a.value() & b.value());
  // constraint: a * b = result, works like AND in booleans
  self.cs.enforce_constraint(
		lc!() + a,
		lc!() + b,
		lc!() + result,
	);
	result // return new result as Var
}

This is cool and all, but it has quite a bit of boilerplate, and seems very tedious & error-prone. So, we would really like a language abstraction somehow, making the library a lot more friendly.

Here is an example, where we can write the same code but apply it in a Boolean struct and overload the and operator.

struct Boolean { var: Var };

impl BitAnd for Boolean {
	fn and(self: Boolean, other: Boolean) -> Boolean {
	 // do the same code above...
		Boolean { var: result } // return result wrapped in Boolean
	}
}

// later in code, you can do stuff like this:
let a = Boolean::new_witness(|| true);
let b = Boolean::new_witness(|| false);

There are many different libraries:

• libsnark: gadgetlib (C++)
• arkworks: r1cs-std + crypto-primitives (Rust)
• Snarky (OCaml)
• GNARK (Go)
• Bellman (Rust)
• PLONKish (Rust)

At this point in lecture, we have an Arkworks tutorial. Please see the lecture itself for that, I will be omitting this part.

Tutorial: ZoKrates - Compiling Programs to Circuits

In the Circom example, we wrote the circuit ourselves. In the Arkworks example, we used a nice high-level language but still had to explicitly specify the wiring and constraints. What if we could have a programming language, that takes in a program and compiles it to R1CS with all it's wires and constraints?

Meet ZoKrates, a tool that does what we have just described.

type F = field;

def multiplication(public F x, private F[2] ys) {
	field y0 = y[0];
	field y1 = y[1];
  assert(x = y0 * y1);
}

def repeated_squaring<N>(field x) -> field {
	field[N] mut xs;
	xs[0] = x;
	for u32 i in 0..n {
		xs[i + 1] = xs[i] * xs[i];
	}
	return xs[N];
}

def main (public field x) -> field {
	repeated_squaring::<1000>(x);
}

ZoKrates has quite a bit of capabilities:

• Custom types via structs
• Variables that contain values during execution/proving
• Visibility is annotated (private/public)
• assert creates constraints
• Integer generics <N>
• Arrays & array accesses
• Variables, which are mutable unlike signals
• Fixed-length loops
• If-else statements

I am omitting the example from this page, please see the lecture for the code.

Recap: The ZKP Toolchains

We have seen that there are generally 3 options:

• HDL: A language for describing circuit synthesis.
  • pros: clear constraint & elegant syntax
  • cons: hard to learn & limited abstraction
• Library: a library for describing circuit synthesis
  • pros: clear constraint & as expressive as it's host language
  • cons: need to know that language & few optimizations
• PL + Compiler: a language, compiled to a circuit
  • pros: easiest to learn & elegant syntax
  • cons: limited witness computation

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
  • Soundness vs. Knowledge Soundness
  • Public Verifiability
• Trivial SNARK is not a SNARK
  • Slightly trivial SNARKs from Interactive Proofs (IPs)
  • Actual SNARKs!
• Functional Commitment Schemes
  • Merkle Tree
    • Example: Committing to a univariate $f(x)\in {\mathbb{F}}_n^{(\le d)}[X]$
• Recall: SZDL Lemma
• Low-Degree & Multilinear Extensions
  • Example: $f:{0,1}^2\to \mathbb{F}$
  • Relation to Interactive Proofs
  • Quick Evaluation of MLEs
• The Sum-Check Protocol
  • Analysis
  • Application: Counting Triangles in a Graph
• SNARK for Circuit-Satisfiability
  • Transcript
  • Polynomial-IOP for SNARK
    • Step 1: Moving from $h$ to $g_h$
    • Step 2: Proving $g_h$

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 $\text{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 polynomial-time $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)\to \mathbb{F}$$

where $x\in {\mathbb{F}}^n$ is some public statement and $w\in {\mathbb{F}}^m$ is some secret witness. Let us look at the types of "soundness" with this example:

• Soundness: $V$ accepts $⟹\exists w:C(x,w)=0$
• Knowledge soundness: $V$ accepts $⟹P$ "knows" $\exists 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 vice-versa is true too, where knowledge soundness means something but you don't really care about soundness. This is usually in cases where the soundness is trivial. For example, $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 Fiat-Shamir Transform [Fiat, Shamir'87], where a public-coin protocol (an IP where randomness is public) can be made public & non-interactive! The trick is to use a random oracle model (via a hash function in practice) to generate the required randomness on your own.

So, in summary:

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 non-interactive when you think about it 🟢

Slightly trivial SNARKs from Interactive Proofs (IPs)

Let us look at the trivial proof from an interactive proof perspective (making it slightly less trivial). Now, the prover will send $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 non-interactive using Fiat-Shamir transform. The trick there is to use a cryptographic hash function as a source of randomness 🟢

Functional Commitment Schemes

We had talked about some very important functional commitment schemes:

• Polynomial Commitments: Committing to a univariate polynomial $f(X)\in {\mathbb{F}}_p^{(\le d)}[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 ${\mathbb{F}}_p^{(\le 1)}[X_1,\dots ,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,\dots ,x_7)=x_1{x}_3+x_1{x}_4{x}_5+x_7$.
• Vector Commitments: Committing to a vector $\vec{u}=(u_1,\dots ,u_d)\in {\mathbb{F}}_p^d$ 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_{\vec{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 root-to-leaf path.
  • Verifier checks if the hashes are consistent with the root hash.
  • The size of this proof to reveal a value is $\mathcal{O}(\log n)$ 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)\in {\mathbb{F}}_n^{(\le d)}[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)\in {\mathbb{F}}_7^{(\le d)}[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),\ast ]$$

Here, $\ast$ 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 $|{\mathbb{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\in {\mathbb{F}}_p^{(\le d)}[X]$ what is the probability that $f(r)=0$ for some $r\in {\mathbb{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 $|{\mathbb{F}}_p|$. So in short:

$$\underset{r\in {\mathbb{F}}_p}{\mathrm{Pr}}[f(r)=0]\le \frac{d}{|{\mathbb{F}}_p|}$$

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 "zero-test" fact, you can obtain an "equality-test" with the same reasoning:

$$\underset{r\in {\mathbb{F}}_p}{\mathrm{Pr}}[f(r)=q(r)]\le \frac{d}{|{\mathbb{F}}_p|}$$

So if you have two polynomials $f,q$ and they both evaluate to the same thing, chances are they are the same polynomial!

Schwarts-Zippel-Demillo-Lipton Lemma is a multi-variate generalization of this fact. Let $f\ne 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^2{x}_2+x_1{x}_2$ has a total degree $3=2+1$ due to the first term. The lemma states that:

$$\underset{r\in {\mathbb{F}}_p^l}{\mathrm{Pr}}[f(r)=q(r)]\le \frac{d}{|{\mathbb{F}}_p|}$$

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.

Low-Degree & Multilinear Extensions

We now have some math to do, but do not fear; it will be quite useful!

Definition [Extension]: Given a function $f:\{0,1{\}}^l\to \mathbb{F}$, a $l$-variate polynomial $g$ over $\mathbb{F}$ is said to extend $f$ if $\forall x\in \{0,1{\}}^l:f(x)=g(x)$.

Definition [Multilinear Extension]: Any function $f:\{0,1{\}}^l\to \mathbb{F}$ has a unique multilinear extension (MLE) denoted $\tilde{f}:{\mathbb{F}}^l\to \mathbb{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^2{x}_2$ is not.

Example: $f:\{0,1{\}}^2\to \mathbb{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 $\tilde{f}:{\mathbb{F}}^2\to \mathbb{F}$ which is:

$$\tilde{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)\in \{0,1{\}}^2$ it holds that $f(x_1,x_2)=\tilde{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 non-multilinear extensions of $f$. For example:

$$g(x_1,x_2)=-x_1^2+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\to \mathbb{F}$, for any point $r\in {\mathbb{F}}^l$ there is an $\mathcal{O}(2^l)$-time algorithm for evaluating the MLE $\tilde{f}(r)$.