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

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

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

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

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

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

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

有沒有一種技術，可以實現數據使用權、所有權的分離，生產方保有數據的所有權而不影響數據需求方提供服務？零知識證明就可以為這種技術提供算法。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

他的數學研究從網絡理論等離散數學的主題開始，這對數學領域其他部分的研究和應用具有不可替代的作用，比如我們熟悉的大數據分析，就需要該研究做支撐。

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

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

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

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

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

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

重視數學算法研究

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

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

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

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

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

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

考特說：“數學是人類智慧皇冠上最燦爛的明珠。”

米斯拉說：“數學是人類的思考中最高的成就?！?/span>

高斯說：“數學是科學之王?！?/span>

培根說：“數學是打開科學大門的鑰匙?！?/span>

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

我們應始終重視對數學算法的研究，重視對數學理論的研究，對結合了數學和計算機領域的算法研究更應重視，因為重視它們，就是重視人類的未來。

-End-