本文作者：郭宇
Once exposed, a secret loses all its power.? 一旦泄露，秘密就失去了全部威力? ― Ann Aguirre
這已經(jīng)是本系列的第五篇文章了，這一篇繼續(xù)深入非交互式零知識(shí)證明。 本文約 12,000 字。
提綱
CRS 的前世今生
哈密爾頓環(huán)路問(wèn)題
云中的秘密：Hidden Bits
升級(jí)隨機(jī)性
FLS變換：從 Hidden Bits 到 NIZK
尋找理想的 Trapdoor Permutation
NIZK Proof vs. NIZK Argument
沒(méi)有秘密的世界
追到這里的讀者想必已對(duì)零知識(shí)證明有了一個(gè)大概的認(rèn)識(shí)。你是否想過(guò)這個(gè)問(wèn)題：零知識(shí)證明為何可行？這里請(qǐng)大家思考一下（比如系列一 中的地圖三染色問(wèn)題的流程） …… （此處停留三分鐘）下面兩個(gè)要素 似乎 必不可少：
「交互」：驗(yàn)證者通過(guò)多次反復(fù)挑戰(zhàn)，把證明者作弊概率降低到一個(gè)極小的值
「隱藏隨機(jī)性」：驗(yàn)證者產(chǎn)生讓證明者無(wú)法預(yù)測(cè)的隨機(jī)數(shù)進(jìn)行挑戰(zhàn)
然而對(duì)于非交互式零知識(shí)證明—— NIZK 來(lái)說(shuō)，如何實(shí)現(xiàn)上面兩點(diǎn)？在 系列四 我們介紹了如何采用「隨機(jī)預(yù)言機(jī)」來(lái)扮演一個(gè)虛擬的「第三方」角色，實(shí)現(xiàn)虛擬的「交互」與「隨機(jī)挑戰(zhàn)」。本文將深入講述另一種方法，如何通過(guò)一段共享的字符串去除「交互」與「隱藏隨機(jī)性」。這個(gè)字符串必須事先由「第三方」來(lái)隨機(jī)產(chǎn)生，這就是傳說(shuō)中的「公共參考串」（Common Reference String，簡(jiǎn)稱 CRS）。
CRS 的前世今生
假如我們不借助任何其它手段，限定證明者 Prover 和驗(yàn)證者 Verifier 只能進(jìn)行「一次交互」來(lái)實(shí)現(xiàn)「零知識(shí)證明」，那么他們只能證明「平凡」問(wèn)題，也就是計(jì)算復(fù)雜類 BPP（Bounded-error Probabilistic Polynomial time），而這個(gè)復(fù)雜度類大家一般猜想可能等價(jià)于 P（但還懸而未決，沒(méi)有被證明！BPP 可以理解為 P + Randomness）。
注：如果 Prover 與 Verifier 只做一次交互，在這樣的 NIZK 系統(tǒng)中，我們很容易能構(gòu)造一個(gè) Decision Procedure —— Verify(x, Sim(x))，來(lái)證明和證偽定理，因此只能證明平凡問(wèn)題 BPP。
平凡問(wèn)題雖然也可以零知識(shí)證明，但沒(méi)有意義！怎么理解呢？因?yàn)轵?yàn)證者直接可以在多項(xiàng)式時(shí)間內(nèi)根據(jù)「輸出」求解出「秘密輸入」，雖然驗(yàn)證者能夠求解，但是「證明」本身并沒(méi)有額外為驗(yàn)證者提供更多的「知識(shí)」。換句話說(shuō)，不需要證明者出示證明，驗(yàn)證者就知道命題為真，于是證明過(guò)程也是零知識(shí)的。
因此，當(dāng)我們討論「零知識(shí)證明」時(shí)，要考慮帶「知識(shí)」的 NP 類問(wèn)題。大家都知道，P 問(wèn)題是「確定性圖靈機(jī)」多項(xiàng)式時(shí)間內(nèi)可以求解的復(fù)雜類，它的執(zhí)行路徑對(duì)于輸入 x是一個(gè)線性的狀態(tài)轉(zhuǎn)移。而 NP 問(wèn)題是「不確定性圖靈機(jī)」多項(xiàng)式時(shí)間可以求解的問(wèn)題類。所謂的不確定性圖靈機(jī)，就是它每次往前走一步是不確定的，有很多個(gè)選擇，只要任何一個(gè)執(zhí)行路徑能到達(dá)終止?fàn)顟B(tài)，就表示它解決了該問(wèn)題 x。換句話說(shuō)，它的執(zhí)行軌跡是一棵樹。那么如果我們把不確定性圖靈機(jī)每一步的路徑選擇記錄下來(lái)（這個(gè)執(zhí)行路徑的記錄叫做 witness，也就是我們反復(fù)提到的「知識(shí)」），那么把(x, witness)交給一個(gè)確定性圖靈機(jī)，那么它也能在多項(xiàng)式時(shí)間內(nèi)解決掉 x 問(wèn)題。
再?gòu)?qiáng)調(diào)一下，「知識(shí)」能提高圖靈機(jī)的解決問(wèn)題的能力。
NP 問(wèn)題中存在著不想「泄露」給驗(yàn)證者的知識(shí) witness，這時(shí)，在一個(gè)交互式證明系統(tǒng)中，證明者和驗(yàn)證者在「知識(shí)」的掌握程度上是不對(duì)等的。
為了保證證明過(guò)程的「零知識(shí)」，我們需要保證：模擬器與驗(yàn)證者的不對(duì)等?？墒?，模擬器沒(méi)有 witness啊，怎么能讓他們不對(duì)等呢？上一篇我們介紹了「隨機(jī)預(yù)言機(jī)」，我們通過(guò)允許讓模擬器可以綁架「隨機(jī)預(yù)言精靈」的方式制造不平等。本篇將講述如何利用 CRS 來(lái)制造不平等。
CRS 是一個(gè)在證明之前就已經(jīng)公開的，并且在證明者與驗(yàn)證者之間共享的，隨機(jī)字符串。我們?cè)趺磥?lái)使用 CRS 呢？直覺(jué)上，一串雙方都「知道」的信息，并不會(huì)增加「知識(shí)」不對(duì)等的情況。
首先大家會(huì)想，能不能直接用 CRS 作為隨機(jī)挑戰(zhàn)數(shù)呢？可不可以讓 CRS 來(lái)代替「隨機(jī)預(yù)言精靈」的角色？答案是不行！
為什么？這是因?yàn)?CRS 是在證明之前就已經(jīng)產(chǎn)生了，如果證明者 Prover 提前知道了所有的隨機(jī)挑戰(zhàn)數(shù)，那么很顯然這個(gè)隨機(jī)挑戰(zhàn)也就失去了意義。
注：請(qǐng)大家回想下「隨機(jī)預(yù)言機(jī)」是如何保證證明者無(wú)法提前預(yù)測(cè)「隨機(jī)挑戰(zhàn)數(shù)」的？沒(méi)想明白的你，請(qǐng)重讀系列（四）。
CRS 的使命就是讓「模擬器」與「驗(yàn)證者」不平等。怎么做呢？隱藏一些「秘密」進(jìn)去。
如果進(jìn)一步追問(wèn)，隱藏了「秘密」有什么用呢？當(dāng)然有用啦，在「理想世界」中，模擬器與抽取器才能很開心地玩耍起來(lái)（獲取某些超能力） ……
1988年，Manuel Blum，Paul Feldman 和 Silvio Micali 三位先驅(qū)發(fā)表的論文 「Non-Interactive Zero-Knowledge and Its Applications」（『非交互式零知識(shí)證明及其應(yīng)用』[BFM88]）展示了「交互」與「隱藏隨機(jī)性」的不必要性。他們給出了一個(gè)地圖三染色問(wèn)題的 NIZK 證明系統(tǒng)，在一段共享的隨機(jī)產(chǎn)生的字符串（即CRS）的幫助下。
不過(guò)，……，我不會(huì)告訴你這個(gè)方案需要共享大概 n^4 超長(zhǎng)的 CRS，其中 n是要證明的「命題」的長(zhǎng)度。
1990 年，Uriel Feige，Dror Lapidot 與 Adi Shamir 三人提出了另一種構(gòu)造 NP 語(yǔ)言的 NIZK 方案 [FLS90]。與 [BFM88] 不一樣的是，這個(gè) NIZK 方案不再基于特定的數(shù)論假設(shè)，而是基于一個(gè)密碼學(xué)工具 Trapdoor Permutation。在這個(gè)方案中，F(xiàn)LS 提出了「隱藏比特」（Hidden Bits）的概念，然后把 Hidden Bits 藏入了 CRS。對(duì)于模擬器而言，就可以通過(guò)修改 CRS 中的 Hidden Bits 來(lái)達(dá)到模擬的效果，從而體現(xiàn)出對(duì)驗(yàn)證者 Verifier 的優(yōu)越性。不過(guò)，這個(gè)方案需要共享更長(zhǎng)的 CRS，超過(guò) k * n^5，這里 k 是安全參數(shù)。
此后，Hidden Bits 的思路被很多人采用，值得一提的是，Kilian 與 Petrank 采用了一種更巧妙的方法來(lái)使用 Hidden Bits [KP98]（這里空間太小，寫不下:），成功地把 CRS 的長(zhǎng)度縮減到了 k * n^2。后來(lái) J. Groth 繼續(xù)優(yōu)化 ，把 CRS 的長(zhǎng)度縮小到了大約 k*n[Groth10a]。
除了 Hidden Bits，J. Groth，R. Ostrovsky 與 A. Sahai? [GOS06] 使用了同態(tài)加密方案 Boneh-Goh-Nissim [BGN05] 或 Boneh-Boyen-Shacham 來(lái)實(shí)現(xiàn) NIZK，他們把加密方案的「公鑰」當(dāng)做是 CRS，同時(shí) Prover 加密作為證明，然后利用同態(tài)性質(zhì)來(lái)證明另一個(gè) NP-Complete 問(wèn)題——布爾電路的可滿足性問(wèn)題。這個(gè)方案的最大優(yōu)點(diǎn)，就是 CRS 長(zhǎng)度是固定的，因?yàn)橹皇且粋€(gè)密鑰而已，長(zhǎng)度只有 k。對(duì)于模擬器而言，它可以通過(guò)超能力，拿到這個(gè)公鑰所對(duì)應(yīng)的陷門，從而能夠?qū)崿F(xiàn)密封任何信息，但得到相同的密文；對(duì)于抽取器而言，它可以用超能力拿到公鑰對(duì)應(yīng)的私鑰，從而能夠解密證明得到「知識(shí)」。
Jens Groth 在 2010 年基于 KEA（Knowledge of Exponent Assumption） 假設(shè)與 Pairing 提出了一種新的 NIZK Arguments 方案[Gorth10b]，這也是后續(xù)許許多多 zkSNARKs 方案的起點(diǎn)。這里的 CRS 由一對(duì)對(duì)的 （g^x^n, g^?x^n） 構(gòu)成，被用來(lái)實(shí)現(xiàn)「知識(shí)承諾」。其中 x 與 ? 是兩個(gè)隨機(jī)數(shù)，在產(chǎn)生完 CRS 之后，必須被「遺忘」。有些人把這部分需要遺忘的隨機(jī)數(shù)叫做「Toxic Wastes」，這容易誤導(dǎo)讀者。他們不僅無(wú)毒無(wú)害，而且非常有用。他們是被藏入 CRS 的「秘密」，是模擬器的武器。如果模擬器得到了 x 與 ?，就能偽造證明，從而保證證明的零知識(shí)。而對(duì)于抽取器，他能直接通過(guò) KEA 假設(shè)內(nèi)建的抽取函數(shù)來(lái)抽取知識(shí)。
最新的 Sonic 方案[MBK+19]又在 [Groth10b] 的基礎(chǔ)上實(shí)現(xiàn)了 Updateable CRS。如果任何人擔(dān)心 CRS 中的秘密已經(jīng)被泄露了，他就可以在原有 CRS 基礎(chǔ)上打一個(gè)補(bǔ)丁，繼續(xù)往里藏一個(gè)秘密，這樣就能保證 CRS 的安全性。這里的 CRS 還是「Universal 全局」 的，即 CRS 只需要生成一次，就可以應(yīng)付所有的命題證明。 這個(gè)方案后續(xù)被最新的 Plonk[GWC19]，Marlin[CHMMVW19] 等方案采用。
接下來(lái)，我們就從一個(gè)簡(jiǎn)單的例子開始，理解如何基于 CRS 來(lái)構(gòu)造 NIZK。在這之前，我們需要介紹一個(gè) NP-Complete 問(wèn)題——哈密爾頓環(huán)路問(wèn)題。
哈密爾頓環(huán)路問(wèn)題
想象出一個(gè)地圖中有若干個(gè)城市，城市與城市間可以有公路。
假如給你一副地圖，讓你找出一條路徑，不重復(fù)地走遍所有的公路（假設(shè)每條公路都是風(fēng)景美如明信片的 Parkway，或許你想不重復(fù)地吃遍每條公路邊上的麥當(dāng)勞，出于某種情懷）。相信你會(huì)馬上興奮起來(lái)，這不就是小時(shí)候?qū)W過(guò)的「一筆畫」么？判斷一個(gè)地圖能否一筆畫，這是小學(xué)生做的數(shù)學(xué)題，我們可以計(jì)算每個(gè)城市連接的公路個(gè)數(shù)，根據(jù)奇偶性分成「奇點(diǎn)」與「偶點(diǎn)」。如果一個(gè)地圖中存在兩個(gè)奇點(diǎn)城市，那么你只能從一個(gè)奇點(diǎn)城市出發(fā)，遍歷所有的公路，并且最終到達(dá)另一個(gè)奇點(diǎn)城市。這條路徑就被稱為「歐拉路徑」（Euler's Path）。
如果一個(gè)地圖中所有的城市都是偶點(diǎn)，那么你可以從任意一個(gè)城市出發(fā)，輕松地找出一條路徑，不重復(fù)地遍歷所有的公路，并且回到起點(diǎn)。這個(gè)環(huán)路被稱為「歐拉環(huán)路」（Euler's Circuit）。
而如果地圖存在超過(guò)2個(gè)以上的奇點(diǎn)，那么就不存在歐拉回路，比如著名的哥德斯堡七橋問(wèn)題。
著名的哥德斯堡七橋問(wèn)題就是這么描述，如果不重復(fù)地穿過(guò)下面七座橋。
哥德斯堡七橋地圖顯然存在多個(gè)奇點(diǎn)，不存在歐拉路徑。如果給定任何一個(gè)地圖，是否存在一個(gè)歐拉環(huán)路，這是一個(gè) P 問(wèn)題，也就是一個(gè)計(jì)算機(jī)可以在 poly(n) 多項(xiàng)式時(shí)間內(nèi)尋找。
注：歐拉環(huán)路的尋找算法被稱為 Fleury算法。
對(duì)于這樣一個(gè) P 問(wèn)題， 如果一個(gè)證明者 Prover 證明他知道一個(gè)歐拉回路，那么他可以直接發(fā)送回路的明文，然后驗(yàn)證者 Verifier 驗(yàn)證回路正確與否。請(qǐng)注意，這個(gè)過(guò)程仍然是零知識(shí)的。因?yàn)?，Verifier 并沒(méi)有通過(guò) Prover 發(fā)送的信息獲得任何 額外的知識(shí)。換句話說(shuō)，Verifier 并沒(méi)有因?yàn)榭吹交芈?，而增?qiáng)了自身計(jì)算能力，因?yàn)?Verifier 本來(lái)就可以自行計(jì)算歐拉回路。
而我們要講的是「哈密爾頓環(huán)路問(wèn)題」則是一個(gè) NP 問(wèn)題，描述如下：
是否一個(gè)地圖存在一個(gè)環(huán)路，能不重復(fù)地穿過(guò)每一個(gè)城市。
比如下面這張地圖：
我們用一個(gè)矩陣 V * V 的矩陣來(lái)表示這個(gè)地圖，凡是兩個(gè)城市（A, B）有公路相連接，那么就在(A, B) 和 (B, A)里面填上 1，否則填 0。這個(gè)矩陣被稱為「鄰接矩陣」，我們可以把這個(gè)鄰接矩陣拍扁，就變成了一個(gè) 0/1 比特串。
尋找「哈密爾頓環(huán)路」是一個(gè) NP-Complete 問(wèn)題，換句話說(shuō)，不存在一個(gè)算法使得計(jì)算機(jī)在 poly(n) 多項(xiàng)式時(shí)間內(nèi)找到環(huán)路。但是，計(jì)算機(jī)可以在多項(xiàng)式時(shí)間內(nèi)檢驗(yàn)一個(gè)路徑是否是「哈密爾頓環(huán)路」。比如這個(gè)地圖中就有一個(gè)帶方向的哈密爾頓環(huán)路，我們一眼就能驗(yàn)證這個(gè)環(huán)路確實(shí)穿過(guò)了每一個(gè)城市。如果一個(gè)地圖有哈密爾頓環(huán)路，那么它的矩陣一定是滿足下面的特征：每一行一定有一個(gè)1，每一列一定也有一個(gè)1。
ZK-HAM 協(xié)議
我們下面給出一個(gè)三步交互的 Sigma 協(xié)議，Alice 向 Bob 證明她「知道」上面這個(gè)地圖 G 的哈密爾頓環(huán)路。
公共輸入：G 為一個(gè)有 6 個(gè)頂點(diǎn)的地圖，表示為一個(gè) 6*6 的鄰接矩陣
秘密輸入：G的哈密爾頓環(huán)路 C（圖中橙色的公路）
第一步：Alice 隨機(jī)選擇一個(gè)「置換」，Perm(.)，然后通過(guò)這個(gè)置換，產(chǎn)生一個(gè)新的圖 G'；然后 Alice 把G' 矩陣的每一個(gè)單元加密，產(chǎn)生一個(gè)新的矩陣發(fā)送給 Bob。
【名詞解釋】：所謂置換，大家可以想象成用 鼠標(biāo) 隨意拖動(dòng)圖中的點(diǎn)，但是點(diǎn)和點(diǎn)之間的連線會(huì)跟著點(diǎn)一起被拖動(dòng)，拖動(dòng)結(jié)束之后形成的圖，進(jìn)行重新編號(hào)就得到 G'，比如上圖左側(cè)的兩個(gè)圖。經(jīng)過(guò)置換變換的圖前后是 同構(gòu) 的。其中下圖中，每一個(gè)頂點(diǎn)上角括號(hào)中的標(biāo)號(hào)為拖動(dòng)之前該頂點(diǎn)在上圖中的編號(hào)。形式化一點(diǎn)可以這么定義：Perm()是一個(gè) {1, V} 到 {1, V}的雙射函數(shù)新圖 G'的鄰接矩陣，[perm(i), perm(i+1) ]=1 當(dāng)且僅當(dāng)[i, i+1]=1，其中 i 是頂點(diǎn)編號(hào)，V 是頂點(diǎn)個(gè)數(shù) 。
第二步：Bob 隨機(jī)選擇 b in {0, 1}} 進(jìn)行挑戰(zhàn)。
第三步情況（1）：Alice 根據(jù) Bob 第二步發(fā)送的值：如果 b=0，那么 Alice 發(fā)送置換函數(shù) Perm()，并且揭示完整的圖 G'。而 Bob 則確認(rèn) G'是否是原圖 G 經(jīng)過(guò)置換無(wú)誤。
第三步情況（2）：如果 Bob 第二步發(fā)送的b=1，那么 Alice 只揭示 G'中的哈密爾頓環(huán)路 C'即可。而 Bob 需要驗(yàn)證 C'是否是一個(gè)哈密爾頓環(huán)路
回憶一下三步 Sigma 協(xié)議，我們?cè)倮斫庀律厦婵此茝?fù)雜的動(dòng)作：
第一步：被稱為 Commit，證明者 Alice 需要把手里的答案進(jìn)行同態(tài)變換，產(chǎn)生一個(gè)新答案，然后把每一條邊都鎖起來(lái)，交給 Bob；
第二步：Bob 進(jìn)行隨機(jī)挑戰(zhàn)；
第三步：Alice 根據(jù) Bob 的隨機(jī)挑戰(zhàn)，做出兩種不同的回應(yīng)。如果 Bob 挑戰(zhàn) 0，那么Alice 打開第一步的承諾，表示自己在第一步?jīng)]有作弊；如果 Bob 挑戰(zhàn) 1，那么 Alice 只解密暴露出哈密爾頓環(huán)路的邊（公路），其它邊則不需解密。Bob 可以輕易地檢查地圖上露出來(lái)的那些邊是否構(gòu)成了一個(gè)不重復(fù)地經(jīng)過(guò)所有城市的環(huán)路。
如果這個(gè) Sigma 協(xié)議只走一遍的話， Alice 作弊的概率是 50%，如果重復(fù) n 遍，Alice 作弊概率會(huì)指數(shù)級(jí)減小。大家可以試著用「模擬器」和「抽取器」的方法來(lái)證明這個(gè)協(xié)議的「零知識(shí)」與「可靠性」。
ZK-HAM 的變形：ZK-HAM-2
接下來(lái)把上面的這個(gè)三步協(xié)議改動(dòng)一下。大家先考慮下這樣一個(gè)簡(jiǎn)單事實(shí)：如果一個(gè)僅包含環(huán)路的子圖 C 是 圖 G的子圖，C <= G那么說(shuō)明 G 包含哈密爾頓環(huán)路。
這個(gè)事實(shí)等價(jià)于另一個(gè)事實(shí)：一個(gè)哈密爾頓圖 G 的補(bǔ)集 !G 是環(huán)路子圖 C 的補(bǔ)集 !C 的子圖。
【名詞解釋】圖的補(bǔ)集：所謂補(bǔ)集就是這樣一個(gè)新地圖，頂點(diǎn)保持不變，舊地圖上的邊在新地圖中不存在，而新地圖中的公路在舊地圖中不存在，但是兩個(gè)圖重合在一起，就變成了一個(gè)完全圖（完全圖是指任意兩個(gè)頂點(diǎn)之間都存在一條邊）。
用鄰接矩陣來(lái)理解，就是如果一個(gè)圖G包含一個(gè)環(huán)路子圖C，那么G矩陣中所有值為 0 的單元集合 必然被 C矩陣中所有值為0的單元集合包含?？梢员硎緸?!G <= !C。
根據(jù)第二個(gè)事實(shí)，我們可以定義如下的 Sigma 協(xié)議：
公共輸入：圖G ，表示為 6*6 的鄰接矩陣
秘密輸入：G的哈密爾頓環(huán)路 C（圖中橙色的公路）
第一步：
Alice 隨機(jī)選擇一個(gè)「置換」，Perm(.)，并且通過(guò)C構(gòu)造一個(gè)哈密爾頓環(huán)路子圖 C'=Perm(C)；
然后 Alice 加密 C'的每一個(gè)單元，把解密后的結(jié)果發(fā)送給 Bob。
第二步：Bob 隨機(jī)選擇 b in {0, 1}進(jìn)行挑戰(zhàn)
第三步情況（1）：如果 b=0，Alice 揭示完整的 C'，而 Bob 驗(yàn)證這個(gè) C' 是否確實(shí)是一個(gè)哈密爾頓環(huán)路子圖。
第三步情況（2）：如果 b=1，Alice 發(fā)送 Perm()，同時(shí)按照 G'=Perm(G)中的所有含 0 單元所在的位置，揭示 C'中所對(duì)應(yīng)的單元；Bob 驗(yàn)證 C'所有被揭示單元是否全部為 0。
再理解下這三步 Sigma 協(xié)議：
第一步：證明者 Alice 需要把哈密爾頓子圖 C 進(jìn)行置換變換，產(chǎn)生一個(gè)新的哈密爾頓子圖 C'，加密后交給 Bob；
第二步：Bob 進(jìn)行隨機(jī)挑戰(zhàn)，0 或者 1；
第三步：如果 Bob 挑戰(zhàn) 0，那么 Alice 打開第一步的承諾，展示一個(gè)帶有唯一環(huán)路的圖；如果 Bob 挑戰(zhàn) 1，Alice 則按照 G'中的 0單元的位置打開承諾，展示承諾中被打開的位置全部為 0。
重點(diǎn)來(lái)了，大家仔細(xì)看看這個(gè)新版的 Sigma 協(xié)議的第一步。有沒(méi)有發(fā)現(xiàn)什么情況？
第一步 Alice 發(fā)送的內(nèi)容是與地圖G無(wú)關(guān)的！
同樣，第二步 Bob 發(fā)送的挑戰(zhàn)也是與地圖無(wú)關(guān)的。這樣我們可以把第一步發(fā)的承諾改成事先準(zhǔn)備好的比特串，而且我們假設(shè)這個(gè)比特串由一個(gè)可信第三方來(lái)產(chǎn)生，這樣一來(lái) Bob 就沒(méi)有必要發(fā)送 b=0 這個(gè)分支，因?yàn)榭尚诺牡谌绞钦\(chéng)實(shí)的，他一定是事先準(zhǔn)備好一個(gè)正確的環(huán)路子圖。這樣，由于 Bob 只需要發(fā)送 1挑戰(zhàn)分支，那么這一步也可以去除。
于是，三步協(xié)議變成了一步，我們成功去除了交互，有望實(shí)現(xiàn) NIZK 。
我們接下來(lái)把 ZK-HAM-2 協(xié)議的第一步和第二步推到一個(gè)事先準(zhǔn)備的字符串中，然后只讓 Alice 發(fā)送第三步的內(nèi)容給 Bob。如下圖所示：
請(qǐng)注意，這里還不算是一個(gè) NIZK 系統(tǒng)，因?yàn)檫@個(gè)共享字符串并不能對(duì) Bob 公開，否則 Bob 就能算出環(huán)路 C。接下來(lái)，我們要解釋一個(gè)新概念：「隱藏比特」（Hidden Bits）[FLS90]。Hidden Bits 是這樣一串隨機(jī)比特，它們對(duì)于驗(yàn)證者 Bob 隱藏，但是對(duì)于證明者 Alice 公開。然后在證明過(guò)程中，Alice 可以選擇性地揭示一部分比特展示給 Bob 看。這是構(gòu)造 NIZK 證明系統(tǒng)的一個(gè)利器，下面我們需要再繼續(xù)深入 ……
云中的秘密：Hidden Bits
讓我們?cè)俅伍_下腦洞，想象天上有朵云，云后面藏著一串隨機(jī)產(chǎn)生的比特值，不是 0 就是 1，然后 Alice （證明者）帶著一個(gè)「超級(jí)眼鏡」，于是能夠看到云后面所有的隨機(jī)比特串，但是 Bob （驗(yàn)證者）卻看不到。同時(shí) Alice 手里還有一個(gè)「超級(jí)手電筒」，她可以打開手電筒用激光穿透云層，讓 Bob 也能看見其中某個(gè)或某些比特。當(dāng)然，Bob 能看到的比特的選擇權(quán)完全在 Alice 手中。
云朵中隱藏的比特串就是所謂的 Hidden Bits。
接下來(lái)我們要通過(guò) Hidden Bits 來(lái)完成一個(gè)單步交互，完成 ZK-HAM-2 協(xié)議的功能。在 ZK-HAM-2 中的第一步，Alice 產(chǎn)生一個(gè)隨機(jī)的置換 Perm()，然后通過(guò) G 中的哈密爾頓環(huán)路子圖 C 產(chǎn)生一個(gè)變換后的環(huán)路子圖 C'=Perm(C)。這等價(jià)于，事先由任何人產(chǎn)生一個(gè)隨機(jī)的哈密爾頓環(huán)路子圖 C'，然后 Alice 根據(jù) C 和 C' 計(jì)算得出一個(gè)相應(yīng)的 Perm()。
假設(shè)由某個(gè)「第三方」產(chǎn)生了一個(gè)隨機(jī)的環(huán)路子圖 C'，編碼成「鄰接矩陣」比特串，放到云朵后面。假設(shè) V 為頂點(diǎn)（城市）的個(gè)數(shù)，E 為邊（公路）的條數(shù)。這個(gè)鄰接矩陣的編碼需要一個(gè) V*V 長(zhǎng)度的比特串，可以解釋成一個(gè) V*V 的矩陣，其中每一行只包含一個(gè) 1，每一列也只包含一個(gè) 1，矩陣的其它單元都為 0。
接下來(lái) Alice 如何構(gòu)造證明呢？這其實(shí)很簡(jiǎn)單：
Alice 通過(guò)「超級(jí)眼鏡」得到了一個(gè)隨機(jī)的哈密爾頓環(huán)路子圖 C'，然后計(jì)算得到一個(gè)置換 Perm()，使得 Perm(C)=C'。
Alice 根據(jù) Perm() 來(lái)計(jì)算出一個(gè)換后的圖 G'=Perm(G)
Alice 產(chǎn)生證明，由兩部分組成：（1）置換Perm() （2）G'的鄰接矩陣中所有值為 0 的單元坐標(biāo)所對(duì)應(yīng)的 C'矩陣的值，相當(dāng)于 Alice 需要用「超級(jí)手電筒」給 Bob 揭示的隱藏比特。
那么 Bob 怎么驗(yàn)證這個(gè)證明呢？Bob 拿到證明之后，只需要檢驗(yàn)兩個(gè)東西：
Perm() 是否是一個(gè)合法的置換 V -> V，比如不能出現(xiàn)兩個(gè)頂點(diǎn)映射到同一個(gè)頂點(diǎn)的情況。
對(duì)于 G 中的每一條「非邊」，經(jīng)過(guò)置換之后，Bob 抬頭看天上對(duì)應(yīng)的「隱藏比特」，比特值必須為 0
我們?cè)僮屑?xì)地深入理解下這個(gè)非交互協(xié)議。先從「完備性」入手：如果 Alice 沒(méi)有作弊，那么很顯然能夠通過(guò) Bob 的驗(yàn)證，這里請(qǐng)大家自行檢查。
接下來(lái)我們分兩步簡(jiǎn)要證明下「可靠性」：首先，因?yàn)?Bob 經(jīng)過(guò)驗(yàn)證得知，所有 G 置換后的非邊集合都已被揭示，且全為 0，那么可以得出結(jié)論，!G <= !C，即G的非邊集合是環(huán)路子圖 C的非邊集合的子集。這等價(jià)于，C <= G，也就是說(shuō) G 包含一個(gè)哈密爾頓環(huán)路。這里請(qǐng)注意，這個(gè)可靠性概率是 100%。
然后，設(shè)想在一個(gè)「理想世界」中，Bob 獲得了某種超能力（比如拿到 Alice 的「超級(jí)眼鏡」），不需要 Alice 的超級(jí)手電筒，就能看穿云層，得到所有的隱藏比特 C'。然后當(dāng) Bob 得到 Perm()之后，就能通過(guò) Perm() 反算出 C，于是 Bob 就相當(dāng)于變身成了一個(gè)「抽取器」（Extractor），在理想世界中，它能把 Alice 要證明的知識(shí)給成功抽取出來(lái)。
那么怎么證明「零知識(shí)」呢？Alice 要具備一個(gè)超能力，就是在「理想世界」中，可以偷偷修改云朵中的隱藏比特。接下來(lái)就簡(jiǎn)單了，模擬器 Zlice 可以這么欺騙 Bob：
Zlice 把云朵中的隱藏比特全部置為 0
Zlice 隨機(jī)產(chǎn)生一個(gè)合法的 Perm()
大家發(fā)現(xiàn)了，關(guān)鍵是，天上隱藏的比特必須是一個(gè)可信的字符串，所謂「可信」，就是指它確實(shí)應(yīng)該是一個(gè)哈密爾頓環(huán)路子圖。那么第三方需要可信。
可是，這樣一個(gè)第三方是不是難以令人滿意？Alice 和 Bob 要絕對(duì)信任他，不會(huì)和對(duì)手串謀。如果他和 Alice 串謀，可以把隱藏比特串直接設(shè)置為全 0；或者他和 Bob 串謀，直接把這個(gè)比特串給 Bob 看。這個(gè)協(xié)議看起來(lái)不錯(cuò)，但是很難實(shí)用。我們接下來(lái)要對(duì)這個(gè)簡(jiǎn)單協(xié)議進(jìn)行升級(jí)。
升級(jí)隨機(jī)性
第一個(gè)升級(jí)是讓隱藏比特串變成一個(gè)「一致性均勻分布」的隨機(jī)的隱藏比特串，是一個(gè)看起來(lái)相當(dāng)隨機(jī)的比特串，而不是一個(gè)刻意擺放好的哈密爾頓子圖。
完全隨機(jī)意味著比特串中的 0 的個(gè)數(shù)和 1出現(xiàn)的概率大概接近。那么接下來(lái)一個(gè)難題是如何讓隨機(jī)比特串中能出現(xiàn)一個(gè)隨機(jī)的哈密爾頓環(huán)路子圖矩陣。方法非常簡(jiǎn)單粗暴：產(chǎn)生一個(gè)足夠長(zhǎng)的隨機(jī)串，然后從頭掃描，直到找到一個(gè)隨機(jī)的哈密爾頓環(huán)路為止。
可是……這個(gè)成功概率是不是非常非常?。课覀兿旅娼o出一個(gè)概率沒(méi)那么小的一種尋找方法。
我們先把比特串按照 5log(V) 的長(zhǎng)度進(jìn)行切分，然后如果每一個(gè)分片中的所有比特全為 1，那么我們把這個(gè)片段被視為鄰接矩陣中的一個(gè)值為 1 的單元，否則視為一個(gè)值為 0 的單元。這樣每一個(gè)矩陣單元出現(xiàn) 1 的概率為 1/(V^5)。
我們?nèi)∵B續(xù)的 V^6 個(gè)片段，構(gòu)成一個(gè) V^3 * V^3 的大矩陣。如果大矩陣中包含一個(gè) V*V的哈密爾頓環(huán)路矩陣，并且其他單元（總共 V^6 - V^2個(gè)） 都為 0。那么我們稱這個(gè)大矩陣為「有用」。
根據(jù)概率計(jì)算，出現(xiàn)一個(gè)「有用」矩陣的概率為 1/[V^(3/2)]。
注：「有用」矩陣的概率計(jì)算過(guò)程請(qǐng)參考 Fact 4.10.8, 「Foundations of Cryptography, Vol I」by Oded Goldreich，P304。
好了，我們需要升級(jí)下上一節(jié)的協(xié)議。因?yàn)楝F(xiàn)在「隱藏比特串」被拆分成了若干個(gè)大矩陣，這些大矩陣有些是「有用」的，有些是沒(méi)用的。
接下來(lái) Alice 要來(lái)構(gòu)造證明了，她先戴上超級(jí)眼鏡，掃描云朵中的 Hidden Bits，這要分兩種情況，
Case 1：如果 Alice 遇到了一個(gè)沒(méi)用的大矩陣 M，Alice 公開 M 的所有單元。
Case 2：如果 Alice 遇到了一個(gè)「有用」的大矩陣 M，這意味著 Alice 得到了一個(gè)隨機(jī)的 哈密爾頓環(huán)路 C'，然后 Alice 參照上一節(jié)的步驟進(jìn)行證明即可。
那么 Bob 怎么驗(yàn)證這個(gè)證明呢？我們還要分情況進(jìn)行討論，
Case 1：如果 Alice 公開了全部的 M，那么 Bob 就檢查這個(gè) M 是否「無(wú)用」。如果 M 無(wú)用，就認(rèn)為證明有效；否則拒絕。
Case 2：如果 Alice 發(fā)送的是形如（Perm()，X）這樣的證明，那么 Bob 按照上一節(jié)的驗(yàn)證方法進(jìn)行驗(yàn)證。
對(duì)于這個(gè)協(xié)議，Bob 已經(jīng)不再擔(dān)心第三方是否作弊，故意產(chǎn)生一個(gè)全零的比特串，但是 Alice 仍然擔(dān)心一旦第三方和 Bob 串謀，那么知識(shí)就徹底泄露了。
不僅如此，現(xiàn)在的協(xié)議還有個(gè)很強(qiáng)的限制，Alice 不能在看到隱藏比特之后再選擇需要證明的 G，否則 Alice 就可以作弊。如果一個(gè)證明者選擇證明的「命題」與 CRS 無(wú)關(guān)，那么這個(gè)證明者被稱為 Non-adaptive Adversary。
FLS 變換：從 Hidden Bits 到 NIZK
接下來(lái)，我們?cè)俅紊?jí)協(xié)議，把「隱藏比特串」中的隱藏特性去除，變成「公共參考串」CRS。這里我們要借助一個(gè)密碼學(xué)工具 —— Trapdoor Permutation，陷門置換。
所謂的陷門置換是指一個(gè)置換函數(shù) F(x)，x是一個(gè)集合 S 中的元素，然后函數(shù) F(x) 把x 映射到 S 中的另一個(gè)元素 y。同時(shí) F(x) 滿足單向性，即通過(guò) y 很難反算出 x；但是如果誰(shuí)擁有陷門 t，就能實(shí)現(xiàn)反向計(jì)算F^(-1)(t,y)=x。陷門置換還可以匹配一個(gè) Hardcore Predicate，h(x)=0/1，它能根據(jù) S 集合中的元素產(chǎn)生一個(gè)一致性分布的 0/1比特。介紹完畢，大家是不是有點(diǎn)暈，沒(méi)關(guān)系，暈一暈就習(xí)慣了?？傊痪湓?，陷門置換可以對(duì)公共參考串和Hidden Bits 進(jìn)行相互轉(zhuǎn)換。
先假設(shè)有這樣的密碼學(xué)工具，然后我們升級(jí)協(xié)議。
我們把公共參考串看成是一個(gè)列表，y1, y2, y3, ..., yn，列表中的每一項(xiàng)都是集合 S 中的元素。然后通過(guò) Hardcore Predicate 產(chǎn)生 Hidden Bits 中的每一個(gè)比特位。但是請(qǐng)注意，這里不能直接通過(guò) h(y)=b 來(lái)產(chǎn)生 Hidden Bits，因?yàn)檫@樣一來(lái) Bob 就能自己算出所有的 Hidden Bits，這違反了上一節(jié)的協(xié)議。為了保證對(duì) Bob 隱藏，我們需要用公共參考串的原象，也就是 x1, x2, x3, ..., xn 來(lái)產(chǎn)生 Hidden Bits，h(x)=b。Bob 雖然不能自己計(jì)算 b1, b2, b3, ..., bn，但是一旦得到一個(gè) x，他就能檢驗(yàn) F(x)?=y來(lái)判斷是否 x 是和公共參考串對(duì)應(yīng)，同時(shí)再計(jì)算 h(x)=b 得到被揭示的 Hidden Bits，b。
我們可以換一種不太準(zhǔn)確，但是更直觀的方式來(lái)理解，Alice 相當(dāng)于自己產(chǎn)生一對(duì)公私鑰。然后Alice 把公共參考串看成是一段「密文」，由于 Alice 有私鑰，于是可以對(duì)密文進(jìn)行解密，得到明文，這些明文，對(duì)于 Bob 而言就相當(dāng)于是 Hidden Bits。當(dāng) Alice 要「揭示」Hidden Bits 時(shí)，就出示相應(yīng)的明文片段，并且?guī)瞎€，那么 Bob 就能通過(guò)公鑰再次「加密」明文，與公共參考串的密文進(jìn)行比對(duì)，確保 Alice 沒(méi)有在揭示過(guò)程作弊。
下面是升級(jí)后的協(xié)議：
對(duì)于證明者 Alice：
Alice 隨機(jī)選擇一個(gè) Trapdoor Permutation，(F, h, t)
根據(jù)公共參考串中的每一個(gè) yi，利用陷門反向計(jì)算出 xi = F^(-1)(t, yi)
計(jì)算 Hidden Bits，bi=h(xi)
根據(jù)上一節(jié)的協(xié)議產(chǎn)生證明。假設(shè) Alice 要揭示的 Hidden bits 的位置集合為 r1,r2,...,rl，那么 Alice 向 Bob 發(fā)送對(duì)應(yīng)位置的 x，分別為 x_r1, x_r2, x_r3, ... x_rl ，連同(F, h)，和證明一起并發(fā)給 Bob。
對(duì)于驗(yàn)證者 Bob：
檢查 (F, h) 是否為一個(gè)合法的 Trapdoor Permutation。
對(duì) L 中的每一個(gè)元素 x_r，計(jì)算出被揭示的 Hidden Bits bi=h(F(x_r))，然后按照上一節(jié)的協(xié)議檢查證明。
這個(gè)新協(xié)議的「完備性」，請(qǐng)大家自行檢查。
對(duì)于「零知識(shí)」，我們需要構(gòu)造一個(gè)「模擬器」Zlice2，它的超能力是修改公共參考串。
模擬器直接調(diào)用上一節(jié)協(xié)議的模擬器 Zlice。得到一個(gè)三元組，(proof, {r}, )
對(duì)于每一個(gè)公共參考串位置，如果它對(duì)應(yīng)某一個(gè) r，模擬器從集合 S 中隨機(jī)選擇一個(gè) x_r，使得 h(x_r)=b_r，這里 b_r就是 中對(duì)應(yīng) r ；然后把 y_r=F(x_r) 作為假參考串的一部分。
對(duì)于每一個(gè)公共參考串位置，如果與 {r}無(wú)關(guān)，那么模擬器隨機(jī)選一個(gè) y即可
模擬器把所有的 y拼在一起，得到一個(gè)假CRS。
對(duì)于「可靠性」，事情變得不那么簡(jiǎn)單了。因?yàn)楝F(xiàn)在 Alice 有能力挑選 (F,h,t)，Alice 可以挑選一個(gè)對(duì)自己有利，甚至作弊的 (F, h, t)，使得她可以控制一次協(xié)議運(yùn)行的 Hidden Bits 的結(jié)果。對(duì)于本節(jié)升級(jí)后的新協(xié)議而言，需要重復(fù)很多遍，以致于雖然 Alice 可以控制一次協(xié)議運(yùn)行的 Hidden Bits，但是她對(duì)其它若干次協(xié)議運(yùn)行的 Hidden Bits 無(wú)能為力。換句話說(shuō)，Alice 無(wú)論如何挑選 (F, h, t) 都無(wú)法完全掌控多次的協(xié)議運(yùn)行。
這個(gè)升級(jí)變換理論上可以支持任意的 Hidden Bits 模型下的非交互式零知識(shí)證明，被稱為 FLS Protocol。FLS 變換有很多的好處：首先，這個(gè)隨機(jī)產(chǎn)生的 CRS 可以多次使用，實(shí)現(xiàn)所謂的「Multi-Theorem NIZK」；其次，可以實(shí)現(xiàn)「Adaptive Soundness」，即 Alice 可以先看到 CRS，然后再選擇要證明的內(nèi)容。最后，這個(gè)協(xié)議還是「Adaptive Zero-Knowledge」，即 Bob 也可以先看到 CRS，然后再選擇要證明的內(nèi)容給 Alice。
注：Adaptive Adversary 是比較符合現(xiàn)實(shí)世界的安全情況，比如第二類CCA安全。因?yàn)?CRS 是公開的，攻擊者可以先分析 CRS，再?zèng)Q定如何發(fā)起攻擊。
尋找理想的 Trapdoor Permutation
陷門置換 Trapdoor Permutation 最早出現(xiàn)在姚期智老師的論文「Theory and Application of Trapdoor Functions」[Yao82]中，是公鑰密碼學(xué)的重要基礎(chǔ)。在上一節(jié)給出的 FLS 變換中，需要一個(gè)理想化的 Trapdoor Permutation，所謂的理想化是指，每一個(gè) n-bit 字符串都能唯一變成另一個(gè) n-bit 字符串，并且不會(huì)出現(xiàn)「多對(duì)一」的映射關(guān)系。Alice 需要隨機(jī)抽樣一個(gè) Index，發(fā)給 Bob，然后 Bob 要能檢查出這個(gè) Index 所對(duì)應(yīng)的 F() 是否是一個(gè)「完美」的置換。問(wèn)題來(lái)了，怎么 Bob 怎么能在多項(xiàng)式時(shí)間內(nèi)檢查出來(lái)呢？如果 Bob 不能檢查，那么 Alice 就可以抽樣一個(gè)不完美的 Permutation（比如一個(gè)「多對(duì)一」的函數(shù)），從而可能作弊，破壞「Soundness」這個(gè)性質(zhì)，Bellare 和 Yung 發(fā)表在 1996 年的論文最早注意到了這一點(diǎn)，但是并沒(méi)有完全解決這個(gè)問(wèn)題[BY96]。
如何找到一個(gè)橋梁，能夠?qū)?Trapdoor Permutation 合適地抽象出來(lái)，同時(shí)能夠?qū)拥矫艽a學(xué)工具的實(shí)現(xiàn)上，是一個(gè)及其有挑戰(zhàn)性的工作。隨后各路密碼學(xué)家（包括 Oded Goldreich） 在這方面研究了很長(zhǎng)時(shí)間，發(fā)表了許許多多的論文 ，各種不同類型的 Trapdoor Permutation 被定義、被研究，但是仍然不能讓人滿意。直到最近（2018年）一個(gè)工作是 Ran Canetti 與 Amit Lichtenberg 提出了 Certifiable Injective Trapdoor Function 這樣一個(gè)新類型[RL18]，并證明了這種 Trapdoor Permutation 終于能滿足 FLS 變換要求。但這是不是故事的結(jié)束呢？理論密碼學(xué)家們估計(jì)不會(huì)停下探索的腳步。
除了基于 Trapdoor Permutation 的 FLS 變換 ，還有各式各樣的解決方案來(lái)升級(jí) Hidden Bits Model，比如采用 Invariant Signature[BG90]，或 Verifiable Random Generator [DN00] 來(lái)實(shí)現(xiàn) Hidden Bits 的變換，或者弱可驗(yàn)證隨機(jī)函數(shù) [BGRV09]， 還有一種叫做 publicly-verifiable trapdoor predicates 的方案[CHK03]。
三十年來(lái)，密碼學(xué)家們發(fā)明的 NIZK 方案有很多，但 Hidden Bits 方法是目前已知唯一的辦法，(1) 基于「一致性分布」的共享 CRS，(2) 實(shí)現(xiàn)任意 NP 語(yǔ)言的 NIZK Proofs（Not Arguments!）。
NIZK Proofs? 與 NIZK Arguments
在本文中，我們構(gòu)造的 NIZK 「證明」系統(tǒng)的可靠性屬于「Statistical Soundness」，而零知識(shí)則屬于「Computational Zero-Knowledge」。這意味著什么呢？這意味著，不管證明者 Alice 的算力有多強(qiáng)大（甚至超多項(xiàng)式），Alice 仍然無(wú)法作弊。但是，如果驗(yàn)證者 Bob 擁有超強(qiáng)的計(jì)算能力，那么是存在這種可能性：Bob 從證明中抽取到有價(jià)值的「知識(shí)」。
這又意味著什么？
這意味著，對(duì)于 NIZK Proofs 來(lái)說(shuō)，它的長(zhǎng)度肯定要比「知識(shí)」長(zhǎng)，知識(shí)即 NP 問(wèn)題中的 witness。只要 Bob 算力夠強(qiáng)，他就可以把證明解密。對(duì)于「抽取器」而言，它也需要在沒(méi)有交互的情況下抽取 witness 。證明最短的 NIZK Proofs 當(dāng)屬 Greg Gentry 等人采用「全同態(tài)加密」技術(shù)構(gòu)造的 NIZK 方案了 [GGI+14]，證明長(zhǎng)度只是稍稍大于 witness 的長(zhǎng)度。
那能不能構(gòu)造證明尺寸小于 witness 的 NIZK 呢？答案是 YES！
還有一類的 NIZK 系統(tǒng)被稱為 NIZK Arguments：它們的可靠性是「Computational Soundness」，零知識(shí)屬于「Perfect Zero-Knowledge」或者「Statistical Zero-Knowledge」。這說(shuō)明，Alice 如果算力超強(qiáng)，那么她是有作弊空間的，但是因?yàn)楝F(xiàn)實(shí)世界中，我們可以通過(guò)加大安全參數(shù)（Security Parameters）來(lái)極大地降低 Alice 作弊的可能性，但是能實(shí)現(xiàn)非常極致的零知識(shí)特性。由于弱化了可靠性，那么我們就可以繼續(xù)壓縮證明的尺寸。
注：在本系列中，我們并不刻意區(qū)分「證明」與「論證」這兩個(gè)詞。如果需要指明 Arguments 而非 Proofs，會(huì)專門強(qiáng)調(diào)。
假如說(shuō)我們要公開一個(gè) NIZK 證明到 Github上，假如過(guò)了一百年以后，Github 網(wǎng)站還在，而未來(lái)計(jì)算機(jī)的計(jì)算能力已經(jīng)有了質(zhì)的飛躍，這時(shí)候，一個(gè) NIZK Proof 可能會(huì)被算力攻破，泄露知識(shí)，而 NIZK Argument 則很大可能性上還保持安全性。
現(xiàn)在流行的熱詞 —— zkSNARK 中的 AR正是指代 Argument。
NIZK Argument 可以實(shí)現(xiàn) O(1) 常數(shù)級(jí)長(zhǎng)度的證明，即與 witness 的長(zhǎng)度無(wú)關(guān)。然而這需要隱藏更多的秘密到 CRS 中。
沒(méi)有秘密的世界
1956 年，哥德爾在一封寄給馮諾依曼的信中提到了一個(gè)著名的問(wèn)題，「P 是否等于 NP」。后來(lái)，這個(gè)問(wèn)題被 Clay 研究所列為七個(gè)千禧年難題之一，懸賞百萬(wàn)美金。
零知識(shí)證明系統(tǒng)正是為了保護(hù) witness 不泄露的前提下，實(shí)現(xiàn) NP 問(wèn)題的驗(yàn)證。那如果一旦證明了「P == NP」，這會(huì)意味著什么？這意味著 witness 不再有多大意義了，反正一個(gè)圖靈機(jī)也可以在多項(xiàng)式時(shí)間內(nèi)找到 witness。零知識(shí)證明試圖保護(hù)的 witness 也變得徒勞無(wú)益。
事實(shí)上，如果「P == NP」，現(xiàn)有的公鑰密碼學(xué)、對(duì)稱加密 AES 與 SM4、哈希算法所依賴的難解問(wèn)題都可能坍塌，我們可能很難保存秘密。不僅如此，
如果 P == NP，我們所處的世界將會(huì)變得非常不一樣?！窩reative Leaps」將不再有價(jià)值，求解問(wèn)題與驗(yàn)證問(wèn)題之間的鴻溝不復(fù)存在。每個(gè)能欣賞交響樂(lè)的人都會(huì)成為莫扎特，每個(gè)會(huì)推理的人都會(huì)變成高斯，每個(gè)能判斷投資好壞的人都會(huì)變成巴菲特。從達(dá)爾文進(jìn)化論的觀點(diǎn)出發(fā)：如果這就是我們存在的宇宙，為什么我們還沒(méi)有進(jìn)化得可以充分利用這個(gè)好處？—— Scott Aaronson (2006)
對(duì)于數(shù)學(xué)也一樣，數(shù)學(xué)證明的驗(yàn)證過(guò)程也是多項(xiàng)式復(fù)雜度的，如果「P == NP」，那么也就存在著多項(xiàng)式時(shí)間尋找證明的算法（如果證明存在）。這意味著哥德巴赫猜想、黎曼猜想將有可能得到證明，難怪 Lance Fortnow 在博客[For04]里這么說(shuō)：
A person who proves P == NP would walk home from the Clay Institute not with one million-dollar check but with seven. 如果誰(shuí)能證明 P = NP，那么他不會(huì)只拿著一張百萬(wàn)美元支票回家，而是七張。? —— Lance Fortnow (2004)
2002年的調(diào)查顯示，61% 的計(jì)算機(jī)科學(xué)家相信「P != NP」，而十年后，這個(gè)比例上升到了 83%[Wil12]。 而我是被 Scott Aaronson 的如下論斷說(shuō)服的：
自指論證：如果 P = NP 是事實(shí)，那么這個(gè)證明會(huì)比較容易被發(fā)現(xiàn)；但是如果 P != NP，那么這個(gè)證明會(huì)比較難發(fā)現(xiàn)。所以相信 P != NP 看起來(lái)會(huì)讓 數(shù)學(xué)現(xiàn)實(shí) 更一致一些?！?Scott Aaronson (2006)
盡管是如此不情愿，如果我們真的生活在一個(gè)沒(méi)有秘密的世界，那會(huì)是什么樣子？「環(huán)形監(jiān)獄 Panopticon」是 18 世紀(jì)英國(guó)哲學(xué)家 Jeremy Bentham 提出的一個(gè)驚悚概念。囚徒們被中心全天候監(jiān)控，沒(méi)有任何隱私可言，而且他們對(duì)自己是否處于被監(jiān)控狀態(tài)也無(wú)從得知。這個(gè)無(wú)比悲觀的論調(diào)讓人渾身不適，但很多人認(rèn)為，這可能是兩百多年前對(duì)未來(lái)網(wǎng)絡(luò)數(shù)字時(shí)代的一則精準(zhǔn)寓言。
從『Billy Budd』，卡夫卡的『The Trial』，到奧威爾的『1984』，到著名黑客 Kevin Mitnick 寫的超級(jí)大賣書『隱形的藝術(shù)』（教你如何在大數(shù)據(jù)時(shí)代保護(hù)自己的信息），似乎，危機(jī)四伏，風(fēng)險(xiǎn)不斷累積，對(duì)末日世界的想象給了作家們很好的素材? ……
偶爾無(wú)意中看到了一本有趣的漫畫『The Private Eye』，它描述了一個(gè)劫后余生的后現(xiàn)代場(chǎng)景：在未來(lái)，我們的所有信息數(shù)據(jù)都存放在云上，然后突然有一天，這個(gè)數(shù)據(jù)云「爆炸」了，不知道是什么原因（可能是誰(shuí)不小心打開了潘多拉的魔盒，找到了 P == NP 的構(gòu)造性證明），反正所有的信息，包括每個(gè)人最陰暗的過(guò)去，都不再成為秘密；所有的數(shù)字化的資產(chǎn)都被抹掉，所有的在線知識(shí)庫(kù)永久丟失；每個(gè)人的言行、賬單、郵件、聊天消息、銀行卡密碼、中學(xué)考卷、GPS位置信息，寫了一半的日記、刪除的照片、上網(wǎng)記錄，這些信息都將暴露給同事、鄰居、 朋友、親人、甚至任何一個(gè)好奇的人。
每個(gè)人都無(wú)地自容，惶惶不可終日，然后逐漸地，大家都選擇隱藏自己，人們出門都要戴上面具，以小心翼翼地保護(hù)自己的身份，甚至一個(gè)人可以選擇使用多個(gè)身份，國(guó)家法律規(guī)定任何偷窺行為都將被嚴(yán)懲，獲取信息成為了一種至少無(wú)上的權(quán)力，照相機(jī)需要被嚴(yán)格管控，互聯(lián)網(wǎng)不再存在，人們通訊又回到了電話亭時(shí)代 ……
這會(huì)是人類的終極命運(yùn)么？
未完待續(xù)
本文開頭提到了「隱藏隨機(jī)性」并不是必要的，我們來(lái)回想下 Hidden Bits 模型。這些 Hidden Bits 并沒(méi)有對(duì) Prover 隱藏，而是敞開了讓 Prover 知道，但是由于 Hidden Bits 是「一致性隨機(jī)分布」的字符串， 所以即使讓 Prover 知道了，他仍然逃不過(guò)隨機(jī)挑戰(zhàn)的火力。然而在流行的 zkSNARK 方案中，并沒(méi)有采用「一致性隨機(jī)分布」的 CRS，而是一組結(jié)構(gòu)化的隨機(jī)數(shù)。不管怎樣，用 CRS 來(lái)構(gòu)建「信任根基」的秘密，就是藏在其中的「秘密」。
這符合直覺(jué)，保守「秘密」也是一種信任。因?yàn)?Alice 不知道 CRS 中隱藏的秘密后門，所以無(wú)法作弊。同樣，Bob 不知道 CRS 中的秘密，也就沒(méi)辦法獲得「知識(shí)」。同樣，人與人之間的協(xié)作既要建立在公開透明的基礎(chǔ)上，也要保守秘密。
All human beings have three lives: public, private, and secret. 每個(gè)人都有三種生活，公開的，私人的，以及秘密的。—— Gabriel García Márqueel
致謝：感謝陳宇，丁晟超，張宇鵬，胡紅鋼，劉巍然，何德彪，萬(wàn)志國(guó)等老師的專業(yè)建議和指正，感謝安比實(shí)驗(yàn)室小伙伴（p0n1, even, valuka, Vawheter, yghu, mr）的修改建議。本文內(nèi)容不代表他們觀點(diǎn)。
最后附上漫畫書的鏈接：http://panelsyndicate.com/comics/tpeye 作者甚至把創(chuàng)作過(guò)程的郵件和草圖都放了出來(lái)，大家可以體驗(yàn)一下窺視制作過(guò)程的快感。
參考文獻(xiàn)
[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." In Theory 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 Cryptology 9.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 ACM 52.9 (2009): 78-86.
[Groth10a] Groth, Jens. "Short non-interactive zero-knowledge proofs." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2010.
[Groth10b] 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 Cryptology 11.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 Archive 2019 (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 News 50.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.
