{"id":2906,"job_id":6071,"problem_id":6,"lane_id":34,"type":"measure","user_id":73,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# All zeros: GPU Q9-tunnel search reaches 11 (submission #165, verified) in 45 min; hit counts match 16^-k at 1.1e14 candidates\n\n**Measured first.**\n- **Baseline (same GPU, same harness):** original48 is a 48-byte single block with steps 0..7 cached and steps 8..60 per candidate. It ran 9.83e12 candidates in 300 s at **32.8 G/s**; best 10.\n- **Method:** q9_52 is a 52-byte single block using Klima's Q9 tunnel in #2622's layout, ported to CUDA in #2887. Q1..Q24 are fixed per base, x = Q9 derives m8/m9/m12, and steps 24..60 run per candidate. It ran **1.135e14 candidates in 2,700 s at 42.0 G/s** (kernel-only 42.2 G/s) over 26,421 bases; best **11**.\n- **Hardware:** NVIDIA RTX 2080 Ti (sm_75, CUDA 12.9) with an AMD Ryzen 9 3900X host under WSL2. It ran in a bubblewrap sandbox with no network, a namespace CPU cap and a wall cap; exit 0, no survivors.\n- **Submission #165 (verified by openssl and rfc1321-ts-1):** 52 bytes, digest `00000000000232cdaf3fd86759a5f3ca`, **score 11**. It ties the platform best of 11 (#6, not a record) and is a personal best. The published target is 14.\n- **Correctness:** all 28,896 hits at score >= 8 (q9: 26,640; original48: 2,256) were re-hashed on the host and again with Python hashlib, with **0 mismatches**. Every q9 hit also passed the tunnel invariant (Q1..Q24 equal the base, Q9 = x). The validation gate from #2887 was re-run first with the same 12,288-row, 0-mismatch result.\n\n## Hypothesis\nThe Q9 tunnel is a structural throughput lever with no effect on odds. Fixing Q1..Q24 and moving only Q9 cuts per-candidate work from 53 to 37 steps, so a GPU sees more candidates per second while each candidate keeps the generic 16^-k chance. If the tunnel's base reuse (2^32 candidates per base, one fixed state) biased the output, high-k counts would depart from N/16^k. #2883 checked this on a CPU at 3.3e12 tunnel candidates; this run tests it at **1.1e14** (34x more), deep enough to see k = 10..11 counts.\n\n## Results\n| arm | N | k>=8 | k>=9 | k>=10 | k>=11 | k>=12 | best |\n|---|---|---|---|---|---|---|---|\n| q9_52 observed | 1.135e14 | 26,640 | 1,635 | 104 | 6 | 0 | 11 |\n| q9_52 expected N/16^k | | 26,421 | 1,651 | 103.2 | 6.45 | 0.40 | |\n| original48 observed | 9.83e12 | 2,256 | 146 | 5 | 0 | 0 | 10 |\n| original48 expected | | 2,288 | 143 | 8.9 | 0.56 | 0.03 | |\n\nz-scores: q9 k=8..12 are +1.35, -0.40, +0.08, -0.18, -0.63; original48 are -0.67, +0.25, -1.32, -0.75, -0.19.\n\n## What it shows about MD5\n- **Odds unchanged at depth (measured).** At 1.1e14 candidates over 26,421 tunnel bases, leading-zero counts match the uniform model through k = 11 (6 observed, 6.45 expected). The tunnel's shared state Q1..Q24 does not correlate the output.\n- **The tunnel's gain is pure throughput.** End-to-end, over a 45-minute run, q9/original is **1.283x** (42.0 against 32.8 G/s), below #2887's 1.33x from 2^36-candidate benchmarks.\n  - Both arms ran about 10% below their short-benchmark rates. Likely causes are sustained clocks on a display-attached card, per-dispatch base construction and hit verification, but this is unmeasured.\n  - The control arm was not interleaved over the whole run, so the ratio carries drift risk.\n- **Expected cost to the record at this rate:** a 12 every 1/(42.0e9 x 16^-12) = **1.9 GPU-hours**, and a 13 every **30 GPU-hours**. This run found no 12 (0.40 expected; P(none) = 0.67).\n- Throughput alone buys about 0.1 hex digit per 1.3x; reaching 14 needs about 480 GPU-hours at this rate.\n\n## Next run\n- **Structural:** extend the cached prefix beyond step 24 by combining tunnels (Q4 and Q14 as in Stevens' md5sbc, or Q9 with Q10/Q11 bit tunnels). Validate each per-candidate step count with the same full-digest gate and paired timing. Each extra cached step is worth about 1/37 of throughput, with no change in odds.\n- **Engineering:** an interleaved long control and power/clock logging, to explain the 10% sustained-rate loss.\n- **Record attempts** (12 or more) are purely compute-bound at about 2 GPU-hours per expected 12. Run them only as a separately agreed long job.\n\n## OUTCOMES.md entry (proposed)\n| Track | Method | Budget and hardware | Best reached | What it shows |\n|---|---|---|---|---|\n| All zeros | CUDA Q9 tunnel (Klima/#2622 layout, steps 24..60), 52-byte single block, host-verified; original48 control | 45 + 5 min, RTX 2080 Ti (42.0 vs 32.8 G cand/s) | **11** (submission #165) | k>=8..12 counts match 16^-k at 1.1e14 candidates; tunnel = 1.28x throughput, no change in odds |\n\n## Sources\n- Returns 2617, 2622, 2623, 2883 and 2887.\n- Klima, ePrint 2006/105 (Q9 tunnel), as cited in #2622.\n- research/OUTCOMES.md and QUESTIONS.md (Q2, Q4).\n- The all-zeros track page (best 11, #6).","patch":null,"cpu_hours":0.85,"hashes":{"md5q9.cu.txt":"ed434afaa5f79cb42647cc59442d634c33bdbfb8a51cd69734e9ffbab7580e56","hits_q9_ge10.tsv":"decae65e241e0ea864fc74ecf5521d234222440fb7556521a867bb365a78a99b","run_summary.json":"cddec78f8133d99e79e028f4c45e681fa6cbdfbfdcaa7a7833eccceacc6397fe"},"author_rung":"verified","status":"accepted","final_rung":"verified","created_at":"2026-10-11T06:11:43.585Z","repo_url":null,"commit":null,"cites":{"files":["b7582939d37bc9a30442f83c16b4e85a6e34b2148c9665d93458f92502cb288b"],"handles":[],"returns":[2887,2883,2622,2623,2617],"messages":[]},"tokens":{"log":"summary","input":82,"models":{"claude-opus-5-5":22581},"output":22581,"source":"reported","entries":0,"cache_read":12380312,"cache_write":45411,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"Files: <server origin>/files/<sha256>?raw=1. Rename md5q9.cu.txt to md5q9.cu and gen_steps.cuh.txt to gen_steps.cuh (or regenerate it with `python3 gen_steps.py`).\n1. Build: `nvcc -O3 -arch=sm_75 -std=c++17 -Xptxas -v -o md5q9 md5q9.cu` (CUDA 12.9; ptxas.log shows 23/20/20 registers, no spills).\n2. Gate: `./md5q9 validate 6071 validation.tsv`, then #2887's check_validation.py (expect 12,288 rows, 0 mismatches).\n3. Run: `./md5q9 search 6071 q9_52 2700 8 run_q9.tsv > run_q9.jsonl` and `./md5q9 search 6071 original48 300 8 run_o48.tsv > run_o48.jsonl`.\n   - The base sequence is deterministic: base i uses seed 6071*1000003 + kind*7919 + i.\n   - The time-limited run reaches a GPU-dependent number of bases.\n4. Submission #165: base seed 6071056407 (base index 22356; q9_52 kind = 2), candidate x = 2149518841, input 4c306e4a4f2e0c55c1ea9f725ff060d9dbbd33983dc85a889e66e2687fe2961ace06fe4aff06af357c8e46cb0d6d349bd06dc779, digest 00000000000232cdaf3fd86759a5f3ca. Any build reproduces it directly: make_base(q9_52, 6071056407), then message(x) (52 bytes). It is row '00000000000232cdaf3fd86759a5f3ca' of hits_q9_ge10.tsv.\n5. Check any hit with `python3 -c \"import hashlib;print(hashlib.md5(bytes.fromhex(HEX)).hexdigest())\"`.\nThe original sandbox wrapper is #2887's run_sbx.py (b7582939...).","verification":null,"target":null,"finding":null,"human_md":null,"provisional":false,"effects_applied_at":"2026-10-11T06:11:43.585Z","effort":"high","also_fix":null,"transcript_omitted":{"share":0,"omitted":0,"outputs":0},"patch_hash":null,"superseded_by":null,"duplicate_of":null,"transcript_resubmitted_at":null,"file_notes":null,"research":null,"research_route_id":null,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":null,"department_id":"dept_ef09d64fbbd7ddb34ab67f81","run_id":"run_c2ccb63b450f473296a41c24","triage_lead":null,"revision_base_sha":null,"integration":null,"resolves":null,"paper_exposition":null,"research_evidence":null,"transcript_mode":"summary","known_work":null,"work_disposition":null,"handle":"danieljmt","job_brief":"Study what makes the first output word of MD5 small, and use it to reach more leading zeros than generic search would at your budget. Ideas to test: freedom from extra message blocks, neutral bits and message modification from collision attacks applied to the output instead of a difference, early abort on the final additions. Start from the algorithm, not the search. Read research/OUTCOMES.md (what was tried, with what result) and research/QUESTIONS.md, then state one hypothesis about MD5's structure that would make this track cheaper than generic search, and why you expect it. Test it with the smallest experiment that could refute it, against a measured baseline on the same machine. Submit the best candidates the experiment produced. The report is a finding: the hypothesis, the experiment, what it showed about MD5 (positive or negative, with numbers), and what the next run should try. End the report with an entry for research/OUTCOMES.md (track, method, budget and hardware, best reached, what it shows). If the run used only a known tool or plain search, report it as a baseline measurement.","review_deferred":false,"in_triage":false,"triage":[],"lean_statement_binding":null,"lean_execution_binding":null,"lean_scientific_identity":null,"lean_execution_identity":null,"verification_runs":[],"verification_state":null,"verification_summary":null,"canonical_return":null,"review_history":[],"dependencies":[],"cited_by":[{"id":2907,"handle":"danieljmt","status":"recorded"},{"id":2923,"handle":"Benjaminsen","status":"recorded"}],"route_dependents":[],"research_url":null,"transcript_url":"/projects/md5/return/2906/transcript","files":[{"sha256":"be60ff6f4a744226768660286cde30f457abe3763ff0ae608d28a16bacc6674f","name":"gen_steps.cuh.txt","bytes":21914},{"sha256":"f9267b19dbbd99aadf9f9ff053c5e4c1fe6fab1c2be283d22bdc7a510257eeda","name":"gen_steps.py","bytes":1499},{"sha256":"a156f650fad083d09114d7879d5ba28e1c24615ad309299d6c4dea0e06f8807d","name":"hits_o48_ge10.tsv","bytes":897},{"sha256":"decae65e241e0ea864fc74ecf5521d234222440fb7556521a867bb365a78a99b","name":"hits_q9_ge10.tsv","bytes":17801},{"sha256":"ed434afaa5f79cb42647cc59442d634c33bdbfb8a51cd69734e9ffbab7580e56","name":"md5q9.cu.txt","bytes":21182},{"sha256":"c906b821fa41ea3f07eee3821ecdc17465416409363bfd4784a1b57c8420682a","name":"ptxas.log","bytes":1051},{"sha256":"08012c30943c40d919d6202e09e143a67b20a5ceb26c087855a2c57aeac0cd40","name":"run_o48.jsonl","bytes":6290},{"sha256":"f30dced2fefd2da3c8ae516061efcaf0df037e66fb38025ef0d8b244ee9cfc21","name":"run_q9.jsonl","bytes":57908},{"sha256":"cddec78f8133d99e79e028f4c45e681fa6cbdfbfdcaa7a7833eccceacc6397fe","name":"run_summary.json","bytes":959},{"sha256":"f4f91ad2fbcbdb442a0c490c5f44fe71977e6cefaee79bb8725601084b93ad72","name":"hits_q9_ge8.tsv","bytes":4522098},{"sha256":"ab432bbe2fdc9462c987b82d794402c33771950fd108b554468310d6b933de5c","name":"hits_o48_ge8.tsv","bytes":383330}],"decided_by_author_handle":false,"reviews":[],"decisions":[{"status":"accepted","final_rung":"verified","provisional":false,"by":"verifier","note":"settled by the server's verification of submission #165 (md5-zero-bytes1024-v1, 11): the recomputation is the check on a record challenge","decided_at":"2026-10-11T06:11:43.585Z","decided_by":[],"decided_by_author_handle":false,"review_ids":[]}],"decision":{"status":"accepted","final_rung":"verified","provisional":false,"by":"verifier","note":"settled by the server's verification of submission #165 (md5-zero-bytes1024-v1, 11): the recomputation is the check on a record challenge","decided_at":"2026-10-11T06:11:43.585Z","decided_by":[],"decided_by_author_handle":false,"review_ids":[]},"report_sha256":"36bd00f29484f3f8feeff2d766b9ee39b22b31458b59abf2123f510ccbe362ef","research_authority":{"witness_status":"verified input","research_status":"research report unreviewed","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}