Host function for Falcon (FN-DSA) & LaBRADOR support

[gnosed]

Abstract

Falcon (Fast Fourier lattice-based compact signatures over NTRU) is a lattice-based signature scheme selected by NIST as a standardized post-quantum (PQ) signature scheme. It offers the most compact PQ signatures currently available, with signature sizes of ~666 bytes and public key sizes of ~897 bytes for Falcon-512, meeting NIST Level I security requirements.

While large-scale post-quantum threats may not be imminent, regulatory pressure makes it increasingly important for TradFi actors settling real-world assets (RWAs) on-chain to prepare for the transition and demonstrate PQ readiness.

This discussion outlines a clear path toward adding Falcon as a host function, making it compatible with Soroban Smart Accounts at the application layer, as well as enabling protocol-level integration by extending its functionality with a signature aggregation scheme based on the LaBRADOR proof system. According to the C LaBRADOR implementation and this EthResearch post, this approach enables compact proofs of approximately ~74 kB for aggregating 10,000 Falcon-512 signatures. However, it incurs a proving time of ~6 s and a relatively slow verification time of 2.7 s. In contrast, hash-based signature aggregation can offer faster verification (~108 ms) at the cost of a larger proof sizes (~128–1.7 MB depending on the optimization level of the STARK; custom circuit vs VM).

[jayz22]

Thanks @gnosed for the proposal, PQ is an important subject and Falcon seems like an important signature scheme (although I'm no expert).

However, it feels a bit premature to discuss host function support. The PQ based smart accounts sounds like an interesting use case but it's unclear about its benefits or feasibility. The cited data mentions aggregating 10000s of signatures, I'm not sure how relevant this scale is for a smart account (as opposed to signature aggregation in a PoS network).
The verification time (2.7s in the compact proof case) is also too large for consideration. The current Soroban instruction limit (100M, to be increased to 400M soon) can tolerant on the order of ~100ms execution time (based on the model assumption), so any single host function needs to stay way under that.

The C library relies on AVX512 instruction set (which is not available everywhere) and it's unclear about how battle tested it is for production use.

It may be worth of a longer term consideration, but as you see the work supporting it is wouldn't be trivial. Would like to see a bit more clear demonstration of the use case and concrete results before we should consider adding it into Soroban host.