深入瞭解 zk-SNARKs

這篇文章主要是更深入介紹zk-SNARKs，不可避免的會有”一些“數學出現，不過會盡量著重在數學式背後的意義，而不是深入探討數學公式，如果不知道什麼是zk-SNARKS的，可以先參考這篇跟這篇。

一開始的假設
1. Alice有一個多項式P(x)
2. Bob選一個點 s 給Alice
3. Alice回傳P(s)給Bob

希望能達到
1. Alice不知道點 s，Bob不知道多項式P(x)。(Blindness)
2. 但Alice可傳回P(s)給Bob，並且Bob可以驗證P(s)。(verifiable)
也就是雙方都不知道對方的資訊，卻可以共同得到一個可被驗證的結果

上面就是基本的假設。然後，先定義一些基本的數學式
上述所提的多項式定義為：
$$P(x) = C_0+C_1x+C_2x^2 + ... + C_nx^n$$
首先，先介紹Homomorphic Hiding(同態隱藏)[1]，藉由同態隱藏可以達到隱藏資訊的目的。我們從數學定義來看他有什麼特質。首先$E(x)$的定義為$E(x) = g^x$ ，然後 $E(x+y) = E(x)*E(y)$
HH支援線性相加，所以下列式子成立
$$E(ax+by) = g^{ax+by} = g^{ax}*g^{by} =E(x)^a + E(y)^b$$

* HH的假設：知道$E(x)$，是無法回推x的值

若我們對$P(x)$作同態隱藏， 可以得出
$$E(P(x)) = E( C_0+C_1x+C_2x^2 + ... + C_d^d) = E(1)^{C_0} * E(s)^{C_1}*E(s^2)^{C_2}...E(s^d)^{C_d}$$
也就是Bob只需要給$E(1), E(s), E(s^2),...E(s^d)$，而不用給s（$E(s)$無法反推出s），Alice就可以得出E(P(s))的值。藉此可以達成第一點的blindness，接下來就是要如何達成verifiable，因為Alice有可能給一個假的值，非P(x)上的點，所以要確保Alice會乖乖地照規矩來。接下來就要介紹如何保證Alice會送出正確的結果，並且Bob可以驗證。


Computation --> Arithmetic Circuit --> R1CS --> QAP --> zk-SNARK

接著我們回到SNARKs基本的計算

SNARKs無法處理所有的問題，只能處理符合某種特定"形式/格式"的問題，SNARKs才能解決，而那特定的"形式/格式"就稱為QAP（quadratic arithmetic program）。
首先，要先把問題用Arithmetic Circuit跟R1CS做簡化。簡單來說就是把複雜的數學式子簡化成基本的+-*/，例如：我們要求$(c1⋅c2)⋅(c1+c3)=7$，把式子拆解成許多單一運算的結合。如下：

// Arithmetic Circuit
S1 = C1 * C2
S2 = C1 + C3
S3 = S1 * S2

接著我們定義一組向量(a, b, c)，使得$s . a * s . b - s . c = 0$。其中s代表[C1, C2, C3, S1, S2, S3]，所以可以得到陣列

// R1SC
// S1 = C1 * C2
a=[0,1,0,0,0,0,0]
b=[0,0,1,0,0,0,0]
c=[0,0,0,0,1,0,0]

// S2 = C1 + C3
a=[1,0,0,0,0,0,0]
b=[0,1,0,1,0,0,0]
c=[0,0,0,0,0,1,0]

// S3 = S1 * S2
a=[0,0,0,0,1,0,0]
b=[0,0,0,0,0,1,0]
c=[0,0,0,0,0,0,1]

接著就是重點！
再來要將上面的向量組轉成多項式，而這個轉換的過程就叫做QAP。QAP利用Lagrange interpolation，將a, b, c三組向量轉換成多項式$A'(x), B'(x), C'(x)$，所以原本的式子變成$P(x) = s.A'(x)*s.B'(x)-s.C'(x)$。接著，我們定義 $P(t)=0$ 當t = 1, 2, 3...，而$P(t)=0$ 相當於$P(t)$可以被$(x-t)$整除，因此，存在著$H(x)$，可以滿足
$$P(x) = A(x)*B(x) - C(x) = H(x)*Z(x),         Z(x) = (x-1)(x-2)...$$

＊ 這裡為了簡化式子，$s.A'(x) = A(x), s.B'(x)=B(x), s.C'(x)=C(x)$

