相信很多人都聽(tīng)說(shuō)過(guò)零知識(shí)證明，但是只有極少數(shù)人聽(tīng)說(shuō)過(guò)模擬，然而模擬是理解零知識(shí)的關(guān)鍵。

如果從直覺(jué)主義角度解釋?zhuān)C明一個(gè)交互系統(tǒng)中存在信息泄露，那么你只需要指證：第幾個(gè) bit 導(dǎo)致信息泄露即可；但如果要證明不存在信息泄露，那么你要對(duì)著所有信息流中的所有 bit 說(shuō)，這從1，2，3，4，5，…… 編號(hào)的 bit 都沒(méi)泄露任何信息?？垂賯?，這是不是很難？

安全的定義與不可區(qū)分性

首先，一個(gè)交互式系統(tǒng)，也就是一個(gè)對(duì)話，它的「零知識(shí)」需要證明。畢竟，現(xiàn)代密碼學(xué)是建立在嚴(yán)格的形式化系統(tǒng)之上。在證明之前，還需要明確「安全假設(shè)」到底有哪些。所謂安全假設(shè)，比如我們說(shuō)一個(gè)系統(tǒng)的權(quán)限隔離做得無(wú)比精確，每一個(gè)用戶(hù)只能看到被授權(quán)的信息，但是這基于一個(gè)安全假設(shè)：管理員賬號(hào)沒(méi)有被破解。又比如在手機(jī)銀行軟件里，只能通過(guò)短信認(rèn)證碼，才能完成轉(zhuǎn)賬功能，這也基于一個(gè)安全假設(shè)：你的手機(jī) SIM 卡沒(méi)有被克隆。如果我們深入地分析每一個(gè)我們感覺(jué)安全的系統(tǒng)，都存在大量的似乎不那么穩(wěn)固的安全假設(shè)。比特幣私鑰安全嗎？比特幣賬戶(hù)的安全假設(shè)也不少：首先你的助記詞不能讓別人知道，手機(jī)錢(qián)包里私鑰保存加密算法足夠強(qiáng)，密鑰派生算法正規(guī)，你不能忘記助記詞，等等等。

脫離安全假設(shè)來(lái)談安全都是在耍流氓。一切安全都有前提的。只有經(jīng)過(guò)數(shù)學(xué)證明之后，大家才能夠確信這個(gè) 算法/方案 的安全性基于一些非常明確的「安全假設(shè)」。

在證明之前，還缺少一個(gè)東西，那就是「安全定義」。在多數(shù)人的認(rèn)知系統(tǒng)中，安全就是一個(gè)框，什么都可以往里裝。大家應(yīng)該好好提醒下自己，當(dāng)談?wù)摪踩值臅r(shí)候，有沒(méi)有想過(guò)到底什么是安全？怎么算安全？

「安全」需要有一個(gè)數(shù)學(xué)意義上的嚴(yán)格定義

偉大的科學(xué)家香農(nóng)（Claude Shannon）從信息論的角度給出了一個(gè)非?？孔V的安全性定義［2］：

完美安全：假設(shè)你是一個(gè)攻擊者，你通過(guò)密文獲取不到任何有價(jià)值的信息，破解的唯一手段就是靠瞎蒙。

大家想一想，這個(gè)定義很有趣，通過(guò)密文獲取不到信息，這就意味著你沒(méi)有獲得任何額外的計(jì)算能力，能夠幫助讓你以更短的時(shí)間來(lái)計(jì)算出明文。

但是這個(gè)定義太完美，以至于使用的加密算法都很難滿(mǎn)足這個(gè)安全性定義。后來(lái) Goldwasser 與 Micali 等人寫(xiě)了另一篇載入史冊(cè)的經(jīng)典『概率加密』［2］。

在這篇論文中定義了這樣一個(gè)概念：語(yǔ)義安全。所謂語(yǔ)義安全在完美安全的定義上放松了些要求。

語(yǔ)義安全：假設(shè)你是一個(gè)攻擊者，你通過(guò)密文在多項(xiàng)式時(shí)間內(nèi)計(jì)算不出來(lái)任何有價(jià)值的信息。

