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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

米斯拉說(shuō)：“數學(xué)是人類(lèi)的思考中最高的成就?！?/span>

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

培根說(shuō)：“數學(xué)是打開(kāi)科學(xué)大門(mén)的鑰匙?！?/span>

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

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

-End-