著名的哥德斯堡七橋問題就是這麼描述,如果不重複地穿過下面七座橋。
哥德斯堡七橋地圖顯然存在多個奇點,不存在尤拉路徑。如果給定任何一個地圖,是否存在一個尤拉環路,這是一個 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 把雲朵中的隱藏位元全部置為 0
Zlice 隨機產生一個合法的 Perm()
大家發現了,關鍵是,天上隱藏的位元必須是一個可信的字串,所謂「可信」,就是指它確實應該是一個哈密爾頓環路子圖。那麼第三方需要可信。
可是,這樣一個第三方是不是難以令人滿意?Alice 和 Bob 要絕對信任他,不會和對手串謀。如果他和 Alice 串謀,可以把隱藏位元串直接設定為全 0;或者他和 Bob 串謀,直接把這個位元串給 Bob 看。這個協議看起來不錯,但是很難實用。我們接下來要對這個簡單協議進行升級。
升級隨機性
第一個升級是讓隱藏位元串變成一個「一致性均勻分佈」的隨機的隱藏位元串,是一個看起來相當隨機的位元串,而不是一個刻意擺放好的哈密爾頓子圖。
完全隨機意味著位元串中的 0 的個數和 1出現的概率大概接近。那麼接下來一個難題是如何讓隨機位元串中能出現一個隨機的哈密爾頓環路子圖矩陣。方法非常簡單粗暴:產生一個足夠長的隨機串,然後從頭掃描,直到找到一個隨機的哈密爾頓環路為止。
可是……這個成功概率是不是非常非常小?我們下面給出一個概率沒那麼小的一種尋找方法。
1. 我們先把位元串按照 5log(V) 的長度進行切分,然後如果每一個分片中的所有位元全為 1,那麼我們把這個片段被視為鄰接矩陣中的一個值為 1 的單元,否則視為一個值為 0 的單元。這樣每一個矩陣單元出現 1 的概率為 1/(V^5)。
2. 我們取連續的 V^6 個片段,構成一個 V^3 * V^3 的大矩陣。如果大矩陣中包含一個 V*V的哈密爾頓環路矩陣,並且其他單元(總共 V^6 - V^2個) 都為 0。那麼我們稱這個大矩陣為「有用」。
3. 根據概率計算,出現一個「有用」矩陣的概率為 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:
1. Alice 隨機選擇一個 Trapdoor Permutation,(F, h, t)
2. 根據公共參考串中的每一個 yi,利用陷門反向計算出 xi = F^(-1)(t, yi)
3. 計算 Hidden Bits,bi=h(xi)
4. 根據上一節的協議產生證明。假設 Alice 要揭示的 Hidden bits 的位置集合為 r1,r2,...,rl,那麼 Alice 向 Bob 傳送對應位置的 x,分別為 xr1, xr2, xr3, ... xrl ,連同(F, h),和證明一起併發給 Bob。
對於驗證者 Bob:
1. 檢查 (F, h) 是否為一個合法的 Trapdoor Permutation。
2. 對 L 中的每一個元素 xr,計算出被揭示的 Hidden Bits bi=h(F(xr)),然後按照上一節的協議檢查證明。
這個新協議的「完備性」,請大家自行檢查。
對於「零知識」,我們需要構造一個「模擬器」Zlice2,它的超能力是修改公共參考串。
1. 模擬器直接呼叫上一節協議的模擬器 Zlice。得到一個三元組,(proof, {r}, {b})
2. 對於每一個公共參考串位置,如果它對應某一個 r,模擬器從集合 S 中隨機選擇一個 xr,使得 h(xr)=br,這裡 br就是 {b}中對應 r ;然後把 yr=F(xr) 作為假參考串的一部分。
3. 對於每一個公共參考串位置,如果與 {r}無關,那麼模擬器隨機選一個 y即可
4. 模擬器把所有的 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 作者甚至把創作過程的郵件和草圖都放了出來,大家可以體驗一下窺視製作過程的快感。