☰

Introduction

Whether or not we are in a cryptocurrency bubble is not what drives the discussion of zk-SNARKs. Yes, zcash is the currency that introduced many people to the topic of this write up; however, the effect of zk-SNARKs could be wider reaching than a cryptocurrency.

This article will be broken up into three parts, each meant to explain the topic to a seperate audience. These audiences are the average adult, an undergraduate focusing on computer science or math, and a graduate student interested in cryptography or some complexity theoritic topic or another. Below is a dependency graph to help in navigating the sections in this article. Note that the dotted line indicates that section two is a "soft prerequisite" for understanding section 3. This is because section 3 assumes graduate level maturity. If you are not comfortable with the material in this section, try revisiting it after reading section 2.

image

For all three audiences, it will be benefitial to know what zk-SNARK is an acronym of. Yeah it’s a catchy thing to say, but it is quite descriptive of an acronym. A zk-SNARK is a zero-knowledge, Succinct, Non-interactive, ARgument of Knowledge and that really is a mouthfull.

Motivation

When trying to understand a cryptographic primitive it always helps to understand why it exists. In other words, what problem does it solve? In doing so, we will have the necessary motivation to drive future research and curiosity! Let’s get to it by first introducing our main characters Alice and Bob. Picture this: our protaganists reside in a dystopian society in the near future where government surveillance runs rampant. Alice and Bob are attempting to orchestrate a rebellion right under the nose of the black suits in office. They have found a hide out to base their operation from, but need a method of proving that a member knows the secret word for getting in. Moreover, no one should be able to learn the secret word or how to find it even if a third party person was listening in.

1. ELI5: A Primer For The Average Person

The above scenario is admittedly very contrived; however, the above can be reworded into the following problem: how can we prove the integrity of encrypted data? zk-SNARKS are the solution to this problem. To answer why, we first delve into understanding the notion of a proof and knowledge.

1.1. What Is A Proof?

As humans, we prove statements every day. We do so without even considering what the definition of a proof is and so let us slow down to consider a proof of a mathematical statement. Such proofs have the following properties:

  1. They consist of a static sequence of statements that follow in some logical order. These statements are therefore either axioms of mathematics or are derivational rules.

  2. The proof itself is at least as important as the theorem it is proving.

Now, this type of proof would not help us in answering our question of proving integrity over encrypted data. Why? Once the proof is read out loud, it is trivially replicable and recitable. Therefore, a third party can trick us of say their identity as a fellow rebel. Looking ahead at the solution, one aspect of mathematical proofs remains. There are two parties present in such a proof system: the Prover and the Verifier.

1.2. What Is Knowledge?

I’m no philosopher. Pass!

1.3. What Does It Mean To Gain Knowledge?

Informally, one gains no knowledge from an interaction if and only if said person does not receive the proof for something that was otherwise infeasible for them to find themselves. For example, if someone told me that \(1 + 1 = 2\), then I have gained no knowledge because I can do at least that much arithmetic. If, however, someone were to show me a proof of extraterrestial life forms, then I have certainly gained some knowledge.

1.4. Bringing It All Together

We now possess the necessary intuition to derive an informal definition of a zk-SNARK. Recall that we know the following:

With this information, we outline the following properties necessary for a protocol that solves our problem:

2. Diving Deeper: zk-SNARKS for the curious

We all ideally understand zk-SNARKs at the level of an average person, but we’ll be formalizing the above notions for those of us who remain curious. I want to be very clear that the definition outlined in this section is not complete and is ignoring some very small technical details that are integral to the study of zk-SNARKs. The decision to omit these details is, in my opinion, necessary to able to discuss this primitive at the level of an undergraduate in Computer Science or mathematics without explaining everything taught in a graduate cryptography course. With that out of the way, let’s brush up on some necessary background material!

2.1. Prerequisites

Note: I will be assuming knowledge of asymptotic analysis and the level of mathematical maturity after having taken a discrete mathematics course.

2.1.1. P and NP

Definition: The complexity class P is the set of all problems \(\mathcal{P}\) that can be solved in polynomial time.

