path: root/67/2044ae46a076082179d96f90b29b038763ff2e

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 <bitcoindev+bncBC555A5RRQLRBVGRVXCAMGQEAQ5B36A@googlegroups.com>)
	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 <bitcoindev@gnusha.org>; 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 <dr.orlovsky@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <1161095e-5203-4eec-93b9-2784fdac4bb1n@googlegroups.com>
In-Reply-To: <bee6b897379b9ae0c3d48f53d40a6d70fe7915f0.camel@real-or-random.org>
References: <bee6b897379b9ae0c3d48f53d40a6d70fe7915f0.camel@real-or-random.org>
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: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
 <https://groups.google.com/group/bitcoindev/subscribe>
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:<div>- if a wallet descriptor with pub keys is =
known, the taproot wallet is not quantum secure even in script-spending pat=
hs,</div><div>- quantum-supreme miners or relay nodes may also replace the =
transaction with an alternative transaction.</div><div><br /></div><div>I d=
oubt the term "quantum secure" can be used for describing taproot script-pa=
th spendings.</div><div><br /></div><div>Kind regards,</div><div>Maxim<br /=
><br /></div><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_at=
tr">On Wednesday, July 23, 2025 at 1:17:50=E2=80=AFPM UTC+2 Tim Ruffing wro=
te:<br/></div><blockquote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8e=
x; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">Hello,
<br>
<br>I posted a new research paper to the Cryptology ePrint Archive:
<br>
<br>&quot;The Post-Quantum Security of Bitcoin&#39;s Taproot as a Commitmen=
t Scheme&quot;
<br><a href=3D"https://eprint.iacr.org/2025/1307" target=3D"_blank" rel=3D"=
nofollow" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den&amp;q=
=3Dhttps://eprint.iacr.org/2025/1307&amp;source=3Dgmail&amp;ust=3D175403999=
3483000&amp;usg=3DAOvVaw1BbPa6oPZsqTHphx8p-ltK">https://eprint.iacr.org/202=
5/1307</a>
<br>
<br>
<br>### Can you summarize the results?
<br>
<br>Taproot, when restricted to script-path spends, is post-quantum secure.
<br>
<br>Specifically, an attacker with a quantum computer can&#39;t create a
<br>Taproot output that can be &quot;opened&quot; to an unexpected Merkle r=
oot.
<br>
<br>This holds in the quantum random oracle model (QROM), i.e., SHA256 is
<br>assumed to be a black box that the attacker can query, possibly &quot;i=
n
<br>superposition&quot;. This effectively models that there will be no weak=
ness
<br>in SHA256.
<br>
<br>The paper also shows that a quantum attacker can&#39;t look inside a
<br>Taproot output, i.e., the attacker learns nothing about the Merkle root
<br>(until it is revealed).=20
<br>
<br>### What are the implications for Bitcoin?
<br>
<br>The primary implication of the paper is that it justifies the security
<br>of an upgrade that adds post-quantum signatures to the scripting
<br>language. This has been suggested a few times, for example by Matt
<br>Corallo on this list [1].=C2=A0Specifically, an upgrade path that adds =
post-
<br>quantum signatures to the scripting language in a first softfork, and
<br>later, before a large-scale quantum computer is available, disables
<br>spending via Schnorr and ECDSA signatures in a second softfork, is
<br>safe.=20
<br>
<br>### Wasn&#39;t this known already?
<br>
<br>It appears to be a common assumption on this list that an attacker
<br>can&#39;t break script-path spends. But I&#39;m not aware that a convin=
cing
<br>justification for this assumption has been presented by anyone before.=
=20
<br>
<br>### Can you quantify the results?
<br>
<br>A quantum attacker needs to perform at least 2^81 evaluations of SHA256
<br>to create a Taproot output and be able to open it to an unexpected
<br>Merkle root with probability 1/2. If the attacker has only quantum
<br>machines whose longest sequence of SHA256 computations is limited to
<br>2^20, then the attacker needs at least 2^92 of these machines to get a
<br>success probability of 1/2.
<br>
<br>### Why is this secure enough?
<br>
<br>What follows from the paper is a security level of at least =E2=89=882^=
81. Most
<br>post-quantum cryptography is designed for a quantum security level of
<br>at least 2^128. However, I claim that 2^81 is fine.=C2=A0
<br>
<br>The Bitcoin network performs about 1 ZH/s of double SHA256, this means
<br>that you&#39;d need 1 ZH/s to get 50% of the hash rate. With this hash
<br>rate, you could do about 2^96 SHA256 evaluations per year. So the
<br>security of Bitcoin already relies on the fact that the attacker can&#3=
9;t
<br>get a hash rate of 2^96 SHA256 evaluations per year.=C2=A0
<br>
<br>Now 2^96 is not exactly 2^81 but the difference is not huge. An attack
<br>that performs 2^96 evaluations will need highly specialized classical
<br>hardware and is highly parallel. The first large-scale quantum
<br>computers certainly won&#39;t be able to evaluate SHA256 at the same sp=
eed
<br>as current ASICs. And even if you can get hold of a large scale quantum
<br>computer, it will still be hard to get hold of millions of them. =20
<br>
<br>Moreover, the paper is only concerned with the number of SHA256
<br>evaluations that an attacker needs to perform. If you count actual
<br>computation and storage, then the best known attacks use classical
<br>computers [2]. Unless better quantum algorithms are found, quantum
<br>computing won&#39;t make a difference at all for the security of script=
-
<br>path spends. In other words, before we need to worry about quantum
<br>computers breaking Taproot, we need to worry about classical computers
<br>breaking Taproot.
<br>
<br>[1] <a href=3D"https://groups.google.com/g/bitcoindev/c/8O857bRSVV8/m/4=
cM-7pf4AgAJ" target=3D"_blank" rel=3D"nofollow" data-saferedirecturl=3D"htt=
ps://www.google.com/url?hl=3Den&amp;q=3Dhttps://groups.google.com/g/bitcoin=
dev/c/8O857bRSVV8/m/4cM-7pf4AgAJ&amp;source=3Dgmail&amp;ust=3D1754039993483=
000&amp;usg=3DAOvVaw3YQRb8RpcAo4a3H8JHcG47">https://groups.google.com/g/bit=
coindev/c/8O857bRSVV8/m/4cM-7pf4AgAJ</a>
<br>[2] <a href=3D"https://cr.yp.to/hash/collisioncost-20090823.pdf" target=
=3D"_blank" rel=3D"nofollow" data-saferedirecturl=3D"https://www.google.com=
/url?hl=3Den&amp;q=3Dhttps://cr.yp.to/hash/collisioncost-20090823.pdf&amp;s=
ource=3Dgmail&amp;ust=3D1754039993483000&amp;usg=3DAOvVaw2tk7sc3CBvpgAIuCgu=
gGLQ">https://cr.yp.to/hash/collisioncost-20090823.pdf</a>
<br></blockquote></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/1161095e-5203-4eec-93b9-2784fdac4bb1n%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/1161095e-5203-4eec-93b9-2784fdac4bb1n%40googlegroups.com</a>.<br />

------=_Part_59475_1131781995.1753953758970--

------=_Part_59474_1480715159.1753953758970--