Zero-Knowledge Proofs

Introduction to SNARK

Interactive proofs are complete and (statistically) sound, while interactive arguments are sound w.r.t computationally bounded prover (computational soundness).

Definition (SNARK).
A succinct (preprocessing) non-interactive argument of knowledge (SNARK) is a triple of algorithms $(S, P, V)$:

• Setup $S(C;r)=(pp,vp)$: Generates public parameters $(pp, vp)$ for the prover and verifier respectively, given a circuit $C$.

• Prove $P(pp, x, w)=\pi$: Produces a short proof $\pi$, where $\mathsf{len}(\pi) = \mathsf{sublinear}(|w|)$

• Verify $V(vp, x, \pi)$: Fast to verify, with verification time: $\mathsf{time}(V) = O_{\lambda}(|x|, \mathsf{sublinear}(|C|))$,

that satisfy:

• Completeness: For all $x,w$ such that $C(x,w)=0$,$\mathbf{Pr}\left[\pi \leftarrow P(pp, x, w): V(vp, x, \pi) = 1\right] = 1$.

• Knowledge Soundness: If $V$ accepts, then $P$ “knows” a witness $w$ such that $C(x,w)=0$.

If the algorithms satisfy:

• Zero-Knowledge: The $(C,pp,vp,x,\pi)$ “reveals nothing new” about the witness $w$.

then the scheme is called a zk-SNARK.

Strong SNARK: all sublinear terms are $\log(|C|)$.

So in SNARK, prover can not simply send a $w$, for $w$ might be long ($|w|\leq |C|$) and it may be hard to verify $C(x,w)=0$.

Observe that $S$ is randomized for setup phase. If $r$ is revealed to $P$, it can prove false statements. This is because while $vp$ is visible from $P$, it can hide some key structures invisible from $P$ without knowing the random $r$.

The pre-processing has different types:

• transparent setup: $S(C)$ uses no random bit.

• trusted but universal setup: $S=(S_{\text{init}}, S_{\text{index}})$, $S_{\text{init}}(r)=gp$ generates global parameters with secret $r$, $S_{\text{index}}(gp,C)=(pp,vp)$ is deterministic.

• trusted setup per circuit: $S(C;r)$ uses random bits for every circuit $C$.

Argument of Knowledge

Here we use trusted but universal setup.

Definition (Adaptive Knowledge Soundness). A preprocessing NARK $(S, P, V)$ is (adaptively) knowledge sound for a circuit $C$ if for every polynomial-time adversary $A = (A_0, A_1)$ such that:

$$\begin{aligned} & gp \leftarrow S_{\text{init}}(1^\lambda;r), \\ & (C, x, \text{st}) \leftarrow A_0(gp), \\ & (pp, vp) \leftarrow S_{\text{index}}(C), \\ & \pi \leftarrow A_1(pp, x, \text{st}) \end{aligned}$$

and

$$\Pr[V(vp, x, \pi) = \text{accept}] > 1/10^6 \quad (\text{non-negligible w.r.t. } \lambda)$$

there exists an efficient extractor $E$ (that uses $A$) such that:

$$\begin{aligned} & gp \leftarrow S_{\text{init}}(1^\lambda;r), \\ & (C, x, \text{st}) \leftarrow A_0(gp), \\ & w \leftarrow E^A(gp, C, x) \end{aligned}$$

and

$$\Pr[C(x, w) = 0] > 1/10^6 - \epsilon \quad (\text{for a negligible } \varepsilon\text{ w.r.t. } \lambda).$$

Adversary chooses $(C, x)$ after seeing $gp$ (adaptive), then produces a proof $\pi$. If $A$ produces an accepting proof with non-negligible probability, then $E$ can extract a valid witness $w$ with essentially the same probability (up to negligible $\varepsilon$).

After intro, we proceed to constructing a SNARK, which uses 2 building blocks, one is functional commitment scheme, and the other is interactive oracle proof. The former is a cryptographic object and the latter is an information-theoretical object.

Building Blocks 1: functional commitment scheme

Definition (Commitment Scheme). A commitment scheme consists of

• $\mathsf{setup}(1^\lambda)\to gp$, outputs public parameters $gp$

• $\mathsf{commit}(gp, f, r)\to \mathsf{com}$, commitment to $f \in \mathcal{F}$ with $r \in \mathcal{R}$ randomly chosen

