中文字幕理论片,69视频免费在线观看,亚洲成人app,国产1级毛片,刘涛最大尺度戏视频,欧美亚洲美女视频,2021韩国美女仙女屋vip视频

本文來(lái)自安比實(shí)驗(yàn)室（ID：SECBIT），作者郭宇，Odaily星球日?qǐng)?bào)經(jīng)授權(quán)轉(zhuǎn)載。

本文已更新至Github

“Challenges are at times an indication of Lord's trust in you.” 挑戰(zhàn)，有時(shí)是上天信任你的一種表現(xiàn)。― D. Todd Christofferson

本文繼續(xù)長(zhǎng)篇大論零知識(shí)證明背后的機(jī)制原理，希望幫助大家理解這一類「現(xiàn)代密碼學(xué)工具」的大致輪廓。本文約8000字，少量數(shù)學(xué)公式。

系列一：初識(shí)「零知識(shí)」與「證明」

系列二：理解「模擬」

系列三：尋找「知識(shí)」

我們之前介紹的零知識(shí)證明系統(tǒng)都是「交互式」的，需要驗(yàn)證者 Bob 在交互中提供一個(gè)或若干個(gè)「隨機(jī)數(shù)」來(lái)挑戰(zhàn)，比如「地圖三染色問(wèn)題」（參看『系列二』）中，驗(yàn)證者 Bob 需要「不斷地」隨機(jī)挑選一條邊來(lái)挑戰(zhàn) Alice 的答案，直到 Bob 滿意為止，而 Alice 的作弊概率會(huì)「指數(shù)級(jí)」地衰減。而讓 Bob 相信證明的「基礎(chǔ)」取決于 Bob 所挑選的隨機(jī)數(shù)是不是足夠隨機(jī)。如果 Alice 能夠提前預(yù)測(cè)到 Bob 的隨機(jī)數(shù)，災(zāi)難就會(huì)發(fā)生，現(xiàn)實(shí)世界就會(huì)退化成「理想世界」，而 Alice 就可以立即升級(jí)成「模擬器」，通過(guò)超能力來(lái)愚弄 Bob。

而『系列三』中，我們分析了 Schnorr 協(xié)議，協(xié)議中雖然驗(yàn)證者 Bob 只需要挑選一個(gè)隨機(jī)數(shù) c 來(lái)挑戰(zhàn) Alice ，讓她計(jì)算一個(gè)值 z，但 Bob 絕對(duì)不能讓 Alice 有能力來(lái)預(yù)測(cè)到 c 的任何知識(shí)，否則，Alice 也會(huì)變身成模擬器。

隨機(jī)數(shù)的重要性不言而喻：

通過(guò)隨機(jī)數(shù)挑戰(zhàn)是交互式零知識(shí)證明的「信任根基」。

但，「交互過(guò)程」會(huì)限制應(yīng)用場(chǎng)景。如果能將交互式零知識(shí)證明變成「非交互」？這會(huì)非常非常激動(dòng)人心。所謂的非交互可以看成是只有「一輪」的證明過(guò)程，即Alice 直接發(fā)一個(gè)證明給 Bob 進(jìn)行驗(yàn)證。

非交互式零知識(shí)證明，英文是 Non-Interactive Zero Knowledge，簡(jiǎn)稱 NIZK。它意味整個(gè)證明被編碼為一個(gè)「字符串」，它可以寫(xiě)到一張紙上，通過(guò)郵件、聊天工具等各種方式隨意發(fā)送給任何驗(yàn)證者，字符串甚至可以放在 Github 上隨時(shí)供大家下載驗(yàn)證。

在區(qū)塊鏈?zhǔn)澜?，「NIZK」可以作為共識(shí)協(xié)議的一部分。因?yàn)橐粋€(gè)交易需要多個(gè)礦工進(jìn)行校驗(yàn)。設(shè)想下，如果交易的發(fā)送者和每個(gè)礦工都要交互一下，讓礦工進(jìn)行挑戰(zhàn)，那么共識(shí)過(guò)程將奇慢無(wú)比。而非交互式零知識(shí)證明則可以直接廣播給所有的礦工節(jié)點(diǎn)，讓他們自行驗(yàn)證。

可能有朋友會(huì)問(wèn)：只讓一個(gè)礦工挑戰(zhàn)不就夠了嗎？把礦工和交易發(fā)送者的交互腳本編碼成證明，然后廣播給其他礦工，然后其他礦工就直接相信這個(gè)挑戰(zhàn)過(guò)程是可信的，不也可以嗎？但是，很顯然，這里需要相信第一個(gè)交互礦工作為可信第三方，第三方？似乎不是一個(gè)好主意……

而非交互式零知識(shí)證明，以下我們直接說(shuō)「NIZK」，似乎就很理想了，沒(méi)有第三方賺差價(jià)。

「非交互」帶來(lái)的困惑

非交互式零知識(shí)證明，NIZK，如果存在，那么它要比交互式證明強(qiáng)大得多。

