zk-SNARK 的注意事項

一份關於 zk-SNARK 的學習筆記，主要集中於 zk-SNARK 中的方程式。

ZK-SNARK 代表 零知識簡潔非互動知識論證。

zk-SNARK 的三個特性

完整性：每個具有有效見證的陳述都有一個能夠說服驗證者的證明。
健全性：具有無效見證的陳述沒有能夠說服驗證者的證明。
零知識：證明僅傳達有關陳述有效性的資訊，而不涉及證明者的見證。

基礎知識#

算術電路#

算術電路是一種計算多項式的模型。對於有限域 $F=\{0,\cdots,p-1\}$ （質數 $p>2$ ），算術電路 $C:F^n\rightarrow F$ 是一個有向無環圖（DAG），其中節點是加法和乘法閘，邊是連接線。DAG 中的每個節點都有兩個輸入和輸出。DAG 有一個最終輸出。

Pasted 2023-10-01T05!48!45.358Z

在一個 $m$ - 閘， $n$ - 線的算術電路中，見證定義為 $s=(s_1,s_2,\cdots, s_n)$ ，其中 $s_i$ 是第 $i$ 條線的值。

Rank-1 約束 (R1CS) 定義如下：對於某些常數 $\{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}$ 。例如，在圖 1 中， $s_1\cdot s_2=s_4$ 是一個 R1CS，其中 $u_{1,1}=1,v_{2,1}=1,w_{4,1}=1$ ，其他 $=0$ 。

二次算術程序 (QAP)#

首先，我們定義目標點為 $r_1,r_2,\cdots,t_m\in F_p$ 。每個目標點對應於算術電路中的一個閘。然後，我們定義消失函數 $t(x)=\Pi_{q=1}^m(x-r_q)$ ，使得 $t(x)=0$ 在目標點 $r_1,r_2,\cdots,t_m$ 。

一個二次算術程序是關於 $s=(s_1,s_2,\cdots, s_n)$ 的一個關係，使得 $\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))$ ，其中 $u_i(x),v_i(x),w_i(x)$ 是度為 $m-1$ 的多項式，使得對於 $1\le i\le n,1\le q\le m$ ， $u_i(r_q)=u_{i,q}$ ， $v_i(r_q)=v_{i,q}$ 和 $w_i(r_q)=w_{i,q}$ 。

當 $x=r_q$ 時，這個方程是第 $q$ 個閘的 R1CS。因此，檢查這個方程等同於同時檢查 $m$ 個 rank-1 約束。

同態編碼#

同態編碼是一個單射同態 $E: F_p\rightarrow G$ ，使得給定 $E(x)$ 很難找到 $x$ 。

例如，給定一個質數階的循環群 $G$ ，以 $g$ 作為生成元，乘法作為群運算，同態編碼為 $E(a)=g^a$ 。它是同態且單射的。此外，根據離散對數問題的困難性，給定 $E(x)$ 也很難找到 $x$ 。

配對函數，或雙線性映射#

配對函數，也稱為雙線性映射，定義如下：

$G_1,G_2$ 和 $G_T$ 是質數階的群，配對函數為 $e:G_1\times G_2\rightarrow G_T$ ，使得：

如果 $g,h$ 分別是 $G_1$ 和 $G_2$ 的生成元，則 $e(g,h)\not= 1$ 是 $G_T$ 的生成元。
$e(g^a,h^b)=e(g,h)^{ab}$ 。

雙線性映射具有幾個性質，如下所示：

$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)$

在 Pinocchio 實現中（zk-SNARK 的一種實現），使用了對稱雙線性映射，其中 $G:=G_1=G_2$ 。

zk-SNARK#

對於任何 NP 計算，證明者和驗證者事先達成一致，他們可以為該計算構建一個算術電路，使得該電路的見證是原始計算的見證。算術電路可以簡化為 QAP，使得驗證 QAP 的見證等同於驗證算術電路的見證。因此，驗證 QAP 的見證等於驗證原始計算的見證。

從算術電路到 QAP 的一般簡化#

對於一個具有 $m$ - 閘和 $n$ - 線的算術電路，見證定義為 $s=(s_1,s_2,\cdots,s_n)\in R^n$ 。對於 $s$ 的 R1CS $(a_i,b_i,c_i)$ 定義為 $(s\cdot a_i)\times(s\cdot b_i)-s\cdot c_i=0$ ，其中 $1\le i\le m$ 且 $a_i,b_i,c_i\in R^n$ 。

一般簡化包括三個步驟：

