ECDSA.Fail: Open Autoresearch for Optimizing Elliptic-Curve Point Addition in Shor's Algorithm
Jieyi Long, Theodore Pender, Zhao Huang, Manuel B. Santos, Samrendra Kumar Singh, Bartosz Naskręcki, Bit Wonka, Joe Doyle, Pierre-Luc Dallaire-Demers, Francesco Giannicola, Ruben M. L. Paschoarelli, Oli Freuler, Jackie Chia-Hsun Lee, Vasily Gnuchev, Gopi Kannappan, John Boyer, Xavier Butler, Akash Balasubramani, Jordan Newman, Bereket Dereje, Alexander Hertlein, Robert Kodra, Lucas Levy, Shaan Patel, JT Rose, Matt Zweil, Okechukwu Wisdom, Tarek El-Eter, Edison Lee, Michael Dong, Alan Li, Anto Joseph, Gajesh Naik, Gautham Anant, Soubhik Deb, Justin Drake
quant-ph, cs.CR
2026-09-09
ECDSA.Fail let 100+ human-agent teams optimize reversible secp256k1 point addition; in eight weeks Q×T fell from 10.75B to 1.496B, more than 50% below Google's published threshold.
Bitcoin and Ethereum signatures sit on secp256k1. A fault-tolerant machine running Shor's algorithm could recover private keys from exposed public keys. Point addition dominates the logical cost: a windowed schedule needs about 28 of these calls, so the width and Toffoli count of one addition nearly set the whole-algorithm estimate.
Until recently the best constructions came from small specialist teams. Google Quantum AI attested unpublished thresholds with a zero-knowledge proof; Schrottenloher then published an open design in the same roughly 3 billion Q×T band. ECDSA.Fail, launched by Eigen Labs at the end of May 2026, turned the same primitive into a public contest. Humans and coding agents submitted circuits to one locked evaluator and a shared leaderboard.
The scored task is reversible mixed addition: a quantum accumulator R plus a classically supplied addend A. The score is S = Q × T, peak live logical qubits times average executed Toffoli-equivalent gates. A submission must be value-correct, ancilla-clean, and phase-clean. The instruction set is restricted to kickmix operations so a classical evaluator can check every test input, rather than sampling or trusting the submitter.
The 9,024 test points are Fiat-Shamir derived from a hash of the serialized circuit. A 48-bit identity nonce can retarget the test set without changing function, width, or Toffoli count. Searching for a clean island is allowed, but a 1% error rate has landability about 2^{-130}, outside that nonce space.
Open Autoresearch is the surrounding process. Teams pick a public base (the current best, a Pareto point, or an off-frontier design), propose a change, and promote only what the evaluator accepts. Failures stay in the record. Over about eight weeks, more than 100 participants using Claude Code, Codex, GPT, Grok, GLM, Kimi and other models produced 400-plus promoted submissions.
The arithmetic bottleneck is modular inversion. The product-score winner uses dialog-GCD: a Euclidean walk records branch decisions, then reverse replay rebuilds Bézout coefficients. Jump-2 retimes consecutive divsteps into macro-steps; a base-5 codec packs three symbols into seven qubits instead of nine, shrinking a 261-step transcript from 783 qubits to 609. Squaring uses a Karatsuba split plus the pseudo-Mersenne identity 2^{256} ≡ 2^{32} + 977 (mod p), accumulating into the destination so no 512-bit product register stays live. The low-width branch packs shrinking remainders and growing cofactors into two shared physical banks.
After the cutoff, a ping-pong dialog-GCD dropped full-width comparisons from the Euclidean walk. It chooses add or subtract from the two lowest bits and updates the two operands in a fixed alternating order.
Against the baseline, the cutoff incumbent cut Q by 57.6%, T by 67.2%, and the product by 86.1%, about 7.19×. Google's published low-gate product is about 2.99B; this circuit sits more than 50% below that number. The paper treats the comparison as contextual: interfaces and accounting differ.
| Circuit | Q | T | Q×T |
| Baseline 30c8ded | 2,715 | 3,960,753 | 10.75B |
| Cutoff best 8e9c9a2 | 1,151 | 1,299,453 | 1.496B |
| Windowed variant | 1,162 | 1,684,161 | 1.961B after /p̂ |
| Post-cutoff ping-pong | 1,321 | 952,707 | 1.259B |
| Low-width b6f2b0a | 825 | 489M | 403B |
The windowed variant wraps the addend in a QROM lookup/use/unlookup: +11 qubits and about 29.6% more Toffoli. On 100,000 independent inputs, empirical success is 0.99809 (0.191% error), indistinguishable from the mixed circuit's 0.192%. The 825-qubit endpoint (later a public 813) pays about 489 million Toffoli, a different time-for-space branch. Of 400 scored competition commits, dead-code elimination was the primary change in 244 (61%); nonce rerolls were 19 (4.8%). Rare architectural swaps moved the frontier; the frequent commits mostly harvested the new regime.
For cryptanalysis, these are among the lowest publicly auditable secp256k1 point-addition operating points reported so far. They remain a kernel, not a full Shor attack and not a physical-resource estimate. For people building research agents, the more durable claim is methodological: cheap machine-checkable objectives, public intermediates, and independent human-agent teams can compound. FunSearch, AlphaEvolve, and The AI Scientist run centrally. This setup puts the evaluator and the repository on the open internet.
Agents were strong at implementation, regression, and local diagnosis. The Kaliski-to-dialog-GCD jump still needed a human literature connection. Submissions using that architecture appeared only after Schrottenloher published the ECDLP adaptation. Agents then implemented and refined it quickly. That is complementarity, not autonomous discovery.
The score is an empirical cost on finite, submission-dependent support. Approximate circuits can pass by nonce-selecting a clean island. The benchmark addend is classical; windowed Shor needs a coherent table lookup. The compatible variant covers a single call, not the 28-call schedule, Fourier layers, or postprocessing. Depth, parallelism, routing, and error correction sit outside S. The public archive has no complete attempt denominator, so success rates per try cannot be estimated. The trajectory is observational: it does not isolate what the same people would have achieved without agents.