• 交互式證明，只能取信于一個(gè)驗(yàn)證者；而 NIZK 可以取信于多個(gè)驗(yàn)證者，以至所有人。

• 交互式證明，只能在交互的那個(gè)時(shí)刻有效；而 NIZK 將始終有效。

NIZK 不僅可以跨越空間，還能跨越時(shí)間

聽(tīng)上去很美，不是嗎？But, ……

重復(fù)下上節(jié)的一個(gè)結(jié)論：

可是如果 NIZK 失去了挑戰(zhàn)過(guò)程，有什么后果？

我們已經(jīng)回憶過(guò)「零知識(shí)」性質(zhì)的證明（參考『系列二』），證明過(guò)程需要構(gòu)造一個(gè)模擬器（算法），它也和驗(yàn)證者（Bob）在理想世界中進(jìn)行交互，而驗(yàn)證者 Bob 沒(méi)有能力區(qū)分出來(lái)對(duì)方是否是真的 Alice 還是一個(gè)模擬器。

如果現(xiàn)在考慮下 NIZK 中的 非交互式，假如「我」向「你」出示一張紙，上面寫(xiě)著一個(gè)「真」證明 X ，又假如「你」在看過(guò)這張紙之后確實(shí)相信我了；又因?yàn)閰f(xié)議是「零知識(shí)」，那么如果把「我」換成一個(gè)模擬器，模擬器也能「?jìng)卧臁挂粋€(gè)假證明 Y，能夠也讓「你」相信。

好了，問(wèn)題來(lái)了：

• 你如何區(qū)分 X 和 Y ，孰真孰假？當(dāng)然你無(wú)法區(qū)分，因?yàn)閰f(xié)議是零知識(shí)的，你必須不能區(qū)分

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

是不是不和諧了？請(qǐng)大家在此處思考兩分鐘。

(兩分鐘后……)

因?yàn)?NIZK 沒(méi)有了交互，也就沒(méi)了挑戰(zhàn)過(guò)程，所有的證明過(guò)程都有 Alice 來(lái)計(jì)算書(shū)寫(xiě)，理論上 Alice 確實(shí)是想寫(xiě)什么就寫(xiě)什么，沒(méi)人攔得住，比如 Alice 就寫(xiě)「理想世界」的 假證明 Y。

想必深刻理解模擬器的朋友，在這里會(huì)發(fā)現(xiàn)一個(gè)關(guān)鍵點(diǎn)：模擬器必須只能在「理想世界」中構(gòu)造Y，也就是說(shuō)，Y 這么邪惡的東西只能存在于「理想世界」，不能到「現(xiàn)實(shí)世界」禍害人間。

繼續(xù)思考……

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

而且，NIZK 中沒(méi)有交互，于是導(dǎo)致了一個(gè)嚴(yán)重的后果，模擬器沒(méi)有辦法使用「時(shí)間倒流」這個(gè)超能力，當(dāng)然似乎也就不能區(qū)分證明者在兩個(gè)世界中的行為。

換句話說(shuō)，如果我們面對(duì)任何一個(gè) NIZK 系統(tǒng)，似乎「模擬器」就很難高高在上了，它好像只能飄落人間，成為一個(gè)普普通通的凡人。如果，我說(shuō)如果，按此推論，假設(shè)模擬器不再具備超能力，那就意味著 Alice 和模擬器沒(méi)有區(qū)別，Alice 也可以成為一個(gè)模擬器，再繼續(xù)推論，Alice 就可以在「現(xiàn)實(shí)世界」中任意欺騙 Bob，那么這個(gè)證明系統(tǒng)就不再有價(jià)值，因?yàn)樗チ恕缚煽啃浴?。結(jié)論：任何的 NIZK 都不可靠。

這一定是哪里出了問(wèn)題……

上面我們?cè)诜治龅倪^(guò)程中，提到了交互挑戰(zhàn)的缺失。確實(shí)，如果 Bob 不參與 Alice 產(chǎn)生證明的過(guò)程，證明所包含的每一個(gè) bit 都由 Alice 提供，似乎「證明」本身不存在任何讓 Bob 信任的「根基」。這個(gè)從「直覺(jué)」上似乎說(shuō)不通。

那是不是說(shuō)，沒(méi)有 Bob 的參與就「徹底」沒(méi)辦法建立「信任根基」了呢？信任的根基還可以從哪里來(lái)呢？

答案是「第三方」！

Wait ……，協(xié)議交互不是只有兩方嗎？ Alice 和 Bob，哪來(lái)第三方？

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

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

回顧 Schnorr 協(xié)議

我們?cè)倏匆幌吕吓笥选猄chnorr 協(xié)議，它是一個(gè)三步協(xié)議：第一步，Alice 發(fā)送一個(gè)承諾，然后第二步 Bob 發(fā)送隨機(jī)數(shù)挑戰(zhàn)，第三步，Alice 回應(yīng)挑戰(zhàn)。

我們來(lái)看，如何把一個(gè)三步的 Schnorr 協(xié)議變成一步。

