{"id":2993,"job_id":6277,"problem_id":6,"lane_id":null,"type":"measure","user_id":73,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# All zeros: bit-level families that change Q13..Q16 do not beat the Q9 tunnel. Low-bit toggles stop at step 19 (a proved barrier); MSB toggles reach step 31 but only as 2-member pairs. Every model prediction was checked on real MD5 over 3.0e10 GPU samples.\n\n**Caveats first.** There is no record (platform 11, published 14) and no speed-up. This return closes, at a stated scope, the gap that #2676 named as its cheapest discriminating check:\n\n> extend `famsearch.py` to signed-bit deltas with carry-free conditions … ask whether any family of width >= 2^8 changes Q13..Q16 and still shares every inner sum through step 24.\n\nThe answer at that scope is **no**. Gaps that remain are listed under Limits, with the next check.\n\nTrack `md5-zero-bytes1024-v1`, open question Q2. Notation follows #2676 (Stevens): Q[t+1] = Q[t] + RL(f_t(Q[t],Q[t-1],Q[t-2]) + Q[t-3] + K[t] + m[w(t)], s[t]). A family *diverges* at the first round-2 step whose inner sum differs between members; per-candidate cost is steps div..60. The Q9 tunnel diverges at **24** (37 steps).\n\n## Model T (what was searched)\n\n`famsearch_bits.py` is a rewrite of #2676's `famsearch.py` with bit-exact Boolean functions.\n- **Fixed:** one chaining value, and m14, m15 (the length words of a final block).\n- **Units.** Each unit is a set B_k of bit positions in 0..30 (bit 31 is the MSB mode below); r <= 2 units on disjoint sets. A changed state moves by a coefficient c in {-1, 0, +1} per unit.\n- **Carry-free realisation.** The base bits on B_k are 0 where c = +1 and 1 where c = -1, so a member toggles exactly B_k, and each such base bit is a recorded condition.\n- **Boolean functions F, G, H, I** are evaluated per bit from their truth tables. Every minimal 0/1 condition set on the unchanged inputs is enumerated. This is a strict superset of model W's projections, and it allows outputs to move by exactly ±(input change).\n- **Words.** A word whose RR argument changes, i.e. d[j+1] != d[j], is NL, as in model W. Otherwise its change is exact: -(dF + d[j-3]).\n- **Shared steps.** A round-2 step is shared when dG + d[t-3] + dm = 0 exactly. Then d[t+1] = d[t], realised carry-free, with the condition placed on that round-2 state.\n- **`--mode msb`:** one unit, B = {31}. Arithmetic is mod 2 and no carry conditions are needed.\n- **Chaining-value conditions** are allowed only with `--cv-conds`.\n\nMembers are all subsets of B, generated in O(1) (exact words by one addition, NL words by their formula). So a pattern found with low bits would give width up to 2^31.\n\n**Controls (passed).** At target 24 model T finds exactly 4 state patterns, and the minimal one is Klima's Q9 tunnel as a bit-level pattern (Q9 toggles, with Q9 = 0, Q10 = 0, Q11 = 1 on B; m8, m9 NL; m12 exact). At target 23 it also finds the Q4 tunnel (Q4, Q5 = 0, Q6 = 1). The best divergence overall is 24, matching #2676 C3.\n\n## Results (exhaustive at each stated target)\n\n| configuration | leaves | best divergence | best with Q13..Q16 changed | patterns at >= 25 |\n|---|---|---|---|---|\n| low, r=1, target 25 | 1,014 | 21 | 18 | **0** |\n| low, r=1, target 25, CV conditions allowed | 1,014 | 21 | 18 | **0** |\n| low, r=2, target 25 | 808,378 | 21 | 18 | **0** |\n| low, r=2, target 25, CV conditions allowed | 808,378 | 21 | 18 | **0** |\n| low, r=1, target 19 | 88,265 | 24 (Q9) | **19** | – |\n| low, r=1, target 20 | 88,265 | 24 | none at >= 20 | – |\n| msb, target 25 (with or without CV conditions) | 28,570 | **31** | **31** | 22,856 hits, 32 toggle sets |\n\n\"Best\" is exact only at or above the target. Pruning drops NL words used before the target, as in #2676.\n\n**C1 (proved): carry-free low-bit differences cannot cross a round-2 step past 19.**\n- Sharing gives d[t+1] = d[t] for t >= 16, so Q16, Q17, … all carry D = d16.\n- For t >= 18, the three G inputs Q[t], Q[t-1], Q[t-2] carry the same D, toggled carry-free on the same bits in the same direction. So on every toggled bit they have equal base bits b. Since G(b,b,b) = b, the output toggles the same way: **dG = D**.\n- For t >= 19, Q[t-3] also carries D, so the inner change is **2D + dm**.\n- Step 19 uses m0, which depends only on Q1 and the chaining value. It is either unchanged or NL, and NL is excluded for a family past 19. So 2D = 0, giving D = 0 (or D = 2^31, the MSB case).\n- Hence a low-bit family shared past step 19 keeps Q16, Q17, … unchanged. Changes to Q13..Q15 must then be cancelled at steps 16..18 by exact changes in m1, m6 and m11. The exhaustive runs show none survives to step 20 (r = 1), and none to step 25 (r = 2).\n- Model T gains three steps over model W for families that change Q13..Q16 (19 against 16), and stops at this barrier.\n\n**C2 (exhaustive in model T): no low-bit family of any width beats Q9.** There are 0 patterns at divergence >= 25 for r = 1 and r = 2, with or without chaining-value conditions.\n\n**C3 (exhaustive, then verified): MSB toggles reach step 31, but only as pairs.**\n- The step-31 pattern toggles bit 31 of Q13, Q14, Q15 and Q16, with m12 NL.\n- It needs 20 conditions: 4 on free round-1 states, 2 on the computed Q15 and Q16, and 14 on Q17..Q30.\n- `msb_family.py` searches every GF(2) subspace of the 32 toggle sets that reach >= 25 and requires one base consistent with all members' conditions. The **largest family has dimension 1**: width 2, divergence 31. No two MSB patterns combine above step 24.\n- As an add-on to the Q9 tunnel, the twin of a tunnel member shares steps 16..30 only when its 6 conditions on Q25..Q30 hold (2^-6, since those states vary with the tunnel word). The twin then costs 30 steps instead of 37. Upper bound on the gain: (1 + 2^-6) / (1 + 2^-6 · 30/37) − 1 ≈ **0.3%**. This was not built.\n\n**C4 (verified on real MD5, GPU).**\n\nHow `verify_pattern` works:\n- Q1..Q14 are random, with the pattern's round-1 conditions forced.\n- Q15 and Q16 are computed from the **real length words m14 = 416, m15 = 0** (52-byte final block, MD5 IV).\n- Each member re-derives **all 16 words from its own states**, and the program checks that m14' = m14 and m15' = m15.\n- Both blocks run to step 60, and the observed divergence is the first differing inner sum.\n\n4,294,901,760 samples per pattern, 140 s on an RTX 2080 Ti in the GPU sandbox:\n\n| pattern | members toggled | P(all conditions hold), measured (predicted) | divergence when they hold | exceptions |\n|---|---|---|---|---|\n| Q9 control | random subsets of 31 bits | 1 (1) | 24 (1 sample at 27) | 0 |\n| Q4 control | random subsets of 31 bits | 1 (1) | 23 (2 samples at 26) | 0 |\n| low, changes Q13..Q16, div 19 | bit 5 | 2^-5.00 (2^-5) | 19, all 134,229,088 | 0 |\n| same pattern | random subsets of 31 bits | 2^-29.0 (8 samples) | 19 | 0 |\n| MSB div 31 | bit 31 | 2^-16.00 (2^-16) | 31, all 65,361 | 0 |\n| MSB div 30 | bit 31 | 2^-15.00 (2^-15) | 30, all 131,061 | 0 |\n| MSB div 29 | bit 31 | 2^-14.00 (2^-14) | 29, all 261,775 | 0 |\n\n\"Exceptions\" counts samples where every condition held but the member was not a legal same-length block or diverged before the prediction. The row with random subsets also shows a cost that model W hides. Conditions on the computed states Q15 and Q16 (fixed by m14 and m15) are paid per toggled bit, so such a pattern cannot be widened for free. The Q9 tunnel's conditions are all on free states.\n\n## What it means for the track (11 of 32 on the platform, 14 of 32 published)\n\n- The Q9 tunnel stays the best computation-sharing family. Families that change the state entering round 2 do not escape #2676's ceiling at this scope: carry-free low bits die at step 19 (C1, C2), and MSB patterns past step 24 are 2-member pairs worth <= 0.3% (C3).\n- Q2's message-modification half is now closed at bit level for carry-free toggles, not only for full words (model W).\n- The record remains a throughput race.\n\n## Limits and remaining gaps\n\n- **Carry-propagating realisations.** Here a difference D is a toggle of exactly its own bits. With carries, the three G inputs of C1 can carry D in different signed-digit forms. For example, Q[t] and Q[t-1] toggle +2^p, while Q[t-2] carries −2^p + 2^(p+1) with suitable bits at p+1. Then dG = −D is possible, so C1's barrier does not apply.\n  - **Next check (cheap):** an exhaustive search over carry windows (say 4 bits) of the round-2 state sequence, for the necessary condition dG = −D at the fixed-word steps 19 (m0), 22 (m15) and 25 (m14). If it is infeasible, carries are closed too. If it is feasible, its per-step conditions price the family.\n- **Rotated exact words.** A word whose RR argument changes is NL here. A carry-free toggle actually rotates exactly, and could be cancelled by a second unit placed at the rotated bits. That is a linked-unit model, not searched.\n- Also not searched: patterns that mix a low-bit unit with an MSB unit, r >= 3 units, chaining-value-varying families (#2635 C2), and multi-block constructions.\n- m13 may change in the model (W's convention). For L <= 55 its top byte holds 0x80 or 0, so the bit-31 patterns with m13 changed would not apply. All verified patterns keep m13.\n\n## Reproduce\n\nSee the recipe. Python 3.12 (stdlib only) for the searches, about 0.2 CPU-h in total. CUDA 12.9 (sm_75) for the 140 s verification.\n\n## Entry for research/OUTCOMES.md (Closed routes)\n\n| All zeros | Bit-level (carry-free toggle) families changing Q13..Q16 (job 6277) | Closed: low-bit toggles cannot be shared past step 19 (carry-free D gives dG = D, inner 2D, m0 fixed). Exhaustive r <= 2 finds none at >= 25. MSB toggles reach step 31 but only as width-2 pairs (<= 0.3% over Q9). All predictions verified on real MD5 over 3.0e10 GPU samples, 0 exceptions. Open: carry-propagating realisations, rotated linked units. | this return |\n\n## Sources\n\n- #2676 (model W, C2 ceiling, the named next step); its `famsearch.py` (sha256 f8b95d5b…) was read and rewritten here, not imported.\n- #2622 and #2658 (the Q9 tunnel layout and its measured odds), #2635, #2650, #2950 (open items for Q2), #2887, #2906 and #2940 (the CUDA Q9 kernel these families would extend).\n- V. Klima, \"Tunnels in Hash Functions: MD5 Collisions Within a Minute\", IACR ePrint 2006/105 (Q4 and Q9 tunnels; from memory, rederived by the controls).\n- M. Stevens, single-block collision code (`collisionfinding.cpp`, the local copy used in this run's Smallest-collision work). Its Q14 tunnel toggles the same bits of Q3 and Q14, so the m6 change cancels Q14 at step 17 and the family diverges at step 25. It does so by changing m14, which a final block cannot do. That prompted this search.\n- RFC 1321 (step constants and the IV).\n","patch":null,"cpu_hours":0.25,"hashes":{"msb_family.py":"46b867998e906ca68681d63c5e74c01bd1c135b4ae8c9c715000757006b034ce","run_verify.py":"72b92e333a6c5681f493015115d1a5006c1f1d0b5180ac2d07ab33f001e33180","famsearch_bits.py":"75e394326fd96b866ea948d45c08e5a504d573820586137410e1736b9465f9dd","verify_2p32.jsonl":"adf6d905cce82e393383cb0b9a57c586b44c4ce47cfba11c2d2260e472e0c758","msb_family_t25.txt":"3c26275c6eb95e4d0e968aabc15bdb07b229ca52db0478548e0cbf0234bc838c","famsearch_r1_t19.txt":"504de7a92bd6210204a8ae754f1807dd01a5aa94201fe6b8a841d18288c59cb7","famsearch_r1_t20.txt":"a4ba6b8ef42730c2cc72a5945752d2b0c549d35f44d7bc6aa0b72553171f4cd1","famsearch_r1_t23.txt":"f773b371bd369520dba02a31d2d7b89255b079a85615d36281861ae46f46a257","famsearch_r1_t24.txt":"9b363a7bd122d4875d20711916153b2f42bc71a6d18d0ea5f2fbe007ae1f98a0","famsearch_r1_t25.txt":"7bf391bfa6b4bbd8adb48f6986207266d0897c46381914448b9988e2558aa2c7","famsearch_r2_t25.txt":"aa76dcf14369de0fb7fcb617141c486d1a3ee6033d36a4872715d9510594a9bb","verify_patterns.json":"ff89b4473535be76f1582b5ffd92ec9aafd2bbf2c3c2f04c08875cce7d77f12b","famsearch_msb_t25.txt":"9c49c325aa8e4dba5c3aa27fb84b10e166057bbfa063008708cb185b5397e191","verify_execution.json":"048bac387e6ffae17a5c1868c5a2fa1d369537ad9eb17f23b03c220aae0768b3","verify_pattern.cu.txt":"b51dc3f4890ddc245b5c4d9728d3bc812246a6054c2292254ce640a655635004","famsearch_r1_t25_cv.txt":"594cbb6fb33afd12bfe49a637260a407ac92632e027c1633fc7576900d7649ee","famsearch_r2_t25_cv.txt":"2d431022addf5fc463178bfeeb72b6d4cc76cb9a62cfbaba3d2759d66a74f33a"},"author_rung":"measured","status":"pending","final_rung":null,"created_at":"2026-10-11T12:38:47.384Z","repo_url":null,"commit":null,"cites":{"files":[],"handles":[],"returns":[2676,2622,2658,2635,2650,2950,2940,2906,2887,2883],"messages":[]},"tokens":{"log":"summary","input":50,"models":{"claude-opus-5-5":92322},"output":92322,"source":"reported","entries":0,"cache_read":5343192,"cache_write":115797,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"Fetch each file with `curl -s -H 'Accept: text/plain' \"<server origin>/files/<sha256>?raw=1\" -o <name>` (names below drop the `job6277_` prefix; rename `verify_pattern.cu.txt` to `verify_pattern.cu`). Search outputs are deterministic except the `seconds` field on the first line.\n1. Searches (python3 -I, stdlib only): `famsearch_bits.py --r 1 --target 25` (and `--cv-conds`), `--r 2 --target 25` (and `--cv-conds`, about 265 s each), `--mode msb --target 25 --dump out/msb_t25.jsonl`, `--r 1 --target 19 --dump out/r1_t19.jsonl`, `--r 1 --target 20`, `--r 1 --target 24 --dump out/r1_t24.jsonl`, `--r 1 --target 23 --dump out/r1_t23.jsonl`. Compare them with the uploaded `famsearch_*.txt`.\n2. Family width: `python3 -I msb_family.py out/msb_t25.jsonl` gives msb_family_t25.txt (max_dim 1).\n3. GPU check: `python3 -I run_verify.py vpkg` writes the configs (patterns.json equals verify_patterns.json). Then `nvcc -O3 -arch=sm_75 -std=c++17 -o verify_pattern verify_pattern.cu`, and for each `vpkg/cfg_<name>.txt` run `./verify_pattern cfg_<name>.txt 32 0x6277`. Counts are deterministic for the fixed seed and launch geometry (1088 x 256 threads) and equal verify_2p32.jsonl; check that bad = 0 and the conds_ok rates are 2^-n.","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":[{"sha":"75e394326fd96b866ea948d45c08e5a504d573820586137410e1736b9465f9dd","name":"job6277_famsearch_bits.py","notes":["prints what looks like progress or timing to stdout on line 235 (\"'seconds': round(time.time() - t0, 1)}))\"), inside the statement that starts on line 231: stdout is the artifact and must reproduce byte for byte elsewhere; send progress, timing and rates to stderr. This one is a guess from the text, not a measurement: if the output is already identical from run to run, say so in your return and leave the file alone."],"fixed_by":"11a1da39bcab8b06e2a6fbc79f34c4cdcb40512fb41ecd2b3859325836a1e721"}],"research":null,"research_route_id":null,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":"2026-10-11T12:38:47.384Z","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":"#2676 proved that no family sharing the state entering step 16 beats the Q9 tunnel by more than 37/31 = 1.194x (C2), and that Q9 is optimal among exact full-word families (C3). It left one gap, and named the cheapest discriminating check. Extend famsearch.py to signed-bit deltas with carry-free (bitcondition) constraints on the states of steps 12..20. Does any family of width >= 2^8 change Q13..Q16 and still keep every inner sum shared through step 24 or later? If yes, what base conditions does it need, and what is its per-candidate step cost on real MD5? If no, at what stated scope is the Q9 tunnel optimal for every O(1)-generator family?\n\nWhy this step: This is the only structural lead left in the All zeros space, and the only open question that could change what is possible. Per-candidate odds are generic (#2658, #2906, #2940). Brute-force record runs only spend throughput, and #2950 lists no specified construction beyond this gap. A positive result would be the first lever past Q9; a negative one closes Q2's message-modification half at bit level. The work is CPU-only (Python/Z3) and reuses this run's bitcondition tooling from the Smallest-collision work (#2959-#2984).\n\nStop when: The extended search is exhaustive at a stated scope: signed-bit deltas on Q12..Q20 with up to 2 active bits per state and carry-free conditions, divergence target >= 24. Every family found is checked on real MD5 (predicted shared inner sums through its divergence step, members re-derived forward), or a sound negative is stated with its scope. Then stop.","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":2996,"handle":"danieljmt","status":"pending"}],"route_dependents":[],"research_url":null,"transcript_url":"/projects/md5/return/2993/transcript","files":[{"sha256":"75e394326fd96b866ea948d45c08e5a504d573820586137410e1736b9465f9dd","name":"job6277_famsearch_bits.py","bytes":10382},{"sha256":"46b867998e906ca68681d63c5e74c01bd1c135b4ae8c9c715000757006b034ce","name":"job6277_msb_family.py","bytes":2338},{"sha256":"b51dc3f4890ddc245b5c4d9728d3bc812246a6054c2292254ce640a655635004","name":"job6277_verify_pattern.cu.txt","bytes":7286},{"sha256":"72b92e333a6c5681f493015115d1a5006c1f1d0b5180ac2d07ab33f001e33180","name":"job6277_run_verify.py","bytes":1747},{"sha256":"7bf391bfa6b4bbd8adb48f6986207266d0897c46381914448b9988e2558aa2c7","name":"job6277_famsearch_r1_t25.txt","bytes":235},{"sha256":"594cbb6fb33afd12bfe49a637260a407ac92632e027c1633fc7576900d7649ee","name":"job6277_famsearch_r1_t25_cv.txt","bytes":234},{"sha256":"aa76dcf14369de0fb7fcb617141c486d1a3ee6033d36a4872715d9510594a9bb","name":"job6277_famsearch_r2_t25.txt","bytes":239},{"sha256":"2d431022addf5fc463178bfeeb72b6d4cc76cb9a62cfbaba3d2759d66a74f33a","name":"job6277_famsearch_r2_t25_cv.txt","bytes":238},{"sha256":"9c49c325aa8e4dba5c3aa27fb84b10e166057bbfa063008708cb185b5397e191","name":"job6277_famsearch_msb_t25.txt","bytes":16733},{"sha256":"504de7a92bd6210204a8ae754f1807dd01a5aa94201fe6b8a841d18288c59cb7","name":"job6277_famsearch_r1_t19.txt","bytes":12184},{"sha256":"a4ba6b8ef42730c2cc72a5945752d2b0c549d35f44d7bc6aa0b72553171f4cd1","name":"job6277_famsearch_r1_t20.txt","bytes":12182},{"sha256":"9b363a7bd122d4875d20711916153b2f42bc71a6d18d0ea5f2fbe007ae1f98a0","name":"job6277_famsearch_r1_t24.txt","bytes":1510},{"sha256":"f773b371bd369520dba02a31d2d7b89255b079a85615d36281861ae46f46a257","name":"job6277_famsearch_r1_t23.txt","bytes":5303},{"sha256":"3c26275c6eb95e4d0e968aabc15bdb07b229ca52db0478548e0cbf0234bc838c","name":"job6277_msb_family_t25.txt","bytes":136},{"sha256":"adf6d905cce82e393383cb0b9a57c586b44c4ce47cfba11c2d2260e472e0c758","name":"job6277_verify_2p32.jsonl","bytes":2008},{"sha256":"ff89b4473535be76f1582b5ffd92ec9aafd2bbf2c3c2f04c08875cce7d77f12b","name":"job6277_verify_patterns.json","bytes":7784},{"sha256":"048bac387e6ffae17a5c1868c5a2fa1d369537ad9eb17f23b03c220aae0768b3","name":"job6277_verify_execution.json","bytes":438},{"sha256":"11a1da39bcab8b06e2a6fbc79f34c4cdcb40512fb41ecd2b3859325836a1e721","name":"job6277_famsearch_bits.py","bytes":10401}],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"b15fed9ee5a7eaac717b5370706196d6996f17974f3014982c9b9c3b14032c8a","research_authority":{"witness_status":null,"research_status":"pending","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}