我们击败了谷歌的量子密码分析零知识证明

两周前，谷歌量子 AI 团队发布了一个经过极致优化的量子电路的零知识证明，并得出结论：第一代量子计算机将在短短 9 分钟内破解椭圆曲线加密密钥。今天，Trail of Bits 发布了自己的零知识证明，在所有指标上都显著优于谷歌的结果。我们的成果并非源于某种量子突破，而是利用了谷歌 Rust 证明器代码中多个细微的内存安全和逻辑漏洞。谷歌已修补了他们的证明，其科学主张未受影响，但这个故事反映了系统在使用零知识证明时所引入的独特攻击面。

谷歌的证明使用了一个零知识虚拟机（zkVM），在三个关键指标上计算量子电路的成本。总操作数和 Toffoli 门数代表电路的运行时间，量子比特数代表内存需求。谷歌与来自加州大学伯克利分校、以太坊基金会和斯坦福大学的合著者一起，发布了两个电路的证明：一个最小化门数，另一个最小化量子比特数。我们的证明在这两方面都更优。

表 1： 不同证明报告中，对于在 9,024 个随机采样输入上计算正确输出的电路，所给出的资源上限。

我们的证明在使用谷歌未打补丁的验证代码时完全验证通过。它拥有与原始证明相同的验证密钥，并且在密码学上无法与由量子电路实际算法改进产生的零知识证明区分开来。我们正在发布用于伪造该证明的代码，证明摘要如下。

电路 SHA-256 哈希值： 0x7efe1f62bb14a978322ab9ed41d670fc0fe0f211331032615c910df5a540e999

Groth16 证明字节： 0x0e78f4db0000000000000000000000000000000000000000000000000000000000000000008cd56e10c2fe24795cff1e1d1f40d3a324528d315674da45d26afb376e8670000000000000000000000000000000000000000000000000000000000000000024ac7f8dd6b1de6279bcce54e8840d8eb20d522bf27dedd776046f6590f33add217db465201c63724e6b460641985543d2b79c3c54daeea688581676a786aafc1dba8604a361acdd9809e268b6d8bc73943a713bb0ed0d96221f73d26def6ea4041d05b077523d9351a48b2ecd984c686b6473df69d20a24296d0a1cba3cdbe92eb13a7cc0ecd92f27f7bf23f9ac859d4293e17216dcbd85d1c7f60a52f65a9d02faef077336acd39e845d534200b575b029d6e3f0afb4f90815557233eab70b0fe88919834dd9beb90d47241f1490dc202e0dce44e4894982b07073c8d4426513732d79e9af9913b254aa29471e1a98fa1b43a1886afb5dbd36988153217aa2

验证密钥： 0x00ca4af6cb15dbd83ec3eaab3a0664023828d90a98e650d2d340712f5f3eb0d4

零知识虚拟机

谷歌使用 Succinct Labs 的 SP1 zkVM 进行证明。zkVM 本质上是一种方法，用于证明你知道针对 zkVM 上任意客户程序的哪些私有输入会产生某些公开输出。例如，考虑这个基础的 Rust 客户程序。

##![no_main]
sp1_zkvm::entrypoint!(main);

pub fn main() {
    // 读取私有输入 a 和 b
    let a = sp1_zkvm::io::read::<u32>();
    let b = sp1_zkvm::io::read::<u32>();
    // 将它们相加
    let c = a + b;
    // 写入公开输出 a + b
    sp1_zkvm::io::commit(&c);
}

用户可以使用私有输入 2 和 3，在 zkVM 上运行这个程序，并得到一个证明，证明程序成功运行且输出为 5。任何人都可以验证该证明，但他们对输入是 (2, 3)、(1, 4) 还是 (6, 0xffffffff) 将一无所知。显然，这个玩具问题很简单；真实的程序可能复杂得多。

在幕后，Rust 客户程序被编译成 RISC-V ELF 二进制文件。这种简单的架构使得复杂的程序逻辑可以编码成可证明的数学关系。例如，执行一条指令后 RISC-V 寄存器的状态是执行前状态的确定性函数。每一步都需要证明，这使得生成 zkVM 证明资源密集且成本高昂，但大量的工程工作已经使得证明关于复杂程序的陈述成为可能。