看一下 Schnorr 協(xié)議的第二步，Bob 需要給出一個(gè)隨機(jī)的挑戰(zhàn)數(shù) c，這里我們可以讓 Alice 用下面這個(gè)式子來(lái)計(jì)算這個(gè)挑戰(zhàn)數(shù)，從而達(dá)到去除協(xié)議第二步的目的。

c = Hash(PK, R)

其中 R 是 Alice 發(fā)給 Bob 的橢圓曲線點(diǎn)，PK 是公鑰。大家可以好好看看這個(gè)利用 Hash 算法計(jì)算 c 的式子。這個(gè)式子達(dá)到了兩個(gè)目的：

• Alice 在產(chǎn)生承諾 R 之前，沒(méi)有辦法預(yù)測(cè) c，即使 c 最終變相是 Alice 挑選的

• c 通過(guò) Hash 函數(shù)計(jì)算，會(huì)均勻分布在一個(gè)整數(shù)域內(nèi)，而且可以作為一個(gè)隨機(jī)數(shù)（注：請(qǐng)大家暫且這么理解，我們?cè)诤笪脑偕钊胗懻摚?/p>

請(qǐng)注意：Alice 絕不能在產(chǎn)生 R 之前預(yù)測(cè)到 c，不然， Alice 就等于變相具有了「時(shí)間倒流」的超能力，從而能任意愚弄 Bob。

而一個(gè)密碼學(xué)安全 Hash 函數(shù)是「單向」的，比如 SHA256，SHA3，blake2 等等。這樣一來(lái)，雖然 c 是 Alice 計(jì)算的，但是 Alice 并沒(méi)有能力實(shí)現(xiàn)通過(guò)挑選 c 來(lái)作弊。因?yàn)橹灰?Alice 一產(chǎn)生 R， c 就相當(dāng)于固定下來(lái)了。我們假設(shè) Alice 這個(gè)凡人在「現(xiàn)實(shí)世界」中是沒(méi)有反向計(jì)算 Hash 的能力的。

看上圖，我們利用 Hash 函數(shù)，把三步 Schnorr 協(xié)議合并為了一步。Alice 可以直接發(fā)送：(R, c, z)。又因?yàn)?Bob 擁有 PK，于是 Bob 可以自行計(jì)算出 c，于是 Alice 可以只發(fā)送 (R, z) 即可。

我們把上面這個(gè)方案稍微變下形，就得到了「數(shù)字簽名」方案。所謂的數(shù)字簽名，就是「我」向「你」出示一個(gè)字符串，比如「白日依山盡，黃河入海流」，然后為了證明這句詩(shī)是我出示的，我需要簽署某樣?xùn)|西。這個(gè)東西能證明我的身份和這句詩(shī)進(jìn)行了關(guān)聯(lián)。

從 NIZK 角度看數(shù)字簽名

不嚴(yán)格地說(shuō)，數(shù)字簽名方案相當(dāng)于在證明（1）我擁有私鑰，并且（2）私鑰和消息進(jìn)行了關(guān)聯(lián)計(jì)算。

我首先要證明我的身份，那么這個(gè)簡(jiǎn)單，這正是 Schnorr 協(xié)議的功能，能夠向?qū)Ψ阶C明「我擁有私鑰」這個(gè)陳述。并且這個(gè)證明過(guò)程是零知識(shí)的：不泄露關(guān)于「私鑰」的任何知識(shí)。

那么如何和這句唐詩(shī)關(guān)聯(lián)呢？我們修改下計(jì)算 c 的過(guò)程：

m = '白日依山盡，黃河入海流'
c = Hash(m, R)

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

注：這里嚴(yán)格點(diǎn)講，為了保證數(shù)字簽名的不可偽造性，需要證明 Schnorr 協(xié)議滿足「Simulation Soundness」這個(gè)更強(qiáng)的性質(zhì)。這點(diǎn)請(qǐng)參考文獻(xiàn)[2]

上圖就是大家所熟知的數(shù)字簽名方案 —— Schnorr 簽名方案[1]。在這里還有一個(gè)優(yōu)化，Alice 發(fā)給 Bob 的內(nèi)容不是 (R, z) 而是 (c, z)，這是因?yàn)?R 可以通過(guò) c, z 計(jì)算出來(lái)。

注：為什么說(shuō)這是一個(gè)「優(yōu)化」呢？目前針對(duì)橢圓曲線的攻擊方法有 Shanks 算法、Lambda 算法 還有 Pollard's rho 算法， 請(qǐng)大家記住他們的算法復(fù)雜度大約都是 [3]，n 是有限域大小的位數(shù)。假設(shè)我們采用了非常接近 2^256 的有限域，也就是說(shuō) z 是 256bit，那么橢圓曲線群的大小也差不多要接近 256bit，這樣一來(lái)，把 2^256 開(kāi)平方根后就是 2^128，所以說(shuō) 256bit 橢圓曲線群的安全性只有 128bit。那么，挑戰(zhàn)數(shù) c 也只需要 128bit 就足夠了。這樣 Alice 發(fā)送 c 要比發(fā)送 R 要更節(jié)省空間，而后者至少需要 256bit。c 和 z兩個(gè)數(shù)值加起來(lái)總共 384bit。相比現(xiàn)在流行的 ECDSA 簽名方案來(lái)說(shuō)，可以節(jié)省1/4 的寶貴空間?，F(xiàn)在比特幣開(kāi)發(fā)團(tuán)隊(duì)已經(jīng)準(zhǔn)備將 ECDSA 簽名方案改為一種類 Schnorr 協(xié)議的簽名方案——muSig[4]，可以實(shí)現(xiàn)更靈活地支持多簽和聚合。

