亞瑟王的「隨機」挑戰：從交互到非交互式零知識證明——探索零知識證明系列（四）_LIC:ALICE

本文來自安比實驗室，作者郭宇，Odaily星球日報經授權轉載。

本文已更新至Githubhttps://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/4/zkp-rom.md“ChallengesareattimesanindicationofLord'strustinyou.”挑戰，有時是上天信任你的一種表現。―D.ToddChristofferson本文繼續長篇大論零知識證明背后的機制原理，希望幫助大家理解這一類「現代密碼學工具」的大致輪廓。本文約8000字，少量數學公式。系列一：初識「零知識」與「證明」系列二：理解「模擬」系列三：尋找「知識」交互與挑戰

我們之前介紹的零知識證明系統都是「交互式」的，需要驗證者Bob在交互中提供一個或若干個「隨機數」來挑戰，比如「地圖三染色問題」中，驗證者Bob需要「不斷地」隨機挑選一條邊來挑戰Alice的答案，直到Bob滿意為止，而Alice的作弊概率會「指數級」地衰減。而讓Bob相信證明的「基礎」取決于Bob所挑選的隨機數是不是足夠隨機。如果Alice能夠提前預測到Bob的隨機數，災難就會發生，現實世界就會退化成「理想世界」，而Alice就可以立即升級成「模擬器」，通過超能力來愚弄Bob。而『系列三』中，我們分析了Schnorr協議，協議中雖然驗證者Bob只需要挑選一個隨機數c來挑戰Alice，讓她計算一個值z，但Bob絕對不能讓Alice有能力來預測到c的任何知識，否則，Alice也會變身成模擬器。隨機數的重要性不言而喻：通過隨機數挑戰是交互式零知識證明的「信任根基」。但，「交互過程」會限制應用場景。如果能將交互式零知識證明變成「非交互」？這會非常非常激動人心。所謂的非交互可以看成是只有「一輪」的證明過程，即Alice直接發一個證明給Bob進行驗證。非交互式零知識證明，英文是Non-InteractiveZeroKnowledge，簡稱NIZK。它意味整個證明被編碼為一個「字符串」，它可以寫到一張紙上，通過郵件、聊天工具等各種方式隨意發送給任何驗證者，字符串甚至可以放在Github上隨時供大家下載驗證。在區塊鏈世界，「NIZK」可以作為共識協議的一部分。因為一個交易需要多個礦工進行校驗。設想下，如果交易的發送者和每個礦工都要交互一下，讓礦工進行挑戰，那么共識過程將奇慢無比。而非交互式零知識證明則可以直接廣播給所有的礦工節點，讓他們自行驗證。可能有朋友會問：只讓一個礦工挑戰不就夠了嗎？把礦工和交易發送者的交互腳本編碼成證明，然后廣播給其他礦工，然后其他礦工就直接相信這個挑戰過程是可信的，不也可以嗎？但是，很顯然，這里需要相信第一個交互礦工作為可信第三方，第三方？似乎不是一個好主意……而非交互式零知識證明，以下我們直接說「NIZK」，似乎就很理想了，沒有第三方賺差價。「非交互」帶來的困惑

非交互式零知識證明，NIZK，如果存在，那么它要比交互式證明強大得多。交互式證明，只能取信于一個驗證者；而NIZK可以取信于多個驗證者，以至所有人。交互式證明，只能在交互的那個時刻有效；而NIZK將始終有效。NIZK不僅可以跨越空間，還能跨越時間聽上去很美，不是嗎？But,……重復下上節的一個結論：通過隨機數挑戰是交互式零知識證明的「信任根基」。可是如果NIZK失去了挑戰過程，有什么后果？我們已經回憶過「零知識」性質的證明，證明過程需要構造一個模擬器，它也和驗證者在理想世界中進行交互，而驗證者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協議

Y2K Finance推出Touch金庫，用戶可預測交易CRV是否跌至0.4美元:8月3日消息，基于Arbitrum的資產脫鉤風險定價協議Y2K Finance推出Touch金庫，目前已上線代幣CRV，用戶可預測交易CRV是否跌至0.4美元，其中用戶可在一輪周期結束時預測CRV價格是否會降至0.4美元，如CRV彼時降至0.4美元，抵押方將向保險方支付保費。[2023/8/3 16:15:43]

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

