“零知识证明”，相关研究者已获得2021年阿贝尔奖 | 对话专家
近日，备受瞩目的数学界大奖阿贝尔奖开出 “双黄蛋”，获奖者是数学和计算机领域大佬：一位是匈牙利数学家拉兹洛・洛瓦兹（László Lovász），一位是以色列计算机科学家阿维・威格森（Avi Wigderson）。
图 | 2021 年阿贝尔奖颁布（来源：Abelprize 官网）
两位数学家因为对零知识证明的研究，而获此殊荣。懂行的朋友可能会大跌眼镜，什么？！就是那个曾经让纯数学家看不起的零知识证明，获了数学界举足轻重的阿贝尔奖？
没错！两位数学家正是因此获奖，正如颁奖词所说：“表彰其在理论计算机科学和离散数学方面做出的杰出贡献，以及在将之塑造为现代数学中心领域中发挥的主导作用。”
没有听说过零知识证明的朋友可能觉得这是个深奥复杂的数学理论，其实不然，相信大家在日常生活中都曾接触过。例如，QQ 账号在设置密码后，在不输入密码的前提下，通过回答密保问题证明你是账户的主人，这就是零知识证明的一个实际应用。
另外一个例子就是，由图灵奖获得者姚期智于 1982 年提出的 “百万富翁” 问题，即两位富翁想要知道谁更富有，但都不愿意透露自己的财富值。借助数学算法，两位富翁不需要告知对方自己的财富值是多少，他们只需要将自己的财富值都进行同一个运算，然后两人公开计算结果，通过各自对比财富值和计算结果，他们就能知道究竟谁更富有了。
这个问题的背后，本质上反映了基于用户数据挖掘的服务数据的使用权、所有权之间的矛盾：服务提供者必须得到你的数据才能提供服务。放到 “百万富翁” 问题中，互联网服务一定要拿到两位富翁的财产数据，才能计算出 “谁更富有”。
有没有一种技术，可以实现数据使用权、所有权的分离，生产方保有数据的所有权而不影响数据需求方提供服务？零知识证明就可以为这种技术提供算法。
图 | 零知识证明（来源：Pixabay）
零知识证明，所谓 “零”，就是不透露任何关于密码的核心信息。所谓 “证明”，就是回答相关问题，答案都正确，就能证明账户是你的。
零知识证明比起其他复杂算法更为简单，却因此受到了 “纯” 数学家们的嘲笑，但为什么偏偏是两位研究它的大佬，获得了阿贝尔奖？
因为他们对于零知识证明的研究，不仅对现代数学核心计算有重大贡献，而且有巨大的现实意义：
其一，零知识证明对数字货币的认证意义重大；
其二，零知识证明还可以用于人的身份验证，即在不透露密码的前提下，验证方通过一系列问题来让对方提供 “我知道正确密码”，或在信息安全领域，提供 “我就是本人” 的证明。
算法，为何让数学家们如此着迷？
从 20 世纪 70 年代初，第四代大规模集成电路计算机诞生以来，算法便不再只是数学领域的研究对象，也成为计算机领域的研究重点。
伴随着数学和计算机的发展，算法的侧重点发生了明显的转变：从一开始的 “有没有算法能够解决这个问题”，转变成后来的 “有没有一种算法能够在计算机上、在合理时间内解决这个问题”。简言之，数学算法和计算机算法的研究逐渐形影不离、密不可分。
图 | 大规模集成电路（来源：Pixabay）
为什么算法如此令人着迷？因为其可计算性和复杂性本身就具有吸引力。
一般来说，大家最初关注的是一个个具体问题的解。而当具有了抽象能力之后，自然就会升阶到去关注算法，即对一类问题普遍的解法。数学的基本特点就是不断在抽象台阶上上升，所以，进入关注算法的阶段是必然的，后面自然又会关注若干类问题之间的共同点与不同点。
关于算法的特性，中国科学技术大学副研究员、中国科学院科学传播研究中心副主任袁岚峰告诉 DeepTech：“理论计算机科学研究的核心是可计算性和计算复杂性。其中，可计算性是指一个问题是否能在有限时间内解决，无论这个时间有多长；计算复杂性是指一个问题是否能快速解决，快速的意思是计算量随计算规模只是多项式增长，而不是指数增长。”
图 | 无处不在的算法（来源：Pixabay）
在计算复杂性方面，需要研究的问题非常多。最基本的问题是，“能够快速求解的问题”（这个集合称为 P）和 “能够快速验证解的问题”（这个集合称为 NP），这两个集合是否相等，即 P 是否等于 NP？
一个典型的例子是因数分解。给定一个合数不一定有办法快速分解它，但给定一个合数的两个质因数我们立刻就可以把它们乘起来验证是不是等于那个合数，所以这个问题属于 NP，但目前还不知道它是否属于 P。
显然，属于 P 的问题肯定也属于 NP。但属于 NP 的是否必然属于 P 呢？惊人的是，经过几十年的研究，人们对这个基本问题仍然无法确定。P 对 NP 问题被公认为数学中最重要的未解之谜之一，跟 “黎曼猜想” 并列。
计算复杂性理论中另一个重要的基本问题，是 “扩展的丘奇 - 图灵论题”（Extended Church-Turing Thesis）：任何一台可计算的机器能快速计算的问题都是一样的，都与图灵机相同。与不扩展的 “丘奇 - 图灵论题”（Church-Turing Thesis）的区别在于，这里讨论的并非是否可计算，而是是否可快速计算。
现在学术界普遍的看法是，“丘奇 - 图灵论题” 是正确的，而 “扩展的丘奇 - 图灵论题” 是错误的。为什么错误呢？因为量子计算机是个例外，它可以快速解决经典计算机无法解决的问题。用计算复杂性的术语说，这个命题是 “P 不等于 BQP”（BQP 是量子计算机可以快速解决的问题的集合）。
图 | 量子计算机概念图（来源：Pixabay）
对此，袁岚峰举例说道，“1994 年，MIT 应用数学教授彼得・肖尔提出了快速分解因数的量子算法，而直到现在都没有快速分解因数的经典算法。不过需要注意的是，这并不能排除哪天人们想到一个快速分解因数的经典算法，因此扩展的丘奇 - 图灵论题并没有被严格地证伪。这种状况跟 P 对 NP 问题一样，在那里是大多数人都相信 P 不等于 NP，但直到现在都无法精确证明。”
“在实验层面，2020 年 12 月中国的量子计算机'九章’对'玻色子取样’这个问题实现了超越现有最强的经典计算机一百万亿倍的优势。这是目前推翻扩展丘奇 - 图灵论题的最强的证据。当然，实验证据也永远不能盖棺定论，还需要理论层面继续研究。这样的实验说明的是，没有发现任何基本的物理原理阻止量子计算机超越经典计算机，这本身就是个大好消息。” 袁岚峰补充道。
为什么这次获奖的两位数学家分别来自理论计算机科学与离散数学？因为离散数学跟理论计算机科学紧密相联，许多难以求解的问题就是离散数学提出来的，如著名的旅行推销员问题（Travelling salesman problem）。人们研究这些离散数学问题，也是为了找到快速算法，所以这两个领域在很大程度上是重叠的。两个领域的珠联璧合、互相成就，催生了以计算机为基础的科技进步，为现代社会和生活带来了巨变。
零知识证明：数学和计算机的“双向奔赴”
匈牙利数学家洛瓦兹的研究是从数学转向计算机。据了解，洛瓦兹曾在 2007~2010 年担任国际数学联盟主席；2014~2020 年担任匈牙利科学院院长，并且他非常注重研究的独立性，为保证研究独立性做过很多努力。
他的数学研究从网络理论等离散数学的主题开始，这对数学领域其他部分的研究和应用具有不可替代的作用，比如我们熟悉的大数据分析，就需要该研究做支撑。
图 | 匈牙利厄特沃什・罗兰大学教授拉兹洛・洛瓦兹（来源：维基百科）
虽然网络理论等离散数学的主题被 “纯” 数学家看不起，但洛瓦兹偏偏对这样的数学基础研究和应用感兴趣。为此，他在微软待了 7 年，在职期间他为网络数学理论中的关键问题寻求解决方案。例如，在计算机领域，计算会对节点进行着色，同时满足 “任何两个相邻节点始终异色” 这一条件，洛瓦兹找到了解决该问题可能方法的数量。
与洛瓦兹不同，以色列数学家威格森的研究是从计算机转向数学。他从 1999 年起任职于 IAS（普林斯顿高等研究院）。他最著名的成就之一就是证明了在一定条件下，任何一个快速的随机算法都可以被转化为确定性算法。
例如，如何判断一个自然数 N 是否是质数？最容易想到的算法，即从 2 到 N 的平方根依次尝试是否能整除 N，计算量是指数增长的。后来，人们提出了若干种快速的算法，不过这些算法都用到了随机数。有没有可能找到快速的确定性算法呢？2002 年，三位印度数学家提出的 AKS 算法实现了这个目标，从而说明随机性在解决这个问题时并不是不可或缺的。
图 | 美国普林斯顿高等研究院教授阿维・威格森（来源：维基百科）
威格森的另一项主要成就对信息经济有着至关重要的作用，这项研究涉及 “零知识证明”，一种允许某人在不透露任何有关陈述内容的信息的情况下验证陈述正确性的方法。早在 1991 年，威格森和团队就证明了，所有的数学语言都可以用零知识证明翻译。
洛瓦兹和威格森对于零知识证明算法的研究，有重大意义。首先，对数字货币的认证非常重要，以比特币为代表的虚拟数学货币问世以来，促进了区块链的发展，令金融体系发生翻天覆地的变化；其次，对金融体系有重大意义，自第一次资产阶级革命以来，不断发展的金融体系带人类走出洪荒，走向文明，而产业革命必须等待金融革命，否则资金陷入自我循环的境地，那么等待人类的便是金融危机。
图 | 虚拟数字货币（来源：Pixabay）
虚拟数字货币作为金融体系浪潮中的重要角色，离不开数学也离不开计算机，金融体系的发展也必将引领时代的行业变革，站在长期视角来看，两位数学家的零知识研究在很大程度上也使得金融体系前景变得更加明朗。
重视数学算法研究，就是重视人类的未来
算法，对于大家而言其实并不陌生，我们小学就学的 “加减乘除” 就属于算法，只不过这是最基础的数学算法。数学发展到今天，已经是一个非常庞大的系统，如果把整个数学领域比作大海，“算法” 以及和算法相关的数学只能看是海洋中的一滴水。
然而，对于大多数的纯数学家，他们主要还是靠纸、笔、黑板、粉笔研究数学。很多重要的基础数学分支，他们的研究基本上不会考虑算法，甚至连计算机都不使用。另外一些领域，他们会用一些简单的编程，辅助验算一些例子作为研究素材，不属于核心。