好了，這個(gè)看起來(lái)靠譜多了。接下來(lái)一個(gè)問(wèn)題就是，怎么理解「計(jì)算不出來(lái)信息」這個(gè)概念？這看來(lái)要對(duì)信息進(jìn)行度量，信息的定義又是什么呢？

我們又引入一個(gè)概念——「不可區(qū)分性」，來(lái)重新表述加密算法的安全性：假設(shè)你是一個(gè)攻擊者，而我有一個(gè)加密算法：

OK，理解完「不可區(qū)分性」，我們?cè)倩氐健噶阒R(shí)」，如何證明一個(gè)交互式系統(tǒng)是「零知識(shí)」呢？首先我們要定義下零知識(shí)這個(gè)概念。

注：不可區(qū)分性是概率意義上的不可區(qū)分；在學(xué)術(shù)上，它可以分為「完全不可區(qū)分」，「統(tǒng)計(jì)不可區(qū)分」，還有「計(jì)算不可區(qū)分」。在本文中，我們暫時(shí)不需要理解這些概念的差別。

遇見(jiàn)模擬器

先開(kāi)個(gè)腦洞，設(shè)想在平行宇宙中，有兩個(gè)平行的世界，一個(gè)叫做「理想世界」（Ideal World），另一個(gè)叫做「現(xiàn)實(shí)世界」（Real World）。我們每一個(gè)個(gè)體可以在兩個(gè)平行世界中愉快地玩耍，但是兩個(gè)世界的普通人無(wú)法互相感知，也無(wú)法互相溝通。

假設(shè)「你」是一個(gè)很厲害的密碼破解者，而且「你」不是普通人，具備在平行宇宙之間穿梭的能力。而 Alice 有一個(gè)地圖三染色的答案，你的目的是通過(guò)和 Alice 對(duì)話來(lái)獲取地圖三染色的答案，會(huì)話的過(guò)程參考上一篇文章的「地圖三染色問(wèn)題」協(xié)議。

繼續(xù)腦洞，Alice 只存在「現(xiàn)實(shí)世界」中；在「理想世界」，Alice 被「替換」成了一個(gè)長(zhǎng)相與聲音一模一樣的個(gè)體，我們稱(chēng)替身為 Zlice。下一步，把「你」同時(shí)放入兩個(gè)世界中，但不讓你知道是你當(dāng)前位于哪一個(gè)世界。你的兩個(gè)分身所面對(duì)的都是一個(gè) “Alice”模樣的人。

再重復(fù)一遍，在「現(xiàn)實(shí)世界」中， 與你對(duì)話的是一個(gè)真實(shí)的，并且誠(chéng)實(shí)的 Alice；而在「理想世界」中，與你對(duì)話的是 Zlice （假 Alice），Zlice 雖然相貌語(yǔ)言與 Alice 并無(wú)二致，但差異是，Zlice 并不知道「知識(shí)」，即不知道一個(gè)三染色問(wèn)題的答案。

接下來(lái)在這兩個(gè)世界中，你的兩個(gè)分身將同時(shí)與真假 Alice 進(jìn)行對(duì)話。神奇的事情發(fā)生了，最終在兩個(gè)世界中，你的兩個(gè)分身都被說(shuō)服了，都經(jīng)過(guò)n輪挑戰(zhàn)，沒(méi)有發(fā)現(xiàn)對(duì)方作弊，即「你」的兩個(gè)分身都認(rèn)為對(duì)方確實(shí)知道「答案」。換句話說(shuō)，「你」沒(méi)有能力「區(qū)分」出來(lái)自己到底在 「現(xiàn)實(shí)世界」 還是 「理想世界」，當(dāng)然也沒(méi)能力「區(qū)分」和自己對(duì)話的究竟是 Alice 還是 Zlice。不僅如此，對(duì)于吃瓜群眾我而言，如果把「我」作為觀察者放入任何一個(gè)世界中，我會(huì)和你一樣「無(wú)法區(qū)分」出來(lái)眼前的 這個(gè)長(zhǎng)相為 “Alice” 的人到底是真還是假。

下面是燒腦結(jié)論：