• $\mathsf{open}(\mathsf{com}, f, r)$: if $\mathsf{com} = \mathsf{commit}(gp, f, r)$, then $\mathsf{open}(\mathsf{com}, f, r) = 1$; otherwise $\mathsf{open}(\mathsf{com}, f, r) = 0$

satisfying hiding and binding properties:

• Binding: for all PPT adversary $\mathcal{A}$：

$$\Pr\left[ \begin{array}{l} gp \leftarrow \mathsf{setup}(1^\lambda) \\ (\mathsf{com}_f, f_0, r_0, f_1, r_1) \leftarrow \mathcal{A}(gp) \end{array} : \begin{array}{l} (f_0, r_0) \neq (f_1, r_1) \\ \wedge \; \mathsf{com}_f = \mathsf{Commit}(gp, f_0, r_0) \\ \wedge \; \mathsf{com}_f = \mathsf{Commit}(gp, f_1, r_1) \end{array} \right] \le \mathsf{negl}(\lambda)$$

• Hiding: for all PPT adversary $\mathcal{A}=(\mathcal{A}_1,\mathcal{A}_2)$:

$$\left| \Pr\left[ \begin{array}{l} gp \leftarrow \mathsf{Setup}(1^\lambda) \\ (f_0, f_1, st) \leftarrow \mathcal{A}_1(gp) \\ b \leftarrow \{0,1\}, \; r \leftarrow \mathcal{R} \\ com_f \leftarrow \mathsf{Commit}(gp, f_b, r) \\ b' \leftarrow \mathcal{A}_2(st, com_f) \end{array} : b' = b \right] - \frac{1}{2} \right| \le \mathsf{negl}(\lambda)$$

also defined as computational indistinguishability.

Note: the $r$ in the open algorithm is the same as that in the commit algorithm.

After sender’s commitment, the sender should also send $(x,r)$ for the receiver to verify. For example, if I want to play paper-scissors-rock with a friend remotely: first we determine our choices; then we send the commitments to each other; finally we send the choice and the random bits used and verify the commitments sent by one another.

To hide the message along the interaction (also, to make the proof short instead of $(x,r)$), we define functional commitment scheme.

Definition (Functional Commitment Scheme). A functional commitment scheme for $\mathcal{F}=\{f:X\mapsto Y\}$:

• $\mathsf{setup}(1^\lambda)\to gp$, outputs public parameters $gp$

• $\mathsf{commit}(gp, f, r)\to \mathsf{com}_f$ , commitment to $f \in \mathcal{F}$ with $r \in \mathcal{R}$, which is a binding (and hiding for zk-SNARK) commitment scheme for $\mathcal{F}$

• $\mathsf{eval}(P, V)$: for a given $\mathsf{com}_f$ and all $x \in X$:

$$\mathsf{open}(gp, f, x, r) \to \text{short proof } \pi\text{ and value }y\in Y$$

$$\mathsf{verify}(gp, \mathsf{com}_f, x, y, \pi) \to \text{accept/reject}$$

satisfying

• Completeness: If $f \in \mathcal{F}$ and $x \in X$ with $f(x)=y$, then $\Pr[V(gp, \mathsf{com}_f, x, y, \pi) = \mathsf{accept}] = 1$.

• Knowledge Soundness: $(\mathsf{setup}\;\|\;\mathsf{commit}, \mathsf{open}, \mathsf{verify})$ is knowledge sound.

The interaction within $\mathsf{eval}(P,V)$ is actually a SNARK for the relation (circuit)

$$\{(gp,\mathsf{com}_f,x,y): \exists (f,r),f(x)=y, f\in\mathcal{F},\mathsf{com}_f=\mathsf{commit}(gp, f, r)\}$$

whose witness is essentially $(f,r)$. The proof $\pi$ actually proves that $f\in\mathcal{F}$, $f(x)=y$ and $\mathsf{com}_f$ is a commitment to $f$.

The definition above essentially illustrates an interactive process. It is like the verifier “queries” the oracle $f$ at $x$ with an additional cost of verifying.

With the scheme above we commit to a function. The $\mathcal{F}$ vary from many different function classes.

• Polynomial commitments: $\mathcal{F} = \mathbb{F}^{\leq d}[X]$

• Multilinear commitments: $\mathcal{F} = \mathbb{F}^{\leq 1}[X_1, \ldots, X_n]$, where the degree is defined the maximum degree of the polynomial in every variable ($\leq1$ means multilinear)

• Vector commitments: $\mathcal{F} = \{f_u: [n] \to \mathbb{F}:f(i) = u_i,u\in\mathbb{F}^n\}$

