簡(jiǎn)約而不簡(jiǎn)單，“零知識(shí)證明”曾被純數(shù)學(xué)家看不起，如今相關(guān)研究者已獲得2021年阿貝爾獎(jiǎng) | 對(duì)話專家

近日，備受矚目的數(shù)學(xué)界大獎(jiǎng)阿貝爾獎(jiǎng)開出 “雙黃蛋”，獲獎(jiǎng)?wù)呤菙?shù)學(xué)和計(jì)算機(jī)領(lǐng)域大佬：一位是匈牙利數(shù)學(xué)家拉茲洛?洛瓦茲（László Lovász），一位是以色列計(jì)算機(jī)科學(xué)家阿維?威格森（Avi Wigderson）。

兩位數(shù)學(xué)家因?yàn)閷?duì)零知識(shí)證明的研究，而獲此殊榮。懂行的朋友可能會(huì)大跌眼鏡，什么？！就是那個(gè)曾經(jīng)讓純數(shù)學(xué)家看不起的零知識(shí)證明，獲了數(shù)學(xué)界舉足輕重的阿貝爾獎(jiǎng)？

沒錯(cuò)！兩位數(shù)學(xué)家正是因此獲獎(jiǎng)，正如頒獎(jiǎng)詞所說：“表彰其在理論計(jì)算機(jī)科學(xué)和離散數(shù)學(xué)方面做出的杰出貢獻(xiàn)，以及在將之塑造為現(xiàn)代數(shù)學(xué)中心領(lǐng)域中發(fā)揮的主導(dǎo)作用?！?/span>

沒有聽說過零知識(shí)證明的朋友可能覺得這是個(gè)深?yuàn)W復(fù)雜的數(shù)學(xué)理論，其實(shí)不然，相信大家在日常生活中都曾接觸過。例如，QQ 賬號(hào)在設(shè)置密碼后，在不輸入密碼的前提下，通過回答密保問題證明你是賬戶的主人，這就是零知識(shí)證明的一個(gè)實(shí)際應(yīng)用。

另外一個(gè)例子就是，由圖靈獎(jiǎng)獲得者姚期智于 1982 年提出的 “百萬富翁” 問題，即兩位富翁想要知道誰更富有，但都不愿意透露自己的財(cái)富值。借助數(shù)學(xué)算法，兩位富翁不需要告知對(duì)方自己的財(cái)富值是多少，他們只需要將自己的財(cái)富值都進(jìn)行同一個(gè)運(yùn)算，然后兩人公開計(jì)算結(jié)果，通過各自對(duì)比財(cái)富值和計(jì)算結(jié)果，他們就能知道究竟誰更富有了。

這個(gè)問題的背后，本質(zhì)上反映了基于用戶數(shù)據(jù)挖掘的服務(wù)數(shù)據(jù)的使用權(quán)、所有權(quán)之間的矛盾：服務(wù)提供者必須得到你的數(shù)據(jù)才能提供服務(wù)。放到 “百萬富翁” 問題中，互聯(lián)網(wǎng)服務(wù)一定要拿到兩位富翁的財(cái)產(chǎn)數(shù)據(jù)，才能計(jì)算出 “誰更富有”。

有沒有一種技術(shù)，可以實(shí)現(xiàn)數(shù)據(jù)使用權(quán)、所有權(quán)的分離，生產(chǎn)方保有數(shù)據(jù)的所有權(quán)而不影響數(shù)據(jù)需求方提供服務(wù)？零知識(shí)證明就可以為這種技術(shù)提供算法。

零知識(shí)證明，所謂 “零”，就是不透露任何關(guān)于密碼的核心信息。所謂 “證明”，就是回答相關(guān)問題，答案都正確，就能證明賬戶是你的。

零知識(shí)證明比起其他復(fù)雜算法更為簡(jiǎn)單，卻因此受到了 “純” 數(shù)學(xué)家們的嘲笑，但為什么偏偏是兩位研究它的大佬，獲得了阿貝爾獎(jiǎng)？

