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

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

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

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

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

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

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

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

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

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

因為他們對于零知識證明的研究，不僅對現(xiàn)代數(shù)學(xué)核心計算有重大貢獻，而且有巨大的現(xiàn)實意義：

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

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

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

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

為什么算法如此令人著迷？因為其可計算性和復(fù)雜性本身就具有吸引力。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

高斯說：“數(shù)學(xué)是科學(xué)之王?！?/span>

培根說：“數(shù)學(xué)是打開科學(xué)大門的鑰匙。”

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

我們應(yīng)始終重視對數(shù)學(xué)算法的研究，重視對數(shù)學(xué)理論的研究，對結(jié)合了數(shù)學(xué)和計算機領(lǐng)域的算法研究更應(yīng)重視，因為重視它們，就是重視人類的未來。

-End-