3.2.3　場景三：數獨挑戰

我們知道數獨是一種邏輯性的數字填充游戲，玩家必須以數字添進每一格，而每行、每列和每個宮（即3×3的大格）有1～9所有數字，且同一個數字在行、列、對角線中皆不重復。游戲設計者會提供一部分數字，使得謎題只有一個答案，如圖3-3所示。

小明、小麗、小剛三個好朋友很喜歡玩數獨游戲。他們三個經常互相出題給對方做。有時候，他們會找來一些非常難的題互相挑戰對方。

1．你行你證明

一天，小明想出了一道非常難的數獨題，小麗花了很長時間嘗試去解開這個數獨，但是怎么都解不出結果。小麗覺得小明在耍她，“這題壓根就無解！你做給我看看。”她跑到小明那里抱怨。

“我能證明給你看這題是有解的，而且我知道這個解。”小明淡定地回答道。

小麗想：“等你證明給我看之后，我就把解記下來然后去找小剛，給他也做一下這題。”

不料，小明卻說：“我會用零知識證明的方法給你證明我會這解這道題。也就是說，我不會把解題步驟給你看，卻能讓你信服我確實會解這道題。”

小麗半信半疑，也好奇這個零知識證明的方法。

2．證明就證明

小明準備了81（9×9）張空白的卡片放在桌上，每張紙上寫上1～9中的一個數字，然后讓小麗閉上眼睛轉過身去，隨后把這81張卡片小心翼翼地按照解的排列放在桌上，代表謎底的卡片，有數字的那一面朝下放在桌上；那些代表謎面的卡片，有數字的那一面則朝上放在桌上。

3．隨機抽查驗證

如圖3-4所示，放置好所有卡片后，小明讓小麗轉過身，睜開眼。小明對小麗說：“你不能偷看這些面朝下的卡片。”

小麗很是失望，她原本以為可以看到一個完整的解。

小明說：“我能讓你檢驗這些解，你可以隨意選擇按照行，或者按照列，或者按照3×3的九宮格來檢驗我的解。你挑一種吧。”

小麗很困惑，嘴上不住念叨著，然后告訴小明她決定選擇按照行的方法來驗證，小明接著把每一行的9張卡片收起來單獨放到一個麻布袋里。所有卡片都被收起來放在9個麻布袋里（見圖3-4）。小明接著搖了搖每個麻布袋，把里面的卡片順序都打散。最后把這9個麻布袋交給小麗。

4．不暴露題解的驗證方法

“好了，你可以打開這些布袋了，”小明對小麗說，“每個布袋里應該都有正好9張，沒有重復數字的，分別是數字1～9的卡片。”小麗打開每個布袋一看，果真是這樣，如圖3-5所示。

“可是，這證明不了什么吧？我也可以這樣做給你看。只要保證每一行都是1～9這9張卡片，不去管縱列和九宮格里的數字是不是也都是沒有重復的，不就行了？”小麗費解地問道。

小明解釋說：“可是我事先并不知道你會按照‘行’還是按照‘列’來收集卡片，或者是按照‘九宮格’。我又不是你肚子里的蛔蟲……我是按照題解來放置卡片的。”

小麗仔細想了想小明說的話，確實，一個數獨只有在有真正正確的解的情況下，才能保證每一行、每一列、每一個九宮格里的數字都是沒有重復的1～9。小明如果真的在騙她，隨機抽查至少有1/3的概率可以抓到他在騙人。

5．不信！隨機驗證多試幾次

小麗心里還是有些不服，覺得小明仍然有欺騙她的可能性，所以要求小明再把卡片復原，按照原來的方法，重新選。這樣反復驗證了幾次，每次都選一個不一樣的試驗方法。試了好多次都是一樣的結果。小麗這下不得不承認，小明要么運氣非常非常好，每次都能押中小麗會選擇哪種試驗方式，要么就是他確實知道題的解。同時也很失望，這么多次試驗下來，也還是不知道真正的解，她只知道小明放置卡片的排列里大概率每行、每列、每個九宮格都是沒有重復的數字，這就說明這題是大概率有解的，同理得證，小明很可能確實知道數獨的解。