到這裡先暫停一下，讓大腦喘息一下。這一小段的重點在於QAP的多項式，所以在Arithmetic Circuit跟R1CS沒有多著墨（細節可以看Vitalik的Quadratic Arithmetic Programs: from Zero to Hero的前半段，或是snarks-explain 5 ）。這個多項式這SNARKs是核心的一個概念，之後的驗證也是基於這個多項式，所以如果看沒有很懂，就記住$P(x) = A(x)*B(x) - C(x) = H(x)*Z(x)$這個重要的方程式就好ＸＤ。

ＫＣＡ（Knowledge of Coefficient Test and Assumption）

回到原本的問題，”Alice回傳$P(s)$給Bob驗證“，原本Bob在不知道$P(x)$的狀況下，無法驗證$P(s)$，但是藉由QAP把問題轉化後，Alice回傳$P(s)$跟$H(s)$，Bob藉由驗證$P(s) ?= H(s)Z(s)$來驗證$P(s)$（避免讓數學式看起來太複雜，這裡我們先忽略同態隱藏，$P(s)$應該是$E(P(s))$）。接下來的問題是，Alice有機會假造$H'(s)$使得$P'(s) == H'(s)Z(s)$，這就是這節的重點，要怎麼逼迫Alice遵守規範。
概念上就是Bob不止提供一個點，而是提供一對有關聯性的點(a, b)， $b = \alpha*a$，這樣的一組點就叫做α-pair。若Alice回傳另一組α-pair，(a', b') 而 $b' = \alpha*a'$，則可以藉由這樣的關係來獲得P(s)。
因為$\alpha$值是無法得知的（無法從b/a得知），所以要傳回一組新的α-pair (a', b')最直覺的想法是將(a, b)再乘上𝛾，所以(a', b') = (𝛾a, 𝛾b)，而 b' = 𝛾b = 𝛾($\alpha*a$) = $\alpha*a'$。

接著，把這個概念延伸到多個點，Bob提供$(a_1, b_1), (a_2, b_2) ... (a_n, b_n)$ N個點（d-KCA）。相同的概念，將每組α-pair乘上一個值，
$(a', b') = (c_1a_1 + c_2a_2 + ...+ c_na_n, c_1b_1 + c_2b_2 + ... c_nb_n)$
$b'$ 也一樣合乎一樣的關係，
$b' = c_1b_1 + c_2b_2 + ... +c_nb_n  = c_1\alpha a_1 + c_2\alpha a_2 + ... + c_n\alpha a_n = \alpha(c_1a_1 + c_2a_2 + ...+ c_na_n) = \alpha a'$
所以，$(a', b') = (\sum_{i=1}^{n} c_ia_i, \sum_{i=1}^{n} c_ib_i)$。（若$a_i$ 的值是$1, s, s^2…s^n$ ，$c_i$ 就相當於$P(x)$參數，所以可以把$a'$視為$P(s)$）

溫馨小提醒，接下來的數學式很多，不過都是類似的東西，不要被嚇到了，準備好了嗎！

剛剛是說明一個點到多個點，然後利用線性相加的方式再合成一對點$(a', b')$。接著，回到原本多項式$P(x) = A(x)*B(x) - C(x)$，而每個多項式都有一組α-pair，因此可得
$A : (\sum_{i=1}^{n} a_iA_i(s), \alpha_a(\sum_{i=1}^{n} a_iA_i(s)))$
$B : (\sum_{i=1}^{n} b_iB_i(s), \alpha_b(\sum_{i=1}^{n} b_iB_i(s)))$
$C : (\sum_{i=1}^{n} c_iC_i(s), \alpha_c(\sum_{i=1}^{n} c_iC_i(s)))$

然後，我們要確保A,B,C有相同的係數（aka. $a_i = b_i = c_i$）。為了達成此目的，Bob需要再多給一組$L_i$，定義為$L_i = A_i+B_i+C_i$。所以假設$L(s) = \sum_{i=1}^{n} l_iL_i(s)$，若$a_i=b_i=c_i=l_i$（相同係數），則$L(s) = A(s)+B(s)+C(s)$。此時Bob再選擇一隨機值$\beta$（但Alice不知道），就可以確保Alice只能選擇相同係數，才能使$\beta L(s) = \beta(A(s) + B(s) + C(s))$ 。因此，可以確保A,B,C有相同的係數。（這一段不懂也沒關係，重點就是要有相同係數）