我們來看，如何把一個三步的Schnorr協議變成一步。看一下Schnorr協議的第二步，Bob需要給出一個隨機的挑戰數c，這里我們可以讓Alice用下面這個式子來計算這個挑戰數，從而達到去除協議第二步的目的。c=Hash(PK,R)其中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角度看數字簽名

不嚴格地說，數字簽名方案相當于在證明我擁有私鑰，并且私鑰和消息進行了關聯計算。我首先要證明我的身份，那么這個簡單，這正是Schnorr協議的功能，能夠向對方證明「我擁有私鑰」這個陳述。并且這個證明過程是零知識的：不泄露關于「私鑰」的任何知識。那么如何和這句唐詩關聯呢？我們修改下計算c的過程：m="白日依山盡，黃河入海流"c=Hash(m,R)這里為了保證攻擊者不能隨意偽造簽名，正是利用了離散對數難題與Hash函數滿足抗第二原象這個假設。注：這里嚴格點講，為了保證數字簽名的不可偽造性，需要證明Schnorr協議滿足「SimulationSoundness」這個更強的性質。這點請參考文獻

上圖就是大家所熟知的數字簽名方案——Schnorr簽名方案。在這里還有一個優化，Alice發給Bob的內容不是(R,z)而是(c,z)，這是因為R可以通過c,z計算出來。注：為什么說這是一個「優化」呢？目前針對橢圓曲線的攻擊方法有Shanks算法、Lambda算法還有Pollard'srho算法，請大家記住他們的算法復雜度大約都是，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，可以實現更靈活地支持多簽和聚合。而采用Hash函數的方法來把一個交互式的證明系統變成非交互式的方法被稱為Fiat-Shamir變換，它由密碼學老前輩AmosFiat和AdiShamir兩人在1986年提出。重建信任——隨機預言精靈

Alameda欠Celsius 1200萬美元未償貸款:金色財經報道，已破產的加密借貸平臺Celsius Network周二告訴法庭，它向Alameda Research提供了1200萬美元的貸款，這給試圖收回存款的Celsius債權人增加了另一個障礙。Celsius新任首席執行官Chris Ferraro表示，該公司過去面臨的風險要大得多。例如，2020年1月，Celsius在FTX Group的總敞口為36億美元。但在今年早些時候申請破產保護之前，它立即將風險敞口削減至3.54億美元。Ferraro還表示，Celsius正在通過質押部署及其挖礦業務產生“適度的收入”，Celsius Mining擁有大約40,000臺采礦設備。[2022/11/16 13:10:02]

前文提到，失去了挑戰，似乎失去了證明的「信任根基」。而在Schnorr簽名方案中，Hash函數擔負起了「挑戰者」的角色，這個角色有一個非常學術的名字：「隨機預言機」。可是這里為何用Hash？實際上當Alice要產生公共隨機數時，需要一個叫做「隨機預言機」的玩意兒，這是什么？開腦洞時間到！我們設想在「現實世界」中，天上有一位「精靈」，他手持一個雙欄表格，左邊一欄為字符串，右邊一欄為數字。任何人，包括你我，包括Alice和Bob，都可以發字符串給「精靈」。

精靈在拿到字符串之后，會查表的左邊欄，看看表格里有沒有這個字符串，下面分兩種情況：情況一：如果左邊欄找不到字符串，那么精靈會產生一個「真隨機數」，然后把字符串與隨機數寫入到表格中，然后把隨機數返回地面上的凡人。情況二：如果左邊欄有這個字符串記錄，那么精靈會將右邊欄里面的數字直接返回給地面。大家會發現這個精靈的行為其實很像一個隨機數發生器，但是又很不一樣，不一樣的地方在于當我們發送相同的字符串時，他會返回相同的數。這個精靈就是傳說中的「隨機預言機」。而在合并Schnorr協議過程中，其實我們需要的是一個這樣的隨機預言精靈，而不是一個Hash函數。兩者有什么不同的地方？區別就是：隨機預言機每次對于新字符串返回的是一個具有一致性分布的「真」隨機數Hash函數計算的結果并不是一個真正具有一致性分布的隨機數那么為什么前面用的是Hash函數呢？這是因為在現實世界中，真正的隨機預言機不存在！為什么呢？事實上，一個Hash函數不可能產生真的隨機數，因為Hash函數是一個「確定性」算法，除了參數以外，再沒有其它隨機量被引入。而一個具有密碼學安全強度的Hash函數「似乎」可以充當一個「偽」隨機預言機。那么合并后的安全協議需要額外增加一個很強的安全假設，這就是：假設：一個密碼學安全的Hash函數可以近似地模擬傳說中的「隨機預言機」因為這個假設無法被證明，所以我們只能信任這個假設，或者說當做一個公理來用。插一句，Hash函數的廣義抗碰撞性質決定了它的輸出可以模擬隨機數，同時在很多情況下，對Hash函數實施攻擊難度很高，于是許多的密碼學家都在大膽使用。不使用這個假設的安全模型叫做「標準模型」，而使用這個假設的安全模型當然不能叫「非標準模型」，它有個好聽的專有名詞，叫做「隨機預言模型」。世界上有兩種不同類型的人，喜歡甜豆花的，不喜歡甜豆花的。同樣，世界上的密碼學家分為兩種，喜歡隨機預言模型的，和不喜歡隨機預言模型的。構造根基——被綁架的精靈

