最接地氣的零知識證明解釋,一定要看!

買賣虛擬貨幣
本文翻譯自Aviv Zohar的博文《The Incredible Machine》。這是小編看過的最接地氣、最好理解的“零知識證明”解釋。推薦大家一定要看!本文分為兩部分,第二部分將於下期小課堂釋出。

小A、小B、小C三個小朋友是學霸,非常喜歡玩數獨遊戲,而且經常湊一起解決難題,以此證明自己更聰明。

他們還經常喜歡挑戰高難度的,比如這樣的:

小A是三個小朋友中最聰明的,他會自己出題,並且設定一些規則,給另外兩個小夥伴去解。

證明

有一天,小A出了一道非常難的題,小B花了很長時間,就是解不開,於是:

小B生氣了:“小A,這個數獨題根本無解,你這是耍我,想看我出醜!”

小A一臉王者之氣:“我能證明給你看這題是有解的,而且我知道這個解。”

小B:“行,我等著”。同時,內心OS:等你解出來之後,我就把答案記下來,再去測試小C。

小A:“我會用‘零知識證明’的方法給你證明我會解這題。也就是說我不會把解給你看,但你卻明白我確實有這題的解。”

小B:“emmm試試吧。”內心OS:別BB了,快點,我還要去看小C吃癟呢。

承諾

小A拿出81張空白卡片,在每張卡片上寫上1-9中的一個數字,並按9x9的矩陣形式,將卡片排列在桌上。代表謎底的卡片,數字面朝下放在桌上;代表謎面的卡片,數字面朝上放在桌上。

隨機挑戰

小B內心很激動,這就像學霸花很長時間沒有解出的附加題,但即將在另一個學霸那看到解題步驟和答案,能不激動嗎。

小A這時說:“小B,你不能偷看這些面朝下的卡片”。小B很失望,還以為很快就能知道答案了呢。

小A接著說:“但我能讓你檢驗這些解,你可以隨意挑一行,或一列,或者一個3x3的九宮格區域來檢驗我的解。”

小B決定挑一行來檢驗。接下來,小A把每一行的9張卡片收起來,每行單獨放到一個袋子裡。總共9行,所有卡片都被收完放在了9個袋子裡。小A搖了搖每個袋子,把裡面的卡片順序打亂,然後把9個袋子遞給小B。

小B很困惑,心想這是什麼鬼?

驗證

小A:“好了,你可以開啟袋子了。每個袋子裡應該都正好有9張卡片,這9張卡片上的數字分別是1-9。”小B開啟袋子一看,還真是這樣。

小B:“你耍賴,這根本沒有證明任何事!我也可以做到,我只要把數字從1到9按任意順序排成一行不就行了!。”

小A解釋說:“我又不會讀心術,我可不知道你事先會按照行來選,還是按照列或者九宮格來選。你之前如果按照列來選,照樣能夠得到這樣的結果。”

事實上,只有正確的解,才會得到這樣的結果,即有了正確的解,任意行、列、九宮格內的數字才會是1-9不重複的數字。如果小A的解不正確,至少有30%的概率得不到這樣的結果。

重複測試

小B還是不服氣,他根本沒有被小A說服,仍然認為這道題無解。他要求小A按照原來的方法重來一次,他重新測試。後來,他們又重新做了好多次這個測試,無論小B選擇行,還是選擇列,或者選擇一塊九宮格,都能得到相同的結果。

這下小明不得不承認,小A確實知道這道題的解,因為小A不可能運氣好到每次都壓中小B會選擇哪一行、哪一列或哪一塊,畢竟小A不是他肚子裡的蛔蟲。小A很失望,這麼多次測試做完,他還是不知道答案,他只知道每次的排列裡,很可能每一行、每一列、每個九宮格確實包含了數字1-9,並且沒有重複的數。這很有可能是小A在知道答案的情況下才能實現的。

後來小C也知道了這個方法,此後三個小夥伴養成了透過零知識證明去證明給對方看自己知道某道題的解的習慣。雖然每次證明所需的時間都很長而且還挺累人的,但每個數獨謎題都是自己花費很長時間才解出來的,才不想把答案告訴其他人呢。

越來越多的人加入遊戲

後來,小A發現世界上有成千上萬的數獨愛好者,很多人都透過線上玩。所以他決定開個抖音直播間,這樣他可以線上上釋出他獨創的數獨挑戰,讓更多人來解謎題。

做這樣直播的人很多,怎樣才能吸引更多粉絲呢?小A想了一個辦法:他和小B聯合直播,每次直播時讓小B用零知識證明的方法向觀看直播的粉絲們證明這題有解,並且自己知道這道題的解,但不會輕易告訴粉絲。就這樣,越來越多的粉絲進入直播間,想要解出小A出的謎題。不僅如此,小A還會把數獨挑戰的謎題以及證明過程拍下來,發到個人頻道上。

作假被發現了

有一天,小A又來找小B一起直播,但他發現自己把記錄謎題答案的筆記本落家裡了。開播時間馬上到了,回去拿又趕不上。於是,他和小B商量說:“我們假裝做一個零知識證明。”兩人一起商定了等會兒小B該如何“隨機地”選擇行、列、塊,因為小A事先就知道小B會選擇什麼,他只需要按照順序擺好數字就行了。

小C也看了這場直播,事後小A和小B告訴小C,這次直播作假了。小C很氣憤,覺得自己的感情受到了欺騙,並且揚言再也不會相信他們倆了,他們根本對不起那麼多粉絲對他們的喜歡。

未完待續......

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;