這個(gè)交互系統(tǒng)為何是「零知識(shí)」？

因?yàn)?Zlice 是沒(méi)有任何知識(shí)，而且她和 Alice 不可區(qū)分。

我再換個(gè)方式解釋?zhuān)阂驗(yàn)槟愫臀叶紱](méi)辦法區(qū)分我們究竟是在哪個(gè)世界中，兩個(gè)世界發(fā)生的交互過(guò)程幾乎不可區(qū)分，而且其中一個(gè)世界中根本就不存在知識(shí)，因此，我們說(shuō)這個(gè)交互協(xié)議——「地圖三染色問(wèn)題」是「零知識(shí)的」。

這里還有個(gè)前提，理想世界必須是算法可構(gòu)造的。然后，有一個(gè)「神」，他通過(guò)算法「模擬」了一個(gè)「理想世界」，其中構(gòu)造了一個(gè)算法叫做 Zlice，她沒(méi)有「知識(shí)」作為輸入，也即「零知識(shí)」；除此之外，「理想世界」與「現(xiàn)實(shí)世界」一模一樣。

設(shè)想你在對(duì)話過(guò)程中，如果真 Alice 泄露了信息，那么你就能立即區(qū)分出面前這個(gè)人是 真 Alice 還是 Zlice，Zlice 是不可能偽裝泄露信息的。因此可以得出結(jié)論：

真 Alice 沒(méi)有泄露任何信息。

這個(gè)神，被稱(chēng)為「模擬器」（Simulator），而在理想世界中，和你對(duì)話的這個(gè) Zlice 幻象其實(shí)也是「模擬器」，你在理想世界中，所有能感知到的東西都是模擬器「模擬」出來(lái)的。

好了，到這里，我們用「模擬器」這個(gè)概念對(duì)「零知識(shí)」進(jìn)行了定義。

接下來(lái)，我們開(kāi)始進(jìn)入證明零知識(shí)的環(huán)節(jié)。

區(qū)分兩個(gè)世界

證明的零知識(shí)過(guò)程，等價(jià)于構(gòu)造（尋找）一個(gè)「模擬」算法，這個(gè)算法能夠讓模擬器來(lái)模擬出一個(gè)「沒(méi)有知識(shí)」的理想世界。如果這個(gè)算法存在，而且兩個(gè)世界不可區(qū)分，那么就證明完畢。

等等，可能「你」會(huì)覺(jué)得哪里不對(duì)勁。

假如說(shuō)真的存在這種算法，而且它能夠在沒(méi)有知識(shí)的情況下騙過(guò)我，那么在「現(xiàn)實(shí)世界」中，不排除真 Alice 也使用了這樣的算法來(lái)欺騙我。這樣一來(lái)，我豈不是在兩個(gè)世界中都被欺騙了。那么這個(gè)交互協(xié)議就失去意義了。

其實(shí)，這里有個(gè)關(guān)鍵點(diǎn)，借用電影『盜夢(mèng)空間』中的劇照，在「理想世界」中有點(diǎn)東西是和「現(xiàn)實(shí)世界」本質(zhì)不同的。這個(gè)東西是區(qū)分兩個(gè)世界的關(guān)鍵，而它要讓我們「無(wú)法感知」。這個(gè)東西不是夢(mèng)境中的陀螺，它是一種「超能力」，模擬器 Simulator 所具備的超能力。

比如這樣一種超能力：「時(shí)光倒流」。

等等，各位看官，不是剛才我們一直在討論不可區(qū)分性嗎？怎么兩個(gè)世界又需要區(qū)分啦？“我糊涂了”。不要慌，所謂的不可區(qū)分性針對(duì)的是理想世界中的個(gè)體認(rèn)知而言。而「可區(qū)分性」是對(duì)位于世界外部的神而言。

