绘素的Blog

A study notes on zk-SNARK, mainly focusing on the equations in zk-SNARK.

ZK-SNARK stands for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge.

Three properties of zk-SNARK

1. Completeness: Every statement with a valid witness has a proof that convinces the verifier.

2. Soundness: A statement with an invalid witness does not have a proof that convinces the verifier.

3. Zero-knowledge: The proof only conveys information about the validity of the statement and nothing about the prover’s witness.

Preliminaries#

Arithmetic circuits#

Arithmetic circuits is a model for computing polynomials. For a finite field $F=\{0,\cdots,p-1\}$ (prime $p>2$), arithmetic circuits $C:F^n\rightarrow F$ is a direct acyclic graph (DAG) where nodes are addition and multiplication gates and edges are wires. Each node in DAG has two input and output. The DAG has one final output.

In a $m$-gate, $n$-wire arithmetic circuit, a witness is defined as $s=(s_1,s_2,\cdots, s_n)$, where $s_i$ is the value of $i$-th wires.

Rank-1 constraints (R1CS) is defined as follows: for some constants $\{u_{i,q},v_{i,q},w_{i,q}\}_{1\le i\le n,1\le q\le m}$, $\sum_{i=1}^ns_iu_{i,q}\cdot \sum_{i=1}^ns_iv_{i,q}=\sum_{i=1}^ns_iw_{i,q}$. For example, in Figure 1, $s_1\cdot s_2=s_4$ is a R1CS, where $u_{1,1}=1,v_{2,1}=1,w_{4,1}=1$, others $=0$.

Quadratic Arithmetic Program (QAP)#

First, we define the target points as $r_1,r_2,\cdots,t_m\in F_p$. Each target point corresponds to a gate in the arithmetic circuit. Then, we define the vanishing function $t(x)=\Pi_{q=1}^m(x-r_q)$ such that $t(x)=0$ at targets points $r_1,r_2,\cdots,t_m$.

A quadratic arithmetic program is a relation over $s=(s_1,s_2,\cdots, s_n)$ such that $\sum_{i=1}^ns_iu_{i}(x)\cdot \sum_{i=1}^ns_iv_{i}(x)-\sum_{i=1}^ns_iw_{i}(x)\equiv 0~(\bmod~t(x))$, where $u_i(x),v_i(x),w_i(x)$ is degree $m-1$ polynomials such that for $1\le i\le n,1\le q\le m$, $u_i(r_q)=u_{i,q}$, $v_i(r_q)=v_{i,q}$ and $w_i(r_q)=w_{i,q}$.

When $x=r_q$, this equation is the $q$th gate’s R1CS. Thus, checking this equation is equivalent to checking the $m$ rank-1 constraints simultaneously

Homomorphic Encoding#

Homemorphic encoding is an injective homomorphism $E: F_p\rightarrow G$ such that it’s hard to find $x$ given $E(x)$.

For example, given a cyclic group $G$ of prime order $p$, with $g$ as generator and multiplication as group operation, a homomorphic encoding is $E(a)=g^a$. It’s homomorphic and injective. Also, by the hardness of the discrete logarithm problem, it is also hard to find $x$ given $E(x)$.

Pairing Function, or Bilinear Map#

A pairing function, also called bilinear map is defined as follows:

$G_1,G_2$ and $G_T$ are groups of prime order $p$, a pairing function is $e:G_1\times G_2\rightarrow G_T$, such that:

1. if $g,h$ are generators of $G_1$ and $G_2$ respectively, then $e(g,h)\not= 1$ is a generator of $G_T$ .

2. $e(g^a,h^b)=e(g,h)^{ab}$.

Bilinear map have several properties, which is shown as follows:

• $e(u,vw)=e(g^a,h^bh^c)=e(g,h)^{a(b+c)}=e(g^a,h^b)e(g^a,h^c)=e(u,v)e(u,w)$

• $e(vw,u)=e(v,u)e(w,u)$

• $e(u^x,v)=e(g,h)^{xab}=e(u,v^x)$

In the Pinocchio implementation (a implementation of zk-SNARK), symmertic bilinear map is used, where $G:=G_1=G_2$

zk-SNARK#

For any NP-computation that a prover and a verifier both agree on beforehand, they can construct an arithmetic circuit for thie computation such that a witness for this circuit is a witness for the original computation. An arithmetic circuit can be reduced to a QAP such that verifying a witness for the QAP is equivalent to a witness for the arithmetic circuit. Thus, verifying a witness for the QAP equals to verifying a witness for original computation.

General Reduction from Arithmetic Circuit to QAP#

For a arithmetic circuit with $m$-gates and $n$-wires, a witness is defined as $s=(s_1,s_2,\cdots,s_n)\in R^n$. A R1CS $(a_i,b_i,c_i)$ for $s$ is defined as $(s\cdot a_i)\times(s\cdot b_i)-s\cdot c_i=0$, where $1\le i\le m$ and $a_i,b_i,c_i\in R^n$.

A general reduction consists of three steps:

