我們再看一下老朋友——Schnorr 協議，它是一個三步協議：第一步，Alice 傳送一個承諾，然後第二步 Bob 傳送隨機數挑戰，第三步，Alice 迴應挑戰。
我們來看，如何把一個三步的 Schnorr 協議變成一步。
看一下 Schnorr 協議的第二步，Bob 需要給出一個隨機的挑戰數 c，這裡我們可以讓 Alice 用下面這個式子來計算這個挑戰數，從而達到去除協議第二步的目的。
c = Hash(PK, R)
其中 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 的過程：
m = "白日依山盡，黃河入海流"
c = Hash(m, R)
這裡為了保證攻擊者不能隨意偽造簽名，正是利用了離散對數難題（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：
sk = (z1 - z2)/(c1 - c2)
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)，只改了個把字，但那一瞬間，我感受到了生命力。知識交流，思想碰撞，很迷人，不是嗎？
