path: root/13/00fbaf770282c1ae51cee4edb9f408348916db

Delivery-date: Sun, 03 Aug 2025 10:47:06 -0700
Received: from mail-ot1-f64.google.com ([209.85.210.64])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBDSJ7DXSQ4PRBDWBX3CAMGQE24GAWTQ@googlegroups.com>)
	id 1uicnZ-00008f-Gz
	for bitcoindev@gnusha.org; Sun, 03 Aug 2025 10:47:06 -0700
Received: by mail-ot1-f64.google.com with SMTP id 46e09a7af769-7419d14da52sf781588a34.2
        for <bitcoindev@gnusha.org>; Sun, 03 Aug 2025 10:47:04 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1754243219; cv=pass;
        d=google.com; s=arc-20240605;
        b=jknzb0RYT6a3qLb9vjjUhukUyZttiA3odRxdXKgKfBn0SO7waXSepl4eEbQc6QtQrv
         NkVMDMgN1XZHAomPCAE880CJkn+eOu7woD+3Ml2bWJaVZd/dvlVexx0GQFtkeb8gt6qs
         FiDbt/S/Yb4GBBAW7DwAm3wRRtRm4nZVFv+NnRiqF4xRYi7uVO3xFvnK5IzER047Wj+I
         8PwkOvgW4GXfTFwad1LpQ3IA0Eu9CAtV5S4JiIxPuhGwg3GZS5OlUQwFfktEalnX5Hts
         Ozqbh9T2Wy9ambJIIuluGLpaVj0WmWXHfWpl6sZufZSRCBnhUlczjV+qVNbJy9YPJyD1
         NG6A==
ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:cc:to:subject:message-id:date:from
         :in-reply-to:references:mime-version:sender:dkim-signature
         :dkim-signature;
        bh=Btdpg/xtNDPdJ82tyyraYOlA1WVPQf7M+AiwNt0u8W4=;
        fh=cnBVg5VGQ1Nq2zvxVLm989g7bELJh57pAeqQQDBPuVA=;
        b=Lxg2eU1vhzEGCcgviKeiGHW0LLX/hpsLBCZInC2+w6bCwfWH5pMQPzeRQ4Jmm/kpuU
         EstEyNcustvgcWGlW19YYbUrnkAvnKQbb5TEhZd4NscWI0b3oihA4TdgGfcoQd8XBfx2
         zmCMr9pfJZBIkHPGUJOtE61XLGZkQwcQjtP72xtaSxqi7jKIIkVH8WSMETASBOqBF4Sc
         mOB4RRHPUfZlPAeynAiJ09CoxegWFk4QmAytH8Vh8Y3wTS/Yynf3kBA3o/tBSyALEnXV
         nhQqNkrl+Ex4IK1EpCShEJRmVWHRLWqveDT9OV4/Hvlcvq4xursIfVmXrzzoNXACxPPf
         vHqw==;
        darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=D2Z+p9SB;
       spf=pass (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::529 as permitted sender) smtp.mailfrom=eth3rs@gmail.com;
       dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;
       dara=pass header.i=@googlegroups.com
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1754243219; x=1754848019; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:cc:to:subject:message-id:date:from:in-reply-to
         :references:mime-version:sender:from:to:cc:subject:date:message-id
         :reply-to;
        bh=Btdpg/xtNDPdJ82tyyraYOlA1WVPQf7M+AiwNt0u8W4=;
        b=Xm6GVaPGDYeXNR8q+t8TV1xk5uiu1jnFErQQRV54rWo43eDfSZ/Usg7zCjR3iZ1XAe
         UhiadZmkB9CBybW5dCM1rtMmY/FEA+CJkGzCyDoP89IqFqO5L4nxmfnuAheYf3W1Bknk
         TcC6OUrfkex+STt1CuHt3h6RQbMZb6EZVgNF/O/t7gh9XKpD4r9eRoHMBqs03TNGbsdC
         ILtEEicfM0j2mqVbkC7v+XjJyb/f+kVzPdDWOWRjbhBQfkzsf27fPSEDXgze0jZZG9XW
         mS68pSeN7IfqirnpxXQI6Nni9jxiFYSU69v9EMk9XIWnG5MNBVyCoWoyb7BQOFVjVyaM
         RsfA==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1754243219; x=1754848019; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:cc:to:subject:message-id:date:from:in-reply-to
         :references:mime-version:from:to:cc:subject:date:message-id:reply-to;
        bh=Btdpg/xtNDPdJ82tyyraYOlA1WVPQf7M+AiwNt0u8W4=;
        b=Q1LHgQ3Zs5MIK+NpE/psSzoeLsS4UUZ3d4rUSiGV+QtJIPabcC6a9BduWweLHIVBbL
         BSQsLP1nkoSPq9g5fKitAXqxQ+k5qhyfA6GuoA7vDISTeddHABYrKynAsUiN5Vdx4FzH
         kQ6+Inm48CKJcxwbTiGuu2tqZTZRqnWhXW7i3byTqPEQvXZaEiZtFmTt5YlpQxgvKi6j
         pEMrlmd3LqKy6EX5bm2r/Gkb3oXi1JyqrO1M9WTmPEHIDjI48G9MdiKc6shctrj3a9Vg
         pic+YKsUFwq1VFRPYnUW5zkh7eW92BGAwW0LqfCnTDGyDKJO8DqivlqsVbymWms6Eqc6
         uDAg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1754243219; x=1754848019;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:cc:to:subject:message-id:date:from:in-reply-to
         :references:mime-version:x-beenthere:x-gm-message-state:sender:from
         :to:cc:subject:date:message-id:reply-to;
        bh=Btdpg/xtNDPdJ82tyyraYOlA1WVPQf7M+AiwNt0u8W4=;
        b=B/1kYkxOAXMpipLO8bo8pmYNLNAENisUghE2pGyNhqNTLMQaxbBt6wcEvfagT7uaVT
         TX9HyrO9Agh8U7CIM2bh3AuCzIVqpM0Ou6kopH1j/LMO1cTfR5UyvBL1t9MW4kxrZdDi
         xWK3YPWR+leLF1bLxOdSlAM5E8kosSkdjApXZeJtPsOwrzjBUX6JmWFhWPFBgjbNGrCF
         AMDsLzyeBIqkTVzuGxs6a7k1VMaw9TF4hBGDS4dBQUB9a2TYYSAVoxEVvpBfhtjHria+
         1YVKmd7Hwb2dsTmrP624SS440FgHuieXJv0X+U7IVdUbGyrfqtUx35+oBrEP+mC0K3/1
         EmUQ==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCWhE33FwtCDlqCt4AJz76jg8opUnpa+xlD6M75hHmk+oyK6FCFV4zvvJ9oVhLd9999Z7gH1foyiyLaJ@gnusha.org