Schnorr協議經過Fiat-Shamir變換之后，就具有NIZK性質。這不同于我們證明過的SHVZK，SHVZK要求驗證者誠實，而NIZK則不再對驗證者有任何不現實的要求，因為驗證者不參與交互，所謂要求誠實的驗證者這個問題就不復存在。注：如果驗證者Bob不誠實會怎樣？那么Bob有可能抽取出Alice的知識。但是對于三步Schnorr協議而言，它是否滿足「零知識」，目前還處于未知狀態。我們在系列三中只證明了它滿足一個比較弱的性質：SHVZK。但是，當Schnorr協議搖身一變，變成非交互零知識證明系統之后，就真正的「零知識」了。然而，可能你的問題也來了，這個論斷聽起來似乎有道理，請問能證明嗎？時間到了，“翠花，上模擬器”怎么用模擬器大法來構造一個「理想世界」呢？大家可以想一下，我們之前使用過「時間倒流」，還有修改「隨機數傳送帶」超能力來讓「模擬器」來作弊。可是沒有交互了，這就意味著：「時間倒流」超能力不能用；Bob的隨機數傳送帶也不存在了，「篡改傳送帶」這個超能力也不能用！但模擬器總要具備某種「超能力」，從而能夠構建信任的「根基」。可能大家現在已經猜出來了，模擬器要在「隨機預言機」上動手腳。先考慮下構造一個「理想世界」來證明「零知識」。在理想世界中，模擬器「綁架」了負責提供預言的「精靈」，當Bob向精靈索要一個隨機數的時候，精靈并沒有給一個真隨機數，而是給Zlice提前準備好的一個數，「精靈」無可奈何地返回Bob一個看起來隨機，但實際上有后門的數字。所謂后門，就是這個數字是Zlice自己提前選擇好的。

灰度比特幣信托負溢價率達28.5%:金色財經消息，Tokenview鏈上數據顯示，當前灰度總持倉量達200.76 億美元，主流幣種信托溢價率如下：

BTC，-28.5%；

ETH，-24.85%；

ETC，-58.34%；

LTC, -42.99%；

BCH，-10.62%。[2022/7/21 2:27:36]

第一步：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變換來把整個協議「壓縮」成一步交互，也就是一個非交互式的證明系統，這個變換技巧最早來自于AmosFiat與AdiShamir兩人的論文『HowtoProveYourself:PracticalSolutionstoIdentificationandSignatureProblems.』，發表在1986年的Crypto會議上。也有一說，這個技巧來源于ManuelBlum.重復一遍，在Public-coin協議中，驗證者Bob只做一類事情，就是產生一個隨機數，然后挑戰Alice。通過Fiat-Shamir變換，可以把Bob每一次的「挑戰行為」用一次「隨機預言」來代替。而在具體實現中，隨機預言需要用一個具有密碼學安全強度的Hash函數，而Hash函數的參數應該是之前所有的上下文輸入。下面是一個示例圖，大家可以迅速理解這個Fiat-Shamir變換的做法。