設(shè)想下在我們周?chē)?，如果有一個(gè)人有時(shí)空穿越能力，或者他能讓時(shí)間回退到一年前，那么我們這些凡夫俗子完全是一臉茫（meng）然（bi）的，無(wú)從感知。那么，如果「模擬器」可以在他構(gòu)造出的「理想世界」中實(shí)現(xiàn)「時(shí)間倒流」，那么他就可以達(dá)成一些神奇的事情，從而騙過(guò)作為驗(yàn)證者身份的「你」，也能騙過(guò)觀察者「我」。對(duì)于「你」而言，你明白，在「理想世界」中，時(shí)間是可以回退的，但是在「現(xiàn)實(shí)世界」中，顯然真 Alice 不可能擁有超能力。雖然你和我不能區(qū)分在哪個(gè)世界里，但是至少我們知道在兩個(gè)世界中的其中「現(xiàn)實(shí)世界」里，對(duì)面那個(gè)Alice是沒(méi)辦法欺騙我們的，當(dāng)然我們卻不能說(shuō)出我們到底在哪個(gè)世界中。

到此，交互協(xié)議的「零知識(shí)」已經(jīng)證明完了。各位是否已經(jīng)明白了？我再給大家再梳理下證明思路：

首先「零知識(shí)」是為了保護(hù) Alice 的利益，因?yàn)?Alice 不想在交互過(guò)程中透露更多的信息給 Bob，不想讓 Bob 知道她所擁有的秘密 w，甚至不想讓 Bob 從交互的過(guò)程中分析出哪怕一丁點(diǎn)的信息。那么怎么保證這一點(diǎn)呢？「模擬器」這時(shí)候登場(chǎng)了，它能模擬出一個(gè)和現(xiàn)實(shí)世界外表一模一樣的「理想世界」，然后「模擬器」在這個(gè)世界中可以輕松地騙過(guò)任何一個(gè)對(duì)手，讓對(duì)方無(wú)法分辨自己是在現(xiàn)實(shí)世界中，還是理想世界中。因?yàn)椤改M器」手里沒(méi)有那個(gè)秘密 w，「理想世界」是零知識(shí)的。又因?yàn)閮蓚€(gè)世界的不可區(qū)分性，所以我們可以得出結(jié)論：Alice 的交互協(xié)議是「零知識(shí)」的。

我們來(lái)看一個(gè)具體的例子，上一篇文章［1］中提到的地圖3染色問(wèn)題。

地圖三染色問(wèn)題的零知識(shí)證明

回憶一下「地圖三染色問(wèn)題交互系統(tǒng)」：

· 第一步：Alice 把地圖染色答案做一次完全置換，然后將所有頂點(diǎn)蓋上紙片，交給 Bob

· 第二步：Bob 隨機(jī)挑選一條邊

· 第三步：Alice 打開(kāi)指定邊的兩端頂點(diǎn)的紙片，Bob檢驗(yàn)兩個(gè)頂點(diǎn)的顏色是否相同，如果不同則通過(guò)，如果相同則失敗

· 回到第一步，重復(fù) n 遍

我們接下來(lái)就來(lái)證明上述這個(gè)交互是零知識(shí)的，這里先假設(shè)驗(yàn)證者 Bob 是誠(chéng)實(shí)的，這有助于大家理解這個(gè)證明過(guò)程。然后我們?cè)儆懻?，如?Bob 不誠(chéng)實(shí)的證明方法。

在「理想世界」中，跟 Bob 對(duì)話的是一個(gè)「模擬器」，它模擬出了整個(gè)世界的樣子。Bob 按照三染色問(wèn)題的交互協(xié)議進(jìn)行交互。模擬器并沒(méi)有一個(gè)三染色答案，它索性把所有的頂點(diǎn)都染成了灰色。

首先，模擬器模仿 Alice ，把每個(gè)頂點(diǎn)用紙片蓋起來(lái)。然后發(fā)給 Bob。

Bob 隨機(jī)挑選了一條邊，挑戰(zhàn)證明者。

Bob 這時(shí)候無(wú)法感知到時(shí)間已經(jīng)倒退回第一步了，對(duì)他來(lái)說(shuō)，一切都是新鮮的，他「誠(chéng)實(shí)」地再次選擇了最下面的邊。

這時(shí)候模擬器就可以放心地打開(kāi)紙片，讓 Bob 檢查。Bob 很顯然會(huì)被騙過(guò)。然后 Bob 一輪輪地重復(fù)這個(gè)過(guò)程，每一次模擬器都能用時(shí)間倒流的方式騙過(guò) Bob。

