From: Maxim Orlovsky <dr.orlovsky@gmail•com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: [bitcoindev] Re: Taproot is post-quantum secure when restricted to script-path spends
Date: Thu, 31 Jul 2025 02:22:38 -0700 (PDT) [thread overview]
Message-ID: <1161095e-5203-4eec-93b9-2784fdac4bb1n@googlegroups.com> (raw)
In-Reply-To: <bee6b897379b9ae0c3d48f53d40a6d70fe7915f0.camel@real-or-random.org>
[-- Attachment #1.1: Type: text/plain, Size: 4642 bytes --]
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 bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/1161095e-5203-4eec-93b9-2784fdac4bb1n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 6298 bytes --]
prev parent reply other threads:[~2025-07-31 13:00 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-07-23 11:03 [bitcoindev] " Tim Ruffing
2025-07-31 9:22 ` Maxim Orlovsky [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1161095e-5203-4eec-93b9-2784fdac4bb1n@googlegroups.com \
--to=dr.orlovsky@gmail$(echo .)com \
--cc=bitcoindev@googlegroups.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox