masked-key-rotation
I diagnosed the problem and built a verified, self-contained solution.
masked-key-rotation is a minimum-makespan scheduling problem, not a key-age loop. I found the surrounding context in the Helix repo (pkg/identity/key_rotation.go produces a RotationPlan but never schedules it), then implemented the missing scheduler.
Constraints modeled exactly: per-window capacity, masked/unavailable key versions (on both endpoints), legal holds, deadlines, no downgrade, and no rewrap twice (nonce/key-version reuse).
Greedy packing is not optimal and can falsely report infeasibility: a record may be forced late by a masked destination or an unreleased hold, consuming capacity that a tighter record needs. The key insight: for a fixed horizon, feasibility is a bipartite b-matching → Dinic max-flow, and feasibility is monotone in the horizon → binary search gives the exact minimum makespan. Minimal conflicts come from greedy record deletion (record-minimal IIS).
| File | Purpose |
|---|---|
/workspace/maskedkeyrotation/solver.go |
model, solver, verifier, minimal-conflict extraction |
/workspace/maskedkeyrotation/dinic.go |
Dinic max-flow |
/workspace/maskedkeyrotation/cmd/solve/main.go |
JSON CLI (exit 0 schedule / 3 conflict / 2 bad input) |
/workspace/maskedkeyrotation/solver_test.go |
unit + property tests |
/workspace/SOLUTION.md |
full self-contained report with all code inlined |
go test ./... → okgo test -cover ./... → 90.5% coveragego test -race ./... → cleanTestSolve_MatchesBruteForce cross-checks 3000 random instances against exhaustive search: identical feasibility, identical optimal makespan, every schedule re-verified, and every conflict proven minimal.Verify independently re-checks all six constraint classes and the CLI refuses to emit an invalid schedule.The full write-up (title, root-cause analysis, exact fix code/commands, verification section) is at /workspace/SOLUTION.md.
# Evidence - Problem class: masked-key-rotation - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-10-06T16:36:45.758Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Given a fleet of encrypted records whose keys rotate asynchronously, determine the smallest safe migration schedule when only a bounded number of records can be rewrapped per time window and some key versions may be temporarily unavailable. The solver must honor per-record legal-hold constraints, prevent downgrade or nonce-reuse hazards, and emit a verifiable schedule or a minimal conflict explanation.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "masked-key-rotation", "provider": "openrouter", "solved_at": "2026-10-06T16:36:45.758Z", "version": "1.26"}