而采用 Hash 函數(shù)的方法來(lái)把一個(gè)交互式的證明系統(tǒng)變成非交互式的方法被稱為 Fiat-Shamir 變換[5]，它由密碼學(xué)老前輩 Amos Fiat 和 Adi Shamir 兩人在 1986 年提出。

重建信任 —— 隨機(jī)預(yù)言精靈

前文提到，失去了挑戰(zhàn)，似乎失去了證明的「信任根基」。而在 Schnorr 簽名方案中，Hash 函數(shù)擔(dān)負(fù)起了「挑戰(zhàn)者」的角色，這個(gè)角色有一個(gè)非常學(xué)術(shù)的名字：「隨機(jī)預(yù)言機(jī)」（Random Oracle）[6]。

可是這里為何用 Hash？實(shí)際上當(dāng) Alice 要產(chǎn)生公共隨機(jī)數(shù)時(shí)，需要一個(gè)叫做「隨機(jī)預(yù)言機(jī)」的玩意兒，這是什么？

開(kāi)腦洞時(shí)間到！

我們?cè)O(shè)想在「現(xiàn)實(shí)世界」中，天上有一位「精靈」，他手持一個(gè)雙欄表格，左邊一欄為字符串，右邊一欄為數(shù)字。任何人，包括你我，包括 Alice 和 Bob，都可以發(fā)字符串給「精靈」。

精靈在拿到字符串之后，會(huì)查表的左邊欄，看看表格里有沒(méi)有這個(gè)字符串，下面分兩種情況：

• 情況一：如果左邊欄找不到字符串，那么精靈會(huì)產(chǎn)生一個(gè)「真隨機(jī)數(shù)」，然后把字符串與隨機(jī)數(shù)寫(xiě)入到表格中，然后把隨機(jī)數(shù)返回地面上的凡人。

• 情況二：如果左邊欄有這個(gè)字符串記錄，那么精靈會(huì)將右邊欄里面的數(shù)字直接返回給地面。

大家會(huì)發(fā)現(xiàn)這個(gè)精靈的行為其實(shí)很像一個(gè)隨機(jī)數(shù)發(fā)生器，但是又很不一樣，不一樣的地方在于當(dāng)我們發(fā)送相同的字符串時(shí)，他會(huì)返回相同的數(shù)。這個(gè)精靈就是傳說(shuō)中的「隨機(jī)預(yù)言機(jī)」。

而在合并 Schnorr 協(xié)議過(guò)程中，其實(shí)我們需要的是一個(gè)這樣的隨機(jī)預(yù)言精靈，而不是一個(gè) Hash 函數(shù)。兩者有什么不同的地方？區(qū)別就是：

• 隨機(jī)預(yù)言機(jī)每次對(duì)于新字符串返回的是一個(gè)具有一致性分布的「真」隨機(jī)數(shù)

• Hash 函數(shù)計(jì)算的結(jié)果并不是一個(gè)真正具有一致性分布的隨機(jī)數(shù)

那么為什么前面用的是 Hash 函數(shù)呢？這是因?yàn)樵诂F(xiàn)實(shí)世界中，真正的隨機(jī)預(yù)言機(jī)不存在！為什么呢？ 事實(shí)上，一個(gè) Hash 函數(shù)不可能產(chǎn)生真的隨機(jī)數(shù)，因?yàn)?Hash 函數(shù)是一個(gè)「確定性」算法，除了參數(shù)以外，再?zèng)]有其它隨機(jī)量被引入。

而一個(gè)具有密碼學(xué)安全強(qiáng)度的 Hash 函數(shù)「似乎」可以充當(dāng)一個(gè)「?jìng)巍闺S機(jī)預(yù)言機(jī)。那么合并后的安全協(xié)議需要額外增加一個(gè)很強(qiáng)的安全假設(shè)，這就是：

假設(shè)：一個(gè)密碼學(xué)安全的 Hash 函數(shù)可以近似地模擬傳說(shuō)中的「隨機(jī)預(yù)言機(jī)」

因?yàn)檫@個(gè)假設(shè)無(wú)法被證明，所以我們只能信任這個(gè)假設(shè)，或者說(shuō)當(dāng)做一個(gè)公理來(lái)用。插一句， Hash 函數(shù)的廣義抗碰撞性質(zhì)決定了它的輸出可以模擬隨機(jī)數(shù)，同時(shí)在很多情況下（并非所有），對(duì) Hash 函數(shù)實(shí)施攻擊難度很高，于是許多的密碼學(xué)家都在大膽使用。

