zk-SNARK

A zk-SNARK, or zero knowledge Succinct Non-interactive Argument of Knowledge, is a zero knowledge proof system that is non-interactive (proofs are one-shot messages) and succinct (proofs are short and cheap to verify).

Formally we consider a prover P who wants to prove knowledge of a witness $w$ such that $z = f(x, w)$ where $x$ is a publicly known input to the publicly known function $f$. The resulting proof $\pi$ must have constant size $O_\lambda(1)$ for any given value of a security parameter $\lambda$, and must be verifiable in time $O(|f| + |x| + |z|)$. This succinctness condition is quite strong: note that even explicitly revealing $w$ (breaking zero knowledge) would not satisfy it, since it has non-constant size and verification would require computing $f(x, w)$ which may be expensive.

Classic zero-knowledge proofs are interactive protocols between a prover and verifier, which work to convince the verifier, but do not necessarily convince a third-party observer. The existence of non-interactive protocols is transformative, because such a proof can be processed by an arbitrary number of verifiers: it works as a one-to-many argument that does convince verifiers who weren't around at its inception. Such a proof can reside on a blockchain, demonstrating secret knowledge in a way that's open to public verification (and that even creates common knowledge).

Example construction

TODO: this section is unfinished and a mess. Read http://chriseth.github.io/notes/articles/zksnarks/zksnarks.pdf instead.

An example of a scheme for demonstrating that the prover can compute some polynomial function $f$, known to have degree at most $d$.

We'll first choose a group and generator $g$, specifying a discrete logarithm encryption scheme $E(x) = g^x$.

A verifier chooses secret group elements $s$ and $z$, and publicly posts a common reference string (CRS) containing the encrypted values

noting that these in particular contain the generators $E(s^0) = g$ and $E(zs^0) = g^z$.

Because the $d$-degree polynomial $f$ must be a sum of powers of $s$, and the encryption scheme using exponentiation simply converts sums into products, the prover can use these terms to compute the encrypted values $m = E(f(s))$ and $n = E(z\cdot f(s))$. For example, if $f(s) = s^2 + s$, then

and similarly for $E(z\cdot f(s))$. For security reasons the prover will in fact computes these values and returns them shifted by a secret random offset $\psi$ , so that the proof is of the form

.

It is not obvious how a verifier should check this proof given that it knows neither the polynomial $f$ nor the original secrets $(s, z)$. The trick is to use a pairing function $p$, chosen such that

holds for all inputs $x, y$. Given such a function, the verifier checks that the two computations

give matching results. This checks that that $m$ and $n$ would decrypt to values that differ by a factor of $z$, even though we can't efficiently decrypt them and we no longer know $z$ explicitly. The only clear way to generate such values is to have evaluated some product of the paired terms provided as part of the common reference strong, representing a polynomial function of $s$.

Note that this verification does not depend on the complexity of $f$; it can proceed even if $f$ is some very complex high-degree polynomial.

q1: what is the pairing function? q2: what are we trying to prove about f?

References

• https://fisher.wharton.upenn.edu/wp-content/uploads/2020/09/Thesis_Terrence-Jo.pdf
• http://chriseth.github.io/notes/articles/zksnarks/zksnarks.pdf
• https://vitalik.ca/general/2021/01/26/snarks.html
• "Quadratic Span Programs and Succinct NIZKs without PCPs" by Gennaro, Gentry, Parno and Raykova https://eprint.iacr.org/2012/215.pdf