亞瑟王的「隨機」挑戰：從互動到非互動式零知識證明

本文已更新至Github

https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/4/zkp-rom.md

Challenges are at times an indication of Lord's trust in you.

挑戰，有時是上天信任你的一種表現。 

——  D. Todd Christofferson

本文繼續長篇大論零知識證明背後的機制原理，希望幫助大家理解這一類「現代密碼學工具」的大致輪廓。本文約8000字，少量數學公式。

互動與挑戰

我們之前介紹的零知識證明系統都是「互動式」的，需要驗證者 Bob 在互動中提供一個或若干個「隨機數」來挑戰，比如「地圖三染色問題」（參看『系列二』）中，驗證者 Bob 需要「不斷地」隨機挑選一條邊來挑戰 Alice 的答案，直到 Bob 滿意為止，而 Alice 的作弊概率會「指數級」地衰減。而讓 Bob 相信證明的「基礎」取決於 Bob 所挑選的隨機數是不是足夠隨機。如果 Alice 能夠提前預測到 Bob 的隨機數，災難就會發生，現實世界就會退化成「理想世界」，而 Alice 就可以立即升級成「模擬器」，透過超能力來愚弄 Bob。

而『系列三』中，我們分析了 Schnorr 協議，協議中雖然驗證者 Bob 只需要挑選一個隨機數 c 來挑戰 Alice ，讓她計算一個值 z，但 Bob 絕對不能讓 Alice 有能力來預測到 c 的任何知識，否則，Alice 也會變身成模擬器。

隨機數的重要性不言而喻：

透過隨機數挑戰是互動式零知識證明的「信任根基」。

但，「互動過程」會限制應用場景。如果能將互動式零知識證明變成「非互動」？這會非常非常激動人心。所謂的非互動可以看成是隻有「一輪」的證明過程，即Alice 直接發一個證明給 Bob 進行驗證。

非互動式零知識證明，英文是 Non-Interactive Zero Knowledge，簡稱 NIZK。它意味整個證明被編碼為一個「字串」，它可以寫到一張紙上，透過郵件、聊天工具等各種方式隨意傳送給任何驗證者，字串甚至可以放在 Github 上隨時供大家下載驗證。

在區塊鏈世界，「NIZK」可以作為共識協議的一部分。因為一個交易需要多個礦工進行校驗。設想下，如果交易的傳送者和每個礦工都要互動一下，讓礦工進行挑戰，那麼共識過程將奇慢無比。而非互動式零知識證明則可以直接廣播給所有的礦工節點，讓他們自行驗證。

可能有朋友會問：只讓一個礦工挑戰不就夠了嗎？把礦工和交易傳送者的互動指令碼編碼成證明，然後廣播給其他礦工，然後其他礦工就直接相信這個挑戰過程是可信的，不也可以嗎？但是，很顯然，這裡需要相信第一個互動礦工作為可信第三方，第三方？似乎不是一個好主意……

而非互動式零知識證明，以下我們直接說「NIZK」，似乎就很理想了，沒有第三方賺差價。

「非互動」帶來的困惑

非互動式零知識證明，NIZK，如果存在，那麼它要比互動式證明強大得多。

• 互動式證明，只能取信於一個驗證者；而 NIZK 可以取信於多個驗證者，以至所有人。

• 互動式證明，只能在互動的那個時刻有效；而 NIZK 將始終有效。

NIZK 不僅可以跨越空間，還能跨越時間

聽上去很美，不是嗎？But, ……

重複下上節的一個結論：

透過隨機數挑戰是互動式零知識證明的「信任根基」。

可是如果 NIZK 失去了挑戰過程，有什麼後果？

我們已經回憶過「零知識」性質的證明（參考『系列二』），證明過程需要構造一個模擬器（演算法），它也和驗證者（Bob）在理想世界中進行互動，而驗證者 Bob 沒有能力區分出來對方是否是真的 Alice 還是一個模擬器。