不使用這個(gè)假設(shè)的安全模型叫做「標(biāo)準(zhǔn)模型」，而使用這個(gè)假設(shè)的安全模型當(dāng)然不能叫「非標(biāo)準(zhǔn)模型」，它有個(gè)好聽(tīng)的專有名詞，叫做「隨機(jī)預(yù)言模型」。

世界上有兩種不同類型的人，喜歡甜豆花的，不喜歡甜豆花的。同樣，世界上的密碼學(xué)家分為兩種，喜歡隨機(jī)預(yù)言模型的，和不喜歡隨機(jī)預(yù)言模型的[6]。

構(gòu)造根基 —— 被綁架的精靈

Schnorr 協(xié)議經(jīng)過(guò) Fiat-Shamir 變換之后，就具有 NIZK 性質(zhì)。這不同于我們證明過(guò)的 SHVZK，SHVZK 要求驗(yàn)證者誠(chéng)實(shí)，而 NIZK 則不再對(duì)驗(yàn)證者有任何不現(xiàn)實(shí)的要求，因?yàn)轵?yàn)證者不參與交互，所謂要求誠(chéng)實(shí)的驗(yàn)證者這個(gè)問(wèn)題就不復(fù)存在。

注：如果驗(yàn)證者 Bob 不誠(chéng)實(shí)會(huì)怎樣？那么 Bob 有可能抽取出 Alice 的知識(shí)。但是對(duì)于三步 Schnorr 協(xié)議而言，它是否滿足「零知識(shí)」，目前還處于未知狀態(tài)。我們?cè)谙盗腥兄蛔C明了它滿足一個(gè)比較弱的性質(zhì)：SHVZK。

但是，當(dāng) Schnorr 協(xié)議搖身一變，變成非交互零知識(shí)證明系統(tǒng)之后，就真正的「零知識(shí)」了。

然而，可能你的問(wèn)題也來(lái)了，這個(gè)論斷聽(tīng)起來(lái)似乎有道理，請(qǐng)問(wèn)能證明嗎？

時(shí)間到了，“翠花，上模擬器”

怎么用模擬器大法來(lái)構(gòu)造一個(gè)「理想世界」呢？大家可以想一下，我們之前使用過(guò)「時(shí)間倒流」，還有修改「隨機(jī)數(shù)傳送帶」超能力來(lái)讓「模擬器」來(lái)作弊?？墒菦](méi)有交互了，這就意味著：「時(shí)間倒流」超能力不能用；Bob 的隨機(jī)數(shù)傳送帶也不存在了，「篡改傳送帶」這個(gè)超能力也不能用！

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

（如果模擬器在沒(méi)有超能力的情況下具備作弊能力，那相當(dāng)于證明了協(xié)議的不可靠性）。

可能大家現(xiàn)在已經(jīng)猜出來(lái)了，模擬器要在「隨機(jī)預(yù)言機(jī)」上動(dòng)手腳。

先考慮下構(gòu)造一個(gè)「理想世界」來(lái)證明「零知識(shí)」。在理想世界中，模擬器「綁架」了負(fù)責(zé)提供預(yù)言的「精靈」，當(dāng) Bob 向精靈索要一個(gè)隨機(jī)數(shù)的時(shí)候，精靈并沒(méi)有給一個(gè)真隨機(jī)數(shù)，而是給 Zlice（模擬器假扮的 Alice）提前準(zhǔn)備好的一個(gè)數(shù)（也符合一致性分布，保證不可區(qū)分性），「精靈」無(wú)可奈何地返回 Bob 一個(gè)看起來(lái)隨機(jī)，但實(shí)際上有后門(mén)的數(shù)字。所謂后門(mén)，就是這個(gè)數(shù)字是 Zlice 自己提前選擇好的。

第一步：Zlice 隨機(jī)選擇 z，隨機(jī)選擇c，計(jì)算 R'=z*G - c*PK 。

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

第三步：Zlice 將簽名 (c, z) 發(fā)送給 Bob。

第四步：Bob 計(jì)算 R=z*G - c*PK，并向精靈發(fā)送 (m, R)，精靈返回 c’。請(qǐng)注意，這里 Bob 計(jì)算出來(lái)的 R 和 Zlice 計(jì)算出來(lái)的 R' 是相等。

第五步：Bob 驗(yàn)證 c ?= c'，看看精靈傳回來(lái)的隨機(jī)數(shù)和對(duì)方發(fā)過(guò)來(lái)的隨機(jī)數(shù)是否相等。如果相等，則驗(yàn)證簽名通過(guò)；否則，則驗(yàn)證失敗。

通過(guò)綁架「精靈」，Zlice 同樣可以提前預(yù)知隨機(jī)數(shù)，這和時(shí)間倒流能達(dá)到同樣的效果。

