跳转到内容
← 返回计算理论
计算理论当代约 18 分钟阅读

交互式证明与零知识

Interactive Proofs and Zero Knowledge

"证明"这个概念在 1980 年代被重新定义了两次，每一次都让它变得更强。 第一次是加入交互与随机：证明不再是一份可以静态检查的文书，而是验证者与证明者之间的一场提问游戏，验证者可以掷硬币，并且只要求"以极高概率不被骗"。第二次更反直觉：证明可以让你确信某件事为真，而不透露任何关于为什么为真的信息。

交互式证明零知识PCP 定理概率检验可验证计算

"证明"这个概念在 1980 年代被重新定义了两次，每一次都让它变得更强。

第一次是加入交互与随机：证明不再是一份可以静态检查的文书，而是验证者与证明者之间的一场提问游戏，验证者可以掷硬币，并且只要求"以极高概率不被骗"。第二次更反直觉：证明可以让你确信某件事为真，而不透露任何关于为什么为真的信息。

这两步的后果远超理论：今天的隐私区块链、可验证计算与匿名认证，全部建立在它们之上。

破除误解

第一个误解：以为"零知识"是加密的另一种说法。 加密隐藏内容而保留内容；零知识根本不传递内容——验证者结束时所知道的，只有"这个命题为真"这一件事，其余与他自己凭空模拟出来的没有区别。它的定义方式本身就是这个领域最精妙的地方（见下文的"模拟器"）。

第二个误解：以为概率证明是"不严格的证明"。 错误概率可以通过重复独立降到 2−1002^{-100} 以下——比硬件故障、宇宙射线翻转比特的概率还低几个数量级。 坚持"必须零错误"在工程上是一个没有意义的要求。

第三个误解：以为这些是纯理论。 PCP 定理最初是复杂性理论的内部成果，如今是近似算法不可近似性结果的基础，也是简洁非交互零知识证明（zk-SNARK）的技术祖先——从"检查证明只需读几个比特"到"链上验证一笔隐私交易"，是同一条技术线。

一、把证明变成对话

经典的证明是NP 的形式：存在一份短证书，验证者读完即可确认。1985 年，戈德瓦瑟、米卡利与拉科夫（以及独立地，巴巴伊）提出了交互式证明系统：

  • 证明者计算能力无限，但不可信；
  • 验证者只有多项式时间，可以掷随机硬币；
  • 双方来回若干轮；
  • 完备性：命题为真时，诚实证明者能让验证者以高概率接受；
  • 可靠性：命题为假时，任何证明者都无法让验证者以不可忽略的概率接受。

一个直观的例子是图不同构。要证明两张图 G0,G1G_0, G_1 不同构（这不属于已知有短证书的问题），验证者可以这样做：私下随机选一张图、随机重排它的顶点，把结果交给证明者，问"这来自哪一张？"如果两图确实不同构，无限强的证明者总能答对；如果两图同构，重排后的图与两者都无法区分，他只能猜——每轮出错概率二分之一。 重复一百轮，被骗的概率就低于 2−1002^{-100}。

随机性在这里不是为了省时间，而是让验证者能提出证明者无法预知的问题——这正是静态证书做不到的事。

值得一提的是历史细节：这个定义诞生于密码学的实际需求而非纯理论的好奇。戈德瓦瑟与米卡利当时关注的是多方协议——例如"心智扑克"（mental poker）——中如何让参与者证明自己遵守了规则，又不暴露自己的手牌。论文会议版 1985 年发表于 STOC，期刊版却拖到 1989 年才刊出；戈德瓦瑟与米卡利后来因"为密码学奠定复杂性理论基础"共同获得 2012 年图灵奖。另一个后来证明并不本质的差别是硬币的公开性：巴巴伊的"亚瑟-梅林"协议要求验证者公开抛硬币，而戈德瓦瑟-西普瑟（1986）证明公开硬币与私有硬币的交互式证明能力相同——验证者可以把硬币藏起来而不损失任何验证能力。这告诉我们，这个模型对细节的扰动异常稳健，其能力边界由交互与随机本身决定。这也解释了为什么随机性在此处与 随机化算法 中"用随机换时间"的角色不同：它换来的不是速度，而是信任结构的改变。