于是在理想世界中，模擬器并沒(méi)有任何三染色答案的「知識(shí)」，卻同樣能騙過(guò)Bob，并且從概率上來(lái)看，與「現(xiàn)實(shí)世界」中被觀察到的交互過(guò)程高度地一致（完全一致的概率分布）。于是上面的過(guò)程展示了模擬器的算法的存在性，也就相當(dāng)于證明了交互系統(tǒng)的「零知識(shí)性質(zhì)」。

不誠(chéng)實(shí)的 Bob

在上面的證明過(guò)程中，有一個(gè)相當(dāng)強(qiáng)的假設(shè)，就是每次時(shí)間倒流之后，Bob都會(huì)選擇同一條邊。如果 Bob 每次都會(huì)換一條不同的邊呢？沒(méi)關(guān)系，如果在模擬器第一次實(shí)施時(shí)間倒流之后，Bob又選擇了不同的邊，那么模擬器可以把顏色打亂之后，再次運(yùn)行時(shí)間倒流，在多次時(shí)間倒流之后，Bob 極大的概率總會(huì)一次選擇模擬器進(jìn)行染色的那條邊，然后這時(shí)候模擬器才走到第三步，打開(kāi)紙片。

阿里巴巴、洞穴與芝麻開(kāi)門(mén)

在網(wǎng)上眾多的講解「零知識(shí)證明」的中文科普文章中，有一個(gè)例子流傳非常廣，這就是阿里巴巴與強(qiáng)盜的故事。可惜地是，這些不同版本的故事都只講了一半。那么我接下來(lái)講一個(gè)不一樣的「阿里巴巴」與「四十大盜」的故事：

在很久很久以前，在一個(gè)叫做巴格達(dá)的城市里，住著一個(gè)人叫阿里巴巴。每天阿里巴巴會(huì)到集市上買(mǎi)東西。

有一天，阿里巴巴被一個(gè)盜賊搶了錢(qián)包，于是他一路追著盜賊到了一個(gè)山洞口，然后盜賊就消失了。阿里巴巴發(fā)現(xiàn)洞口里面有兩條岔路，如下圖所示。

阿里巴巴不知道盜賊往哪邊跑了，于是他決定去「左邊」岔道看看，很快阿里巴巴就發(fā)現(xiàn)這是個(gè)死胡同，也不見(jiàn)盜賊蹤影。然后他又去「右邊」岔道檢查，也是個(gè)死胡同，不見(jiàn)盜賊蹤影。阿里巴巴自言自語(yǔ)道：「該死的盜賊跑哪去了呢？」

第二天，阿里巴巴又去集市買(mǎi)東西，這次另一個(gè)盜賊搶了他的籃子，然后阿里巴巴追著這個(gè)盜賊到了昨天同樣的山洞口，然后盜賊又不見(jiàn)了，這一次阿里巴巴決定先去「右邊」岔道看看，沒(méi)有發(fā)現(xiàn)盜賊，然后再去左邊看看，也同樣不見(jiàn)盜賊。這好奇怪。

第三天，第四天，……，第四十天，同樣的故事上演，阿里巴巴追著第四十個(gè)大盜到了神秘的洞口，盜賊就消失了。阿里巴巴想，這個(gè)山洞里面一定有機(jī)關(guān)，于是他躲在「右邊」岔道的盡頭，耐心地等了很長(zhǎng)時(shí)間，這時(shí)一個(gè)盜賊跑了進(jìn)來(lái)，走道岔道盡頭之后，念了一個(gè)咒語(yǔ)「芝麻開(kāi)門(mén)」。這時(shí)候墻壁居然打開(kāi)了，盜賊跑進(jìn)去之后，然后墻壁又合上了，這時(shí)候另一個(gè)受害者追了進(jìn)來(lái)，找了半天，一無(wú)所獲。

