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

The exploration of post-quantum cryptographic solutions for Bitcoin has been a subject of discussion within the community, focusing on enhancing security against quantum computing threats. A significant part of this discourse revolves around hash-based signature schemes, which are considered a promising direction due to their reliance on the well-analyzed security properties of hash functions, such as SHA-256, which Bitcoin already employs. These schemes offer a straightforward approach and have been rigorously analyzed during the NIST post-quantum standardization process, highlighting their potential robustness against quantum attacks.

A detailed analysis available at this technical report delves into various hash-based schemes, emphasizing SPHINCS+ due to its extensive cryptanalysis. The report also outlines several optimization techniques that could significantly reduce the size of signatures, a critical factor given the comparatively large size of standard SPHINCS+ signatures (almost 8KB). By implementing these optimizations and adjusting the bounds on the number of signatures, substantial reductions in signature size can be achieved, making them more practical for integration into Bitcoin's framework. For instance, optimizing for a lower bound of signatures can result in sizes ranging from 3128 bytes to 4036 bytes, depending on the specific bound set, while also maintaining reasonable signing times.

Furthermore, the report suggests that hash-based schemes could achieve smaller public key sizes compared to other options, which is advantageous for keeping both the public key and signature sizes minimal. This aspect is crucial for Bitcoin to ensure that the blockchain does not become excessively burdened with large transaction sizes. Additionally, the security analysis within the report argues that achieving NIST Level 1 (128-bit security) is adequate for protecting against quantum attacks, considering the practical requirements for quantum computational operations.

The conversation also touches upon the operational complexity introduced by stateful schemes, which require updating secret keys for each signature. While these schemes potentially offer improved performance, they pose challenges in key management. An alternative consideration is the integration of hash-based schemes with Hierarchical Deterministic Wallets, although issues arise with efficient public child key derivation.

On another front, the discussion extends to the feasibility of employing N/N Multiparty Computation (MPC) for hash-based signatures in a Bitcoin context. This approach would allow for cosigning by multiple parties, resulting in a single, standard-size signature. Despite the attractiveness of reducing signature sizes by roughly N times versus collecting N independent signatures, the heavy computational overhead of generic MPC protocols remains a concern. A shared reference point is a two-party SHA-256 MPC demo (sha2pc) that showcases the potential of this technology, albeit with limitations that need addressing for broader applicability.

The collective feedback from the community is sought to further refine these proposals, particularly regarding performance requirements across various hardware platforms, the standardization of multiple schemes with distinct signature limits, and the potential benefits of supporting both stateful and stateless schemes. This ongoing dialogue aims to solidify Bitcoin's security posture in anticipation of future quantum computing capabilities, ensuring its resilience and long-term viability.