前面提到，在非交互式證明系統中，需要引入一個第三方來構建信任的「根基」，使得Bob可以完全相信由Alice所構造的證明。在這里，第三方就是那個「精靈」，用學術黑話就是「隨機預言」。這個精靈并不是一個真實存在的第三方，而是一個虛擬的第三方，它同時存在于「現實世界」與「理想世界」。在「現實世界」中，精靈是一個負責任的安靜美男子，而在「理想世界」中，它會被「模擬器」綁架。Public-Coin協議還有一個好聽的名字，「Arthur-Merlin游戲」……

看上圖，左邊的“白袍”就是Merlin，中間拿劍的帥哥就是KingArthur，兩個角色來源于中世紀歐洲傳說——亞瑟王的圓桌騎士。Arthur是一個不耐煩的國王，他隨身攜帶一個硬幣，而Merlin是一個有著無限制計算能力的神奇魔法師，然后魔法師想說服國王相信某個「論斷」為真，于是魔法師會和國王進行到對話，但是由于國王比較懶，他每次只會拋一個硬幣，然后「挑戰」魔法師，而魔法師需要及時應對，而且需要讓國王在k輪之后能夠相信自己的論斷。由于Merlin有魔法，所以亞瑟王拋的硬幣都能被Merlin看到。這與我們在『系列一』中提到的交互式證明系統有些神似，但又不同。IP由Goldwasser，Micali與Rackoff在1985年正式提出，它的證明能力覆蓋很大一類的計算復雜性問題。而不同的地方在于：在IP的定義中，證明者Prover和驗證者Verifier都是可以拋硬幣的圖靈機，Verifier可以偷偷拋硬幣，并對Prover隱藏；而在Arthur-Merlin游戲中，國王只能拋硬幣，不僅如此，而且拋硬幣的結果總會被Merlin知道。但是，Fiat-Shamir變換只能在「隨機預言模型」下證明安全，而用Hash函數實現隨機預言的過程是否安全是缺少安全性證明的。不僅如此，「隨機預言模型」下安全的協議可能是有不安全的，已經有人找到了一些反例；更不幸的是，S.Goldwasser與Y.Tauman在2003年證明了Fiat-Shamir變換本身也是存在安全反例的。但是這并不意味著Fiat-Shamir變換不能用，只是在使用過程中要非常小心，不能盲目套用。盡管如此，人們無法抵擋Fiat-Shamir變換的誘惑，其使用極其廣泛。值得一提的是，最熱的通用非交互零知識證明zkSNARK的各種方案中，Fiat-Shamir變換比比皆是。比如大家可能耳熟能詳的Bulletproofs，此外還有一些暫時還不那么有名的通用零知識證明方案，比如Hyrax，Ligero，Supersonic，Libra等。小心：Fiat-Shamir變換中的安全隱患

加密金融公司Matrixport推出NFT機構托管服務:6月27日消息，吳忌寒旗下加密金融公司Matrixport宣布通過第三方機構托管服務Cactus Custody推出NFT機構托管業務，幫助機構安全存儲和管理其NFT和加密資產。

據Matrixport首席運營官Cynthia Wu稱，Cactus Custody正在加強基礎設施和工具，NFT資產管理產品將嵌入風險管理功能，機構能夠自定義用戶訪問控制和dApp智能合約白名單，只有獲得批準的NFT市場、DeFi、GameFi、SocialFi和Web3協議才能與平臺上的錢包進行交互，保護數字資產免受惡意行為者的侵害。（美通社）[2022/6/27 1:33:33]

在Fiat-Shamir變換中，要尤其注意喂給Hash函數的參數，在實際的代碼實現中，就有這樣的案例，漏掉了Hash函數的部分參數：比如在A,Hash(A),B,Hash(B)中，第二個Hash函數就漏掉了參數A，正確的做法應該是A,Hash(A),B,Hash(A,B)。這一類的做法會引入嚴重的安全漏洞，比如在瑞士的電子投票系統SwissPost-Scytl中，就在Fiat-Shamir變換的實現代碼中多次漏掉了本來應該存在的參數，導致了攻擊者不僅可以隨意作廢選票，還可以任意偽造選票，達到舞弊的目的。因此在工程實現中，請務必注意。細心讀者也許會回看一下Schnorr簽名，大家會發現Schnorr簽名中的Hash算法似乎也漏掉了一個參數PK，并不是嚴格的Fiat-Shamir變換，這被稱為WeakFiat-Shamir變換，不過這個特例并沒有安全問題，請未成年人不要隨意模仿。最近一些學者開始在標準模型下研究如何嚴格證明Fiat-Shamir變換的安全性，目前要么引入額外的強安全假設，要么針對某個特定協議進行證明，但似乎進展并不大。交互的威力

