全面理解零知識證明

原文標題：《 分析｜零知識證明 》

原文作者： CryptoYC Tech，CryptoYC Labs

零知識證明由 S.Goldwasser, S.Micali 和 C. Rackoff 在二十世紀 80 年代提出。此證明的意義在於不用向對方展示證明或解題的過程，使對方相信某個結論是正確的。零知識證明被大量地運用在密碼學中，並且高度證明了此概念和應用可以解決很多問題。

零知識證明定義

零知識證明：zkSNARK，zero-knowledge Succint Non-interactive ARguments of Knowledge 的簡稱：

Succinct：證明的數據量比較小

Non-interactive：沒有或者只有很少交互。

ARguments：驗證者只對計算能力有限的證明者有效。擁有足夠計算能力的證明者可以僞造證明。這也叫「計算可靠性"（相對的還有」完美可靠性"）。

of Knowledge：對於證明者來說在不知道證據（Witness，比如一個哈希函數的輸入或者一個確定 Merkle-tree 節點的路徑）的情況下，構造出一組參數和證明是不可能的。

零知識證明示例———以數獨爲例

證明

有一天，小明出了一道非常難的數獨題，小紅花了很長時間嘗試去解開這個數獨，但是怎麼都解不出結果。小紅覺得小明在耍她，「這題壓根就無解！小明你耍我！」，她跑到小明那抱怨。「我能證明給你看這題是有解的，而且我知道這個解」，小明淡定的回答道。「好啊」，小紅暗自想着，「哼哼，等你證明給我看之後，我就把解記下來然後去戲耍下小剛，給他也做一下這題。」小明接着說：「我會用零知識證明的方法給你證明我會這題的解。也就是說我不會把解給你看，卻能讓你信服我確實有這題的解。」小紅並不相信他能這樣做到，還在想象小剛被耍的樣子。小明拿出 81（9x9）張空白的卡片放在桌上，在每張紙上寫上 1-9 中的一個數字，他讓小紅轉過身閉上眼，然後把這 81 張卡片小心翼翼地按照解的排列放在桌上，代表謎底的卡片，數字面朝下放在桌上；代表謎面的卡片，則數字面朝上放在桌上。

隨機試驗

小明放好卡片後，讓小紅睜開眼轉過身。小紅很激動，她覺得謎底就要揭曉了，很是開心。她可花了好幾天時間都沒能解出這題。小明對小紅說：「小紅，你不能偷看這些面朝下的卡片。」，明顯能看出小紅很失望，她以爲能看到完整的一個解。「但是我能讓你檢驗這些解：你可以隨意選擇按照行 (row)，或者按照列 (column)，或者按照 3x3 的九宮格 (box) 來檢驗我的解。你挑一種吧」小紅告訴小明她決定選擇按照行的方法來驗證。小明接着把每一行的 9 張卡片收起來單獨放到一個麻布袋裏。所有卡片都被收完放在了 9 個麻布袋裏。小明接着搖了搖每個麻布袋，把裏面的卡片順序都打散。最後把這 9 個麻布袋交給小紅。

驗證

「好了，你可以打開這些布袋了。「小明對小紅說，「每個布袋裏應該都有正好 9 張，沒有重複數字的，分別是數字 1-9 的卡片。」小紅打開每個布袋一看，還果真是這樣。

「可這啥都證明不了啊！我也可以這樣做給你看。我只要保證每一行都是 1-9 這 9 張卡片，不去管縱列和九宮格里的數字是不是也都是沒有重複的不就行了。「小紅說道。小明解釋說：「可是我事先也不知道你會選按照行來收集卡片，還是按照列，還是按照九宮格啊。我是按照題解來放置卡片的，你選啥我都沒在怕的。」

重複驗證

小紅還是不服氣。覺得小明仍然有可能在騙她，所以要求小明再把卡片復原，按照原來的方法，重新選。這樣接連試了幾次，小紅每次都選一個不一樣的試驗方法。試了好多次都是一樣的結果。小紅這下不得不承認，小明要麼運氣非常非常好，每次都能押中小紅會選擇哪種試驗方式，要麼就是他確實知道題解，（或者小明會讀心術能預先知道小紅會選什麼試驗方式）。小紅很失望，這麼多次試驗下來，她還是不知道真正的題解，她只知道每次小明放置卡片的排列裏很大機率每行每列每個九宮格確實都是沒有重複的 1-9，這就說明很大機率這題是有解的，而且小明很大機率確實知道這題的解。

