Taproot is post-quantum secure when restricted to script-path spends

The study asserts that an attacker equipped with quantum computing capabilities cannot generate a Taproot output that could be opened to reveal an unexpected Merkle root. This conclusion is based on the quantum random oracle model (QROM), which operates under the assumption that SHA256 can be treated as a secure black box against quantum attacks, thereby presuming no inherent vulnerabilities within SHA256 itself.

The implications for Bitcoin are profound, especially in relation to enhancing its scripting language with post-quantum signatures. The research supports the notion of a two-phase softfork upgrade path suggested by Matt Corallo and others. Initially, this path would integrate post-quantum signatures into Bitcoin's scripting language. Subsequently, before the advent of large-scale quantum computing, a second softfork would disable the use of Schnorr and ECDSA signatures for transactions. This approach is deemed safe and justifiable by the paper's findings, countering the previously unproven assumption that script-path spends were inherently secure against quantum attacks.

Quantitatively, the paper details that a quantum attacker would need to perform a minimum of 2^81 evaluations of SHA256 to successfully create and open a Taproot output to an unexpected Merkle root with a 50% probability. For attackers limited to quantum machines capable of executing a sequence of SHA256 computations up to 2^20 times, acquiring at least 2^92 such machines would be necessary to achieve the same probability of success. This establishes a security threshold that, while below the often-targeted 2^128 level for post-quantum cryptography, is considered adequate given the current computational capabilities of the Bitcoin network. Specifically, considering the network's hash rate and the practical challenges of achieving a significantly higher rate of SHA256 evaluations with quantum computing, the paper argues that the security level of ≈2^81 is satisfactory.

Furthermore, the study emphasizes that the foremost concern should not be quantum computing's potential impact but rather the capacity of classical computers to compromise Taproot's security. It concludes that unless more efficient quantum algorithms are developed, quantum computing does not pose a significant threat to the security of script-path spends within Bitcoin's framework. This perspective shifts the focus towards maintaining vigilance against advancements in classical computing techniques that could threaten Taproot's integrity before quantum computing becomes a relevant concern.