五分彩网站欢迎您的到來!

<font id="nttpt"><video id="nttpt"><listing id="nttpt"></listing></video></font>

<delect id="nttpt"></delect><p id="nttpt"><output id="nttpt"><font id="nttpt"></font></output></p>

<p id="nttpt"></p>
<p id="nttpt"></p>

<video id="nttpt"></video>

<p id="nttpt"><delect id="nttpt"></delect></p>
<output id="nttpt"><output id="nttpt"><font id="nttpt"></font></output></output>
<p id="nttpt"></p>

<video id="nttpt"></video>

<p id="nttpt"></p>

<p id="nttpt"></p>
<p id="nttpt"><output id="nttpt"><font id="nttpt"></font></output></p>
<video id="nttpt"><output id="nttpt"></output></video>
<video id="nttpt"></video>
<p id="nttpt"><p id="nttpt"></p></p><video id="nttpt"><p id="nttpt"></p></video>
<video id="nttpt"></video>

<output id="nttpt"></output>

<video id="nttpt"><output id="nttpt"><delect id="nttpt"></delect></output></video><p id="nttpt"></p>

<video id="nttpt"></video>
<p id="nttpt"></p>

<video id="nttpt"></video><p id="nttpt"></p>
手機版

探索零知識證明系列 從「模擬」理解零知識證明:平行宇宙與時光倒流

2019-08-06 15:02:55 來源: 巴比特 百度搜索更多類似文章,點擊進入>>>

I know that I know nothing —— 蘇格拉底

相信很多人都聽說過零知識證明,但是只有極少數人聽說過模擬,然而模擬是理解零知識的關鍵。

我們在第一篇文章『初識「零知識」與「證明」』(鏈接)[1]中介紹了一個簡單的零知識交互系統:地圖三染色問題。那么這個系統真的是零知識的嗎?我們為什么要相信這個結論呢?有證明嗎?在 Alice 與 Bob 的對話過程中,如果不零知識,Alice就被坑了。交互式系統的設計者「我」需要讓 Alice 確信,這個對話確實是零知識的。

如果從直覺主義角度解釋,要證明一個交互系統中存在信息泄露,那么你只需要指證:第幾個 bit 導致信息泄露即可;但如果要證明不存在信息泄露,那么你要對著所有信息流中的所有 bit 說,這從1,2,3,4,5,…… 編號的 bit 都沒泄露任何信息??垂賯?,這是不是很難?

本文約八千字,略微燒腦。

 

安全的定義與不可區分性

 

首先,一個交互式系統,也就是一個對話,它的「零知識」需要證明。畢竟,現代密碼學是建立在嚴格的形式化系統之上。在證明之前,還需要明確「安全假設」到底有哪些。所謂安全假設,比如我們說一個系統的權限隔離做得無比精確,每一個用戶只能看到被授權的信息,但是這基于一個安全假設:管理員賬號沒有被破解。又比如在手機銀行軟件里,只能通過短信認證碼,才能完成轉賬功能,這也基于一個安全假設:你的手機 SIM 卡沒有被克隆。如果我們深入地分析每一個我們感覺安全的系統,都存在大量的似乎不那么穩固的安全假設。比特幣私鑰安全嗎?比特幣賬戶的安全假設也不少:首先你的助記詞不能讓別人知道,手機錢包里私鑰保存加密算法足夠強,密鑰派生算法正規,你不能忘記助記詞,等等等。

脫離安全假設來談安全都是在耍流氓。一切安全都有前提的。只有經過數學證明之后,大家才能夠確信這個 算法/方案 的安全性基于一些非常明確的「安全假設」。

在證明之前,還缺少一個東西,那就是「安全定義」。在多數人的認知系統中,安全就是一個框,什么都可以往里裝。大家應該好好提醒下自己,當談論安全二字的時候,有沒有想過到底什么是安全?怎么算安全?

 

「安全」需要有一個數學意義上的嚴格定義

偉大的科學家香農(Claude Shannon)從信息論的角度給出了一個非??孔V的安全性定義[2]:

完美安全:假設你是一個攻擊者,你通過密文獲取不到任何有價值的信息,破解的唯一手段就是靠瞎蒙。

