🔐 Beyond the Square-Root Barrier
UQO Working Paper No. 34 — Automated Discovery of Algebraic and Algorithmic Shortcuts in Bitcoin Cryptography
TL;DR — Can a systematic, automated exploration of secp256k1, ECDSA, BIP340 Schnorr and SHA-256 find a computational shortcut the literature has missed? We ran a six-stage discovery pipeline (verified literature database → 25 structured hypotheses → exact symbolic checks → seeded experiments with provenance → Lean 4 machine-checked statements → six-way classification) autonomously under a written mandate. Outcome: no shortcut; every secp256k1 invariant verified twice with exact arithmetic; the libsecp256k1 GLV constants shown to be the Eisenstein ideal (π̄−1): a1 = (t−f)/2 − 1, b1 = −f; the "orbit quotient group" conjecture refuted; 6 000 synthetic ECDLP instances (20–56 bits) giving α ∈ [0.48, 0.50] and the rho constant 1.254·√n (theory 1.2533); order-6 automorphism classes 2.42× in iterations (√6) but ≈ 1× in wall time in our engine; BIP340 batch verification 3.1×; reduced-step SHA-256 diffusion/bias/SAT calibrations far below the published 31-step records; bit-level SHA-256 identities and signature facts machine-checked. Everything synthetic; nothing bears on deployed systems.
📌 Status
| Item | Value |
|---|---|
| Version | 1.0 (2026-11-01) — 74 pages, 16 figures, 22 tables, 129 references |
| SSRN | not yet submitted |
| Journal | — (candidate venues: Journal of Cryptology, DCC, IACR ToSC/TCHES depending on emphasis) |
| Code & data | fully reproducible from this repository (synthetic instances only; see Appendix A of the paper) |
🎯 What this paper does
The mandate (docs/MANDATE.md, pasted by the author on 2026-11-01) asks an autonomous research agent to test whether
unexplored algebraic transformations or algorithmic strategies improve on the established attacks on Bitcoin's
primitives — and to reject them rigorously if not. Four axes: (A) secp256k1 structure, (B) algorithmic complexity of
the ECDLP and of signature verification, (C) reduced-step SHA-256, (D) the discovery methodology and formal
verification. Hypotheses live in hypotheses/ (one file each, 16 mandatory fields), their evaluation in
research_log/discovery_log.jsonl and Table 15 of the paper.
Core objects:
E: y² = x³ + 7 over F_p, p = 2²⁵⁶ − 2³² − 977, #E = n prime
φ(x, y) = (βx, y) = [λ](x, y), End(E) = Z[ω], GLV lattice = (π̄ − 1)·Z[ω]
Q = dG (generic cost Θ(√n); √6 from Aut(E); nothing more)
sG = R + eP (BIP340); H(x) = y (SHA-256, 64 steps)🏆 Headline results
| Object | Result | Classification |
|---|---|---|
| secp256k1 parameters and invariants (14 facts) | Python = PARI/GP; twist cofactor 220-bit prime; embedding degree 253-bit; no 2-torsion; 4p = t² + 3f² | known, reproduced |
| libsecp256k1 GLV constants | a1 = (t−f)/2 − 1, b1 = −f, a2 = a1 − b1, b2 = a1; lattice = ideal (π̄−1); found by the identity search, then proved | known structure, explicit form |
| Orbit-quotient "group of order n/6" | impossible (proof + 1 500/1 500 counterexamples) | rejected |
| ECDLP scaling, 3 840 generic + 2 400 j=0 instances | α ∈ [0.478, 0.500]; rho 1.254·√n [1.21, 1.30]; BSGS 1.50·√n; kangaroo 1.94·√n | known, reproduced |
| Order-6 automorphism classes | 2.42× [2.19, 2.70] fewer iterations (√6 = 2.449); wall-clock 0.95× in this engine | known, reproduced + implementation observation |
| Automated iteration-function search (25 designs) | nothing below the random-mapping constant; r = 2, 3 walks 3.8× / 2.3× worse | rejected shortcut |
| Parallel DP collision search | 22.1× on 28 threads (M3 Ultra), 14.8× on 16 | known, reproduced |
| Preprocessing | online cost 1.5·√(n/T); per-instance speed-up up to 42× | known, reproduced |
| BIP340 batch verification | 7.9 µs/sig at b = 2048, 3.10× [3.05, 3.16] vs single (k256); saturation explained | known, reproduced |
| Implementations | pure Python 7.4 ms vs libsecp256k1 13.2 µs per Schnorr verify (560×) | empirical |
| SHA-256 reduced steps | full diffusion at step 6 (W_0), no first-order regularity from step 5; generic SAT: preimages only with 16 free bits beyond 16 steps, collisions up to 18 steps (UNSAT for ≤ 8), 9-step local collision reproduced (conforming pairs for all 32 bit positions) | empirical / known |
| Lean 4 (32 s build, no sorry) | Ch/Maj identities, linearity and bijectivity of Σ0, Σ1, σ0, σ1 (refuting our conjecture that σ0/σ1 are singular), step bijection, schedule inversion, 9-step linearised local collision, ECDSA malleability, Schnorr correctness | machine-checked |
🗂 Repository layout
beyond-square-root-barrier/ (git: wp34_uqo)
├── CLAUDE.md, docs/MANDATE.md # operational summary and the verbatim mandate
├── src/wp34/ # exact-arithmetic library: ec, secp256k1, ecdsa, schnorr (BIP340), sha256, dlp, provenance
├── theory/ # derivation notes + SymPy symbolic checks + cost models
├── experiments/
│ ├── baselines/ # secp256k1_facts.py (Python + PARI/GP), scalar_mult_opcount.py
│ ├── synthetic_ecdlp/ # rho_engine (Rust), ecdlp_study.py, run_batch_remote.py, analyze_ecdlp.py, preprocessing, index-calculus probe
│ ├── signature_benchmarks/ # sigbench (Rust: libsecp256k1 + k256, own Straus/Pippenger), run_bench.py
│ ├── reduced_round_sha256/ # diffusion, bias, CNF encoder, SAT/SMT preimage & collision grids, local collision
│ └── automated_discovery/ # identity_search.py, registry.py (hypothesis registry → discovery log + table)
├── formal/ # Lean 4 project (bv_decide), formal/README.md lists every theorem
├── hypotheses/ # H01–H25 structured records
├── literature/ # db.yaml (82 items), records.md, research_gaps.md, unverified.md
├── results/ # JSON results with provenance blocks (host, versions, seed, command)
├── figures/ # generated figures (copied to paper/figures)
├── tests/ # pytest gates (core, DLP reference, Rust engine fixtures, signature cross-checks, CNF)
├── scripts/ # make_tables.py (numbers.tex), write_hypotheses.py, fig_ec_geometry.py
├── research_log/ # dated narrative entries + discovery_log.jsonl
└── paper/ # main.tex, sections/, appendix/, tables/ (generated), figures/, references.bib (129 verified) → main.pdf🚀 Quick start
uv venv --python 3.12 .venv && uv pip install -r requirements.txt
brew install pari cadical kissat z3 # PARI/GP (point counting), SAT/SMT solvers
.venv/bin/python -m pytest -q tests/ # cross-implementation gates
.venv/bin/python experiments/baselines/secp256k1_facts.py
.venv/bin/python experiments/automated_discovery/identity_search.py
cargo build --release --manifest-path experiments/synthetic_ecdlp/rho_engine/Cargo.toml
.venv/bin/python experiments/synthetic_ecdlp/ecdlp_study.py all # job files (PARI/GP)
.venv/bin/python experiments/synthetic_ecdlp/run_batch_remote.py --engine experiments/synthetic_ecdlp/rho_engine/target/release/rho_engine \
--jobs results/synthetic_ecdlp/scaling_generic.jobs.json --out results/synthetic_ecdlp/scaling_generic_$(hostname -s).json --parallel 8
.venv/bin/python experiments/synthetic_ecdlp/analyze_ecdlp.py
(cd formal && lake build)
.venv/bin/python experiments/automated_discovery/registry.py && .venv/bin/python scripts/make_tables.py
(cd paper && make)🔬 Integrity
Synthetic curves and keys only; no real wallets, addresses, third-party keys or blockchain data; full-strength
primitives analysed through exact algebra and legitimate implementations. Every number in the paper is generated from
a saved result file by scripts/make_tables.py or analyze_ecdlp.py (LaTeX macros in paper/tables/numbers*.tex).
📝 Notes
- Series standard:
Recherche-UQO/HARMONISATION.md. Deviation: the mandate's required directories (theory/,experiments/,formal/,hypotheses/,literature/,research_log/) are kept at the root in addition to the standardsrc/,scripts/,results/,figures/,paper/. - Built autonomously by Claude Code (Claude Fable 5.1) on 2026-11-01 on the author's laptop and MacLustr nodes
M3U96a, M3U96b, M2U64; see
research_log/.