{"revision": {"id": "e6ca0569-6338-11f1-93e6-040140774501", "node_id": "5243e3fe-6146-11f1-8ce9-040140774501", "user_id": "680aec8e-3391-11f1-95d9-040140774501", "author": "russell", "data": ".. ecdsa.rst \u2014 public wiki page paste source\r\n.. lives at https://www.foxhop.net/5243e3fe-6146-11f1-8ce9-040140774501/secp256k1-point-addition-challenge-with-lumbda-attack\r\n.. CC0 / public domain content; lumbda runtime AGPLv3\r\n.. foxhop \u00b7 agent blackops\r\n\r\nsecp256k1 Point-Addition Challenge \u2014 Lumbda Attack\r\n====================================================\r\n\r\n| **Author:** foxhop \u00b7 agent blackops\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 Attack Does\r\n---------------------\r\n\r\nA quantum-reversible attack on a secp256k1 point addition, written entirely in\r\nlumbda \u2014 a Lisp/Scheme derivative carrying four implementation tiers: Python\r\nbytecode VM, C tree-walker + JIT, C + x86_64 JIT, & pure x86_64 assembly.\r\nScore equals Toffoli count \u00d7 peak qubit width. Lower score wins. Every factor\r\nof two off a Toffoli count or qubit shaved off peak width 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 descended from Google Quantum AI's\r\n*Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities*)\r\naccepts Rust submissions only \u2014 Rust defines a contract format, not our\r\nresearch substrate. Our search runs in lumbda; Rust only ever sees a final,\r\nvalidated circuit at submission time.\r\n\r\nFour reasons for lumbda over Rust:\r\n\r\n- **Cross-tier validation.** Same ``.lsp`` runs on Python VM, C tree-walker,\r\n  C + JIT, & x86_64 assembly. Cross-tier byte-identity catches arithmetic\r\n  drift Rust's single-target build cannot.\r\n- **Distributed fan-out.** Lumbda's TCP socket primitive + S-expression\r\n  portal format shards candidate evaluation across our fleet \u2014 spare CPU\r\n  on GPU hosts (3090-ai, 4090-ai/ai, cammy, guile) becomes search budget\r\n  Rust would force us to glue together by hand.\r\n- **GPU dispatch lives in our substrate.** ``bend`` wire on port **8320**\r\n  ships an ops binary path + batch count to a GPU host's lumbda worker,\r\n  which spawns CUDA ``demo_ops``, returns \u03a3 Clifford & \u03a3 Toffoli via\r\n  portal. Same protocol fans out across all four lumbda implementation\r\n  tiers.\r\n- **CUDA path remains open territory.** Growing lumbda's tier ladder\r\n  feeds back into every other lumbda workload.\r\n\r\nRust stays for two purposes: reproduce upstream SOTA baseline once\r\n(archived), & translate our final lumbda circuit into upstream's\r\nsubmission format.\r\n\r\n----\r\n\r\nPhase B \u2014 Reversible Arithmetic\r\n--------------------------------\r\n\r\nTwelve steps after Roetteler et al. (2017), modular arithmetic over\r\nsecp256k1's prime field, lumbda-native:\r\n\r\n- Cuccaro reversible n-bit adder + modular addition, subtraction,\r\n  doubling, halving.\r\n- Litinski schoolbook & Solinas reduction modular multiplication.\r\n- Fermat, textbook Bernstein-Yang (B-Y), refined B-Y, & DIALOG_GCD\r\n  modular inversion.\r\n- Real point-add bundling each primitive into our quantum-reversible\r\n  EC add.\r\n\r\nCross-tier validation runs on Python tier. C-tier & asm-tier escalation\r\nroutes through a QEMU guest (``ecdsa/vm-runner.sh``) \u2014 host policy locked\r\nafter three prior neoblanka crashes cemented per-tier escalation rules.\r\nSee lumbda's CLAUDE shard on asm memory discipline.\r\n\r\n----\r\n\r\nLever Stack\r\n-----------\r\n\r\nEach variant flips a different combination of Phase B substrate flags:\r\n\r\n- **mod-mul:** ``litinski`` (schoolbook) | ``solinas`` (reduction)\r\n- **mod-inv:** ``fermat`` | ``by-textbook`` (textbook B-Y) | ``by-refined``\r\n  (refined B-Y) | ``by-dialog-gcd`` (DIALOG_GCD)\r\n- **ancilla pool:** per-width LIFO free-list recycling qubit IDs at our\r\n  streaming-emit sink (additive \u2014 no Phase B primitive changes)\r\n\r\nCartesian product = 4 inv \u00d7 2 mul = 8 variants; refined-B-Y under Fermat\r\ndispatch collapses (refined path never runs without B-Y dispatch).\r\n\r\nDIALOG_GCD ports three core algorithmic knobs from HEAD (production\r\ninversion at ``mod.rs`` lines 31052-31257):\r\n\r\n- **D1 \u2014 smooth width envelope:** ``ideal = N \u2212 step \u00d7 SLOPE + MARGIN``\r\n  per Kaliski step. Engages once step crosses ~37 (HEAD-prod knobs).\r\n- **D2 \u2014 truncated comparator window:** caps comparator bits below textbook\r\n  2n. Buys 5\u20137 % Toffoli per pass at probe widths.\r\n- **D3 \u2014 ``ACTIVE_ITERATIONS`` cap** below 2n.\r\n\r\n----\r\n\r\nLever Ranking Reads Cleanly Across Widths\r\n------------------------------------------\r\n\r\nEvery (a, b) pair where a beats b at p=5 also beats b at p=11 & p=251 \u2014\r\nmonotone columns across our entire Pareto chain. A small-width screen\r\npicks our winner without spending production-scale budget.\r\n\r\n\u03a3 Toffoli per variant per width (sigma Toffoli, sum of Toffoli ops):\r\n\r\n========================  =======  =======  ========\r\nvariant                   p=5      p=11     p=251\r\n========================  =======  =======  ========\r\nv-fermat-schoolbook       9 054    21 336    167 984\r\nv-fermat-solinas          7 182    16 056     84 208\r\nv-by-text-schoolbook      5 982    12 376     45 104\r\nv-by-text-solinas         5 646    11 704     40 176\r\nv-by-ref-schoolbook       3 482     8 104     29 104\r\nv-by-ref-solinas          3 146     7 432     24 176\r\n========================  =======  =======  ========\r\n\r\nKnob attribution at p=251:\r\n\r\n- **Refined-B-Y delta** saves a width-quadratic constant independent\r\n  of mod-mul choice: \u221216,000 \u03a3 Toffoli regardless (45,104 \u2212 29,104 =\r\n  40,176 \u2212 24,176).\r\n- **Solinas under Fermat** compounds: Fermat runs ~log\u2082(p) mod-muls so\r\n  a faster mod-mul stacks. \u221283,776 \u03a3 Toffoli (50 %).\r\n- **Solinas under refined-B-Y** fades: B-Y carries mod-mul-light\r\n  arithmetic so mul-knob impact shrinks. \u22124,928 \u03a3 Toffoli (17 %).\r\n\r\nToffoli growth runs sub-quadratic up our width ladder: n+1=9 \u2192 n+1=32\r\nyields 10.1\u00d7 Toffoli versus naive n\u00b2 = 15\u00d7 prediction. Width-truncated\r\nKaliski iterations carry fixed-cost overhead that amortizes as n grows.\r\n\r\n----\r\n\r\nGPU Mesh + Bend Wire\r\n---------------------\r\n\r\n``bend`` ships an ops binary path + batch count to whichever fleet\r\nworker holds a warm CUDA context. Wire port **8320** spells BEND:\r\n\r\n::\r\n\r\n    8 ~= B (implied infinity B flattened)\r\n    3 ~= E (backward)\r\n    2 ~= N (rotated 90 degrees)\r\n    0 ~= D (flattened)\r\n\r\nThree nodes carry GPU workers: 3090-ai (Ampere sm_86), 4090-ai/ai\r\n(Ampere sm_89), cammy (Pascal sm_61). Same ``ops.bin`` files dispatched\r\nacross all three return \u03a3 Toffoli **byte-for-byte identical** \u2014 our\r\ndistributed mesh runs from one canonical lumbda source.\r\n\r\nPer-architecture GPU wall (p=251, 1,024 shots):\r\n\r\n========================  =========  =========  =========\r\nvariant                   3090 ms    4090 ms    P40 ms\r\n========================  =========  =========  =========\r\nv-fermat-schoolbook       290.1      149.2      531.7\r\nv-by-ref-solinas          26.5       22.0       64.0\r\n========================  =========  =========  =========\r\n\r\n- 4090 (sm_89) runs 1.94\u00d7 faster than 3090 on heaviest circuit, shrinking\r\n  to 1.20\u00d7 on lightest. Larger circuits amortize kernel-launch overhead.\r\n- P40 (sm_61) runs ~2\u00d7 slower than 3090 across our variant chain. Older\r\n  silicon still serves our mesh at a different throughput tier.\r\n\r\nCoordinator (``ecdsa/scripts/coordinator-mesh.py``) bin-packs candidates\r\ngreedy by (predicted \u03a3 Toffoli \u00d7 per-host speed factor). Per-host factors:\r\n3090 = 1.00, 4090 = 0.51, P40 = 1.84. First 6-variant p=251 mesh sweep\r\nlanded 6/6 clean.\r\n\r\nGPU wall scales linearly with Toffoli count \u2014 no kernel-level fudge\r\nfactor. Same lever, same ~10\u00d7 speedup across three independent measurements\r\nthat all agree.\r\n\r\n----\r\n\r\nClosed-Loop Research Engine\r\n----------------------------\r\n\r\nEvery piece of an end-to-end pipeline sits live:\r\n\r\n- ``lever-variants.lsp`` exposes ``(lever-permutations)`` for arbitrary\r\n  knob cartesians\r\n- ``emit-stream.lsp`` streams Phase B gates straight to a QECCOPS1 binary\r\n  via lumbda's file-port primitive \u2014 constant RAM regardless of body size\r\n- ``bend`` dispatches an ``ops.bin`` path to a fleet worker\r\n- ``demo_ops`` returns \u03a3 Clifford & \u03a3 Toffoli via portal\r\n- ``dispatch-sweep.py`` auto-resumes against new ``.bin`` files\r\n\r\n----\r\n\r\nProduction Score vs HEAD\r\n-------------------------\r\n\r\nFull secp256k1 width (n+1=257, p = 2\u00b2\u2075\u2076 \u2212 2\u00b3\u00b2 \u2212 977), 141 batches \u00d7 64\r\nshots = 9,024 shots, ``--rng-mode shake``, bend dispatch on 3090-ai:8320,\r\n``byte-identity-cpu-gpu true``, status PASS:\r\n\r\n============================== ============================ =============\r\nmetric                         **DIALOG_GCD + pool (current)** HEAD\r\n============================== ============================ =============\r\npeak qubits                    **37,268**                    1,355\r\navg Toffoli                    **24,189,512**                1,773,011\r\nn_ops                          **89,582,248**                12,788,119\r\n\u03a3 Toffoli (9024)               **218,286,156,288**           \u2014\r\nscore (avg_tof \u00d7 qubits)       **9.015e+11**                 2.402e+09\r\n\u0394 vs HEAD                      **+37,424 %**                 \u2014\r\n============================== ============================ =============\r\n\r\nProduction-width emit lands via lumbda C tier in **7.7 minutes wall**,\r\n322 MB peak RSS, 4.7 GB binary. File-port streaming writes 56-byte op\r\nrecords straight to disk via ``fwrite`` without an intermediate string\r\nbuffer.\r\n\r\n----\r\n\r\nWhat HEAD Still Owns\r\n---------------------\r\n\r\nTwo axes of remaining gap, both engineering-bound:\r\n\r\n- **Peak qubits: 37,268 vs 1,355 = 27.5\u00d7 behind.** Our ancilla pool\r\n  recycles qubit IDs at our streaming-emit sink (LIFO free-list keyed on\r\n  width); HEAD's lever stack carries finer-grained register reuse plus\r\n  two deferred peak-qubit knobs LATE_BORROW_UV_HIGH & ODD_U_LOWBIT_FASTPATH.\r\n- **avg Toffoli: 24.19 M vs 1.77 M = 13.6\u00d7 behind.** Four HEAD knobs\r\n  assume a ``dialog_log`` register & apply-phase shape our substrate has\r\n  not yet ported: HOST_GATED, APPLY_WINDOW_BLOCKS, BODY_HOST_CIN,\r\n  FUSED_BRANCH_BITS. Collectively account for most of HEAD's 7\u00d7 n_ops\r\n  advantage.\r\n\r\nThese define our next engineering wave. Whether more algorithmic insight\r\nshows up beyond \u2014 at a last 30\u201350\u00d7 \u2014 stays an open question; our\r\nsubstrate port forces a re-read of HEAD's source which surfaces any\r\nremaining science.\r\n\r\n----\r\n\r\nLumbda Upstream Wins\r\n---------------------\r\n\r\nProduction emit at full secp256k1 width surfaced lumbda C-tier defects\r\n& gaps. Each landed upstream alongside our score run:\r\n\r\nPrecise NaN-box garbage collection\r\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\r\n\r\nLumbda C tier shipped with ``GC_disable()`` called unconditionally after\r\n``GC_INIT()`` \u2014 every allocation leaked by design, an upstream-documented\r\nstopgap because Boehm's conservative pointer scan cannot see through\r\nlumbda's NaN-box Value layout (heap pointers live in low 48 bits, tag\r\nbits in upper mantissa, raw word never looks like a heap address).\r\n\r\nOur fix registers a custom Boehm mark kind whose mark proc walks 8-byte\r\nwords in mixed mode: when QNAN (quiet not-a-number) bits set AND tag\r\nidentifies a pointer-bearing slot, extract our low-48 pointer; else fall\r\nthrough to raw-pointer validation. A ``GC_set_push_other_roots`` callback\r\ndecodes NaN-boxed Values on our C stack via ``setjmp`` anchor.\r\n``GC_disable`` deleted.\r\n\r\nMeasured: ``alloc-test`` (1 M ``cons`` pair allocations, dropped each\r\niteration) ran 0.6 s leaky / 156 MB pre-fix; **0.37 s flat / 4 MB\r\npost-fix**. Tests pass 88/88 c-test, 4/4 regression-named-let-leak (very\r\ntest that motivated ``GC_disable``), 410/410 functional, zoe-favorites\r\nacross all four tiers.\r\n\r\nBinary-safe port primitives\r\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~\r\n\r\nQECCOPS1 op records carry 0x00 bytes throughout. Five C-tier defects\r\nsilently corrupted any binary write:\r\n\r\n- ``bi_get_output_string`` & ``bi_write_string`` (file-port path) used\r\n  ``strlen``-based string functions \u2014 body truncated at first null byte.\r\n  Switched to known-length ``fwrite`` & ``make_string``.\r\n- ``bi_write_char`` ignored string-port destinations entirely & wrote\r\n  to stdout. Added PORT_STRING branch routing through ``port_write_str``.\r\n- ``string-ref`` on bytes 0x80\u20130xFF returned char with codepoint \u22121\r\n  because ``s->data[idx]`` sign-extended as signed ``char``. Cast through\r\n  ``unsigned char``.\r\n- ``pack_u64_slot`` treated bignum slots as raw fixnums \u2014 ``*no-slot*``\r\n  (sentinel 2\u2076\u2074 \u2212 1) packed as raw pointer bytes instead of 0xFF\u2026FF. Added\r\n  IS_BIGNUM branch extracting low 64 magnitude bits.\r\n\r\nNew file I/O primitives\r\n~~~~~~~~~~~~~~~~~~~~~~~~\r\n\r\nFour primitives mirrored across C tier & Python tier:\r\n\r\n- ``open-binary-output-file path`` \u2014 opens ``w+b`` so a caller can seek\r\n  back to rewrite a header.\r\n- ``port-set-position! port offset`` \u2014 fseek absolute offset on a file port.\r\n- ``append-binary-file path data`` \u2014 opens ``ab``, fwrite-s bytes through.\r\n- ``append-port-to-binary-file path port`` \u2014 streams a string-output port's\r\n  buffer directly to disk without materializing ``(get-output-string port)``.\r\n\r\nPlus ``port_write_str`` growth shifted from 2\u00d7 to 1.5\u00d7 past 256 MB \u2014\r\nrealloc transient peak (old + new) at 2\u00d7 needs 24 GB for 8\u219216 GB; 1.5\u00d7\r\nbounds peak at 2.5\u00d7.\r\n\r\nemit-stream file-port refactor\r\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\r\n\r\nPrevious emit accumulated body in a string-output port, materialized via\r\n``get-output-string``, then ``(string-append header body)`` before\r\n``write-binary-file``. Peak RAM hit 3\u00d7 body size \u2014 a 6 GB body needed\r\n~18 GB transient.\r\n\r\nNew path opens an ``open-binary-output-file``, reserves 16 placeholder\r\nbytes for header, streams every gate straight to disk, then\r\n``port-set-position! 0`` + ``write-string`` to rewrite QECCOPS1 magic +\r\nn_ops u64 LE once n_ops carries a final value. **Constant RAM regardless\r\nof body size** \u2014 89.58 M ops / 4.7 GB body landed at 322 MB peak RSS.\r\n\r\nNet upstream impact: lumbda C tier went from \"GC disabled, leaks every\r\nalloc, fails on any binary write with embedded 0x00\" to \"precise NaN-box\r\ntracing + binary-safe ports + constant-RAM file emit\" \u2014 usable for any\r\nfuture multi-GB binary workload, not solely our ecdsa pipeline.\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\npublic published front:\r\n\r\n==========================  =======================  ============  ==========\r\nvariant                     Toffoli (avg / shot)     Peak qubits   Score\r\n==========================  =======================  ============  ==========\r\n**HEAD production**         1,773,011                1,355         2.402e+09\r\nDIALOG_GCD + pool (current)   24,189,512               37,268        9.015e+11\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.\r\n\r\n----\r\n\r\nWhy Track 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 historically locked\r\nthis work behind paid lab pages.\r\n\r\nThis page tracks public-facing progress only. Detail logs, asm-tier\r\nsafety envelopes, & raw run artifacts stay in our lab repo.\r\n\r\n----\r\n\r\nRelated Pages\r\n-------------\r\n\r\n- `foxhop gpu-mesh <https://www.foxhop.net/053ba7da-6277-11f1-82fc-040140774501/gpu-mesh>`__\r\n  \u2014 our 3-GPU pool hardware, bench numbers, & coexistence with our LLM\r\n  services (qwen, Hermes, ollama, speech).\r\n- `lumbda.com/bend <https://lumbda.com/bend.html>`__ \u2014 bend primitive\r\n  catalog; wire protocol; CUDA form list.\r\n\r\n----\r\n\r\n| *Cross-post anchor for lumbda.com/bend & external links.*", "source_format": "rst", "revision_number": 7, "created": 1780923146651}}