The leverage plan

A scan tells you what’s wrong with each server, one at a time. But many names share one TLS terminator — a load balancer, an appliance, a hosting front end — one provider runs many terminators, and the head of a popularity list carries most of the traffic. So the useful question for a list is a different one: with a given amount of effort, which fixes make the most traffic post-quantum?

pqdoctor scan top.csv --fingerprint --out results.jsonl
pqdoctor plan results.jsonl --ranks top.csv --budget 50

PQ leverage plan — traffic-weighted (Zipf s = 1 over list rank)

  post-quantum today       61.3%
  after this plan          69.0% (expected)   cost 50
  certificate              the best possible plan at this cost reaches at most 69.0%; this one gets ≥ 99.9% of that gain

The model

• Sites are weighted by Zipf over their rank (1/rank, --zipf for another exponent) with --ranks — a rank,domain list such as Tranco. Without it, every site counts the same.
• Actions: one per TLS terminator (same IP and the same handshake shape), of the kind its class needs — a config change, a provider setting, a sidecar, turning on TLS 1.3, investigating, a middlebox fix, moving behind a PQ edge — plus one “ask the provider” action that covers every site a provider without a PQ setting terminates.
• Each action has an effort cost and odds of working, scaled down for low-confidence fingerprints. The defaults (a config change is 1 at 90%, a sidecar 3 at 85%, asking a provider 5 at 30%, …) are judgement calls; --costs and --odds change them (--costs sidecar=4,config-change=0.5).

The plan maximises the expected traffic made post-quantum:

f(S) = Σ_h w_h · (1 − Π_{a ∈ S, h ∈ a} (1 − p_a))

That’s a monotone submodular function — each extra action adds less than it would alone — so choosing actions under a budget is budgeted maximum coverage.

The algorithm, and the proof

• Lazy greedy (CELF): pick the action with the best expected gain per unit of effort; because gains only shrink, a stale gain is an upper bound, so only the top of the queue is ever re-evaluated. Compared with the best single affordable action, this is guaranteed to reach at least (1 − 1/e)/2 of the optimum.
• A certificate. For any set of actions S, submodularity gives f(OPT) ≤ f(S) + Σ_{a ∈ OPT} δ_a(S), and the sum is at most a fractional knapsack over the marginal gains. pqdoctor evaluates that bound along the greedy path and keeps the tightest, so every plan prints how far from the best possible plan it can be. On the Tranco top-10k study (2026-10-24) the plan reaches at least 99.6% of the best possible gain at every budget from 10 to 250.
• Sensitivity. Re-planned under 20 random cost models (every cost and every odd × 0.5–1.5), the top 25 actions kept a median of 21 (worst 16): the head of the list comes from where the traffic is and how many sites share a fix, not from the exact numbers.

--json gives every step; --top N how many to print.