話說在1985年，當GMR三人的論文歷經多次被拒之后終于被STOC’85接受，另一篇類似的工作也同時被STOC'85接受，這就是來自于匈牙利羅蘭大學的LászlóBabai，與來自以色列理工的ShlomoMoran兩人撰寫的論文『Arthur-MerlinGames:ARandomizedProofSystem,andaHierarchyofComplexityClasses』，引入了Public-coin交互式協議。國王Arthur的方法很簡單，通過反復地「隨機」挑戰來檢驗Merlin的論斷，這符合我們前面講述過的直覺：采用隨機挑戰來構建信任的「根基」。Babai在論文中證明了一個有趣的結論：AM=AM，其中k表示交互的次數，交互多次產生的效果居然和交互兩次等價。所謂交互兩次是指：Arthur發一個挑戰數，然后Merlin回應。注：還有一類的問題屬于MA，這一類問題的交互順序與AM不同，MA中是Merlin先給出證明，然后Arthur拋硬幣檢驗。已證明：MA能處理的問題是AM的子集。不僅如此，Babai還大膽猜測：AM與IP是等價的。這是一個神奇的論斷：國王很懶，他只需要通過拋多項式次硬幣，就能成功挑戰魔法師，而這種方式的表達能力居然完全等價于GMR描述的交互式證明系統IP。果不其然，在STOC'86會議上，來自S.Goldwasser與M.Sipser的論文證明了這一點，AM==IP。

這意味著：反復公開的「隨機挑戰」威力無窮，它等價于任意的交互式證明系統。但是AM和別的計算復雜性類的關系如何，是接下來的研究熱點。三年后，1989年11月底，距今恰好三十年，年輕的密碼學家NoamNisan發出了一封郵件，把自己的臨時學術結論發給了幾個密碼學家，然后他就跑去南美洲度假了。可是他不曾想到，這一個郵件會引爆歷史上一場激烈的學術競賽，M.Blum,S.Kannan,D.Lipton,D.Beaver,J.Feigenbaum,H.Karloff,C.Lund等等一大群精英開始加入戰斗，他們沒日沒夜地互相討論，并且競相發布自己的研究成果，終于在12月26號，剛好一個月，AdiShamir證明了下面的結論：AM==IP==PSPACE

Coinbase 正測試“Dot Collector”應用程序，讓員工在會議或其它互動期間互相評分:5月24日消息，Coinbase 正測試一款橋水基金（Bridgewater Associates）開發的名為“Dot Collector”的應用程序，讓員工在會議或其它互動期間對同事（或上司）互相評分，內容包括如何體現加密公司的 10 個文化原則。（The Information）[2022/5/24 3:37:33]

它解釋了「有效證明」這個概念的計算理論特征，并且解釋了「交互式證明系統」這個概念所能涵蓋的計算能力。注：NP類是PSPACE類的子集，前者大家比較熟悉，后者關聯游戲或者下棋中的制勝策略。而L.Babai于是寫了一篇文章，名為「Emailandtheunexpectedpowerofinteraction」，詳細闡述了這一整個月在「郵件交互」中精彩紛呈的學術競賽，以及關于「交互證明」的來龍去脈。公共參考串——另一種「信任根基」

除了采用「隨機預言機」之外，非交互零知識證明系統采用「公共參考串」，簡稱「CRS」，完成隨機挑戰。它是在證明者Alice在構造NIZK證明之前由一個受信任的第三方產生的隨機字符串，CRS必須由一個受信任的第三方來完成，同時共享給Alice和驗證者Bob。是的，你沒看錯，這里又出現了「第三方」！雖然第三方不直接參與證明，但是他要保證隨機字符串產生過程的可信。而產生CRS的過程也被稱為「TrustedSetup」，這是大家又愛又恨的玩意兒。顯然，在現實場景中引入第三方會讓人頭疼。CRS到底用來做什么？TrustedSetup的信任何去何從？這部分內容將留給本系列的下一篇。未完待續