我們已經(jīng)證明了模擬器 Zlice 的「存在性」，于是我們上面已經(jīng)證明了 NIZK。

接下來(lái)我們證明這個(gè)這個(gè)協(xié)議的「可靠性」。設(shè)想在另一個(gè)「理想世界」中，一個(gè)叫做「抽取器」的玩意兒，也同樣綁架了精靈。當(dāng)無(wú)辜 Alice 的向「精靈」索要一個(gè)隨機(jī)數(shù)時(shí)，「精靈」返回了一個(gè) c1，「抽取器」從精靈的表格中偷窺到了c1，當(dāng) Alice 計(jì)算出來(lái) z1 之后，然后這時(shí)候「抽取器」仍然可以發(fā)動(dòng)「時(shí)間倒流」超能力，讓 Alice 倒退到第二步，再次向「精靈」要一個(gè)隨機(jī)數(shù)，Alice 發(fā)送的字符串顯然和第一次發(fā)送的字符串是相同的，(R, m)。按道理，因?yàn)?(R, m) 已經(jīng)寫(xiě)在精靈表格的「左欄」里，所以一個(gè)誠(chéng)實(shí)的「精靈」應(yīng)該返回 c1。但是，「抽取器」綁架了精靈，他把表格中對(duì)應(yīng) (R, m) 這一行的「右欄」改成了一個(gè)不同的數(shù) c2。當(dāng) Alice 計(jì)算出另一個(gè) z2 之后，抽取器就完成了任務(wù)，通過(guò)下面的方程計(jì)算出 Alice 的私鑰 sk：

sk = (z1 - z2)/(c1 - c2)
Fiat-Shamir 變換 —— 從 Public-Coin 到 NIZK

不僅僅對(duì)于 Schnorr 協(xié)議，對(duì)于任意的 「Public-Coin 協(xié)議」，都可以用 Fiat-Shamir 變換來(lái)把整個(gè)協(xié)議「壓縮」成一步交互，也就是一個(gè)非交互式的證明系統(tǒng)，這個(gè)變換技巧最早來(lái)自于 Amos Fiat 與 Adi Shamir 兩人的論文『How to Prove Yourself: Practical Solutions to Identification and Signature Problems.』，發(fā)表在 1986 年的 Crypto 會(huì)議上[5]。也有一說(shuō)，這個(gè)技巧來(lái)源于 Manuel Blum[6].

重復(fù)一遍，在 Public-coin 協(xié)議中，驗(yàn)證者 Bob 只做一類事情，就是產(chǎn)生一個(gè)隨機(jī)數(shù)，然后挑戰(zhàn) Alice 。通過(guò) Fiat-Shamir 變換，可以把 Bob 每一次的「挑戰(zhàn)行為」用一次「隨機(jī)預(yù)言」來(lái)代替。

而在具體實(shí)現(xiàn)中，隨機(jī)預(yù)言需要用一個(gè)具有密碼學(xué)安全強(qiáng)度的 Hash 函數(shù)（不能隨便選，一定要采用密碼學(xué)安全的 Hash），而 Hash 函數(shù)的參數(shù)應(yīng)該是之前所有的上下文輸入。下面是一個(gè)示例圖，大家可以迅速理解這個(gè) Fiat-Shamir 變換的做法。

前面提到，在非交互式證明系統(tǒng)中，需要引入一個(gè)第三方來(lái)構(gòu)建信任的「根基」，使得 Bob 可以完全相信由 Alice 所構(gòu)造的證明。在這里，第三方就是那個(gè)「精靈」，用學(xué)術(shù)黑話就是「隨機(jī)預(yù)言」（Random Oracle）。這個(gè)精靈并不是一個(gè)真實(shí)存在的第三方，而是一個(gè)虛擬的第三方，它同時(shí)存在于「現(xiàn)實(shí)世界」與「理想世界」。在「現(xiàn)實(shí)世界」中，精靈是一個(gè)負(fù)責(zé)任的安靜美男子，而在「理想世界」中，它會(huì)被「模擬器」綁架。

Public-Coin 協(xié)議還有一個(gè)好聽(tīng)的名字， 「Arthur-Merlin 游戲」 ……

看上圖，左邊的“白袍”就是 Merlin（魔法師梅林），中間拿劍的帥哥就是 King Arthur（亞瑟王），兩個(gè)角色來(lái)源于中世紀(jì)歐洲傳說(shuō)——亞瑟王的圓桌騎士。

Arthur 是一個(gè)不耐煩的國(guó)王，他隨身攜帶一個(gè)硬幣，而 Merlin是一個(gè)有著無(wú)限制計(jì)算能力的神奇魔法師，然后魔法師想說(shuō)服國(guó)王相信某個(gè)「論斷」為真，于是魔法師會(huì)和國(guó)王進(jìn)行到對(duì)話，但是由于國(guó)王比較懶，他每次只會(huì)拋一個(gè)硬幣，然后「挑戰(zhàn)」魔法師，而魔法師需要及時(shí)應(yīng)對(duì)，而且需要讓國(guó)王在 k 輪之后能夠相信自己的論斷。由于 Merlin 有魔法，所以亞瑟王拋的硬幣都能被 Merlin 看到[7]。

