微软研究院发布 Magnetar：基于哈希的零知识证明实现通用计算验证提速 10-39 倍

概览

• 一种全新的计算形式。零知识证明（Zero-knowledge proofs）允许你运行一项工作负载，并在获得结果的同时，收到一个简短的证明，以证实程序正确运行。任何人都可以在毫秒内检查该证明，无需重新运行程序，无需信任执行者，也无需获取程序所处理的数据。
• 三大挑战阻碍了广泛采用：使证明生成的速度足够快；让普通程序无需密码学专业知识即可使用；以及确保其底层加密技术在未来数十年内依然可信。
• Magnetar 在这三大挑战上均取得了重大进展。 它能够证明用 Rust、Go 或 C 编写的程序，平均速度比此前最快的同类系统快 10 到 39 倍，且其安全性仅依赖于标准哈希函数。这是微软研究院（Microsoft Research）在推动零知识证明实用化方面十余年研究的最新成果。

一种全新的计算形式

计算机产生的每一个结果都隐含着一个问题：程序是否如声称那样运行并产生了正确的输出？如今，回答这个问题往往需要在验证之外建立一定程度的信任。我们信任操作员、供应商、交易对手或智能体，并依赖合同、审计和日志来确立这种信任。

零知识证明提供了一种从根本上不同的建立信任的方式。程序运行后，除了输出结果外，还会生成一个简短的证明——这是一份密码学证书，证明该程序在这些输入下产生了该输出。该证明体积小且验证速度快。接收者可以在毫秒内确认结果，而无需重新运行程序，并且可以将该证明传递给任何需要相同保证的其他人。凭借零知识特性，该证明也不会泄露本应保持私密的输入信息。

这改变了现实世界中“正确性”的含义。一个结果不再因为是谁产生的而值得信任，而是因为它所附带的证明而可以被验证。代表用户行事的 AI 智能体可以附加一份证明，表明其每一步操作都符合被赋予的策略。受监管的金融机构可以在不公开交易细节的情况下，证明交易处理是正确的。一旦生成证明变得像运行程序一样常规，这些场景便成为可能。

三大核心挑战

零知识证明诞生于 20 世纪 80 年代，而关于证明程序执行的理念几乎同样历史悠久。阻碍它们成为通用工具的是三个长期难以同时解决的挑战。

效率。历史上，生成证明所需的计算量比运行程序本身高出数百万倍。多年的研究已大幅降低了这一开销，但最快的系统往往通过在其他方面做出妥协来实现速度提升。

通用性与易用性。 许多证明系统要求开发者手动将程序重写为密码学电路（即对特定计算的固定算术描述）。这一过程耗时数月。应用程序的任何改动都意味着需要构建新的电路，且这种转换本身也是安全漏洞频发的来源。一种通用的替代方案是证明普通处理器的执行过程，从而可以对任何编译后的程序按其原始形式进行证明。直到最近，这种通用性仍以牺牲速度或安全性为高昂代价。

安全性。 证明的强度取决于其底层的密码学基础。许多证明系统依赖于椭圆曲线，而足够强大的量子计算机可以破解这些曲线。微软正通过其“量子安全计划”（Quantum Safe Program）解决这一问题，该计划旨在将其产品和服务迁移至后量子密码学领域，这一目标已加速推进至 2029 年。后量子证明系统已经存在，但其中一些基于格假设，而大多数则依赖于为降低证明成本而发明的新型密码函数。这些新型密码函数尚未经历当今互联网所依赖的密码学技术那样长达数十年的严格审查，且部分方案建立在关于纠错码、尚未被证实的数学猜想之上。它们以强假设换取了速度。

十余年的深耕

十多年来，微软研究院一直致力于让零知识证明和可验证计算走向实用化。早期的研究遵循两种路径，但两者仅适用于小型程序。第一种方法（在新标签页中打开） (opens in new tab)允许验证者通过与证明者的简短交互来检查长计算过程，该技术称为求和检验协议（sum-check protocol）（在新标签页中打开），但这仅适用于具有特定分层结构的计算。第二种方法（在新标签页中打开） (opens in new tab)利用椭圆曲线密码学为几乎任何计算生成极小的证明。但这需要一个涉及秘密信息的一次性可信设置，如果这些信息泄露，任何人都可以伪造证明。此外，这种方法也容易受到量子计算机的攻击。

2019 年，一种名为 Spartan 的新型零知识证明系统回归到求和检验方法，并使其能够在无需可信设置的情况下支持通用程序。Spartan 还可以使用不同的密码学构建模块进行实例化。正是这种灵活性，使得后来的证明系统能够仅基于哈希函数构建。随后的一系列成果填补了剩余的空白：