喘一下，這一小節是為了解決Alice回傳假的P(s)，所以藉由α-pair來確保Alice會遵守規範。而多點α-pair是為了取得多項式P(s)。

HH + KCA

大部分的數學式都介紹完了，這邊把HH再加進來一起看。

***接下來的數學式子看起來更恐怖，不過只是把上面的式子用HH包裝起來，沒有新的東西，別擔心，慢慢看

最一開始的問題是Bob要隱藏s不讓Alice知道，所以使用HH隱藏了s（$E(1), E(s), E(s^2),...E(s^n)$）。那現在假設Bob提供的α-pair是$(1, \alpha), (s, \alpha s) ... (s^n, \alpha s^n)$，所以$a = (1, s, s^2 ..., s^n), b = (\alpha, \alpha s, \alpha s^2, ... ,\alpha s^n)$，看到這有沒有覺得很面熟，然後加上HH，可得
$a = (E(1), E(s), E(s^2),...E(s^n)),$
$b = (E(1)^\alpha, E(s)^\alpha, E(s^2)^\alpha,...E(s^n)^\alpha)$

再來，我們把HH用到KCA的式子上
$E(A(s)) = E(a_1A_1(s) + a_2A_2(s) + ... + a_nA_n(s)) = E(A_1(s))^{a_1}+E(A_2(s))^{a_2} + ... + E(A_n(s))^{a_n}$
$E(\alpha_a A(s)) = E(a_1\alpha_a A_1(s) + a_2\alpha_a A_2(s) + ... + a_n\alpha_a A_n(s)) = E(\alpha_a A_1(s))^{a_1}+E(\alpha_a A_2(s))^{a_2} + ... + E(\alpha_a A_n(s))^{a_n}$

$E(B(s)), E(\alpha_b B(s))$跟$E(C(s)), E(\alpha_c C(s))$同理，就不列出來了....

Elliptic Curve Pairing/Bilinear maps

加了HH之後，運算上會有問題，也就是$E(A(x))$無法乘以$E(B(x))$減$E(C(x))$，這時候就需要神奇的橢圓曲線了...

這裡不推導數學式子，直接介紹pairing的特性
簡單來講，就這兩個式子
$e(P+R, Q) = e(P, Q) * e(R, Q)$
$e(P, Q+S) = e(P, Q) * e(P, S)$

這樣看有點抽象，舉實際的例子幫助理解，假設$e(g^x, g^y) = e(g,g)^{xy}$，則
$e(3, 4+5) = g^{3*(4+5)} = g^{27}$
$e(3,4)*e(3,5) = g^{3*4}*g^{3*5}=g^{12}*g^{15}=g^{27}$

把HH加入一起
$E(ax_1+bx_2) = e(E_1(ax_1+bx_2), E_2(1))$
$= e(E_1(x_1)^a+E_1(x_2)^b, E_2(1))$
$= e(E_1(x_1)^a, E_2(1)) + e(E_1(x_2)^b, E_2(1))$
$= E(x_1)^a+E(x_2)^b$

再來，把之前的α-pair重新定義為
$\pi_a = E(A(s)), \pi_a' = E(\alpha_a A(t))$
$\pi_b = E(B(s)), \pi_b' = E(\alpha_b B(t))$
$\pi_c = E(C(s)), \pi_c' = E(\alpha_c C(t))$

所以驗證$\pi_a' ?= \alpha_a\pi_a$變成，$e(\pi_a, E(\alpha_a)) ?= e(\pi_a', E(1))$
而 $$A(x)*B(x) - C(x) = H(x)*Z(x)$$ 變成
$$e(\pi_a, \pi_b)/e(\pi_c, E(1)) ?= e(\pi_h, E(Z(s))),  \pi_h = E(H(s))$$

SNARKs

到這邊，小結一下，Bob會提供
三組α-pair，
$(\sum_{i=1}^{n} a_iA_i(s), \alpha_a(\sum_{i=1}^{n} a_iA_i(s))),$
$(\sum_{i=1}^{n} b_iB_i(s), \alpha_b(\sum_{i=1}^{n} b_iB_i(s))),$
($\sum_{i=1}^{n} c_iC_i(s), \alpha_c(\sum_{i=1}^{n} c_iC_i(s)))$
跟一組驗證相同係數的多項式$L(s) = \beta\sum_{i=1}^{n}L_i(s)$
還有E(Z(s))：$E(1), E(s), E(s^2),...E(s^n)$

