Hash-Based Signatures for Bitcoin's Post-Quantum Future

The ongoing discussion between Mikhail Kudinov and Greg addresses several critical aspects of cryptographic schemes in the context of Bitcoin's development, focusing particularly on post-quantum (PQ) alternatives and their integration with existing protocols. Mikhail emphasizes the importance of considering the size of public keys when comparing PQ alternatives to current schemes, noting that for ML-DSA, a PQ scheme, the public key exceeds 1kB. This point underscores the need to weigh the trade-offs between security enhancements and the increased data requirements of PQ cryptography.

Mikhail also delves into the topic of verification costs, highlighting the significance of comparing the ratio of signature size to verification cost across different cryptographic schemes. He points out that certain parameter sets for ML-DSA exhibit a far more favorable ratio than Schnorr signatures, with some parameters allowing for signatures up to 4480 bytes while maintaining a verification cost ratio nearly nine times better than Schnorr signatures. This discussion raises the question of whether larger signatures might be justified by lower verification costs, suggesting an area where further feedback and research could be beneficial.

On the subject of stateful versus stateless security, Mikhail seeks clarification from Greg regarding the potential for schemes with weakened stateless security to achieve full repeated-use security through statefulness, such as by modifying the message to prevent signature leakage. This inquiry reflects the complexities involved in balancing security, efficiency, and practicality in cryptographic design.

Finally, Mikhail addresses the idea of combining threshold Schnorr signatures with a single PQ scheme. He acknowledges the potential advantages of such an approach but also expresses concerns about the risks of introducing loosely-defined security models, which could inadvertently create vulnerabilities. The possibility of implementing these combined schemes at the scripting layer without additional opcodes is noted, suggesting a pathway for user-assembled constructions that leverage both Schnorr and PQ cryptography within Bitcoin's framework.

Overall, this exchange highlights the nuanced challenges and considerations involved in evolving Bitcoin’s cryptographic foundations to address the threats posed by quantum computing, while also navigating the implications for transaction sizes, verification processes, and security models.