大家想一想,這個定義很有趣,通過密文獲取不到信息,這就意味著你沒有獲得任何額外的計算能力,能夠幫助讓你以更短的時間來計算出明文。

但是這個定義太完美,以至于使用的加密算法都很難滿足這個安全性定義。后來 Goldwasser 與 Micali 等人寫了另一篇載入史冊的經典『概率加密』[2]。

探索零知識證明系列  從「模擬」理解零知識證明:平行宇宙與時光倒流

在這篇論文中定義了這樣一個概念:語義安全。所謂語義安全在完美安全的定義上放松了些要求。

語義安全:假設你是一個攻擊者,你通過密文在多項式時間內計算不出來任何有價值的信息。

好了,這個看起來靠譜多了。接下來一個問題就是,怎么理解「計算不出來信息」這個概念?這看來要對信息進行度量,信息的定義又是什么呢?

我們又引入一個概念——「不可區分性」,來重新表述加密算法的安全性:假設你是一個攻擊者,而我有一個加密算法:

  1. 你隨機產生兩段等長的明文,m1=「白日依山盡,黃河入海流」,m2=「燙燙燙燙燙,燙燙燙燙燙」
  2. 你把這兩段明文,m1 與 m2 交給我
  3. 我隨機挑選一個明文,不告訴你是哪一個,然后進行加密,產生一個密文 c
  4. 我把密文 c 出示給你看,讓你猜這個c 究竟是由唐詩加密產生,還是亂碼加密產生
  5. 如果你用一臺計算機來破解c,在多項式時間內破解不出來,也就是說你沒辦法區分c的來源,那么就說明加密算法是語義安全的

OK,理解完「不可區分性」,我們再回到「零知識」,如何證明一個交互式系統是「零知識」呢?首先我們要定義下零知識這個概念。

注:不可區分性是概率意義上的不可區分;在學術上,它可以分為「完全不可區分」,「統計不可區分」,還有「計算不可區分」。在本文中,我們暫時不需要理解這些概念的差別。

 

遇見模擬器

 

先開個腦洞,設想在平行宇宙中,有兩個平行的世界,一個叫做「理想世界」(Ideal World),另一個叫做「現實世界」(Real World)。我們每一個個體可以在兩個平行世界中愉快地玩耍,但是兩個世界的普通人無法互相感知,也無法互相溝通。

假設「你」是一個很厲害的密碼破解者,而且「你」不是普通人,具備在平行宇宙之間穿梭的能力。而 Alice 有一個地圖三染色的答案,你的目的是通過和 Alice 對話來獲取地圖三染色的答案,會話的過程參考上一篇文章的「地圖三染色問題」協議。

繼續腦洞,Alice 只存在「現實世界」中;在「理想世界」,Alice 被「替換」成了一個長相與聲音一模一樣的個體,我們稱替身為 Zlice。下一步,把「你」同時放入兩個世界中,但不讓你知道是你當前位于哪一個世界。你的兩個分身所面對的都是一個 “Alice”模樣的人。

再重復一遍,在「現實世界」中, 與你對話的是一個真實的,并且誠實的 Alice;而在「理想世界」中,與你對話的是 Zlice (假 Alice),Zlice 雖然相貌語言與 Alice 并無二致,但差異是,Zlice 并不知道「知識」,即不知道一個三染色問題的答案。

接下來在這兩個世界中,你的兩個分身將同時與真假 Alice 進行對話。神奇的事情發生了,最終在兩個世界中,你的兩個分身都被說服了,都經過n輪挑戰,沒有發現對方作弊,即「你」的兩個分身都認為對方確實知道「答案」。換句話說,「你」沒有能力「區分」出來自己到底在 「現實世界」 還是 「理想世界」,當然也沒能力「區分」和自己對話的究竟是 Alice 還是 Zlice。不僅如此,對于吃瓜群眾我而言,如果把「我」作為觀察者放入任何一個世界中,我會和你一樣「無法區分」出來眼前的 這個長相為 “Alice” 的人到底是真還是假。

探索零知識證明系列  從「模擬」理解零知識證明:平行宇宙與時光倒流

下面是燒腦結論:

這個交互系統為何是「零知識」?因為 Zlice 是沒有任何知識,而且她和 Alice 不可區分。

我再換個方式解釋:因為你和我都沒辦法區分我們究竟是在哪個世界中,兩個世界發生的交互過程幾乎不可區分,而且其中一個世界中根本就不存在知識,因此,我們說這個交互協議——「地圖三染色問題」是「零知識的」。

這里還有個前提,理想世界必須是算法可構造的。然后,有一個「神」,他通過算法「模擬」了一個「理想世界」,其中構造了一個算法叫做 Zlice,她沒有「知識」作為輸入,也即「零知識」;除此之外,「理想世界」與「現實世界」一模一樣。

設想你在對話過程中,如果真 Alice 泄露了信息,那么你就能立即區分出面前這個人是 真 Alice 還是 Zlice,Zlice 是不可能偽裝泄露信息的。因此可以得出結論:

真Alice 沒有泄露任何信息。

這個神,被稱為「模擬器」(Simulator),而在理想世界中,和你對話的這個 Zlice 幻象其實也是「模擬器」,你在理想世界中,所有能感知到的東西都是模擬器「模擬」出來的。

好了,到這里,我們用「模擬器」這個概念對「零知識」進行了定義。

接下來,我們開始進入證明零知識的環節。

 

區分兩個世界

(Save World State as Snapshot X)

證明的零知識過程,等價于構造(尋找)一個「模擬」算法,這個算法能夠讓模擬器來模擬出一個「沒有知識」的理想世界。如果這個算法存在,而且兩個世界不可區分,那么就證明完畢。

等等,可能「你」會覺得哪里不對勁。

假如說真的存在這種算法,而且它能夠在沒有知識的情況下騙過我,那么在「現實世界」中,不排除真 Alice 也使用了這樣的算法來欺騙我。這樣一來,我豈不是在兩個世界中都被欺騙了。那么這個交互協議就失去意義了。

探索零知識證明系列  從「模擬」理解零知識證明:平行宇宙與時光倒流

其實,這里有個關鍵點,借用電影『盜夢空間』中的劇照,在「理想世界」中有點東西是和「現實世界」本質不同的。這個東西是區分兩個世界的關鍵,而它要讓我們「無法感知」。這個東西不是夢境中的陀螺,它是一種「超能力」,模擬器 Simulator 所具備的超能力。

比如這樣一種超能力:「時光倒流」。

探索零知識證明系列  從「模擬」理解零知識證明:平行宇宙與時光倒流

(上圖是電影『土撥鼠之日』的劇照,劇中主人公每次睡醒都會回到2月2日的早上,這樣他永遠活在同一天里)

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

設想下在我們周圍,如果有一個人有時空穿越能力,或者他能讓時間回退到一年前,那么我們這些凡夫俗子完全是一臉茫(meng)然(bi)的,無從感知。那么,如果「模擬器」可以在他構造出的「理想世界」中實現「時間倒流」,那么他就可以達成一些神奇的事情,從而騙過作為驗證者身份的「你」,也能騙過觀察者「我」。對于「你」而言,你明白,在「理想世界」中,時間是可以回退的,但是在「現實世界」中,顯然真 Alice 不可能擁有超能力。雖然你和我不能區分在哪個世界里,但是至少我們知道在兩個世界中的其中「現實世界」里,對面那個Alice是沒辦法欺騙我們的,當然我們卻不能說出我們到底在哪個世界中。

到此,交互協議的「零知識」已經證明完了。各位是否已經明白了?我再給大家再梳理下證明思路:

首先「零知識」是為了保護 Alice 的利益,因為 Alice 不想在交互過程中透露更多的信息給 Bob,不想讓 Bob 知道她所擁有的秘密 w,甚至不想讓 Bob 從交互的過程中分析出哪怕一丁點的信息。那么怎么保證這一點呢?「模擬器」這時候登場了,它能模擬出一個和現實世界外表一模一樣的「理想世界」,然后「模擬器」在這個世界中可以輕松地騙過任何一個對手,讓對方無法分辨自己是在現實世界中,還是理想世界中。因為「模擬器」手里沒有那個秘密 w,「理想世界」是零知識的。又因為兩個世界的不可區分性,所以我們可以得出結論:Alice 的交互協議是「零知識」的。