阿里巴巴隨后等他們走了之后，試驗(yàn)了一下這個(gè)咒語(yǔ)，果然非常有效，而且阿里巴巴發(fā)現(xiàn)這個(gè)墻壁通向「左邊」岔道。后來(lái)，阿里巴巴找到了更換咒語(yǔ)的辦法，并且把一個(gè)新咒語(yǔ)和洞穴的地理位置寫(xiě)在了一張羊皮紙上。

注：到這里，故事并沒(méi)有結(jié)束。..。 （上字幕）很久很久以后

在很多年后，到了80年代，阿里巴巴的羊皮紙流落到了幾個(gè)密碼學(xué)家手里，他們跑到巴格達(dá)，找到了洞穴的位置，盡管過(guò)了幾個(gè)世紀(jì)，咒語(yǔ)居然仍然有效，這幾個(gè)密碼學(xué)家興奮地打開(kāi)墻壁，在兩個(gè)岔道之間跑來(lái)跑去。

一家電視臺(tái)很快知道了這個(gè)奇異事件，一個(gè)密碼學(xué)家 Mick Ali（與密碼學(xué)家 Micali 發(fā)音相似）決定向電視觀眾展示他知道這個(gè)咒語(yǔ)，首先，電視節(jié)目主持人把攝像機(jī)架在洞口，然后讓所有人都在山洞口等待，這時(shí)候 Mick Ali一個(gè)人進(jìn)入到山洞中，然后主持人拋一個(gè)硬幣，來(lái)決定讓 Mick Ali 從哪個(gè)岔道跑出來(lái)。為了紀(jì)念阿里巴巴與四十大盜，Mick Ali 重復(fù)了四十遍每次都成功。

節(jié)目非常成功。但很快，另外一個(gè)電視臺(tái)眼紅，也想拍一個(gè)類(lèi)似的節(jié)目，但是Mick Ali 因?yàn)楹灹霜?dú)家協(xié)議，沒(méi)辦法參與這個(gè)新節(jié)目。怎么辦呢？第二個(gè)電視臺(tái)的主持人心生一計(jì)，他找了一個(gè)和 Mick Ali 很像的演員，穿著打扮、姿態(tài)和說(shuō)話口音都模仿 Mick Ali。然后他們開(kāi)拍了，每次主持人擲硬幣后，都讓這個(gè)演員跑出來(lái)，但是很顯然，演員并不知道咒語(yǔ)，沒(méi)辦法打開(kāi)那個(gè)墻壁。于是有時(shí)候演員碰巧會(huì)成功，有時(shí)候則會(huì)失敗，于是演員很辛苦，重復(fù)了將近一百次，才成功了四十次。最后這個(gè)狡猾的新節(jié)目主持人，把錄制視頻進(jìn)行了剪輯，只保留了成功的片段，錯(cuò)誤的片段都刪除了。然后這個(gè)新節(jié)目和 Mick Ali 的節(jié)目在同一時(shí)間，不同頻道播出。然后觀眾們完全無(wú)法區(qū)分哪個(gè)視頻是真的，哪個(gè)視頻是假的。第一個(gè)電視臺(tái)的主持人完全明白 Mick Ali 是真正知道墻壁的咒語(yǔ)的人，但是他卻不能把這個(gè)事實(shí)傳遞給無(wú)辜的觀眾們。

看到這里，大家是不是對(duì)「模擬」慢慢有了感覺(jué)？這里第二個(gè)電視臺(tái)的主持人通過(guò)剪輯視頻的方式，而不是「時(shí)間倒流」。他對(duì)「理想世界」，也就是電視中播出的內(nèi)容所在的世界，進(jìn)行了外部干預(yù)，達(dá)到了同樣的效果。對(duì)理想世界而言，這種剪輯本質(zhì)上就是一種超能力。

這個(gè)故事其實(shí)來(lái)源于一篇論文『如何向你的孩子解釋零知識(shí)證明』（How to Explain Zero-Knowledge Protocols to Your Children）［3］，發(fā)表在1989年的美密會(huì)議上。

模擬與圖靈機(jī)

