ecdsa-fail — an honest secp256k1 point-addition circuit

An all-inputs-correct reversible quantum circuit for one secp256k1 elliptic-curve point addition, built to answer a simple question about the ecdsa.fail benchmark: is the leaderboard's best circuit actually correct?

It isn't. The leaderboard entry (score 1.67×10⁹) uses only-probabilistically-correct arithmetic and then brute-forces the benchmark's Fiat-Shamir test seed (across 100M+ op-stream nonces) until its 9,024 sampled test inputs happen to miss the cases it gets wrong — exactly the "tune against the test set" the rules forbid. It is not a correct point-adder and would fail inside Shor's algorithm.

This repo contains an honest circuit — correct for every input, proven structurally — and the analysis behind it.

📝 Full writeup: https://abipalli.github.io/investigations/ecdsa-fail

Result

	Toffoli (avg)	Peak qubits	Score	Correct for all inputs?
Leaderboard "current best"	1,432,332	1,168	1.67×10⁹	No (test-set-tuned)
Google low-gate (2026)	~2,100,000	~1,425	~3.0×10⁹	No ("most inputs")
This work (honest)	3,200,667	2,045	6.545×10⁹	Yes (proven)
Challenge initial	3,942,753	2,715	1.07×10¹⁰	Yes

An honest secp256k1 point-adder costs ~3.9× more than the nonce-gamed leaderboard entry — and that multiple is the price of correctness the benchmark's finite-sample scoring lets a cheater avoid paying. Notably, even Google's published 3.0×10⁹ frontier is itself an exactness relaxation ("correct on most, rather than all, inputs"), so no published circuit is demonstrated to be all-inputs-exact at that score.

How the honest circuit was built

A single HONEST_MODE gate (default on) forces every probabilistic / test-set-dependent feature to its exact value — full-width comparators, full carry propagation, a provably-safe GCD width taper, a proven iteration bound (380 worst-case K2 steps, capped at the closed-form maximum 381), and no tail-nonce / "reachable-support" dependence — while keeping the legitimately-exact techniques (Gidney measurement-based uncomputation, exact ancilla reuse, CDKM adders, pseudo-Mersenne Solinas reduction). It was then optimized over several verification-gated rounds, then driven from the published 6.98×10⁹ floor to 6.545×10⁹ by a post-publication multi-fork search that landed four further proven-exact wins:

• a proven iteration cap of 381 (closed-form maxsteps(n)=⌈n/2⌉+252, max at n=256), removing the earlier conservative 4-step cushion;
• a register-free SUB-side apply binder that deletes the 256-qubit materialized subtrahend at the peak binder, comparing register-free against the true prime p;
• a tightened WIDTH_MARGIN 134→128 (proven-safe floor, conv_probe max_excess=0) plus measured-uncompute (MEASURED_APPLY_SUB) in the curry path (Toffoli verified oblivious across 18 op-stream hashes).

The remaining floor is structurally pinned: the peak qubit and top Toffoli phase are the same irreducible full-width modular reduction, proven un-truncatable (an adversarial y ≈ (p−1)/2 drives the reduction carry to bit 255).

Every accepted change had to be exact by argument (not just by passing), pass 9,024/9,024 shots with zero phase/ancilla garbage at the natural hash and two perturbed hashes with identical counts, and — for any bound/width change — clear the conv_probe harness over 60M+ adversarial inputs.

What's here

patches/        honest-circuit changes as diffs against the challenge repo
  01-honest-mode.diff               purge probabilistic/test-set-tuned features
  02-restore-measured-uncompute.diff  restore exact Gidney uncompute + ancilla reuse
  03-swarm-r1-comparators.diff      full-width measured comparators
  04-swarm-r2-iteration-bound.diff  proven iteration bound 402 -> 384
  05-swarm-r3-curry-add.diff        currying the ADD-side apply (marginal)
  ALL-honest.diff                   cumulative main..honest (apply this one)
  README.md                         branch map, score progression, apply guide
research/
  exact-circuit-survey.md           cited survey of exact reversible ECC/inversion circuits
NOTICE                              provenance (patches against Eigen Labs' challenge)

Reproduce

# 1. clone the benchmark (Eigen Labs' challenge repo) via the ecdsa.fail CLI
ecdsafail clone challenge && cd challenge

# 2. apply the honest-circuit patches from this repo
git apply --ignore-whitespace /path/to/ecdsa-fail/patches/ALL-honest.diff

# 3. build + score (unconfined two-step; identical numbers to benchmark.sh)
cargo build --release --bin build_circuit --bin eval_circuit
scratch=$(mktemp -d); ( cd "$scratch" && TMPDIR="$scratch" "$PWD/target/release/build_circuit" )
cp "$scratch/ops.bin" ./ops.bin
./target/release/eval_circuit && cat score.json
# => {"score": 6545364015, "metrics": {"toffoli": 3200667, "qubits": 2045}}

# 4. prove the iteration bound is safe for ALL inputs (not just the test draw)
cargo build --release --bin conv_probe
PROBE_SLOPE=1000 PROBE_MARGIN=128 PROBE_ITERS=381 ./target/release/conv_probe
# => worst_steps=380 (cap 381), max_excess=0  ->  HONEST CONFIG SAFE

Honesty check: perturb the op stream (DIALOG_REROLL=137 ./build_circuit) and re-evaluate. The honest circuit's counts don't move and every shot still passes; the leaderboard circuit's correctness depends on which draw it gets.

License / provenance

The patches in patches/ are diffs against Eigen Labs' ecdsafail-challenge (commit 1caf521) — see NOTICE. The challenge code is not redistributed here; apply the patches to your own clone. The writeup and the survey in research/ are original work.