Notes on zkSNARKs in Nutshell

Article

https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/

https://media.consensys.net/introduction-to-zksnarks-with-examples-3283b554fc3b

0 Introduction

zkSNARKs has 4 main ingredients:

  • Encoding as a polynomial problem
  • Succinctness by random sampling
  • Homomorphic encoding/encryption
  • Zero Knowledge

1 RSA and Zero-Knowledge Proofs

zero-knowledge succinct non-interactive arguments of knowledge:

  • Succinct
  • Non-interactive
  • ARguments
  • of Knowledge
  • zk(zero-knowledge)

2 NP and Complexity-Theoretic Reductions

3 Quadratic Span Programs

A QSP over a field $F$ for inputs of length $n$ consists of

  • a set of polynomials $v_0, \dots, v_m$, $w_0, \dots, w_m$ over this fild $G$,
  • a polynomial $t$ over $F$ (the target polynomial),
  • an injective function $f : \{ (i, j) | i \le i \le n, j \in \{ 0, 1 \} \} \rightarrow \{ 1, \dots, m \}$

An input $u$ is accepted (verified) by the QSP if and only if there are tuples $a=(a_1, \dots, a_m), b = (b_1, \dots, b_m)$ from the field $G$ such that

  • $a_k, b_k = 1$ if $k = f(i, u[i])$
  • $a_k, b_k = 0$ if $k = f(i, 1 - u[i])$
  • the target polynomial $t$ divides $v_a w_b$ where $v_a = v_0 + a_1 v_1 + \dots + a_m v_m$ and $w_b = w_0 + b_1 w_1 + \dots + b_m w_m$.

The witness is $a$ and $b$.

QSP is NP-Complete.

How to verify:

  • The prover provides another polynomial $h$ such that $th = v_a w_b$.
  • But the polynomials are quite large, it’s not very efficiently.
  • Instead, the verifier chooses a secret random point $s$, computes the numbers $t(s), v_k(s), w_k(s), v_a(s), w_b(s)$ and only checks that $t(s) h(s)=v_a(s) w_b(s)$.

Checking a polynomial identity only at a single point instead of at all points.

  • reduces the security - the prover can cheat, but with almost 0 possibility.

4 The zkSNARK in Details

A step phase:

  • In zCash, the circuit is fixed, and thus the polynomials for the QSP are fixed.
  • The commom reference string(CRS), the verifier chooses a random and secret field element $s$ and encrypts the values the polynomails at that point.

The verifier uses some specific encryption $E$ and publishes $E(v_k(s))$ and $E(w_k(s))$.

$E$ has homomorphic property.

4.1 How to Evaluate a Polynomial Succinctly and with Zero-Knowledge

How to evaluate a polynomial at a secret point:

  • Let $g$ be a group (elliptic curve) generator, $E(x) = g^x$.
  • The verifier chooses a secret field elements $s$, and publishes (as part of the CRS) $E(s^0), E(s^1), \dots, E(s^d)$.
  • After that, $s$ is destroyed.
  • Using these values, the prover can compute $E(f(s))$ for arbitrary polynomials $f$ without knowing $s$.

The problem is that, $s$ was destroyed, the verifier cannot check that the prover evaluated the polynomial correctly.

  • The verifier choose another secret field element, $\alpha$, and publish the values, $E(\alpha s^0), E(\alpha s^1), \dots, E(\alpha s^d)$.
  • The value $\alpha$ is also destoryed after the setup phase.
  • The prover publishes $A = E(f(s))$ and $B = E(\alpha f(s))$.
  • The verifier can check that $A$ and $B$ match or not.

To check that $A$ and $B$ match:

  • a pairing function $e$ has be chosen with elliptic curve, such that $e(g^x, g^y) = e(g,g)^{xy}$.
  • The verifier checks that $e(A, g^\alpha) = e(B, g)$.

The first problem is that, whether the prover can come up with values $A, B$ that fulfill the check $e(A, g^\alpha) = e(B, g)$, but are not $E(f(s))$ and $E(\alpha f(s))$.

  • The answer is “we hope not”.