一談到超能力，大家有沒(méi)有覺(jué)得這玩意不科學(xué)。是的，如果我們無(wú)腦地用「超能力」來(lái)解釋任何事情，那么我們邏輯就無(wú)法自恰（Consistent）。在理想世界中，模擬器是不能隨便開(kāi)掛的，比如模擬器肯定不能直接修改 Bob 的內(nèi)部狀態(tài)，比如 Bob 在驗(yàn)證步驟明明驗(yàn)證失敗，但是模擬器強(qiáng)硬去把驗(yàn)證結(jié)果改為「接受」，這會(huì)導(dǎo)致我們可以證明：「任何的交互系統(tǒng)都是零知識(shí)的」，這個(gè)錯(cuò)誤結(jié)論。

模擬器不是理想世界中全能的上帝。

那么模擬器到底可以是什么呢？模擬器其實(shí)只是一個(gè)圖靈機(jī)。所謂的「時(shí)間倒流」，「剪輯錄像」這類(lèi)的所謂超能力并不是玄乎的超自然能力，而是圖靈機(jī)可以實(shí)現(xiàn)的功能。計(jì)算機(jī)專(zhuān)業(yè)的朋友們肯定都用過(guò) VMWare，虛擬機(jī)之類(lèi)的軟件，本文講的「模擬器」完全可以想象成一個(gè)「虛擬機(jī)」軟件，它能虛擬出一個(gè)計(jì)算機(jī)環(huán)境，這個(gè)虛擬環(huán)境就是我們上文說(shuō)的「理想世界」?！笗r(shí)間倒流」如何解釋呢？不知道大家有沒(méi)有用過(guò)虛擬機(jī)軟件的「快照」功能（Snapshot），使用快照的時(shí)候，虛擬機(jī)軟件可以把整個(gè)虛擬計(jì)算機(jī)的所有狀態(tài)保存下來(lái)，然后在任意時(shí)刻，虛擬機(jī)軟件都可以重新回到保存快照的位置繼續(xù)運(yùn)行。

注：其實(shí)所謂時(shí)間倒流是計(jì)算機(jī)中的一個(gè)基本操作，在程序語(yǔ)言理論中有一個(gè)概念叫做 Continuation。抽象地講，Continuation 表示從現(xiàn)在開(kāi)始到未來(lái)的計(jì)算。Continuation這是控制流的一個(gè)顯式抽象，而 goto，call-with-current-continuation，甚至 thread scheduling 都可以看做是操作 Continuation 的操作符。比如采用call/cc，也就是call-with-current-continuation 就可以輕松地實(shí)現(xiàn)「回溯」功能。保存快照可以理解為保存當(dāng)前的 Continuation，而回到過(guò)去的某一刻，就是應(yīng)用這個(gè) Continuation。

不管 Zlice 還是 Bob，還有我們的每一個(gè)觀察者，都是一個(gè)個(gè)可執(zhí)行程序。這些程序被拷貝到了虛擬機(jī)里。Zlice 與 Bob 的會(huì)話實(shí)際上就是這兩個(gè)程序之間的通訊。觀察者是 Hook 在 Zlice 與 Bob 進(jìn)程 IO 上的程序。在上文的地圖三染色「理想世界」的誠(chéng)實(shí) Bob，實(shí)際上是 Bob 進(jìn)程調(diào)用了虛擬機(jī)的「隨機(jī)數(shù)發(fā)生器」，而這個(gè)隨機(jī)數(shù)發(fā)生器是能被 Zlice 操縱的?！脯F(xiàn)實(shí)世界」是外部運(yùn)行虛擬機(jī)軟件的計(jì)算機(jī)環(huán)境。

大家是不是又有所悟，我再?gòu)?qiáng)調(diào)一下：

證明零知識(shí)的過(guò)程，就是要尋找一個(gè)算法，或者更通俗點(diǎn)說(shuō)，寫(xiě)出一段代碼，它運(yùn)行在外部計(jì)算機(jī)系統(tǒng)中，但是實(shí)現(xiàn)了虛擬機(jī)的功能。而且在虛擬機(jī)中，需要有一個(gè)不帶有「知識(shí)」作為輸入的 Zlice，可以騙過(guò)放入虛擬機(jī)運(yùn)行的 Bob。