二、IP = PSPACE：这条对话能走多远

交互式证明系统能验证多大范围的命题？ 1990 年，沙米尔（在伦德、福特诺、卡洛夫与尼桑的算术化技术之上）证明了：

IP=PSPACE\mathrm{IP} = \mathrm{PSPACE}

一个只有多项式时间与硬币的验证者，通过与不可信的强大证明者对话，可以验证任何用多项式空间可判定的命题——这个类远大于 NP，包含完全信息博弈的最优策略这类问题。

这个结果在当时几乎无人预料，因为它撞破了一道方法论上的墙。此前两年，福特诺与西普瑟（1988）构造了一个"神谕"（oracle）世界，在其中 coNP 没有交互式证明——也就是说 IP ≠ PSPACE 相对该神谕成立。而复杂性理论当时几乎所有已知的证明技术（对角线化、模拟）都是"可相对化"的：它们在任何神谕世界里同样成立。因此主流猜测是 coNP 根本不在 IP 里。突破发生在 1989 年末到 1990 年：伦德等人先用"算术化"为 #P 完全问题（计算矩阵永久式）构造了交互式证明；据福特诺本人的回忆，沙米尔在数周内通过邮件往来把同一技术推广到了整个 PSPACE。算术化之所以能做到可相对化技术做不到的事，恰恰因为它打开了证明对象的内部结构——它利用了布尔公式的代数性质，而不是把它当作黑盒。这是复杂性理论中第一个重量级的不可相对化结果，此后"代数化"成为绕开神谕障碍的标准武器之一。

证明的关键技术叫算术化：把布尔公式提升为有限域上的多项式，于是"这个公式是否可满足"变成了多项式的代数性质，而多项式有一个极好的性质——两个不同的低次多项式在随机点上取值相同的概率极小。验证者因此可以只在一个随机点上检查，就对整体获得高置信度。"随机抽查一点即可判断全局"这一思想，是此后二十年整个领域的引擎。

三、PCP 定理：只读三个比特

如果允许证明者先写下一份（可能极长的）证明，验证者能少读多少？

PCP 定理（阿罗拉与萨夫拉；阿罗拉、伦德、莫特瓦尼、苏丹与塞盖迪，1990 年代初，1998 年正式发表）给出了一个惊人的答案：任何 NP 命题都存在一种概率可检验的证明格式，使得验证者只需使用对数量级的随机比特、读取证明中常数个位置，就能以高概率判断真假。

NP=PCP(O(log⁡n),O(1))\mathrm{NP} = \mathrm{PCP}(O(\log n), O(1))

换句话说：错误必须被"摊开"。 在这种编码下，一份错误的证明不可能只在某个隐蔽角落出错——它必然在很大比例的位置上都不自洽，因此随机看几眼就能撞见。

这条结论不是凭空出现的。1991 年，费格、戈德瓦瑟、洛瓦兹、萨夫拉与塞盖迪（FGLSS）注意到一个深刻的对应：多证明者交互式证明的可靠性与"近似最大团有多难"是同一个问题的两面——一个验证协议越难被欺骗，对应的团问题就越难被近似。正是这个观察把"概率检验证明"从一个验证技术变成了攻克 近似算法 极限的工具，也直接催生了 PCP 定理的最终形式。值得一提的是，PCP 定理的原始证明长达数百页，涉及递归的验证器组合；2006 年迪努尔（Irit Dinur）给出了一个全新的、只有几十页的组合式证明——通过反复做"间隙放大"（把验证者发现错误的概率一步步翻倍），绕开了原先沉重的代数机器。一个定理出现两个本质上不同的证明，本身就是它触及深层结构的证据。

它最出人意料的后果出现在另一个方向：PCP 定理直接给出了大量优化问题的不可近似性下界。比如若 P ≠ NP，则不存在把某些问题近似到任意给定比例的多项式算法。一个关于"证明如何被检查"的结果，反过来限定了"问题能被优化到多好"——这是复杂性理论中最漂亮的跨界之一。

