Post Quantum Signatures and Scaling Bitcoin

The email from Brandon Black emphasizes the urgent need for Bitcoin to adopt Post-Quantum (PQ) signatures due to the inherent vulnerabilities of current cryptographic methods against quantum computing attacks. PQ signatures, however, introduce new challenges such as their larger size, which could significantly reduce Bitcoin's transaction volume by increasing the size of transactions and consequently the blocks that contain them. Despite these challenges, a proposed solution involves the use of Non-interactive Transaction Compression (NTC) or Non-Interactive Witness Aggregation (NIWA) for transactions supporting PQ signatures. This approach would allow for the compression of transaction data and aggregation of all PQ signatures in a block into one comprehensive proof, utilizing STARKs (Scalable Transparent ARgument of Knowledge), which are quantum-resistant cryptographic proofs.

This solution could drastically reduce the size of PQ signature transactions to approximately 76 bytes, enhancing Bitcoin's scalability and making payment transactions much cheaper compared to the storage or transfer of non-financial data (like JPEGs) on the blockchain. Moreover, this methodology would address potential scalability issues within the mempool and offer privacy and cost benefits through the ability for transactions to be pre-aggregated and compressed. However, there are concerns regarding the computational costs associated with generating these proofs, which could potentially centralize block production if not managed correctly. The use of specific PQ signature schemes that support non-interactive aggregation and recursive STARKs could mitigate these issues by enabling parallelized or decentralized proof generation.

The email further discusses the broader implications of failing to implement such a system, including the risk of Bitcoin losing its functionality for on-chain payments and becoming more centralized. Nonetheless, the adoption of BIP-360 and other PQ signatures into Bitcoin is advocated as a necessary step towards achieving PQ transaction compression. The email concludes with acknowledgments to various individuals who have contributed feedback or ideas to this proposal, clarifying that their mention does not necessarily imply agreement or endorsement of the presented ideas.

For further exploration of these concepts and technical proposals, references are provided, including links to discussions on Bitcoin Improvement Proposals (BIP), libraries for Bitcoin with post-quantum cryptography, and articles discussing the future of blockchain technology in relation to SNARKs and rollups:

• Bitcoin Improvement Proposals
• Libbitcoinpq Report
• SNARKs and Blockchain Future
• Validity Rollups on Bitcoin
• Rollups Overview by Vitalik Buterin
• LaBRADOR Signature Scheme
• Recursive STARKs
• Interactive Payment Batching