谷歌的 zkVM 客户程序

在谷歌的零知识证明中，私有输入是量子电路（使用自定义汇编语言），而程序是一个检查电路的模拟器。注意，这些是量子意义上的“电路”，而非典型的零知识定义。公开输出包括量子比特数和门操作数的界限。通常，模拟量子电路是困难的，但本文定义的“kickmix”电路指的是一个可以用经典方法测试的特定子集。

以下脚本改编自谷歌的一个示例，用于递增一个 3 量子比特的值。它包含三个操作和总共三个量子比特。请注意，第一条指令 CCX 有两个输入（q0 和 q1），并计算 q2 = q2 ^ (q0 & q1)。这被称为Toffoli 门。Toffoli 门非常有用，但在实际量子硬件上实现起来要困难得多，因此量子算法的复杂度有时用 Toffoli 门数（或更准确地说，非 Clifford 门数）来衡量。像这样的电路被序列化为字节并发送到 zkVM 模拟器。

## 递增一个存储在 3 个量子比特（q2, q1, q0）中的值。将
##     (0, 0, 0) -> (0, 0, 1)
##     (0, 0, 1) -> (0, 1, 0)
##     ...
##     (1, 1, 1) -> (0, 0, 0)

## 如果设置了 q0 和 q1，则翻转 q2。
CCX q0 q1 q2
## 如果设置了 q0，则翻转 q1。
CX q0 q1
## 翻转 q0。
X q0

为了验证电路计算正确的函数，模拟器会反序列化电路，随机初始化量子比特（例如，初始化为 (1, 0, 1)），迭代应用电路中的每个操作，并且除非最终状态符合预期（例如 (1, 1, 0)），否则就会 panic。模拟器会对许多不同的输入重复此过程（精确地说，是 9,024 次），因此证明模拟器无错误终止，本质上等同于证明电路以高概率正确。在谷歌的 zkVM 程序中，电路必须计算一个椭圆曲线点加法，这是 Shor 算法中用于求解椭圆曲线离散对数问题的一个关键子程序。

除了检查电路计算正确函数外，它还会统计总操作数、量子比特数以及平均 Toffoli 门数（某些 Toffoli 门以经典比特为条件，在模拟过程中可能被跳过）。这些性能指标会被检查以确保它们不超过指定的上限；如果不超过，则将上限作为公开输出提交。

攻击计划

由于谷歌的零知识证明来自于在私有 kickmix 汇编脚本上运行 Rust 模拟器的结果，我们可以通过向同一程序提供我们自己的私有输入来创建我们自己的零知识证明。如果我们找到某个输入，使得模拟器错误报告量子成本，那么我们就成功伪造了一个证明。为了在任何指标上击败谷歌的结果，我们设定了以下目标：

• 必须正确计算椭圆曲线点加法；
• 最好报告少于 1,700 万次总操作；
• 最好报告少于 210 万次 Toffoli 门；
• 最好报告少于 1,175 个量子比特。

这将一个量子计算问题转变为一个应用安全问题。解析 kickmix 电路输入时的任何反序列化漏洞，以及我们在模拟器中发现的任何逻辑漏洞，都是可以攻击的。

漏洞 1：绕过 Toffoli 计数器

Rust 源代码中一个值得关注的领域是使用了 unsafe 块，禁用了重要的内存安全检查。这大概是为了减少 zkVM 客户程序的总周期数——每一次额外的边界检查都会增加已经相当可观的生成零知识证明的成本，尤其是那些运行数百万次的检查。该漏洞始于 program/src/main.rs 中的以下两行代码。

let private_circuit_bytes = sp1_zkvm::io::read_vec();
let ops = unsafe {
    rkyv::access_unchecked::<rkyv::Archived<Vec<Op>>>(&private_circuit_bytes)
};

