This repository contains resources for the Trail of Bits blog post detailing how we beat Google's zero-knowledge proof that they have a high-efficiency quantum circuit for elliptic curve cryptanalysis. It includes our forged proof, instructions for verification, and code to generate the quantum circuit which exploits vulnerabilities in the unpatched zkVM simulator code.
The full proof binary is here, and the results comparing Google's proofs to ours are below.
| Resource Type | Google’s Low-Gate | Google’s Low-Qubit | Our Proof |
|---|---|---|---|
| Total Operations | 17,000,000 | 17,000,000 | 8,300,000 |
| Number of Qubits | 1,425 | 1,175 | 1,164 |
| Toffoli Count | 2,100,000 | 2,700,000 | 0 |
A summary of the proof is as follows.
Circuit SHA-256 Hash: 0x7efe1f62bb14a978322ab9ed41d670fc0fe0f211331032615c910df5a540e999
Groth16 Proof Bytes: 0x0e78f4db0000000000000000000000000000000000000000000000000000000000000000008cd56e10c2fe24795cff1e1d1f40d3a324528d315674da45d26afb376e8670000000000000000000000000000000000000000000000000000000000000000024ac7f8dd6b1de6279bcce54e8840d8eb20d522bf27dedd776046f6590f33add217db465201c63724e6b460641985543d2b79c3c54daeea688581676a786aafc1dba8604a361acdd9809e268b6d8bc73943a713bb0ed0d96221f73d26def6ea4041d05b077523d9351a48b2ecd984c686b6473df69d20a24296d0a1cba3cdbe92eb13a7cc0ecd92f27f7bf23f9ac859d4293e17216dcbd85d1c7f60a52f65a9d02faef077336acd39e845d534200b575b029d6e3f0afb4f90815557233eab70b0fe88919834dd9beb90d47241f1490dc202e0dce44e4894982b07073c8d4426513732d79e9af9913b254aa29471e1a98fa1b43a1886afb5dbd36988153217aa2
Verification Key: 0x00ca4af6cb15dbd83ec3eaab3a0664023828d90a98e650d2d340712f5f3eb0d4
Google provided scripts for verifying their ZK proofs in a Zenodo dataset. Our attack targets version 1, and version 2 contains patches. Instructions for installing dependencies are in docs/getting_started.md. The environment requires Rust, Go, and optionally Docker. Commands for verification are provided at the end of run_proofs.sh. Google’s proof artifacts are in the proofs/ directory, and our proof artifact is in proof_trailofbits.bin.
# Verify Google's proofs
cargo run --release -p verifier -- \
--vkey proofs/vkey.bin --proof proofs/low_toffoli/proof_9024.bin
cargo run --release -p verifier -- \
--vkey proofs/vkey.bin --proof proofs/low_qubits/proof_9024.bin
# Verify our proof
cargo run --release -p verifier -- \
--vkey proofs/vkey.bin --proof proof_trailofbits.binThe output of the final command includes the following.
Successfully verified Groth16 SNARK proof.
Circuit hash commitment: 0x7efe1f62bb14a978322ab9ed41d670fc0fe0f211331032615c910df5a540e999
Demanded Number of tests: 9024
Demanded Qubit count: 1164
Demanded Average non-Clifford count: 0
Demanded Total ops: 8300000
The verification commands check the ZK proofs against the verification key, which is a concise cryptographic representation of the zkVM guest program. Alternatively, you can use --elf proofs/zkp_ecc-program to provide the verifier with the guest program ELF binary. If you omit this flag entirely, the verifier uses a Docker container to rebuild the guest program binary from the source code in program/.
Running gen_secp256k1_tob.py generates a 142MB kickmix script named ec_secp256k1_add_into.kmx. To achieve the 0-Toffoli proof, use prove.rs.diff to patch prover/prove.rs in the Zenodo repository. This modifies untrusted code running outside of the zkVM to manipulate the serialization of the kickmix circuit.
Proof generation instructions are in the Zenodo repository. We followed the instructions in docs/sp1_cluster_deployment_guide.md on a cloud machine with 4 NVIDIA H100 GPUs and ran the following command to generate the proof.
./run_proofs.sh --num-tests 9024 --kmx "ec_secp256k1_add_into.kmx" --qubit-counts 1164 --toffoli-counts 0 --total-ops 8300000 --proving-mode "multi-gpu" > proofs/ec_secp256k1_add/log_run.out 2>&1 &The forged proof took approximately 4 hours to generate.