小剛在看了這種零知識證明的方法后，三個好友養成了通過零知識證明去證明自己知道數獨題的解的習慣。畢竟每個人在解題的時候都花了很大工夫，不想輕易地把題解直接告訴別人。雖然每次零知識證明的過程很花時間，但是他們的成就感得到了滿足。

6．席卷全球的數獨風暴

通過互聯網，小明和小麗發現了全世界更多的數獨愛好者，他倆決定開一個直播間，直播解數獨。為了展現自己的聰明才智，每周開播前，小明在粉絲團里隨機抽取一個粉絲遞交的數獨，直播時，小明會把題解告訴小麗，然后由小麗用零知識證明的方法向觀看直播的人們證明這題有解，并且自己知道題解。

7．作弊風波

這一天，小明和小麗準備直播一個非常難的數獨，可是小明發現他把解出的答案落在自己家了。時間緊迫，要重新算一遍指定趕不上開播的時間。但是他和小麗還是決定開播。開播前，小明和小麗說：“咱倆假裝弄一弄零知識證明，我告訴你一會兒我會怎么選試驗方式。你只要確保每次我選的那種試驗方式（每行、每列或每個九宮格）里的數字不要重復就行。”

小麗同意了。

事后，小明和小麗把他倆這次作假的方法告訴了小剛，小剛很失望地斥責他倆：“你們這樣做和作弊有什么區別？對得起支持你們的人嗎？我再也不相信你們倆的零知識證明了！”

8．非交互式證明（Non-interactive Proofs）

小剛很不爽。他很享受之前和小明、小麗一起挑戰數獨的樂趣，但是，現在的他覺得無法信任小明和小麗。小剛想找到另一種方法來保證直播中的小明和小麗不能再這樣作假。冥思苦想之后，小剛告訴小明、小麗，他終于想到了一個好方法。小剛把自己關在屋里忙活了一整天，第二天他把小明、小麗叫來，給他們展示自己的新發明：零知識數獨非交互式證明機——“The Zero-Knowledge Sudoku Non-Interactive Proof Machine”（zk-SNIPM）。

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

這臺機器有一個控制面板，打開里面是一串旋鈕，這些旋鈕用來指示每次試驗的選擇（行——Rows、列——Columns、九宮格——Blocks），如圖3-6所示。

小剛已經設置好了試驗的序列，然后把控制面板焊死，以保證小明和小麗不會知道他到底選擇了哪一個試驗序列。

小剛可以完全信任自己這臺機器，他放心地把機器交給小明和小麗，讓他倆下次直播就直接用這臺機器來證明。

9．魔法盒子的開啟儀式

小明和小麗很羨慕小剛有這臺機器，并且想也能用這臺機器來驗證小剛自己出的數獨題。問題來了，小剛如果知道自己選了什么樣的試驗序列，那么，用這臺機器去驗證小剛自己的數獨題解，小剛就可以作弊。

怎么解決這個問題呢？其實也挺簡單的，只要把大伙聚集起來，共同把控制面板重新打開，然后由大家一起來設置控制面板上的試驗序列即可。這個過程可以稱之為“可信任的初始設置儀式”（Trusted Setup Ceremony）。

為了增加隨機性和保密性，如果把這臺機器放在一個漆黑的房間里，并且把旋鈕上的指示貼紙也都撕去。三人分別進入到這個屋子，大家進房間時蒙上眼睛來減少作弊的可能性。這樣，最后這些旋鈕所代表的試驗序列他們三個人基本上就都沒有辦法知道。即便他們三個人中有兩個人事先商量好自己會怎么選，他們也無法得知第三個人會怎么選，從而沒有辦法作假。等儀式結束之后，他們一起把控制面板焊死，這樣至少比原來的可信度增加了不少。

10．如何破解魔法盒子？