Definition: The complexity class NP is the set of all problems \(\mathcal{P}\) that can be verified in polynomial time when given a potential solution \(\pi\) to an instance of the problem \(x\). Here \(\pi\) acts as a proof of sorts for the membership of \(x\) in the set of inputs with a solution for \(\mathcal{P}\).

Remark: Given these defintions, we know that P \(\subseteq\) NP. Why is this the case? If we could find the solution to a problem, then of course we could verify the validity of any solution to said problem! However, the literal million dollar question is does P \(=\) NP?

2.1.2. Algorithms and Randomness

We later define our prover and verifier in terms of an algorithm and so we need to introduce some notation. An algorithm is said to accept its input if it outputs one after halting. On the other hand, if an algorithm outputs 0, then we say it rejected its input. Lastly, an important class of algorithms to consider are probabilistic polynomial time algorithms. These are algorithms that terminate in a polynomial number of steps but are allowed some randomness. This randomness is expressed through an algorithms ability to flip coins. Therefore, the probability of an event occuring related to a probabilistic polynomial time algorithm is always over the random coin tosses said algorithm has access to.

2.1.3. Negligible Functions

A negligible function is something that is thrown around all the time in the cryptographic literature. It is absolutely essential to know what functions are negligible. We should all be asking why are negligible functions used so often? The answer lies in the necessity to capture the notion of certain events being so unlikely that we need not consider them. Such events include breaking the security of algorithms which we discuss in the section regarding indistinguishability.

An intuitive explanation of an event being unlikely is something like a function being exponentially small. In other words a function is small if it grows slower than every polynomial function. This is a definition that we decided on because it satisfies our needs.

Definition: A function \(\mu\) is negligible if and only if \(\forall{c} \in {\mathbf N}\), \(\exists n_0 \in {\mathbf N}\) such that \(\forall n \geq n_0\) it is the case that \(\mu(n) < n^{-c}\).

2.1.4. Indistinguishability

Cryptography would be useless if we cannot guarantee the security of our primitives when under attack by adversaries. Most cryptographic primitives (if not all) are randomized algorithms. In effect, they are allowed to flip some number of coins during their execution. Because our primitives are randomized algorithms, they output a random variable with some distribution. Ideally, this random variable would distributed uniformally.

Sanity Check: Why would we want the distribution of the random variable outputted by some cryptographic primitive to be distributed uniformally?

There are three notions of indistinguishability and they are in order of decreasing strength: perfect, statistical, and computational.

Definition: A random variable \(X\) is perfectly indistinguishable from the uniform distribution \(U\) if the distribution of \(X\) is equivalent to \(U\). The notation used for this is \(X \equiv U\) or \(X \stackrel{p}{=} U\).

Definition: A random variable \(X\) is statistically indistinguishable from the uniform distribution \(U\) if the total variation distance between \(X\) and \(U\) is negligible. Intuitivally, this is an information theoretic argument saying that there does not exist a function or algorithm that can pull these two distributions any further apart. The notation used for this is \(X \stackrel{\Delta}{=}U\).

Definition: A random variable \(X\) is computationally indistinguishable from the uniform distribution \(U\) if for every probabilistic polynomial time algorithm \(A\) and for all security parameter \(k \in {\mathbf N}\): \[\bigg\lvert \Pr[D(X) = 1] - \Pr[D(U) = 1]\bigg\rvert = \text{ negl}(k)\] The notation used for this is \(X \stackrel{c}{=}U\).

2.1.5. Proof Systems

Recall that a proof involves a prover and a verifier. Therefore, we have the following definition of a a proof system:

Definition: A proof system is a pair of algorithms \((P, V)\) for a problem \(\mathcal{P}\) such that below properties are satisfied:

  1. Efficiency: The verifier must run in polynomial time and is allowed access to some randomness.

  2. Completeness: If the prover has a correct proof for the validity of a statement related to an instance of the problem \(\mathcal{P}\), then the verifier must be convinced: \[\Pr\bigg[V(x, \pi) = 1 \Bigg\vert \pi = P(x)\bigg] \geq \frac{2}{3}\]

  3. Soundness: The verifier cannot be tricked by any prover \(P^*\) into believing statements about instances to the problem with no valid solution: \[\Pr\bigg[V(x, \pi) = 1 \Bigg\vert \pi = P^*(x)\bigg] \leq \frac{1}{3}\]