非交互式零知識證明NIZK的「信任根基」也需要某種形式的隨機「挑戰」，一種「挑戰」形式是交給「隨機預言精靈」；另一種「挑戰」是通過Alice與Bob雙方共享的隨機字符串來實現。兩種挑戰形式本質上都引入了第三方，并且兩者都必須提供可以讓「模擬器」利用的「后門」，以使得讓模擬器在「理想世界」中具有某種「優勢」，而這種優勢在「現實世界」中必須失效。NIZK散發著無窮魅力，讓我不時驚嘆，在過去三十多年里，先驅們所探尋到的精妙結論，同時還有如此之多的未知角落，在等待靈感之光的照射。本系列文章在Github上的項目倉庫收到了第一個PullRequest，來自JingyuHu(colortigerhu)，只改了個把字，但那一瞬間，我感受到了生命力。知識交流，思想碰撞，很迷人，不是嗎？“Everyoneweinteractwithbecomesapartofus.”與我們交往互動的每一個人都是我們自身的一部分。―JodiAman*致謝：特別感謝丁晟超，劉巍然，陳宇的專業建議和指正，感謝安比實驗室小伙伴們(p0n1,even,aphasiayc,Vawheter,yghu,mr)的修改建議。致謝：自Nisan發起的密碼學研究軼事參考自鄧老師的文章。參考文獻Schnorr,Claus-Peter."Efficientsignaturegenerationbysmartcards."Journalofcryptology4.3(1991):161-174.Paillier,Pascal,andDamienVergnaud."Discrete-log-basedsignaturesmaynotbeequivalenttodiscretelog."InternationalConferenceontheTheoryandApplicationofCryptologyandInformationSecurity.Springer,Berlin,Heidelberg,2005.Pointcheval,David,andJacquesStern."Securityargumentsfordigitalsignaturesandblindsignatures."Journalofcryptology13.3(2000):361-396.Maxwell,Gregory,AndrewPoelstra,YannickSeurin,andPieterWuille."Simpleschnorrmulti-signatureswithapplicationstobitcoin."Designs,CodesandCryptography87,no.9(2019):2139-2164.Fiat,Amos,andAdiShamir."Howtoproveyourself:Practicalsolutionstoidentificationandsignatureproblems."ConferenceontheTheoryandApplicationofCryptographicTechniques.Springer,Berlin,Heidelberg,1986.Bellare,Mihir,andPhillipRogaway."RandomOraclesArePractical:aParadigmforDesigningEfficientProtocols."Proc.ofthe1stCCS(1995):62-73.LászlóBabai,andShlomoMoran."Arthur-Merlingames:arandomizedproofsystem,andahierarchyofcomplexityclasses."JournalofComputerandSystemSciences36.2(1988):254-276.mCanetti,Ran,OdedGoldreich,andShaiHalevi."Therandomoraclemethodology,revisited."JournaloftheACM(JACM)51.4(2004):557-594.ShafiGoldwasser,andYaelTauman."Onthe(in)securityoftheFiat-Shamirparadigm."44thAnnualIEEESymposiumonFoundationsofComputerScience,2003.Proceedings..IEEE,2003.Lewis,SarahJamie,OlivierPereira,andVanessaTeague."Addendumtohownottoproveyourelectionoutcome:TheuseofnonadaptivezeroknowledgeproofsintheScytlSwissPostInternetvotingsystem,anditsimplicationsforcastasintendedverification."Univ.Melbourne,Parkville,Australia(2019).Bernhard,David,OlivierPereira,andBogdanWarinschi."Hownottoproveyourself:Pitfallsofthefiat-shamirheuristicandapplicationstohelios."InternationalConferenceontheTheoryandApplicationofCryptologyandInformationSecurity.Springer,Berlin,Heidelberg,2012.Goldwasser,Shafi,andMichaelSipser."Privatecoinsversuspubliccoinsininteractiveproofsystems."ProceedingsoftheeighteenthannualACMsymposiumonTheoryofcomputing.ACM,1986.Papadimitriou,ChristosH."Gamesagainstnature."JournalofComputerandSystemSciences31.2(1985):288-301.Babai,László."E-mailandtheunexpectedpowerofinteraction."ProceedingsFifthAnnualStructureinComplexityTheoryConference.IEEE,1990.YiDeng."零知識證明：一個略顯嚴肅的科普."https://zhuanlan.zhihu.com/p/29491567

Tags：LICICEALIALICEALICE幣ICE幣Noah Decentralized State CoinAliceNet

ICP