因?yàn)樗麄儗?duì)于零知識(shí)證明的研究，不僅對(duì)現(xiàn)代數(shù)學(xué)核心計(jì)算有重大貢獻(xiàn)，而且有巨大的現(xiàn)實(shí)意義：

其一，零知識(shí)證明對(duì)數(shù)字貨幣的認(rèn)證意義重大；

其二，零知識(shí)證明還可以用于人的身份驗(yàn)證，即在不透露密碼的前提下，驗(yàn)證方通過一系列問題來讓對(duì)方提供 “我知道正確密碼”，或在信息安全領(lǐng)域，提供 “我就是本人” 的證明。

從 20 世紀(jì) 70 年代初，第四代大規(guī)模集成電路計(jì)算機(jī)誕生以來，算法便不再只是數(shù)學(xué)領(lǐng)域的研究對(duì)象，也成為計(jì)算機(jī)領(lǐng)域的研究重點(diǎn)。

伴隨著數(shù)學(xué)和計(jì)算機(jī)的發(fā)展，算法的側(cè)重點(diǎn)發(fā)生了明顯的轉(zhuǎn)變：從一開始的 “有沒有算法能夠解決這個(gè)問題”，轉(zhuǎn)變成后來的 “有沒有一種算法能夠在計(jì)算機(jī)上、在合理時(shí)間內(nèi)解決這個(gè)問題”。簡(jiǎn)言之，數(shù)學(xué)算法和計(jì)算機(jī)算法的研究逐漸形影不離、密不可分。

為什么算法如此令人著迷？因?yàn)槠淇捎?jì)算性和復(fù)雜性本身就具有吸引力。

一般來說，大家最初關(guān)注的是一個(gè)個(gè)具體問題的解。而當(dāng)具有了抽象能力之后，自然就會(huì)升階到去關(guān)注算法，即對(duì)一類問題普遍的解法。數(shù)學(xué)的基本特點(diǎn)就是不斷在抽象臺(tái)階上上升，所以，進(jìn)入關(guān)注算法的階段是必然的，后面自然又會(huì)關(guān)注若干類問題之間的共同點(diǎn)與不同點(diǎn)。

關(guān)于算法的特性，中國(guó)科學(xué)技術(shù)大學(xué)副研究員、中國(guó)科學(xué)院科學(xué)傳播研究中心副主任袁嵐峰告訴 DeepTech：“理論計(jì)算機(jī)科學(xué)研究的核心是可計(jì)算性和計(jì)算復(fù)雜性。其中，可計(jì)算性是指一個(gè)問題是否能在有限時(shí)間內(nèi)解決，無論這個(gè)時(shí)間有多長(zhǎng)；計(jì)算復(fù)雜性是指一個(gè)問題是否能快速解決，快速的意思是計(jì)算量隨計(jì)算規(guī)模只是多項(xiàng)式增長(zhǎng)，而不是指數(shù)增長(zhǎng)?！?/span>

在計(jì)算復(fù)雜性方面，需要研究的問題非常多。最基本的問題是，“能夠快速求解的問題”（這個(gè)集合稱為 P）和 “能夠快速驗(yàn)證解的問題”（這個(gè)集合稱為 NP），這兩個(gè)集合是否相等，即 P 是否等于 NP？

一個(gè)典型的例子是因數(shù)分解。給定一個(gè)合數(shù)不一定有辦法快速分解它，但給定一個(gè)合數(shù)的兩個(gè)質(zhì)因數(shù)我們立刻就可以把它們乘起來驗(yàn)證是不是等于那個(gè)合數(shù)，所以這個(gè)問題屬于 NP，但目前還不知道它是否屬于 P。

顯然，屬于 P 的問題肯定也屬于 NP。但屬于 NP 的是否必然屬于 P 呢？驚人的是，經(jīng)過幾十年的研究，人們對(duì)這個(gè)基本問題仍然無法確定。P 對(duì) NP 問題被公認(rèn)為數(shù)學(xué)中最重要的未解之謎之一，跟 “黎曼猜想” 并列。

