From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Thu, 31 Jul 2025 06:00:18 -0700 Received: from mail-oa1-f57.google.com ([209.85.160.57]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uhStN-0007B4-3O for bitcoindev@gnusha.org; Thu, 31 Jul 2025 06:00:18 -0700 Received: by mail-oa1-f57.google.com with SMTP id 586e51a60fabf-2ffa5b5f321sf248852fac.0 for ; Thu, 31 Jul 2025 06:00:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1753966808; x=1754571608; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:sender:from :to:cc:subject:date:message-id:reply-to; bh=S+Jr1Linku+zOarkdgWLHf20AtUKt/j+oZeS5V3KfdE=; b=X6eUIOBM8nK2pA1SbJm8KU5xbiLsg59dC1FFEToGiCOMavpoPEJhUUGuG/y9LOWAvr xV672wqkq3Ag5lvDem5i+l0lt9LcCRotlyJPeTi56bmL9QkosS5t4edNLeBVgKbql/bV G+ux6tHRmQfD4CA5+wxEEr9DPUPjy4gBwiLWHsU1gK8WL1IA5Wd1Uwk7w1wYHKTPkjEF bsVOohbE1/57Dzmbxcui9W2c7c50r5D5e61qXZAkOUPhos6JX1/6BjVMN3/roVcrgFwb yaKSH7bqqsBmk8MaZ7hu29DdCd2DM8f+98nndzp4EscKPLmzIj14q3kuNCWg/Bj2MWoJ J+8w== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1753966808; x=1754571608; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:from:to:cc :subject:date:message-id:reply-to; bh=S+Jr1Linku+zOarkdgWLHf20AtUKt/j+oZeS5V3KfdE=; b=D9m1pMeW+8FgSg4Lr2l3TRyctpL/tu4Ykj8IryjVXSe5xzHERvEEcuSvrmvxidrSUX uU6idhNt6LpQexD8pdw0aFs2k1JjswUGHeS5szv+8h77arX+Ugo/iXWUEowmrahh69Ws XJmCbeiAB4xLN3pZ+b7V8BRoqCteWXDG8MnckRIGEQWj3/k9598XeieeiUZFCb45bQdi uThz52MRABoZIo9QnaqIRlJoyFePgwKoJ34GoifkKxYjcccgB65+soyftRBFS7aPTflz kxYUAufGKxsTZSfwvWkNYVBTpMJgy5J1+4x79RtyVWn5AuWC48P7aDImRBjqo3xwO6Xv Ootw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1753966808; x=1754571608; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=S+Jr1Linku+zOarkdgWLHf20AtUKt/j+oZeS5V3KfdE=; b=fKu7bVCalqBNv35UcIG6iBIiC4bcRiCOpHW3Kd8f5CaUQ1xEhnxKiY7BbVo+IdYTQf y+zeh6nR0BplOzQ0ktcUCca1/MppdnFYzMNxUlsZt01byymUDUgDNoG7qvIGfahlyJOv K0BLs3ZuiwUnWX479Skie0PSEqXUwHtq43O/AszZL3t1yLbbgFHwvD4qcCT4mHsMvNz9 USdah/x55sucDnLy4koeCWTIo3UfHyRCnUZJycL/EWspakIzz+G5OC9dn/Z9S9Or4lKP bFsm2oioyDa/i2K0D2REpU0BrcilojJ7gOVC9wvP1owdLGHGeFd6JJgkVErcmfn4A6BH c3uQ== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCVCTA/ZStJeuJWJpRy2CjaunsounL/MFlW2qWJxN2rogC+2RBITHWGRXCgpSD71MYvNqGWSF5h9YreP@gnusha.org X-Gm-Message-State: AOJu0Ywm13Rp/+GSnPDCOfDePo/2l4BZ0ElD6hawSY7uwMXgDZXLajMF jqMMHpAVbNaU4XN3wiTlFg5qceKeKRz3IzM0tRgchcpna+JvrO/zdppP X-Google-Smtp-Source: AGHT+IH/HwYYi7JzMH9me/pqRjJK+dozSp6w2q+pCr/iVDPzClrzCxAcbAK378uwdo+07rPEaV7yoA== X-Received: by 2002:a05:6870:3123:b0:2e8:797b:bf23 with SMTP id 586e51a60fabf-30785bb6b72mr4385207fac.21.1753966807694; Thu, 31 Jul 2025 06:00:07 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZdpzGYkHzGem3M8DwPuB+5PDiaxVT0l1IWccSJ9Tqyp+g== Received: by 2002:a05:6871:e80e:b0:2ea:701f:7255 with SMTP id 586e51a60fabf-307a73ff90als437448fac.1.-pod-prod-07-us; Thu, 31 Jul 2025 06:00:04 -0700 (PDT) X-Received: by 2002:a05:6808:f04:b0:40c:f220:67fd with SMTP id 5614622812f47-4319a07f28amr4182491b6e.9.1753966804650; Thu, 31 Jul 2025 06:00:04 -0700 (PDT) Received: by 2002:a05:690c:4708:b0:71a:913:f75c with SMTP id 00721157ae682-71a4714c597ms7b3; Thu, 31 Jul 2025 02:22:40 -0700 (PDT) X-Received: by 2002:a05:690c:d8d:b0:715:2081:f2f8 with SMTP id 00721157ae682-71a468f7a9amr79341507b3.27.1753953759556; Thu, 31 Jul 2025 02:22:39 -0700 (PDT) Date: Thu, 31 Jul 2025 02:22:38 -0700 (PDT) From: Maxim Orlovsky To: Bitcoin Development Mailing List Message-Id: <1161095e-5203-4eec-93b9-2784fdac4bb1n@googlegroups.com> In-Reply-To: References: Subject: [bitcoindev] Re: Taproot is post-quantum secure when restricted to script-path spends MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_59474_1480715159.1753953758970" X-Original-Sender: dr.orlovsky@gmail.com Precedence: list Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com List-ID: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , X-Spam-Score: -0.5 (/) ------=_Part_59474_1480715159.1753953758970 Content-Type: multipart/alternative; boundary="----=_Part_59475_1131781995.1753953758970" ------=_Part_59475_1131781995.1753953758970 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Well, from my understanding: - if a wallet descriptor with pub keys is known, the taproot wallet is not= =20 quantum secure even in script-spending paths, - quantum-supreme miners or relay nodes may also replace the transaction=20 with an alternative transaction. I doubt the term "quantum secure" can be used for describing taproot=20 script-path spendings. Kind regards, Maxim On Wednesday, July 23, 2025 at 1:17:50=E2=80=AFPM 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).=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]. 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.=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.=20 > > 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.=20 > > 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/= 1161095e-5203-4eec-93b9-2784fdac4bb1n%40googlegroups.com. ------=_Part_59475_1131781995.1753953758970 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Well, from my understanding:
- if a wallet descriptor with pub keys is = known, the taproot wallet is not quantum secure even in script-spending pat= hs,
- quantum-supreme miners or relay nodes may also replace the = transaction with an alternative transaction.

I d= oubt the term "quantum secure" can be used for describing taproot script-pa= th spendings.

Kind regards,
Maxim

On Wednesday, July 23, 2025 at 1:17:50=E2=80=AFPM UTC+2 Tim Ruffing wro= te:
Hello,

I posted a new research paper to the Cryptology ePrint Archive:

"The Post-Quantum Security of Bitcoin's Taproot as a Commitmen= t Scheme"
https://eprint.iacr.org/202= 5/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 r= oot.

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 "i= n
superposition". This effectively models that there will be no weak= ness
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 convin= cing
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= 9;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 sp= eed
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/bit= coindev/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 &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoind= ev/1161095e-5203-4eec-93b9-2784fdac4bb1n%40googlegroups.com.
------=_Part_59475_1131781995.1753953758970-- ------=_Part_59474_1480715159.1753953758970--