四、零知识：用"模拟器"定义"什么都没学到"

如何严格地说"验证者什么都没学到"？戈德瓦瑟、米卡利与拉科夫给出的定义是这个领域的思想核心：

存在一个多项式时间的"模拟器"，它不知道秘密，却能生成一份与真实交互记录在计算上不可区分的对话。

如果验证者看到的东西他自己就能伪造出来，那么这段交互没有传递任何他原先不能自行获得的信息。 这个定义把一个哲学味道很重的问题（"知道"是什么）转成了完全可操作的形式。

一个可以徒手验证的例子是三染色（这个协议由布鲁姆给出）。证明者声称知道一张图的三染色方案。他把每个顶点的颜色随机置换后分别装进不透明的盒子（承诺）；验证者随机挑一条边，要求打开这条边的两个端点；如果两端颜色不同，则通过。

  • 图确实可三染色 → 每次都通过；
  • 不可三染色 → 至少有一条边两端同色，被抽中的概率至少是 $1/|E|$，重复足够多轮即可揭穿；
  • 而验证者每轮只看到两个不同的随机颜色——这他自己就能编出来，因此什么也没学到。

"不透明的盒子"是整个构造的支点，它要求一种叫承诺方案（commitment scheme）的原语：证明者先把值封存（封存后自己改不了——这叫绑定性），验证者拆封前看不到内容（这叫隐藏性）。这个协议的两个安全性质恰好分别由承诺的两个性质撑起：可靠性靠绑定性（证明者不能在被抽查后临时改颜色），零知识性靠隐藏性（验证者拆封前确实一无所知）。而在单向函数存在的假设下，承诺方案可以被高效构造——这就是为什么零知识的大厦与整个 密码学基础 共用同一块地基。

1991 年，戈德赖希、米卡利与维格森进一步证明：在存在单向函数的假设下，NP 中的每个命题都有零知识证明。这一步把零知识从少数几个特例推广成了普遍工具。

五、从理论到部署

zk-SNARK / zk-STARK 把上述思想工程化为简洁的、非交互的证明：证明只有几百字节，验证只需几毫秒，且不需要来回对话（借助公共随机串或哈希函数）。它们的实际用途包括：

  • 隐私交易：证明"这笔转账合法且余额充足"，而不透露金额与地址；
  • 可验证计算：把计算外包给不可信的服务器，用一份短证明确认结果正确，验证成本远低于自己重算；
  • 区块链扩容：把大批交易的正确性压缩成一个证明，主链只验证这个证明。

从理论到这一步走了近三十年。消除交互的经典做法是 Fiat-Shamir 变换（1986，最初为 数字签名 提出）：把验证者的随机提问换成对已有对话的哈希值，让证明者一次性生成整份"自问自答"的记录。它的安全性分析有个著名的尴尬：戈德瓦瑟与卡莱（2003）证明，存在这样的协议——对任意具体的哈希函数，Fiat-Shamir 变换后的版本都不安全；也就是说"把随机预言机换成真实哈希"这一步在一般意义下无法被证明。然而用具体哈希函数实例化的实际方案二十多年来没有被攻破，理论与实践之间的这条缝至今没有被完全填上——这是该领域少有的、从业者必须睁一只眼闭一只眼的基础性问题。

工程化的另一条线索是把证明做得足够短、验证足够快：2013 年的 Pinocchio 系统首次让通用计算的可验证证明实用化（"zk-SNARK"一词由比坦斯基等人于 2012 年提出）；2014 年的 Zerocash 协议论文将其变成匿名货币设计，并于 2016 年 10 月以 Zcash 上线——这是零知识证明第一次承载真实的金融资产；2018 年本-萨松等人提出的 zk-STARK 则只依赖哈希函数，无需可信设置，且天然抗量子。今天，区块链 生态中的零知识扩容方案（zk-Rollup）已把"用一份证明压缩上万笔交易"变成日常运行的基础设施。