計(jì)算復(fù)雜性理論中另一個(gè)重要的基本問題，是 “擴(kuò)展的丘奇 - 圖靈論題”（Extended Church-Turing Thesis）：任何一臺(tái)可計(jì)算的機(jī)器能快速計(jì)算的問題都是一樣的，都與圖靈機(jī)相同。與不擴(kuò)展的 “丘奇 - 圖靈論題”（Church-Turing Thesis）的區(qū)別在于，這里討論的并非是否可計(jì)算，而是是否可快速計(jì)算。

現(xiàn)在學(xué)術(shù)界普遍的看法是，“丘奇 - 圖靈論題” 是正確的，而 “擴(kuò)展的丘奇 - 圖靈論題” 是錯(cuò)誤的。為什么錯(cuò)誤呢？因?yàn)榱孔佑?jì)算機(jī)是個(gè)例外，它可以快速解決經(jīng)典計(jì)算機(jī)無法解決的問題。用計(jì)算復(fù)雜性的術(shù)語(yǔ)說，這個(gè)命題是 “P 不等于 BQP”（BQP 是量子計(jì)算機(jī)可以快速解決的問題的集合）。

對(duì)此，袁嵐峰舉例說道，“1994 年，MIT 應(yīng)用數(shù)學(xué)教授彼得?肖爾提出了快速分解因數(shù)的量子算法，而直到現(xiàn)在都沒有快速分解因數(shù)的經(jīng)典算法。不過需要注意的是，這并不能排除哪天人們想到一個(gè)快速分解因數(shù)的經(jīng)典算法，因此擴(kuò)展的丘奇 - 圖靈論題并沒有被嚴(yán)格地證偽。這種狀況跟 P 對(duì) NP 問題一樣，在那里是大多數(shù)人都相信 P 不等于 NP，但直到現(xiàn)在都無法精確證明?！?/span>

“在實(shí)驗(yàn)層面，2020 年 12 月中國(guó)的量子計(jì)算機(jī)‘九章’對(duì)‘玻色子取樣’這個(gè)問題實(shí)現(xiàn)了超越現(xiàn)有最強(qiáng)的經(jīng)典計(jì)算機(jī)一百萬億倍的優(yōu)勢(shì)。這是目前推翻擴(kuò)展丘奇 - 圖靈論題的最強(qiáng)的證據(jù)。當(dāng)然，實(shí)驗(yàn)證據(jù)也永遠(yuǎn)不能蓋棺定論，還需要理論層面繼續(xù)研究。這樣的實(shí)驗(yàn)說明的是，沒有發(fā)現(xiàn)任何基本的物理原理阻止量子計(jì)算機(jī)超越經(jīng)典計(jì)算機(jī)，這本身就是個(gè)大好消息。” 袁嵐峰補(bǔ)充道。

為什么這次獲獎(jiǎng)的兩位數(shù)學(xué)家分別來自理論計(jì)算機(jī)科學(xué)與離散數(shù)學(xué)？因?yàn)殡x散數(shù)學(xué)跟理論計(jì)算機(jī)科學(xué)緊密相聯(lián)，許多難以求解的問題就是離散數(shù)學(xué)提出來的，如著名的旅行推銷員問題（Travelling salesman problem）。人們研究這些離散數(shù)學(xué)問題，也是為了找到快速算法，所以這兩個(gè)領(lǐng)域在很大程度上是重疊的。兩個(gè)領(lǐng)域的珠聯(lián)璧合、互相成就，催生了以計(jì)算機(jī)為基礎(chǔ)的科技進(jìn)步，為現(xiàn)代社會(huì)和生活帶來了巨變。

零知識(shí)證明：數(shù)學(xué)和計(jì)算機(jī)的“雙向奔赴”

匈牙利數(shù)學(xué)家洛瓦茲的研究是從數(shù)學(xué)轉(zhuǎn)向計(jì)算機(jī)。據(jù)了解，洛瓦茲曾在 2007~2010 年擔(dān)任國(guó)際數(shù)學(xué)聯(lián)盟主席；2014~2020 年擔(dān)任匈牙利科學(xué)院院長(zhǎng)，并且他非常注重研究的獨(dú)立性，為保證研究獨(dú)立性做過很多努力。