堆疊 $m$ 個約束向量以獲得矩陣 $A,B,C\in R^{m\times n}$ ，其中
- $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}$
使用拉格朗日插值，找到 $3$ 組 $n$ 個多項式 $\{u_i\}_{i=1}^n,\{v_i\}_{i=1}^n,\{w_i\}_{i=1}^n$ ，使得
- 對於所有 $i\in[n]$ 和 $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}$
找到多項式 $h(x)$ ，使得
- $\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)$
- 其中 $t(x)=(x-1)(x-2)\cdots(x-n)$

因此，檢查 $\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)$ 等同於檢查算術電路中的 R1CS 關係。也就是說，見證可以滿足每個節點中的所有 R1CS 關係。

Pinocchio 協議#

Pinocchio 協議是 zk-SNARK 的一種實現。

該協議建立在一個質數階的群 $G$ 上，生成元為 $g$ 。定義同態編碼為 $E:F_p\rightarrow G$ ， $E(x)=g^x$ 。定義一個橢圓曲線雙線性映射為 $e:G\times G\rightarrow G_T$ 。證明者知道見證 $\{s_i\}_{i=1}^n$ ，並且他可以通過簡化獲得以下方程： $\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)$ 。

主要思想如下：

$V$ 在隨機點 $z\in F_p$ 測試 $P$ 的多項式
$P$ 計算 $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)$ 和 $h(z)$ ，並同態編碼這些值並發送給 $V$
$V$ 可以驗證同態編碼的值滿足相同的方程，而不需要了解見證本身。

Pinocchio 協議由三個步驟組成：（1）可信第三方生成公共參考字符串（CRS）；（2）證明者生成證明；（3）驗證者檢查證明並決定接受或拒絕。

在 CRS 生成過程中，可信第三方隨機選擇 $\alpha, \beta_u,\beta_v,\beta_w,\gamma,z\in F_p^*$ 並發布 CRS。然後，可信第三方丟棄其生成過程中使用的所有抽樣群元素（有毒廢物）。CRS 包含證明者的評估密鑰和驗證者的驗證密鑰。

評估密鑰定義如下：

$\{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$

驗證密鑰定義如下：

$E(1),E(\alpha),E(t(z))$
$E(\gamma),E(\beta_u\gamma),E(\beta_v\gamma),E(\beta_w\gamma)$

在證明生成過程中，由於證明者知道多項式 $\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)$ ，他將首先計算 $h(x)$ 。然後，證明者使用評估密鑰生成證明，如下所示：

$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))$

例如，

$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))$ ： $z^i$ 的線性組合，可以從 $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))$

在證明驗證過程中，驗證者將進行三次驗證。

首先，驗證者檢查項 $u(z), v(z), w(z), h(z)$ 是否作為 CRS 中項的線性組合構建，通過檢查以下方程：

$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))$

然後，驗證者檢查每個項 $u(z), v(z), w(z)$ 是否使用相同的線性係數生成，即檢查是否 $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))$

最後，驗證者檢查描述多項式可除性標準的關鍵條件，通過檢查以下方程：

$e(E(u(z)),E(v(z)))=e(E(w(z)),E(1))\cdot e(E(t(z)),E(h(z)))$
即 $e(E(u(z)),E(v(z)))/e(E(w(z)),E(1))= e(E(t(z)),E(h(z)))$
即檢查 $\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)$

如果所有檢查都通過，驗證者將接受。

由於現在的過程不是零知識。如果 $V$ 提出自己的見證 $s^\prime=(s_1^\prime,s_2^\prime,\cdots,s_n^\prime)$ ，他們可以計算 $E(u^\prime(z)),E(v^\prime(z)),E(w^\prime(z)),E(h^\prime(z))$ 。如果這些值與 $E(u(z)),E(v(z)),E(w(z)),E(h(z))$ 不同，則驗證者得出結論，證明者的見證不是 $s^\prime$ 。

通過向多項式 $u,v,w$ 添加隨機偏移，可以實現零知識。隨機偏移將是 $t(x)$ 的倍數，因此一切仍然是相同的 $\bmod~t(x)$ 。對於隨機的 $\delta_1,\delta_2,\delta_3\in F_p$ ，偏移多項式定義為

$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)$

然後， $P$ 將在其證明中用偏移項替換未偏移項。例如， $E(u_z(x))=E(u(x)+\delta_1t(x))=E(u(x))E(\delta_1t(x))$

Groth-16 協議#

Groth-16 協議是 zk-SNARK 的一種更簡潔的實現。證明大小和驗證者複雜度都顯著低於 Pinocchio 的 Groth-16。

在 Groth-16 中，由於證明者知道多項式 $\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)$ ，證明定義如下：

$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))$

驗證者將檢查： $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))$

參考文獻#

A Review of zk-SNARKs

Zero Knowledge Proofs MOOC