如果現在考慮下 NIZK 中的 非互動式，假如「我」向「你」出示一張紙，上面寫著一個「真」證明 X ，又假如「你」在看過這張紙之後確實相信我了；又因為協議是「零知識」，那麼如果把「我」換成一個模擬器，模擬器也能「偽造」一個假證明 Y，能夠也讓「你」相信。

好了，問題來了：

• 你如何區分 X 和 Y ，孰真孰假？當然你無法區分，因為協議是零知識的，你必須不能區分

• 我可以同樣可以把 Y 出示給你看，那豈不是「我」就可以欺騙你了嗎？

是不是不和諧了？請大家在此處思考兩分鐘。

(兩分鐘後……)

因為 NIZK 沒有了互動，也就沒了挑戰過程，所有的證明過程都有 Alice 來計算書寫，理論上 Alice 確實是想寫什麼就寫什麼，沒人攔得住，比如 Alice 就寫「理想世界」的 假證明 Y。

想必深刻理解模擬器的朋友，在這裡會發現一個關鍵點：模擬器必須只能在「理想世界」中構造Y，也就是說，Y 這麼邪惡的東西只能存在於「理想世界」，不能到「現實世界」禍害人間。

繼續思考……

還有一個更深層次的問題，請大家回憶下「地圖三染色問題」，之所以模擬器不能在「現實世界」中為非作歹，核心原因是，他在理想世界中有「時間倒流」的超能力，而在「現實世界」中不存在這種黑魔法。現實世界的「不存在性」是關鍵。

而且，NIZK 中沒有互動，於是導致了一個嚴重的後果，模擬器沒有辦法使用「時間倒流」這個超能力，當然似乎也就不能區分證明者在兩個世界中的行為。

換句話說，如果我們面對任何一個 NIZK 系統，似乎「模擬器」就很難高高在上了，它好像只能飄落人間，成為一個普普通通的凡人。如果，我說如果，按此推論，假設模擬器不再具備超能力，那就意味著 Alice 和模擬器沒有區別，Alice 也可以成為一個模擬器，再繼續推論，Alice 就可以在「現實世界」中任意欺騙 Bob，那麼這個證明系統就不再有價值，因為它失去了「可靠性」。結論：任何的 NIZK 都不可靠。

這一定是哪裡出了問題……

上面我們在分析的過程中，提到了互動挑戰的缺失。確實，如果 Bob 不參與 Alice 產生證明的過程，證明所包含的每一個 bit 都由 Alice 提供，似乎「證明」本身不存在任何讓 Bob 信任的「根基」。這個從「直覺」上似乎說不通。

那是不是說，沒有 Bob 的參與就「徹底」沒辦法建立「信任根基」了呢？信任的根基還可以從哪裡來呢？

答案是「第三方」！

Wait ……，協議互動不是隻有兩方嗎？Alice 和 Bob，哪來第三方？

需要用特殊的方式引入第三方，而且方法不止一種，我們先研究第一種。

（淚目：不是說的好好的，咱們不引入第三方嗎？）

回顧 Schnorr 協議

我們再看一下老朋友——Schnorr 協議，它是一個三步協議：第一步，Alice 傳送一個承諾，然後第二步 Bob 傳送隨機數挑戰，第三步，Alice 迴應挑戰。

我們來看，如何把一個三步的 Schnorr 協議變成一步。

看一下 Schnorr 協議的第二步，Bob 需要給出一個隨機的挑戰數 c，這裡我們可以讓 Alice 用下面這個式子來計算這個挑戰數，從而達到去除協議第二步的目的。

其中 R 是 Alice 發給 Bob 的橢圓曲線點，PK 是公鑰。大家可以好好看看這個利用 Hash 演算法計算 c 的式子。這個式子達到了兩個目的：

1. Alice 在產生承諾 R 之前，沒有辦法預測 c，即使 c 最終變相是 Alice 挑選的

2. c 透過 Hash 函式計算，會均勻分佈在一個整數域內，而且可以作為一個隨機數（注：請大家暫且這麼理解，我們在後文再深入討論）

請注意：Alice 絕不能在產生 R 之前預測到 c，不然， Alice 就等於變相具有了「時間倒流」的超能力，從而能任意愚弄 Bob。