他的數(shù)學(xué)研究從網(wǎng)絡(luò)理論等離散數(shù)學(xué)的主題開始，這對(duì)數(shù)學(xué)領(lǐng)域其他部分的研究和應(yīng)用具有不可替代的作用，比如我們熟悉的大數(shù)據(jù)分析，就需要該研究做支撐。

雖然網(wǎng)絡(luò)理論等離散數(shù)學(xué)的主題被 “純” 數(shù)學(xué)家看不起，但洛瓦茲偏偏對(duì)這樣的數(shù)學(xué)基礎(chǔ)研究和應(yīng)用感興趣。為此，他在微軟待了 7 年，在職期間他為網(wǎng)絡(luò)數(shù)學(xué)理論中的關(guān)鍵問題尋求解決方案。例如，在計(jì)算機(jī)領(lǐng)域，計(jì)算會(huì)對(duì)節(jié)點(diǎn)進(jìn)行著色，同時(shí)滿足 “任何兩個(gè)相鄰節(jié)點(diǎn)始終異色” 這一條件，洛瓦茲找到了解決該問題可能方法的數(shù)量。

與洛瓦茲不同，以色列數(shù)學(xué)家威格森的研究是從計(jì)算機(jī)轉(zhuǎn)向數(shù)學(xué)。他從 1999 年起任職于 IAS（普林斯頓高等研究院）。他最著名的成就之一就是證明了在一定條件下，任何一個(gè)快速的隨機(jī)算法都可以被轉(zhuǎn)化為確定性算法。

例如，如何判斷一個(gè)自然數(shù) N 是否是質(zhì)數(shù)？最容易想到的算法，即從 2 到 N 的平方根依次嘗試是否能整除 N，計(jì)算量是指數(shù)增長(zhǎng)的。后來，人們提出了若干種快速的算法，不過這些算法都用到了隨機(jī)數(shù)。有沒有可能找到快速的確定性算法呢？2002 年，三位印度數(shù)學(xué)家提出的 AKS 算法實(shí)現(xiàn)了這個(gè)目標(biāo)，從而說明隨機(jī)性在解決這個(gè)問題時(shí)并不是不可或缺的。

威格森的另一項(xiàng)主要成就對(duì)信息經(jīng)濟(jì)有著至關(guān)重要的作用，這項(xiàng)研究涉及 “零知識(shí)證明”，一種允許某人在不透露任何有關(guān)陳述內(nèi)容的信息的情況下驗(yàn)證陳述正確性的方法。早在 1991 年，威格森和團(tuán)隊(duì)就證明了，所有的數(shù)學(xué)語(yǔ)言都可以用零知識(shí)證明翻譯。

洛瓦茲和威格森對(duì)于零知識(shí)證明算法的研究，有重大意義。首先，對(duì)數(shù)字貨幣的認(rèn)證非常重要，以比特幣為代表的虛擬數(shù)學(xué)貨幣問世以來，促進(jìn)了區(qū)塊鏈的發(fā)展，令金融體系發(fā)生翻天覆地的變化；其次，對(duì)金融體系有重大意義，自第一次資產(chǎn)階級(jí)革命以來，不斷發(fā)展的金融體系帶人類走出洪荒，走向文明，而產(chǎn)業(yè)革命必須等待金融革命，否則資金陷入自我循環(huán)的境地，那么等待人類的便是金融危機(jī)。

虛擬數(shù)字貨幣作為金融體系浪潮中的重要角色，離不開數(shù)學(xué)也離不開計(jì)算機(jī)，金融體系的發(fā)展也必將引領(lǐng)時(shí)代的行業(yè)變革，站在長(zhǎng)期視角來看，兩位數(shù)學(xué)家的零知識(shí)研究在很大程度上也使得金融體系前景變得更加明朗。

重視數(shù)學(xué)算法研究