X-Gm-Message-State: AOJu0YxCwPuicpSoX2iqCAXiMXKjnp/hAgema5rskDLEOUkHWoPOR5+h
	buMS6CLey48h+56L9HdnHtazRrR+pyQW6TpoKXzfm4JLw2rEh0Vaoj0c
X-Google-Smtp-Source: AGHT+IFtiTTnCH2bV9PtPlhOewkvUZ1Sgdkc3XyesbPsYg9Wwcx897dnwKkcw4IyFcu1ZlDQSduHWA==
X-Received: by 2002:a05:6871:3232:b0:30b:8730:ba92 with SMTP id 586e51a60fabf-30b8730bc57mr1382664fac.3.1754243218746;
        Sun, 03 Aug 2025 10:46:58 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZfDDjskiKy9pG1S3TngI/snrccMx7+4Y+n5yWDCwjWgbA==
Received: by 2002:a05:6871:a31b:b0:2c2:3dd8:d41e with SMTP id
 586e51a60fabf-307a713a52fls769192fac.0.-pod-prod-04-us; Sun, 03 Aug 2025
 10:46:54 -0700 (PDT)
X-Received: by 2002:a05:6808:124e:b0:433:e660:16b6 with SMTP id 5614622812f47-433f034a6c5mr3539282b6e.30.1754243214217;
        Sun, 03 Aug 2025 10:46:54 -0700 (PDT)
Received: by 2002:a05:600c:3042:b0:456:53b:5b5e with SMTP id 5b1f17b1804b1-458b5f7d6cfms5e9;
        Sun, 3 Aug 2025 10:43:35 -0700 (PDT)
