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
|
Delivery-date: Sun, 15 Dec 2024 16:02:02 -0800
Received: from mail-qt1-f189.google.com ([209.85.160.189])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBDD7VM4YZ4NBB4O37W5AMGQELJA2DZA@googlegroups.com>)
id 1tMyYk-0002t3-45
for bitcoindev@gnusha.org; Sun, 15 Dec 2024 16:02:02 -0800
Received: by mail-qt1-f189.google.com with SMTP id d75a77b69052e-467bb8aad28sf13511951cf.1
for <bitcoindev@gnusha.org>; Sun, 15 Dec 2024 16:02:01 -0800 (PST)
ARC-Seal: i=2; a=rsa-sha256; t=1734307316; cv=pass;
d=google.com; s=arc-20240605;
b=kaX4Ii6sbi/J0Pa52BxrBsFAnplL3L5yPRle6xwBeggM0mvU3v5EhnbX8RgVmmir1x
oeSCy69SzlJ8DSaRVBiM6Ex7zI3tIdIUW9Md2960+MfuTcm9ZF4oSVFIGuvgDG14kiCz
7BjrzzBNPD8NUMduW6bITSrqdJV5sGzUzMRU8OsmlsM/mOf/zehSGHRUCwes5F9Tqd6y
c5SZ4lxvXlS+G7F8ptzytWe/ftzkN79H/fQvfJai8AfRKfohYb2c3SLjwjMYavC0Tz2/
YYd3p0seCBfARi7tqot+HOJ3O8LE7y14WuLgm5OU2q52kK2jTvDZnRt1fxZJhK3I5fBD
5DGg==
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:in-reply-to:from:content-language
:references:to:subject:user-agent:mime-version:date:message-id
:sender:dkim-signature;
bh=Wri3wgAdTZHUVoI/PVZQ+8LiQuLAPLVDjzHKX+rDKrI=;
fh=llMjroX8hQmrxu+sVoJ9gB7yeIXwVTjwEp8vDZQLXME=;
b=XyPH9/aBXBdqauVrfRx6sA1VUHo39wIDeSK7W7xsQBcieJ017pV660B4n1cm4POIeT
Cb6mzljZw8zNgOn7iTNtLvE4mRO3cxRLLujlI6vZtfJLhNLbYjxEm+bO9WvzOXALSz8h
GzaGRiQZ1YjEgBCD+bXr+ahIHlv6fBnbex6PDjBymJblygHev5wGXClTzasnzdqHdf5N
9q5JNabxLgZ3TC3DJ51xl6s/Md7u8r0/ECmY9GGIfI5ZG0BRn46Acj5SpuRVpH0V5hfN
cmSbyHUSPXLEqr+4EkiShUjNljvj4lFG3d16ulpxiTVHGiN/jVng4I9NziHPmGXrr7Of
JwJg==;
darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
dkim=pass (test mode) header.i=@dashjr.org header.s=zinan header.b=qftEHde5;
spf=pass (google.com: domain of luke@dashjr.org designates 192.3.11.21 as permitted sender) smtp.mailfrom=luke@dashjr.org;
dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=dashjr.org
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1734307316; x=1734912116; 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:in-reply-to:from:content-language:references:to
:subject:user-agent:mime-version:date:message-id:sender:from:to:cc
:subject:date:message-id:reply-to;
bh=Wri3wgAdTZHUVoI/PVZQ+8LiQuLAPLVDjzHKX+rDKrI=;
b=UTd34WH7qCA9DnSjrbVzmgzat+CnfZeLBUF5k4Z2WhIDuXLHElzTOiwHn2bp+qdrFM
0GD/Orf7EffchmET6kbXCvtbqIdrV7Igz+5eppUlAbpqrh3i/a8CIVNYx9DdsmstfM5Y
AF7CBnGlNAmf5zji4kRVsw00c27ezNGMEtGXTtZ6fWDnomHr1o27QEDTm5RKojaTnDsz
Lh6y/TPXsipHwEKEzeR3E1KyhTmMzUB9mvqzLDexnWqEhCNrE8XoDALw4yOjpGAif5hU
QvOs4Ho1QoozQD9vkEgiFV+MWsmXSeH6/mK+sH+Pvh6pWkFhPMW/KPQq1TUwgOVFCfZa
W9RQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1734307316; x=1734912116;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-authentication-results
:x-original-sender:in-reply-to:from:content-language:references:to
:subject:user-agent:mime-version:date:message-id:x-beenthere
:x-gm-message-state:sender:from:to:cc:subject:date:message-id
:reply-to;
bh=Wri3wgAdTZHUVoI/PVZQ+8LiQuLAPLVDjzHKX+rDKrI=;
b=Xr9gj/BimyqeYz41rn4iGWR4j5dlqsqOQAcJg7Xc1h9n1GycYOMsMlXybgztxk7Kdc
Q0DWspoA62seThGlGn5X5R3gKSTTbulwtXCf2FoKfSOGt6JuA32iaP2jSSTersAgHC3V
Xp419LESOui1pOhlzS/rpIZbbogn+jQwpbBvwV/5iLYx3uvQV+KvicRvluOLKuLmXG1h
BDw52RDbwezCrSxKK/5/O7lp8FtEowbcVdvZJryLtICN634rDSTO5KwZkknGqQ5cEkBT
NNXoVqmRXw1j/Sk0wTWkjK9fAJb1k7IKtGgsnGiTfZy8aL4fU/YsumRg94yaC0AzoSUW
NxjQ==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCUaBxnSnyOzmcX6JZRWUzo6f3Is4aIT8pCXJ+nxNP7b8vZFcjjkP7ctWmS5lOs/WWYImEZ71R/xTE47@gnusha.org
X-Gm-Message-State: AOJu0YyVUn4aTOZdmdrFV3Bl+8uxHku31bnPaE/qTrcjX7A5IU6DA8VY
cf0KHtYQg1oxCWatkbbajaIFoz8nEI+RY6F9jxUT3d+e84qeoFZ3
X-Google-Smtp-Source: AGHT+IFlOzsYPR3BRTrA4Wl2P0gcTA8XKrfnIg9qyPjDKN5j7d8oSrMmTuwJUNgDfQ8I/O4taIO5YA==
X-Received: by 2002:ac8:7f14:0:b0:467:b625:b37d with SMTP id d75a77b69052e-467b625b86amr140266331cf.56.1734307315376;
Sun, 15 Dec 2024 16:01:55 -0800 (PST)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a05:622a:1314:b0:466:98fc:1e42 with SMTP id
d75a77b69052e-467a67480afls51483551cf.1.-pod-prod-08-us; Sun, 15 Dec 2024
16:01:53 -0800 (PST)
X-Received: by 2002:a05:620a:8809:b0:7b1:4327:7b63 with SMTP id af79cd13be357-7b6fbf172d2mr1696789185a.32.1734307312796;
Sun, 15 Dec 2024 16:01:52 -0800 (PST)
Received: by 2002:a05:620a:209d:b0:7b6:d72a:7c26 with SMTP id af79cd13be357-7b6f32386a0ms85a;
Sun, 15 Dec 2024 15:54:29 -0800 (PST)
X-Received: by 2002:a05:600c:5254:b0:434:a902:97cd with SMTP id 5b1f17b1804b1-4362aa3f7damr84080665e9.12.1734306867690;
Sun, 15 Dec 2024 15:54:27 -0800 (PST)
ARC-Seal: i=1; a=rsa-sha256; t=1734306867; cv=none;
d=google.com; s=arc-20240605;
b=MO4qkO4VsmRTWsgTaViPb5l+6AcpzA66vSEAObu+2BZqrHwQEVWzDtRqDiKaynOfyM
CkifFQABRFGDGF74ZiTFmFv4FzM/LzlBodqGA5eHxRfrr1cmUizk7vCDTRI9nezEyInb
CtPBtR5x449BDTFijF99Qjkt98wvceS9f+4Wwed3oVftnIP93BgMBf4Ux+YmpDt2U6R2
JRHf3VrE6FLIFOV73PffZ7PqFb3XzxAq6LS1msFX6EeYU3TWhEyMqMLv7WQ64YSgbJEJ
OJdFi9XBRYxgfd5Y4nAGsR4fJkybXXnWBU4iIgdVh7YDXRb0XX/vHY9E/xL5Xyb+MXag
F8ng==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
h=content-transfer-encoding:in-reply-to:from:content-language
:references:to:subject:user-agent:mime-version:date:message-id
:dkim-signature;
bh=8UAGhheZx2btS84BuZhgiucNPtJrLVQieOu+bey2YN8=;
fh=VcGcg+Zjs9gw1uDcHbxsAILhBAcecnbJzZRdxgKVDIc=;
b=XoX5MvjgwpPA3LLiP2i/oPmB5RlswwlQHxU8+FBQV8HeWxh+ATEoaY19PCFqkUrUei
QNvQD4aOUHCkS6kfJdW7FJiDWvmJIp0QfiYeAFZHrAK76zNjTW41XnM6X7WkfzCW33OO
fUFz+DnyGoiPWuMBZJTQpyEGLqWB9dQxdD4nvYiPuH5ZPn9epRS3iiwRu7pvOzvynD7J
bn7tK4Y0z0xMx5hF+SZkd76Oty7al1TIKmKT7vzkcZx/JpZRFi3Cyt/+39dZctWzimcg
XOYOm2q/hspImP3rU/7lbWPzMSHCK7DvRw5reUpt4huUDBLD8hoB2nzHoTfVooxzXANt
z9ow==;
dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
dkim=pass (test mode) header.i=@dashjr.org header.s=zinan header.b=qftEHde5;
spf=pass (google.com: domain of luke@dashjr.org designates 192.3.11.21 as permitted sender) smtp.mailfrom=luke@dashjr.org;
dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=dashjr.org
Received: from zinan.dashjr.org (zinan.dashjr.org. [192.3.11.21])
by gmr-mx.google.com with ESMTP id 5b1f17b1804b1-43635f65285si726285e9.0.2024.12.15.15.54.27
for <bitcoindev@googlegroups.com>;
Sun, 15 Dec 2024 15:54:27 -0800 (PST)
Received-SPF: pass (google.com: domain of luke@dashjr.org designates 192.3.11.21 as permitted sender) client-ip=192.3.11.21;
Received: from [192.168.86.24] (99-39-46-195.lightspeed.dybhfl.sbcglobal.net [99.39.46.195])
(Authenticated sender: mailrelay)
by zinan.dashjr.org (Postfix) with ESMTPSA id E7FF038AF043
for <bitcoindev@googlegroups.com>; Sun, 15 Dec 2024 23:54:24 +0000 (UTC)
Message-ID: <52f3bfc0-9446-4400-bf7a-7e38e5777c56@dashjr.org>
Date: Sun, 15 Dec 2024 18:54:18 -0500
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: [bitcoindev] Trivial QC signatures with clean upgrade path
To: bitcoindev@googlegroups.com
References: <c2684826-6c93-419b-9a96-c0f0a791c9ac@mattcorallo.com>
Content-Language: en-US, en-GB
From: Luke Dashjr <luke@dashjr.org>
In-Reply-To: <c2684826-6c93-419b-9a96-c0f0a791c9ac@mattcorallo.com>
Content-Type: text/plain; charset="UTF-8"; format=flowed
X-Original-Sender: luke@dashjr.org
X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass (test
mode) header.i=@dashjr.org header.s=zinan header.b=qftEHde5; spf=pass
(google.com: domain of luke@dashjr.org designates 192.3.11.21 as permitted
sender) smtp.mailfrom=luke@dashjr.org; dmarc=pass (p=NONE sp=NONE
dis=NONE) header.from=dashjr.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 (/)
One thing to add: the post-QC script path does not require a softfork to
commit to, as long as it is well-defined. So wallets could begin
implementing this fallback immediately, without waiting for _any_
softfork activation, as soon as the spec is final. They _would_ need to
guard the post-QC script as if it were itself a private key, which could
be an issue for hardware wallets - but I suspect there's probably a way
around that too...
On 12/15/24 4:42 PM, Matt Corallo wrote:
> There's been a few rough ideas for QC robustness in the signature
> scheme over Bitcoin transactions over the past many years, but many of
> them have a number of fairly major drawbacks.
>
> First, some base assumptions:
>
> (a) QCs that can break EC will take a while (probably closer to a
> decade or two than a few years). This lines up with NSA and other
> recommendations. We have time to upgrade, but we might consider having
> an option today for wallets to get QC security later.
> (b) Its entirely possible that fundamental scaling constraints will
> emerge and QCs that break EC simply won't ever be reality. We might
> not want to bet on this, but its possible.
> (c) We'll get some reasonable warning before QCs are there - QC
> development requires immense resources, so much so that only a few
> organizations in the world can afford to hire the talent required and
> fund the lab. This type of development has and will likely continue to
> lead to announcements as progress continues, and we'll have a few
> years warning as QCs get closer and closer.
> (d) post-QC security assumptions (like Lattices and obviously
> Supersingular Elliptic Curve Isogeny) are insufficient to secure coins
> today, and are bad candidates for inclusion in Bitcoin's consensus due
> to the likelihood of future cryptography research. This implies the
> only candidates for post-QC signature security in Bitcoin's consensus
> today are hash-based signatures (basically SPHINCS/SPHINCS+).
> (e) its not worth waiting on OP_CAT and the other more general script
> opcode additions for this, as those seem stuck in bikeshed hell, not
> to mention questions around MEVil and Bitcoin's future abound.
> Further, doing this via dedicated opcode simplifies wallet adoption,
> which is likely to struggle already given the additional workload for
> wallet developers for no immediate user-facing features.
>
>
> Given these assumptions, it seems ill-advised for wallets today to
> start locking funds up in a way where they need to pay the on-chain
> footprint cost to get post-QC security for their transactions *today*,
> but given upgrade cycles in Bitcoin it also seems ill-advised to not
> have some option for wallets to have "emergency" paths.
>
> Luckily, taproot provides a great way to build such a scheme! Because
> taproot script-path spends are strongly-bound (the taproot script-path
> hash t includes the internal key in its hash), a future QC could
> determine the associated private key and script-path merkle root, but
> it cannot forge an alternative script-path merkle-root.
>
> This provides a compelling hook for post-QC security - with the simple
> addition of an OP_SPHINCS (or equivalent post-QC non-one-time-use
> (i.e. not Lamport/Winternitz) signature verification opcode,
> functioning in much the same was OP_CHECKSIG works today), wallets
> simply need to construct their taproot outputs to always contain a
> script-path alternative spending condition. When QCs are becoming a
> reality, key-path taproot spends could be disabled via soft-fork,
> forcing spends to be done using the QC-secure path.
>
> This scheme obviously has the major drawback of non-upgraded funds
> confiscation at the time of QC existence, but:
>
> (a) we could instead require explicit opt-in for this scheme. This has
> the drawback of yet another on-chain fingerprint and would require a
> new scriptPubKey format (but keeping the existing bech32m address
> format, hopefully most wallets support that without any code changes
> today). Of course if we do, substantial quantities of Bitcoin which
> are unlikely to ever be spent could lead to supply shock, severely
> damaging Bitcoin's utility in other ways,
> (b) alternatively, we could allow key-path spends for wallets which
> prove the script-path is a NUMS point (via some new keypath+proof
> spend variant). I doubt many wallets today bother committing to a NUMS
> point for their taproot output pubkeys, so this would break existing
> wallets, but it would allow for an opt-out scheme.
>
> This scheme has the incredibly nice property of not bloating existing
> use-cases nearly at all (just one extra taproot script-path branch,
> but that's not a huge deal generally).
>
> There's a few things to bike-shed on here, though - first of all
> whether to require opt-in or provide an opt-out and secondly whether
> to also fail any script-paths that hit an ECDSA signature validation
> (probably yes?).
>
> I assume this has been written up elsewhere but I couldn't find it.
> Most of this is due to not_nothingmuch, I'm just writing it up here
> and taking credit for it.
>
> This doesn't address the questions around PoW in a post-QC world, of
> course, but that likely isn't something that can be answered until we
> see more practical limitations of QCs (eg what is the minimal latency
> of a QC gate? If its particularly low, can we simply complexify
> Bitcoin's PoW hash function in order to delay QC results far past when
> traditional hardware is able to mine a block?)
>
> Matt
>
--
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/52f3bfc0-9446-4400-bf7a-7e38e5777c56%40dashjr.org.
|
