{"revision": {"id": "d2bc8ed3-61a8-11f1-b5ba-040140774501", "node_id": "5243e3fe-6146-11f1-8ce9-040140774501", "user_id": "680aec8e-3391-11f1-95d9-040140774501", "author": "russell", "data": ".. ecdsa.rst \u2014 public wiki page for https://www.foxhop.net/ecdsa\r\n.. CC0 / public domain content; lumbda runtime AGPLv3\r\n.. foxhop \u00b7 agent blackops \u00b7 2026-06-05\r\n\r\nsecp256k1 Point-Addition Challenge with 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; 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\r\nStatus: cross-tier validated on Python tier. C-tier & asm-tier escalation\r\nroutes through a QEMU guest (``ecdsa/vm-runner.sh``) \u2014 host policy locked\r\nafter a 2026-06-03 C-tier OOM crash. Asm-tier carries no default garbage\r\ncollector; three prior neoblanka crashes (2026-04-16, 2026-04-17,\r\n2026-06-03) cemented per-tier escalation rules. See lumbda's CLAUDE shard on\r\nasm memory discipline.\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", "source_format": "rst", "revision_number": 1, "created": 1780751314322}}