零知識證明的本質就是在不揭曉我所知道或擁有的某樣東西的前提下，向別人證明我有很大機率（這點很重要，零知識證明說到底是一個概率上的證明）確實知道或擁有這個東西。

故事裏要證明的東西就是一個數獨題的解，小明讓小紅每次隨機抽取行，列，九宮格的卡片，並收集在一起隨機打亂，小紅通過拆開袋子並不能知道題解，但是卻能相信小明很大機率確實知道題解。

這個故事裏的 zk-SNIPM 也是半開玩笑地暗指了零知識證明現在最普遍的 zk-SNARKs（Zero-Knowledge Succinct Non-Interactive Argument of Knowledge）算法。故事中的 zk-SNIPM 雖然存在漏洞，但是他還有改進的餘地，比如用一臺掃描儀把第一次卡片的組合就全掃描下來，然後一次性同時驗證所有的試驗序列。這樣就很難通過試錯的方式來破解機器。

小明和小紅之間最開始那種互動式的證明方法暗指的是交互式零知識證明（interactive zero-knowledge proof）。交互式零知識證明需要驗證方（小紅）在證明方（小明）放好答案（commitment）後，不斷的發送隨機試驗。如果驗證和證明雙方事先串通好，那麼他們就可以在不知道真實答案的情況下開掛（simulate/forge a proof）。

非交互式的證明則不需要這種互動。但是會額外需要一些機器或者程序，並且需要一串試驗序列，這個試驗序列不能被任何人知道。有了這麼一個程序和試驗序列，證明機就能自動算出一個證明，並且能防止任何一方作假。

零知識證明分析———問題拆解

零知識證明大體由四部分組成：

多項式問題的轉化 - 需要證明的問題轉化爲多項式問題 t(x)h(x) = w(x)v(x)，證明者提交證明讓驗證者確認多項式成立。

隨機挑選驗證 - 隨機選擇驗證的數值 s，驗證 t(s)h(s) = w(s)v(s)。相對於驗證多項式相等 t(x)h(x) = w(x)v(x)，隨機挑選驗證，簡單，驗證數據少。隨機挑選驗證，安全性肯定不及多項式等式驗證，但如果確實足夠隨機，安全性還是相當高的。

同態隱藏 - 同態隱藏指的是函數的一種特性。輸入的計算和輸出的計算保持「同態」。以加法同態爲例，滿足如下的三個條件的函數 E(x)，稱爲加法同態：

1. 給定 E(x)，很難推導出 x. 

2. 不同的輸入，對應不同輸出 3. E(x+y) 可以由 E(x)，E(y) 計算出來。乘法同態類似。

零知識 - 證明者和驗證者之間除了「問題證明與否」知識外，不知道其他任何知識（不知道隨機挑選值，不知道挑選值的多項式計算結果等等）。

多項式問題轉化

NP 問題以及約化   

解決一個問題需要花費時間。如果解決問題需要的時間與問題的規模之間是多項式關係，則可以稱該問題具有多項式複雜度。一般問題可分成兩類：P 問題和 NP 問題。P 問題指的是在多項式時間內可解的問題。 NP 問題（Non-Deterministic Polynomial Problem，非確定性多項式問題），指不能在多項式內可解，但是可以在多項式時間內驗證的問題。

很顯然，P 問題也是 NP 問題，但是是否 NP 問題是 P 問題，NP=P？，目前爲止還沒有人能證明。一般認爲，NP 問題不等於 P 問題，也就是說，NP 問題不存在多項式解法。

約化 (Reduction)，可以理解成問題的轉化。對任意一個程序 A 的輸入，都能按某種法則變換成程序 B 的輸入，使兩程序的輸出相同，那麼，可以說，問題 A 可約化爲問題 B。

NPC 問題，是一個 NP 問題，並且，其他所有的 NP 問題都能歸約到它。簡單的說，NP 問題之間可以相互歸約，一個 NP 問題求解，其他 NP 問題一樣能求解。

舉例說明，NP 問題以及 NP 問題的歸約。

