零知識證明-隱私問題的解決方案

採用零知識證明最知名的技術就是匿蹤幣 Zcash 的  zk-SNARKs 。目前主流加密貨幣,不論是比特幣以太幣都是匿名資訊公開,簡單來說就是不會有人知道錢包的主人是誰,但是大家都知道這錢包有多少錢、做過哪些交易,這將大幅降低人們使用的意願。請想像一下,在加密貨幣支付的生活下,你想瞞著你老婆買 SWITCH,雖然他不直接擁有錢包,但他卻能看到你的錢包轉帳金額,與轉到哪個錢包,輕輕鬆鬆就能查出你做的好事。
零知識證明是一個相當有趣的驗證方式,能夠在不公開交易資訊的情況下,礦工還能夠驗證交易的有效性以太坊創辦人Vitalik Buterin 也多次公開讚賞zk-SNARK的零知識證明技術,並表示此技術有助於提升以太坊的交易速度。

零知識證明

究竟零知識證明是什麼意思呢? 用一個有趣的方式跟大家解釋。

零知識證明-wally

小時候沒有智慧型手機也沒有電腦玩,唯一的樂趣就是玩 Where is Wally ,找出圖片中Wally在哪裡,大家可以玩玩看,回味一下沒有3C的童年時光,如果你找了十分鐘還是找不到,開始懷疑我在騙你,Wally根本不在圖片裡的時候,零知識證明就能太上用場了!

零知識證明的概念就是「不透漏詳細資訊的情況下,證明自己知道真相」。如果我直接告訴你Wally在哪裡,那你就沒辦法繼續玩了,所以我給了你一張Wally的截圖:

零知識證明-wally thumbnail

透過這張圖,除了能夠證明Wally真的存在,而且我知道在哪裡之外,由於你不知道Wally的實際位置,你還能夠繼續尋找Wally,零知識證明就是這麼簡單的概念。

交互式零知識證明

了解零知識證明之後,我們再來介紹什麼是交互式零知識證明,我們一樣用童年遊戲來跟大家解釋。

有一天阿菜出了一道數獨的題目給阿平,阿平回家玩了三天三夜,發現根本解不出來,由於阿菜平常做人不老實,阿平懷疑阿菜的這道題目根本沒有答案,只是隨便填幾個數字進去,於是隔天氣沖沖地跑去找阿菜。

但是阿菜覺得自己秀才遇到兵,有理說不清,這道題目明明就是好不容易設計好的,於是阿菜就決定用一個方式證明給阿平看,讓他知道這道題目是真的有解。

阿菜先讓阿平轉過身去,阿菜拿出81(9×9)張空白的卡片放在桌上,在每張紙上寫上1-9中的一個數字,然後把這81張卡片按照解答順序排列在桌上,代表謎底的卡片,數字面朝下放在桌上,公開數字的卡片,則數字面朝上放在桌上。

零知識證明-數讀1

排好之後,阿菜叫阿平轉過身,跟阿平說「現在我全部都按照順序擺好了,但是我不會讓你看答案,你可以隨意選擇按照行、列或按照3×3的九宮格來檢驗,你可以隨便選一種。」

阿平不知道阿菜葫蘆裡賣甚麼藥

「不給看答案,就能讓我知道你沒騙我,我看你搞甚麼花樣,我在 “行” 與 “列” 當中選擇檢驗 “行”。」

於是阿菜按照順序將每一行的牌收起來,裝在麻布袋裡,並將所有的牌搖散。

零知識證明-數讀2

「好了,你隨便選一袋吧,只要袋子裡的數字是1~9就代表我的題目沒有錯。」

阿平把每一個袋子打開,仔細檢查每一個袋子裡的牌,結果數字確實都是1~9沒有重複,但是阿平很不服氣。

「那又怎樣,雖然”行”的數字沒有重複,那也不代表”列”跟”九宮格”裡的數字沒有重複阿。」

阿菜解釋

「可是我事先也不知道你會按照”行”、”列”還是按照”九宮格”來檢驗啊。我是按照題解來放置卡片的,你選啥我都沒在怕的」

阿平想了想,確實,一個數獨只有真正正確的解才能保證每一行、每一列、每一個九宮格里的數字都是沒有重複的1-9。阿菜如果真的在騙他,阿平也至少有1/3的概率可以抓到他在騙人。