算法，對(duì)于大家而言其實(shí)并不陌生，我們小學(xué)就學(xué)的 “加減乘除” 就屬于算法，只不過這是最基礎(chǔ)的數(shù)學(xué)算法。數(shù)學(xué)發(fā)展到今天，已經(jīng)是一個(gè)非常龐大的系統(tǒng)，如果把整個(gè)數(shù)學(xué)領(lǐng)域比作大海，“算法” 以及和算法相關(guān)的數(shù)學(xué)只能看是海洋中的一滴水。

然而，對(duì)于大多數(shù)的純數(shù)學(xué)家，他們主要還是靠紙、筆、黑板、粉筆研究數(shù)學(xué)。很多重要的基礎(chǔ)數(shù)學(xué)分支，他們的研究基本上不會(huì)考慮算法，甚至連計(jì)算機(jī)都不使用。另外一些領(lǐng)域，他們會(huì)用一些簡(jiǎn)單的編程，輔助驗(yàn)算一些例子作為研究素材，不屬于核心。

但是，很多應(yīng)用數(shù)學(xué)領(lǐng)域和 “算法” 息息相關(guān)，比如運(yùn)籌學(xué)、控制論、統(tǒng)計(jì)學(xué)等，如果結(jié)合具體的工程項(xiàng)目，往往一個(gè)算法的改進(jìn)，就能帶來巨大的效率提升 —— 這個(gè)也是很多工程領(lǐng)域認(rèn)為數(shù)學(xué)很有用的原因之一。

不過，數(shù)學(xué)學(xué)科里經(jīng)常發(fā)生這樣的事情，正如哆嗒數(shù)學(xué)網(wǎng)的負(fù)責(zé)人告訴 DeepTech 的那樣：“一個(gè)數(shù)學(xué)具體研究，在研究之初并沒有什么功利的出發(fā)點(diǎn)，數(shù)學(xué)家只是出于本能求知或者想讓數(shù)學(xué)本身更完美而研究它。但成果出來后，意外地發(fā)現(xiàn)其他的地方有重要的應(yīng)用。這個(gè)‘轉(zhuǎn)化’時(shí)間可能還很長(zhǎng)，有時(shí)上百年，甚至上千年?！?/span>

零知識(shí)證明算法的研究者獲獎(jiǎng)，很大程度上源于該算法的實(shí)際應(yīng)用性，這個(gè)曾被 “純” 數(shù)學(xué)家看不起的研究獲得了數(shù)學(xué)領(lǐng)域的大獎(jiǎng)，也引發(fā)我們的思考，我們應(yīng)該如何對(duì)待理論層面算法的研究呢？

對(duì)此，袁嵐峰告訴 DeepTech：“有個(gè)詞叫做‘跳蚤效應(yīng)’，即給跳蚤加個(gè)蓋子，讓它只能跳到某個(gè)高度，在拿掉蓋子以后，跳蚤也不會(huì)跳得超過原來蓋子的高度，因?yàn)樗J(rèn)為自己只能跳到這么高了。許多人也是如此，不敢去追求夢(mèng)想，因?yàn)樗麄冃睦锞湍J(rèn)了自己做不到。如果你認(rèn)為自己肯定做不到，那么你當(dāng)然就真的做不到了。但如果你勇敢地去做，你就會(huì)發(fā)現(xiàn)許多事都是可以做到的，你取得的進(jìn)步會(huì)超出自己的預(yù)期。科學(xué)事業(yè)就是如此！”

考特說：“數(shù)學(xué)是人類智慧皇冠上最燦爛的明珠?！?/span>

米斯拉說：“數(shù)學(xué)是人類的思考中最高的成就。”

高斯說：“數(shù)學(xué)是科學(xué)之王。”

培根說：“數(shù)學(xué)是打開科學(xué)大門的鑰匙?！?/span>

恩格斯說：“數(shù)和形的概念不是從其他任何地方，而是從現(xiàn)實(shí)世界中得來的?！?/span>

我們應(yīng)始終重視對(duì)數(shù)學(xué)算法的研究，重視對(duì)數(shù)學(xué)理論的研究，對(duì)結(jié)合了數(shù)學(xué)和計(jì)算機(jī)領(lǐng)域的算法研究更應(yīng)重視，因?yàn)橹匾曀鼈?，就是重視人類的未來?/span>

-End-