我們來看一個具體的例子,上一篇文章[1]中提到的地圖3染色問題。

 

地圖三染色問題的零知識證明

 

回憶一下「地圖三染色問題交互系統」:

探索零知識證明系列  從「模擬」理解零知識證明:平行宇宙與時光倒流

  • 第一步:Alice 把地圖染色答案做一次完全置換,然后將所有頂點蓋上紙片,交給 Bob
  • 第二步:Bob 隨機挑選一條邊
  • 第三步: Alice 打開指定邊的兩端頂點的紙片,Bob檢驗兩個頂點的顏色是否相同,如果不同則通過,如果相同則失敗
  • 回到第一步,重復 n 遍

我們接下來就來證明上述這個交互是零知識的,這里先假設驗證者 Bob 是誠實的,這有助于大家理解這個證明過程。然后我們再討論,如果 Bob 不誠實的證明方法。

探索零知識證明系列  從「模擬」理解零知識證明:平行宇宙與時光倒流

在「理想世界」中,跟 Bob 對話的是一個「模擬器」,它模擬出了整個世界的樣子。Bob 按照三染色問題的交互協議進行交互。模擬器并沒有一個三染色答案,它索性把所有的頂點都染成了灰色。

探索零知識證明系列  從「模擬」理解零知識證明:平行宇宙與時光倒流

首先,模擬器模仿 Alice ,把每個頂點用紙片蓋起來。然后發給 Bob。

探索零知識證明系列  從「模擬」理解零知識證明:平行宇宙與時光倒流

Bob 隨機挑選了一條邊,挑戰證明者。

探索零知識證明系列  從「模擬」理解零知識證明:平行宇宙與時光倒流

模擬器這時候不能打開紙片,因為這條邊兩端的顏色都是灰色啊。

探索零知識證明系列  從「模擬」理解零知識證明:平行宇宙與時光倒流

這時候,模擬器要發揮「超能力」了,他運用時間倒流的技能,回到對話第一步之前。

探索零知識證明系列  從「模擬」理解零知識證明:平行宇宙與時光倒流

模擬器現在處于第一步,他把最下面那條邊的兩端染上任意不同的顏色,然后重新蓋上紙片,并發給 Bob。

探索零知識證明系列  從「模擬」理解零知識證明:平行宇宙與時光倒流

Bob 這時候無法感知到時間已經倒退回第一步了,對他來說,一切都是新鮮的,他「誠實」地再次選擇了最下面的邊。

探索零知識證明系列  從「模擬」理解零知識證明:平行宇宙與時光倒流

這時候模擬器就可以放心地打開紙片,讓 Bob 檢查。Bob 很顯然會被騙過。然后 Bob 一輪輪地重復這個過程,每一次模擬器都能用時間倒流的方式騙過 Bob。

于是在理想世界中,模擬器并沒有任何三染色答案的「知識」,卻同樣能騙過Bob,并且從概率上來看,與「現實世界」中被觀察到的交互過程高度地一致(完全一致的概率分布)。于是上面的過程展示了模擬器的算法的存在性,也就相當于證明了交互系統的「零知識性質」。

不誠實的 Bob

在上面的證明過程中,有一個相當強的假設,就是每次時間倒流之后,Bob都會選擇同一條邊。如果 Bob 每次都會換一條不同的邊呢?沒關系,如果在模擬器第一次實施時間倒流之后,Bob又選擇了不同的邊,那么模擬器可以把顏色打亂之后,再次運行時間倒流,在多次時間倒流之后,Bob 極大的概率總會一次選擇模擬器進行染色的那條邊,然后這時候模擬器才走到第三步,打開紙片。

 

阿里巴巴、洞穴與芝麻開門

 

在網上眾多的講解「零知識證明」的中文科普文章中,有一個例子流傳非常廣,這就是阿里巴巴與強盜的故事??上У厥?,這些不同版本的故事都只講了一半。那么我接下來講一個不一樣的「阿里巴巴」與「四十大盜」的故事:

在很久很久以前,在一個叫做巴格達的城市里,住著一個人叫阿里巴巴。每天阿里巴巴會到集市上買東西。

有一天,阿里巴巴被一個盜賊搶了錢包,于是他一路追著盜賊到了一個山洞口,然后盜賊就消失了。阿里巴巴發現洞口里面有兩條岔路,如下圖所示。

探索零知識證明系列  從「模擬」理解零知識證明:平行宇宙與時光倒流

阿里巴巴不知道盜賊往哪邊跑了,于是他決定去「左邊」岔道看看,很快阿里巴巴就發現這是個死胡同,也不見盜賊蹤影。然后他又去「右邊」岔道檢查,也是個死胡同,不見盜賊蹤影。阿里巴巴自言自語道:「該死的盜賊跑哪去了呢?」

第二天,阿里巴巴又去集市買東西,這次另一個盜賊搶了他的籃子,然后阿里巴巴追著這個盜賊到了昨天同樣的山洞口,然后盜賊又不見了,這一次阿里巴巴決定先去「右邊」岔道看看,沒有發現盜賊,然后再去左邊看看,也同樣不見盜賊。這好奇怪。

第三天,第四天,……,第四十天,同樣的故事上演,阿里巴巴追著第四十個大盜到了神秘的洞口,盜賊就消失了。阿里巴巴想,這個山洞里面一定有機關,于是他躲在「右邊」岔道的盡頭,耐心地等了很長時間,這時一個盜賊跑了進來,走道岔道盡頭之后,念了一個咒語「芝麻開門」。這時候墻壁居然打開了,盜賊跑進去之后,然后墻壁又合上了,這時候另一個受害者追了進來,找了半天,一無所獲。

阿里巴巴隨后等他們走了之后,試驗了一下這個咒語,果然非常有效,而且阿里巴巴發現這個墻壁通向「左邊」岔道。后來,阿里巴巴找到了更換咒語的辦法,并且把一個新咒語和洞穴的地理位置寫在了一張羊皮紙上。

注:到這里,故事并沒有結束…. (上字幕)很久很久以后

在很多年后,到了80年代,阿里巴巴的羊皮紙流落到了幾個密碼學家手里,他們跑到巴格達,找到了洞穴的位置,盡管過了幾個世紀,咒語居然仍然有效,這幾個密碼學家興奮地打開墻壁,在兩個岔道之間跑來跑去。

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

節目非常成功。但很快,另外一個電視臺眼紅,也想拍一個類似的節目,但是Mick Ali 因為簽了獨家協議,沒辦法參與這個新節目。怎么辦呢?第二個電視臺的主持人心生一計,他找了一個和 Mick Ali 很像的演員,穿著打扮、姿態和說話口音都模仿 Mick Ali。然后他們開拍了,每次主持人擲硬幣后,都讓這個演員跑出來,但是很顯然,演員并不知道咒語,沒辦法打開那個墻壁。于是有時候演員碰巧會成功,有時候則會失敗,于是演員很辛苦,重復了將近一百次,才成功了四十次。最后這個狡猾的新節目主持人,把錄制視頻進行了剪輯,只保留了成功的片段,錯誤的片段都刪除了。然后這個新節目和 Mick Ali 的節目在同一時間,不同頻道播出。然后觀眾們完全無法區分哪個視頻是真的,哪個視頻是假的。第一個電視臺的主持人完全明白 Mick Ali 是真正知道墻壁的咒語的人,但是他卻不能把這個事實傳遞給無辜的觀眾們。

看到這里,大家是不是對「模擬」慢慢有了感覺?這里第二個電視臺的主持人通過剪輯視頻的方式,而不是「時間倒流」。他對「理想世界」,也就是電視中播出的內容所在的世界,進行了外部干預,達到了同樣的效果。對理想世界而言,這種剪輯本質上就是一種超能力。

這個故事其實來源于一篇論文『如何向你的孩子解釋零知識證明』(How to Explain Zero-Knowledge Protocols to Your Children)[3],發表在1989年的美密會議上。

探索零知識證明系列  從「模擬」理解零知識證明:平行宇宙與時光倒流

模擬與圖靈機

 