如果還沒(méi)理解上面我這句話，請(qǐng)時(shí)光回退到『區(qū)分兩個(gè)世界』這一小節(jié)，重新思考模擬。：P （Load World State from Snapshot X）

柏拉圖的洞穴寓言

模擬無(wú)處不在，哥德?tīng)柌煌陚湫远ɡ砭褪褂昧四M的概念，用哥德?tīng)枖?shù)（Godel Numbers）模擬了形式算術(shù)。圖靈提出了「Universal Turing Machine」（通用圖靈機(jī)）的概念，這種圖靈機(jī)可以模擬自身。

但最早的「模擬」概念，出自『理想國(guó)』一書(shū)的第七卷［4］中，古希臘哲學(xué)家柏拉圖講了這么一則寓言——Allegory of Cave：

設(shè)想在一個(gè)暗無(wú)天日的山洞中，有一排被鎖鏈鎖住的囚徒，他們從小就只能看到前方的墻壁。這些囚徒們身后是一堵墻，再后面有一堆放著火，在火與墻壁之間，有一些人舉著道具和木偶來(lái)回走，這樣道具木偶就會(huì)在火光映射下在墻壁上投下影子。而這些囚徒們整天就只能看著這些影子。因?yàn)檫@些囚徒們從打出生起，所聞所見(jiàn)就只是前方洞壁上的各種影子，他們會(huì)以為所看到的這些影子就是真實(shí)的世界。

然而有一天，一個(gè)囚徒偶然掙脫鎖鏈，他回頭看到了火。但是他從小到大僅能看到暗淡的影子，他第一次看到了明亮的火光?？吹搅说谰吆湍九?，假如有人告訴他，這些道具和木偶才是實(shí)物，他一定會(huì)嗤之以鼻，會(huì)堅(jiān)持認(rèn)為影子才是真實(shí)的。

柏拉圖假設(shè)說(shuō)，如果把這個(gè)囚徒強(qiáng)制拖出洞穴，到外面去看到真實(shí)的世界， 一開(kāi)始囚徒會(huì)不適應(yīng)真實(shí)世界的光亮而感到刺目眩暈，他會(huì)因此而憤怒。但是當(dāng)他慢慢適應(yīng)了這個(gè)世界，看到太陽(yáng)，樹(shù)木，河流，看到星空，他逐漸明白，這個(gè)世界比洞穴中那個(gè)世界更為優(yōu)越高級(jí)。他再也不想回到黑暗的洞穴生活中了。

過(guò)了一段時(shí)間，他對(duì)洞穴中的囚徒心生憐憫，于是想去把他們都帶出來(lái)。但是當(dāng)他再次返回洞穴中，他因?yàn)橐呀?jīng)適應(yīng)了外面明亮的世界，回到洞穴中反而看不清楚。被鎖的囚徒們反而認(rèn)為他的視力受損，胡言亂語(yǔ)，是個(gè)瘋子，最后當(dāng)他想盡辦法把這群囚徒帶出洞穴時(shí)，被囚徒們聯(lián)手殺死。

這是則人類(lèi)命運(yùn)的寓言，就和那一排被鎖鏈鎖著的囚徒類(lèi)似， 我們以為眼睛看到的就是世界的真相，但實(shí)際上，那也許是幻象，就像洞穴墻壁上投下的影子一樣。

未完待續(xù)

本文章介紹了理解零知識(shí)所需的關(guān)鍵概念——模擬。任何一個(gè)零知識(shí)的協(xié)議，都可以通過(guò)構(gòu)造一個(gè)「理想世界」來(lái)理解。第一次接觸這個(gè)概念的讀者需要反復(fù)琢磨。

計(jì)算機(jī)科學(xué)中有兩個(gè)方法論至關(guān)重要，第一個(gè)是「抽象」，第二個(gè)是「模擬」。

回顧一下在地圖三染色問(wèn)題中，Bob 在「理想世界」與「現(xiàn)實(shí)世界」中的對(duì)話。雖然 Bob 無(wú)法區(qū)分兩個(gè)世界，但是有一點(diǎn)，他可以確信：現(xiàn)實(shí)世界中，Alice 沒(méi)有超能力。