UQO Working Papers · WP34 · v1.0
Beyond the Square-Root Barrier: Automated Discovery of Algebraic and Algorithmic Shortcuts in Bitcoin Cryptography
A hypothesis-driven, reproducible study of secp256k1, ECDSA, BIP340 Schnorr and SHA-256 with machine-checked identities and controlled negative results
- Year
- 2026
- First release
- November 2026
- Latest revision
- November 2026
- Publication status
- Working paper
No shortcut past the square-root barrier: an autonomous pipeline checked 25 hypotheses against Bitcoin's primitives and reports controlled negatives
secp256k1's structure is fully explained by complex multiplication by Z[ω] (the libsecp256k1 GLV constants are the coordinates of π̄ − 1), Pollard rho matches 1.254√n on 6,240 instances, batch Schnorr verification saturates at 3.1×, reduced SHA-256 yields to SAT only up to 18 steps, and the word-level identities are machine-checked in Lean 4.
Abstract
Bitcoin's security rests on the elliptic-curve discrete-logarithm problem on secp256k1, on SHA-256, and on the ECDSA and BIP340 Schnorr signature schemes. The generic cost of the discrete logarithm, Θ(√n), is a theorem in the generic-group model; the curve's unusual structure, a special prime, j-invariant 0 and complex multiplication by the Eisenstein integers, has long invited speculation that an algebraic shortcut might exist. The paper tests this speculation with an autonomous, six-stage discovery pipeline (verified literature base, 25 structured hypotheses, exact symbolic checks, seeded experiments with full provenance, Lean 4 machine-checked statements, six-way classification) executed by an AI research agent under a written mandate that forbids assuming shortcuts exist.
Results. Every secp256k1 parameter and invariant is verified twice with exact arithmetic; End(E) = Z[ω] leaves nothing beyond the six automorphisms; the GLV lattice is the ideal (π̄ − 1), which gives the hard-coded libsecp256k1 constants in closed form; the automorphism orbits admit no compatible group law; prime-field index calculus and all transfer attacks are excluded quantitatively. A native engine solved 6,240 synthetic ECDLP instances of 20–56 bits: empirical exponents 0.48–0.50, rho constant 1.254√n against the random-mapping prediction 1.2533, order-6 classes 2.42× fewer iterations (√6) but no wall-clock gain in this implementation, 22× parallel speed-up on 28 threads, the predicted time–memory and preprocessing trade-offs, and no iteration-function design below the random-mapping floor. BIP340 batch verification reaches 3.1× and saturates for an identified reason; ECDSA and Schnorr verify at the same cost and differ in proof structure.
Reduced-step SHA-256 diffuses fully in six steps, shows no first-order regularity beyond five, and yields to generic SAT search only up to 18-step collisions and 2^16-bit preimages, far below the 31-step records; the 9-step local collision is reproduced and its linear part proved. Lean 4 proofs cover the word-level identities, the bijectivity of the step and of all four Σ/σ functions (refuting the pipeline's own conjecture that σ0, σ1 are singular), the schedule inversion, the linearised local collision, ECDSA malleability and Schnorr correctness. The pipeline produced sixteen reproductions with measured constants, six empirical observations, three rejected conjectures and no claim of a weakness; the paper argues that this is the correct output for automated mathematical research on cryptographic standards, and releases everything needed to reproduce it.
Key findings
25
structured, falsifiable hypotheses tested through a six-stage pipeline under a no-assumed-shortcut mandate
6,240
synthetic ECDLP instances (20–56 bits) solved by a native engine; exponents 0.48–0.50
1.254√n
measured Pollard rho iterations vs the random-mapping prediction 1.2533√n
(π̄ − 1)
the GLV lattice ideal: libsecp256k1's hard-coded constants in closed form
3.1×
BIP340 batch verification speed-up, saturating for an identified reason
18 steps
largest reduced-round SHA-256 collision reached by generic SAT search (records: 31 steps)
Scientific contributions
- Algebraic structure of secp256k1 fully accounted for
- Complex multiplication by Z[ω] yields the √6 reduction in rho iterations and the halving of doublings in scalar multiplication, determines the GLV constants of libsecp256k1 in closed form, and leaves no room for a further endomorphism, a compatible group law on automorphism orbits, or index-calculus and transfer attacks.
- Generic algorithms measured, not assumed
- A native engine with operation counts and provenance reproduces the random-mapping theory on 6,240 instances, including the order-6 iteration saving (2.42×) without wall-clock gain, 22× parallel scaling on 28 threads, and the 1.5√(n/T) preprocessing trade-off; an automated search over iteration functions cannot beat the floor.
- Signature schemes compared on cost and proof structure
- ECDSA and BIP340 Schnorr verify at the same cost and differ in proof structure; batch verification is the one real, consensus-neutral speed-up and saturates near 3×.
- Reduced-step SHA-256 under SAT
- Full diffusion in six steps, no first-order regularity beyond five, 18-step collisions and 2^16-bit preimages as the reach of generic solvers, and the 9-step local collision reproduced with its linear part proved.
- Machine-checked identities and a methodology for automated discovery
- Lean 4 proofs of word-level identities, Σ/σ bijectivity (refuting the pipeline's own conjecture), schedule inversion, ECDSA malleability and Schnorr correctness; the controls that prevented over-interpretation (operation counts beside timings, two implementations per component, negative controls, exact arithmetic, provenance, literature match before the word new) are documented as the pattern for automated research on cryptographic standards.
Methodology
Methodology (5)
Six-stage hypothesis-driven pipeline
Verified literature base, 25 structured hypotheses, exact symbolic checks, seeded experiments with full provenance, machine-checked statements and a six-way classification rubric executed by an AI research agent under a written mandate.
Exact algebra of the curve
Endomorphism ring, automorphism orbits, GLV lattice as the ideal (π̄ − 1), and quantitative exclusion of index calculus and transfer attacks.
Native experimental engine
Pollard rho with order-6 classes, parallel, time–memory and preprocessing variants, with an automated search over iteration-function designs against the random-mapping floor.
SAT-based cryptanalysis of reduced SHA-256
Diffusion and regularity tests, collision and preimage search with generic solvers, reproduction of the 9-step local collision.
Formal verification and classification
Lean 4 proofs separated from informal statements; every candidate result classified as reproduction, observation, rejected conjecture or new only with a literature match.
Research data
- No external data: generated instances with provenance
- 6,240 synthetic ECDLP instances of 20–56 bits generated from seeds, with operation counts, timings and provenance recorded for every run; secp256k1 parameters and invariants verified twice with exact arithmetic.
- Verified literature base
- A curated, checked bibliography of the discrete-logarithm, endomorphism, signature and SHA-256 cryptanalysis literature against which every candidate result is classified before the word new can be used.
- Formal artefacts
- Lean 4 statements and proofs for the word-level identities, Σ/σ functions, schedule inversion, linearised local collision, ECDSA malleability and Schnorr correctness; SAT instances for reduced-step collisions and preimages.
Reproducibility
- Everything needed to reproduce the sixteen reproductions, six observations and three rejected conjectures is released: hypotheses, experiments with seeds and provenance, formal proofs, figures and logs
- Two implementations per component, negative controls per family and exact arithmetic throughout
- Lean 4 formalisation of the word-level and signature-equation facts
- Full LaTeX source of the 74-page paper
Research artifacts
Version history
| Version | Date | Description | File |
|---|---|---|---|
| v1.0current | November 2026 | Current manuscript as published on www.spboucher.ai (revised edition after the 2026-10-17 scientific review for papers 1–17). | PDF · 74 p. |