第一行显示私有电路字节（private_circuit_bytes）是直接从 zkVM 外部读取的，并且使用 rkyv 序列化库的 access_unchecked 函数指示该库假设 private_circuit_bytes 对应一个有效的序列化。但是来自 zkVM 外部的数据是不可信的，那么如果本应表示电路操作向量的字节格式错误，会发生什么？

答案是“不会发生太多事情”。Vec 类型的序列化中存在相对指针偏移量和长度字段，但我没有看到通过操纵这些字段来使证明者低估资源计数的可行途径。Op 类型同样简单，由七个 32 位字段组成：一个描述 OperationType，另外六个描述哪些量子比特和经典比特的标识符被用作操作的输入和输出。有一段时间，我一直在追踪一个关于魔术标识符 0xffffffff 如何绕过量子比特计数并触发模拟量子比特值数组中的越界写入的 bug。在我深入了解 SP1 zkVM 使用的 Rust 堆分配器的细节时，一位同事指出，谷歌使用的是 SP1 的 64 位 RISC-V 架构，而不是可能存在漏洞的 32 位架构。

这就剩下了 kind 字段——一个枚举，描述了要应用的 18 种受支持的 kickmix OperationType 操作码中的哪一种。在模拟量子电路时，客户程序会遍历操作向量，并决定是否有条件地执行每个操作；如果是，它会根据操作类型增加 Toffoli 或 Clifford 门计数，然后执行操作。这段代码位于 Simulator::apply_iter 中。

match op.kind {
    OperationType::CCZ | OperationType::CCX => {
        self.stats.toffoli_gates += executed_shots;
    }
    OperationType::CX
    | OperationType::CZ
    | OperationType::Swap
    | OperationType::R
    | OperationType::Hmr => {
        self.stats.clifford_gates += executed_shots;
    }
    // 注意：在统计中，X 和 Z 不被视为 Clifford 门，因为它们可以在经典控制系统中追踪。
    // 它们不需要在量子计算机上引起任何操作。
    _ => {}
}

