# 🔐 Beyond the Square-Root Barrier **UQO Working Paper No. 34** — *Automated Discovery of Algebraic and Algorithmic Shortcuts in Bitcoin Cryptography* [](paper/main.pdf) [](requirements.txt) [](experiments/synthetic_ecdlp/rho_engine) [](formal/) [](results/) [](https://uqo.ca) [](mailto:simon-pierre.boucher@uqo.ca) > **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 ```bash 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 standard `src/`, `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/`.