Remark: We allow the verifier to fail with a probability of a third for completeness because we repeat the protocol for any proof system to drive down the probability of failure. A similar argument can be made for the error probability of the soundness property.

2.2. Adding Some Formalities

We are not too far from being able to have some formality when discussing the definition of a zk-SNARK. At this point, we only really have a basic proof system. We’re missing quite a bit from our zk-SNARK acronym so let us dive right in!

2.2.1. Non-interactive Proof Systems

Because I don’t expect everyone to know what an interactive proof system is, the above definition for a proof system suffices for the level of understanding we are going for with zk-SNARKs in this section. Do note that the above definition is missing a detail that will be touched on extensively in the last section of this write up.

2.2.2. From Proof Systems to ARgument Systems

Looking back at our property for efficiency of a proof system, its clear that I did not specify any requirements for the prover. This is because in many proof systems, we do not care about how long it takes for the prover to come up with the a proof. In real life, all I care about is if I am convinced. Yes, this is quite selfish but such is life. Instead, we want an efficient verification process; therefore, the majority of the work falls on the shoulders of the prover in a proof system. A prover is computationally unbounded often times for this very reason. Now, this is interesting. There is a clear discrepancy between the amount of work expected of the prover and the amount of work expected of the verifier, but this imbalance in power or efficiency should remind us of something––NP! The complexity class NP can be thought of a class for problems with a proof system.

Sanity Check: Can you define the complexity class NP in terms of a proof system? Don’t be afraid to redefine soundness and completeness to satisfy your needs. This is math and as mathematicians, we are the wizards!

This is all great, but do we really have unlimited time for provers. Say you are able to verify something quickly. If the prover cannot supply me with a proof to verify before life on Earth ends, then what good is our proof system. There are reasons to consider proof systems for which the prover is computationally unbounded; however, we can relax our definition of a proof system by requiring that the prover is computationally bounded. One might ask: "how is this a relaxation of the problem?" Well our definition will now account for a set of provers that is less powerful. Therefore, possibly malicious provers are also less powerful and the above properties are easier to satisfy. We refer to this "relaxed" definition as a Computationally Sound Non-interactive Proof or a Non-interactive ARgument. Woohoo, we have NAR!

2.2.3. Succinctness

The proofs the verifier receives should ideally be small. Why? A smaller proof that satisfies the above conditions for a NAR can only improve the efficiency of the verifier. So the question to ask is more along the lines of why wouldn’t we want this? More formally, we add the following property to our NAR:

5. Succinctness: The size of the proof is polynomial in the size of the problem instance. In other words, for an instance \(x\) of problem \(\mathcal{P}\), \(\pi = p(\lvert x \rvert)\) for some polynomial \(p\) where \(\pi\) is the output of \(P(x)\).

The scoreboard has us at SNAR. What’s left?

2.2.4. Zero-knowledge and the Simulation Paradigm

Previously, we defined the property of zero-knowledge to be such that "the verifier does not learn the prover’s proof and cannot use it later". We have some new tools in our tool belt and we will use them to formulate a definition that satisfies our needs. First, what does it mean to "learn" a proof? I argue that this means the verifier is able to replicate the proof for any input with a satisfying solution to the problem our proof system is defined under. How can we guarantee this cannot happen?

In a non-interactive proof system, the verifier sees only the proof \(\pi\) and the input \(x\). If the verifier learns nothing outside of these two from the protocol, then there is no way the verifier could have learned the proof. To formalize this notion, we introduce the idea of a simulator. A simulator \(S\) is an algorithm that outputs a random variable. Because the output of the protocol between the prover and verifier is a random variable as well, we want the distribution of these random variables to be indistinguishable. The level of indistinguishability can vary meaning that our proof system can have perfect, statistical, or computational zero-knowledge. More formally,

