What are SNARKs?

Question

What does it mean and what is it used for, I have been hearing this term a lot lately.
From the context I've heard it talked about it seems to be connected with zero knowledge?

Answer 1

I assume you are familiar with $P$ and $NP$. Also, my knowledge of SNARKs is based mostly on the work of Parno et al., other work may differ in some fine details.

So, a SNARK is a succinct non-interactive argument of knowledge. Leaving the "knowledge" part aside for the moment, let's look at "plain" succinct non-interactive arguments (called SNARGs in the work linked above). An argument is another name for a computationally sound proof. You probably know that the soundness property of a proof system is the technical term for the property that it is impossible to "prove" a false assertion (in the system under consideration).

Traditional non-interactive proof systems have "perfect soundness", meaning that it is absolutely impossible to prove a false statement. For example, given a $NP$-language $L$, if a prover wants to prove to a verifier that a certain word $x$ is in $L$, he can simply produce a witness $w$ for $x$. Then, the verifier will accept the input $(x,w)$ and be convinced that $x$ is indeed in $L$. On the other hand, if $x$ is in fact not in $L$, it does not have any $NP$-witness, and so the verifier will always reject any purported witness $w$ for $x$. This is very good in a security sense: the verifier can be certain that a malicious prover can never trick it into believing that a statement is true when it is in fact false. The problem, however, is that a $NP$ witness can't be too small (if we allow $NP$ witnesses to be too small, then we "shrink" $NP$ to the point where it is smaller than it is commonly believed to be).

Proof systems with perfect soundness are reminiscent of cryptosystems with perfect secrecy, such as the one-time pad: even an adversary with infinite computing power can't "break" them (for cryptosystems, this means decrypting messages; for proof systems, this means proving false statements). However, the price to pay for such strong security is a loss of efficiency which is generally considered too high for such systems to be practical. The way out is to recognise that adversaries with infinite computing power do not exist in practice. We don't really care that such an adversary can break our system, and we are satisfied if no efficient adversary (i.e., no adversary running in polynomial time) can break our system with non-negligible probability. And, just like with cryptosystems, relaxing our requirements in that way allows the system to be much more efficient: in the work of Parno et al. the proofs are constant-sized, whereas a traditional $NP$ witness has size polynomial in the statement's size.

In the end, a succinct non-interactive argument for a $NP$-language $L$ is a non-interactive and computationally sound proof system for $L$ where the proofs are succinct. This latter term may be defined slightly differently in different works, Parno et al. define it as "polynomial in the security parameter". Such a proof system consists of three algorithms $\mathsf{Gen}$ (key generation), $\mathsf{P}$ (proving), and $\mathsf{V}$ (verifying):

• $\mathsf{Gen}$ is typically run by the verifier. It takes as input $1^k$ ($k$ being the security parameter) and outputs some keypair, $\mathsf{priv}$ and $\mathsf{pub}$.
• $\mathsf{P}$ (the proving algorithm) takes as input $\mathsf{pub}$, a word $x \in L$ and a $NP$-witness $w$ for $x$, and outputs the proof $\pi$.
• $\mathsf{V}$ (the verifying algorithm) takes as input $\mathsf{priv}$, $x$ and $\pi$, and returns $0$ or $1$ depending on whether the verifier "accepts" the proof that $x$ is in $L$.

The system must satisfy the three following properties (which I state here informally):

• Perfect completeness: if $x$ is in $L$ and $w$ is a $NP$-witness for $x$, then the proof $\pi$ produced by the prover on input $(x,w)$ will always be accepted by the verifier.
• Succinctness: the length of $\pi$ is polynomial in $k$. Notice that this polynomial is universal, and may not depend on the length of the instance (i.e., $|x|$), the language $L$, or the theorem $x\in L$ being proven.
• Computational soundness: for any polynomial-time adversary running on input $(1^k,\mathsf{pub})$ and producing a pair $(x,\pi)$, the probability that $x$ is not in $L$ and that $(x,\pi)$ is accepted by $\mathsf{V}$ is negligible in $k$.

Finally, what's a succinct non-interactive argument of knowledge (SNARK)? If you paid attention to the above, the fact that the verifier returns $1$ on some input $(x,\pi)$ only certifies that $x$ is in $L$, but it does not rule out the possibility that the prover generated the pair $(x,\pi)$ in a non-standard way, without knowing a $NP$-witness for $x$. A SNARK does this by requiring one additional property:

• Extractability: for any polynomial-time prover $\mathsf{P}^*$ running on input $(\mathsf{pub},z)$ (where $z$ is some auxiliary input) and producing a pair $(x,\pi)$, there is a polynomial-time extractor $\mathcal{E}_{\mathsf{P}^*}$ also running on input $(\mathsf{pub},z)$ and producing $w$, such that the probability that $(x,\pi)$ is accepted by the verifier and that $w$ is not a $NP$-witness for $x$ is negligible in $k$.

Informally, the extractability property says that for any algorithm which takes some input $z$ and produces a valid pair $(x,\pi)$, there is an extractor algorithm which takes that same input and outputs a $NP$-witness $w$ for $x$. Hence, we consider that the first algorithm "knows" $w$, because it is possible to compute $w$ efficiently using only data which is known by the first algorithm.