有那么一天，小明在家守著這臺機器。他開始反思它是不是像大家認為的那樣安全可靠。過了一會兒，他開始嘗試給機器故意傳送一些假的題解（只保證每行、每列或每個九宮格的數字不重復），試圖通過這種試錯來找出機器里設置的試驗序列。慢慢反復嘗試，終于把機器里的試驗序列都推斷出來了。他既興奮又沮喪，如何能設計一個更好的證明機呢？

11．故事的本質

看到這里，相信讀者又鞏固了對零知識證明的基本認知：零知識證明的本質，就是在不暴露我所知道或擁有的某樣東西的前提下，向別人證明我有很大概率（零知識證明說到底是一個概率上的證明）確實知道或擁有這個東西。

故事里要證明的，就是一個數獨題的題解，小明讓小麗每次隨機抽取行、列、九宮格的卡片，并收集在一起隨機打亂，小麗通過拆開袋子并不能知道題的解，但是卻能相信小明很大概率知道題的解。

本場景中的zk-SNIPM也是暗指零知識證明現在最普遍的zk-SNARKs（Zero-Knowledge Succinct Non-Interactive Argument of Knowledge）算法。zk-SNIPM還有改進的余地，比如用一臺掃描儀把第一次卡片的組合就全掃描下來，然后一次性同時驗證所有的試驗序列。這樣就很難用試錯的方式來破解機器。

小明和小麗最開始的那種互動式證明方法暗指的是交互式零知識證明（interactive zero-knowledge proof）。交互式零知識證明需要驗證方（小麗）在證明方（小明）放好答案（commitment）后，不斷發送隨機試驗。如果驗證和證明雙方事先串通好，那么他們就可以在不知道真實答案的情況下作弊（simulate/forge a proof）。

非交互式證明則不需要這種互動，但會額外需要一些機器或者程序，并且需要一串試驗序列，這個試驗序列不能被任何人知道。有了這么一個程序和試驗序列，證明機就能自動算出一個證明，并且能防止任何一方作假。

這里需要再升級一下，通過同態加密的方法，把采樣點隱藏起來，把加密后的點寫入區塊鏈，一樣可以完成驗證，同時還不暴露采樣點。這樣就形成了最終的zk-SNARKs。

zk-SNARKs目前也存在很多已知的問題，比如：第一步從函數到代數表達式再到多項式的轉換過于復雜，實際操作起來難度太高。采樣點的生成仍然需要依賴一個可信的操作方。這個操作方知道采樣點，可以偽造任何證明（這也是Zcash引入Trusted Setup的原因）。這個設置的過程需要在系統初始化的時候完成。如果在以太坊上，我們部署了一個新的函數，就沒法通過鏈上的方法完成這個安全的初始化，這也間接限制了其應用。

而技術的問題最終總會被技術升級所解決。零知識證明為區塊鏈帶來保護隱私的特性，有可能帶來區塊鏈的下一個爆發點。

Zcash是在2016年10月28日推出的一種新的加密貨幣。它是一個比特幣的克隆，來自比特幣代碼庫0.11的分叉，Zcash通過增加完全匿名交易的附加功能與比特幣、以太坊區分開來。因此，Zcash被譽為“不可跟蹤的”加密學貨幣。

Zcash為了實現匿名交易，采用了零知識證明的密碼學和計算機科學分支技術。即使是這個世界上最聰明的數學家也將零知識證明描述為“月球數學”，全球只有少數專門的研究人員對零知識證明運作細節有完全的了解。

零知識證明通過在公共Zcash區塊鏈上創建匿名交易來實現Zcash的“不可跟蹤”。Zcash上加密的交易隱藏了發件人和收件人的地址，以及一個地址發送給另一個地址的價值。這是獨一無二的，因為迄今為止，其他區塊鏈會顯示從一個地址到另一個地址的價值傳輸，并且區塊鏈上的任何人都可以看到此交易的值。與其他區塊鏈不同，Zcash用戶可以完全隱藏交易，唯一公開的是在某個時間點發生了某件事。

發送Zcash的地址都是匿名的，這意味著如果你不知道他們的實際身份或真實世界的地址，則無法看到貨幣從哪里流入或流出。