Definition: A proof system \((P, V)\) for a problem \(\mathcal{P}\) is zero-knowledge if there exists a probabilistic polynomial time simulator \(S\) such that for all \(x\) with solutions to \(\mathcal{P}\), \[\{x, P(x)\} \stackrel{p/\Delta/c}{=} S(x)\]
Sanity Check: I heavily relied on notational macros to shorten the definition. Rewrite the definition for the three different notions of zero-knowledge more explicitly. Once you have done this, we now have zk-SNARs. One more letter...

2.2.5. zk-SNAR of Knowledge

Thus far, we have discussed proof systems for which a prover can prove whether or not a statement is true. Just as a reminder, the statements are asked by the verifier and are of the form "does \(x\) have a solution to the problem \(\mathcal{P}\)". Therefore, with our current definitions, we can answer the question "is \(x\) the secret word for entrance?" Really we want someone to prove why \(x\) is the secret word for entrance. This is the idea behind a proof of knowledge.

Now, we need to formulaize this notion of the prover "knowing a secret". Recall that the zero-knowledge property of the proof system we are working with is such that the prover is not going to just reveal their proofs of anything. However, if a prover knows something, then we should be able to extract it. More formally,

Definition: A proof system \((P, V)\) is a proof of knowledge if there exists a probabistic polynomial time extractor E such that for all provers \(P^*\) and for all \(k \in {\mathbf N}\) the following property of Extractability holds, \[\Pr\bigg[\begin{array}{c} (x, \pi) \leftarrow P^*(z) \\ V(x, \pi) = 1\end{array} \wedge \begin{array}{c} (x, w) \leftarrow E^{P^*}(z) \\ w \text{ is not a solution for } x \text{ under problem } \mathcal{P}\end{array}\bigg]\]
Remark: Here the proof \(\pi\) is a proof of the statement "\(w\) is a solution to \(x\) for problem \(\mathcal{P}\). Moreover, the funky notation for \(E^{P^*}\) is saying that \(E\) has "oracle" access to \(P^*\). This means that \(E\) can makes function calls to \(P^*\).

\(<\)Wipes sweat from forehead\(>\) There. zk-SNARKs. Done.

3. The Real Thing: zk-SNARK

Again, I assume graduate level maturity of complexity theory and cryptography. This really is an advanced primitive and requires a delicate treatment of the definitions of simpler primitives.

3.1. Prerequisites

3.1.1. NP Relations

Definition: A relation \(R\) for some language \(\mathcal{L}\) is the set of instance, witness pairs \((x, w)\) such that \(\mathcal{L}_{R} := \{x : \exists w \text{ s.t } (x, w) \in R\}\).

Sanity Check: Can you define the class of languages NP?

Definition: The universal relation \(R_U\) is the set of instance, witness pairs \((x, w)\) where \(x = (M, y, t)\). Here, \(|x|, |w| \leq t\) and \(M\) is a random access machine that accepts the input \((y, w)\) in \(O(t)\) steps.

Remark: \(R_U\) is the relation for the universal language \(\mathcal{L}_U\).

3.1.2. Common Reference String Model

In section 2, the definition of Non-interactive Zero-Knowledge Proof Systems (NIZK) was said to be missing something. It’s missing randomness. Think about it. A non-interactive proof system with no randomness is unidirectional and doesn’t give us much room for growth outside of simplistic NP proofs where zero-knowledge is not attainable. There are a few commonly used models for constructing NIZKs and the one we will be focusing on here is known as the Common Reference String model (CRS).

In this model, both the verifier and prover have access to a common source of randomness that is trusted to be uniformly distributed. With this in mind, the definition for a Non-Interactive proof system with the Zero-Knowledge property is not too different from the one presented in section 2.

Definition: A NIZK for a language \(\mathcal{L}\) is a triplet of probabilistic algorithms \((G, P, V)\) such that,

The property of non-adaptive soundness is simply saying that a possibly malicious prover \(P^*\) cannot choose an adversarial \(x\) after seeing the common reference string \(\sigma\). Of course, this is a weaker guarantee of soundness than one where an adversarial \(x\) can be chosen after seeing the shared randomness. This stronger soundness notion is as follows for a triplet \((G, P, V)\),