一談到超能力,大家有沒有覺得這玩意不科學。是的,如果我們無腦地用「超能力」來解釋任何事情,那么我們邏輯就無法自?。–onsistent)。在理想世界中,模擬器是不能隨便開掛的,比如模擬器肯定不能直接修改 Bob 的內部狀態,比如 Bob 在驗證步驟明明驗證失敗,但是模擬器強硬去把驗證結果改為「接受」,這會導致我們可以證明:「任何的交互系統都是零知識的」,這個錯誤結論。

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

那么模擬器到底可以是什么呢?模擬器其實只是一個圖靈機。所謂的「時間倒流」,「剪輯錄像」這類的所謂超能力并不是玄乎的超自然能力,而是圖靈機可以實現的功能。計算機專業的朋友們肯定都用過 VMWare,虛擬機之類的軟件,本文講的「模擬器」完全可以想象成一個「虛擬機」軟件,它能虛擬出一個計算機環境,這個虛擬環境就是我們上文說的「理想世界」?!笗r間倒流」如何解釋呢?不知道大家有沒有用過虛擬機軟件的「快照」功能(Snapshot),使用快照的時候,虛擬機軟件可以把整個虛擬計算機的所有狀態保存下來,然后在任意時刻,虛擬機軟件都可以重新回到保存快照的位置繼續運行。

注:其實所謂時間倒流是計算機中的一個基本操作,在程序語言理論中有一個概念叫做 Continuation。抽象地講,Continuation 表示從現在開始到未來的計算。Continuation這是控制流的一個顯式抽象,而 goto,call-with-current-continuation,甚至 thread scheduling 都可以看做是操作 Continuation 的操作符。比如采用call/cc,也就是call-with-current-continuation 就可以輕松地實現「回溯」功能。保存快照可以理解為保存當前的 Continuation,而回到過去的某一刻,就是應用這個Continuation。

不管 Zlice 還是 Bob,還有我們的每一個觀察者,都是一個個可執行程序。這些程序被拷貝到了虛擬機里。Zlice 與 Bob 的會話實際上就是這兩個程序之間的通訊。觀察者是 Hook 在 Zlice 與 Bob 進程 IO 上的程序。在上文的地圖三染色「理想世界」的誠實 Bob,實際上是 Bob 進程調用了虛擬機的「隨機數發生器」,而這個隨機數發生器是能被 Zlice 操縱的?!脯F實世界」是外部運行虛擬機軟件的計算機環境。

大家是不是又有所悟,我再強調一下:

證明零知識的過程,就是要尋找一個算法,或者更通俗點說,寫出一段代碼,它運行在外部計算機系統中,但是實現了虛擬機的功能。而且在虛擬機中,需要有一個不帶有「知識」作為輸入的 Zlice,可以騙過放入虛擬機運行的 Bob。

如果還沒理解上面我這句話,請時光回退到『區分兩個世界』這一小節,重新思考模擬。:P (Load World State from Snapshot X)

 

柏拉圖的洞穴寓言

 

模擬無處不在,哥德爾不完備性定理就使用了模擬的概念,用哥德爾數(Godel Numbers)模擬了形式算術。圖靈提出了「Universal Turing Machine」(通用圖靈機)的概念,這種圖靈機可以模擬自身。

但最早的「模擬」概念,出自『理想國』一書的第七卷[4]中,古希臘哲學家柏拉圖講了這么一則寓言——Allegory of Cave:

探索零知識證明系列  從「模擬」理解零知識證明:平行宇宙與時光倒流

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

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

柏拉圖假設說,如果把這個囚徒強制拖出洞穴,到外面去看到真實的世界, 一開始囚徒會不適應真實世界的光亮而感到刺目眩暈,他會因此而憤怒。 但是當他慢慢適應了這個世界,看到太陽,樹木,河流,看到星空,他逐漸明白,這個世界比洞穴中那個世界更為優越高級。他再也不想回到黑暗的洞穴生活中了。