布爾公式滿足性問題（SAT 問題，boolean formula satisfiability) 就是一個 NP 問題。布爾公式定義如下：

•假設變量 x1  , x2  , x3  , ... 是布爾公式

•假設 f 是布爾公式， ￢f 也是布爾公式（取反）

•假設 f 和 g 是布爾公式， f∧g 和 f∨g 也是布爾公式（與和或）

一個布爾公式可滿足，指輸入是 0/1 的情況下，存在輸出爲真。SAT 問題指，找出所有可滿足的布爾公式。SAT 問題看上去，除了枚舉一個個可能的布爾公式外，沒有更好的辦法，也就是多項式時間內不可解。如果知道一個可滿足的布爾公式，驗證非常方便（輸入是 0/1 的情況下，看看輸出是否爲真）。SAT 問題是 NP 問題。

再看看另外一個 NP 問題：PolyZero 問題。PolyZero 問題指某個多項式滿足：多項式輸入是 0 或 1 的情況下，多項式輸出爲 0。

PolyZero(f):=1

f 滿足輸入是 0/1 的情況下，多項式輸出爲 0。

一個布爾表達式 f 可以通過如下的歸約函數 r，轉化爲多項式：

•r(xi ):=(1-xi )

•r(￢f):=(1-r(f))

•r(f∧g):=(1-(1-r(f))(1-r(g)))

•r(f∨g):=r(f)r(g)

也就是說，一個 SAT 問題，通過歸約函數 r，可以歸約爲一個 PolyZero 問題：f 是可滿足的，當且僅當 r(f) 輸出爲 0。

SAT(f)=PolyZero(r(f))

總結一下，NP 問題是在多項式時間內無解，但是可以可以多項式時間驗證的問題。NP 問題可以相互歸約。

QSP 問題

需要證明的問題，肯定是 NP 問題，如果是 P 問題，不存在問題解的」尋找「，也就不存在證明。簡單的說，zkSNARK 問題處理的都是 NP 問題。既然 NP 問題相互可以歸約，首先需要確定一個 NP 問題，其他 NP 問題都可以歸約到這個 NP 問題，再進行證明。也就是，證明了一個 NP 問題，就可以證明所有 NP 問題。QSP 問題是個 NP 問題，也特別適合 zkSNARK。

給定一系列的多項式，以及給定一個目標多項式，找出多項式的組合能整除目標多項式。輸入爲 n 位的 QSP 問題定義如下：

給定多個多項式：v0 ,...,vm ,w0 ,...,wm

目標多項式：t

映射函數：f:{(i,j)∣1≤i≤n,j∈0,1}→{1,...m}

給定一個證據（Witness）u，滿足如下條件，即可驗證 u 是 QSP 問題的解：

ak ,bk =1  如果 k=f(i,u[i])

ak ,bk =0  如果 k=f(i,1-u[i])

va wb 能整除 t，其中 va =v0 +a1 v1 +...+am vm ,wb =w0 +b1 w1 +...+bm wm

對一個證據 u，對每一位進行兩次映射計算（u[i] 以及 1 -u[i] ），確定多項式之間的係數。因爲針對證據 u 的每一位，計算兩次，確定多項式之間的係數，如果 2n < m，多項式的選擇還是有很大的靈活性。

如果證明者知道 QSP 問題的解，需要提供證據（也就是 u）。驗證者在獲知證據 u 的情況下，按照上述的規則恢復出多項式的係數，驗證 va vb  是否能整除 t ：th=va wb  。爲了方便驗證者驗證，證明者可以同時提供 h。在多項式維度比較大的情況下，多項式的乘法還是比較複雜的。

有個簡單的想法，與其驗證者驗證整個多項式是否相等，不如隨機挑選數值進行驗證。假設驗證者隨機挑選驗證數值 s，驗證者只需要驗證 t(s)h(s)=va (s)wb (s) 。

多項式證明問題舉例

多項式問題的證明過程

假設一個多項式

證明一個多項式，即給定一個輸入 x，提供 f(x) 的證明。

3.1 有線羣論基礎（橢圓曲線）

定一個有限羣，生成元是 g，階爲 n，則該羣包括如下的元素：g0,g1,g2,...,gn−1。通過有限羣加密的方式很簡單：E(x):=gx。也就是說，得知 gx 的情況下，不能反推出 x。