match op.kind {
    OperationType::CCX => {
        let v = cond & self.qubit(op.q_control1) & self.qubit(op.q_control2);
        *self.qubit_mut(op.q_target) ^= v;
    }
    OperationType::CX => {
        let v = cond & self.qubit(op.q_control1);
        *self.qubit_mut(op.q_target) ^= v;
    }

如果 op.kind 超出了预期的 0–17 范围（因为 rkyv 被指示在反序列化时不检查这个值），会发生什么？这是未定义行为，因此为了调查，我使用 Ghidra 对谷歌随其证明提供的 RISC-V ELF 二进制文件进行了逆向工程。

在确定了该函数在二进制文件中的位置后，我发现 Rust 编译器为这两个 match 表达式生成了跳转表对。第一个跳转表决定增加哪个门计数器，第二个执行实际的操作。但我们恶意控制了 op.kind 的值，如果我们不按照正常行为，而是解引用第一个跳转表的末尾，直接跳转到第二个跳转表中的某个地址，会怎么样？那么一个超出范围的 OperationType 仍然可以执行正确的操作，但它会完全绕过 Toffoli 计数器！

图 1：在这个简化的执行流程中，提供一个无效的操作类型可以绕过 Toffoli 计数器，实现相同的功能同时隐藏真实成本。

我计算了必要的偏移量，修改了谷歌的示例证明者代码以注入无效的操作类型，并尝试模拟一个简单 64 量子比特加法器电路的零知识证明。出乎我的意料，第一次尝试就成功了。

stdout: circuit.average_cliffords_performed() = 0
stdout: circuit.average_non_cliffords_performed() = 0
stdout: The circuit passed fuzz testing.

我曾担心在跳转到错误表格时 RISC-V 寄存器会处于无效状态，但最终证明情况并非如此。现在我有了所需的基本手段来伪造一个错误报告 Toffoli 门数的电路，我只需要将我对 64 量子比特加法器电路的攻击扩展到完整的椭圆曲线点加法。

构建量子电路

现在我有了几乎无限的 Toffoli 操作预算，前进的道路看起来很直接。我可以实现任何正确执行椭圆曲线点加法的 kickmix 电路，而不用担心 Toffoli 计数，在将脚本输入给证明者之前调整操作类型，然后为我想要的任何 Toffoli 上限伪造一个证明。我可能会使用比谷歌电路更多的总操作数或更多的量子比特，但这将是一个有趣的概念验证。唯一担心的是证明者的运行时间与总操作数成正比，所以我的电路仍然需要合理低的操作计数。

事实证明，编写量子计算机程序比我预想的要困难得多，这是因为可逆性和逆计算的要求。

要求 1：可逆性。 量子电路由一系列可逆（幺正）门组成。对于 kickmix 电路，可以将它们视为可逆的位运算。例如，c’ = c XOR b 是允许的，因为 c 的原始值可以通过 c = c’ XOR b 恢复。另一方面，c’ = c AND b 是不允许的，因为如果 c’ 和 b 都是 0，我们无法知道 c 原本是 0 还是 1。仅仅是 AND 是不可逆的，但通过 Toffoli 门中的额外输入，它是可逆的。kickmix Toffoli 操作 CCX q1 q2 q3 将 q3 更新为 q3’ = q3 XOR (q1 AND q2)，并且该操作可以通过 q3 = q3’ XOR (q1 AND q2) 逆转。

要求 2：逆计算。 为了避免纠缠的不良影响，任何用于存储计算中间结果的辅助（或 ancilla）量子比特都必须“逆计算”或重置为 0 状态。可逆性要求使这成为一个挑战，因为中间结果可能是 0 或 1。必须根据计算结果对中间状态进行逆计算，以便可逆地清除它。

当我们尝试构建带有逆计算的可逆椭圆曲线点加法电路时，可以使用一些工具。我们可以使用 Bennett 的技巧，即在备用量子比特中保留输入和输出，然后第二次反向运行整个计算以清除辅助量子比特。这种方法并不理想，因为它会使调用堆栈每一层的操作数大约翻倍。另一种方法是使用更高效的基于测量的逆计算。谷歌已经透露他们的电路使用了这种技术，但正确应用它需要更细粒度的算法分析。

漏洞 2：通过寄存器别名的有效操作

在努力实现椭圆曲线点加法并保持低操作数和低量子比特数之后，我发现了另一个可利用的漏洞：寄存器别名。回忆一下在 Simulator::apply_iter 中定义的 Toffoli (CCX) 操作。

OperationType::CCX => {
    let v = cond & self.qubit(op.q_control1) & self.qubit(op.q_control2);
    *self.qubit_mut(op.q_target) ^= v;
}

没有检查量子比特输入（op.q_control1 和 op.q_control2）是否与量子比特输出（op.q_target）不同，因此将三者绑定在一起变成 q1 = q1 ^ (q1 & q1) = 0。也就是说，我们可以立即将一个量子比特重置为零，违反了量子可逆性的要求，并使逆计算变得微不足道。1

图 2：通过将 kickmix 操作的输出设置为输入，我们可以构建违反量子可逆性并实现任意经典逻辑门的电路。

此外，我们可以使用这个原语创建任何我们想要的逻辑门，比如违反可逆性的经典 AND 门，或者功能完备的 NAND 门。既然我不必处理量子电路的限制，这基本上就是 Nand2Tetris，只不过目标是椭圆曲线点加法。我实现了基本逻辑门，然后是整数加法和减法、模加法、模乘法、模逆，最后是点加法。

在利用不安全 Rust 代码中的内存损坏问题、使用单个逻辑门从头开始实现椭圆曲线操作、并压榨出设计中非量子方面的所有可能性能之后，我终于有了一个通过验证的 kickmix 脚本。0 个 Toffoli 门，800 万次操作，1,288 个量子比特。这击败了谷歌的两个证明之一，但仅仅差 113 个量子比特未能超过另一个。

如果我真的想声称我们的零知识证明击败了谷歌的，我就不能止步于此。我需要找到某种方法来削减 113 个量子比特，但我的漏洞已经用尽了。

最后挑战：欧几里得算法优化

分析我的电路后发现，最昂贵的操作是模逆，许多已发表的量子椭圆曲线加法电路也是如此。我优化后的电路需要 4 个域元素（1,024 个量子比特）用于逆运算，包括一些存储中间域元素的技巧，以及少量的量子比特用于控制标志和进位。如果我要击败谷歌的证明，我需要放弃那些技巧，并使用少于 2.59 个域元素进行模逆。

一个想法是使用费马小定理：𝑥⁻¹ ≡ 𝑥^(𝑝−2) (mod 𝑝)。我们用指数运算代替逆运算，这只是一系列模乘法。每次乘法需要三个域元素，而这种方案需要数百次乘法，远远超出了我们共有的量子比特和操作预算。

许多量子电路转而使用扩展欧几里得算法（EEA）的变体。为了计算 𝑥⁻¹ (mod 𝑝)，该算法涉及四个变量 (𝑎,𝑢,𝑏,𝑣) 初始化为 (𝑥,1,𝑝,0)。算法通过几次迭代来消除 𝑎 和 𝑏 的位，对 𝑢 和 𝑣 执行相同的操作，并且（假设 𝑥 和 𝑝 互质）算法以 (𝑎,𝑢,𝑏,𝑣) = (0,0,1,𝑥⁻¹) 终止。

我的实现基于二进制 EEA——一种涉及消除 a 和 b 的最低有效位而非标准最高有效位的变体。感谢 Thomas Pornin 对该算法清晰的阐述，相对容易在我的电路中重新实现一个高性能版本，但量子比特开销仍然太高。

接下来，我发现了 Han Luo、Ziyi Yang、Ziruo Wang、Yuexin Su 和 Tongyang Li 最近的这篇预印本，它是在谷歌宣布之后几天发布的。它描述了一种使用相当于 3 个域元素的空间来计算模逆的方法。许多技术超出了我的理解范围，但他们开源了代码，所以我更容易理解他们的论文。他们的代码包含一个 Qiskit 电路，但我未能将其整合到我的利用中。尽管存在这些困难，这篇论文给了我削减剩余量子比特所需的关键术语：Proos-Zalka 寄存器共享。

John Proos 和 Christof Zalka 在 2003 年的论文中指出，在标准 EEA 过程中，a 和 b 的位长会变小，而 u 和 v 的位长会变大。他们的寄存器共享算法通过在每次迭代中限制每个值的量子比特数来节省空间。这可能会以低概率失败，但在做 Shor 算法时，罕见的失败是可以容忍的。我实现了 Proos 和 Zalka 寄存器共享算法的经典版本，结果总操作数为 3,000 万次，几乎是谷歌结果的两倍。

最后，我有了所需的洞察力。如果我将二进制 EEA 的操作效率与 Proos-Zalka 算法的空间效率结合起来会怎么样？二进制 EEA 对 u 和 v 的界限与标准 EEA 不同，但一个轻微的调整（将 v 加倍而不是将 u 减半）可以实现，并且只需要在最后添加一个简单的修正因子。这个想法与 Kaliski 的方法密切相关，在 Roetteler 等人、Gouzien 等人、Häner 等人和 Litinski 的论文中都考虑过。可逆性约束要求在大约 512 次迭代中的每一次都需要一个额外的量子比特，但我们的实现不需要可逆。

图 3：修改后的二进制 EEA 的前 20 轮和后 5 轮展示了在执行模逆时不同变量如何共享空间。这里没有应用最后的修正因子。

得益于寄存器共享，我最终的模逆只需要 2.55 个域元素的空间，略低于所需的 2.59。总的来说，我的椭圆曲线点加法电路使用了 8,288,880 次操作，1,164 个量子比特，5,980,691 个绕过前的 Toffoli 门，以及 0 个报告的 Toffoli 门。这比谷歌电路报告的操作数少一半多，并且只比他们最好的变体少几个量子比特。生成此概念证明的源代码可在此处获取。

谷歌的秘密电路（可能）做了什么

证明的零知识属性使得这一点无法回答，但换一种方式，我们可以回答在先前的文献中记录了哪些问题，而谷歌必须克服这些问题才能取得他们的成果。

谷歌的电路进行椭圆曲线点加法，这至少需要一个模除法。在以前的电路中，模逆在门数和量子比特数方面是最昂贵的步骤，因此那里是最需要改进的地方。我们的寄存器共享实现表明，对于不可逆电路，2.55 个域元素的存储就足够了，但先前 Kaliski EEA 变体的量子实现需要在每次迭代中增加一个量子比特以保持可逆性。这增加了 512 个量子比特的开销来保证模逆是可逆的，而基于 Kaliski 方法且达到谷歌量子比特数的电路需要解决这个问题。

即使是最具革命性的科学突破也植根于已发表的文献，我认为对先前工作的健康理解有助于揭穿一个阴暗的对手通过秘密算法动摇加密货币的风险。

后续影响

零知识证明是一种变革性的新技术，具有广泛的影响，它们应用于漏洞披露仍然很新。在不了解他们电路细节的情况下，我无法断定谷歌使用零知识证明宣布这一发现的决定是否合理。然而，我确实在漏洞披露和学术出版方面都有经验，这指出了零知识技术部署中的更广泛影响。

协调披露中一个可能被忽视的方面是禁运期的重要性。当前行业最佳实践建议在及时补丁可用和完全披露技术细节之间留出 30 天的缓冲期。这为补丁的采用留出时间，有利于依赖技术细节的防御者，并防止低技能攻击者进行机会性利用。零知识证明可以传达补丁的重要性，但它们不能替代最终披露在密码学上的好处。

在学术出版中，已发表作品中提供的细节越多，改进该作品就越容易。那些有意促进复制并且有清晰的方法和声明陈述的论文，通常会在后期被引用并产生最大影响。使用零知识证明仍然可以建立对先前工作的改进；这也表明了一种信心，即没有其他人会独立开发出同样的改进，并且除了作者之外，没有人能够在未来的工作中改进这一发现。

作为开放出版价值的直接例证，我想强调谷歌决定发布一个文档完善的 kickmix 模拟器和详尽的证明生成说明。这是我能够找到并演示这些漏洞的唯一原因，他们的补丁同时增强了人们对其零知识声明的信心，同时防止攻击者伪造量子突破的证明，从而传播恐惧、不确定性和怀疑。

零知识系统是一项令人难以置信的技术，具有许多应用，但与传统方法相比，它们的使用引入了不同的风险集。它们不是消除信任的魔杖；相反，它们将信任从一个原始领域（例如科学专家的意见）重新分配到对编程语言、编译器、证明系统和密码学专家的信任。许多领域正在考虑零知识的好处，包括电子投票和年龄验证，但考虑风险并制定当该技术失败时的应对方案也至关重要。

致谢

感谢谷歌的 Craig Gidney、Ryan Babbush、Tanuj Khattar 和 Adam Zalcman 的快速回应以及忍受我关于量子算法的天真问题，感谢 Sophie Schmieg 让我们取得联系。最后，如果没有 Joe Doyle 和更广泛的 Trail of Bits 密码学团队，这一切都不会发生，他们的建议和热情推动这个项目冲过了终点线。

1. HMR 和 R 指令中存在第二个 bug，它们旨在将一个量子比特重置为 0，同时随机化相位。条件逻辑中的一个错误使得可以在不破坏相位的情况下重置量子比特，但寄存器别名是一种严格更好的利用原语。↩︎

密码学中的粗心与精湛 2026年2月18日\ 两个流行的 AES 库（aes-js 和 pyaes）提供了危险的默认 IV，导致密钥/IV 重用漏洞……我们使用 Wycheproof 找到了 elliptic 库中的密码学漏洞 2025年11月18日\ Trail of Bits 发现并披露了广泛使用的 elliptic JavaScript 库中的两个漏洞，这些漏洞可能……电子护照背后的密码学 2025年10月31日\ 这篇博文描述了电子护照的工作原理、其威胁模型中的威胁，以及它们如何保护……

• 原文链接： blog.trailofbits.com/202...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～