阿平又按照同樣的方式輪流將”行”、”列”和”九宮格”檢驗了好幾遍,結果袋子裡的數字真的都沒有重複。

藉由這個故事,我們發現,阿平選擇”行”、”列”和”九宮格”,阿菜再將卡片收集起來交給阿平驗證,像這樣一來一往,不斷提出證據給對放驗證,就是所謂的「交互式零知識證明」。

「交互式零知識證明」需要驗證方(阿平)在證明方(阿菜)放好答案後,不斷的發送隨機試驗,是最簡單的零知識證明與驗證方式。

就像是我們打電話給銀行客服,客服人員會詢問你的出生年月日與身分證字號,來驗證你是否為本人。然而,這種方式只有建立在驗證方與證明方對立的情況下才能成功,一旦牽涉到第三方,驗證和證明雙方事先串通好,那麼他們就可以在不知道真實答案的情況下作弊。因此衍生出了另一種證明與驗證方式「非交互式零知識證明」。

非交互式零知識證明

後來阿平跟阿菜找了阿佑一起玩數獨,阿平跟阿菜向阿佑展示了這個驗整方式,阿平將”行”、”列”和”九宮格”檢驗了一輪後,只見阿佑沉默不語,若有所思。

隔天阿佑找來阿菜跟阿平

「你們平常最愛胡搞瞎搞,我很難信任你們,昨天你們的驗證方式,如果你們兩個串通好,那檢驗出來的答案就不值得相信,所以我做了這台機器『零知識數獨非交互式證明機』。」

這台機器基本上就是把阿菜和阿平之前當面做的那套證明自動化,不再需要人為交互驗證。阿菜只要把卡片放在傳送帶上,機器會自動選擇按行,或列,或九宮格來收取卡片,放到袋子里打亂順序,然後把袋子通過傳送帶再送出來。然後阿菜就可以當著大家的面拆開袋子展示裡面的卡片。

零知識證明-證明機

機器裡有控制面板,可以設置檢驗”行”、”列”和”九宮格”的檢驗順序,阿佑把驗證順序設定好之後就把外殼焊死,沒有任何人會知道驗證順序,阿佑就能放心的和他們倆玩數讀了。

但是現在換阿菜跟阿平兩人不開心了,驗證的順序只有阿佑知道,這樣他不就有機會搞鬼了。於是,他們三個人集結起來,讓阿佑再次把外殼打開,然後大家一起設置控制面板上的驗證順序。這個過程稱為“可信任的初始設置儀式(trusted setup ceremony)”。

阿菜提議把這台機器放在一個漆黑的屋子裡,把旋鈕上的指示貼紙都撕掉。三人輪流進入屋子,阿平還提議大家進房間時蒙上眼來保證隨機性。這樣,最後這些旋鈕所代表的驗證順序他們三個人都沒有辦法知道,就能保證這驗證結果的可信度了。

「交互式零知識證明」之所以存在風險,是因為過程中需要需要在證明方與驗證方雙方交互驗證,但「非交互式零知識證明」則不需要這種互動,但是會額外需要一些機器或程式,並且需要一串試驗序列,這個試驗序列不能被任何人知道,才能維持驗證的公正性。有了這麼一個程序和試驗序列,證明機就能自動算出一個證明,並且能防止任何一方作假。

運用在區塊鏈的零知識證明所採用的就是「非交互式零知識證明」,將交易資訊交給程式,程式會給出一份證明給礦工驗證,礦工雖然不知道交易的詳細資訊,卻能夠透過這份證明,驗證交易的有效性。最有名的例子就是 Zcash 的 zk-SNARKs 零知識證明技術。

總結

透過這些故事,我們就能知道零知識證明的本質,就是在不透漏我所知道或擁有的某樣東西的前提下,向別人證明我有很大機率(這點很重要,零知識證明只是一個概率上的證明)確實知道或擁有這個東西

將零知識證明的概念運用在區塊鏈上,除了解決加密貨幣的隱私問題外,零知識證明還能夠提升網路的效率。藉由 zk-SNARKs 礦工可以不用再重新執行交易的運算,而是只要對方提得出證明即可,能夠將大量信息量壓縮,大幅提升網路的吞吐量。

本文由 AMIS 首席科學家 – 陳昶吾博士協助審閱

相關文章