{"revision": {"id": "f0924215-61aa-11f1-a065-040140774501", "node_id": "5243e3fe-6146-11f1-8ce9-040140774501", "user_id": "680aec8e-3391-11f1-95d9-040140774501", "author": "russell", "data": "secp256k1 Point-Addition Challenge \u2014 Lumbda Attack\r\n====================================================\r\n\r\n| **Author:** foxhop \u00b7 agent blackops\r\n| **Started:** 2026-06-04\r\n| **Status:** Phase B reversible arithmetic landed; first lever sweep measured at p=11; no upstream submission yet\r\n| **Upstream challenge:** ecdsa.fail_ (Eigen Labs \u00b7 Google Quantum AI lineage)\r\n| **Substrate:** lumbda.com_\r\n\r\n.. _ecdsa.fail: https://ecdsa.fail\r\n.. _lumbda.com: https://lumbda.com\r\n\r\n----\r\n\r\n.. contents::\r\n   :depth: 2\r\n   :local:\r\n\r\n----\r\n\r\nWhat This Page Tracks\r\n---------------------\r\n\r\nA quantum-reversible attack on a secp256k1 point addition, written entirely in\r\nlumbda \u2014 a Lisp/Scheme derivative across four implementation tiers: Python\r\nbytecode VM, C tree-walker + JIT, C + x86_64 JIT, & pure x86_64 assembly.\r\nLumbda's docs & live runtimes sit at lumbda.com_; this page covers our attack\r\nitself, scored by Toffoli count \u00d7 peak qubit width.\r\n\r\nLower score wins. Every factor of two saved at point addition multiplies straight\r\nthrough Shor's algorithm into a factor of two off our resource estimate for\r\ncracking secp256k1 \u2014 a curve that protects Bitcoin & Ethereum.\r\n\r\n----\r\n\r\nWhere This Work Lives in Our Stack\r\n-----------------------------------\r\n\r\necdsa.fail (an Eigen Labs challenge sponsored by Eigen Labs, descended from\r\nGoogle Quantum AI's *Securing Elliptic Curve Cryptocurrencies against Quantum\r\nVulnerabilities*, March 2026) accepts Rust submissions only \u2014 that defines a\r\ncontract format, not our research substrate. Our search runs in lumbda; Rust\r\nonly ever sees a final, validated circuit at submission time.\r\n\r\nWhy lumbda \u2014 four reasons:\r\n\r\n- **Cross-tier portal validation.** Every variant emits an identical result\r\n  S-expression across Python, C tree-walker, & asm. Byte-mismatch on any tier\r\n  halts promotion to a next phase. Rust gives us one tier with no cross-tier\r\n  check.\r\n- **Fleet sharding via TCP + S-expression portals.** Lumbda hands candidate\r\n  evaluation across spare CPU on our GPU boxes; Rust carries no equivalent\r\n  without bespoke distribution code.\r\n- **A CUDA path already exists.** Our ``bend`` primitive on lumbda.com_\r\n  dispatches GPU work over a binary wire (magic ``BSHK``). Bend hands lumbda's\r\n  upstream-format ``ops.bin`` to a CUDA worker, receives \u03a3 (sigma, sum-of)\r\n  Clifford & \u03a3 Toffoli totals back \u2014 same byte-identical portal contract our\r\n  hash demo proves.\r\n- **Future CUDA growth feeds back.** Porting upstream's Rust simulator to CUDA\r\n  costs multi-week with one-shot payoff. Growing lumbda's tier ladder costs\r\n  less & feeds every other lumbda workload.\r\n\r\n----\r\n\r\nPhase B \u2014 Reversible Arithmetic Landed\r\n---------------------------------------\r\n\r\nTwelve steps after Roetteler et al. (2017), modular arithmetic over secp256k1's\r\nprime field, lumbda-native:\r\n\r\n- **Steps 1\u20138** \u2014 modular add, subtract, multiply, square, inverse\r\n  (Bernstein-Yang safegcd flavor), exponentiation\r\n- **Steps 9\u201310** \u2014 refined Bernstein-Yang modular inverse wired into a real\r\n  point-addition circuit\r\n- **emit-ops.bin walker** \u2014 lumbda \u2192 (to) upstream QECCOPS1 binary format,\r\n  full kind table 0..17 coverage, cross-validated against demo_ops\r\n  byte-identical on a real round trip\r\n\r\nCross-tier validated on Python tier. C-tier & asm-tier escalation routes\r\nthrough a QEMU guest (``ecdsa/vm-runner.sh``) \u2014 host policy locked after a\r\n2026-06-03 C-tier OOM crash. Asm-tier carries no default garbage collector;\r\nthree prior neoblanka crashes (2026-04-16, 2026-04-17, 2026-06-03) cemented\r\nper-tier escalation rules. See lumbda's CLAUDE shard on asm memory\r\ndiscipline.\r\n\r\n----\r\n\r\nFirst Lever Sweep \u2014 2026-06-05/06\r\n-----------------------------------\r\n\r\nA six-variant cartesian product of our active Phase B knobs, scored at\r\np=11 n+1=5 (point-add width small enough to fit a full sweep into one\r\nafternoon of CPU) through our closed-loop pipeline:\r\n\r\n::\r\n\r\n   lever-variants.lsp  \u2192  emit-ops-bin walker  \u2192  /tmp/variant-N.bin\r\n                                                          \u2193\r\n                                  bend wire \u2192 3090-ai gpu-worker\r\n                                                          \u2193\r\n                                       demo_ops portal \u2192 results.tsv\r\n\r\nThree boolean Phase B knobs surveyed produce six structurally distinct\r\ncircuits (refined-B-Y collapses when B-Y itself stays off):\r\n\r\n==  =========  =============  ======  ============  ===========\r\nid  mul       inv             n_ops   \u03a3 Toffoli     vs default\r\n==  =========  =============  ======  ============  ===========\r\n5   solinas    refined-B-Y    32 333  **475 648**   **\u221265.2 %**\r\n2   litinski   refined-B-Y    34 468  518 656       \u221262.0 %\r\n4   solinas    textbook-B-Y   48 763  749 056       \u221245.1 %\r\n1   litinski   textbook-B-Y   50 898  792 064       \u221242.0 %\r\n3   solinas    Fermat         77 439  1 027 584     \u221224.7 %\r\n0   litinski   Fermat (def.)  94 214  1 365 504     0.0 %\r\n==  =========  =============  ======  ============  ===========\r\n\r\n**Headline:** combined Solinas mod-mul + refined Bernstein-Yang mod-inv\r\ncuts \u03a3 Toffoli by 65.2 % versus our default lever stack (Litinski\r\nschoolbook mod-mul + Fermat inversion).\r\n\r\nKnob attribution\r\n~~~~~~~~~~~~~~~~~\r\n\r\n*Inversion knob* (refined-B-Y vs Fermat) dominates:\r\n\r\n- at Litinski mod-mul: 1 365 504 \u2192 518 656 = **\u221262.0 %**\r\n- at Solinas mod-mul:  1 027 584 \u2192 475 648 = **\u221253.7 %**\r\n\r\n*Multiplication knob* (Solinas vs Litinski) carries a non-additive\r\ninteraction with inv-knob choice:\r\n\r\n- at Fermat:        1 365 504 \u2192 1 027 584 = **\u221224.7 %**\r\n- at textbook-B-Y:    792 064 \u2192   749 056 =  \u22125.4 %\r\n- at refined-B-Y:     518 656 \u2192   475 648 =  \u22128.3 %\r\n\r\nFermat does repeated mod-muls so a faster mod-mul compounds; Bernstein-Yang\r\ncarries mod-mul-light arithmetic so a mul-knob contribution fades.\r\n**\u221262 % combined with \u22128 % rounds to \u221265 % rather than \u221270 %** \u2014 exactly\r\nour observed math.\r\n\r\nCross-scale prediction check\r\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\r\n\r\nA small-fixture screen (p=5, n+1=4) ran during lever-space discovery\r\npredicted refined-B-Y at roughly \u221256 %; an independent p=251 ground-truth\r\nreference predicted \u221240 %. Our p=11 measurement landed at \u221236.5 % within a\r\nSolinas branch \u2014 within three percentage points of our p=251 prediction.\r\n**A cheap small-width screen survives a scale jump faithfully**, which\r\nlets future runs sweep wide at p=11 first, filter to winners, then spend\r\nexpensive p=251 budget only on a short list.\r\n\r\nSubstrate now closed-loop\r\n~~~~~~~~~~~~~~~~~~~~~~~~~~\r\n\r\nEvery piece of an end-to-end research engine sits live:\r\n\r\n- ``lever-variants.lsp`` exposes ``(lever-permutations)`` for arbitrary\r\n  knob cartesians\r\n- ``emit-ops-bin.lsp`` walks any Phase B circuit form into a QECCOPS1\r\n  binary on disk\r\n- ``bend`` dispatches an ops.bin path to whichever fleet worker holds a\r\n  warm CUDA context\r\n- ``demo_ops`` returns \u03a3 Clifford & \u03a3 Toffoli via a portal\r\n- ``dispatch-sweep.py`` auto-resumes against new ``.bin`` files\r\n\r\nNo piece needs hand-running. A next sweep at wider p only waits on emit\r\nthroughput, never on substrate plumbing.\r\n\r\n----\r\n\r\nForm D Structural Finding \u2014 2026-06-05\r\n---------------------------------------\r\n\r\n``cuda-clifford-stabilizer`` as originally scoped on our bend catalog\r\n(`lumbda.com/bend <https://lumbda.com/bend.html>`__) does not apply to a\r\npoint-addition circuit. Build agent measured Toffoli fraction at 13.87 %\r\n(well under a 40 % stabilizer-win threshold), then noticed our circuit\r\ncarries no Hadamard or S gates \u2014 only X (Pauli-X), CX (controlled-X), CCX\r\n(Toffoli), CZ, CCZ, SWAP, R, HMR, Z, & NEG. State never leaves a\r\ncomputational basis. Aaronson-Gottesman tableau compression buys nothing\r\nwhen superposition does not exist; it reduces to exactly what a per-shot\r\nkernel already does, at one bit per qubit per shot.\r\n\r\nTwo replacement directions landed 2026-06-05; both pivots converged on one\r\ndiagnosis.\r\n\r\n**Axis-flip refactor** (per-candidate parallel kickmix sim) \u2014 DONE\r\n(foxhop commit ``1f7ac9d``). 217 Mops/s (mega-ops per second) at K=32 M=4\r\non a RTX 3090; 23.7\u00d7 (times) over per-shot N=4 at same M. Both kernels\r\nsaturate at ~220\u2013250 Mops/s. Axis-flip's win comes from\r\noccupancy-amortization, not bandwidth redistribution. Right tool for a\r\nmany-candidates \u00d7 few-shots search-loop early-screen pattern.\r\n\r\n**QECCOPS2 packed ops.bin** \u2014 DONE (foxhop commit ``90484ca``). 1.07\u00d7\r\nkernel speedup, 2.33\u00d7 on-disk shrink (716 MB \u2192 307 MB). Our original 3.5\u00d7\r\nprojection assumed 56 B/op stayed VRAM-resident; ``ops_loader.c`` already\r\nnarrowed to 28 B on load, so realistic ceiling sat at 1.17\u00d7. Per-shot\r\nstate traffic (qubits + bits per thread) dominates kernel bandwidth ~85\u00d7\r\nover op stream.\r\n\r\n**Diagnosis:** 3090 saturates compute at ~250 Mops/s on a kickmix circuit,\r\nnot bandwidth. Next macro-lever: multi-GPU fan-out across our fleet\r\n(3090-ai, ai/4090, cammy P40, guile CPU bulk).\r\n\r\n----\r\n\r\nMeasured Numbers \u2014 RTX 3090\r\n----------------------------\r\n\r\nAgainst HEAD's 12.8 M-op kickmix ``ops.bin`` (716 MB) via bend:\r\n\r\n=========  ======  =======  =======  =======  ===========\r\nn_batches  shots   wire-s   cpu-ms   gpu-ms   gpu/cpu\r\n=========  ======  =======  =======  =======  ===========\r\n1          64      5.5      42       5 107    0.008\r\n16         1 024   7.3      850      5 800    0.146\r\n64         4 096   11.4     3 444    6 216    0.553\r\n128        8 192   17.1     7 060    6 604    **1.07**\r\n=========  ======  =======  =======  =======  ===========\r\n\r\nCrossover at ~115 batches. GPU kernel carries ~5 070 ms fixed overhead\r\n(init + alloc + upload) plus ~12 ms per batch; CPU runs ~55 ms per batch.\r\nConditional ops in a kickmix circuit cause branch divergence \u2014 one form\r\nwhere GPU does not dominate at small batch counts.\r\n\r\nHonest signal, not hype.\r\n\r\n----\r\n\r\nWhat Lives Where\r\n----------------\r\n\r\n- **Lab repo (private)** \u2014 lumbda source for our attack, circuit build /\r\n  sim / score / candidate sweep, QEMU envelope around C-tier & asm-tier\r\n  runs, run artifacts under ``runs/lumbda-*/``\r\n- **Bend catalog & wire protocol** \u2014 `lumbda.com/bend\r\n  <https://lumbda.com/bend.html>`__\r\n- **Upstream challenge** \u2014 `ecdsafail/ecdsafail-challenge\r\n  <https://github.com/ecdsafail/ecdsafail-challenge>`__\r\n- **Lineage** \u2014 `Google Quantum AI \u00b7 ECC quantum vulnerabilities\r\n  <https://research.google>`__ (Zenodo dataset 19597130, March 2026)\r\n\r\n----\r\n\r\nPareto Frontier We Aim To Beat\r\n-------------------------------\r\n\r\nUpstream README reports two Google private Pareto points sitting below a\r\ntextbook 1.07 \u00d7 10\u00b9\u2070 score; upstream claims both points sit strictly\r\nbeatable.\r\n\r\n==========================================  ==================  ===========  ============\r\nVariant                                     Toffoli (avg/shot)  Peak qubits  Score\r\n==========================================  ==================  ===========  ============\r\nChallenge initial circuit (textbook)        3 942 753           2 715        1.07 \u00d7 10\u00b9\u2070\r\nGoogle private, low-qubit Pareto point      2 700 000           1 175        3.2  \u00d7 10\u2079\r\nGoogle private, low-gate Pareto point       2 100 000           1 425        3.0  \u00d7 10\u2079\r\n==========================================  ==================  ===========  ============\r\n\r\nOur lumbda-tier validation gates each variant against byte-identical\r\ncross-tier portals before we ever spend Rust submission budget against\r\n9024 Fiat-Shamir-derived test points.\r\n\r\n----\r\n\r\nWhy Track This Publicly\r\n-----------------------\r\n\r\nA challenge of this shape rewards aggressive, asymmetric search. Every\r\nfactor of two off a Toffoli count, every qubit shaved off peak width,\r\nmultiplies straight through Shor's algorithm. Documenting our path\r\npublicly \u2014 what we tried, what saturated, what surprised us \u2014\r\ncontributes intellectual capital to a commons that has historically locked\r\nthis work behind paid lab pages.\r\n\r\nThis page tracks public-facing progress only. Detail logs, asm-tier safety\r\nenvelopes, & raw run artifacts stay in our lab repo.\r\n\r\n----\r\n\r\n| *Updated 2026-06-06.*\r\n| *Cross-post anchor for lumbda.com/bend & external links.*", "source_format": "rst", "revision_number": 2, "created": 1780752223364}}