1. stack the $m$ constraints vectors to obtain matrices $A,B,C\in R^{m\times n}$, where

   • $A=\begin{pmatrix}a_1^T\\a_2^T\\\vdots\\a_m^T\end{pmatrix}B=\begin{pmatrix}b_1^T\\b_2^T\\\vdots\\b_m^T\end{pmatrix}C=\begin{pmatrix}c_1^T\\c_2^T\\\vdots\\c_m^T\end{pmatrix}$

2. use Langrange Interpolation, find $3$ sets of $n$ polynomials $\{u_i\}_{i=1}^n,\{v_i\}_{i=1}^n,\{w_i\}_{i=1}^n$, such that

   • for all $i\in[n]$ and $x\in[m]$

   • $\begin{aligned}u_i(x)&=A[x][i]\\v_i(x)&=B[x][i]\\w_i(x)&=C[x][i]\end{aligned}$

3. find the polynomial $h(x)$ such that

   • $\left(\sum_{i=1}^ns_iu_i(x)\right)\cdot\left(\sum_{i=1}^ns_iv_i(x)\right)-\left(\sum_{i=1}^ns_iw_i(x)\right)=h(x)t(x)$

   • where $t(x)=(x-1)(x-2)\cdots(x-n)$

Thus, checking $\left(\sum_{i=1}^ns_iu_i(x)\right)\cdot\left(\sum_{i=1}^ns_iv_i(x)\right)-\left(\sum_{i=1}^ns_iw_i(x)\right)=h(x)t(x)$ is equivalent to checking the the R1CS relations in the arithmetic circuit. That is, the witness can satisfy all R1CS relation in each node.

Pinocchio Protocol#

Pinocchio protocol is an implementation for zk-SNARK.

The protocol is built on a group $G$ of prime order $p$ with a generator $g$. Define the homomorphic encoding as $E:F_p\rightarrow G$, $E(x)=g^x$. Define a elliptic curve bilinear map as $e:G\times G\rightarrow G_T$. The prover knows a witness $\{s_i\}_{i=1}^n$ and he can get the following equation by reduction: $\left(\sum_{i=1}^ns_iu_i(x)\right)\cdot\left(\sum_{i=1}^ns_iv_i(x)\right)-\left(\sum_{i=1}^ns_iw_i(x)\right)=h(x)t(x)$.

The main idea are as follows:

1. $V$ tests $P$ at a random point $z\in F_p$ for the polynomials

2. $P$ computes $u(z)=\sum_{i=1}^{n}s_{i}u_{i}(z),v(z)=\sum_{i=1}^{n}s_{i}v_{i}(z),w(z)=\sum_{i=1}^{n}s_{i}w_{i}(z)$ and $h(z)$ and homomorphically encodes these values and send them to $V$

3. $V$ can verify that the homomorphically encoded values satisfy the same equation without learning the witness itself.

The Pinocchio protocol consists of three steps: (1) Trusted third party generates a common reference string (CRS); (2)Prover generates proofs; (3)Verifier checks proofs and decides to accept or reject.

In the CRS generation process, the trusted third party picks random $\alpha, \beta_u,\beta_v,\beta_w,\gamma,z\in F_p^*$ and publishs the CRS. Then, the trusted third party discards all of the sampled group elements used in its generation (the toxic waste). The CRS consists of evaluation key for the prover and verification key for the verifier.

The evaluation key is defined as follows:

• $\{E(z^{i})\}_{i=0}^{n},\{E(\alpha z^{i})\}_{i=0}^{n}$

