Post Quantum Signatures and Scaling Bitcoin with STARKs

Firstly, the unavoidable necessity of transitioning to PQ signatures for Bitcoin in the near future is emphasized due to their larger size compared to current signature schemes. The smallest proposed PQ signature, as outlined in BIP-360, measures 1.5kb for the combination of the public key and signature. This increase in size could potentially lead to a substantial reduction in the transaction volume per block without specific adjustments, posing a threat to Bitcoin's scalability and efficiency.

To address this issue, the concept of Non-interactive Transaction Compression (NTC), or Non-Interactive Witness Aggregation (NIWA), is introduced as a viable solution. NTC involves creating a new transaction type that supports PQ signatures, allowing miners to extract signatures and hash pointers from transactions. These elements are then compressed and aggregated into a single STARK (a form of SNARK which is PQ-resistant), significantly reducing the overall size of PQ signatures and making them more cost-effective than the existing ECDSA and Schnorr signatures.

This compression method proposes a drastic reduction in transaction size, estimating a 1-input-2-output transaction to be around 76 bytes. This efficiency could theoretically increase Bitcoin's transaction throughput to approximately 87 transactions per second based on back-of-the-envelope calculations. Moreover, by adopting an account-based model, further optimization could achieve around 555 transactions per second. This reduction in size not only addresses the scalability concerns but also alters the economic dynamics between on-chain payments and other data storage uses, like JPEGs, making payments much more economically feasible.

However, implementing such a system introduces complexities, particularly regarding the initial large size of PQ transactions before compression, which could strain the mempool. Pre-aggregating transactions could mitigate this, offering both privacy and scalability benefits. Additionally, the process of constructing these proofs must be efficient to avoid centralization pressures on mining, with parallelization and distribution of proof construction being potential solutions.

There's a broader concern that without effective reduction techniques for PQ signatures, the larger sizes would limit Bitcoin's functionality and favor centralized custody solutions, especially in the face of cryptographically relevant quantum computers (CRQC). Thus, the development and adoption of technologies like STARKs for compressing PQ signatures are critical for maintaining Bitcoin's decentralization and self-custody capabilities.

Acknowledgements within the discussion highlight the collaborative nature of this exploration, involving contributions and feedback from multiple experts in the field. This discourse underscores the importance of community engagement and open dialogue in evolving Bitcoin's technology to meet future challenges, as detailed in discussions on the bitcoin-dev mailing list and personal web pages of contributors involved in this ongoing research.