這與我們?cè)?span>『系列一』中提到的交互式證明系統(tǒng)（Interactive Proof System，簡(jiǎn)稱 IP）有些神似，但又不同。IP 由 Goldwasser，Micali 與 Rackoff（簡(jiǎn)稱GMR）在 1985 年正式提出，它的證明能力覆蓋很大一類的計(jì)算復(fù)雜性問(wèn)題。而不同的地方在于：在 IP 的定義中，證明者 Prover 和 驗(yàn)證者 Verifier 都是可以拋硬幣的圖靈機(jī)，Verifier 可以偷偷拋硬幣，并對(duì) Prover 隱藏；而在 Arthur-Merlin 游戲中，國(guó)王只能拋硬幣，不僅如此，而且拋硬幣的結(jié)果總會(huì)被 Merlin 知道。

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

盡管如此，人們無(wú)法抵擋 Fiat-Shamir 變換的誘惑，其使用極其廣泛。值得一提的是，最熱的通用非交互零知識(shí)證明 zkSNARK 的各種方案中，F(xiàn)iat-Shamir 變換比比皆是。比如大家可能耳熟能詳?shù)?Bulletproofs（子彈證明），此外還有一些暫時(shí)還不那么有名的通用零知識(shí)證明方案，比如 Hyrax，Ligero，Supersonic，Libra 等（我們后續(xù)會(huì)抽絲剝繭，逐一解讀）。

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

在 Fiat-Shamir 變換中，要尤其注意喂給 Hash 函數(shù)的參數(shù)，在實(shí)際的代碼實(shí)現(xiàn)中，就有這樣的案例，漏掉了 Hash 函數(shù)的部分參數(shù)：

比如在 A, Hash(A), B, Hash(B) 中，第二個(gè) Hash 函數(shù)就漏掉了參數(shù)A，正確的做法應(yīng)該是A, Hash(A), B, Hash(A,B)。這一類的做法會(huì)引入嚴(yán)重的安全漏洞，比如在瑞士的電子投票系統(tǒng) SwissPost-Scytl 中，就在 Fiat-Shamir 變換的實(shí)現(xiàn)代碼中多次漏掉了本來(lái)應(yīng)該存在的參數(shù)，導(dǎo)致了攻擊者不僅可以隨意作廢選票，還可以任意偽造選票，達(dá)到舞弊的目的[10]。因此在工程實(shí)現(xiàn)中，請(qǐng)務(wù)必注意。

細(xì)心讀者也許會(huì)回看一下 Schnorr 簽名，大家會(huì)發(fā)現(xiàn) Schnorr 簽名中的 Hash 算法似乎也漏掉了一個(gè)參數(shù) PK，并不是嚴(yán)格的 Fiat-Shamir 變換，這被稱為 Weak Fiat-Shamir 變換[11]，不過(guò)這個(gè)特例并沒(méi)有安全問(wèn)題[3]，請(qǐng)未成年人不要隨意模仿。

最近一些學(xué)者開(kāi)始在標(biāo)準(zhǔn)模型下研究如何嚴(yán)格證明 Fiat-Shamir 變換的安全性，目前要么引入額外的強(qiáng)安全假設(shè)，要么針對(duì)某個(gè)特定協(xié)議進(jìn)行證明，但似乎進(jìn)展并不大。

交互的威力

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

國(guó)王 Arthur 的方法很簡(jiǎn)單，通過(guò)反復(fù)地「隨機(jī)」挑戰(zhàn)來(lái)檢驗(yàn) Merlin 的論斷，這符合我們前面講述過(guò)的直覺(jué)：采用隨機(jī)挑戰(zhàn)來(lái)構(gòu)建信任的「根基」。Babai 在論文中證明了一個(gè)有趣的結(jié)論：AM[k]=AM[2]，其中 k 表示交互的次數(shù)，交互多次產(chǎn)生的效果居然和交互兩次等價(jià)。所謂交互兩次是指：Arthur 發(fā)一個(gè)挑戰(zhàn)數(shù)，然后 Merlin 回應(yīng)。

注：還有一類的問(wèn)題屬于 MA，這一類問(wèn)題的交互順序與 AM不同，MA中是 Merlin 先給出證明，然后 Arthur 拋硬幣檢驗(yàn)。已證明：MA 能處理的問(wèn)題是 AM 的子集。

不僅如此，Babai 還大膽猜測(cè)： AM[poly] 與 IP 是等價(jià)的。這是一個(gè)神奇的論斷：國(guó)王很懶，他只需要通過(guò)拋多項(xiàng)式次硬幣，就能成功挑戰(zhàn)魔法師，而這種方式的表達(dá)能力居然完全等價(jià)于 GMR 描述的交互式證明系統(tǒng) IP。果不其然，在 STOC'86 會(huì)議上，來(lái)自 S. Goldwasser 與 M. Sipser 的論文證明了這一點(diǎn)，AM[poly] == IP[12]。

