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
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
|
Delivery-date: Sun, 16 Mar 2025 11:31:41 -0700
Received: from mail-oo1-f63.google.com ([209.85.161.63])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBDZPZFXW2IMRBA5S3S7AMGQEA77CZBY@googlegroups.com>)
id 1ttslw-0003xm-3v
for bitcoindev@gnusha.org; Sun, 16 Mar 2025 11:31:41 -0700
Received: by mail-oo1-f63.google.com with SMTP id 006d021491bc7-5fe9286b93fsf1012053eaf.3
for <bitcoindev@gnusha.org>; Sun, 16 Mar 2025 11:31:40 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1742149894; cv=pass;
d=google.com; s=arc-20240605;
b=Uv06x0EC7YRYpLKcmHrG503ntR1gr5ayHwcdExhBml46Ma3Pe43HoZGarBNULH5vMf
l59YLnaFU5rL/wKtc7YQRxwRuVb7nq5JbSX8QTMRGVeLMX6LSsemsZqm/hk0FWjQBIYI
mbh3E/vGehBSfdz9O1lgPNfXh04qQzB78s3CTltUg2cYILIyWpdrI8XUMj5dfEuMOFT3
YT54tFpTVqBY3q39Q8j/SX+jIhozxnhO16wpvSFJ+rP5+Ja5zCIOuYFNUBsAs0A0AF7J
2DzpLL6AQaKohQRCduNukabt1K/lfP8/WHRSDbm0rnfG+YHMT/BOzrBjAlsg/ZzAv5fz
L95Q==
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:to:subject:message-id:date:from
:mime-version:sender:dkim-signature:dkim-signature;
bh=2Rky/zre2CgOmki3Royz+bT0OwzDkWU56RD4GhwDois=;
fh=LCms8p0NppexC291oUGBmTuzkSwUW9FiR/xi2yLs4LE=;
b=b+uE5/wWhNw0dYH9LHWcWoKya2IXKnAH3r0Cqfry+N9oXrcQ+X5qFyjZN22oDjrZc8
IVImN3UHOjfJ60ECU9s8o1ge7OR60UjsC0F7aeuzu+7tDBrcV1oijY4jO6nPTTFmm7y4
y0l2AS1vd4KuOYnyrcpm0KCrdXUDpAnTob4g+XgcGqZEEpKP/6RCusQiAOvFvCZlMsLQ
Cx4ispipdlUDuQAXHO3DZUjQ66mmv1qH+9P8y3to23rpANezEZD3G3FoTMOHeOcPqQ7C
TJA0ObJ7T7CsUqQYxWniL3HKV+gSZss8bV9Uwe5qm0096+BvUL85pP3DbNv1ssI3xNuM
IF9w==;
darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
dkim=pass header.i=@gmail.com header.s=20230601 header.b=QhmbMRQN;
spf=pass (google.com: domain of martin.habovstiak@gmail.com designates 2607:f8b0:4864:20::92e as permitted sender) smtp.mailfrom=martin.habovstiak@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=1742149894; x=1742754694; 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:to:subject:message-id:date:from:mime-version
:sender:from:to:cc:subject:date:message-id:reply-to;
bh=2Rky/zre2CgOmki3Royz+bT0OwzDkWU56RD4GhwDois=;
b=LcxYwWtFQJsou9uVVTH2SzeZpxp8ej+nsiXxYCPJbgxdQESkTg54x7f8gsvfEmirCJ
2cg7Yn5jNysy9exC2FX1g5xzSC7E/k05c+F36Aq018elHn9qe1Dc8PWcKle1GzyhCh6j
QUGiQgQTUxttivkQoRi1/morHQxqOznGfRv0vckJ2AvvsgqP0RArsiN5l0rGQF968thH
KjKR+UvgNfyWACF0b1GDSXARAmUDSe8uSIWOtYuI/my9xWdcqoGGebff9k00gw3KpmKN
sXlpP8acizDt4iBFmKFPueiyt8YOq2X9qUOoB8p4Sk98nU5WWoZVsUH18+gDlS5jBcW+
+7bg==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=gmail.com; s=20230601; t=1742149894; x=1742754694; 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:to:subject:message-id:date:from:mime-version:from
:to:cc:subject:date:message-id:reply-to;
bh=2Rky/zre2CgOmki3Royz+bT0OwzDkWU56RD4GhwDois=;
b=LSkLIGpG9ShZjXLaSritYcpo85aaGN2VjknMQg6krh3mK4uSvS3P9TTFmN3YmlsMbg
pZyG7lhu3Sjg7HAIyu/TMnXQLb5yS4CKWQnll3w3m7hsBq+QcE/taZuvdKE2DKEUybO3
GUR5e8ovC3WL8fe4YMwGAHY+LPN5x7eHoimlk0FXIaWZzJjaUSJm/iT7goNg2KUswiVr
L0U4P42CWI9ed8S9yBUFpl4uZWAQze7Dlcje9fkr1ZIoIFlqwCoMrTRrop+VJDfjWJAn
BIdS2MxeoJWb1H93fOX/5TwdMk8vgf6d56MMuWqI1PmpVi2wSRsKB0URBFRQLdcmn4il
68DQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1742149894; x=1742754694;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-authentication-results
:x-original-sender:to:subject:message-id:date:from:mime-version
:x-beenthere:x-gm-message-state:sender:from:to:cc:subject:date
:message-id:reply-to;
bh=2Rky/zre2CgOmki3Royz+bT0OwzDkWU56RD4GhwDois=;
b=SAS1StzU4TWHJfVq//Uk0qnfXcEmrMkUcRkBkjC6pIhFSGo5zL6EuzruV8VMLUZMlW
Pvx7mzJnYRkitjx3sDSMeNy1r54eRHUyx6hHM/r/aPs0QUJYXr1vTsdZ57nqNISC5gUc
u+VQbOl24PDUOK9GmmABiCodYiiCxQwfC80X2EmxijVXPv751geapSaEy05ZuPUws+oh
+CAMHmPr8J9Q17DvEFusS0Qe7pBt9lCuIOUXzoYu4kqnKo3aELJZQumQOHWau1x+5p2Y
o3WGq+T4i15tiGrit25y6F0EOzrbBNwZ+PW0hd7TbyxluhW8L7uaiBaMakIUrbdSX47X
cINg==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCWUZpfzAqJ5W8QP5iN5ZV31Ok4A/QNqzlSfgfty244SlwvMG0SMCbPTZIQhZxoCgSEbGZOjJIH04tZH@gnusha.org
X-Gm-Message-State: AOJu0YwejpnjEpq00UoAtPtG9AqU9JuFcyRGZf8Yetgv8L8ijbOYnki5
LKcdeEV4nFNLkWckywlb4LOlJFFvOdMWRJWZQMuQeYz6vc6PVbi9
X-Google-Smtp-Source: AGHT+IFqQyNDqVxrs5yX7IlLEGHK0/IsmKF2topx9jMjl3cCVhrbdXpWqG+Wzen2jnmlALYmOWq/uQ==
X-Received: by 2002:a05:6871:3a06:b0:29d:c832:840d with SMTP id 586e51a60fabf-2c691254509mr6492487fac.35.1742149894341;
Sun, 16 Mar 2025 11:31:34 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=ARLLPAL76dRBIMVRZnqzAz/OSCukdT3DhqKUt+IrH+w4YFmERQ==
Received: by 2002:a05:6870:b69d:b0:2bc:69a2:c157 with SMTP id
586e51a60fabf-2c66701f3d7ls1048960fac.0.-pod-prod-06-us; Sun, 16 Mar 2025
11:31:31 -0700 (PDT)
X-Received: by 2002:a05:6808:f0a:b0:3f8:5160:befb with SMTP id 5614622812f47-3fdf0647561mr6546365b6e.35.1742149891197;
Sun, 16 Mar 2025 11:31:31 -0700 (PDT)
Received: by 2002:a05:6808:3712:b0:3fa:da36:efcd with SMTP id 5614622812f47-3fddff56d2fmsb6e;
Sun, 16 Mar 2025 11:25:13 -0700 (PDT)
X-Received: by 2002:a05:6871:6a4:b0:29e:5c94:5b10 with SMTP id 586e51a60fabf-2c69123ed16mr6341440fac.34.1742149512408;
Sun, 16 Mar 2025 11:25:12 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1742149512; cv=none;
d=google.com; s=arc-20240605;
b=CIB7qUaEavH0ZAtDvdTWl+mWvAK+I0qE03TqFEWXOKXFv4agXE721Hcfw1H1RNhPxW
mo6hoIdGvyz9zi5C9WNrAwQnjSOXCwJzraHi2BmUkelMawXVvYJv8MzZSHshMCsO4Tc8
DBr4POz7W1DQk1/gWfFPywHa5qPxpZsxUI0FADzZ5ElLZiVogB7p+w3+uhMN7hQTyQp/
irG9x3t+cok7HOQqaWzxoPXoei17EuDASOK8E24w9UFLso0Dq4Ot6vu5Jhp+RxB4YGh3
gRYZV0+/ShK4/Zso25zY3DuVg32uDcrG1UIseeg+QVfnNn1uRj84L0NhmeoOJAWGNBla
Y42g==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
h=to:subject:message-id:date:from:mime-version:dkim-signature;
bh=a6pcOIDAXo9dIEbuNU8GDxrWdkoJN9n76U8c0goa+UY=;
fh=DMP0F9ULS1guKiqimntQRCN8ZraraesEgQuVcn7F0Z0=;
b=ONCxVxTwd9i9KhiQyHylPfhqhSgvfqUtE6yr4B5JMU7KVke8cCdjR6/0XfSLXdrHzc
8GPom41p0k2YlZXSoL/62iWk5+qSQmL50HC0APCR7mVDQmkIG576efv5XKZvKYVafZ0F
VGtZfysj8wnpE6DhsaQT+ADf/VTpjPsv6qJoaOcpOMHMTsT3NW/msSnqocgMxmCntVt7
kkoT9/jwqxtsyPTlcJ0vrpX5duFMsk08MOQ7HG9r9lJEy1kYDflyzzCnwkiZbLnkk2FY
u5SnKpRrKMqLf/IgvcSjEQ9ox2c2kw0bDQfwaT4p/5U9hnwWx7mbt898tcFH0vR4p1Au
3v3g==;
dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
dkim=pass header.i=@gmail.com header.s=20230601 header.b=QhmbMRQN;
spf=pass (google.com: domain of martin.habovstiak@gmail.com designates 2607:f8b0:4864:20::92e as permitted sender) smtp.mailfrom=martin.habovstiak@gmail.com;
dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;
dara=pass header.i=@googlegroups.com
Received: from mail-ua1-x92e.google.com (mail-ua1-x92e.google.com. [2607:f8b0:4864:20::92e])
by gmr-mx.google.com with ESMTPS id 586e51a60fabf-2c670fbb73fsi361500fac.1.2025.03.16.11.25.12
for <bitcoindev@googlegroups.com>
(version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
Sun, 16 Mar 2025 11:25:12 -0700 (PDT)
Received-SPF: pass (google.com: domain of martin.habovstiak@gmail.com designates 2607:f8b0:4864:20::92e as permitted sender) client-ip=2607:f8b0:4864:20::92e;
Received: by mail-ua1-x92e.google.com with SMTP id a1e0cc1a2514c-86b9d9b02cbso1638552241.1
for <bitcoindev@googlegroups.com>; Sun, 16 Mar 2025 11:25:12 -0700 (PDT)
X-Gm-Gg: ASbGncvzPyGt3ccEErm5dsUstLBFXuVnKZYB3fDpb9TpCFBS/1G/QnLJUwduXPofkXa
vjvwJUV4jvuxIvNawk0qfEcQvwkE40mYSdohG8+51q4ZkHXavfqI/ctgYtWKord8CGYxSUtIo1j
PVOtdtz/1LK0AGqK7YpkL2jXQ0gQ==
X-Received: by 2002:a05:6102:304d:b0:4bb:b809:36c0 with SMTP id
ada2fe7eead31-4c383201e6fmr6114257137.20.1742149511358; Sun, 16 Mar 2025
11:25:11 -0700 (PDT)
MIME-Version: 1.0
From: =?UTF-8?Q?Martin_Habov=C5=A1tiak?= <martin.habovstiak@gmail.com>
Date: Sun, 16 Mar 2025 19:25:00 +0100
X-Gm-Features: AQ5f1JoqxNKtMock_V97v_BKnTN6TY874Xi6sxixWuXB8OwYItkAC4STWE0nJvo
Message-ID: <CALkkCJY=dv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ@mail.gmail.com>
Subject: [bitcoindev] Hashed keys are actually fully quantum secure
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Content-Type: multipart/alternative; boundary="000000000000c531b3063079ca58"
X-Original-Sender: martin.habovstiak@gmail.com
X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass
header.i=@gmail.com header.s=20230601 header.b=QhmbMRQN; spf=pass
(google.com: domain of martin.habovstiak@gmail.com designates
2607:f8b0:4864:20::92e as permitted sender) smtp.mailfrom=martin.habovstiak@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 (/)
--000000000000c531b3063079ca58
Content-Type: text/plain; charset="UTF-8"
Hello list,
this is somewhat related to Jameson's recent post but different enough to
warrant a separate topic.
As you have probably heard many times and even think yourself, "hashed keys
are not actually secure, because a quantum attacker can just snatch them
from mempool". However this is not strictly true.
It is possible to implement fully secure recovery if we forbid spending of
hashed keys unless done through the following scheme:
0. we assume we have *some* QR signing deployed, it can be done even after
QC becomes viable (though not without economic cost)
1. the user obtains a small amount of bitcoin sufficient to pay for fees
via external means, held on a QR script
2. the user creates a transaction that, aside from having a usual spendable
output also commits to a signature of QR public key. This proves that the
user knew the private key even though the public key wasn't revealed yet.
3. after sufficient number of blocks, the user spends both the old and QR
output in a single transaction. Spending requires revealing the
previously-committed sigature. Spending the old output alone is invalid.
This way, the attacker would have to revert the chain to steal which is
assumed impossible.
The only weakness I see is that (x)pubs would effectively become private
keys. However they already kinda are - one needs to protect xpubs for
privacy and to avoid the risk of getting marked as "dirty" by some
agencies, which can theoretically render them unspendable. And non-x-pubs
generally do not leak alone (no reason to reveal them without spending).
I think that the mere possibility of this scheme has two important
implications:
* the need to have "a QR scheme" ready now in case of a QC coming tomorrow
is much smaller than previously thought. Yes, doing it too late has the
effect of temporarily freezing coins which is costly and we don't want that
but it's not nearly as bad as theft
* freezing of *these* coins would be both immoral and extremely dangerous
for reputation of Bitcoin (no comments on freezing coins with revealed
pubkeys, I haven't made my mind yet)
If the time comes I'd be happy to run a soft fork that implements this
sanely.
Cheers
Martin
--
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/CALkkCJY%3Ddv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ%40mail.gmail.com.
--000000000000c531b3063079ca58
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"auto">Hello list,<div dir=3D"auto"><br></div><div dir=3D"auto">=
this is somewhat related to Jameson's recent post but different enough =
to warrant a separate topic.</div><div dir=3D"auto"><br></div><div dir=3D"a=
uto">As you have probably heard many times and even think yourself, "h=
ashed keys are not actually secure, because a quantum attacker can just sna=
tch them from mempool". However this is not strictly true.</div><div d=
ir=3D"auto"><br></div><div dir=3D"auto">It is possible to implement fully s=
ecure recovery if we forbid spending of hashed keys unless done through the=
following scheme:</div><div dir=3D"auto">0. we assume we have *some* QR si=
gning deployed, it can be done even after QC becomes viable (though not wit=
hout economic cost)</div><div dir=3D"auto">1. the user obtains a small amou=
nt of bitcoin sufficient to pay for fees via external means, held on a QR s=
cript</div><div dir=3D"auto">2. the user creates a transaction that, aside =
from having a usual spendable output also commits to a signature of QR publ=
ic key. This proves that the user knew the private key even though the publ=
ic key wasn't revealed yet.</div><div dir=3D"auto">3. after sufficient =
number of blocks, the user spends both the old and QR output in a single tr=
ansaction. Spending requires revealing the previously-committed sigature. S=
pending the old output alone is invalid.</div><div dir=3D"auto"><br></div><=
div dir=3D"auto">This way, the attacker would have to revert the chain to s=
teal which is assumed impossible.</div><div dir=3D"auto"><br></div><div dir=
=3D"auto">The only weakness I see is that (x)pubs would effectively become =
private keys. However they already kinda are - one needs to protect xpubs f=
or privacy and to avoid the risk of getting marked as "dirty" by =
some agencies, which can theoretically render them unspendable. And non-x-p=
ubs generally do not leak alone (no reason to reveal them without spending)=
.</div><div dir=3D"auto"><br></div><div dir=3D"auto">I think that the mere =
possibility of this scheme has two important implications:</div><div dir=3D=
"auto">* the need to have "a QR scheme" ready now in case of a QC=
coming tomorrow is much smaller than previously thought. Yes, doing it too=
late has the effect of temporarily freezing coins which is costly and we d=
on't want that but it's not nearly as bad as theft</div><div dir=3D=
"auto">* freezing of *these* coins would be both immoral and extremely dang=
erous for reputation of Bitcoin (no comments on freezing coins with reveale=
d pubkeys, I haven't made my mind yet)</div><div dir=3D"auto"><br></div=
><div dir=3D"auto">If the time comes I'd be happy to run a soft fork th=
at implements this sanely.</div><div dir=3D"auto"><br></div><div dir=3D"aut=
o">Cheers</div><div dir=3D"auto"><br></div><div dir=3D"auto">Martin</div></=
div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List" 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/CALkkCJY%3Ddv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ%40mail.gma=
il.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/=
msgid/bitcoindev/CALkkCJY%3Ddv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ%40ma=
il.gmail.com</a>.<br />
--000000000000c531b3063079ca58--
|