而一個密碼學安全 Hash 函式是「單向」的，比如 SHA256，SHA3，blake2 等等。這樣一來，雖然 c 是 Alice 計算的，但是 Alice 並沒有能力實現透過挑選 c 來作弊。因為只要 Alice 一產生 R， c 就相當於固定下來了。我們假設 Alice 這個凡人在「現實世界」中是沒有反向計算 Hash 的能力的。

看上圖，我們利用 Hash 函式，把三步 Schnorr 協議合併為了一步。Alice 可以直接傳送：(R, c, z)。又因為 Bob 擁有 PK，於是 Bob 可以自行計算出 c，於是 Alice 可以只傳送 (R, z) 即可。

我們把上面這個方案稍微變下形，就得到了「數字簽名」方案。所謂的數字簽名，就是「我」向「你」出示一個字串，比如「白日依山盡，黃河入海流」，然後為了證明這句詩是我出示的，我需要簽署某樣東西。這個東西能證明我的身份和這句詩進行了關聯。

從 NIZK 角度看數字簽名

不嚴格地說，數字簽名方案相當於在證明（1）我擁有私鑰，並且（2）私鑰和訊息進行了關聯計算。

我首先要證明我的身份，那麼這個簡單，這正是 Schnorr 協議的功能，能夠向對方證明「我擁有私鑰」這個陳述。並且這個證明過程是零知識的：不洩露關於「私鑰」的任何知識。

那麼如何和這句唐詩關聯呢？我們修改下計算 c 的過程：

這裡為了保證攻擊者不能隨意偽造簽名，正是利用了離散對數難題（DLP）與 Hash 函式滿足抗第二原象（Secondary Preimage Resistance ）這個假設。

注：這裡嚴格點講，為了保證數字簽名的不可偽造性，需要證明 Schnorr 協議滿足「Simulation Soundness」這個更強的性質。這點請參考文獻[2]

上圖就是大家所熟知的數字簽名方案 —— Schnorr 簽名方案[1]。在這裡還有一個最佳化，Alice 發給 Bob 的內容不是 (R, z) 而是 (c, z)，這是因為 R 可以透過 c, z 計算出來。

注：為什麼說這是一個「最佳化」呢？目前針對橢圓曲線的攻擊方法有 Shanks 演算法、Lambda 演算法 還有 Pollard's rho 演算法， 請大家記住他們的演算法複雜度大約都是 [6]，n 是有限域大小的位數。假設我們採用了非常接近 2^256 的有限域，也就是說 z 是 256bit，那麼橢圓曲線群的大小也差不多要接近 256bit，這樣一來，把 2^256 開平方根後就是 2^128，所以說 256bit 橢圓曲線群的安全性只有 128bit。那麼，挑戰數 c 也只需要 128bit 就足夠了。這樣 Alice 傳送 c 要比傳送 R 要更節省空間，而後者至少需要 256bit。c 和 z 兩個數值加起來總共 384bit。相比現在流行的 ECDSA 簽名方案來說，可以節省1/4 的寶貴空間。現在比特幣開發團隊已經準備將 ECDSA 簽名方案改為一種類 Schnorr 協議的簽名方案——muSig[2]，可以實現更靈活地支援多籤和聚合。

而採用 Hash 函式的方法來把一個互動式的證明系統變成非互動式的方法被稱為 Fiat-Shamir 變換[3]，它由密碼學老前輩 Amos Fiat 和 Adi Shamir 兩人在 1986 年提出。

重建信任 —— 隨機預言精靈

前文提到，失去了挑戰，似乎失去了證明的「信任根基」。而在 Schnorr 簽名方案中，Hash 函式擔負起了「挑戰者」的角色，這個角色有一個非常學術的名字：「隨機預言機」（Random Oracle）[6]。

可是這裡為何用 Hash？實際上當 Alice 要產生公共隨機數時，需要一個叫做「隨機預言機」的玩意兒，這是什麼？

開腦洞時間到！