• Inner product commitments: $\mathcal{F} = \{f_{u}: \mathbb{F}^n \to \mathbb{F}:f_{u}(v) = \langle u,v\rangle, u\in\mathbb{F}^n\}$

Building Blocks 2: $\mathcal{F}$-Interactive Oracle Proof

IOP is a proof system that proves the prover knows $w$ such that $C(x,w)=0$. The verifier uses oracles of $f\in\mathcal{F}$, which is later replaced by functional commitments to construct a SNARK; here we use oracles.

Definition ($\mathcal{F}$-IOP): An $\mathcal{F}$-IOP is a proof system that proves $\exists w,\;C(x,w)=0$ and consists of

• $\mathsf{setup}(1^\lambda)\to pp,vp=(\mathsf{Oracle}_{f_{-s}},\dots,\mathsf{Oracle}_{f_{0}})$

• At round $i\in[t]$, prover $P$ sends $\mathsf{Oracle}_{f_i}$ where $f_i$ is based on the interaction history from view of $P$; verifier sends $r_i\xleftarrow{\$} R$ unless $i=t$.

• $\mathsf{verify}^{\mathsf{Oracle}_{f_{-s}},\dots,\mathsf{Oracle}_{f_t}}(vp,x,r_1,\dots,r_{t-1})$ uses $(f_i)_{i=-s}^t$ as oracles and output the result.

which satisfies

• Completeness: If $\exists w,\;C(x,w)=0$, then the verifier is bound to accept

• Knowledge Soundness: if we use $\mathsf{com}_f$’s for $\mathsf{Oracle}_f$’s, the extractor can use $(f_{i})_{i=-s}^t$ to compute $w$ because the functional commitment scheme is knowledge sound (functional commitment scheme is actually a SNARK).

• (Optional) Zero-Knowledge

Polynomial IOP for Circuit SAT

In this lecture we are going to construct a poly-IOP for circuit satisfiability. $C$ is an arithmetic circuit with size $S$. The prover wants to prove that it knows the solution $w$ to $C(w)=y$.

First, we label every gate of $C$ with a bit string of length $\log S$. Thus the computation of $C(w)=y$ can be expressed in a form of function $T:\{0,1\}^{\log S}\mapsto\mathbb{F}$, which maps the label of some gate to the output of the gate with its output (notice that $T(\text{root})=y$). Let $h:\mathbb{F}^{\log S}\mapsto\mathbb{F}$ be the unique multilinear extension of $T$, satisfying $h(x)=T(x)$ for all $x \in \{0,1\}^{\log S}$ (the uniqueness is trivial by dynamic programming).

Why shall we extend the function $T$ to a multilinear polynomial $h$? The necessity is shown in the part of the sum-check protocol.

Here $V$ should have verified the $h$ and $T$ are the same on $\{0,1\}^{\log S}$. However $V$ only has the commitment of $h$, so $V$ verifies this by another approach shown below.

We use labels to denote gates, and define the polynomial $g_h:\mathbb{F}^{3\log S}\mapsto\mathbb{F}$ as follows:

which satisfies:

We shall modify a little in $g_h$: we embed the result $g_h(a,b,c)$ into $\mathbb{Z}$. So the condition above is equivalent to $\sum_{x\in\{0,1\}^{3\log S}} \tilde{g}_h(x)=0$ where $\tilde{g}_h:\mathbb{F}^{3\log S}\mapsto\mathbb{Z}$ has the same values as $g_h$ on all inputs. Then $P$ and $V$ interact to let $V$ believe that the sum is $0$. If the sum is $0$, $V$ believes that $P$ knows the correct $T$.

Here comes the usage of the sum-check protocol.

Sum-Check Protocol

The goal of the protocol is to check the answer $C$ provided by prover satisfies:

where $g$ is an $n$-variate polynomial over the field $\mathbb{F}$ and the sum is computed in $\mathbb{Z}$ (i.e. add them up without taking the modulo).

In setup phase, $P$ sends the commitment of $g$ to $V$. Then they interact for $n$ rounds, and in the end $V$ checks the final claim by querying the oracle of $g$ for one time at a random point.

The probability that a cheating prover can make the verifier accept a false claim is at most $\frac{n\deg(g)}{|\mathbb{F}|}$ (by Schwartz-Zippel lemma, $\deg$ is the maximum degree in total, regardless of different variables). So we can make the soundness error negligible by choosing a large enough field.

