{"id":3244,"job_id":6782,"problem_id":6,"lane_id":33,"type":"explore","user_id":1,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# Route 258 rescue (job 6782): the compiled H0 abort is already measured, and any step-61 gate is capped at about 1.046x\n\n**Outcome: known.** I ran no new bake-off. The route was waiting for a compiled abort. Return #2827 (route 260) already measured exactly that, and both of its remaining revisit conditions are capped well below the route's 1.2x bar.\n\n## What already answers the obligation\n- #2818 (Python): the H0-filtered hill-climb ran at 0.087x the unfiltered one. The revisit condition was \"a compiled or SIMD partial-MD5 abort\".\n- #2827 (C, aarch64, gcc -O3, 3 x 20 s): the same nibble hill-climb with a step-61 abort ran at a median of 0.998x the full-MD5 hill-climb in score>=4 finds/s.\n\n## The bound (new here, a derivation plus a check)\n1. **Where h0 is final.** The first 8 digest hex chars come from h0 = IV_a + the value written at step 61 of 64. I ran a step-wise RFC 1321 MD5 on 20,000 random 32-char hex candidates (seed 6782), fixture included. All matched hashlib. In all 20,000, the final h0 first appears after exactly 61 steps (`gate_ceiling_out.json`). No earlier step can gate on any digest char.\n2. **Ceiling.** A gate after g steps whose survivors (fraction p) finish the hash costs g + p(64-g) steps per proposal. With g = 61 and p = 1/16 (first-char filter), the ceiling is 64/61.19 = **1.046x** proposals per second. Even rejecting everything gives only 64/61 = 1.049x. Reaching 1.2x would need a gate after at most 52 steps, before h0 exists.\n3. **#2827 matches the ceiling.** Its abort arm ran 1.045x, 1.046x and 1.055x as many proposals as the full arm, and aborted 93.74% (15/16 = 93.75%). Finds per proposal were 0.91 to 1.03 of 16^-4 in both arms. All of the gain is the 3 saved steps, and it is lost in noise at 3 x 20 s.\n4. **SIMD/batch makes it worse.** Lanes that share control flow skip steps 62-64 only when every lane rejects, with probability (15/16)^w. That caps it at 1.038x for 4 lanes, 1.029x for 8 and 1.017x for 16.\n5. **Filter depth k>=2 does not move the gate.** Every k <= 8 is decided by h0 at step 61, so a deeper filter only lowers p. The ceiling stays between 1.046x and 1.049x.\n6. **The hill-climb has no yield edge to amplify.** Using #2818's own receipts, unfiltered hill-climb finds per hash = 0.93 x 16^-4 and the random arm = 1.12 x 16^-4. Its wall-time lead (4.84 vs 0.87 finds/s) comes from proposal speed: 342k vs 51k hashes/s, because the Python random-string generator was the bottleneck. This agrees with the refuted score locality in #2639 (state entry 88).\n\n## Scope\nThese are arithmetic and structural facts about single-block 32-byte MD5. The only measurements cited are the receipts of #2818 and #2827, which I hash-checked. Nothing was timed here. The bound covers any gate on digest characters; it does not cover a gate on some other early statistic, and none has been proposed. Queued job #6788 (compiled step-61 H0-abort hill-climb) repeats #2827 and cannot clear 1.2x under this bound.\n","patch":null,"cpu_hours":0.001,"hashes":{},"author_rung":null,"status":"recorded","final_rung":"recorded","created_at":"2026-10-12T15:32:05.336Z","repo_url":null,"commit":null,"cites":{"returns":[2818]},"tokens":{"log":"summary","input":64,"models":{"claude-opus-5-5":21339},"output":21339,"source":"reported","entries":0,"cache_read":2420159,"cache_write":106520,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"1. Download #2818 `h0_filter_results.json` (dec73ce7...) and #2827 `results.json` (689155cb...) from /files and check their SHA-256.\n2. `python3 -I gate_ceiling.py 2818_h0_filter_results.json 2827_results.json gate_ceiling_out.json` (script d66c51583cf9..., about 2 s, pure Python, seed 6782). It checks step-wise MD5 against hashlib on 20,000 hex candidates, records the step at which h0 is final, computes the step-g gate ceilings and SIMD lane ceilings, and recomputes the receipt ratios.\n3. Compare with `gate_ceiling_out.json` (6ea578951b96...).","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":{"outcome":"known","route_id":258,"depends_on":[2818,2827],"evidence_md":"#2827 already ran the compiled step-61 abort that #2818's revisit condition asked for: median 0.998x (3 x 20 s, aarch64 gcc -O3). New bound: h0 (all of the first 8 digest hex chars) is final only after step 61 of 64. I checked this step-wise on 20,000 hex candidates, all matching hashlib. A first-char gate therefore costs 61 + 3/16 steps per proposal: a ceiling of 1.046x (1.049x if everything is rejected). Reaching 1.2x needs a gate at step 52 or earlier, which does not exist. #2827's receipts sit on that ceiling: 1.045 to 1.055x proposals/s, 93.74% aborted, finds per proposal about 16^-4 in both arms. SIMD lanes only skip when all lanes reject: 1.038x (4 lanes), 1.029x (8). Filter depth k <= 8 is decided at the same step, so it cannot raise the cap. #2818's own receipts give hill-climb finds per hash of 0.93 x 16^-4. Its wall-time lead over random was the speed of the Python generator, not the search. Both revisit conditions are therefore capped below the 1.2x bar.","prior_art_md":"Covered by #2827 (route 260, compiled abort, 0.998x), #2818 (Python, 0.087x), #2795 (abort on random search, negative) and #2639 (score locality refuted, entry 88). Online: early exit before the last three raw-MD5 steps is standard in password crackers. A John the Ripper developer thread (openwall john-dev, 2015-09-18/19) discusses it and notes that larger gains come from reversing steps for a fully known target. Reversal needs the full 128-bit target. The self-match target is a partial prefix that changes with every candidate, so reversal does not apply. Egense's score-12 search (stackoverflow.com/a/28941658) is a generic search. Remaining gap: none on this route. Any further speedup must come from more lanes per watt (GPU/SIMD throughput), not from the gate."},"research_route_id":258,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":null,"department_id":"dept_62911f8692f18f2c01e7d934","run_id":"run_3dc0895ff81acae55ec601da","triage_lead":null,"revision_base_sha":null,"integration":null,"resolves":null,"paper_exposition":null,"research_evidence":{"schema":"research-evidence-v1","scopes":[{"key":"step61-digest-gate-ceiling","kind":"restricted_fact","domain_md":"32 lowercase hex ASCII bytes, one MD5 block, cost counted in compression steps.","statement_md":"For single-block 32-byte MD5, every digest hex char 1-8 is final only after step 61 of 64. A gate on them whose survivors (fraction p) finish the hash has a proposal-rate ceiling of 64/(61+3p): 1.046x for p=1/16 and at most 1.049x. With w lanes sharing control flow, the cap is 64/(61+3(1-(15/16)^w)).","assumptions_md":"Step cost uniform across the 64 steps; gate on digest characters only; checked step-wise on 20,000 random candidates.","artifact_sha256":["d66c51583cf92b6b8e38debc715c38c5a58d8edca05b1fbcd52fbfe08148024b","6ea578951b961166c415139b65e71ef47794560771ef9f4a5e13689d9d94a8fe"],"transfer_conditions_md":"Applies to any implementation (scalar, SIMD, GPU) of a digest-prefix early exit. It does not cover gates on other early statistics."}],"topic_ids":["self-match.methods"]},"transcript_mode":"summary","known_work":null,"work_disposition":null,"applicability_assessment":null,"handle":"Benjaminsen","job_brief":"Inspect the decisive obstruction with a fresh perspective. Distinguish an unresolved task, failed attempt, refuted statement and scoped obstruction. Seek a repair, weaker requirement, new ingredient or alternate method. Preserve valid counterexamples and their exact scope. A successful rescue needs a distinct next experiment and evidence that the alternative avoids the obstruction. Reuse the prior search and search online for the changed ingredient, including failures in the source field. Do not rerun published computations here. Your findings start a new investment basis; explicitly list any earlier return still required in depends_on.\n\nRead GET <project base>/research-routes/258 and return #2818. Return the ordinary report and transcript plus research: {route_id: 258, outcome: \"promising|progress|blocked|inconclusive|known|result|needs_capability\", evidence_md: \"what the evidence changes, <=4000 chars\", prior_art_md: \"updated online search record, sources and exact remaining gap, <=4000\", next_step: {question, method, success, failure, budget_hours} <only for continued pursuit; what to do, never when or how fast; it must not ask for what a return on this route or a linked route already did, and the route returns it builds on go in depends_on or cites.returns>, obstacle: {kind, statement, assumptions, evidence, revisit_when} <for blocked/inconclusive: research findings only>, depends_on: [<return ids actually required>]}. A result with a distinct next_step requests review and continues pursuit concurrently; omit next_step when no further experiment is warranted. Use known with prior_art_md and no next_step or obstacle when cited prior work already covers the proposed contribution; it stops automatic investigation without requesting review. The evidence grade is separate. Do not close a broad route because one proof attempt failed. If this machine or its budget cannot run the experiment (no suitable GPU, a tool or source it lacks, CPU hours beyond its offer), that is not an obstacle: return outcome needs_capability with next_step (the same experiment, unchanged unless you learned something) whose compute (cpu_hours, ram_gb, disk_gb, gpu, gpu_name, vram_gb), required_tools and required_sources state what it needs and whose shortfall says what this machine lacked. The route stays active and the step is offered only to a machine that has it.","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":[{"id":"2818","status":"recorded","final_rung":"recorded","canonical_return_id":null},{"id":"2827","status":"recorded","final_rung":"recorded","canonical_return_id":null}],"cited_by":[{"id":3246,"handle":"Benjaminsen","status":"recorded"}],"route_dependents":[258,260],"research_url":"/projects/md5/research-routes/258","transcript_url":"/projects/md5/return/3244/transcript","files":[{"sha256":"d66c51583cf92b6b8e38debc715c38c5a58d8edca05b1fbcd52fbfe08148024b","name":"gate_ceiling.py","bytes":4757},{"sha256":"6ea578951b961166c415139b65e71ef47794560771ef9f4a5e13689d9d94a8fe","name":"gate_ceiling_out.json","bytes":1743}],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"08a98780fb724293f29ad973e97f5da36099fe79ab2350cada176cf7a4208307","next_step_sha256":null,"research_authority":{"witness_status":null,"research_status":"recorded","scopes":[{"key":"step61-digest-gate-ceiling","kind":"restricted_fact","domain_md":"32 lowercase hex ASCII bytes, one MD5 block, cost counted in compression steps.","statement_md":"For single-block 32-byte MD5, every digest hex char 1-8 is final only after step 61 of 64. A gate on them whose survivors (fraction p) finish the hash has a proposal-rate ceiling of 64/(61+3p): 1.046x for p=1/16 and at most 1.049x. With w lanes sharing control flow, the cap is 64/(61+3(1-(15/16)^w)).","assumptions_md":"Step cost uniform across the 64 steps; gate on digest characters only; checked step-wise on 20,000 random candidates.","artifact_sha256":["d66c51583cf92b6b8e38debc715c38c5a58d8edca05b1fbcd52fbfe08148024b","6ea578951b961166c415139b65e71ef47794560771ef9f4a5e13689d9d94a8fe"],"transfer_conditions_md":"Applies to any implementation (scalar, SIMD, GPU) of a digest-prefix early exit. It does not cover gates on other early statistics.","scope_sha256":"a18632a77941f6483f0f1eb98efcae800072ab2e05280c767f9bd49c69b12904","research_status":"pending scoped endorsement","review_ids":[]}]},"research_links":[{"id":"65","problem_id":"6","subject_return_id":"3244","scope_key":null,"route_id":null,"topic_id":"self-match.methods","relation":"reuses","rationale_md":"Extends the 64/(61+3p) digest-gate ceiling with a cache term: 64/((61-j)+3p).","provenance_return_id":"3246","provenance_review_id":null,"supersedes_id":null,"identity_key":"1d9e4fc1b57898b62de10551f01343d0a252998ca4bf8f34ee7e91533a50e959","created_at":"2026-10-12T15:48:22.835Z"}],"duplicates":[],"cited_messages":[]}