• $\{E(u_i(z)\}_{i=1}^n,\{E(\alpha u_i(z)\}_{i=1}^n,\{E(\beta_uu_i(z)\}_{i=1}^n$

• $\{E(v_{i}(z)\}_{i=1}^{n},\{E(\alpha v_{i}(z)\}_{i=1}^{n},\{E(\beta_{v}v_{i}(z)\}_{i=1}^{n}$

• $\{E(w_i(z)\}_{i=1}^n,\{E(\alpha w_i(z)\}_{i=1}^n,\{E(\beta_ww_i(z)\}_{i=1}^n$

The verification key is defines as follows:

• $E(1),E(\alpha),E(t(z))$

• $E(\gamma),E(\beta_u\gamma),E(\beta_v\gamma),E(\beta_w\gamma)$

In the proof generation process, since the prover knows the polynomials $\left(\sum_{i=1}^ns_iu_i(x)\right)\cdot\left(\sum_{i=1}^ns_iv_i(x)\right)-\left(\sum_{i=1}^ns_iw_i(x)\right)=h(x)t(x)$, he will first computes $h(x)$. Then, the prover generates proof using the evaluation key as follows:

• $E(u(z)),E(\alpha u(z)),\mathrm{~where~}u(z)=\sum_{i=1}^ns_iu_i(z)$

• $E(v(z)),E(\alpha v(z)),\mathrm{~where~}v(z)=\sum_{i=1}^ns_iv_i(z)$

• $E(w(z)),E(\alpha w(z)),\text{ where }w(z)=\sum_{i=1}^ns_iw_i(z)$

• $E(h(z)),E(\alpha h(z))$

• $E(\beta_uu(z)+\beta_vv(z)+\beta_ww(z))$

For example,

• $E(u(z))=E(\sum_{i=1}^ns_iu_i(z))=g^{\sum_{i=1}^ns_iu_i(z)}=\Pi_{i=1}^ng^{s_iu_i(z)}=\Pi_{i=1}^n(g^{u_i(z)})^{s_i}=\Pi_{i=1}^n(E(u_i(z))^{s_i})$

• $E(\alpha u(z))=E(\sum_{i=1}^ns_i\alpha u_i(z))=\Pi_{i=1}^n(E(\alpha u_i(z))^{s_i})$

• $E(h(z))$: linear combination of $z^i$, can be computed from $E(z^i)$

• $E(\beta_uu(z)+\beta_vv(z)+\beta_ww(z))=E(\beta_uu(z))E(\beta_vv(z))E(\beta_ww(z))$

In the proof verification process, the verifier will conduct three verifications.

First, the verifier checks that the terms $u(z), v(z), w(z), h(z)$ were constructed as linear combinations of terms in the CRS by checking the following equations:

• $e(E(u(z)),E(\alpha u_{1}(z))) =e(E(\alpha u(z)),E(u_1(z)))$

• $e(E(v(z)),E(\alpha v_1(z))) =e(E(\alpha v(z)),E(v_1(z)))$

• $e(E(w(z)),E(\alpha w_{1}(z))) =e(E(\alpha w(z)),E(w_1(z)))$

• $e(E(h(z)),E(\alpha)) =e(E(\alpha h(z)),E(1))$

Then, the verifier checks that each term $u(z), v(z), w(z)$ were generated using the same linear coefficients, $\{s_i\}^n_{i=1}$, that is check whether $u(z)=\sum_{i=1}^{n}s_{i}u_{i}(z),v(z)=\sum_{i=1}^{n}s_{i}v_{i}(z),w(z)=\sum_{i=1}^{n}s_{i}w_{i}(z)$

• $e(E(\beta_uu(z)+\beta_vv(z)+\beta_ww(z)),E(\gamma))=e(E(u(z)),E(\beta_u\gamma))e(E(v(z)),E(\beta_v\gamma))e(E(w(z)),E(\beta_w\gamma))$

Finally the verifier checks the key condition that characterizes the polynomial divisibility criterion by checking the following equations:

• $e(E(u(z)),E(v(z)))=e(E(w(z)),E(1))\cdot e(E(t(z)),E(h(z)))$

• i.e. $e(E(u(z)),E(v(z)))/e(E(w(z)),E(1))= e(E(t(z)),E(h(z)))$

• i.e. checks $\left(\sum_{i=1}^ns_iu_i(x)\right)\cdot\left(\sum_{i=1}^ns_iv_i(x)\right)-\left(\sum_{i=1}^ns_iw_i(x)\right)=h(x)t(x)$

The verifier will accept if all checks hold.

Since now, the process is not zero-knowledge. If $V$ comes up with their own witness $s^\prime=(s_1^\prime,s_2^\prime,\cdots,s_n^\prime)$, they can compute $E(u^\prime(z)),E(v^\prime(z)),E(w^\prime(z)),E(h^\prime(z))$. If these values are different from $E(u(z)),E(v(z)),E(w(z)),E(h(z))$, then the verifier concludes that the prover’s witness is not $s^\prime$

Zero knowledge can be achieved by adding a random shift to the polynomials $u,v,w$. The random shift will be a multiple of $t(x)$, so that everything is still the same $\bmod~t(x)$. For random $\delta_1,\delta_2,\delta_3\in F_p$, the shifted polynomials is defined as

• $u_z(x)=u(x)+\delta_1 t(x)$

• $v_z(x)=v(x)+\delta_2t(x)$

• $w_z(x)=w(x)+\delta_3t(x)$

Then, $P$ will replace the unshifted terms with the shifted terms in its proof. For example, $E(u_z(x))=E(u(x)+\delta_1t(x))=E(u(x))E(\delta_1t(x))$

Groth-16 Protocol#

Groth-16 protocol is a more succinct implementation for zk-SNARK. Both the proof size and the verifier complexity is significantly lower than Pinocchno in Groth-16.

In Growth-16, since the prover knows the polynomial $\left(\sum_{i=1}^ns_iu_i(x)\right)\cdot\left(\sum_{i=1}^ns_iv_i(x)\right)-\left(\sum_{i=1}^ns_iw_i(x)\right)=h(x)t(x)$, the proof is defined as follows:

• $E(\alpha+u(z))$

• $E(\beta+v(z))$

• $E(\sum s_i\times(\beta u_i(z)+\alpha v_i(z)+w_i(z))+h(z)t(z))$

The verifier will checks: $e(E(\alpha+u(z)), E(\beta+v(z)))=e(E(\sum s_i\times(\beta u_i(z)+\alpha v_i(z)+w_i(z))+h(z)t(z)), E(1))e(E(\alpha), E(\beta))$

References#

A Review of zk-SNARKs

Zero Knowledge Proofs MOOC