Algorithm agility to defeat quantum and classical attacks on Bitcoin's signature algorithms

The discussion revolves around enhancing the security of Bitcoin against potential long-term threats, including both quantum and classical breaks in its signature algorithms. The proposal focuses on adding algorithm agility mechanisms to Bitcoin, allowing for an easier migration between different algorithm suites as needed. This concept is supported by RFC 7696: Guidelines for Cryptographic Algorithm Agility, which emphasizes the need for protocols to have the flexibility to shift from one cryptographic algorithm to another to remain secure against advances in computing and cryptographic analysis.

A very secure post-quantum signature algorithm is suggested to be introduced alongside the current algorithms used by Bitcoin. This new algorithm would be designed for emergency use, allowing Bitcoin holders to prepare for any unexpected breaks in signature algorithms without incurring prohibitive transaction fees or block space usage under normal conditions. This approach aims to ensure that Bitcoin can maintain its value and security over extended periods, theoretically enabling someone to securely store their Bitcoin for up to 75 years.

To implement this idea, it is proposed that Bitcoin could support two digital signature algorithms simultaneously, with separate CHECKSIG opcodes for each. This dual-algorithm structure would allow users to switch to a backup signature scheme if the primary one were compromised, without an attacker being able to exploit the broken algorithm due to the inability to access the corresponding public key. It's crucial that these algorithms rely on different cryptographic assumptions to mitigate the risk of both being compromised simultaneously. The secondary algorithm should offer higher security at the expense of efficiency, ensuring a fallback option remains viable even if a replacement for a broken algorithm is found to be weak.

The proposal outlines the use of Schnorr signatures as the current algorithm (DSA1) and introduces SLH-DSA, a hash-based signature algorithm, as the emergency fallback (DSA2). Hash-based signatures are highlighted as potentially secure against both classical and quantum attacks in the long term. To accommodate this setup, BIP 360 is mentioned as a mechanism for integrating SLH-DSA into the Bitcoin protocol, alongside necessary changes to wallet standards and the introduction of new script types to prevent public key reuse and facilitate algorithm migration.

Finally, the text addresses potential concerns and clarifications regarding the proposal, such as the impracticality of using these mechanisms for non-intended purposes like storing non-financial data on the blockchain, and the reasons for preferring SLH-DSA over other hash-based signature schemes. It also touches on the necessity of both consensus-critical and non-consensus critical changes to support the proposed enhancements, including the development of new wallet standards and the integration of a CHECKSIG opcode for SLH-DSA.