X-Received: by 2002:a05:600c:1d12:b0:459:d667:1842 with SMTP id 5b1f17b1804b1-459d6671b3dmr16280065e9.12.1754243012826;
        Sun, 03 Aug 2025 10:43:32 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1754243012; cv=none;
        d=google.com; s=arc-20240605;
        b=VMPKzllYh3GMbOsN8ZQaquY9dZStUrakgYjZ8DTixgHW7A7hOi9Ool/o8JAyBvPC8G
         iqB5pJakmAX7eQzJdfFJ/YhxrxtkYIw6aDPnrD2b6n386au1dCXanHsSDncb3CrSTDws
         a8Ei1/1h57dwssAE49LhNtbKznB9dHKk4Bd62PYRLBS8sAJuM5TZa4kw3J/Xd9RfOpeX
         RiAFBL8qbvAu06cJo86XIE7VLPeitrmKiVO/yEyz01va25ZU2oBUt0hsFp3KkkLJddM5
         q6Faej6UTetqb3DpOS/PhiMwrsDGrr7a0jUv/JqzgInWM/7ZYg3THGeuDOJ827342wYN
         WCjQ==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
        h=cc:to:subject:message-id:date:from:in-reply-to:references
         :mime-version:dkim-signature;
        bh=LBEOCaK8ew7ZuC+M5ATIRRTus2rwCTfmKdIp4b8am+U=;
        fh=mdo1pC9lp0I9QXOxyNSi+GIY3NZifwW86i2rzi7qT7I=;
        b=UHowjVmaTL/LjYIJ3WuEl3tjo/Uvwcao0Qas/5dn0Fhrbi1kkMbWWS9qORYjgRFYCH
         /hb+OmjjupA1loBn/iyjVs7lnlvyebielFPdAZTPtCZsJQsYVFNDTlbKgDLB8FBqdKEL
         +7VNYzn2JSTuAezTbe+wxXpBTu5pO2gqGPaIlhqNkAI7kYk7OGzCNSIvOODbOoSNuSzc
         Usnz/DQ1ERDDJwJI4vXk4ZJVYTtp0ku+1l9xPwaiDjOLpywwX+utnUPZAfoWbo9vO1d6
         hsJM1YE3lSs5L6IW0ugxuqcsSB1Ak0nqQF6lz3z7JmJQ4pmJtqWCr0yYrTDSLzz8s0Wq
         fK1Q==;
        dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=D2Z+p9SB;
       spf=pass (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::529 as permitted sender) smtp.mailfrom=eth3rs@gmail.com;
       dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;
       dara=pass header.i=@googlegroups.com
Received: from mail-ed1-x529.google.com (mail-ed1-x529.google.com. [2a00:1450:4864:20::529])
        by gmr-mx.google.com with ESMTPS id 5b1f17b1804b1-4589ee09341si2459135e9.2.2025.08.03.10.43.32
        for <bitcoindev@googlegroups.com>
        (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
        Sun, 03 Aug 2025 10:43:32 -0700 (PDT)
Received-SPF: pass (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::529 as permitted sender) client-ip=2a00:1450:4864:20::529;
Received: by mail-ed1-x529.google.com with SMTP id 4fb4d7f45d1cf-60c9d8a169bso4686774a12.1
        for <bitcoindev@googlegroups.com>; Sun, 03 Aug 2025 10:43:32 -0700 (PDT)
X-Gm-Gg: ASbGncvhESDy9gIbz0aHxs5MlUtqPv+jh7tdPpbIpXDZCV3UlzrpSWvNELVfNeRlfhn
	EtW25+7u52zHj98FST1xlkBEx1zsdMlBRXgkPHjetKxhX38mGXhAYaxzTjwQTqyfAaXbm2RG5ra
	SP3n4k7G0nspo3Wl9C0wkziF3VaLbM4PtYeh6sZHrFKyOIb0bTPUfCVfyi8m6NogDAK2ALmQSVj
	E6rJhRKJmt4erAgQSiJJ+a3QWfd9G2yXsho9Hv2Mw==
X-Received: by 2002:a05:6402:3546:b0:615:826:208d with SMTP id
 4fb4d7f45d1cf-615e7173137mr6186845a12.24.1754243011977; Sun, 03 Aug 2025
 10:43:31 -0700 (PDT)
MIME-Version: 1.0
References: <bee6b897379b9ae0c3d48f53d40a6d70fe7915f0.camel@real-or-random.org>
 <1161095e-5203-4eec-93b9-2784fdac4bb1n@googlegroups.com>
In-Reply-To: <1161095e-5203-4eec-93b9-2784fdac4bb1n@googlegroups.com>
From: Ethan Heilman <eth3rs@gmail.com>
Date: Sun, 3 Aug 2025 13:42:55 -0400
X-Gm-Features: Ac12FXywwgHq__Ws-MLpHADmfFPT8rkOW9TCd5rcRIAt_D04LzDKWXE5basvnak
Message-ID: <CAEM=y+WFF4Fegm2JZPLkbqJD=VNqZy4eZr+TO5nOXdoDuCZMAw@mail.gmail.com>
Subject: Re: [bitcoindev] Re: Taproot is post-quantum secure when restricted
 to script-path spends
To: Maxim Orlovsky <dr.orlovsky@gmail.com>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Content-Type: multipart/alternative; boundary="0000000000009423f8063b7987fd"
X-Original-Sender: eth3rs@gmail.com
X-Original-Authentication-Results: gmr-mx.google.com;       dkim=pass
 header.i=@gmail.com header.s=20230601 header.b=D2Z+p9SB;       spf=pass
 (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::529 as
 permitted sender) smtp.mailfrom=eth3rs@gmail.com;       dmarc=pass (p=NONE
 sp=QUARANTINE dis=NONE) header.from=gmail.com;       dara=pass header.i=@googlegroups.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 (/)

--0000000000009423f8063b7987fd
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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=E2=80=AFAM Maxim Orlovsky <dr.orlovsky@gmail.c=
om>
wrote:

> Well, from my understanding:
> - if a wallet descriptor with pub keys is known, the taproot wallet is no=
t
> 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=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).
>>
>> ### 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 =E2=89=882^8=
1. 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-2784=
fdac4bb1n%40googlegroups.com
> <https://groups.google.com/d/msgid/bitcoindev/1161095e-5203-4eec-93b9-278=
4fdac4bb1n%40googlegroups.com?utm_medium=3Demail&utm_source=3Dfooter>
> .
>