這意味著：反復(fù)公開(kāi)的「隨機(jī)挑戰(zhàn)」威力無(wú)窮，它等價(jià)于任意的交互式證明系統(tǒng)。但是 AM[poly] 和別的計(jì)算復(fù)雜性類的關(guān)系如何，是接下來(lái)的研究熱點(diǎn)。

三年后，1989 年11月底，距今恰好三十年，年輕的密碼學(xué)家 Noam Nisan 發(fā)出了一封郵件，把自己的臨時(shí)學(xué)術(shù)結(jié)論發(fā)給了幾個(gè)密碼學(xué)家，然后他就跑去南美洲度假了?？墒撬辉氲?，這一個(gè)郵件會(huì)引爆歷史上一場(chǎng)激烈的學(xué)術(shù)競(jìng)賽，M. Blum, S. Kannan, D. Lipton, D. Beaver, J. Feigenbaum, H. Karloff, C. Lund 等等一大群精英開(kāi)始加入戰(zhàn)斗，他們沒(méi)日沒(méi)夜地互相討論，并且競(jìng)相發(fā)布自己的研究成果，終于在12月26號(hào)，剛好一個(gè)月，Adi Shamir 證明了下面的結(jié)論：

AM[poly] == IP == PSPACE

它解釋了「有效證明」這個(gè)概念的計(jì)算理論特征，并且解釋了「交互式證明系統(tǒng)」這個(gè)概念所能涵蓋的計(jì)算能力。

注：NP 類 是 PSPACE 類的子集，前者大家比較熟悉，后者關(guān)聯(lián)游戲或者下棋中的制勝策略[13]。

而 L. Babai 于是寫(xiě)了一篇文章，名為「Email and the unexpected power of interaction」（電子郵件與交互的始料未及的威力）[14]，詳細(xì)闡述了這一整個(gè)月在「郵件交互」中精彩紛呈的學(xué)術(shù)競(jìng)賽，以及關(guān)于「交互證明」的來(lái)龍去脈。

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

除了采用「隨機(jī)預(yù)言機(jī)」之外，非交互零知識(shí)證明系統(tǒng)采用「公共參考串」（Common Reference String），簡(jiǎn)稱「CRS」，完成隨機(jī)挑戰(zhàn)。它是在證明者 Alice 在構(gòu)造 NIZK 證明之前由一個(gè)受信任的第三方產(chǎn)生的隨機(jī)字符串，CRS 必須由一個(gè)受信任的第三方來(lái)完成，同時(shí)共享給 Alice 和 驗(yàn)證者 Bob。

是的，你沒(méi)看錯(cuò)，這里又出現(xiàn)了「第三方」！雖然第三方不直接參與證明，但是他要保證隨機(jī)字符串產(chǎn)生過(guò)程的可信。而產(chǎn)生 CRS 的過(guò)程也被稱為「Trusted Setup」，這是大家又愛(ài)又恨的玩意兒。顯然，在現(xiàn)實(shí)場(chǎng)景中引入第三方會(huì)讓人頭疼。CRS 到底用來(lái)做什么？Trusted Setup 的信任何去何從？這部分內(nèi)容將留給本系列的下一篇。

未完待續(xù)

非交互式零知識(shí)證明 NIZK 的「信任根基」也需要某種形式的隨機(jī)「挑戰(zhàn)」，一種「挑戰(zhàn)」形式是交給「隨機(jī)預(yù)言精靈」；另一種「挑戰(zhàn)」是通過(guò) Alice 與 Bob 雙方共享的隨機(jī)字符串來(lái)實(shí)現(xiàn)。兩種挑戰(zhàn)形式本質(zhì)上都引入了第三方，并且兩者都必須提供可以讓「模擬器」利用的「后門(mén)」，以使得讓模擬器在「理想世界」中具有某種「優(yōu)勢(shì)」，而這種優(yōu)勢(shì)在「現(xiàn)實(shí)世界」中必須失效。

NIZK 散發(fā)著無(wú)窮魅力，讓我不時(shí)驚嘆，在過(guò)去三十多年里，先驅(qū)們所探尋到的精妙結(jié)論，同時(shí)還有如此之多的未知角落，在等待靈感之光的照射。

本系列文章在 Github 上的項(xiàng)目倉(cāng)庫(kù)收到了第一個(gè) Pull Request，來(lái)自Jingyu Hu(colortigerhu)，只改了個(gè)把字，但那一瞬間，我感受到了生命力。知識(shí)交流，思想碰撞，很迷人，不是嗎？

“Everyone we interact with becomes a part of us.” 與我們交往互動(dòng)的每一個(gè)人都是我們自身的一部分。 ― Jodi Aman

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

致謝：自Nisan發(fā)起的密碼學(xué)研究軼事參考自鄧?yán)蠋煹奈恼耓15]。

參考文獻(xiàn)