我們設想在「現實世界」中，天上有一位「精靈」，他手持一個雙欄表格，左邊一欄為字串，右邊一欄為數字。任何人，包括你我，包括 Alice 和 Bob，都可以發字串給「精靈」。

精靈在拿到字串之後，會查表的左邊欄，看看錶格里有沒有這個字串，下面分兩種情況：

• 情況一：如果左邊欄找不到字串，那麼精靈會產生一個「真隨機數」，然後把字串與隨機數寫入到表格中，然後把隨機數返回地面上的凡人。

• 情況二：如果左邊欄有這個字串記錄，那麼精靈會將右邊欄裡面的數字直接返回給地面。

大家會發現這個精靈的行為其實很像一個隨機數發生器，但是又很不一樣，不一樣的地方在於當我們傳送相同的字串時，他會返回相同的數。這個精靈就是傳說中的「隨機預言機」。

而在合併 Schnorr 協議過程中，其實我們需要的是一個這樣的隨機預言精靈，而不是一個 Hash 函式。兩者有什麼不同的地方？區別就是：

• 隨機預言機每次對於新字串返回的是一個具有一致性分佈的「真」隨機數

• Hash 函式計算的結果並不是一個真正具有一致性分佈的隨機數

那麼為什麼前面用的是 Hash 函式呢？這是因為在現實世界中，真正的隨機預言機不存在！為什麼呢？事實上，一個 Hash 函式不可能產生真的隨機數，因為 Hash 函式是一個「確定性」演算法，除了引數以外，再沒有其它隨機量被引入。

而一個具有密碼學安全強度的 Hash 函式「似乎」可以充當一個「偽」隨機預言機。那麼合併後的安全協議需要額外增加一個很強的安全假設，這就是：

假設：一個密碼學安全的 Hash 函式可以近似地模擬傳說中的「隨機預言機」

因為這個假設無法被證明，所以我們只能信任這個假設，或者說當做一個公理來用。插一句， Hash 函式的廣義抗碰撞性質決定了它的輸出可以模擬隨機數，同時在很多情況下（並非所有），對 Hash 函式實施攻擊難度很高，於是許多的密碼學家都在大膽使用。

不使用這個假設的安全模型叫做「標準模型」，而使用這個假設的安全模型當然不能叫「非標準模型」，它有個好聽的專有名詞，叫做「隨機預言模型」。

世界上有兩種不同型別的人，喜歡甜豆花的，不喜歡甜豆花的。同樣，世界上的密碼學家分為兩種，喜歡隨機預言模型的，和不喜歡隨機預言模型的[6]。

構造根基 —— 被綁架的精靈

Schnorr 協議經過 Fiat-Shamir 變換之後，就具有 NIZK 性質。這不同於我們證明過的 SHVZK，SHVZK 要求驗證者誠實，而 NIZK 則不再對驗證者有任何不現實的要求，因為驗證者不參與互動，所謂要求誠實的驗證者這個問題就不復存在。

注：如果驗證者 Bob 不誠實會怎樣？那麼 Bob 有可能抽取出 Alice 的知識。但是對於三步 Schnorr 協議而言，它是否滿足「零知識」，目前還處於未知狀態。我們在系列三中只證明了它滿足一個比較弱的性質：SHVZK。

但是，當 Schnorr 協議搖身一變，變成非互動零知識證明系統之後，就真正的「零知識」了。

然而，可能你的問題也來了，這個論斷聽起來似乎有道理，請問能證明嗎？

時間到了，“翠花，上模擬器”

怎麼用模擬器大法來構造一個「理想世界」呢？大家可以想一下，我們之前使用過「時間倒流」，還有修改「隨機數傳送帶」超能力來讓「模擬器」來作弊。可是沒有互動了，這就意味著：「時間倒流」超能力不能用；Bob 的隨機數傳送帶也不存在了，「篡改傳送帶」這個超能力也不能用！

但模擬器總要具備某種「超能力」，從而能夠構建信任的「根基」

（如果模擬器在沒有超能力的情況下具備作弊能力，那相當於證明了協議的不可靠性）。