3.2 選定隨機數

驗證者隨機選擇一個有限羣中的元素，比如 s。提供如下的計算結果（s 的不同階的加密結果）：

E(s0),E(s1),...,E(sd)

在生成這些計算結果後，s 就不需要了，可以忘記。

3.3E(f(s)) 計算

舉個例子, f(x)=4+2x+4x2 , E(f(s))=E(s0)4E(s1)2E(s2)4。顯然, E(f(s)) 可以不知道 s 的情況下，通過驗證者提供的數據計算出來。

多項式證明問題舉例

多項式問題的證明過程

3.4α 對

注意的是，驗證者是不知道待證明的多項式參數的，即使證明者提供了 E(f(s)) ，驗證者也無法驗證。 α 對的方法可以讓驗證者確認證明者是通過多項式計算出結果。在 3.2 的基礎上，驗證者還隨機選擇另外一個元素 α ，並提供額外的計算結果：

E(αs0),E(αs1),...,E(αsd)

證明者需要提供 E(f(s)) 和 E(αf(s)) 。

E(f(s))=E(s0)4E(s1)2E(s2)4

E(αf(s))=E(αs0)4E(αs1)2E(αs2)4

3.5 配對函數

配對函數 e，滿足如下定義：

e(gx,gy)=e(g,g)xy

驗證者驗證α對的方式很簡單，檢驗如下的等式是否成立：

e(E(f(s)),gα)=e(E(αf(s)),g)

假設 A=e(E(f(s)),B=E(αf(s)) 推導過程如下：

e(A,gα)=e(E(f(s)),gα)=e(gf(s),gα)=e(g,g)αf(s)

e(B,g)=e(E(αf(s)),g)=e(gαf(s),g)=e(g,g)αf(s)

到此爲止，驗證者提供α對的情況下，證明者可以證明通過某個多項式計算出某個結果，驗證者不知道具體的多項式的參數

多項式證明問題舉例

多項式問題的證明過程

3.6 δ 偏移

更進一步，證明者採用δ 偏移，甚至不想讓驗證者知道 E(f(s))。採用δ 偏移，證明者不再提供 A 和 B，而是隨機一個δ參數，提供 A′和 B′。

很顯然，驗證者從 A′無法推導出 E(f(s))，但驗證者一樣能驗證α對的配對函數是否成立：

多項式證明問題舉例--整體過程 

QSP 問題的 skSNARK 證明

 skSNARK 證明過程分爲兩部分：

a) setup 階段 

b）證明階段。QSP 問題就是給定一系列的多項式 v0,...,vm,w0,...,wm 以及目標多項式 t，證明存在一個證據 u。這些多項式中的最高階爲 d。

4.1 setup 和 CRS

CRS - Common Reference String，也就是預先 setup 的公開信息。在選定 s 和α的情況下，發佈如下信息：

s 和α的計算結果   

多項式的α對的計算結果  

多項式的βv,βw,γ 參數的計算結果

4.2 證明者提供證據

在 QSP 的映射函數中，如果 2n < m，1, ..., m 中有些數字沒有映射到。這些沒有映射到的數字組成 Ifree，並定義（k 爲未映射到的數字）：  

證明者需提供的證據如下  

4.3 驗證者驗證

在 QSP 的映射函數中，如果 2n < m，1, ..., m 中所有映射到的數字作爲組成係數組成的二項式定義爲（和 vfree 互補）：

驗證者需要驗證如下的等式是否成立：  

至此，zkSNARK 的推導邏輯就基本完整。使用 zkSNARK 證明，由如下的幾步組成： 

問題轉化：一個需要證明的 NP 問題轉化爲選定的 NP 問題（比如 QSP 問題）

設置參數（setup）：設置參數的過程也是挑選隨機數的過程，並提供 CRS

證明者獲取證據 u，通過 CRS 計算證據（proof）

驗證者驗證證據以及響應的 proof 

原文鏈接

歡迎加入律動 BlockBeats 官方社群：

Telegram 訂閱群：https://t.me/theblockbeats

Telegram 交流群：https://t.me/BlockBeats_App

Twitter 官方帳號：https://twitter.com/BlockBeatsAsia