深入瞭解 zk-SNARKs
這篇文章主要是更深入介紹zk-SNARKs，不可避免的會有”一些“數學出現，不過會盡量著重在數學式背後的意義，而不是深入探討數學公式，如果不知道什麼是zk-SNARKS的，可以先參考這篇跟這篇。
(Medium上數學符號支援有限，可參考原文，有比較好閱讀的數學表示式)
一開始的假設
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² + … + 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² + … + C_d^d) = E(1)^{C_0} * E(s)^{C_1}*E(s²)^{C_2}…E(s^d)^{C_d}
也就是Bob只需要給 E(1), E(s), E(s²),…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代表[1, 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 = α*a，這樣的一組點就叫做α-pair。若Alice回傳另一組α-pair，(a’, b’) 而 b’ = α*a’，則可以藉由這樣的關係來獲得P(s)。
因為 α 值是無法得知的（無法從b/a得知），所以要傳回一組新的α-pair (a’, b’)最直覺的想法是將(a, b)再乘上𝛾，所以(a’, b’) = (𝛾a, 𝛾b)，而 b’ = 𝛾b = 𝛾(α*a) = α*a’。接著，把這個概念延伸到多個點(d-KCA)，Bob提供(a_1, b_1), (a_2, b_2) … (a_n, b_n) N個點。相同的概念，將每組α-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*α*a_1 + c_2*α*a_2 + … + c_n*α*a_n
= α*(c_1a_1 + c_2a_2 + …+ c_na_n)
= α*a’
所以，
溫馨小提醒，接下來的數學式很多，不過都是類似的東西，不要被嚇到了，準備好了嗎！
剛剛是說明一個點到多個點，然後利用線性相加的方式再合成一對點(a’, b’)。接著，回到原本多項式P(x) = A(x)*B(x) — C(x)，而每個多項式都有一組α-pair，因此可得
目的，Bob需要再多給一組L_i，定義為L_i = A_i+B_i+C_i。所以假設
，若a_i=b_i=c_i=l_i（相同係數），則L(s) = A(s)+B(s)+C(s)。此時Bob再選擇一隨機值 β（但Alice不知道），就可以確保Alice只能選擇相同係數，才能使 β L(s) = β(A(s) + B(s) + C(s)) 。因此，可以確保A,B,C有相同的係數。（這一段不懂也沒關係，重點就是要有相同係數）
喘一下，這一小節是為了解決Alice回傳假的P(s)，所以藉由α-pair來確保Alice會遵守規範。而多點α-pair是為了取得多項式P(s)。
HH + ＫＣＡ
大部分的數學式都介紹完了，這邊把HH再加進來一起看。
***接下來的數學式子看起來更恐怖，不過只是把上面的式子用HH包裝起來，沒有新的東西，別擔心，慢慢看
最一開始的問題是Bob要隱藏s不讓Alice知道，所以使用HH隱藏了s（ E(1), E(s), E(s²),…E(s^n)）。那現在假設Bob提供的α-pair是(1, α), (s, αs) … (s^n, αs^n)，所以a = (1, s, s² …, s^n), b = (α, αs, αs², … ,αs^n)，看到這有沒有覺得很面熟，然後加上HH，可得
a = ( E(1), E(s), E(s²),…E(s^n) ),
b = ( E(1)^α, E(s)^α, E(s²)^α,…E(s^n)^α )
再來，我們把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(α_a A(s))
= E(a_1α_a A_1(s) + a_2α_a A_2(s) + … + a_nα_a A_n(s))
= E(α_a A_1(s))^{a_1}+E(α_a A_2(s))^{a_2} + … + E(α_a A_n(s))^{a_n}
E(B(s)), E(α_b B(s))跟E(C(s)), E(α_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}，則
把HH加入一起
再來，把之前的α-pair重新定義為
所以驗證 π_a’ ?= α_a*π_a 變成，e(π_a, E(α_a)) ?= e(π_a’, E(1))
而A(x)*B(x) — C(x) = H(x)*Z(x)變成
SNARKs
到這邊，小結一下，Bob會提供
而Alice則回傳
最後Bob驗證
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”，指的是應該被丟棄，而沒有人可以存取到的資料。像是α_a, α_b, α_c, β當然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(s)來證明她知道 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
Originally published at kimiwublog.blogspot.com.