• Phalanx（在新标签页中打开） 于 2021 年展示了如何利用重复性（例如处理器在每一步执行相同的指令周期），以比 Spartan 快一个数量级的速度证明计算。Magnetar 的处理器描述正是基于这一理念构建的。
• Nova（在新标签页中打开）、HyperNova（在新标签页中打开）、NeutronNova（在新标签页中打开） 以及 Neo 和 SuperNeo（在新标签页中打开） 表明，提前停止 Spartan 的证明过程并将部分结果折叠在一起，使得以更低成本证明任意规模的计算变得切实可行。
• Brakedown（在新标签页中打开） 于 2021 年引入了一种快速的基于哈希的承诺方案，并将其与 Spartan 结合，从而产生了首个安全性依赖于标准哈希函数的 Spartan 变体。
• Spice（在新标签页中打开）、Lasso（在新标签页中打开）、Nebula（在新标签页中打开），随后是 Twist and Shout（在新标签页中打开），使通用处理器核心的内存操作证明变得廉价；而 Jolt（在新标签页中打开） 则展示了将这些技术与 Spartan 结合，可以高效地证明完整处理器的执行过程。
• 今年早些时候，Vega（在新标签页中打开） 将这一系列工作应用于数字身份领域，能够在 不到十分之一秒 内从政府凭证中证明事实。
• 最近，BinarySpartan（在新标签页中打开） 将 Spartan 引入二元域，在该域中可以高效表达处理器的逻辑和标准哈希函数。BinarySpartan 还依赖于 Ligerito（在新标签页中打开）——一种类似 Brakedown 的承诺方案，其证明更短——以及 ring switching（在新标签页中打开），该技术使得对比特向量的承诺更加高效。

每一项工作都解决了问题的一部分。Magnetar 则是这些拼图汇聚之处。

Magnetar

Magnetar 是一款零知识虚拟机（zkVM），它在上述三大挑战上均取得了重大进展。

图 1. Magnetar 对程序的执行过程进行证明，并生成一个任何人都可以验证的小型证明，其安全性仅依赖于标准哈希函数。

它是通用型的。 Magnetar 能够证明 RISC-V 的执行过程，RISC-V 是一种开放的处理器架构，拥有支持所有主流编程语言的成熟编译器。开发者可以使用 Rust、Go 或 C 编写程序，按常规方式编译，Magnetar 即可直接对其原始代码进行证明。这意味着在实际应用中，无论是业务策略、数据管道，还是以太坊虚拟机（EVM）的解释器，本质上都是程序；负责维护这些程序的工程师可以直接对其执行过程进行证明，无需修改代码。因此，证明工作不再是一项需要专家才能完成的任务。

它的速度优于同类现有系统。 在笔记本电脑上，Magnetar 每秒可证明 720 万至 870 万条处理器指令。在涵盖从加密哈希到小型 EVM 解释器内代币转账等 15 个基准测试程序中，在同一台机器上，其平均速度比最快的现有 zkVM 快 10 到 39 倍，而在代币转账基准测试中，比另外两个系统快 300 倍以上。经过优化的 Magnetar 每秒可证明 950 万至 1280 万个周期，这将使文中报告的每一项加速倍数提升约 1.3 倍。其证明的验证时间约为 12 毫秒。

其安全性基于标准密码学。 Magnetar 依赖于 SHA-256 或 SHA-3 等标准哈希函数，即目前保护各组织系统所使用的相同原语。它不需要椭圆曲线、格密码、专用哈希函数、可信设置，也不依赖关于纠错码的未经验证的猜想。哈希函数是密码学工具包中研究最为透彻的原语，也是 NIST 将其作为保守的后量子选项标准化的无状态基于哈希的签名的基础。对于一个在未来数十年内仍需保持可信的系统而言，仅依赖标准哈希函数消除了路线图中的密码学迁移需求。

这一设计决策还带来了第二个红利。验证 Magnetar 证明主要涉及标准哈希函数和二元域算术的求值，而这些正是 Magnetar 能够高效证明的操作。因此，对 Magnetar 而言，验证证明只是一项普通的工作负载。这使得 Magnetar 能够通过分块证明再组合各部分的方式，来证明任意规模的计算。这也使得 Magnetar 能够为账本或区块链等长期运行的系统提供证明。

技术论文提供了完整的设计、安全性分析和测量数据。

展望未来

Magnetar 将零知识证明和可验证计算推进到一个新阶段：它们可以建立在组织已经信任的密码学基础之上，以可用的速度运行，并由编写常规代码的工程师实现。Magnetar 开启了一个未来，其中加密证明成为计算的常规输出。我们预计，技术领导者将不再询问执行证明是否实用，而是转而关注他们更愿意验证哪些结果，而不是选择承担信任风险。

如果您有兴趣探索零知识证明如何支持您的用例，我们非常乐意听取您的意见（在新标签页中打开）。

在新标签页中打开

文章 基于证明的通用计算与 Magnetar 首发于 Microsoft Research。