代价同样要讲清楚：许多方案需要可信设置（若初始参数生成过程被操纵，可以伪造证明）；证明生成的计算开销远高于验证；而安全性依赖具体的密码学假设，其中部分假设不能抵抗未来的量子攻击。

跨域连接

  • 哥德尔不完备定理：两者都在追问"证明"能力的边界，方向却相反——哥德尔证明了在足够强的形式系统内存在为真但不可证的命题，交互式证明则显示放宽要求（允许交互、随机与极小的错误概率）能让可验证的范围大幅扩张；把两者并读可以看清一件事：可证性不是一个固定的概念，它随着"什么算作一次成功的验证"而变。
  • RSA 与公钥密码：零知识的普遍构造依赖单向函数的存在，而这正是公钥密码的同一块基石——这意味着"任何 NP 命题都有零知识证明"这一定理是有条件的：它建立在我们相信但未证明的计算困难性假设之上；如果单向函数不存在（等价于某种意义上 P = NP），整座大厦连同现代密码学一起坍塌。
  • 概率论：整个领域的可靠性都来自一个概率论事实——独立重复让错误概率指数下降；同时算术化技术依赖 Schwartz–Zippel 引理这类"低次多项式在随机点上难以碰巧相等"的结论；把这两条放在一起就能理解为什么随机性在这里不是权宜之计，而是使新能力成为可能的资源。
  • 后量子密码：许多高效零知识方案的安全性建立在离散对数或配对假设上，而这些正是量子算法能攻破的目标——基于哈希的方案（如 STARK）因此在抗量子上更保守，代价是证明体积更大；这组权衡说明"零知识"本身是信息论层面的性质，而具体系统的安全性却取决于底层假设，两者不能混为一谈。
  • 数据权利与隐私：零知识给出了"最小披露"原则的技术实现——可以证明自己已成年而不透露生日、证明收入达标而不透露数额；这把隐私保护从"承诺不滥用数据"变成了"根本不需要交出数据"，而法律上的数据最小化原则至今仍主要依赖前者；技术在此走到了制度前面，如何在合规框架中承认这类证明是当前的空白。

参考文献

  • Goldwasser, Shafi, Silvio Micali, and Charles Rackoff. "The Knowledge Complexity of Interactive Proof Systems." SIAM Journal on Computing, vol. 18, no. 1, 1989, pp. 186–208.
  • Shamir, Adi. "IP = PSPACE." Journal of the ACM, vol. 39, no. 4, 1992, pp. 869–877.
  • Arora, Sanjeev, and Shmuel Safra. "Probabilistic Checking of Proofs: A New Characterization of NP." Journal of the ACM, vol. 45, no. 1, 1998, pp. 70–122.
  • Arora, Sanjeev, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. "Proof Verification and the Hardness of Approximation Problems." Journal of the ACM, vol. 45, no. 3, 1998, pp. 501–555.
  • Goldreich, Oded, Silvio Micali, and Avi Wigderson. "Proofs That Yield Nothing but Their Validity." Journal of the ACM, vol. 38, no. 3, 1991, pp. 690–728.
  • Feige, Uriel, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy. "Interactive Proofs and the Hardness of Approximating Cliques." Journal of the ACM, vol. 43, no. 2, 1996, pp. 268–292.
  • Dinur, Irit. "The PCP Theorem by Gap Amplification." Journal of the ACM, vol. 54, no. 3, 2007, Article 12.
  • Fiat, Amos, and Adi Shamir. "How to Prove Yourself: Practical Solutions to Identification and Signature Problems." CRYPTO '86, LNCS 263, Springer, 1987, pp. 186–194.
  • Ben-Sasson, Eli, et al. "Zerocash: Decentralized Anonymous Payments from Bitcoin." IEEE Symposium on Security and Privacy, 2014, pp. 459–474.

延伸阅读

  • Arora, Sanjeev, and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009（第 8、11、18 章）.
  • Goldreich, Oded. Foundations of Cryptography, Volume 1: Basic Tools. Cambridge University Press, 2001.
  • Thaler, Justin. Proofs, Arguments, and Zero-Knowledge. Now Publishers, 2022.

正文中引用本条 · 2