而Alice則回傳
$(\pi_a, \alpha_a \pi_a'), (\pi_b, \alpha_b \pi_b'), (\pi_c, \alpha_c \pi_c'), \pi_L'(=E(\beta L(s))), \pi_h$

最後Bob驗證
$e(\pi_a, \pi_b)/e(\pi_c, E(1)) ?= e(\pi_h, E(Z(s)))$


SNARKs的流程大概就這樣。在這個之後還有Alice對於Bob給予的α-pair做shift再回傳，才會讓zk(zero knowledge)的部份更完整。但這部份不影響SNARKs的理解，所以就不多介紹了，可以參考snarks-explain_6。

Non-interactive

所謂的non-interactive就是在沒有（或很少）互相溝通下，任何人都可以驗證，也就是Alice丟出的訊息全網路都可以驗證，不只有Bob。要達成這件事，只需要把Bob第一次傳給Alice的內容放到一個公共區域稱為CRS(common reference string)，網路裡的人都可以存取得到，因此證明者跟驗證者只須去CRS裡面取資訊即可。

此外，zk-SNARKs裡有所謂的"toxic waste"，指的是應該被丟棄，而沒有人可以存取到的資料。像是$\alpha_a, \alpha_b, \alpha_c, \beta$當然s也是。因為這些值若是被知道了，上面用來驗證的資訊就可以被假造，所以在CRS創造出來後，這幾個toxic waste就應該要被徹底消滅。

補充

在看SNARKs文章時，卡最久的是QAP，像KCA就是單純的數學推導，而同態隱藏或是pairing可以直接當作一種數學性質看，像是交換律一樣（a*b=b*a），所以可以帶入而先不用探究背後的證明。但是看在QAP時，總覺得似懂非懂，知道可以幹麻，卻又不清楚為什麼。加上有些文章會提到NP問題，這又有點牽涉到哲學問題，因此卡許久。
而什麼是NP問題，粗略不嚴謹地來說，就是在有限時間內，能夠"驗證"的是NP問題，而能"求解"的為P問題。第一個條件，是要在有限時間內，這個條件不難理解，若你的計算，時間複雜度是$2^n$，n稍微大一點，電腦應該就會跑到當住了 XD，所以電腦如果不能在一定時間內算出來，那求出來意義就不大了。再來，假設p = q*r，如果知道q, r 那很容易驗證q, r是p的因數，但是，知道p要求出q, r 就相對難上許多（假設p為很大的數）。還有像RSA，這類的也都算是NP問題。而目前無法證明NP ?= P，若有一天被證明NP==P，那現今很多的加密演算法就都無用了...
[2] 接著QAP做了什麼事，到底哪裡重要？
概念上：兩個多項式交集在隨機的n個點，若隨機在有限域（範圍很大，相較於n）中取一點，而那點是兩個多像是的交集，則有很高的機率，證明你是知道答案的。
實做上：是藉由多項式是否可被另一個多項式所整除（$P(x)/Z(x) ?= H(x)$）。所以Alice不用提供P(x)的解來證明她知道P(x)（事實上Alice也不知道，她只知道P'(x)），而是把問題被轉化為去驗證$P(x)/Z(x) ?= H(x)$以證明，因此驗證者(Bob)不需要知道實際的答案，但又能確定答案是對的。而這是了解SNARKs的重要關鍵。
＊ 在有的文章同態隱藏的表示會有點不同，$E(ax+by)=a*E(x) + b*E(y)$，而非文中的次方。此外，在文章中很多地方的+-*/只是示意，並非一般數的+-*/，這邊的表示式是follow zCash官網的表示方式，例如，在讀橢圓曲線的文章，會看到P+Q=R（部份的會寫P*Q=R），但這邊並不是兩個點的相加或是相乘，而是將兩點做某種運算。


Reference:
Explaining SNARKs series：ZCash官網的系列文章，前半部淺顯易懂
Zk-SNARKs: Under the Hood：Vitalik寫的文章，可以跟官網的相互對照看
Quadratic Arithmetic Programs: from Zero to Hero：Vitalik解釋QAP的文章
zkSNARKs in a nutshell：對於witness跟NP問題有詳細的解釋
[译] zkSNARKs（零知识证明）简述：上面的簡中翻譯
读懂区块链之零知识证明（zk-SNARK）：對岸寫得很詳細的一篇文章
零知识证明与zkSNARK