Falcon Post-Quantum Signature Scheme Proposal

The discussion begins with skepticism about prioritizing arithmetic circuit optimization for SNARKs in the post-quantum (PQ) transition within Bitcoin's development, suggesting ZK-STARKs as a more viable option due to their transparent setup and quantum security. The author notes that while ZK-STARKs have a significant communication complexity for small circuits, this complexity scales well (as O(n log n)) for larger computations, making them suitable for applications like zk-rollups or chain validity proofs where large amounts of data or computations are involved.

A key point emphasized is the necessity of aggregating a substantial number of signatures to make the utilization of STARKs for PQ signature aggregation on the Bitcoin blockchain worthwhile in terms of block space savings. The scalability of STARKs benefits the verifier significantly because proof sizes remain under 1MB and verification times are fast, regardless of the computation size. However, this places a heavier burden on the prover, who must commit considerable computational resources to generate these proofs, especially as circuit sizes increase.

The conversation also touches upon the trade-offs between optimizing for arithmetic circuit size and ZK prover efficiency versus classical computational efficiency. An example provided is the Poseidon hash function, which, while being potentially beneficial for ZK proofs, performs an order of magnitude slower than traditional functions like SHA2. This highlights the ongoing challenges and developments in the field, such as Circle STARKs, which aim to improve STARK proving times, indicating active research and interest in enhancing ZK technology applicability to PQ signature schemes.

Further, the author expresses curiosity about comparing the arithmetized circuit sizes of various signing schemes, including SPHINCS, XMSS, Dilithium, and EC Schnorr, inviting contributions from others with data on these comparisons. The inclusion of links to relevant research and discussions (ZK-STARKs introduction, communication complexity graph, ZeroSync, Shielded CSV paper, and Circle STARKs) throughout the email provides valuable resources for further exploration of these topics.