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

In the realm of cryptocurrency, particularly within Bitcoin's architecture, the debate around signature and public key sizes is pivotal. The evaluation metric often revolves around the combined size of the signature, public key, and a hash, or simply the signature plus public key if it remains under 500 bits. This discussion is crucial because, despite lower concerns about validation costs for hash-based signatures due to their minimal size difference, when the size expands significantly—up to 40 times larger in some cases—the validation costs become a notable concern. This issue is magnified without an accompanying increase in block capacity, raising questions about the utility of large signatures.

The conversation extends into the design decisions for Bitcoin, exploring the balance between relying on stateless security versus introducing statefulness to enhance security measures. Statefulness, while offering potential improvements to security, presents challenges with Bitcoin's private keys, especially concerning cold storage and the risk of key loss. The best practice of making duplicate copies for key storage contrasts with the ideal of single or near-single use of keys, highlighting a significant security consideration.

Moreover, the discussion delves into advanced cryptographic solutions like multi-signatures, distributed signatures, and threshold signatures. There's a specific interest in combining threshold Schnorr signatures with post-quantum (PQ) schemes to create a hybrid security model. This model would require either a consensus among participants or a successful attack on the Schnorr signature for a breach, potentially offering a balanced approach considering the costs and security needs of multiple PQ keys.

When it comes to implementation across various hardware, the performance requirements, especially in low-power devices, are regarded as less critical compared to the minimum dynamic RAM needed even at lower performance levels. The debate also touches upon the standardization of multiple schemes based on their signature limits and the associated relative costs. While the flexibility of configurations may pose privacy and practicality issues, having two standardized options that cater to different security needs and support optional statefulness could provide a middle ground. This approach allows users to choose between security levels at the moment of signing, possibly with an added nominal byte cost, offering adaptiveness in securing transactions against potential compromises.