過了一段時間,他對洞穴中的囚徒心生憐憫,于是想去把他們都帶出來。但是當他再次返回洞穴中,他因為已經適應了外面明亮的世界,回到洞穴中反而看不清楚。被鎖的囚徒們反而認為他的視力受損,胡言亂語,是個瘋子,最后當他想盡辦法把這群囚徒帶出洞穴時,被囚徒們聯手殺死。

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

 

未完待續

 

本文章介紹了理解零知識所需的關鍵概念——模擬。任何一個零知識的協議,都可以通過構造一個「理想世界」來理解。第一次接觸這個概念的讀者需要反復琢磨。

計算機科學中有兩個方法論至關重要,第一個是「抽象」,第二個是「模擬」

回顧一下在地圖三染色問題中,Bob 在「理想世界」與「現實世界」中的對話。雖然 Bob 無法區分兩個世界,但是有一點,他可以確信:現實世界中,Alice 沒有超能力。

問題來了,Alice 沒有超能力,并不能直接證明 Alice 真的有答案。萬一這個交互協議并不能保證 Alice 一定有知識呢?「零知識」保護了 Alice 的利益,誰來保證 Bob 的利益呢?這個問題留給下一篇。

參考文獻

[1] 初識「零知識」與「證明」. 安比實驗室. 2019.

[2] Shafi Goldwasser and Silvio Micali, Probabilistic Encryption, Special issue of Journal of Computer and Systems Sciences, Vol. 28, No. 2, pages 270-299, April 1984.

[3]Quisquater, J.J., Quisquater, M., Quisquater, M., Quisquater, M., Guillou, L., Guillou, M.A., Guillou, G., Guillou, A., Guillou, G. and Guillou, S., 1989, August. How to explain zero-knowledge protocols to your children. In Conference on the Theory and Application of Cryptology (pp. 628-631). Springer, New York, NY.

[4] 柏拉圖 and 吳獻書, 1986. 理想國 (Vol. 1, No. 986, p. 1). 商務印書館.

[5] Goldwasser, Shafi, Silvio Micali, and Charles Rackoff. “The knowledge complexity of interactive proof systems.” SIAM Journal on computing 18.1 (1989): 186-208.

[6] Oded, Goldreich. “Foundations of cryptography basic tools.” (2001).

[7] Rackoff, Charles, and Daniel R. Simon. “Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack.” Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1991.

[8] Goldreich, Oded, Silvio Micali, and Avi Wigderson. “Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems.” Journal of the ACM (JACM) 38.3 (1991): 690-728.

[9] zkPoD: 區塊鏈,零知識證明與形式化驗證,實現無中介、零信任的公平交易. 安比實驗室. 2019.

 

作者:郭宇

來源:安比實驗室

本文標題:探索零知識證明系列 從「模擬」理解零知識證明:平行宇宙與時光倒流
本文地址:http://www.admun.site/coin/news/115041.html
風險提示 >>本站所提供資訊信息不代表任何投資暗示!

其他人都在看

你可能感興趣
五分彩网站 幸运飞艇全天开奖计划 北京PK10全天计划 欢乐生肖开奖计划 腾讯分分彩
<font id="nttpt"><video id="nttpt"><listing id="nttpt"></listing></video></font>

<delect id="nttpt"></delect><p id="nttpt"><output id="nttpt"><font id="nttpt"></font></output></p>

<p id="nttpt"></p>
<p id="nttpt"></p>

<video id="nttpt"></video>

<p id="nttpt"><delect id="nttpt"></delect></p>
<output id="nttpt"><output id="nttpt"><font id="nttpt"></font></output></output>
<p id="nttpt"></p>

<video id="nttpt"></video>

<p id="nttpt"></p>

<p id="nttpt"></p>
<p id="nttpt"><output id="nttpt"><font id="nttpt"></font></output></p>
<video id="nttpt"><output id="nttpt"></output></video>
<video id="nttpt"></video>
<p id="nttpt"><p id="nttpt"></p></p><video id="nttpt"><p id="nttpt"></p></video>
<video id="nttpt"></video>

<output id="nttpt"></output>

<video id="nttpt"><output id="nttpt"><delect id="nttpt"></delect></output></video><p id="nttpt"></p>

<video id="nttpt"></video>
<p id="nttpt"></p>

<video id="nttpt"></video><p id="nttpt"></p>