The second problem is that the above protocol does not really allow the verifier to check that the prover evaluated the correct polynomial. The verifier can only check that the prover evaluated some polynomial at the point $s$.

  • The zkSNARK will contains another value that allows the verifier to check that the prover did indeed evaluate the correct polynomial.

The next step is adding the zero-knowledge part, so that the verifier cannot reconstruct anything about $f(s)$, not even $E(f(s))$.

  • The prover picks a random $\delta$, and she published $A’ = E(\delta + f(s))$ and $B’ = E(\alpha (\delta + f(s)))$.
  • $A’ = E(\delta) A, B’ = E(\alpha)^\delta B$.
  • $e(A’, g^\alpha) = e(g^{\delta + f(s)}, g^\alpha) = e(g,g)^{\alpha (\delta + f(s))}$
  • $e(B’, g) = e(g^{\alpha (\delta + f(s))}, g) = e(g,g)^{\alpha (\delta + f(s))}$
  • Nothing changed for the verifier.

4.2 A SNARK for the QSP Problem

The commom reference string(CRS):

  • $E(s^0), \dots, E(s^d)$ and $E(\alpha s^0), \dots, E(\alpha s^d),$
  • $E(t(s)), E(\alpha t(s)),$
  • $E(v_0(s)), \dots, E(v_m(s))$ and $E(\alpha v_0(s)), \dots, E(\alpha v_m(s)),$
  • $E(w_0(s)), \dots, E(w_m(s))$ and $E(\alpha w_0(s)), \dots, E(\alpha w_m(s)),$

and secret numbers $\beta_v$, $\beta_w$, $\gamma$ (to verify not some arbitrary polynomials) and publish

  • $E(\gamma), E(\beta_v \gamma), E(\beta_w \gamma),$
  • $E(\beta_v v_1(s)), \dots, E(\beta_v v_m(s)),$
  • $E(\beta_w w_1(s)), \dots, E(\beta_w w_m(s)),$
  • E(\beta_v t(s)), E(\beta_w t(s))

This is the full common reference string.

Let $I_{free}$ be the indices which are not restricted, and $v_{free}(x) = \sum_{k \in I_{free}} a_k v_k(x)$. Let $w(x) = b_1 w_1(x) + \dots + b_m w_m(x)$. The prover publishes

  • $V_{free} = E(v_{free}(s)), W = E(w(s)), H = E(h(s)),$
  • $V_{free}’ = E(\alpha v_{free}(s)), W’ = E(\alpha w(s)), H’ = E(\alpha h(s)),$
  • $Y = E(\beta_v v_{free}(s) + \beta_w w(s))$

The verifier checks three things:

  • The prover evaluates some polynomial.
  • The prover used the correct polynomials $v$ and $w$.
  • $v(s)w(s) = t(s)h(s)$.

How to verify, let $v_{in} = \sum_{k \not \in I_{free}} a_k v_k(s)$:

  • $e(V_{free}’, g) = e(V_{free}, g^\alpha)$, $e(W’, E(1)) = e(W, E(\alpha))$, $e(H’, E(1)) = e(H, E(\alpha))$
  • $e(E(\gamma), Y) = e(E(\beta_v, \gamma), V_{free}) e(E(\beta_w \gamma), W)$
  • $e(E(v_0(s) E(v_{in}(s)) V_{free}, E(w_0(s)) W) = e(H, E(t(s)))$.

How the second equality works:

  • $\beta_v$ and $\beta_w$ are unknown.
  • $\gamma, \beta_v v(s), \beta_w w(s), \beta_v \gamma, \beta_w \gamma$ are known.
  • $\gamma (\beta_v v(s) + \beta_w w(s)) = (\beta_v \gamma) v(s) + (\beta_w \gamma) w(s)$.
  • No other way to compute the combination.

4.3 Adding Zero-Knowledge

The prover chooses random $\delta_{free}, \delta_w$:

  • $v_{free}(s) \rightarrow v_{free}(s) + \delta_{free} t(s)$
  • $w(s) \rightarrow w(s) + \delta_w t(s)$

5 Tradeoff between Input and Witness Size

6 How is this Relevant to Ethereum