Subject: Re: [bitcoindev] Re: Taproot is post-quantum secure when restricted to script-path spends

From: Ethan Heilman <[email-masked]>
Date: Sun, 3 Aug 2025 13:42:55 -0400

There is a very important security difference between "quantum secure"
outputs/script commitments and signatures.

quantum vulnerable output + quantum vulnerable signature --> Vulnerable to
long-exposure and short-exposure attacks
quantum secure output + quantum vulnerable signature -->  Vulnerable only
to short-exposure attacks
quantum vulnerable  output + quantum secure signature -->  Vulnerable to
both long-exposure and short-exposure attacks
quantum secure output + quantum secure signature --> Fully secure

You really want quantum secure outputs/script commitments as the foundation
for everything else you do.

On Thu, Jul 31, 2025 at 9:00 AM Maxim Orlovsky <[email-masked]>
wrote:

> Well, from my understanding:
> - if a wallet descriptor with pub keys is known, the taproot wallet is not
> quantum secure even in script-spending paths,
> - quantum-supreme miners or relay nodes may also replace the transaction
> with an alternative transaction.
>
> I doubt the term "quantum secure" can be used for describing taproot
> script-path spendings.
>
> Kind regards,
> Maxim
>
> On Wednesday, July 23, 2025 at 1:17:50 PM UTC+2 Tim Ruffing wrote:
>
>> Hello,
>>
>> I posted a new research paper to the Cryptology ePrint Archive:
>>
>> "The Post-Quantum Security of Bitcoin's Taproot as a Commitment Scheme"
>> https://eprint.iacr.org/2025/1307
>>
>>
>> ### Can you summarize the results?
>>
>> Taproot, when restricted to script-path spends, is post-quantum secure.
>>
>> Specifically, an attacker with a quantum computer can't create a
>> Taproot output that can be "opened" to an unexpected Merkle root.
>>
>> This holds in the quantum random oracle model (QROM), i.e., SHA256 is
>> assumed to be a black box that the attacker can query, possibly "in
>> superposition". This effectively models that there will be no weakness
>> in SHA256.
>>
>> The paper also shows that a quantum attacker can't look inside a
>> Taproot output, i.e., the attacker learns nothing about the Merkle root
>> (until it is revealed).
>>
>> ### What are the implications for Bitcoin?
>>
>> The primary implication of the paper is that it justifies the security
>> of an upgrade that adds post-quantum signatures to the scripting
>> language. This has been suggested a few times, for example by Matt
>> Corallo on this list [1]. Specifically, an upgrade path that adds post-
>> quantum signatures to the scripting language in a first softfork, and
>> later, before a large-scale quantum computer is available, disables
>> spending via Schnorr and ECDSA signatures in a second softfork, is
>> safe.
>>
>> ### Wasn't this known already?
>>
>> It appears to be a common assumption on this list that an attacker
>> can't break script-path spends. But I'm not aware that a convincing
>> justification for this assumption has been presented by anyone before.
>>
>> ### Can you quantify the results?
>>
>> A quantum attacker needs to perform at least 2^81 evaluations of SHA256
>> to create a Taproot output and be able to open it to an unexpected
>> Merkle root with probability 1/2. If the attacker has only quantum
>> machines whose longest sequence of SHA256 computations is limited to
>> 2^20, then the attacker needs at least 2^92 of these machines to get a
>> success probability of 1/2.
>>
>> ### Why is this secure enough?
>>
>> What follows from the paper is a security level of at least ≈2^81. Most
>> post-quantum cryptography is designed for a quantum security level of
>> at least 2^128. However, I claim that 2^81 is fine.
>>
>> The Bitcoin network performs about 1 ZH/s of double SHA256, this means
>> that you'd need 1 ZH/s to get 50% of the hash rate. With this hash
>> rate, you could do about 2^96 SHA256 evaluations per year. So the
>> security of Bitcoin already relies on the fact that the attacker can't
>> get a hash rate of 2^96 SHA256 evaluations per year.
>>
>> Now 2^96 is not exactly 2^81 but the difference is not huge. An attack
>> that performs 2^96 evaluations will need highly specialized classical
>> hardware and is highly parallel. The first large-scale quantum
>> computers certainly won't be able to evaluate SHA256 at the same speed
>> as current ASICs. And even if you can get hold of a large scale quantum
>> computer, it will still be hard to get hold of millions of them.
>>
>> Moreover, the paper is only concerned with the number of SHA256
>> evaluations that an attacker needs to perform. If you count actual
>> computation and storage, then the best known attacks use classical
>> computers [2]. Unless better quantum algorithms are found, quantum
>> computing won't make a difference at all for the security of script-
>> path spends. In other words, before we need to worry about quantum
>> computers breaking Taproot, we need to worry about classical computers
>> breaking Taproot.
>>
>> [1] https://groups.google.com/g/bitcoindev/c/8O857bRSVV8/m/4cM-7pf4AgAJ
>> [2] https://cr.yp.to/hash/collisioncost-20090823.pdf
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Bitcoin Development Mailing List" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email-masked].
> To view this discussion visit
> https://groups.google.com/d/msgid/bitcoindev/1161095e-5203-4eec-93b9-2784fdac4bb1n%40googlegroups.com
> <https://groups.google.com/d/msgid/bitcoindev/1161095e-5203-4eec-93b9-2784fdac4bb1n%40googlegroups.com?utm_medium=email&utm_source=footer>
> .
>

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [email-masked].
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BWFF4Fegm2JZPLkbqJD%3DVNqZy4eZr%2BTO5nOXdoDuCZMAw%40mail.gmail.com.