Note that every polynomial from $P$ is sent in its coefficients. Let $d=\deg(g)$ and it takes $T_g$ time to verify/evaluate any $g(x)$, we have

and the proof length is $O(nd)$ .

For dense polynomial $g$ , the time to evaluate its multilinear extension $\tilde g$ on point $x$ is at most $O(2^n)$ . Thus our prover has quadratic time. The [Libra] puts forwards a linear time sum-check prover.

This sum-check protocol is also used in the proof that $\mathbf{IP}=\mathbf{PSPACE}$. Define the decisional counting problem of 3CNF as:

so by translating the boolean formula into a multilinear polynomial, with the sum-check protocol we have $(\#\mathsf{SAT})_D\in\mathbf{IP}$.

Suppose we have a $\mathsf{TQBF}$ formula $\psi=\forall x_1\exists x_2\dots Qx_n.\varphi(x_1,x_2,\dots,x_n)$ , if we directly make $\forall$ into multiplication and $\exists$ into addition, the degree will skyrocket. Define for a $p\in\mathbb{F}[X_1,\dots,X_n]$,

these polynomials are all in $\mathbb{F}[X_1\dots,X_n]$.

In analogy to the sum-check protocol, we can also define $\mathsf{X}_ip:=p^{i\leftarrow0}+p^{i\leftarrow1}\in\mathbb{F}[X_1\dots X_{i-1},X_{i+1},\dots,X_n]$.

The idea is to linearize the polynomial after each multiplication. So the formula is described by the polynomial

then the prover and verifier go through a $O(n^2)$ interaction to establish the protocol. Thus $\mathsf{TQBF}\in\mathbf{IP}$ and $\mathbf{IP}=\mathbf{PSPACE}$.

PLONK IOP

Based on the lecture 4, we can encode a circuit problem into a polynomial. The sum-check protocol uses multi-variable polynomials with a large proof size (linear to $n\sim\log |C|$ even if we send commitments of polynomials instead of coefficients). PLONK is also used for circuit SAT with a different encoding, which uses univariate polynomials and has a proof size independent of $n$.

Small gadgets to build PLONK IOP

Let $\Omega=\langle\omega\rangle\subset\mathbb{F}_p$ be a multiplicative subgroup of size $k\mid\varphi(p)$. And we want to provide protocols to prove that a committed polynomial $f$ has some properties on $\Omega$. The properties of given $f,g\in\mathbb{F}_p[X]$ include:

• Zeroness: $f(x)=0$ for all $x\in\Omega$

• Sum/Product over $\Omega$: $\sum_{x\in\Omega}\left(f(x)-g(x)\right)=0$ or $\prod_{x\in\Omega}\frac{f(x)}{g(x)}=1$

• Permutation: $(f(\omega^i))_{i=0}^{k-1}$ is a permutation of $(g(\omega^i))_{i=0}^{k-1}$ . Warning: it is not enough to check $\prod_{x\in\Omega}\frac{f(x)}{g(x)}=1$ ! The soundness relies on the random challenge by the verifier.

• Prescribed permutation: $f(y)=g(W(y))$ for some known permutation $W:\Omega\to\Omega$

Encoding a circuit into a polynomial

We again take $C(x,w)$ as the circuit satisfiability problem. Let $d=3|C|+|x|+|w|$, and label each gate with a integer. And we have the $d$-th root $\omega$, which satisfies $\omega^d=1$.

Setup phase outputs polynomial $S$ and permutation $W$. The prover wants to prove that it knows $w$ such that $C(x,w)=0$, so it interpolates a polynomial $T\in\mathbb{F}_p^{\leq d}[X]$ such that

• $T(\omega^{-j})=$ the value of the $j$-th input

• $T(\omega^{3i}),T(\omega^{3i+1}),T(\omega^{3i+2})$ are the left-input/right-input/output of the $i$-th gate, $i=0,1,\dots,|C|-1$

using FFT in time $O(d\log d)$.

Then the prover proves the following:

• The inputs are correct: $T(\omega^{-j})=x_j$ for $j=0,1,\dots,|x|-1$

• The math operations are correct: Use a public $S(\omega^{3i})=1$ iff $i$-th gate is multiplicative; then, prove for all $y\in\{\omega^{3i}:i<|C|\}$,

• Wiring is correct: Use a public $W$ to rotate the wires that share the same value; then, prove $T(y)=T(W(y))$ for all $y\in\{\omega^{i}:i<d\}$

• The output is $0$ : $T(\omega^{3|C|-1})=0$

using the gadgets mentioned above.

Polynomial commitment based on discrete-log and pairing

KZG: pairing

We have $G$ as a group of prime order $p$ with generator $g$. We have a bilinear map $e:G\times G\to G_T$ where $G\cong G_T\cong C_p$ are $p$-order cyclic groups. We use $\mathcal{F}=\mathbb{F}_p^{\leq d}[X]$, and the public parameters $gp$ are generated as

where $\tau$ is a random element in $\mathbb{F}_p$; after computing, abort the random $\tau$. To commit to a polynomial $f(X)=\sum_{i=0}^d f_iX^i$, we compute

In the evaluation phase, with input $u$, the prover sends $v$ and a proof $\pi$ for the verifier to verify $f(u)=v$ using $\pi$. The idea is if $f(u)=v$, then $f(X)-v$ is divisible by $X-u$. Let $q(X)=(f(X)-v)/(X-u)$, then the proof is written as $\pi=g^{q(\tau)}$ and $(v,\pi)\leftarrow\mathsf{open}(gp,f,u)$. The verifier checks if $e\left(g^{\tau-u},\pi\right)=e\left(\frac{\mathsf{com}_f}{g^{v}}, g\right)$. The verifier knows $g^{\tau-u}$ because it knows $g^\tau$ from the global parameter and it can compute $g^u$ from $u$.

Time: commit $O(d)$ group exponentiations, open (including computing $q$) $O(d)$ group exponentiations and $O(d)$ group multiplications, verify $O(1)$ pairings. Size: proof and commitment are both $O(1)$ group elements.

The completeness is trivial. For soundness, if the prover outputs another $(v',\pi')$ such that $f(u)\not=v'$ and $e\left(g^{\tau-u},\pi'\right)=e\left(\frac{\mathsf{com}_f}{g^{v'}}, g\right)$, then we have (denote $\delta=f(u)-v'$):

so as a result

where the operations on the exponent are in $\mathbb{F}_p$ which corresponds to the multiplication in the groups $G$ and $G_T$. This is the $q$-Strong Bilinear Diffie-Hellman** assumption, which says that it is hard to compute $e(g,g)^{\frac{1}{\tau-u}}$ given $(p,G,g,G_T,e)$ and $gp=(g,g^\tau,\dots,g^{\tau^d})$.

Knowledge Soundness

The plain KZG is not knowledge soundness without assumptions like KoE or GGM. We will discuss the assumptions in the PCP-based SNARK.

Zero-Knowledge-ness

The plain KZG is not zk since the commit algorithm is deterministic. For example, you can use $g^{f(\tau)}$ to test if $f$ is a zero polynomial. Here, we denote the protocol modified to zk in the graph below.

The polynomial is hidden by the random $r'$.

Variants of KZG

• For multivariate poly: $f(x_1,\dots,x_k)-f(u_1,\dots,u_k)=\sum_{i\in[k]}(x_i-u_i)q_i(x_1,\dots,x_k)$ . Prover computes and sends $\pi_i=g^{q_i(\tau_1,\dots,\tau_n)}$ . Prover time is $O(km)$ group exponentials where $m\leq 2^k$ is the number of terms of $f$ . [Chopin] claims to reduce the prover time to $m+O(\sqrt{m})$ MSMs (compute $\prod_j g_j^{a_j}$ ).

• For batch query on $u_1,\dots,u_m$: $f(x)-h(x)=q(x)\prod_{i\in[m]}(x-u_i)$ where $h(x)$ is the extrapolation of $(u_i,f(u_i))$’s.

• For multi-party, each party has a private number for setup, and the public parameters are (for example, 2-party) $gp=\left(g,g^{st},\dots,g^{(st)^d}\right)$. The parameters can be generated party after party, since $g^{(st)^i}=\left(g^{s^i}\right)^{t^i}$.

And it is worth noting that PLONK uses univariate KZG and plonk IOP, while vSQL uses multivariate KZG and sum-check protocol.

Bulletproofs: discrete-log

KZG requires trusted setup. Here we present Bulletproofs which has transparent setup. The goal of the prover is to convince the verifier that $f(u)=v$ where $f=\sum_{i=0}^{d+1}f_ix^i\in\mathbb{F}_p[X]$. The setup phase is just a random $gp=(gp_{0,0},\dots,gp_{0,d})\in G$ and we assume $d+1=2^k$ is some exponential of $2$. Then the prover and verifier go through a interaction shown below: