本文來自本文來自本文來自
安比實驗室（ID：SECBIT）
https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/4/zkp-rom.md
本文已更新至Github
，作者郭宇，Odaily經授權轉載。
本文繼續長篇大論零知識證明背後的機制原理，希望幫助大家理解這一類「現代密碼學工具」的大致輪廓。本文約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 協議
c = Hash(PK, R)
我們再看一下老朋友——Schnorr 協議，它是一個三步協議：第一步，Alice 發送一個承諾，然後第二步Bob 發送隨機數挑戰，第三步，Alice 回應挑戰。
我們來看，如何把一個三步的Schnorr 協議變成一步。
看一下Schnorr 協議的第二步，Bob 需要給出一個隨機的挑戰數c，這裡我們可以讓Alice 用下面這個式子來計算這個挑戰數，從而達到去除協議第二步的目的。
其中R 是Alice 發給Bob 的橢圓曲線點，PK 是公鑰。大家可以好好看看這個利用Hash 算法計算c 的式子。這個式子達到了兩個目的：
Alice 在產生承諾R 之前，沒有辦法預測c，即使c 最終變相是Alice 挑選的
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 角度看數字簽名
m = "不嚴格地說，數字簽名方案相當於在證明（1）我擁有私鑰，並且（2）私鑰和消息進行了關聯計算。"
c = Hash(m, R)
我首先要證明我的身份，那麼這個簡單，這正是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 算法， 請大家記住他們的算法複雜度大約都是[3]，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[4]，可以實現更靈活地支持多籤和聚合。
而採用Hash 函數的方法來把一個交互式的證明系統變成非交互式的方法被稱為Fiat-Shamir 變換[5]，它由密碼學老前輩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'，看看精靈傳回來的隨機數和對方發過來的隨機數是否相等。如果相等，則驗證簽名通過；否則，則驗證失敗。
sk = (z1 - z2)/(c1 - c2)
通過綁架「精靈」，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 遊戲」 ……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 函數的部分參數：
細心讀者也許會回看一下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 的子集。
AM[poly] == IP == PSPACE
不僅如此，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 證明了下面的結論：
它解釋了「有效證明」這個概念的計算理論特徵，並且解釋了「交互式證明系統」這個概念所能涵蓋的計算能力。
注：NP 類是PSPACE 類的子集，前者大家比較熟悉，後者關聯遊戲或者下棋中的製勝策略[13]。
是的，你沒看錯，這裡又出現了「第三方」！雖然第三方不直接參與證明，但是他要保證隨機字符串產生過程的可信。而產生CRS 的過程也被稱為「Trusted Setup」，這是大家又愛又恨的玩意兒。顯然，在現實場景中引入第三方會讓人頭疼。 CRS 到底用來做什麼？ Trusted Setup 的信任何去何從？這部分內容將留給本系列的下一篇。
未完待續
未完待續
未完待續
未完待續非交互式零知識證明NIZK 的「信任根基」也需要某種形式的隨機「挑戰」，一種「挑戰」形式是交給「隨機預言精靈」；另一種「挑戰」是通過Alice 與Bob 雙方共享的隨機字符串來實現。兩種挑戰形式本質上都引入了第三方，並且兩者都必須提供可以讓「模擬器」利用的「後門」，以使得讓模擬器在「理想世界」中具有某種「優勢」，而這種優勢在「現實世界」中必須失效。NIZK 散發著無窮魅力，讓我不時驚嘆，在過去三十多年裡，先驅們所探尋到的精妙結論，同時還有如此之多的未知角落，在等待靈感之光的照射。
本系列文章在Github 上的
正文
正文
參考文獻
[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
