Delivery-date: Wed, 23 Jul 2025 04:17:58 -0700
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of me@real-or-random.org designates 2001:67c:2050:0:465::102 as permitted sender) client-ip=2001:67c:2050:0:465::102;
Message-ID: <bee6b897379b9ae0c3d48f53d40a6d70fe7915f0.camel@real-or-random.org>
Subject: [bitcoindev] Taproot is post-quantum secure when restricted to
 script-path spends
From: Tim Ruffing <me@real-or-random.org>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Date: Wed, 23 Jul 2025 13:03:19 +0200
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

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).=20

### 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].=C2=A0Specifically, 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.=20

### 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.=20

### 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 =E2=89=882^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.=C2=A0

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.=C2=A0

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. =20

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

--=20
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 e=
mail to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/=
bee6b897379b9ae0c3d48f53d40a6d70fe7915f0.camel%40real-or-random.org.