1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
|
Delivery-date: Wed, 23 Jul 2025 04:17:58 -0700
Received: from mail-oo1-f56.google.com ([209.85.161.56])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBCMNZ4EPXYNRBW4JQPCAMGQEM7MZX3I@googlegroups.com>)
id 1ueXTx-0000ys-TO
for bitcoindev@gnusha.org; Wed, 23 Jul 2025 04:17:58 -0700
Received: by mail-oo1-f56.google.com with SMTP id 006d021491bc7-615cd8c885fsf2094965eaf.1
for <bitcoindev@gnusha.org>; Wed, 23 Jul 2025 04:17:57 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1753269470; cv=pass;
d=google.com; s=arc-20240605;
b=PYNEHdYe99oRlBUQvwiaFbTJglKThT391B+1w/yJlK3d6er6IfjjcT0EGBhDWuIf8p
IYrP/fBQYGJBFrxfIhxMG8V6Tk5pTy1I3b9sfUijM6keOW6iN4h8MZfqSJIDTgHAKnCa
zQPDAH4oZtBy2mSLpsVh/a4Mv5MrG2gC6L9v6Ew5WFoZxW0HXW+DCWJCSdGuA1nmLtdo
DnmnobJi+yZpN+ba60aFfnzwaO82Om/Mq5ELkVeAapkLOok8Jtpnk3inDMAhOdvhqvlD
OLK94f+amqpKPZhJRhFFL29joUXD4iOSdnxbQTSpO1eQFyIwsgUPw99CycjVUrfoy5x4
isrg==
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:mime-version
:content-transfer-encoding:date:to:from:subject:message-id:sender
:dkim-signature;
bh=s3OjHm26rzkAeV2ubg/4HW3TL06WtMm3CBmW4vW3/24=;
fh=E1hYwwygCfruJDTpsgmq0LLOzcRX6VOYhH8hkxztEwg=;
b=h0tuTk27xbm9SR9B1bXIgnSAB6xgnMP1pgNGDKEfvOyRPlp6zl/ZM6zC01FmSrYqia
j2tJ9UM8T6JnOOtQqvkKenNxHbhq/o/V3ZbDhdwQzdGTBerq0flvQzKQI93X3DM/br08
UBWJbXQDFdBSm+J0aPmnpr/gQGDuzpaRsPxpoE3cIZc1I5DcUBcbzp5uFBrm1KRIPLEq
eXdus5kDuWyY/+OsNAeWkF4nsvXCe7pLA3xcbMpQ1kt3h4nKmCaYyc+UM8wKQpxw+R/T
Esb3J5JICHrdUY6uwHtstrYvZJQM93NuUWbI8M06HhElqOXY2BeJgIDW+GIOrjKtdWrk
DHdw==;
darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
dkim=pass header.i=@real-or-random.org header.s=MBO0001 header.b=xoZl1o3e;
spf=pass (google.com: domain of me@real-or-random.org designates 2001:67c:2050:0:465::102 as permitted sender) smtp.mailfrom=me@real-or-random.org;
dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=real-or-random.org
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1753269470; x=1753874270; 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:mime-version:content-transfer-encoding:date:to
:from:subject:message-id:sender:from:to:cc:subject:date:message-id
:reply-to;
bh=s3OjHm26rzkAeV2ubg/4HW3TL06WtMm3CBmW4vW3/24=;
b=ZgkHg+74hyZbzmF8704KxCNEeZFm+IA1vdaeYuivagMQquUpzwZlxhyPmslCXKteE9
P7dwQt1Jh2Z56k8Zg0aB60GQ8Vb/Eud3/6SLmWxW/WrYS0Y/xmCWxeQBRzdlxSjM+2UU
0g9qGGo6kdep9AUH3CvC4FP1SPrmpMquQ7uGjfG4Arw7WyP4pRCewxncrdfWi4JvvNWA
b7nvQ/PMPR+HufPI7FXtVoK6CjjCvUvUe9ZTV7E0ReznNxHwI7J3hHqn5THRp+y3q9lx
3gm2as1xQD1Z+w29ahD+M0uMc5tmStRzCaiGAH3ddXgIqQH9rJcwIGxxLW3Yp2e5dtj/
WHJA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1753269470; x=1753874270;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-authentication-results
:x-original-sender:mime-version:content-transfer-encoding:date:to
:from:subject:message-id:x-beenthere:x-gm-message-state:sender:from
:to:cc:subject:date:message-id:reply-to;
bh=s3OjHm26rzkAeV2ubg/4HW3TL06WtMm3CBmW4vW3/24=;
b=rqQc5KeCI9rPIkQSLWNXI+aPgObPWHKYBbgDnxfL33wC3ioOUvMZeX7buHzFC2lYUY
2jqSN9TwUnDqwv41ITVefKs+CrjyyryY1X3btXo2NbQ4K3rAaWXKmH63/E431rqdjsAS
S6gVZL6PTvp2a4QJLnWl7pSP3uHFD7YJk9gPT3PJbgXE/1ueDT/td/x64XKSQOHwwuam
u8WHRByaMIwzFcfinhkQBat9L/lL9bRZN2KIThfaeSGIwYOjHfFKedmtbnMEgS9Dpp64
3RFFEPAMhJkY3cr8Jf+8Wt7ImjMG+ZBRSCgSoRCPGMF0qxbRZX4fBHa3cJaMyrTFgY4P
2boA==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCWdNRYc2pWrGsurytqdcFvrQdptXccndNf10iEQOdqjjY5B7N3mdmfV3uNxG1DKwid5jIskwB8qubxJ@gnusha.org
X-Gm-Message-State: AOJu0Yw1TDbBT879R707I4RPSukjq2U/LCSlbD8FAWq4nQmrWYAtjjU3
VlXW1CXnakjb26E6HlcbBBwoX+Tnc17Vc0EW1mWWquhCmZX+bSuqlyMo
X-Google-Smtp-Source: AGHT+IHO13lzAV1isyUoM93HlEkArD+2fY1pXQ5YElcj5E8ttiDEZFYOO4E/DcsSfZXa1JomXmUpxA==
X-Received: by 2002:a05:6820:7512:b0:618:d339:1f0 with SMTP id 006d021491bc7-618d3391091mr948784eaf.4.1753269470449;
Wed, 23 Jul 2025 04:17:50 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZdh5r/VpSFumJ4SRl5sBLrqLUYXg8xAELRQzUwFNxbswQ==
Received: by 2002:a05:6820:438a:b0:611:a15e:a1e5 with SMTP id
006d021491bc7-61774464f4als407070eaf.1.-pod-prod-07-us; Wed, 23 Jul 2025
04:17:47 -0700 (PDT)
X-Received: by 2002:a05:6808:1708:b0:40a:526e:5e7a with SMTP id 5614622812f47-426cd8cfed3mr2028762b6e.23.1753269467353;
Wed, 23 Jul 2025 04:17:47 -0700 (PDT)
Received: by 2002:a05:600c:1c25:b0:456:53b:5b5e with SMTP id 5b1f17b1804b1-4586767246fms5e9;
Wed, 23 Jul 2025 04:03:25 -0700 (PDT)
X-Received: by 2002:a05:600c:c049:b0:440:6a1a:d89f with SMTP id 5b1f17b1804b1-4586954d4dfmr15831875e9.4.1753268603160;
Wed, 23 Jul 2025 04:03:23 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1753268603; cv=none;
d=google.com; s=arc-20240605;
b=dzOEWVaxYcw1cuRLjfmmXfBsW9J475ogwJP33zHCaitdEyDlclrFbaDvtaIg87pW1b
gnfIStvdD0WzNS3qB5PqVoNoe5/wnDL8GF0Urmpxe5Zq08BjJid5wupZWzNSq+i5Q9I/
7RQzU6eOFhbMWK1cYTqgMJ2vxKGnF8a0mFdjJhj5vVGLKCKnkQsXQo3txCdCXScY73Xv
tRaz91E4JERsIKY7gn3nLE+xg3vTu+BjZo5L4Y+PfVVSxcuoCxvMCFmD8WZyDly4ZlSp
TL3ZKhR0ygTFgiEoks05KimRlU08aU3aeeKkHORtiK696UBaOGmdZ+3/NxuJCesMfyHT
FS3A==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
h=mime-version:content-transfer-encoding:date:to:from:subject
:message-id:dkim-signature;
bh=iBibjb4WGWKW90bsO2Eh3D6rXwbkFWSKrQC36yrkGww=;
fh=DMP0F9ULS1guKiqimntQRCN8ZraraesEgQuVcn7F0Z0=;
b=BZUiXvr8PalmB8gN+RbDZ7oqofBvQMJufwLOa/RDE0589NGq637PZwpwx8d7UYqrFd
eStPHqTWxjPdk5p3K+W0IP3EejlbN41wuPXwJ6ap4ngmG5DOs5oK3bk6/hKNC7Fep9nu
TGN+dqgvxfffQ0QvrXjIJHo7z2jAKdsbY7YwW9tJi4lGd17ughUa3uNsB1YD5YVVV+DU
s+uULmmed6RyD5/11HT38y7VVvXLVvX7lWd4b8IuKi+O1PpjzzaWDFUEZYmiHnY4f3oa
znEb9irraRLJsLt0whc2xX1vb6tx9uxo3KQMpqGADyMCNldbaV2kgREIga+wk7+/COB2
s0/A==;
dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
dkim=pass header.i=@real-or-random.org header.s=MBO0001 header.b=xoZl1o3e;
spf=pass (google.com: domain of me@real-or-random.org designates 2001:67c:2050:0:465::102 as permitted sender) smtp.mailfrom=me@real-or-random.org;
dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=real-or-random.org
Received: from mout-p-102.mailbox.org (mout-p-102.mailbox.org. [2001:67c:2050:0:465::102])
by gmr-mx.google.com with ESMTPS id 5b1f17b1804b1-4586917c880si454545e9.1.2025.07.23.04.03.23
for <bitcoindev@googlegroups.com>
(version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
Wed, 23 Jul 2025 04:03:23 -0700 (PDT)
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;
Received: from smtp1.mailbox.org (smtp1.mailbox.org [IPv6:2001:67c:2050:b231:465::1])
(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)
key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256)
(No client certificate requested)
by mout-p-102.mailbox.org (Postfix) with ESMTPS id 4bnB7r50k0z9tk5
for <bitcoindev@googlegroups.com>; Wed, 23 Jul 2025 13:03:20 +0200 (CEST)
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
X-Rspamd-Queue-Id: 4bnB7r50k0z9tk5
X-Original-Sender: me@real-or-random.org
X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass
header.i=@real-or-random.org header.s=MBO0001 header.b=xoZl1o3e;
spf=pass (google.com: domain of me@real-or-random.org designates
2001:67c:2050:0:465::102 as permitted sender) smtp.mailfrom=me@real-or-random.org;
dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=real-or-random.org
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.8 (/)
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.
|
