本文已更新至Githubhttps://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/5/zkp-crs.md
Once exposed, a secret loses all its power.
一旦洩露，秘密就失去了全部威力。
——Ann Aguirre
這已經是本系列的第五篇文章了，這一篇繼續深入非互動式零知識證明。本文約 12,000字。
回顧
探索零知識證明系列（一）：初識「零知識」與「證明」
探索零知識證明系列（二）：從「模擬」理解零知識證明：平行宇宙與時光倒流
探索零知識證明系列（三）：讀心術：從零知識證明中提取「知識」
探索零知識證明系列（四）：亞瑟王的「隨機」挑戰：從互動到非互動式零知識證明
追到這裡的讀者想必已對零知識證明有了一個大概的認識。你是否想過這個問題：零知識證明為何可行？這裡請大家思考一下（比如系列一（初識「零知識」與「證明」）中的地圖三染色問題的流程） …… （此處停留三分鐘）下面兩個要素似乎必不可少：
「互動」：驗證者透過多次反覆挑戰，把證明者作弊概率降低到一個極小的值
「隱藏隨機性」：驗證者產生讓證明者無法預測的隨機數進行挑戰
然而對於非互動式零知識證明—— NIZK 來說，如何實現上面兩點？在系列四（亞瑟王的「隨機」挑戰：從互動到非互動式零知識證明）我們介紹瞭如何採用「隨機預言機」來扮演一個虛擬的「第三方」角色，實現虛擬的「互動」與「隨機挑戰」。本文將深入講述另一種方法，如何透過一段共享的字串去除「互動」與「隱藏隨機性」。這個字串必須事先由「第三方」來隨機產生，這就是傳說中的「公共參考串」（Common Reference String，簡稱 CRS）。
CRS 的前世今生假如我們不借助任何其它手段，限定證明者 Prover 和驗證者 Verifier 只能進行「一次互動」來實現「零知識證明」，那麼他們只能證明「平凡」問題，也就是計算複雜類BPP（Bounded-error Probabilistic Polynomial time），而這個複雜度類大家一般猜想可能等價於P（但還懸而未決，沒有被證明！BPP可以理解為P+Randomness）。注：如果 Prover 與 Verifier 只做一次互動，在這樣的 NIZK 系統中，我們很容易能構造一個 Decision Procedure —— Verify(x, Sim(x))，來證明和證偽定理，因此只能證明平凡問題 BPP。平凡問題雖然也可以零知識證明，但沒有意義！怎麼理解呢？因為驗證者直接可以在多項式時間內根據「輸出」求解出「秘密輸入」，雖然驗證者能夠求解，但是「證明」本身並沒有額外為驗證者提供更多的「知識」。換句話說，不需要證明者出示證明，驗證者就知道命題為真，於是證明過程也是零知識的。因此，當我們討論「零知識證明」時，要考慮帶「秘密知識」的NP類問題。大家都知道，P問題是「確定性圖靈機」多項式時間內可以求解的複雜類，它的執行路徑對於輸入x是一個線性的狀態轉移。而NP問題是「不確定性圖靈機」多項式時間可以求解的問題類。所謂的不確定性圖靈機，就是它每次往前走一步是不確定的，有很多個選擇，只要任何一個執行路徑能到達終止狀態，就表示它解決了該問題x。換句話說，它的執行軌跡是一棵樹。那麼如果我們把不確定性圖靈機每一步的路徑選擇記錄下來（這個執行路徑的記錄叫做witness，也就是我們反覆提到的「知識」），那麼把(x, witness)交給一個確定性圖靈機，那麼它也能在多項式時間內解決掉x問題。再強調一下，「知識」能提高圖靈機的解決問題的能力。NP問題中存在著不想「洩露」給驗證者的知識witness，這時，在一個互動式證明系統中，證明者和驗證者在「知識」的掌握程度上是不對等的。為了保證證明過程的「零知識」，我們需要保證：模擬器與驗證者的不對等。可是，模擬器沒有witness啊，怎麼能讓他們不對等呢？上一篇我們介紹了「隨機預言機」，我們透過允許讓模擬器可以綁架「隨機預言精靈」的方式製造不平等。本篇將講述如何利用 CRS 來製造不平等。CRS 是一個在證明之前就已經公開的，並且在證明者與驗證者之間共享的，隨機字串。我們怎麼來使用 CRS 呢？直覺上，一串雙方都「知道」的資訊，並不會增加「知識」不對等的情況。首先大家會想，能不能直接用 CRS 作為隨機挑戰數呢？可不可以讓 CRS 來代替「隨機預言精靈」的角色？答案是不行！為什麼？這是因為 CRS 是在證明之前就已經產生了，如果證明者 Prover 提前知道了所有的隨機挑戰數，那麼很顯然這個隨機挑戰也就失去了意義。注：請大家回想下「隨機預言機」是如何保證證明者無法提前預測「隨機挑戰數」的？沒想明白的你，請重讀系列（四）。CRS 的使命就是讓「模擬器」與「驗證者」不平等。怎麼做呢？隱藏一些「秘密」進去。如果進一步追問，隱藏了「秘密」有什麼用呢？當然有用啦，在「理想世界」中，模擬器與抽取器才能很開心地玩耍起來（獲取某些超能力） ……1988年，Manuel Blum，Paul Feldman 和 Silvio Micali 三位先驅發表的論文「Non-Interactive Zero-Knowledge and Its Applications」（『非互動式零知識證明及其應用』[BFM88]）展示了「互動」與「隱藏隨機性」的不必要性。他們給出了一個地圖三染色問題的 NIZK 證明系統，在一段共享的隨機產生的字串（即CRS）的幫助下。不過，……，我不會告訴你這個方案需要共享大概n^4超長的 CRS，其中n是要證明的「命題」的長度。1990 年，Uriel Feige，Dror Lapidot 與 Adi Shamir 三人提出了另一種構造 NP 語言的 NIZK 方案 [FLS90]。與 [BFM88] 不一樣的是，這個 NIZK 方案不再基於特定的數論假設，而是基於一個密碼學工具 Trapdoor Permutation。在這個方案中，FLS 提出了「隱藏位元」（Hidden Bits）的概念，然後把 Hidden Bits 藏入了 CRS。對於模擬器而言，就可以透過修改 CRS 中的 Hidden Bits 來達到模擬的效果，從而體現出對驗證者 Verifier 的優越性。不過，這個方案需要共享更長的 CRS，超過k * n^5，這裡k是安全引數。此後，Hidden Bits 的思路被很多人採用，值得一提的是，Kilian 與 Petrank 採用了一種更巧妙的方法來使用 Hidden Bits [KP98]（這裡空間太小，寫不下:），成功地把 CRS 的長度縮減到了k * n^2。後來 J. Groth 繼續最佳化 ，把 CRS 的長度縮小到了大約k*n[Groth20a]。除了 Hidden Bits，J. Groth，R. Ostrovsky 與 A. Sahai [GOS06] 使用了同態加密方案 Boneh-Goh-Nissim [BGN05] 或 Boneh-Boyen-Shacham 來實現 NIZK，他們把加密方案的「公鑰」當做是 CRS，同時 Prover 加密作為證明，然後利用同態性質來證明另一個 NP-Complete 問題——布林電路的可滿足性問題。這個方案的最大優點，就是 CRS 長度是固定的，因為只是一個金鑰而已，長度只有k。對於模擬器而言，它可以透過超能力，拿到這個公鑰所對應的陷門，從而能夠實現密封任何資訊，但得到相同的密文；對於抽取器而言，它可以用超能力拿到公鑰對應的私鑰，從而能夠解密證明得到「知識」。Jens Groth 在 2010 年基於 KEA（Knowledge of Exponent Assumption） 假設與 Pairing 提出了一種新的 NIZK Arguments 方案[Gorth20b]，這也是後續許許多多 zkSNARKs 方案的起點。這裡的 CRS 由一對對的 （g^x^n, g^⍺x^n） 構成，被用來實現「知識承諾」。其中x與⍺是兩個隨機數，在產生完 CRS 之後，必須被「遺忘」。有些人把這部分需要遺忘的隨機數叫做「Toxic Wastes」，這容易誤導讀者。他們不僅無毒無害，而且非常有用。他們是被藏入 CRS 的「秘密」，是模擬器的武器。如果模擬器得到了x與⍺，就能偽造證明，從而保證證明的零知識。而對於抽取器，他能直接透過 KEA 假設內建的抽取函式來抽取知識。最新的 Sonic 方案[MBK+19]又在 [Groth20b] 的基礎上實現了 Updateable CRS。如果任何人擔心 CRS 中的秘密已經被洩露了，他就可以在原有 CRS 基礎上打一個補丁，繼續往裡藏一個秘密，這樣就能保證 CRS 的安全性。這裡的 CRS 還是「Universal 全域性」 的，即 CRS 只需要生成一次，就可以應付所有的命題證明。這個方案後續被最新的 Plonk[GWC19]，Marlin[CHMMVW19] 等方案採用。接下來，我們就從一個簡單的例子開始，理解如何基於 CRS 來構造 NIZK。在這之前，我們需要介紹一個 NP-Complete 問題——哈密爾頓環路問題。
哈密爾頓環路問題想象出一個地圖中有若干個城市，城市與城市間可以有公路。假如給你一副地圖，讓你找出一條路徑，不重複地走遍所有的公路（假設每條公路都是風景美如明信片的 Parkway，或許你想不重複地吃遍每條公路邊上的麥當勞，出於某種情懷）。相信你會馬上興奮起來，這不就是小時候學過的「一筆畫」麼？判斷一個地圖能否一筆畫，這是小學生做的數學題，我們可以計算每個城市連線的公路個數，根據奇偶性分成「奇點」與「偶點」。如果一個地圖中存在兩個奇點城市，那麼你只能從一個奇點城市出發，遍歷所有的公路，並且最終到達另一個奇點城市。這條路徑就被稱為「尤拉路徑」（Euler's Path）。如果一個地圖中所有的城市都是偶點，那麼你可以從任意一個城市出發，輕鬆地找出一條路徑，不重複地遍歷所有的公路，並且回到起點。這個環路被稱為「尤拉環路」（Euler's Circuit）。而如果地圖存在超過2個以上的奇點，那麼就不存在尤拉回路，比如著名的哥德斯堡七橋問題。著名的哥德斯堡七橋問題就是這麼描述，如果不重複地穿過下面七座橋。
哥德斯堡七橋地圖顯然存在多個奇點，不存在尤拉路徑。如果給定任何一個地圖，是否存在一個尤拉環路，這是一個 P 問題，也就是一個計算機可以在poly(n)多項式時間內尋找。注：尤拉環路的尋找演算法被稱為 Fleury演算法。而我們要講的是「哈密爾頓環路問題」描述如下：是否一個地圖存在一個環路，能不重複地穿過每一個城市。比如下面這張地圖：
我們用一個矩陣V * V的矩陣來表示這個地圖，凡是兩個城市（A, B）有公路相連線，那麼就在(A, B)和(B, A)裡面填上1，否則填0。這個矩陣被稱為「鄰接矩陣」，我們可以把這個鄰接矩陣拍扁，就變成了一個0/1位元串。尋找「哈密爾頓環路」是一個 NP-Complete 問題，也是一個 NP-Hard 問題。換句話說，不存在一個演算法使得計算機在poly(n)多項式時間內找到環路。但是，計算機可以在多項式時間內檢驗一個路徑是否是「哈密爾頓環路」。比如這個地圖中就有一個帶方向的哈密爾頓環路，我們一眼就能驗證這個環路確實穿過了每一個城市。如果一個地圖有哈密爾頓環路，那麼它的矩陣一定是滿足下面的特徵：每一行一定有一個1，每一列一定也有一個1。
ZK-HAM 協議我們下面給出一個三步互動的Sigma協議，Alice 向 Bob 證明她「知道」上面這個地圖G的哈密爾頓環路。公共輸入：G為一個有 6 個頂點的地圖，表示為一個6*6的鄰接矩陣秘密輸入：G的哈密爾頓環路C（圖中橙色的公路）
第一步：Alice 隨機選擇一個「置換」，Perm(.)，然後透過這個置換，產生一個新的圖G'；然後 Alice 把G'矩陣的每一個單元加密，產生一個新的矩陣傳送給 Bob。【名詞解釋】：所謂置換，大家可以想象成用滑鼠隨意拖動圖中的點，但是點和點之間的連線會跟著點一起被拖動，拖動結束之後形成的圖，進行重新編號就得到G'，比如上圖左側的兩個圖。經過置換變換的圖前後是同構的。其中下圖中，每一個頂點上角括號中的標號為拖動之前該頂點在上圖中的編號。形式化一點可以這麼定義：Perm()是一個 {1, V} 到 {1, V}的雙射函式新圖G'的鄰接矩陣，[perm(i), perm(i+1) ]=1當且僅當[i, i+1]=1，其中i是頂點編號，V是頂點個數 。第二步：Bob 隨機選擇b in {0, 1}}進行挑戰。
第三步情況（1）：Alice 根據 Bob 第二步傳送的值：如果b=0，那麼 Alice 傳送置換函式Perm()，並且揭示完整的圖G'。而 Bob 則確認G'是否是原圖G經過置換無誤。
第三步情況（2）：如果 Bob 第二步傳送的b=1，那麼 Alice 只揭示G'中的哈密爾頓環路C'即可。而 Bob 需要驗證C'是否是一個哈密爾頓環路回憶一下三步 Sigma 協議，我們再理解下上面看似複雜的動作：第一步：被稱為Commit，證明者 Alice 需要把手裡的答案進行同態變換，產生一個新答案，然後把每一條邊都鎖起來，交給 Bob；第二步：Bob 進行隨機挑戰；第三步：Alice 根據 Bob 的隨機挑戰，做出兩種不同的迴應。如果 Bob 挑戰0，那麼Alice 開啟第一步的承諾，表示自己在第一步沒有作弊；如果 Bob 挑戰1，那麼 Alice 只解密暴露出哈密爾頓環路的邊（公路），其它邊則不需解密。Bob 可以輕易地檢查地圖上露出來的那些邊是否構成了一個不重複地經過所有城市的環路。如果這個 Sigma 協議只走一遍的話， Alice 作弊的概率是 50%，如果重複 n 遍，Alice 作弊概率會指數級減小。大家可以試著用「模擬器」和「抽取器」的方法來證明這個協議的「零知識」與「可靠性」。
ZK-HAM 的變形：ZK-HAM-2接下來把上面的這個三步協議改動一下。大家先考慮下這樣一個簡單事實：如果一個僅包含環路的子圖C是 圖G的子圖，C <= G那麼說明G包含哈密爾頓環路。這個事實等價於另一個事實：一個哈密爾頓圖G的補集!G是環路子圖C的補集!C的子圖。【名詞解釋】圖的補集：所謂補集就是這樣一個新地圖，頂點保持不變，舊地圖上的邊在新地圖中不存在，而新地圖中的公路在舊地圖中不存在，但是兩個圖重合在一起，就變成了一個完全圖（完全圖是指任意兩個頂點之間都存在一條邊）。用鄰接矩陣來理解，就是如果一個圖G包含一個環路子圖C，那麼G矩陣中所有值為0的單元集合 必然被C矩陣中所有值為0的單元集合包含。可以表示為!G <= !C。根據第二個事實，我們可以定義如下的 Sigma 協議：公共輸入：圖G，表示為6*6的鄰接矩陣秘密輸入：G的哈密爾頓環路C（圖中橙色的公路）
第一步：Alice 隨機選擇一個「置換」，Perm(.)，並且透過C構造一個哈密爾頓環路子圖C'=Perm(C)；然後 Alice 加密C'的每一個單元，把解密後的結果傳送給 Bob。第二步：Bob 隨機選擇b in {0, 1}進行挑戰
第三步情況（1）：如果b=0，Alice 揭示完整的C'，而 Bob 驗證這個C'是否確實是一個哈密爾頓環路子圖。
第三步情況（2）：如果b=1，Alice 傳送Perm()，同時按照G'=Perm(G)中的所有含0單元所在的位置，揭示C'中所對應的單元；Bob 驗證C'所有被揭示單元是否全部為0。再理解下這三步 Sigma 協議：第一步：證明者 Alice 需要把哈密爾頓子圖C進行置換變換，產生一個新的哈密爾頓子圖C'，加密後交給 Bob；第二步：Bob 進行隨機挑戰，0或者1；第三步：如果 Bob 挑戰0，那麼 Alice 開啟第一步的承諾，展示一個帶有唯一環路的圖；如果 Bob 挑戰1，Alice 則按照G'中的0單元的位置開啟承諾，展示承諾中被開啟的位置全部為0。重點來了，大家仔細看看這個新版的 Sigma 協議的第一步。有沒有發現什麼情況？第一步 Alice 傳送的內容是與地圖G無關的！同樣，第二步 Bob 傳送的挑戰也是與地圖無關的。這樣我們可以把第一步發的承諾改成事先準備好的位元串，而且我們假設這個位元串由一個可信第三方來產生，這樣一來 Bob 就沒有必要傳送b=0這個分支，因為可信的第三方是誠實的，他一定是事先準備好一個正確的環路子圖。這樣，由於 Bob 只需要傳送1挑戰分支，那麼這一步也可以去除。於是，三步協議變成了一步，我們成功去除了互動，有望實現 NIZK 。我們接下來把ZK-HAM-2協議的第一步和第二步推到一個事先準備的字串中，然後只讓 Alice 傳送第三步的內容給 Bob。如下圖所示：
請注意，這裡還不算是一個 NIZK 系統，因為這個共享字串並不能對 Bob 公開，否則 Bob 就能算出環路C。接下來，我們要解釋一個新概念：「隱藏位元」（Hidden Bits）[FLS90]。Hidden Bits 是這樣一串隨機位元，它們對於驗證者 Bob 隱藏，但是對於證明者 Alice 公開。然後在證明過程中，Alice 可以選擇性地揭示一部分位元展示給 Bob 看。這是構造 NIZK 證明系統的一個利器，下面我們需要再繼續深入 ……
雲中的秘密：Hidden Bits讓我們再次開下腦洞，想象天上有朵雲，雲後面藏著一串隨機產生的位元值，不是0就是1，然後 Alice （證明者）帶著一個「超級眼鏡」，於是能夠看到雲後面所有的隨機位元串，但是 Bob （驗證者）卻看不到。同時 Alice 手裡還有一個「超級手電筒」，她可以開啟手電筒用鐳射穿透雲層，讓 Bob 也能看見其中某個或某些位元。當然，Bob 能看到的位元的選擇權完全在 Alice 手中。雲朵中隱藏的位元串就是所謂的Hidden Bits。
接下來我們要透過 Hidden Bits 來完成一個單步互動，完成ZK-HAM-2協議的功能。在ZK-HAM-2中的第一步，Alice 產生一個隨機的置換Perm()，然後透過G中的哈密爾頓環路子圖C產生一個變換後的環路子圖C'=Perm(C)。這等價於，事先由任何人產生一個隨機的哈密爾頓環路子圖C'，然後 Alice 根據C和C'計算得出一個相應的Perm()。假設由某個「第三方」產生了一個隨機的環路子圖C'，編碼成「鄰接矩陣」位元串，放到雲朵後面。假設V為頂點（城市）的個數，E為邊（公路）的條數。這個鄰接矩陣的編碼需要一個V*V長度的位元串，可以解釋成一個V*V的矩陣，其中每一行只包含一個1，每一列也只包含一個1，矩陣的其它單元都為0。接下來 Alice 如何構造證明呢？這其實很簡單：
Alice 透過「超級眼鏡」得到了一個隨機的哈密爾頓環路子圖C'，然後計算得到一個置換Perm()，使得Perm(C)=C'。Alice 根據Perm()來計算出一個換後的圖G'=Perm(G)Alice 產生證明，由兩部分組成：（1）置換Perm()（2）G'的鄰接矩陣中所有值為0的單元座標所對應的C'矩陣的值，相當於 Alice 需要用「超級手電筒」給 Bob 揭示的隱藏位元。那麼 Bob 怎麼驗證這個證明呢？Bob 拿到證明之後，只需要檢驗兩個東西：Perm()是否是一個合法的置換V -> V，比如不能出現兩個頂點對映到同一個頂點的情況。對於G中的每一條「非邊」，經過置換之後，Bob 抬頭看天上對應的「隱藏位元」，位元值必須為0我們再仔細地深入理解下這個非互動協議。先從「完備性」入手：如果 Alice 沒有作弊，那麼很顯然能夠透過 Bob 的驗證，這裡請大家自行檢查。接下來我們分兩步簡要證明下「可靠性」：首先，因為 Bob 經過驗證得知，所有G置換後的非邊集合都已被揭示，且全為0，那麼可以得出結論，!G <= !C，即G的非邊集合是環路子圖C的非邊集合的子集。這等價於，C <= G，也就是說G包含一個哈密爾頓環路。這裡請注意，這個可靠性概率是 100%。然後，設想在一個「理想世界」中，Bob 獲得了某種超能力（比如拿到 Alice 的「超級眼鏡」），不需要 Alice 的超級手電筒，就能看穿雲層，得到所有的隱藏位元C'。然後當 Bob 得到Perm()之後，就能透過Perm()反算出C，於是 Bob 就相當於變身成了一個「抽取器」（Extractor），在理想世界中，它能把 Alice 要證明的知識給成功抽取出來。那麼怎麼證明「零知識」呢？Alice 要具備一個超能力，就是在「理想世界」中，可以偷偷修改雲朵中的隱藏位元。接下來就簡單了，模擬器 Zlice 可以這麼欺騙 Bob：Zlice 把雲朵中的隱藏位元全部置為0Zlice 隨機產生一個合法的Perm()大家發現了，關鍵是，天上隱藏的位元必須是一個可信的字串，所謂「可信」，就是指它確實應該是一個哈密爾頓環路子圖。那麼第三方需要可信。可是，這樣一個第三方是不是難以令人滿意？Alice 和 Bob 要絕對信任他，不會和對手串謀。如果他和 Alice 串謀，可以把隱藏位元串直接設定為全0；或者他和 Bob 串謀，直接把這個位元串給 Bob 看。這個協議看起來不錯，但是很難實用。我們接下來要對這個簡單協議進行升級。
升級隨機性第一個升級是讓隱藏位元串變成一個「一致性均勻分佈」的隨機的隱藏位元串，是一個看起來相當隨機的位元串，而不是一個刻意擺放好的哈密爾頓子圖。完全隨機意味著位元串中的0的個數和1出現的概率大概接近。那麼接下來一個難題是如何讓隨機位元串中能出現一個隨機的哈密爾頓環路子圖矩陣。方法非常簡單粗暴：產生一個足夠長的隨機串，然後從頭掃描，直到找到一個隨機的哈密爾頓環路為止。可是……這個成功概率是不是非常非常小？我們下面給出一個概率沒那麼小的一種尋找方法。我們先把位元串按照5log(V)的長度進行切分，然後如果每一個分片中的所有位元全為1，那麼我們把這個片段被視為鄰接矩陣中的一個值為1的單元，否則視為一個值為0的單元。這樣每一個矩陣單元出現1的概率為1/(V^5)。我們取連續的V^6個片段，構成一個V^3 * V^3的大矩陣。如果大矩陣中包含一個V*V的哈密爾頓環路矩陣，並且其他單元（總共V^6 - V^2個） 都為0。那麼我們稱這個大矩陣為「有用」。根據概率計算，出現一個「有用」矩陣的概率為1/[V^(3/2)]。注：「有用」矩陣的概率計算過程請參考 Fact 4.10.8, 「Foundations of Cryptography, Vol I」by Oded Goldreich，P304。好了，我們需要升級下上一節的協議。因為現在「隱藏位元串」被拆分成了若干個大矩陣，這些大矩陣有些是「有用」的，有些是沒用的。接下來 Alice 要來構造證明了，她先戴上超級眼鏡，掃描雲朵中的 Hidden Bits，這要分兩種情況，Case 1：如果 Alice 遇到了一個沒用的大矩陣M，Alice 公開M的所有單元。Case 2：如果 Alice 遇到了一個「有用」的大矩陣M，這意味著 Alice 得到了一個隨機的 哈密爾頓環路C'，然後 Alice 參照上一節的步驟進行證明即可。那麼 Bob 怎麼驗證這個證明呢？我們還要分情況進行討論，Case 1：如果 Alice 公開了全部的M，那麼 Bob 就檢查這個M是否「無用」。如果M無用，就認為證明有效；否則拒絕。Case 2：如果 Alice 傳送的是形如（Perm()，X）這樣的證明，那麼 Bob 按照上一節的驗證方法進行驗證。對於這個協議，Bob 已經不再擔心第三方是否作弊，故意產生一個全零的位元串，但是 Alice 仍然擔心一旦第三方和 Bob 串謀，那麼知識就徹底洩露了。不僅如此，現在的協議還有個很強的限制，Alice 不能在看到隱藏位元之後再選擇需要證明的G，否則 Alice 就可以作弊。如果一個證明者選擇證明的「命題」與 CRS 無關，那麼這個證明者被稱為 Non-adaptive Adversary。
FLS 變換：從 Hidden Bits 到 NIZK接下來，我們再次升級協議，把「隱藏位元串」中的隱藏特性去除，變成「公共參考串」CRS。這裡我們要藉助一個密碼學工具 —— Trapdoor Permutation，陷門置換。所謂的陷門置換是指一個置換函式F(x)，x是一個集合S中的元素，然後函式F(x)把x對映到S中的另一個元素y。同時F(x)滿足單向性，即透過y很難反算出x；但是如果誰擁有陷門t，就能實現反向計算F^(-1)(t,y)=x。陷門置換還可以匹配一個 Hardcore Predicate，h(x)=0/1，它能根據S集合中的元素產生一個一致性分佈的0/1位元。介紹完畢，大家是不是有點暈，沒關係，暈一暈就習慣了。總之一句話，陷門置換可以對公共參考串和Hidden Bits 進行相互轉換。先假設有這樣的密碼學工具，然後我們升級協議。
我們把公共參考串看成是一個列表，y1, y2, y3, ..., yn，列表中的每一項都是集合 S中的元素。然後透過 Hardcore Predicate 產生 Hidden Bits 中的每一個位元位。但是請注意，這裡不能直接透過 h(y)=b來產生 Hidden Bits，因為這樣一來 Bob 就能自己算出所有的 Hidden Bits，這違反了上一節的協議。為了保證對 Bob 隱藏，我們需要用公共參考串的原象，也就是x1, x2, x3, ..., xn來產生 Hidden Bits，h(x)=b。Bob 雖然不能自己計算b1, b2, b3, ..., bn，但是一旦得到一個x，他就能檢驗F(x)?=y來判斷是否x是和公共參考串對應，同時再計算h(x)=b得到被揭示的 Hidden Bits，b。我們可以換一種不太準確，但是更直觀的方式來理解，Alice 相當於自己產生一對公私鑰。然後Alice 把公共參考串看成是一段「密文」，由於 Alice 有私鑰，於是可以對密文進行解密，得到明文，這些明文，對於 Bob 而言就相當於是 Hidden Bits。當 Alice 要「揭示」Hidden Bits 時，就出示相應的明文片段，並且帶上公鑰，那麼 Bob 就能透過公鑰再次「加密」明文，與公共參考串的密文進行比對，確保 Alice 沒有在揭示過程作弊。下面是升級後的協議：對於證明者 Alice：Alice 隨機選擇一個 Trapdoor Permutation，(F, h, t)根據公共參考串中的每一個 yi，利用陷門反向計算出xi = F^(-1)(t, yi)計算 Hidden Bits，bi=h(xi)根據上一節的協議產生證明。假設 Alice 要揭示的 Hidden bits 的位置集合為 r1,r2,...,rl，那麼 Alice 向 Bob 傳送對應位置的x，分別為 xr1, xr2, xr3, ... xrl，連同(F, h)，和證明一起併發給 Bob。對於驗證者 Bob：檢查(F, h)是否為一個合法的 Trapdoor Permutation。對L中的每一個元素 xr，計算出被揭示的 Hidden Bits bi=h(F(xr))，然後按照上一節的協議檢查證明。這個新協議的「完備性」，請大家自行檢查。對於「零知識」，我們需要構造一個「模擬器」Zlice2，它的超能力是修改公共參考串。模擬器直接呼叫上一節協議的模擬器 Zlice。得到一個三元組，(proof, {r}, {b})對於每一個公共參考串位置，如果它對應某一個r，模擬器從集合S中隨機選擇一個 xr，使得 h(xr)=br，這裡 br就是{b}中對應r；然後把 yr=F(xr) 作為假參考串的一部分。對於每一個公共參考串位置，如果與{r}無關，那麼模擬器隨機選一個y即可模擬器把所有的y拼在一起，得到一個假CRS。對於「可靠性」，事情變得不那麼簡單了。因為現在 Alice 有能力挑選(F,h,t)，Alice 可以挑選一個對自己有利，甚至作弊的(F, h, t)，使得她可以控制一次協議執行的 Hidden Bits{b}的結果。對於本節升級後的新協議而言，需要重複很多遍，以致於雖然 Alice 可以控制一次協議執行的 Hidden Bits，但是她對其它若干次協議執行的 Hidden Bits 無能為力。換句話說，Alice 無論如何挑選(F, h, t)都無法完全掌控多次的協議執行。這個升級變換理論上可以支援任意的 Hidden Bits 模型下的非互動式零知識證明，被稱為 FLS Protocol。FLS 變換有很多的好處：首先，這個隨機產生的 CRS 可以多次使用，實現所謂的「Multi-Theorem NIZK」；其次，可以實現「Adaptive Soundness」，即 Alice 可以先看到 CRS，然後再選擇要證明的內容。最後，這個協議還是「Adaptive Zero-Knowledge」，即 Bob 也可以先看到 CRS，然後再選擇要證明的內容給 Alice。注：Adaptive Adversary 是比較符合現實世界的安全情況，比如第二類CCA安全。因為 CRS 是公開的，攻擊者可以先分析 CRS，再決定如何發起攻擊。
尋找理想的 Trapdoor Permutation陷門置換 Trapdoor Permutation 最早出現在姚期智老師的論文「Theory and Application of Trapdoor Functions」[Yao82]中，是公鑰密碼學的重要基礎。在上一節給出的 FLS 變換中，需要一個理想化的 Trapdoor Permutation，所謂的理想化是指，每一個 n-bit 字串都能唯一變成另一個 n-bit 字串，並且不會出現「多對一」的對映關係。Alice 需要隨機抽樣一個 Index，發給 Bob，然後 Bob 要能檢查出這個 Index 所對應的F()是否是一個「完美」的置換。問題來了，怎麼 Bob 怎麼能在多項式時間內檢查出來呢？如果 Bob 不能檢查，那麼 Alice 就可以抽樣一個不完美的 Permutation（比如一個「多對一」的函式），從而可能作弊，破壞「Soundness」這個性質，Bellare 和 Yung 發表在 1996 年的論文最早注意到了這一點，但是並沒有完全解決這個問題[BY96]。如何找到一個橋樑，能夠將 Trapdoor Permutation 合適地抽象出來，同時能夠對接到密碼學工具的實現上，是一個及其有挑戰性的工作。隨後各路密碼學家（包括 Oded Goldreich） 在這方面研究了很長時間，發表了許許多多的論文 ，各種不同型別的 Trapdoor Permutation 被定義、被研究，但是仍然不能讓人滿意。直到最近（2018年）一個工作是 Ran Canetti 與 Amit Lichtenberg 提出了 Certifiable Injective Trapdoor Function 這樣一個新型別[RL18]，並證明了這種 Trapdoor Permutation 終於能滿足 FLS 變換要求。但這是不是故事的結束呢？理論密碼學家們估計不會停下探索的腳步。除了基於 Trapdoor Permutation 的 FLS 變換 ，還有各式各樣的解決方案來升級 Hidden Bits Model，比如採用 Invariant Signature[BG90]，或 Verifiable Random Generator [DN00] 來實現 Hidden Bits 的變換，或者弱可驗證隨機函式 [BGRV09]， 還有一種叫做 publicly-verifiable trapdoor predicates 的方案[CHK03]。三十年來，密碼學家們發明的 NIZK 方案有很多，但 Hidden Bits 方法是目前已知唯一的辦法，(1) 基於「一致性分佈」的共享 CRS，(2) 實現任意 NP 語言的 NIZK Proofs（Not Arguments!）。
NIZK Proofs 與 NIZK Arguments在本文中，我們構造的 NIZK 「證明」系統的可靠性屬於「Statistical Soundness」，而零知識則屬於「Computational Zero-Knowledge」。這意味著什麼呢？這意味著，不管證明者 Alice 的算力有多強大（甚至超多項式），Alice 仍然無法作弊。但是，如果驗證者 Bob 擁有超強的計算能力，那麼是存在這種可能性：Bob 從證明中抽取到有價值的「知識」。這又意味著什麼？這意味著，對於 NIZK Proofs 來說，它的長度肯定要比「知識」長，知識即NP問題中的witness。只要 Bob 算力夠強，他就可以把證明解密。對於「抽取器」而言，它也需要在沒有互動的情況下抽取witness。證明最短的 NIZK Proofs 當屬 Greg Gentry 等人採用「全同態加密」技術構造的 NIZK 方案了 [GGI+14]，證明長度只是稍稍大於 witness 的長度。那能不能構造證明尺寸小於 witness 的 NIZK 呢？答案是 YES！還有一類的 NIZK 系統被稱為 NIZK Arguments：它們的可靠性是「Computational Soundness」，零知識屬於「Perfect Zero-Knowledge」或者「Statistical Zero-Knowledge」。這說明，Alice 如果算力超強，那麼她是有作弊空間的，但是因為現實世界中，我們可以透過加大安全引數（Security Parameters）來極大地降低 Alice 作弊的可能性，但是能實現非常極致的零知識特性。由於弱化了可靠性，那麼我們就可以繼續壓縮證明的尺寸。注：在本系列中，我們並不刻意區分「證明」與「論證」這兩個詞。如果需要指明 Arguments 而非 Proofs，會專門強調。假如說我們要公開一個 NIZK 證明到 Github上，假如過了一百年以後，Github 網站還在，而未來計算機的計算能力已經有了質的飛躍，這時候，一個 NIZK Proof 可能會被算力攻破，洩露知識，而 NIZK Argument 則很大可能性上還保持安全性。現在流行的熱詞 —— zkSNARK 中的AR正是指代 Argument。NIZK Argument 可以實現O(1)常數級長度的證明，即與witness的長度無關。然而這需要隱藏更多的秘密到 CRS 中。
沒有秘密的世界1956 年，哥德爾在一封寄給馮諾依曼的信中提到了一個著名的問題，「P 是否等於 NP」。後來，這個問題被 Clay 研究所列為七個千禧年難題之一，懸賞百萬美金。零知識證明系統正是為了保護 witness 不洩露的前提下，實現 NP 問題的驗證。那如果一旦證明了「P == NP」，這會意味著什麼？這意味著 witness 不再有多大意義了，反正一個圖靈機也可以在多項式時間內找到 witness。零知識證明試圖保護的 witness 也變得徒勞無益。事實上，如果「P == NP」，現有的公鑰密碼學、對稱加密 AES 與 SM4、雜湊演算法所依賴的難解問題都可能坍塌，我們可能很難儲存秘密。不僅如此，“ 如果 P == NP，我們所處的世界將會變得非常不一樣。「Creative Leaps」將不再有價值，求解問題與驗證問題之間的鴻溝不復存在。每個能欣賞交響樂的人都會成為莫扎特，每個會推理的人都會變成高斯，每個能判斷投資好壞的人都會變成巴菲特。從達爾文進化論的觀點出發：如果這就是我們存在的宇宙，為什麼我們還沒有進化得可以充分利用這個好處？—— Scott Aaronson (2006)”對於數學也一樣，數學證明的驗證過程也是多項式複雜度的，如果「P == NP」，那麼也就存在著多項式時間尋找證明的演算法（如果證明存在）。這意味著哥德巴赫猜想、黎曼猜想將有可能得到證明，難怪 Lance Fortnow 在部落格[For04]裡這麼說：“
A person who proves P == NP would walk home from the Clay Institute not with one million-dollar check but with seven.
如果誰能證明 P = NP，那麼他不會只拿著一張百萬美元支票回家，而是七張。
—— Lance Fortnow (2004)”2002年的調查顯示，61% 的電腦科學家相信「P != NP」，而十年後，這個比例上升到了 83%[Wil12]。而我是被 Scott Aaronson 的如下論斷說服的：“
自指論證：如果 P = NP 是事實，那麼這個證明會比較容易被發現；但是如果 P != NP，那麼這個證明會比較難發現。所以相信 P != NP 看起來會讓數學現實更一致一些。
—— Scott Aaronson (2006)”儘管是如此不情願，如果我們真的生活在一個沒有秘密的世界，那會是什麼樣子？「環形監獄 Panopticon」是 18 世紀英國哲學家 Jeremy Bentham 提出的一個驚悚概念。囚徒們被中心全天候監控，沒有任何隱私可言，而且他們對自己是否處於被監控狀態也無從得知。這個無比悲觀的論調讓人渾身不適，但很多人認為，這可能是兩百多年前對未來網路數字時代的一則精準寓言。
從『Billy Budd』，卡夫卡的『The Trial』，到奧威爾的『1984』，到著名駭客 Kevin Mitnick 寫的超級大賣書『隱形的藝術』（教你如何在大資料時代保護自己的資訊），似乎，危機四伏，風險不斷累積，對末日世界的想象給了作家們很好的素材 ……偶爾無意中看到了一本有趣的漫畫『The Private Eye』，它描述了一個劫後餘生的後現代場景：在未來，我們的所有資訊資料都存放在雲上，然後突然有一天，這個資料雲「爆炸」了，不知道是什麼原因（可能是誰不小心開啟了潘多拉的魔盒，找到了 P == NP 的構造性證明），反正所有的資訊，包括每個人最陰暗的過去，都不再成為秘密；所有的數字化的資產都被抹掉，所有的線上知識庫永久丟失；每個人的言行、賬單、郵件、聊天訊息、銀行卡密碼、中學考卷、GPS位置資訊，寫了一半的日記、刪除的照片、上網記錄，這些資訊都將暴露給同事、鄰居、 朋友、親人、甚至任何一個好奇的人。
每個人都無地自容，惶惶不可終日，然後逐漸地，大家都選擇隱藏自己，人們出門都要戴上面具，以小心翼翼地保護自己的身份，甚至一個人可以選擇使用多個身份，國家法律規定任何偷窺行為都將被嚴懲，獲取資訊成為了一種至少無上的權力，照相機需要被嚴格管控，網際網路不再存在，人們通訊又回到了電話亭時代 ……這會是人類的終極命運麼？
未完待續本文開頭提到了「隱藏隨機性」並不是必要的，我們來回想下 Hidden Bits 模型。這些 Hidden Bits 並沒有對 Prover 隱藏，而是敞開了讓 Prover 知道，但是由於 Hidden Bits 是「一致性隨機分佈」的字串， 所以即使讓 Prover 知道了，他仍然逃不過隨機挑戰的火力。然而在流行的 zkSNARK 方案中，並沒有採用「一致性隨機分佈」的 CRS，而是一組結構化的隨機數。不管怎樣，用 CRS 來構建「信任根基」的秘密，就是藏在其中的「秘密」。這符合直覺，保守「秘密」也是一種信任。因為 Alice 不知道 CRS 中隱藏的秘密後門，所以無法作弊。同樣，Bob 不知道 CRS 中的秘密，也就沒辦法獲得「知識」。同樣，人與人之間的協作既要建立在公開透明的基礎上，也要保守秘密。
All human beings have three lives: public, private, and secret.
每個人都有三種生活，公開的，私人的，以及秘密的。
——Gabriel García Márqueel
致謝：感謝陳宇，丁晟超，張宇鵬，胡紅鋼，劉蔚然，何德彪等老師的專業建議和指正，感謝安比實驗室小夥伴（p0n1, even, valuka, Vawheter, yghu, mr）的修改建議。本文內容不代表他們觀點。
最後附上漫畫書的連結：http://panelsyndicate.com/comics/tpeye作者甚至把創作過程的郵件和草圖都放了出來，大家可以體驗一下窺視製作過程的快感。
參考文獻
[Aar06] Aaronson, Scott.Reasons to believe, 2006.https://www.scottaaronson.com/blog/?p=122
[BFM88] Blum, Manuel, Paul Feldman, and Silvio Micali. "Non-interactive zero-knowledge and its applications." STOC'88. 1988.
[BG90] Bellare, Mihir, and Shafi Goldwasser. "New paradigms for digital signatures and message authentication based on non-interactive zero knowledge proofs."Conference on the Theory and Application of Cryptology. Springer, New York, NY, 1989.
[BGN05] Boneh, Dan, Eu-Jin Goh, and Kobbi Nissim. "Evaluating 2-DNF formulas on ciphertexts."Theory of Cryptography Conference. Springer, Berlin, Heidelberg, 2005.
[BGRV09] Brakerski, Zvika, Shafi Goldwasser, Guy N. Rothblum, and Vinod Vaikuntanathan. "Weak verifiable random functions." InTheory of Cryptography Conference, pp. 558-576. Springer, Berlin, Heidelberg, 2009.
[BY96] Bellare, Mihir, and Moti Yung. "Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation."Journal of Cryptology9.3 (1996): 149-166.
[CHK03] Canetti, Ran, Shai Halevi, and Jonathan Katz. "A forward-secure public-key encryption scheme."International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2003.
[CHMMVW19] Chiesa, Alessandro, et al.Marlin: Preprocessing zksnarks with universal and updatable srs. Cryptology ePrint Archive, Report 2019/1047, 2019,https://eprint.iacr.org/2019/1047, 2019.
[DN00] Dwork, Cynthia, and Moni Naor. "Zaps and their applications."Proceedings 41st Annual Symposium on Foundations of Computer Science. IEEE, 2000.
[FLS90] Feige, Uriel, Dror Lapidot, and Adi Shamir. "Multiple non-interactive zero knowledge proofs based on a single random string."Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science. IEEE, 1990.
[For04] Fortnow, Lance. "What if P = NP?". 2004.https://blog.computationalcomplexity.org/2004/05/what-if-p-np.html
[For09] Fortnow, Lance. "The status of the P versus NP problem."Communications of the ACM52.9 (2009): 78-86.
[Groth20a] Groth, Jens. "Short non-interactive zero-knowledge proofs."International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2010.
[Groth20b] Groth, Jens. "Short pairing-based non-interactive zero-knowledge arguments."International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2010.
[GOS06] Groth, Jens, Rafail Ostrovsky, and Amit Sahai. "Perfect non-interactive zero knowledge for NP."Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2006.
[GWC19] Gabizon, Ariel, Zachary J. Williamson, and Oana Ciobotaru.PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. Cryptology ePrint Archive, Report 2019/953, 2019.
[KP98] Kilian, Joe, and Erez Petrank. "An efficient noninteractive zero-knowledge proof system for NP with general assumptions."Journal of Cryptology11.1 (1998): 1-27.
[MBK+19] Maller, Mary, et al. "Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings."IACR Cryptology ePrint Archive2019 (2019): 99.
[RL18] Ran Canetti and Amit Lichtenberg. "Certifying trapdoor permutations, revisited."Theory of Cryptography Conference. Springer, Cham, 2018.
[Wil12]Gasarch, William I. "Guest Column: The Third P=? NP Poll."ACM SIGACT News50.1 (2019): 38-59.
[Yao82] Yao, Andrew C. "Theory and application of trapdoor functions."23rd Annual Symposium on Foundations of Computer Science (sfcs 1982). IEEE, 1982.
