{"id":2976,"job_id":6233,"problem_id":6,"lane_id":null,"type":"measure","user_id":73,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# Smallest collision: sustained L=63-class Q29 rate from multi-witness seeding is ~67.5/s (~0.34x unconstrained md5sbc), pricing a 126-byte single-block MD5 collision at ~3x Stevens' attack (~2^51.3 compressions)\n\n**Measured** (step following #2974/#2975). No collision; the record stays 248 and the published reference 128.\n\n## Method\n- For 8 model-sat instances, Z3 generated **6 distinct L=63 class + Q23 witnesses** each, blocking repeats of (Q9, Q10, Q11, Q12 >> 20): 48 witnesses, all replay-verified (multi_witness_z3.py, multi_witnesses.json).\n- Each witness seeded a 20 s class-filtered md5sbc burst (#2974's build; bursts.sh), sandboxed.\n- The run hit its 1,500 CPU-s cap during the second round of 24 bursts: per-burst table construction costs CPU but is excluded from md5sbc's own search timer. So **21 bursts on 4 instances** have counters. The planned unseeded baselines did not run; the baseline uses the unconstrained rates measured on this machine in #2959, #2972 and #2974 (158–267 Q29/s, median 197).\n\n## Results (search time only, as md5sbc's Q29/s is)\n| instance | bursts (with reports) | productive bursts | class Q29 | CPU-s | class Q29/s |\n|---|---|---|---|---|---|\n| 0x61630021 | 3 | 3 | 8,812 | 67 | 131.6 |\n| 0x6163002f | 6 | 4 | 16,384 | 167 | 98.1 |\n| 0x61630027 | 6 | 2 | 7,398 | 129 | 57.3 |\n| 0x61630023 | 6 | 0 | 0 | 120 | 0 |\n| **total** | 21 | 9 | **32,594** | **483** | **67.5** |\n\n- **Sustained class Q29 rate: 67.5/s, which is 0.34x the unconstrained median (197/s).**\n- Productivity is lumpy: a Q23 pass expands into thousands of Q29 states, many witnesses yield none within 20 s, and one instance yielded none at all.\n\n## Pricing (estimate, not a measurement of a pair)\n- Downstream odds of class Q29 states equal unconstrained (#2972), so the cost per collision scales with 1/rate: **about 3x Stevens' ~2^49.8, i.e. about 2^51.3 compression-equivalents**, plus negligible per-instance Z3 (seconds) and table-build overhead shared with stock md5sbc.\n- That is still several CPU-years, or a long GPU port; no 126-byte pair is in reach on this machine.\n- The full chain is:\n  - 126 bytes (L=63) is the only sub-128 equal-length target on Stevens' path for md5sbc-style search (#2891, #2975);\n  - it is reachable on about half of instances (#2968);\n  - it streams at 0.34x (this return), with unchanged downstream odds (#2972).\n\n## Limits\n- 4 instances and 21 bursts; the second round was cut by the CPU cap.\n- Table-build CPU is excluded, as in md5sbc's own Q29/s.\n- Full-collision odds are extrapolated (2^-33.85 per Q29 state, #2661/717).\n\n## Next step\n- The cheap investigation of this route is complete.\n- Pricing it directly needs a multi-hour run or a GPU port of md5sbc's search with Z3-selected instances and witness seeding. That is a separate decision for the person, since it is compute-heavy.\n\n## OUTCOMES.md entry (proposed)\n| Track | Method | Budget and hardware | Best reached | What it shows |\n|---|---|---|---|---|\n| Smallest collision | md5sbc seeded at 48 Z3 L=63 witnesses (21 bursts measured) | ~25 CPU-min incl. table builds | 248 (unchanged) | Sustained class Q29 67.5/s = 0.34x unconstrained: 126-byte pair ~3x Stevens (~2^51.3) |","patch":null,"cpu_hours":0.44,"hashes":{"multi_witnesses.json":"a7f864a26e871f2be5df7f28d711938a788dfd96dfdd30d6fa705258212b10a7","sustained_results.json":"c0c9845f8d7777ca7cf2a4ef3512382a42b36ca0514b9e36443d9f97ca2ccdbc"},"author_rung":"measured","status":"pending","final_rung":null,"created_at":"2026-10-11T10:56:38.524Z","repo_url":null,"commit":null,"cites":{"files":[],"handles":[],"returns":[2974,2975,2972,2968,2891,2959,2661],"messages":[]},"tokens":{"log":"summary","input":12,"models":{"claude-opus-5-5":9408},"output":9408,"source":"reported","entries":0,"cache_read":5302333,"cache_write":9065,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"1. `python multi_witness_z3.py tables.json instances.txt 0x61630021,0x61630023,0x61630027,0x6163002f,0x61630030,0x61630031,0x61630034,0x6163003e 6` (about 3 s) writes multi_witnesses.json.\n2. Run `sh bursts.sh` in a directory with #2974's md5sbc_seed: 48 lines of `SQ9.. SQ12.. FILTER63=1 ./md5sbc_seed 20 <seed>`. Allow at least 2,500 CPU-s, because table builds add CPU outside the 20 s search timer.\n3. Read the DONE/Q29REP lines in burst_logs.txt (q29_cls and t). The aggregate is in sustained_results.json.","verification":null,"target":null,"finding":null,"human_md":null,"provisional":false,"effects_applied_at":null,"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":"2026-10-11T10:56:38.524Z","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":"Using #2968's live-coupling model, enumerate several distinct L=63 class+Q23 witnesses per sat instance (blocking previous Q9..Q11 and Q12 high bits) and run witness-seeded class-filtered md5sbc bursts from each; what is the sustained class Q29 rate per CPU-second across instances and witnesses, compared with unconstrained md5sbc?\n\nWhy this step: #2974 measured 40-290 class Q29/s from one witness per instance (lumpy, 2/6 zero); a sustained average over many witnesses gives the single number needed to price a 126-byte pair as a multiple of Stevens' ~2^49.8.\n\nStop when: Aggregate class Q29/s over >= 30 witness bursts on >= 5 instances with a baseline, or 20 CPU-minutes.","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":2978,"handle":"danieljmt","status":"pending"},{"id":2979,"handle":"danieljmt","status":"pending"}],"route_dependents":[],"research_url":null,"transcript_url":"/projects/md5/return/2976/transcript","files":[{"sha256":"b2a27a9274cade62f098a760fa6b9b2132f086a14e17aead47c7f5196abffb83","name":"burst_logs.txt","bytes":4697},{"sha256":"60dd7db3acaef16beda899d8944f0228210bc78a8bf1e3cfb1c5173014be86f5","name":"bursts.sh","bytes":5631},{"sha256":"507988e3de070faa23f7596129459032e93c56154ad3c8045c48169b08f9d379","name":"multi_witness_z3.py","bytes":7717},{"sha256":"a7f864a26e871f2be5df7f28d711938a788dfd96dfdd30d6fa705258212b10a7","name":"multi_witnesses.json","bytes":9122},{"sha256":"c0c9845f8d7777ca7cf2a4ef3512382a42b36ca0514b9e36443d9f97ca2ccdbc","name":"sustained_results.json","bytes":4899}],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"4f4ac26c302ac3d59b7f06a80ef08407c4e980b5dd65a8e510897f1845e97f5f","research_authority":{"witness_status":null,"research_status":"pending","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}