Trail of Bits Forges Google's Quantum Cryptanalysis Zero-Knowledge Proof via Rust Memory Bugs
Trail of Bits researchers exploited memory safety and logic vulnerabilities in Google's Rust-based zero-knowledge proof code to forge a proof that falsely claims a quantum circuit can break elliptic curve cryptography in 9 minutes with zero Toffoli gates.
Two weeks ago, Google's Quantum AI group published a zero-knowledge proof of a quantum circuit so optimized, they concluded that first-generation quantum computers will break elliptic curve cryptography keys in as little as 9 minutes. Today, Trail of Bits is publishing their own zero-knowledge proof that significantly improves Google's on all metrics — but not due to a quantum breakthrough. Instead, the Trail of Bits team exploited multiple subtle memory safety and logic vulnerabilities in Google's Rust prover code to forge a proof that is cryptographically indistinguishable from a legitimate one. Google has patched their proof, and their scientific claims remain unaffected, but the incident highlights the unique attack surface introduced by zero-knowledge virtual machines (zkVMs).
Google's proof used Succinct Labs' SP1 zkVM to calculate the cost of a quantum circuit on three key metrics: total operations, Toffoli gate count, and qubit count. The private input was the quantum circuit itself, written in a custom assembly language, and the zkVM guest program simulated the circuit to verify its correctness. The public output included bounds on the number of qubits and gate operations. Google, along with coauthors from UC Berkeley, the Ethereum Foundation, and Stanford, published proofs for two circuits — one minimizing gates, the other minimizing qubits. Trail of Bits' forged proof improves on both, claiming zero Toffoli gates and fewer total operations and qubits.
The forged proof fully verifies when using Google's unpatched verification code. It has the same verification key as Google's original proofs and is cryptographically indistinguishable from a zero-knowledge proof resulting from actual algorithmic improvements to the quantum circuit. Trail of Bits is releasing the code they developed to forge the proof. The vulnerabilities exploited include memory safety issues and logic errors in the Rust prover code, which allowed the researchers to craft a proof that passes verification without actually running the quantum circuit simulation correctly.
Zero-knowledge virtual machines like SP1 are designed to prove that a program ran correctly on private inputs without revealing those inputs. However, the complexity of the prover code introduces a new attack surface. As Trail of Bits notes, "Having to prove every step makes generating zkVM proofs resource-intensive and costly, but significant engineering work has enabled proving statements about complex programs." The vulnerabilities they found demonstrate that even carefully audited Rust code can contain flaws that undermine the integrity of the proof system.
Google has patched the vulnerabilities in their prover code, and the underlying scientific claims about quantum cryptanalysis remain unaffected. The incident does not change the timeline for quantum computers breaking elliptic curve cryptography — Google's original estimates still stand. However, the episode serves as a cautionary tale for the growing use of zkVMs in security-critical applications, from blockchain to cryptography. As Trail of Bits concludes, "this story reflects the unique attack surface that systems introduce when they use zero-knowledge proofs."
The research underscores the importance of rigorous security auditing for zkVM implementations, which are increasingly used in decentralized finance, identity systems, and other high-stakes environments. While the specific vulnerabilities have been patched, the broader lesson is that the trustworthiness of a zero-knowledge proof depends not only on the mathematical soundness of the protocol but also on the correctness of the software that implements it. As zkVMs become more prevalent, the security community will need to develop new techniques for verifying their implementations.