可能大家現在已經猜出來了，模擬器要在「隨機預言機」上動手腳。

先考慮下構造一個「理想世界」來證明「零知識」。在理想世界中，模擬器「綁架」了負責提供預言的「精靈」，當 Bob 向精靈索要一個隨機數的時候，精靈並沒有給一個真隨機數，而是給 Zlice（模擬器假扮的 Alice）提前準備好的一個數（也符合一致性分佈，保證不可區分性），「精靈」無可奈何地返回 Bob 一個看起來隨機，但實際上有後門的數字。所謂後門，就是這個數字是 Zlice 自己提前選擇好的。

• 第一步：Zlice 隨機選擇 z，隨機選擇c，計算 R'=z*G - c*PK 。

• 第二步：Zlice 將 c 與 (m, R') 寫入精靈的表格。

• 第三步：Zlice 將簽名 (c, z) 傳送給 Bob。

• 第四步：Bob 計算 R=z*G - c*PK，並向精靈傳送 (m, R)，精靈返回 c’。請注意，這裡 Bob 計算出來的 R 和 Zlice 計算出來的 R' 是相等。

• 第五步：Bob 驗證 c ?= c'，看看精靈傳回來的隨機數和對方發過來的隨機數是否相等。如果相等，則驗證簽名透過；否則，則驗證失敗。

透過綁架「精靈」，Zlice 同樣可以提前預知隨機數，這和時間倒流能達到同樣的效果。

我們已經證明了模擬器 Zlice 的「存在性」，於是我們上面已經證明了 NIZK。

接下來我們證明這個這個協議的「可靠性」。設想在另一個「理想世界」中，一個叫做「抽取器」的玩意兒，也同樣綁架了精靈。當無辜 Alice 的向「精靈」索要一個隨機數時，「精靈」返回了一個 c1，「抽取器」從精靈的表格中偷窺到了c1，當 Alice 計算出來 z1 之後，然後這時候「抽取器」仍然可以發動「時間倒流」超能力，讓 Alice 倒退到第二步，再次向「精靈」要一個隨機數，Alice 傳送的字串顯然和第一次傳送的字串是相同的，(R, m)。按道理，因為 (R, m) 已經寫在精靈表格的「左欄」裡，所以一個誠實的「精靈」應該返回 c1。但是，「抽取器」綁架了精靈，他把表格中對應 (R, m) 這一行的「右欄」改成了一個不同的數 c2。當 Alice 計算出另一個 z2 之後，抽取器就完成了任務，透過下面的方程計算出 Alice 的私鑰 sk：

Fiat-Shamir 變換 —— 從 Public-Coin 到 NIZK

不僅僅對於 Schnorr 協議，對於任意的 「Public-Coin 協議」，都可以用 Fiat-Shamir 變換來把整個協議「壓縮」成一步互動，也就是一個非互動式的證明系統，這個變換技巧最早來自於 Amos Fiat 與 Adi Shamir 兩人的論文『How to Prove Yourself: Practical Solutions to Identification and Signature Problems.』，發表在 1986 年的 Crypto 會議上[5]。也有一說，這個技巧來源於 Manuel Blum[6].

重複一遍，在 Public-coin 協議中，驗證者 Bob 只做一類事情，就是產生一個隨機數，然後挑戰 Alice 。透過 Fiat-Shamir 變換，可以把 Bob 每一次的「挑戰行為」用一次「隨機預言」來代替。

而在具體實現中，隨機預言需要用一個具有密碼學安全強度的 Hash 函式（不能隨便選，一定要採用密碼學安全的 Hash），而 Hash 函式的引數應該是之前所有的上下文輸入。下面是一個示例圖，大家可以迅速理解這個 Fiat-Shamir 變換的做法。

前面提到，在非互動式證明系統中，需要引入一個第三方來構建信任的「根基」，使得 Bob 可以完全相信由 Alice 所構造的證明。在這裡，第三方就是那個「精靈」，用學術黑話就是「隨機預言」（Random Oracle）。這個精靈並不是一個真實存在的第三方，而是一個虛擬的第三方，它同時存在於「現實世界」與「理想世界」。在「現實世界」中，精靈是一個負責任的安靜美男子，而在「理想世界」中，它會被「模擬器」綁架。

Public-Coin 協議還有一個好聽的名字， 「Arthur-Merlin 遊戲」 ……

看上圖，左邊的“白袍”就是 Merlin（魔法師梅林），中間拿劍的帥哥就是 King Arthur（亞瑟王），兩個角色來源於中世紀歐洲傳說——亞瑟王的圓桌騎士。

Arthur 是一個不耐煩的國王，他隨身攜帶一個硬幣，而 Merlin是一個有著無限制計算能力的神奇魔法師，然後魔法師想說服國王相信某個「論斷」為真，於是魔法師會和國王進行到對話，但是由於國王比較懶，他每次只會拋一個硬幣，然後「挑戰」魔法師，而魔法師需要及時應對，而且需要讓國王在 k 輪之後能夠相信自己的論斷。由於 Merlin 有魔法，所以亞瑟王拋的硬幣都能被 Merlin 看到[7]。

這與我們在『系列一』中提到的互動式證明系統（Interactive Proof System，簡稱 IP）有些神似，但又不同。IP 由 Goldwasser，Micali 與 Rackoff（簡稱GMR）在 1985 年正式提出，它的證明能力覆蓋很大一類的計算複雜性問題。而不同的地方在於：在 IP 的定義中，證明者 Prover 和 驗證者 Verifier 都是可以拋硬幣的圖靈機，Verifier 可以偷偷拋硬幣，並對 Prover 隱藏；而在 Arthur-Merlin 遊戲中，國王只能拋硬幣，不僅如此，而且拋硬幣的結果總會被 Merlin 知道。

但是，Fiat-Shamir 變換隻能在「隨機預言模型」下證明安全，而用 Hash 函式實現隨機預言的過程是否安全是缺少安全性證明的。不僅如此，「隨機預言模型」下安全的協議可能是有不安全的，已經有人找到了一些反例[8]；更不幸的是，S. Goldwasser 與 Y. Tauman 在 2003 年證明了 Fiat-Shamir 變換本身也是存在安全反例的[9]。但是這並不意味著 Fiat-Shamir 變換不能用，只是在使用過程中要非常小心，不能盲目套用。

儘管如此，人們無法抵擋 Fiat-Shamir 變換的誘惑，其使用極其廣泛。值得一提的是，最熱的通用非互動零知識證明 zkSNARK 的各種方案中，Fiat-Shamir 變換比比皆是。比如大家可能耳熟能詳的 Bulletproofs（子彈證明），此外還有一些暫時還不那麼有名的通用零知識證明方案，比如 Hyrax，Ligero，Supersonic，Libra 等（我們後續會抽絲剝繭，逐一解讀）。

小心：Fiat-Shamir 變換中的安全隱患

在 Fiat-Shamir 變換中，要尤其注意餵給 Hash 函式的引數，在實際的程式碼實現中，就有這樣的案例，漏掉了 Hash 函式的部分引數：

比如在 A, Hash(A), B, Hash(B)中，第二個 Hash 函式就漏掉了引數A，正確的做法應該是A, Hash(A), B, Hash(A,B)。這一類的做法會引入嚴重的安全漏洞，比如在瑞士的電子投票系統 SwissPost-Scytl 中，就在 Fiat-Shamir 變換的實現程式碼中多次漏掉了本來應該存在的引數，導致了攻擊者不僅可以隨意作廢選票，還可以任意偽造選票，達到舞弊的目的[10]。因此在工程實現中，請務必注意。

細心讀者也許會回看一下 Schnorr 簽名，大家會發現 Schnorr 簽名中的 Hash 演算法似乎也漏掉了一個引數 PK，並不是嚴格的 Fiat-Shamir 變換，這被稱為 Weak Fiat-Shamir 變換[11]，不過這個特例並沒有安全問題[3]，請未成年人不要隨意模仿。

最近一些學者開始在標準模型下研究如何嚴格證明 Fiat-Shamir 變換的安全性，目前要麼引入額外的強安全假設，要麼針對某個特定協議進行證明，但似乎進展並不大。

互動的威力

話說在1985年，當 GMR 三人的論文歷經多次被拒之後終於被 STOC’85 接受，另一篇類似的工作也同時被 STOC'85 接受，這就是來自於匈牙利羅蘭大學的 László Babai，與來自以色列理工的 Shlomo Moran 兩人撰寫的論文『Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes』[7]，引入了 Public-coin 互動式協議（顧名思義，Verifier 只公開拋硬幣）。

國王 Arthur 的方法很簡單，透過反覆地「隨機」挑戰來檢驗 Merlin 的論斷，這符合我們前面講述過的直覺：採用隨機挑戰來構建信任的「根基」。Babai 在論文中證明了一個有趣的結論：AM[k]=AM[2]，其中 k 表示互動的次數，互動多次產生的效果居然和互動兩次等價。所謂互動兩次是指：Arthur 發一個挑戰數，然後 Merlin 迴應。

注：還有一類的問題屬於 MA，這一類問題的互動順序與 AM不同，MA中是 Merlin 先給出證明，然後 Arthur 拋硬幣檢驗。已證明：MA 能處理的問題是 AM 的子集。

不僅如此，Babai 還大膽猜測： AM[poly] 與 IP 是等價的。這是一個神奇的論斷：國王很懶，他只需要透過拋多項式次硬幣，就能成功挑戰魔法師，而這種方式的表達能力居然完全等價於 GMR 描述的互動式證明系統 IP。果不其然，在 STOC'86 會議上，來自 S. Goldwasser 與 M. Sipser 的論文證明了這一點，AM[poly] == IP[12]。

這意味著：反覆公開的「隨機挑戰」威力無窮，它等價於任意的互動式證明系統。但是 AM[poly] 和別的計算複雜性類的關係如何，是接下來的研究熱點。

三年後，1989 年11月底，距今恰好三十年，年輕的密碼學家 Noam Nisan 發出了一封郵件，把自己的臨時學術結論發給了幾個密碼學家，然後他就跑去南美洲度假了。可是他不曾想到，這一個郵件會引爆歷史上一場激烈的學術競賽，M. Blum, S. Kannan, D. Lipton, D. Beaver, J. Feigenbaum, H. Karloff, C. Lund 等等一大群精英開始加入戰鬥，他們沒日沒夜地互相討論，並且競相釋出自己的研究成果，終於在12月26號，剛好一個月，Adi Shamir 證明了下面的結論：

AM[poly] == IP == PSPACE

它解釋了「有效證明」這個概念的計算理論特徵，並且解釋了「互動式證明系統」這個概念所能涵蓋的計算能力。

注：NP 類 是 PSPACE 類的子集，前者大家比較熟悉，後者關聯遊戲或者下棋中的制勝策略[13]。

而 L. Babai 於是寫了一篇文章，名為「Email and the unexpected power of interaction」（電子郵件與互動的始料未及的威力）[14]，詳細闡述了這一整個月在「郵件互動」中精彩紛呈的學術競賽，以及關於「互動證明」的來龍去脈。

公共參考串 —— 另一種「信任根基」

除了採用「隨機預言機」之外，非互動零知識證明系統採用「公共參考串」（Common Reference String），簡稱「CRS」，完成隨機挑戰。它是在證明者 Alice 在構造 NIZK 證明之前由一個受信任的第三方產生的隨機字串，CRS 必須由一個受信任的第三方來完成，同時共享給 Alice 和 驗證者 Bob。

是的，你沒看錯，這裡又出現了「第三方」！雖然第三方不直接參與證明，但是他要保證隨機字串產生過程的可信。而產生 CRS 的過程也被稱為「Trusted Setup」，這是大家又愛又恨的玩意兒。顯然，在現實場景中引入第三方會讓人頭疼。CRS 到底用來做什麼？Trusted Setup 的信任何去何從？這部分內容將留給本系列的下一篇。

未完待續

非互動式零知識證明 NIZK 的「信任根基」也需要某種形式的隨機「挑戰」，一種「挑戰」形式是交給「隨機預言精靈」；另一種「挑戰」是透過 Alice 與 Bob 雙方共享的隨機字串來實現。兩種挑戰形式本質上都引入了第三方，並且兩者都必須提供可以讓「模擬器」利用的「後門」，以使得讓模擬器在「理想世界」中具有某種「優勢」，而這種優勢在「現實世界」中必須失效。

NIZK 散發著無窮魅力，讓我不時驚歎，在過去三十多年裡，先驅們所探尋到的精妙結論，同時還有如此之多的未知角落，在等待靈感之光的照射。

本系列文章在 Github 上的專案倉庫收到了第一個 Pull Request，來自Jingyu Hu(colortigerhu)，只改了個把字，但那一瞬間，我感受到了生命力。知識交流，思想碰撞，很迷人，不是嗎？

Everyone we interact with becomes a part of us.

與我們交往互動的每一個人都是我們自身的一部分。

—— Jodi Aman

致謝：特別感謝 丁晟超，劉巍然 ，陳宇的專業建議和指正，感謝安比實驗室小夥伴們(p0n1, even, aphasiayc, Vawheter, yghu, mr)的修改建議。

致謝：自Nisan起密碼學研究競賽軼事參考自鄧老師的文章[13]。

參考文獻

[1] Schnorr, Claus-Peter. "Efficient signature generation by smart cards." Journal of cryptology 4.3 (1991): 161-174.

[2] Paillier, Pascal, and Damien Vergnaud. "Discrete-log-based signatures may not be equivalent to discrete log." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2005.

[3] Pointcheval, David, and Jacques Stern. "Security arguments for digital signatures and blind signatures." Journal of cryptology 13.3 (2000): 361-396.

[4] Maxwell, Gregory, Andrew Poelstra, Yannick Seurin, and Pieter Wuille. "Simple schnorr multi-signatures with applications to bitcoin." Designs, Codes and Cryptography 87, no. 9 (2019): 2139-2164.

[5] Fiat, Amos, and Adi Shamir. "How to prove yourself: Practical solutions to identification and signature problems." Conference on the Theory and Application of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1986.

[6] Bellare, Mihir, and Phillip Rogaway. "Random Oracles Are Practical: a Paradigm for Designing Efficient Protocols."  Proc. of the 1st CCS (1995): 62-73.

[7] László Babai, and Shlomo Moran. "Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes." Journal of Computer and System Sciences 36.2 (1988): 254-276.m

[8] Canetti, Ran, Oded Goldreich, and Shai Halevi. "The random oracle methodology, revisited." Journal of the ACM (JACM)51.4 (2004): 557-594.

[9] Shafi Goldwasser, and Yael Tauman . "On the (in) security of the Fiat-Shamir paradigm." 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.. IEEE, 2003.

[10] Lewis, Sarah Jamie, Olivier Pereira, and Vanessa Teague. "Addendum to how not to prove your election outcome: The use of nonadaptive zero knowledge proofs in the ScytlSwissPost Internet voting system, and its implica tions for castasintended verifi cation." Univ. Melbourne, Parkville, Australia (2019).

[11] Bernhard, David, Olivier Pereira, and Bogdan Warinschi. "How not to prove yourself: Pitfalls of the fiat-shamir heuristic and applications to helios." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2012.

[12] Goldwasser, Shafi, and Michael Sipser. "Private coins versus public coins in interactive proof systems." Proceedings of the eighteenth annual ACM symposium on Theory of computing. ACM, 1986.

[13]  Papadimitriou, Christos H. "Games against nature." Journal of Computer and System Sciences 31.2 (1985): 288-301.

[14] Babai, László. "E-mail and the unexpected power of interaction." Proceedings Fifth Annual Structure in Complexity Theory Conference. IEEE, 1990.

[15] Yi Deng. "零知識證明：一個略顯嚴肅的科普."   https://zhuanlan.zhihu.com/p/29491567