--=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/=
CAEM%3Dy%2BWFF4Fegm2JZPLkbqJD%3DVNqZy4eZr%2BTO5nOXdoDuCZMAw%40mail.gmail.co=
m.

--0000000000009423f8063b7987fd
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">There is a very important security difference=C2=A0between=
 &quot;quantum secure&quot; outputs/script commitments and signatures.<br><=
br>quantum vulnerable output=C2=A0+ quantum vulnerable signature --&gt; Vul=
nerable to long-exposure and short-exposure attacks<br>quantum secure outpu=
t=C2=A0+ quantum vulnerable signature --&gt;=C2=A0 Vulnerable only to short=
-exposure attacks<br>quantum vulnerable=C2=A0 output=C2=A0+ quantum secure =
signature --&gt;=C2=A0

Vulnerable to both long-exposure and short-exposure attacks<br>quantum secu=
re output=C2=A0+ quantum secure signature --&gt; Fully secure<br><br>You re=
ally want quantum secure outputs/script commitments as the foundation for e=
verything else you do.</div><br><div class=3D"gmail_quote gmail_quote_conta=
iner"><div dir=3D"ltr" class=3D"gmail_attr">On Thu, Jul 31, 2025 at 9:00=E2=
=80=AFAM Maxim Orlovsky &lt;<a href=3D"mailto:dr.orlovsky@gmail.com">dr.orl=
ovsky@gmail.com</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" s=
tyle=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);pad=
ding-left:1ex">Well, from my understanding:<div>- if a wallet descriptor wi=
th pub keys is known, the taproot wallet is not quantum secure even in scri=
pt-spending paths,</div><div>- quantum-supreme miners or relay nodes may al=
so replace the transaction with an alternative transaction.</div><div><br><=
/div><div>I doubt the term &quot;quantum secure&quot; can be used for descr=
ibing taproot script-path 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_attr">On Wednesday, July 23, 2025 at 1:17:50=E2=80=AFPM UTC+=
2 Tim Ruffing wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"ma=
rgin:0px 0px 0px 0.8ex;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" rel=3D"nofollow" target=
=3D"_blank">https://eprint.iacr.org/2025/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" rel=3D"nofollow" target=3D"_blank">https://groups.google.com/g=
/bitcoindev/c/8O857bRSVV8/m/4cM-7pf4AgAJ</a>
<br>[2] <a href=3D"https://cr.yp.to/hash/collisioncost-20090823.pdf" rel=3D=
"nofollow" target=3D"_blank">https://cr.yp.to/hash/collisioncost-20090823.p=
df</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" target=
=3D"_blank">bitcoindev+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&amp;utm_source=3Dfooter" target=3D"_blank">https://groups.googl=
e.com/d/msgid/bitcoindev/1161095e-5203-4eec-93b9-2784fdac4bb1n%40googlegrou=
ps.com</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/CAEM%3Dy%2BWFF4Fegm2JZPLkbqJD%3DVNqZy4eZr%2BTO5nOXdoDuCZMAw%40ma=
il.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/d/msgid/bitcoindev/CAEM%3Dy%2BWFF4Fegm2JZPLkbqJD%3DVNqZy4eZr%2BTO5nOXdo=
DuCZMAw%40mail.gmail.com</a>.<br />

--0000000000009423f8063b7987fd--