本文作者：郭宇
本文已更新至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.”? 挑戰(zhàn)，有時是上天信任你的一種表現(xiàn)。― D. Todd Christofferson
本文繼續(xù)長篇大論零知識證明背后的機制原理，希望幫助大家理解這一類「現(xiàn)代密碼學(xué)工具」的大致輪廓。本文約8000字，少量數(shù)學(xué)公式。
交互與挑戰(zhàn)
我們之前介紹的零知識證明系統(tǒng)都是「交互式」的，需要驗證者 Bob 在交互中提供一個或若干個「隨機數(shù)」來挑戰(zhàn)，比如「地圖三染色問題」（參看『系列二』）中，驗證者 Bob 需要「不斷地」隨機挑選一條邊來挑戰(zhàn) Alice 的答案，直到 Bob 滿意為止，而 Alice 的作弊概率會「指數(shù)級」地衰減。而讓 Bob 相信證明的「基礎(chǔ)」取決于 Bob 所挑選的隨機數(shù)是不是足夠隨機。如果 Alice 能夠提前預(yù)測到 Bob 的隨機數(shù)，災(zāi)難就會發(fā)生，現(xiàn)實世界就會退化成「理想世界」，而 Alice 就可以立即升級成「模擬器」，通過超能力來愚弄 Bob。
而『系列三』中，我們分析了 Schnorr 協(xié)議，協(xié)議中雖然驗證者 Bob 只需要挑選一個隨機數(shù) c 來挑戰(zhàn) Alice ，讓她計算一個值 z，但 Bob 絕對不能讓 Alice 有能力來預(yù)測到 c 的任何知識，否則，Alice 也會變身成模擬器。
隨機數(shù)的重要性不言而喻：
通過隨機數(shù)挑戰(zhàn)是交互式零知識證明的「信任根基」。
但，「交互過程」會限制應(yīng)用場景。如果能將交互式零知識證明變成「非交互」？這會非常非常激動人心。所謂的非交互可以看成是只有「一輪」的證明過程，即Alice 直接發(fā)一個證明給 Bob 進行驗證。
非交互式零知識證明，英文是 Non-Interactive Zero Knowledge，簡稱 NIZK。它意味整個證明被編碼為一個「字符串」，它可以寫到一張紙上，通過郵件、聊天工具等各種方式隨意發(fā)送給任何驗證者，字符串甚至可以放在 Github 上隨時供大家下載驗證。
在區(qū)塊鏈世界，「NIZK」可以作為共識協(xié)議的一部分。因為一個交易需要多個礦工進行校驗。設(shè)想下，如果交易的發(fā)送者和每個礦工都要交互一下，讓礦工進行挑戰(zhàn)，那么共識過程將奇慢無比。而非交互式零知識證明則可以直接廣播給所有的礦工節(jié)點，讓他們自行驗證。
可能有朋友會問：只讓一個礦工挑戰(zhàn)不就夠了嗎？把礦工和交易發(fā)送者的交互腳本編碼成證明，然后廣播給其他礦工，然后其他礦工就直接相信這個挑戰(zhàn)過程是可信的，不也可以嗎？但是，很顯然，這里需要相信第一個交互礦工作為可信第三方，第三方？似乎不是一個好主意……
而非交互式零知識證明，以下我們直接說「NIZK」，似乎就很理想了，沒有第三方賺差價。
「非交互」帶來的困惑
非交互式零知識證明，NIZK，如果存在，那么它要比交互式證明強大得多。
交互式證明，只能取信于一個驗證者；而 NIZK 可以取信于多個驗證者，以至所有人。
交互式證明，只能在交互的那個時刻有效；而 NIZK 將始終有效。
NIZK 不僅可以跨越空間，還能跨越時間
聽上去很美，不是嗎？But, ……
重復(fù)下上節(jié)的一個結(jié)論：
通過隨機數(shù)挑戰(zhàn)是交互式零知識證明的「信任根基」。
可是如果 NIZK 失去了挑戰(zhàn)過程，有什么后果？
我們已經(jīng)回憶過「零知識」性質(zhì)的證明（參考『系列二』），證明過程需要構(gòu)造一個模擬器（算法），它也和驗證者（Bob）在理想世界中進行交互，而驗證者 Bob 沒有能力區(qū)分出來對方是否是真的 Alice 還是一個模擬器。
如果現(xiàn)在考慮下 NIZK 中的 非交互式，假如「我」向「你」出示一張紙，上面寫著一個「真」證明 X ，又假如「你」在看過這張紙之后確實相信我了；又因為協(xié)議是「零知識」，那么如果把「我」換成一個模擬器，模擬器也能「偽造」一個假證明 Y，能夠也讓「你」相信。
好了，問題來了：
你如何區(qū)分 X 和 Y ，孰真孰假？當(dāng)然你無法區(qū)分，因為協(xié)議是零知識的，你必須不能區(qū)分
我可以同樣可以把 Y 出示給你看，那豈不是「我」就可以欺騙你了嗎？
是不是不和諧了？請大家在此處思考兩分鐘。
(兩分鐘后……)
因為 NIZK 沒有了交互，也就沒了挑戰(zhàn)過程，所有的證明過程都有 Alice 來計算書寫，理論上 Alice 確實是想寫什么就寫什么，沒人攔得住，比如 Alice 就寫「理想世界」的 假證明 Y。
想必深刻理解模擬器的朋友，在這里會發(fā)現(xiàn)一個關(guān)鍵點：模擬器必須只能在「理想世界」中構(gòu)造Y，也就是說，Y 這么邪惡的東西只能存在于「理想世界」，不能到「現(xiàn)實世界」禍害人間。
繼續(xù)思考……
還有一個更深層次的問題，請大家回憶下「地圖三染色問題」，之所以模擬器不能在「現(xiàn)實世界」中為非作歹，核心原因是，他在理想世界中有「時間倒流」的超能力，而在「現(xiàn)實世界」中不存在這種黑魔法?，F(xiàn)實世界的「不存在性」是關(guān)鍵。
而且，NIZK 中沒有交互，于是導(dǎo)致了一個嚴重的后果，模擬器沒有辦法使用「時間倒流」這個超能力，當(dāng)然似乎也就不能區(qū)分證明者在兩個世界中的行為。
換句話說，如果我們面對任何一個 NIZK 系統(tǒng)，似乎「模擬器」就很難高高在上了，它好像只能飄落人間，成為一個普普通通的凡人。如果，我說如果，按此推論，假設(shè)模擬器不再具備超能力，那就意味著 Alice 和模擬器沒有區(qū)別，Alice 也可以成為一個模擬器，再繼續(xù)推論，Alice 就可以在「現(xiàn)實世界」中任意欺騙 Bob，那么這個證明系統(tǒng)就不再有價值，因為它失去了「可靠性」。結(jié)論：任何的 NIZK 都不可靠。
這一定是哪里出了問題……
上面我們在分析的過程中，提到了交互挑戰(zhàn)的缺失。確實，如果 Bob 不參與 Alice 產(chǎn)生證明的過程，證明所包含的每一個 bit 都由 Alice 提供，似乎「證明」本身不存在任何讓 Bob 信任的「根基」。這個從「直覺」上似乎說不通。
那是不是說，沒有 Bob 的參與就「徹底」沒辦法建立「信任根基」了呢？信任的根基還可以從哪里來呢？
答案是「第三方」！
Wait ……，協(xié)議交互不是只有兩方嗎？ Alice 和 Bob，哪來第三方？
需要用特殊的方式引入第三方，而且方法不止一種，我們先研究第一種。
（淚目：不是說的好好的，咱們不引入第三方嗎？）
回顧 Schnorr 協(xié)議
我們再看一下老朋友——Schnorr 協(xié)議，它是一個三步協(xié)議：第一步，Alice 發(fā)送一個承諾，然后第二步 Bob 發(fā)送隨機數(shù)挑戰(zhàn)，第三步，Alice 回應(yīng)挑戰(zhàn)。
我們來看，如何把一個三步的 Schnorr 協(xié)議變成一步。
看一下 Schnorr 協(xié)議的第二步，Bob 需要給出一個隨機的挑戰(zhàn)數(shù) c，這里我們可以讓 Alice 用下面這個式子來計算這個挑戰(zhàn)數(shù)，從而達到去除協(xié)議第二步的目的。
c = Hash(PK, R)
其中 R 是 Alice 發(fā)給 Bob 的橢圓曲線點，PK 是公鑰。大家可以好好看看這個利用 Hash 算法計算 c 的式子。這個式子達到了兩個目的：
Alice 在產(chǎn)生承諾 R 之前，沒有辦法預(yù)測 c，即使 c 最終變相是 Alice 挑選的
c 通過 Hash 函數(shù)計算，會均勻分布在一個整數(shù)域內(nèi)，而且可以作為一個隨機數(shù)（注：請大家暫且這么理解，我們在后文再深入討論）
請注意：Alice 絕不能在產(chǎn)生 R 之前預(yù)測到 c，不然， Alice 就等于變相具有了「時間倒流」的超能力，從而能任意愚弄 Bob。
而一個密碼學(xué)安全 Hash 函數(shù)是「單向」的，比如 SHA256，SHA3，blake2 等等。這樣一來，雖然 c 是 Alice 計算的，但是 Alice 并沒有能力實現(xiàn)通過挑選 c 來作弊。因為只要 Alice 一產(chǎn)生 R， c 就相當(dāng)于固定下來了。我們假設(shè) Alice 這個凡人在「現(xiàn)實世界」中是沒有反向計算 Hash 的能力的。
看上圖，我們利用 Hash 函數(shù)，把三步 Schnorr 協(xié)議合并為了一步。Alice 可以直接發(fā)送：(R, c, z)。又因為 Bob 擁有 PK，于是 Bob 可以自行計算出 c，于是 Alice 可以只發(fā)送 (R, z) 即可。
我們把上面這個方案稍微變下形，就得到了「數(shù)字簽名」方案。所謂的數(shù)字簽名，就是「我」向「你」出示一個字符串，比如「白日依山盡，黃河入海流」，然后為了證明這句詩是我出示的，我需要簽署某樣?xùn)|西。這個東西能證明我的身份和這句詩進行了關(guān)聯(lián)。
從 NIZK 角度看數(shù)字簽名
不嚴格地說，數(shù)字簽名方案相當(dāng)于在證明（1）我擁有私鑰，并且（2）私鑰和消息進行了關(guān)聯(lián)計算。
我首先要證明我的身份，那么這個簡單，這正是 Schnorr 協(xié)議的功能，能夠向?qū)Ψ阶C明「我擁有私鑰」這個陳述。并且這個證明過程是零知識的：不泄露關(guān)于「私鑰」的任何知識。
那么如何和這句唐詩關(guān)聯(lián)呢？我們修改下計算 c 的過程：
m = "白日依山盡，黃河入海流"
c = Hash(m, R)
這里為了保證攻擊者不能隨意偽造簽名，正是利用了離散對數(shù)難題（DLP）與 Hash 函數(shù)滿足抗第二原象（Secondary Preimage Resistance ）這個假設(shè)。
注：這里嚴格點講，為了保證數(shù)字簽名的不可偽造性，需要證明 Schnorr 協(xié)議滿足「Simulation Soundness」這個更強的性質(zhì)。這點請參考文獻[2]
上圖就是大家所熟知的數(shù)字簽名方案 —— Schnorr 簽名方案[1]。在這里還有一個優(yōu)化，Alice 發(fā)給 Bob 的內(nèi)容不是 (R, z) 而是 (c, z)，這是因為 R 可以通過 c, z 計算出來。
注：為什么說這是一個「優(yōu)化」呢？目前針對橢圓曲線的攻擊方法有 Shanks 算法、Lambda 算法 還有 Pollard's rho 算法， 請大家記住他們的算法復(fù)雜度大約都是 ?[3]，n 是有限域大小的位數(shù)。假設(shè)我們采用了非常接近 2^256 的有限域，也就是說 z 是 256bit，那么橢圓曲線群的大小也差不多要接近 256bit，這樣一來，把 2^256 開平方根后就是 2^128，所以說 256bit 橢圓曲線群的安全性只有 128bit。那么，挑戰(zhàn)數(shù)? c 也只需要 128bit 就足夠了。這樣 Alice 發(fā)送 c 要比發(fā)送 R 要更節(jié)省空間，而后者至少需要 256bit。c 和 z兩個數(shù)值加起來總共 384bit。相比現(xiàn)在流行的 ECDSA 簽名方案來說，可以節(jié)省1/4 的寶貴空間?，F(xiàn)在比特幣開發(fā)團隊已經(jīng)準備將 ECDSA 簽名方案改為一種類 Schnorr 協(xié)議的簽名方案——muSig[4]，可以實現(xiàn)更靈活地支持多簽和聚合。
而采用 Hash 函數(shù)的方法來把一個交互式的證明系統(tǒng)變成非交互式的方法被稱為 Fiat-Shamir 變換[5]，它由密碼學(xué)老前輩 Amos Fiat 和 Adi Shamir 兩人在 1986 年提出。
重建信任 —— 隨機預(yù)言精靈
前文提到，失去了挑戰(zhàn)，似乎失去了證明的「信任根基」。而在 Schnorr 簽名方案中，Hash 函數(shù)擔(dān)負起了「挑戰(zhàn)者」的角色，這個角色有一個非常學(xué)術(shù)的名字：「隨機預(yù)言機」（Random Oracle）[6]。
可是這里為何用 Hash？實際上當(dāng) Alice 要產(chǎn)生公共隨機數(shù)時，需要一個叫做「隨機預(yù)言機」的玩意兒，這是什么？
開腦洞時間到！
我們設(shè)想在「現(xiàn)實世界」中，天上有一位「精靈」，他手持一個雙欄表格，左邊一欄為字符串，右邊一欄為數(shù)字。任何人，包括你我，包括 Alice 和 Bob，都可以發(fā)字符串給「精靈」。
精靈在拿到字符串之后，會查表的左邊欄，看看表格里有沒有這個字符串，下面分兩種情況：
情況一：如果左邊欄找不到字符串，那么精靈會產(chǎn)生一個「真隨機數(shù)」，然后把字符串與隨機數(shù)寫入到表格中，然后把隨機數(shù)返回地面上的凡人。
情況二：如果左邊欄有這個字符串記錄，那么精靈會將右邊欄里面的數(shù)字直接返回給地面。
大家會發(fā)現(xiàn)這個精靈的行為其實很像一個隨機數(shù)發(fā)生器，但是又很不一樣，不一樣的地方在于當(dāng)我們發(fā)送相同的字符串時，他會返回相同的數(shù)。這個精靈就是傳說中的「隨機預(yù)言機」。
而在合并 Schnorr 協(xié)議過程中，其實我們需要的是一個這樣的隨機預(yù)言精靈，而不是一個 Hash 函數(shù)。兩者有什么不同的地方？區(qū)別就是：
隨機預(yù)言機每次對于新字符串返回的是一個具有一致性分布的「真」隨機數(shù)
Hash 函數(shù)計算的結(jié)果并不是一個真正具有一致性分布的隨機數(shù)
那么為什么前面用的是 Hash 函數(shù)呢？這是因為在現(xiàn)實世界中，真正的隨機預(yù)言機不存在！為什么呢？ 事實上，一個 Hash 函數(shù)不可能產(chǎn)生真的隨機數(shù)，因為 Hash 函數(shù)是一個「確定性」算法，除了參數(shù)以外，再沒有其它隨機量被引入。
而一個具有密碼學(xué)安全強度的 Hash 函數(shù)「似乎」可以充當(dāng)一個「偽」隨機預(yù)言機。那么合并后的安全協(xié)議需要額外增加一個很強的安全假設(shè)，這就是：
假設(shè)：一個密碼學(xué)安全的 Hash 函數(shù)可以近似地模擬傳說中的「隨機預(yù)言機」
因為這個假設(shè)無法被證明，所以我們只能信任這個假設(shè)，或者說當(dāng)做一個公理來用。插一句， Hash 函數(shù)的廣義抗碰撞性質(zhì)決定了它的輸出可以模擬隨機數(shù)，同時在很多情況下（并非所有），對 Hash 函數(shù)實施攻擊難度很高，于是許多的密碼學(xué)家都在大膽使用。
不使用這個假設(shè)的安全模型叫做「標準模型」，而使用這個假設(shè)的安全模型當(dāng)然不能叫「非標準模型」，它有個好聽的專有名詞，叫做「隨機預(yù)言模型」。
世界上有兩種不同類型的人，喜歡甜豆花的，不喜歡甜豆花的。同樣，世界上的密碼學(xué)家分為兩種，喜歡隨機預(yù)言模型的，和不喜歡隨機預(yù)言模型的[6]。
構(gòu)造根基 —— 被綁架的精靈
Schnorr 協(xié)議經(jīng)過 Fiat-Shamir? 變換之后，就具有 NIZK 性質(zhì)。這不同于我們證明過的 SHVZK，SHVZK 要求驗證者誠實，而 NIZK 則不再對驗證者有任何不現(xiàn)實的要求，因為驗證者不參與交互，所謂要求誠實的驗證者這個問題就不復(fù)存在。
注：如果驗證者 Bob 不誠實會怎樣？那么 Bob 有可能抽取出 Alice 的知識。但是對于三步 Schnorr 協(xié)議而言，它是否滿足「零知識」，目前還處于未知狀態(tài)。我們在系列三中只證明了它滿足一個比較弱的性質(zhì)：SHVZK。
但是，當(dāng) Schnorr 協(xié)議搖身一變，變成非交互零知識證明系統(tǒng)之后，就真正的「零知識」了。
然而，可能你的問題也來了，這個論斷聽起來似乎有道理，請問能證明嗎？
時間到了，“翠花，上模擬器”
怎么用模擬器大法來構(gòu)造一個「理想世界」呢？大家可以想一下，我們之前使用過「時間倒流」，還有修改「隨機數(shù)傳送帶」超能力來讓「模擬器」來作弊?？墒菦]有交互了，這就意味著：「時間倒流」超能力不能用；Bob 的隨機數(shù)傳送帶也不存在了，「篡改傳送帶」這個超能力也不能用！
但模擬器總要具備某種「超能力」，從而能夠構(gòu)建信任的「根基」
（如果模擬器在沒有超能力的情況下具備作弊能力，那相當(dāng)于證明了協(xié)議的不可靠性）。
可能大家現(xiàn)在已經(jīng)猜出來了，模擬器要在「隨機預(yù)言機」上動手腳。
先考慮下構(gòu)造一個「理想世界」來證明「零知識」。在理想世界中，模擬器「綁架」了負責(zé)提供預(yù)言的「精靈」，當(dāng) Bob 向精靈索要一個隨機數(shù)的時候，精靈并沒有給一個真隨機數(shù)，而是給 Zlice（模擬器假扮的 Alice）提前準備好的一個數(shù)（也符合一致性分布，保證不可區(qū)分性），「精靈」無可奈何地返回 Bob 一個看起來隨機，但實際上有后門的數(shù)字。所謂后門，就是這個數(shù)字是 Zlice 自己提前選擇好的。
第一步：Zlice 隨機選擇 z，隨機選擇c，計算 R'=z*G - c*PK 。
第二步：Zlice 將 c 與 (m, R') 寫入精靈的表格。
第三步：Zlice 將簽名 (c, z) 發(fā)送給 Bob。
第四步：Bob 計算 R=z*G - c*PK，并向精靈發(fā)送 (m, R)，精靈返回 c’。請注意，這里 Bob 計算出來的 R 和 Zlice 計算出來的 R' 是相等。
第五步：Bob 驗證 c ?= c'，看看精靈傳回來的隨機數(shù)和對方發(fā)過來的隨機數(shù)是否相等。如果相等，則驗證簽名通過；否則，則驗證失敗。
通過綁架「精靈」，Zlice 同樣可以提前預(yù)知隨機數(shù)，這和時間倒流能達到同樣的效果。
我們已經(jīng)證明了模擬器 Zlice 的「存在性」，于是我們上面已經(jīng)證明了 NIZK。
接下來我們證明這個這個協(xié)議的「可靠性」。設(shè)想在另一個「理想世界」中，一個叫做「抽取器」的玩意兒，也同樣綁架了精靈。當(dāng)無辜 Alice 的向「精靈」索要一個隨機數(shù)時，「精靈」返回了一個 c1，「抽取器」從精靈的表格中偷窺到了c1，當(dāng) Alice 計算出來 z1 之后，然后這時候「抽取器」仍然可以發(fā)動「時間倒流」超能力，讓 Alice 倒退到第二步，再次向「精靈」要一個隨機數(shù)，Alice 發(fā)送的字符串顯然和第一次發(fā)送的字符串是相同的，(R, m)。按道理，因為 (R, m) 已經(jīng)寫在精靈表格的「左欄」里，所以一個誠實的「精靈」應(yīng)該返回 c1。但是，「抽取器」綁架了精靈，他把表格中對應(yīng) (R, m) 這一行的「右欄」改成了一個不同的數(shù) c2。當(dāng) Alice 計算出另一個 z2 之后，抽取器就完成了任務(wù)，通過下面的方程計算出 Alice 的私鑰 sk：
sk = (z1 - z2)/(c1 - c2)
Fiat-Shamir 變換 —— 從 Public-Coin 到 NIZK
不僅僅對于 Schnorr 協(xié)議，對于任意的 「Public-Coin 協(xié)議」，都可以用 Fiat-Shamir 變換來把整個協(xié)議「壓縮」成一步交互，也就是一個非交互式的證明系統(tǒng)，這個變換技巧最早來自于 Amos Fiat 與 Adi Shamir 兩人的論文『How to Prove Yourself: Practical Solutions to Identification and Signature Problems.』，發(fā)表在 1986 年的 Crypto 會議上[5]。也有一說，這個技巧來源于 Manuel Blum[6].
重復(fù)一遍，在 Public-coin 協(xié)議中，驗證者 Bob 只做一類事情，就是產(chǎn)生一個隨機數(shù)，然后挑戰(zhàn) Alice 。通過 Fiat-Shamir 變換，可以把 Bob 每一次的「挑戰(zhàn)行為」用一次「隨機預(yù)言」來代替。
而在具體實現(xiàn)中，隨機預(yù)言需要用一個具有密碼學(xué)安全強度的 Hash 函數(shù)（不能隨便選，一定要采用密碼學(xué)安全的 Hash），而 Hash 函數(shù)的參數(shù)應(yīng)該是之前所有的上下文輸入。下面是一個示例圖，大家可以迅速理解這個 Fiat-Shamir 變換的做法。
前面提到，在非交互式證明系統(tǒng)中，需要引入一個第三方來構(gòu)建信任的「根基」，使得 Bob 可以完全相信由 Alice 所構(gòu)造的證明。在這里，第三方就是那個「精靈」，用學(xué)術(shù)黑話就是「隨機預(yù)言」（Random Oracle）。這個精靈并不是一個真實存在的第三方，而是一個虛擬的第三方，它同時存在于「現(xiàn)實世界」與「理想世界」。在「現(xiàn)實世界」中，精靈是一個負責(zé)任的安靜美男子，而在「理想世界」中，它會被「模擬器」綁架。
Public-Coin 協(xié)議還有一個好聽的名字， 「Arthur-Merlin 游戲」 ……
看上圖，左邊的“白袍”就是 Merlin（魔法師梅林），中間拿劍的帥哥就是 King Arthur（亞瑟王），兩個角色來源于中世紀歐洲傳說——亞瑟王的圓桌騎士。
Arthur 是一個不耐煩的國王，他隨身攜帶一個硬幣，而 Merlin是一個有著無限制計算能力的神奇魔法師，然后魔法師想說服國王相信某個「論斷」為真，于是魔法師會和國王進行到對話，但是由于國王比較懶，他每次只會拋一個硬幣，然后「挑戰(zhàn)」魔法師，而魔法師需要及時應(yīng)對，而且需要讓國王在 k 輪之后能夠相信自己的論斷。由于 Merlin 有魔法，所以亞瑟王拋的硬幣都能被 Merlin 看到[7]。
這與我們在『系列一』中提到的交互式證明系統(tǒng)（Interactive Proof System，簡稱 IP）有些神似，但又不同。IP 由 Goldwasser，Micali 與 Rackoff（簡稱GMR）在 1985 年正式提出，它的證明能力覆蓋很大一類的計算復(fù)雜性問題。而不同的地方在于：在 IP 的定義中，證明者 Prover 和 驗證者 Verifier 都是可以拋硬幣的圖靈機，Verifier 可以偷偷拋硬幣，并對 Prover 隱藏；而在 Arthur-Merlin 游戲中，國王只能拋硬幣，不僅如此，而且拋硬幣的結(jié)果總會被 Merlin 知道。
但是，F(xiàn)iat-Shamir 變換只能在「隨機預(yù)言模型」下證明安全，而用 Hash 函數(shù)實現(xiàn)隨機預(yù)言的過程是否安全是缺少安全性證明的。不僅如此，「隨機預(yù)言模型」下安全的協(xié)議可能是有不安全的，已經(jīng)有人找到了一些反例[8]；更不幸的是，S. Goldwasser 與 Y. Tauman 在 2003 年證明了 Fiat-Shamir 變換本身也是存在安全反例的[9]。但是這并不意味著 Fiat-Shamir 變換不能用，只是在使用過程中要非常小心，不能盲目套用。
盡管如此，人們無法抵擋 Fiat-Shamir 變換的誘惑，其使用極其廣泛。值得一提的是，最熱的通用非交互零知識證明 zkSNARK 的各種方案中，F(xiàn)iat-Shamir 變換比比皆是。比如大家可能耳熟能詳?shù)?Bulletproofs（子彈證明），此外還有一些暫時還不那么有名的通用零知識證明方案，比如 Hyrax，Ligero，Supersonic，Libra 等（我們后續(xù)會抽絲剝繭，逐一解讀）。
小心：Fiat-Shamir 變換中的安全隱患
在 Fiat-Shamir 變換中，要尤其注意喂給 Hash 函數(shù)的參數(shù)，在實際的代碼實現(xiàn)中，就有這樣的案例，漏掉了 Hash 函數(shù)的部分參數(shù)：
比如在 A, Hash(A), B, Hash(B) 中，第二個 Hash 函數(shù)就漏掉了參數(shù)A，正確的做法應(yīng)該是A, Hash(A), B, Hash(A,B)。這一類的做法會引入嚴重的安全漏洞，比如在瑞士的電子投票系統(tǒng) SwissPost-Scytl 中，就在 Fiat-Shamir 變換的實現(xiàn)代碼中多次漏掉了本來應(yīng)該存在的參數(shù)，導(dǎo)致了攻擊者不僅可以隨意作廢選票，還可以任意偽造選票，達到舞弊的目的[10]。因此在工程實現(xiàn)中，請務(wù)必注意。
細心讀者也許會回看一下 Schnorr 簽名，大家會發(fā)現(xiàn) Schnorr 簽名中的 Hash 算法似乎也漏掉了一個參數(shù) PK，并不是嚴格的 Fiat-Shamir 變換，這被稱為 Weak Fiat-Shamir 變換[11]，不過這個特例并沒有安全問題[3]，請未成年人不要隨意模仿。
最近一些學(xué)者開始在標準模型下研究如何嚴格證明 Fiat-Shamir 變換的安全性，目前要么引入額外的強安全假設(shè)，要么針對某個特定協(xié)議進行證明，但似乎進展并不大。
交互的威力
話說在1985年，當(dāng) GMR 三人的論文歷經(jīng)多次被拒之后終于被 STOC’85 接受，另一篇類似的工作也同時被 STOC'85 接受，這就是來自于匈牙利羅蘭大學(xué)的 László Babai，與來自以色列理工的 Shlomo Moran 兩人撰寫的論文『Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes』[7]，引入了 Public-coin 交互式協(xié)議（顧名思義，Verifier 只公開拋硬幣）。
國王 Arthur 的方法很簡單，通過反復(fù)地「隨機」挑戰(zhàn)來檢驗 Merlin 的論斷，這符合我們前面講述過的直覺：采用隨機挑戰(zhàn)來構(gòu)建信任的「根基」。Babai 在論文中證明了一個有趣的結(jié)論：AM[k]=AM[2]，其中 k 表示交互的次數(shù)，交互多次產(chǎn)生的效果居然和交互兩次等價。所謂交互兩次是指：Arthur 發(fā)一個挑戰(zhàn)數(shù)，然后 Merlin 回應(yīng)。
注：還有一類的問題屬于 MA，這一類問題的交互順序與 AM不同，MA中是 Merlin 先給出證明，然后 Arthur 拋硬幣檢驗。已證明：MA 能處理的問題是 AM 的子集。
不僅如此，Babai 還大膽猜測： AM[poly] 與 IP 是等價的。這是一個神奇的論斷：國王很懶，他只需要通過拋多項式次硬幣，就能成功挑戰(zhàn)魔法師，而這種方式的表達能力居然完全等價于 GMR 描述的交互式證明系統(tǒng) IP。果不其然，在 STOC'86 會議上，來自 S. Goldwasser 與 M. Sipser 的論文證明了這一點，AM[poly] == IP[12]。
這意味著：反復(fù)公開的「隨機挑戰(zhàn)」威力無窮，它等價于任意的交互式證明系統(tǒng)。但是 AM[poly] 和別的計算復(fù)雜性類的關(guān)系如何，是接下來的研究熱點。
三年后，1989 年11月底，距今恰好三十年，年輕的密碼學(xué)家 Noam Nisan 發(fā)出了一封郵件，把自己的臨時學(xué)術(shù)結(jié)論發(fā)給了幾個密碼學(xué)家，然后他就跑去南美洲度假了?？墒撬辉氲?，這一個郵件會引爆歷史上一場激烈的學(xué)術(shù)競賽，M. Blum, S. Kannan, D. Lipton, D. Beaver, J. Feigenbaum, H. Karloff, C. Lund 等等一大群精英開始加入戰(zhàn)斗，他們沒日沒夜地互相討論，并且競相發(fā)布自己的研究成果，終于在12月26號，剛好一個月，Adi Shamir 證明了下面的結(jié)論：
AM[poly] == IP == PSPACE
它解釋了「有效證明」這個概念的計算理論特征，并且解釋了「交互式證明系統(tǒng)」這個概念所能涵蓋的計算能力。
注：NP 類 是 PSPACE 類的子集，前者大家比較熟悉，后者關(guān)聯(lián)游戲或者下棋中的制勝策略[13]。
而 L. Babai 于是寫了一篇文章，名為「Email and the unexpected power of interaction」（電子郵件與交互的始料未及的威力）[14]，詳細闡述了這一整個月在「郵件交互」中精彩紛呈的學(xué)術(shù)競賽，以及關(guān)于「交互證明」的來龍去脈。
公共參考串 —— 另一種「信任根基」
除了采用「隨機預(yù)言機」之外，非交互零知識證明系統(tǒng)采用「公共參考串」（Common Reference String），簡稱「CRS」，完成隨機挑戰(zhàn)。它是在證明者 Alice 在構(gòu)造 NIZK 證明之前由一個受信任的第三方產(chǎn)生的隨機字符串，CRS 必須由一個受信任的第三方來完成，同時共享給 Alice 和 驗證者 Bob。
是的，你沒看錯，這里又出現(xiàn)了「第三方」！雖然第三方不直接參與證明，但是他要保證隨機字符串產(chǎn)生過程的可信。而產(chǎn)生 CRS 的過程也被稱為「Trusted Setup」，這是大家又愛又恨的玩意兒。顯然，在現(xiàn)實場景中引入第三方會讓人頭疼。CRS 到底用來做什么？Trusted Setup 的信任何去何從？這部分內(nèi)容將留給本系列的下一篇。
未完待續(xù)
非交互式零知識證明 NIZK 的「信任根基」也需要某種形式的隨機「挑戰(zhàn)」，一種「挑戰(zhàn)」形式是交給「隨機預(yù)言精靈」；另一種「挑戰(zhàn)」是通過 Alice 與 Bob 雙方共享的隨機字符串來實現(xiàn)。兩種挑戰(zhàn)形式本質(zhì)上都引入了第三方，并且兩者都必須提供可以讓「模擬器」利用的「后門」，以使得讓模擬器在「理想世界」中具有某種「優(yōu)勢」，而這種優(yōu)勢在「現(xiàn)實世界」中必須失效。
NIZK 散發(fā)著無窮魅力，讓我不時驚嘆，在過去三十多年里，先驅(qū)們所探尋到的精妙結(jié)論，同時還有如此之多的未知角落，在等待靈感之光的照射。
本系列文章在 Github 上的項目倉庫收到了第一個 Pull Request，來自Jingyu Hu(colortigerhu)，只改了個把字，但那一瞬間，我感受到了生命力。知識交流，思想碰撞，很迷人，不是嗎？
“Everyone we interact with becomes a part of us.”? 與我們交往互動的每一個人都是我們自身的一部分。 ― Jodi Aman
*致謝：特別感謝丁晟超，劉巍然，陳宇的專業(yè)建議和指正，感謝安比實驗室小伙伴們(p0n1, even, aphasiayc, Vawheter, yghu, mr) 的修改建議。
致謝：自Nisan發(fā)起的密碼學(xué)研究軼事參考自鄧老師的文章[15]。
本文首發(fā)于微信公眾號：安比實驗室，進群討論零知識證明可添加微信 secbit_xiaoanbi
參考文獻
[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
