Algorithm Agility for Bitcoin to maintain security in the face of quantum and classic breaks in the signature algorithms

Exploring the potential of hash-based schemes as a post-quantum (PQ) solution for Bitcoin, the conversation highlights significant points regarding the implementation and parameters of such cryptographic methods. The focus is primarily on the advantages of limiting the number of signatures to 2^10 and employing a fast route for the initial signature to achieve small signatures. Furthermore, the discussion leans towards the utilization of 128-bit hash functions for chains to meet the 128-bit security requirement, arguing against the necessity of using full 256-bit hashes in Merkle trees due to the specific security needs of signature contexts. Here, target collision resistance is emphasized over collision resistance, which is vulnerable to attacks by the birthday paradox.

The statefulness of blockchain technology is brought into question, especially considering its reliability as a source of state. Given that not all signed transactions may end up recorded on the blockchain, reliance on the blockchain state as a source for verifying the state can lead to issues, particularly because reusing a nonce could result in signature scheme forgery.

Comparing hash-based signature schemes, it's mentioned that the number of supported signatures stands out as a crucial metric directly impacting the efficiency of these schemes. This perspective underlines the importance of not overlooking such factors when evaluating cryptographic solutions.

Additionally, the security of the W-OTS+ scheme is discussed, pointing out that second-preimage resistance alone does not suffice for security. Preimage resistance and undetectability are also necessary, contradicting some details mentioned in the paper. A newer and tighter proof for XMSS is referenced (here), which is an improvement over previous proofs and addresses the issue of additional bits required for security, potentially avoiding the loss previously thought necessary.

Lastly, the original implementation of the SPHINCS scheme utilized HORST, not FORS, with FORS being introduced in the later SPHINCS+ scheme. This correction emphasizes the evolution and refinement of hash-based cryptographic methods over time, suggesting a continuous process of assessment and improvement in the quest for quantum-resistant cryptographic solutions.