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?

up vote 40 down vote accepted

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$.
  • 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.

  • Can you give some references for the statement "NP witnesses are generally not short"? – Jus12 Sep 26 '16 at 16:24
  • @Jus12 If NP-witnesses are short, then clearly P = NP. – fkraiem Sep 27 '16 at 7:09
  • 1
    I don't see the connection. In factoring, the factors are generally very short. Perhaps the definition of "short" needs to be clarified. – Jus12 Sep 27 '16 at 10:15
  • @Jus12 You have a possible one right there in my answer. – fkraiem Sep 27 '16 at 21:15
  • @Jus12 P.S.: in mathematics, "generally" and "in general" are synonyms of "always". – fkraiem Sep 27 '16 at 21:17

protected by e-sushi Jun 28 at 18:59

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.