本文作者：郭宇
Once exposed, a secret loses all its power.? 一旦泄露薛闪，秘密就失去了全部威力? ― Ann Aguirre
這已經(jīng)是本系列的第五篇文章了，這一篇繼續(xù)深入非交互式零知識(shí)證明俊犯。 本文約 12,000 字。
提綱
CRS 的前世今生
哈密爾頓環(huán)路問題
云中的秘密：Hidden Bits
升級(jí)隨機(jī)性
FLS變換：從 Hidden Bits 到 NIZK
尋找理想的 Trapdoor Permutation
NIZK Proof vs. NIZK Argument
沒有秘密的世界
追到這里的讀者想必已對(duì)零知識(shí)證明有了一個(gè)大概的認(rèn)識(shí)岔乔。你是否想過這個(gè)問題：零知識(shí)證明為何可行？這里請(qǐng)大家思考一下（比如系列一 中的地圖三染色問題的流程） …… （此處停留三分鐘）下面兩個(gè)要素 似乎 必不可少：
「交互」：驗(yàn)證者通過多次反復(fù)挑戰(zhàn)，把證明者作弊概率降低到一個(gè)極小的值
「隱藏隨機(jī)性」：驗(yàn)證者產(chǎn)生讓證明者無法預(yù)測(cè)的隨機(jī)數(shù)進(jìn)行挑戰(zhàn)
然而對(duì)于非交互式零知識(shí)證明—— NIZK 來說狰腌，如何實(shí)現(xiàn)上面兩點(diǎn)？在 系列四 我們介紹了如何采用「隨機(jī)預(yù)言機(jī)」來扮演一個(gè)虛擬的「第三方」角色牧氮，實(shí)現(xiàn)虛擬的「交互」與「隨機(jī)挑戰(zhàn)」琼腔。本文將深入講述另一種方法，如何通過一段共享的字符串去除「交互」與「隱藏隨機(jī)性」蹋笼。這個(gè)字符串必須事先由「第三方」來隨機(jī)產(chǎn)生展姐，這就是傳說中的「公共參考串」（Common Reference String，簡稱 CRS）剖毯。
CRS 的前世今生
假如我們不借助任何其它手段圾笨，限定證明者 Prover 和驗(yàn)證者 Verifier 只能進(jìn)行「一次交互」來實(shí)現(xiàn)「零知識(shí)證明」，那么他們只能證明「平凡」問題逊谋，也就是計(jì)算復(fù)雜類 BPP（Bounded-error Probabilistic Polynomial time）擂达，而這個(gè)復(fù)雜度類大家一般猜想可能等價(jià)于 P（但還懸而未決，沒有被證明胶滋！BPP 可以理解為 P + Randomness）板鬓。
注：如果 Prover 與 Verifier 只做一次交互，在這樣的 NIZK 系統(tǒng)中究恤，我們很容易能構(gòu)造一個(gè) Decision Procedure —— Verify(x, Sim(x))俭令，來證明和證偽定理，因此只能證明平凡問題 BPP部宿。
平凡問題雖然也可以零知識(shí)證明抄腔，但沒有意義！怎么理解呢理张？因?yàn)轵?yàn)證者直接可以在多項(xiàng)式時(shí)間內(nèi)根據(jù)「輸出」求解出「秘密輸入」赫蛇，雖然驗(yàn)證者能夠求解，但是「證明」本身并沒有額外為驗(yàn)證者提供更多的「知識(shí)」雾叭。換句話說悟耘，不需要證明者出示證明，驗(yàn)證者就知道命題為真织狐，于是證明過程也是零知識(shí)的暂幼。
因此，當(dāng)我們討論「零知識(shí)證明」時(shí)移迫，要考慮帶「知識(shí)」的 NP 類問題旺嬉。大家都知道，P 問題是「確定性圖靈機(jī)」多項(xiàng)式時(shí)間內(nèi)可以求解的復(fù)雜類起意，它的執(zhí)行路徑對(duì)于輸入 x是一個(gè)線性的狀態(tài)轉(zhuǎn)移鹰服。而 NP 問題是「不確定性圖靈機(jī)」多項(xiàng)式時(shí)間可以求解的問題類病瞳。所謂的不確定性圖靈機(jī)揽咕，就是它每次往前走一步是不確定的悲酷，有很多個(gè)選擇，只要任何一個(gè)執(zhí)行路徑能到達(dá)終止?fàn)顟B(tài)亲善，就表示它解決了該問題 x设易。換句話說，它的執(zhí)行軌跡是一棵樹蛹头。那么如果我們把不確定性圖靈機(jī)每一步的路徑選擇記錄下來（這個(gè)執(zhí)行路徑的記錄叫做 witness顿肺，也就是我們反復(fù)提到的「知識(shí)」），那么把(x, witness)交給一個(gè)確定性圖靈機(jī)渣蜗，那么它也能在多項(xiàng)式時(shí)間內(nèi)解決掉 x 問題屠尊。
再強(qiáng)調(diào)一下替梨，「知識(shí)」能提高圖靈機(jī)的解決問題的能力否彩。
NP 問題中存在著不想「泄露」給驗(yàn)證者的知識(shí) witness，這時(shí)其兴，在一個(gè)交互式證明系統(tǒng)中骚烧，證明者和驗(yàn)證者在「知識(shí)」的掌握程度上是不對(duì)等的浸赫。
為了保證證明過程的「零知識(shí)」，我們需要保證：模擬器與驗(yàn)證者的不對(duì)等赃绊〖认浚可是，模擬器沒有 witness啊碧查，怎么能讓他們不對(duì)等呢运敢？上一篇我們介紹了「隨機(jī)預(yù)言機(jī)」，我們通過允許讓模擬器可以綁架「隨機(jī)預(yù)言精靈」的方式制造不平等么夫。本篇將講述如何利用 CRS 來制造不平等者冤。
CRS 是一個(gè)在證明之前就已經(jīng)公開的，并且在證明者與驗(yàn)證者之間共享的档痪，隨機(jī)字符串涉枫。我們?cè)趺磥硎褂?CRS 呢？直覺上腐螟，一串雙方都「知道」的信息愿汰，并不會(huì)增加「知識(shí)」不對(duì)等的情況。
首先大家會(huì)想乐纸，能不能直接用 CRS 作為隨機(jī)挑戰(zhàn)數(shù)呢衬廷？可不可以讓 CRS 來代替「隨機(jī)預(yù)言精靈」的角色？答案是不行汽绢！
為什么吗跋？這是因?yàn)?CRS 是在證明之前就已經(jīng)產(chǎn)生了，如果證明者 Prover 提前知道了所有的隨機(jī)挑戰(zhàn)數(shù)，那么很顯然這個(gè)隨機(jī)挑戰(zhàn)也就失去了意義跌宛。
注：請(qǐng)大家回想下「隨機(jī)預(yù)言機(jī)」是如何保證證明者無法提前預(yù)測(cè)「隨機(jī)挑戰(zhàn)數(shù)」的酗宋？沒想明白的你，請(qǐng)重讀系列（四）疆拘。
CRS 的使命就是讓「模擬器」與「驗(yàn)證者」不平等蜕猫。怎么做呢？隱藏一些「秘密」進(jìn)去哎迄。
如果進(jìn)一步追問回右，隱藏了「秘密」有什么用呢？當(dāng)然有用啦漱挚，在「理想世界」中翔烁，模擬器與抽取器才能很開心地玩耍起來（獲取某些超能力） ……
1988年，Manuel Blum旨涝，Paul Feldman 和 Silvio Micali 三位先驅(qū)發(fā)表的論文 「Non-Interactive Zero-Knowledge and Its Applications」（『非交互式零知識(shí)證明及其應(yīng)用』[BFM88]）展示了「交互」與「隱藏隨機(jī)性」的不必要性租漂。他們給出了一個(gè)地圖三染色問題的 NIZK 證明系統(tǒng)，在一段共享的隨機(jī)產(chǎn)生的字符串（即CRS）的幫助下颊糜。
不過哩治，……，我不會(huì)告訴你這個(gè)方案需要共享大概 n^4 超長的 CRS衬鱼，其中 n是要證明的「命題」的長度业筏。
1990 年，Uriel Feige鸟赫，Dror Lapidot 與 Adi Shamir 三人提出了另一種構(gòu)造 NP 語言的 NIZK 方案 [FLS90]蒜胖。與 [BFM88] 不一樣的是，這個(gè) NIZK 方案不再基于特定的數(shù)論假設(shè)抛蚤，而是基于一個(gè)密碼學(xué)工具 Trapdoor Permutation台谢。在這個(gè)方案中，F(xiàn)LS 提出了「隱藏比特」（Hidden Bits）的概念岁经，然后把 Hidden Bits 藏入了 CRS朋沮。對(duì)于模擬器而言，就可以通過修改 CRS 中的 Hidden Bits 來達(dá)到模擬的效果缀壤，從而體現(xiàn)出對(duì)驗(yàn)證者 Verifier 的優(yōu)越性樊拓。不過，這個(gè)方案需要共享更長的 CRS塘慕，超過 k * n^5筋夏，這里 k 是安全參數(shù)。
此后图呢，Hidden Bits 的思路被很多人采用条篷，值得一提的是骗随，Kilian 與 Petrank 采用了一種更巧妙的方法來使用 Hidden Bits [KP98]（這里空間太小，寫不下:）赴叹，成功地把 CRS 的長度縮減到了 k * n^2蚊锹。后來 J. Groth 繼續(xù)優(yōu)化 ，把 CRS 的長度縮小到了大約 k*n[Groth10a]稚瘾。
除了 Hidden Bits，J. Groth姚炕，R. Ostrovsky 與 A. Sahai? [GOS06] 使用了同態(tài)加密方案 Boneh-Goh-Nissim [BGN05] 或 Boneh-Boyen-Shacham 來實(shí)現(xiàn) NIZK摊欠，他們把加密方案的「公鑰」當(dāng)做是 CRS，同時(shí) Prover 加密作為證明柱宦，然后利用同態(tài)性質(zhì)來證明另一個(gè) NP-Complete 問題——布爾電路的可滿足性問題些椒。這個(gè)方案的最大優(yōu)點(diǎn)，就是 CRS 長度是固定的掸刊，因?yàn)橹皇且粋€(gè)密鑰而已免糕，長度只有 k。對(duì)于模擬器而言忧侧，它可以通過超能力石窑，拿到這個(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)成烁兰，被用來實(shí)現(xiàn)「知識(shí)承諾」。其中 x 與 ? 是兩個(gè)隨機(jī)數(shù)徊都，在產(chǎn)生完 CRS 之后沪斟，必須被「遺忘」。有些人把這部分需要遺忘的隨機(jī)數(shù)叫做「Toxic Wastes」暇矫，這容易誤導(dǎo)讀者币喧。他們不僅無毒無害，而且非常有用袱耽。他們是被藏入 CRS 的「秘密」杀餐，是模擬器的武器。如果模擬器得到了 x 與 ?朱巨，就能偽造證明史翘，從而保證證明的零知識(shí)。而對(duì)于抽取器，他能直接通過 KEA 假設(shè)內(nèi)建的抽取函數(shù)來抽取知識(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] 等方案采用旗国。
接下來，我們就從一個(gè)簡單的例子開始注整，理解如何基于 CRS 來構(gòu)造 NIZK能曾。在這之前，我們需要介紹一個(gè) NP-Complete 問題——哈密爾頓環(huán)路問題肿轨。
哈密爾頓環(huán)路問題
想象出一個(gè)地圖中有若干個(gè)城市寿冕，城市與城市間可以有公路。
假如給你一副地圖椒袍，讓你找出一條路徑蚂斤，不重復(fù)地走遍所有的公路（假設(shè)每條公路都是風(fēng)景美如明信片的 Parkway，或許你想不重復(fù)地吃遍每條公路邊上的麥當(dāng)勞槐沼，出于某種情懷）曙蒸。相信你會(huì)馬上興奮起來，這不就是小時(shí)候?qū)W過的「一筆畫」么岗钩？判斷一個(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）。
而如果地圖存在超過2個(gè)以上的奇點(diǎn)编饺，那么就不存在歐拉回路乖篷，比如著名的哥德斯堡七橋問題。
著名的哥德斯堡七橋問題就是這么描述透且，如果不重復(fù)地穿過下面七座橋撕蔼。
哥德斯堡七橋地圖顯然存在多個(gè)奇點(diǎn)，不存在歐拉路徑秽誊。如果給定任何一個(gè)地圖鲸沮，是否存在一個(gè)歐拉環(huán)路，這是一個(gè) P 問題养距，也就是一個(gè)計(jì)算機(jī)可以在 poly(n) 多項(xiàng)式時(shí)間內(nèi)尋找。
注：歐拉環(huán)路的尋找算法被稱為 Fleury算法日熬。
對(duì)于這樣一個(gè) P 問題棍厌， 如果一個(gè)證明者 Prover 證明他知道一個(gè)歐拉回路，那么他可以直接發(fā)送回路的明文竖席，然后驗(yàn)證者 Verifier 驗(yàn)證回路正確與否耘纱。請(qǐng)注意，這個(gè)過程仍然是零知識(shí)的毕荐。因?yàn)槭觯琕erifier 并沒有通過 Prover 發(fā)送的信息獲得任何 額外的知識(shí)。換句話說憎亚，Verifier 并沒有因?yàn)榭吹交芈吩笨埽鰪?qiáng)了自身計(jì)算能力，因?yàn)?Verifier 本來就可以自行計(jì)算歐拉回路第美。
而我們要講的是「哈密爾頓環(huán)路問題」則是一個(gè) NP 問題蝶锋，描述如下：
是否一個(gè)地圖存在一個(gè)環(huán)路，能不重復(fù)地穿過每一個(gè)城市什往。
比如下面這張地圖：
我們用一個(gè)矩陣 V * V 的矩陣來表示這個(gè)地圖扳缕，凡是兩個(gè)城市（A, B）有公路相連接，那么就在(A, B) 和 (B, A)里面填上 1别威，否則填 0躯舔。這個(gè)矩陣被稱為「鄰接矩陣」，我們可以把這個(gè)鄰接矩陣拍扁省古，就變成了一個(gè) 0/1 比特串粥庄。
尋找「哈密爾頓環(huán)路」是一個(gè) NP-Complete 問題，換句話說豺妓，不存在一個(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í)穿過了每一個(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(.)黍析，然后通過這個(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)過置換變換的圖前后是 同構(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)過置換無誤羽历。
第三步情況（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è)新答案祷愉，然后把每一條邊都鎖起來陨晶，交給 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 可以輕易地檢查地圖上露出來的那些邊是否構(gòu)成了一個(gè)不重復(fù)地經(jīng)過所有城市的環(huán)路。
如果這個(gè) Sigma 協(xié)議只走一遍的話诫龙， Alice 作弊的概率是 50%析显，如果重復(fù) n 遍，Alice 作弊概率會(huì)指數(shù)級(jí)減小签赃。大家可以試著用「模擬器」和「抽取器」的方法來證明這個(gè)協(xié)議的「零知識(shí)」與「可靠性」谷异。
ZK-HAM 的變形：ZK-HAM-2
接下來把上面的這個(gè)三步協(xié)議改動(dòng)一下。大家先考慮下這樣一個(gè)簡單事實(shí)：如果一個(gè)僅包含環(huán)路的子圖 C 是 圖 G的子圖姊舵，C <= G那么說明 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)之間都存在一條邊）仰税。
用鄰接矩陣來理解构资，就是如果一個(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(.)耙饰，并且通過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)來了鳞贷，大家仔細(xì)看看這個(gè)新版的 Sigma 協(xié)議的第一步。有沒有發(fā)現(xiàn)什么情況虐唠？
第一步 Alice 發(fā)送的內(nèi)容是與地圖G無關(guān)的搀愧！
同樣，第二步 Bob 發(fā)送的挑戰(zhàn)也是與地圖無關(guān)的疆偿。這樣我們可以把第一步發(fā)的承諾改成事先準(zhǔn)備好的比特串咱筛，而且我們假設(shè)這個(gè)比特串由一個(gè)可信第三方來產(chǎn)生，這樣一來 Bob 就沒有必要發(fā)送 b=0 這個(gè)分支杆故，因?yàn)榭尚诺牡谌绞钦\實(shí)的迅箩，他一定是事先準(zhǔn)備好一個(gè)正確的環(huán)路子圖。這樣处铛，由于 Bob 只需要發(fā)送 1挑戰(zhàn)分支饲趋，那么這一步也可以去除。
于是撤蟆，三步協(xié)議變成了一步奕塑，我們成功去除了交互，有望實(shí)現(xiàn) NIZK 枫疆。
我們接下來把 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。接下來圃泡，我們要解釋一個(gè)新概念：「隱藏比特」（Hidden Bits）[FLS90]碟案。Hidden Bits 是這樣一串隨機(jī)比特，它們對(duì)于驗(yàn)證者 Bob 隱藏颇蜡，但是對(duì)于證明者 Alice 公開价说。然后在證明過程中，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。
接下來我們要通過 Hidden Bits 來完成一個(gè)單步交互鳍贾，完成 ZK-HAM-2 協(xié)議的功能鞍匾。在 ZK-HAM-2 中的第一步交洗，Alice 產(chǎn)生一個(gè)隨機(jī)的置換 Perm()骑科，然后通過 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 長度的比特串，可以解釋成一個(gè) V*V 的矩陣行贪，其中每一行只包含一個(gè) 1漾稀，每一列也只包含一個(gè) 1模闲，矩陣的其它單元都為 0。
接下來 Alice 如何構(gòu)造證明呢崭捍？這其實(shí)很簡單：
Alice 通過「超級(jí)眼鏡」得到了一個(gè)隨機(jī)的哈密爾頓環(huán)路子圖 C'尸折，然后計(jì)算得到一個(gè)置換 Perm()，使得 Perm(C)=C'殷蛇。
Alice 根據(jù) Perm() 來計(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)過置換之后昼蛀，Bob 抬頭看天上對(duì)應(yīng)的「隱藏比特」宴猾，比特值必須為 0
我們?cè)僮屑?xì)地深入理解下這個(gè)非交互協(xié)議。先從「完備性」入手：如果 Alice 沒有作弊叼旋，那么很顯然能夠通過 Bob 的驗(yàn)證仇哆，這里請(qǐng)大家自行檢查。
接下來我們分兩步簡要證明下「可靠性」：首先夫植，因?yàn)?Bob 經(jīng)過驗(yàn)證得知讹剔，所有 G 置換后的非邊集合都已被揭示，且全為 0详民，那么可以得出結(jié)論延欠，!G <= !C，即G的非邊集合是環(huán)路子圖 C的非邊集合的子集沈跨。這等價(jià)于由捎，C <= G，也就是說 G 包含一個(gè)哈密爾頓環(huán)路饿凛。這里請(qǐng)注意狞玛，這個(gè)可靠性概率是 100%。
然后涧窒，設(shè)想在一個(gè)「理想世界」中心肪，Bob 獲得了某種超能力（比如拿到 Alice 的「超級(jí)眼鏡」），不需要 Alice 的超級(jí)手電筒纠吴，就能看穿云層硬鞍，得到所有的隱藏比特 C'。然后當(dāng) Bob 得到 Perm()之后，就能通過 Perm() 反算出 C固该，于是 Bob 就相當(dāng)于變身成了一個(gè)「抽取器」（Extractor）碑隆，在理想世界中，它能把 Alice 要證明的知識(shí)給成功抽取出來蹬音。
那么怎么證明「零知識(shí)」呢上煤？Alice 要具備一個(gè)超能力，就是在「理想世界」中著淆，可以偷偷修改云朵中的隱藏比特劫狠。接下來就簡單了，模擬器 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é)議看起來不錯(cuò)，但是很難實(shí)用狭郑。我們接下來要對(duì)這個(gè)簡單協(xié)議進(jìn)行升級(jí)腹暖。
升級(jí)隨機(jī)性
第一個(gè)升級(jí)是讓隱藏比特串變成一個(gè)「一致性均勻分布」的隨機(jī)的隱藏比特串，是一個(gè)看起來相當(dāng)隨機(jī)的比特串翰萨，而不是一個(gè)刻意擺放好的哈密爾頓子圖脏答。
完全隨機(jī)意味著比特串中的 0 的個(gè)數(shù)和 1出現(xiàn)的概率大概接近。那么接下來一個(gè)難題是如何讓隨機(jī)比特串中能出現(xiàn)一個(gè)隨機(jī)的哈密爾頓環(huán)路子圖矩陣缨历。方法非常簡單粗暴：產(chǎn)生一個(gè)足夠長的隨機(jī)串以蕴，然后從頭掃描糙麦，直到找到一個(gè)隨機(jī)的哈密爾頓環(huán)路為止辛孵。
可是……這個(gè)成功概率是不是非常非常小赡磅？我們下面給出一個(gè)概率沒那么小的一種尋找方法魄缚。
我們先把比特串按照 5log(V) 的長度進(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ì)算過程請(qǐng)參考 Fact 4.10.8, 「Foundations of Cryptography, Vol I」by Oded Goldreich墓懂，P304。
好了霉囚，我們需要升級(jí)下上一節(jié)的協(xié)議捕仔。因?yàn)楝F(xiàn)在「隱藏比特串」被拆分成了若干個(gè)大矩陣，這些大矩陣有些是「有用」的盈罐，有些是沒用的榜跌。
接下來 Alice 要來構(gòu)造證明了，她先戴上超級(jí)眼鏡盅粪，掃描云朵中的 Hidden Bits斜做，這要分兩種情況，
Case 1：如果 Alice 遇到了一個(gè)沒用的大矩陣 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 是否「無用」。如果 M 無用民晒，就認(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 無關(guān)，那么這個(gè)證明者被稱為 Non-adaptive Adversary津滞。
FLS 變換：從 Hidden Bits 到 NIZK
接下來耕陷，我們?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) 滿足單向性隆敢，即通過 y 很難反算出 x；但是如果誰擁有陷門 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)暈皇钞，沒關(guān)系悼泌，暈一暈就習(xí)慣了〖薪纾總之一句話馆里，陷門置換可以對(duì)公共參考串和Hidden Bits 進(jìn)行相互轉(zhuǎn)換。
先假設(shè)有這樣的密碼學(xué)工具可柿，然后我們升級(jí)協(xié)議鸠踪。
我們把公共參考串看成是一個(gè)列表，y1, y2, y3, ..., yn复斥，列表中的每一項(xiàng)都是集合 S 中的元素营密。然后通過 Hardcore Predicate 產(chǎn)生 Hidden Bits 中的每一個(gè)比特位。但是請(qǐng)注意永票，這里不能直接通過 h(y)=b 來產(chǎn)生 Hidden Bits卵贱，因?yàn)檫@樣一來 Bob 就能自己算出所有的 Hidden Bits滥沫，這違反了上一節(jié)的協(xié)議侣集。為了保證對(duì) Bob 隱藏键俱，我們需要用公共參考串的原象，也就是 x1, x2, x3, ..., xn 來產(chǎn)生 Hidden Bits世分，h(x)=b。Bob 雖然不能自己計(jì)算 b1, b2, b3, ..., bn，但是一旦得到一個(gè) x庵楷，他就能檢驗(yàn) F(x)?=y來判斷是否 x 是和公共參考串對(duì)應(yīng)百姓，同時(shí)再計(jì)算 h(x)=b 得到被揭示的 Hidden Bits，b瓢阴。
我們可以換一種不太準(zhǔn)確畅蹂，但是更直觀的方式來理解，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 就能通過公鑰再次「加密」明文检访，與公共參考串的密文進(jìn)行比對(duì)，確保 Alice 沒有在揭示過程作弊仔掸。
下面是升級(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}無關(guān)，那么模擬器隨機(jī)選一個(gè) y即可
模擬器把所有的 y拼在一起外里，得到一個(gè)假CRS怎爵。
對(duì)于「可靠性」，事情變得不那么簡單了盅蝗。因?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 無能為力裂问。換句話說侧啼，Alice 無論如何挑選 (F, h, t) 都無法完全掌控多次的協(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è)「完美」的置換喻鳄。問題來了扼倘，怎么 Bob 怎么能在多項(xiàng)式時(shí)間內(nèi)檢查出來呢？如果 Bob 不能檢查除呵，那么 Alice 就可以抽樣一個(gè)不完美的 Permutation（比如一個(gè)「多對(duì)一」的函數(shù)）再菊，從而可能作弊，破壞「Soundness」這個(gè)性質(zhì)颜曾，Bellare 和 Yung 發(fā)表在 1996 年的論文最早注意到了這一點(diǎn)纠拔，但是并沒有完全解決這個(gè)問題[BY96]。
如何找到一個(gè)橋梁泛豪，能夠?qū)?Trapdoor Permutation 合適地抽象出來稠诲，同時(shí)能夠?qū)拥矫艽a學(xué)工具的實(shí)現(xiàn)上，是一個(gè)及其有挑戰(zhàn)性的工作诡曙。隨后各路密碼學(xué)家（包括 Oded Goldreich） 在這方面研究了很長時(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 變換 既鞠，還有各式各樣的解決方案來升級(jí) Hidden Bits Model煤傍，比如采用 Invariant Signature[BG90]，或 Verifiable Random Generator [DN00] 來實(shí)現(xiàn) Hidden Bits 的變換嘱蛋，或者弱可驗(yàn)證隨機(jī)函數(shù) [BGRV09]蚯姆， 還有一種叫做 publicly-verifiable trapdoor predicates 的方案[CHK03]。
三十年來洒敏，密碼學(xué)家們發(fā)明的 NIZK 方案有很多龄恋，但 Hidden Bits 方法是目前已知唯一的辦法，(1) 基于「一致性分布」的共享 CRS凶伙，(2) 實(shí)現(xiàn)任意 NP 語言的 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 仍然無法作弊。但是金拒，如果驗(yàn)證者 Bob 擁有超強(qiáng)的計(jì)算能力兽肤，那么是存在這種可能性：Bob 從證明中抽取到有價(jià)值的「知識(shí)」。
這又意味著什么殖蚕？
這意味著轿衔，對(duì)于 NIZK Proofs 來說，它的長度肯定要比「知識(shí)」長睦疫，知識(shí)即 NP 問題中的 witness害驹。只要 Bob 算力夠強(qiáng)，他就可以把證明解密蛤育。對(duì)于「抽取器」而言宛官，它也需要在沒有交互的情況下抽取 witness 。證明最短的 NIZK Proofs 當(dāng)屬 Greg Gentry 等人采用「全同態(tài)加密」技術(shù)構(gòu)造的 NIZK 方案了 [GGI+14]瓦糕，證明長度只是稍稍大于 witness 的長度底洗。
那能不能構(gòu)造證明尺寸小于 witness 的 NIZK 呢？答案是 YES咕娄！
還有一類的 NIZK 系統(tǒng)被稱為 NIZK Arguments：它們的可靠性是「Computational Soundness」亥揖，零知識(shí)屬于「Perfect Zero-Knowledge」或者「Statistical Zero-Knowledge」。這說明，Alice 如果算力超強(qiáng)费变，那么她是有作弊空間的摧扇，但是因?yàn)楝F(xiàn)實(shí)世界中，我們可以通過加大安全參數(shù)（Security Parameters）來極大地降低 Alice 作弊的可能性挚歧，但是能實(shí)現(xiàn)非常極致的零知識(shí)特性扛稽。由于弱化了可靠性，那么我們就可以繼續(xù)壓縮證明的尺寸滑负。
注：在本系列中在张，我們并不刻意區(qū)分「證明」與「論證」這兩個(gè)詞。如果需要指明 Arguments 而非 Proofs矮慕，會(huì)專門強(qiáng)調(diào)帮匾。
假如說我們要公開一個(gè) NIZK 證明到 Github上，假如過了一百年以后凡傅，Github 網(wǎng)站還在辟狈，而未來計(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í)長度的證明趟妥，即與 witness 的長度無關(guān)猫态。然而這需要隱藏更多的秘密到 CRS 中。
沒有秘密的世界
1956 年披摄，哥德爾在一封寄給馮諾依曼的信中提到了一個(gè)著名的問題亲雪，「P 是否等于 NP」。后來疚膊，這個(gè)問題被 Clay 研究所列為七個(gè)千禧年難題之一义辕，懸賞百萬美金。
零知識(shí)證明系統(tǒng)正是為了保護(hù) witness 不泄露的前提下寓盗，實(shí)現(xiàn) NP 問題的驗(yàn)證灌砖。那如果一旦證明了「P == NP」，這會(huì)意味著什么傀蚌？這意味著 witness 不再有多大意義了基显，反正一個(gè)圖靈機(jī)也可以在多項(xiàng)式時(shí)間內(nèi)找到 witness。零知識(shí)證明試圖保護(hù)的 witness 也變得徒勞無益善炫。
事實(shí)上撩幽，如果「P == NP」，現(xiàn)有的公鑰密碼學(xué)箩艺、對(duì)稱加密 AES 與 SM4窜醉、哈希算法所依賴的難解問題都可能坍塌制跟，我們可能很難保存秘密。不僅如此酱虎，
如果 P == NP雨膨，我們所處的世界將會(huì)變得非常不一樣《链「Creative Leaps」將不再有價(jià)值聊记，求解問題與驗(yàn)證問題之間的鴻溝不復(fù)存在。每個(gè)能欣賞交響樂的人都會(huì)成為莫扎特恢暖，每個(gè)會(huì)推理的人都會(huì)變成高斯排监，每個(gè)能判斷投資好壞的人都會(huì)變成巴菲特。從達(dá)爾文進(jìn)化論的觀點(diǎn)出發(fā)：如果這就是我們存在的宇宙杰捂，為什么我們還沒有進(jìn)化得可以充分利用這個(gè)好處舆床？—— Scott Aaronson (2006)
對(duì)于數(shù)學(xué)也一樣，數(shù)學(xué)證明的驗(yàn)證過程也是多項(xiàng)式復(fù)雜度的嫁佳，如果「P == NP」挨队，那么也就存在著多項(xiàng)式時(shí)間尋找證明的算法（如果證明存在）。這意味著哥德巴赫猜想蒿往、黎曼猜想將有可能得到證明盛垦，難怪 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，那么他不會(huì)只拿著一張百萬美元支票回家瓤漏，而是七張腾夯。? —— Lance Fortnow (2004)
2002年的調(diào)查顯示，61% 的計(jì)算機(jī)科學(xué)家相信「P != NP」蔬充，而十年后蝶俱，這個(gè)比例上升到了 83%[Wil12]。 而我是被 Scott Aaronson 的如下論斷說服的：
自指論證：如果 P = NP 是事實(shí)饥漫，那么這個(gè)證明會(huì)比較容易被發(fā)現(xiàn)榨呆；但是如果 P != NP，那么這個(gè)證明會(huì)比較難發(fā)現(xiàn)趾浅。所以相信 P != NP 看起來會(huì)讓 數(shù)學(xué)現(xiàn)實(shí) 更一致一些愕提。—— Scott Aaronson (2006)
盡管是如此不情愿皿哨，如果我們真的生活在一個(gè)沒有秘密的世界浅侨，那會(huì)是什么樣子？「環(huán)形監(jiān)獄 Panopticon」是 18 世紀(jì)英國哲學(xué)家 Jeremy Bentham 提出的一個(gè)驚悚概念证膨。囚徒們被中心全天候監(jiān)控如输，沒有任何隱私可言，而且他們對(duì)自己是否處于被監(jiān)控狀態(tài)也無從得知。這個(gè)無比悲觀的論調(diào)讓人渾身不適不见，但很多人認(rèn)為澳化，這可能是兩百多年前對(duì)未來網(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ì)末日世界的想象給了作家們很好的素材? ……
偶爾無意中看到了一本有趣的漫畫『The Private Eye』希痴，它描述了一個(gè)劫后余生的后現(xiàn)代場(chǎng)景：在未來，我們的所有信息數(shù)據(jù)都存放在云上春感，然后突然有一天砌创，這個(gè)數(shù)據(jù)云「爆炸」了，不知道是什么原因（可能是誰不小心打開了潘多拉的魔盒鲫懒，找到了 P == NP 的構(gòu)造性證明）嫩实，反正所有的信息，包括每個(gè)人最陰暗的過去刀疙，都不再成為秘密舶赔；所有的數(shù)字化的資產(chǎn)都被抹掉，所有的在線知識(shí)庫永久丟失谦秧；每個(gè)人的言行、賬單撵溃、郵件疚鲤、聊天消息、銀行卡密碼缘挑、中學(xué)考卷集歇、GPS位置信息，寫了一半的日記语淘、刪除的照片诲宇、上網(wǎng)記錄，這些信息都將暴露給同事惶翻、鄰居姑蓝、 朋友、親人吕粗、甚至任何一個(gè)好奇的人纺荧。
每個(gè)人都無地自容，惶惶不可終日，然后逐漸地宙暇，大家都選擇隱藏自己输枯，人們出門都要戴上面具，以小心翼翼地保護(hù)自己的身份占贫，甚至一個(gè)人可以選擇使用多個(gè)身份桃熄，國家法律規(guī)定任何偷窺行為都將被嚴(yán)懲，獲取信息成為了一種至少無上的權(quán)力型奥，照相機(jī)需要被嚴(yán)格管控蜻拨，互聯(lián)網(wǎng)不再存在，人們通訊又回到了電話亭時(shí)代 ……
這會(huì)是人類的終極命運(yùn)么桩引？
未完待續(xù)
本文開頭提到了「隱藏隨機(jī)性」并不是必要的缎讼，我們來回想下 Hidden Bits 模型。這些 Hidden Bits 并沒有對(duì) Prover 隱藏坑匠，而是敞開了讓 Prover 知道血崭，但是由于 Hidden Bits 是「一致性隨機(jī)分布」的字符串， 所以即使讓 Prover 知道了厘灼，他仍然逃不過隨機(jī)挑戰(zhàn)的火力夹纫。然而在流行的 zkSNARK 方案中，并沒有采用「一致性隨機(jī)分布」的 CRS设凹，而是一組結(jié)構(gòu)化的隨機(jī)數(shù)舰讹。不管怎樣，用 CRS 來構(gòu)建「信任根基」的秘密闪朱，就是藏在其中的「秘密」月匣。
這符合直覺，保守「秘密」也是一種信任奋姿。因?yàn)?Alice 不知道 CRS 中隱藏的秘密后門锄开，所以無法作弊。同樣称诗，Bob 不知道 CRS 中的秘密萍悴，也就沒辦法獲得「知識(shí)」。同樣寓免，人與人之間的協(xié)作既要建立在公開透明的基礎(chǔ)上癣诱，也要保守秘密。
All human beings have three lives: public, private, and secret. 每個(gè)人都有三種生活袜香，公開的撕予，私人的，以及秘密的困鸥⌒崾撸—— Gabriel García Márqueel
致謝：感謝陳宇剑按，丁晟超，張宇鵬澜术，胡紅鋼艺蝴，劉巍然，何德彪鸟废，萬志國等老師的專業(yè)建議和指正猜敢，感謝安比實(shí)驗(yàn)室小伙伴（p0n1, even, valuka, Vawheter, yghu, mr）的修改建議。本文內(nèi)容不代表他們觀點(diǎn)盒延。
最后附上漫畫書的鏈接：http://panelsyndicate.com/comics/tpeye 作者甚至把創(chuàng)作過程的郵件和草圖都放了出來缩擂，大家可以體驗(yàn)一下窺視制作過程的快感奕枢。
參考文獻(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.
