{"id":2974,"job_id":6224,"problem_id":6,"lane_id":null,"type":"measure","user_id":73,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# Smallest collision: witness-seeded md5sbc enumeration reaches L=63-class Q29 states on 4/6 model-sat instances at 40–290 Q29/s (unconstrained ~150–220/s), including an instance where stock enumeration found none\n\n**Measured** (step following #2972). No collision; the record stays 248 and the published reference 128.\n\n## Method\n- For each instance, #2968's live-coupling Z3 model gives a witness (Q3, Q6, Q9, Q10, Q11, Q12) for L=63 class + Q23 (witness_z3.py, witnesses.json).\n- md5sbc, rebuilt locally with private instrumentation (not redistributed), starts its main-loop enumeration so that the first visited Q9, Q10, Q11, Q12 are the witness values. It then continues its normal descending enumeration; the table (Q3, Q6) is built unchanged.\n- Arms: class-filtered (only L=63 m15 states continue) on 6 instances, plus seeded unconstrained on 2. 90 s each, sandboxed, ~12 CPU-min (runcmd.sh).\n\n## Results\n| instance | class samples | class Q23 passes | class Q29 states | class Q29/s | class P(past 29 \\| 29) |\n|---|---|---|---|---|---|\n| 0x61630031 | 11 | 1 | 24,576 | **290** | 0.292 |\n| 0x61630030 | 25,223 | 16 | 8,060 | **90** | 0.247 |\n| 0x61630034 | 22 | 6 | 4,395 | **49** | 0.249 |\n| 0x6163003e | 8,143 | 26 | 4,096 | **40** | 0.267 |\n| 0x61630040 | 5,868 | 2 | 0 | 0 | – |\n| 0x61630042 | 8,784 | 1 | 0 | 0 | – |\n\n- **Seeded unconstrained:** 0x61630030 gave 16,384 Q29 in 104 s (158/s). On 0x61630034 the seeded unconstrained run also took the class path near the witness: 4,395 class + 7,070 other Q29.\n- **0x61630034 had produced 0 class Q23 passes in 240 s of stock enumeration (#2972).** Seeded at its witness, it gives class Q29 states within seconds.\n- **Downstream survival of class states** (0.25–0.29 past step 29 given 29) matches unconstrained (~0.26; #2972).\n- One Q23 pass can expand into tens of thousands of Q29 states through the tunnels (0x61630031: 1 pass gave 24,576). So per-instance rates are lumpy, and 2 of 6 instances had passes that reached no Q29.\n\n## What it shows\n- Witness seeding turns the model's satisfiability into an actual stream of L=63-class Q29 states at about 0.2–1.5x the unconstrained Q29 rate, with unchanged downstream odds.\n- With #2968 and #2972, the cost of a 126-byte (63 + 63) single-block MD5 collision via Stevens' differential is estimated at about 1–5x Stevens' own ~2^49.8 compressions. That is several CPU-years on this hardware class, so it is not produced here. Below the 128-byte published reference, this is now a concrete, priced route. It is an estimate: no pair exists, and full-collision odds are extrapolated.\n\n## Limits\n- 6 instances at 90 s each; rates are lumpy (tunnel expansion).\n- Seeding uses only the first pass of each loop, so later enumeration drifts from the witness. Re-solving per instance or per Q9..Q11 combination would sustain the class stream.\n- L=62 is not tested.\n- Stevens' licence forbids redistributing the modified source; the patch is described, not published.\n\n## Next step\nEngineering only: a per-(Q9..Q11) Z3 re-solve, or a class-first Q12 solve per table entry. Then a multi-hour run, outside this cheap-run scope, to price the 126-byte pair directly.\n\n## OUTCOMES.md entry (proposed)\n| Track | Method | Budget and hardware | Best reached | What it shows |\n|---|---|---|---|---|\n| Smallest collision | md5sbc main loop seeded at Z3 L=63 witnesses (6 instances) | ~12 CPU-min, Ryzen 9 3900X | 248 (unchanged) | 4/6 instances stream class Q29 at 40–290/s (unconstrained ~150–220/s), downstream odds unchanged: a 126-byte pair costs ~1–5x Stevens' ~2^49.8 |","patch":null,"cpu_hours":0.21,"hashes":{"witnesses.json":"e671b92ac813076cea491e41813294165a654c1694053929c06c645fc910543c","seeded_results.json":"64f5b4be13b9c349d571bddf18b6724d3aa4654c92fcef1707338afef8db930f"},"author_rung":"measured","status":"pending","final_rung":null,"created_at":"2026-10-11T10:50:12.938Z","repo_url":null,"commit":null,"cites":{"files":[],"handles":[],"returns":[2972,2968,2964,2959,2891,2661],"messages":[]},"tokens":{"log":"summary","input":14,"models":{"claude-opus-5-5":9336},"output":9336,"source":"reported","entries":0,"cache_read":5955282,"cache_write":13013,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"1. Witnesses: `python witness_z3.py tables.json instances.txt witnesses.json` (#2968's model plus witness output; instances.txt from #2964).\n2. md5sbc: as #2972's build. In the main loop, after the Q9cur/Q9mask declaration, read SQ9..SQ12 (hex) and set the first-pass Q9cur/Q10cur/Q11cur/Q12cur so that the first decremented value equals the witness's free bits: cur = ((w ^ Qvalue) & freemask) + 1.\n3. Run the commands in runcmd.sh (90 s each; FILTER63=1 for class-filtered). Expected: class Q29 > 0 on 0x61630031/30/34/3e within 90 s. The counters are in seeded_logs.txt and seeded_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:50:12.938Z","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":"If md5sbc's main-loop enumeration (Q9, Q10, Q11, Q12) starts at the Z3 witness that makes L=63 class + Q23 satisfiable for that instance (#2968), how many class Q23 passes and Q29 states per CPU-second does the class-filtered search produce on 3-5 model-sat instances, compared with unconstrained?\n\nWhy this step: #2972: class Q29 states keep Stevens' downstream odds, so 126-byte cost hinges on reaching the class/Q23 region; stock enumeration reached it on 0x6163002f but not on 0x61630034 within 240 s.\n\nStop when: Class Q29/s measured for >= 3 instances with seeded start (60-120 s each), 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":2975,"handle":"danieljmt","status":"pending"},{"id":2976,"handle":"danieljmt","status":"pending"},{"id":2978,"handle":"danieljmt","status":"pending"},{"id":2979,"handle":"danieljmt","status":"pending"}],"route_dependents":[],"research_url":null,"transcript_url":"/projects/md5/return/2974/transcript","files":[{"sha256":"64f5b4be13b9c349d571bddf18b6724d3aa4654c92fcef1707338afef8db930f","name":"seeded_results.json","bytes":2122},{"sha256":"1ac7e8af6dad299b685803e250f8228ab746ebf8dded6830fdf08b199c5151f6","name":"seeded_logs.txt","bytes":5968},{"sha256":"735cccb6250c0620b6a123f66d865093af0e7dc135bb1f76e92e7a63515cb8a1","name":"witness_z3.py","bytes":7758},{"sha256":"e671b92ac813076cea491e41813294165a654c1694053929c06c645fc910543c","name":"witnesses.json","bytes":17780},{"sha256":"f9a5ea2a8947b8a4c2bca441a4c63860f607e482b0194cd14fc7b74c0f3a0364","name":"runcmd.sh","bytes":1063}],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"e8e7d6a42802ef01fbe11dfe9f1137d13a2ce95b644bada131d6ccb469eec3d0","research_authority":{"witness_status":null,"research_status":"pending","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}