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
|
Delivery-date: Sun, 15 Dec 2024 13:57:10 -0800
Received: from mail-oa1-f59.google.com ([209.85.160.59])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBAABBLFB7W5AMGQEBQDM6GY@googlegroups.com>)
id 1tMwbt-0000vr-Su
for bitcoindev@gnusha.org; Sun, 15 Dec 2024 13:57:10 -0800
Received: by mail-oa1-f59.google.com with SMTP id 586e51a60fabf-2a3da95c5b5sf284023fac.0
for <bitcoindev@gnusha.org>; Sun, 15 Dec 2024 13:57:09 -0800 (PST)
ARC-Seal: i=2; a=rsa-sha256; t=1734299824; cv=pass;
d=google.com; s=arc-20240605;
b=ADlBxzSAtUe16Ca37NcKiw4sGrFmyNv0613SvEXyVCVGufuy1htLJXABTpnZB91OGT
IvKQe/ytO2O3+30fan94ab4LKzKQ3aoDBdQlkUw4nHT/cLoeOrgl8BvbDnJCqudiGWOs
N7qY0BZATuW+1bOZUQyRGrutgoTtMxiG3rURuxnRKLnX3y2yieUrsu2DXka7XaBjSK6z
LaLwgwmmAHnC+0RFQAxyceLsE1AbfoEG892CKvlq1oobu5iPIbzJpyasT56svZtNhueB
xIstQeoCzMo6mxSx5PN2svlWsWcuwVI2Nql+9aAmOKfVI4H/+46Kf+wxS3gozA7wg8i6
Bqug==
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:subject:from:to:content-language
:mime-version:date:message-id:sender:dkim-signature;
bh=z0S2rwBAHUhTH3LrsQDyd79PUA5Ll2v68J2jk8rbNII=;
fh=kY9MEgddKdCbEpqdhsxiV1lrCfprJYmHxy12hR9XOoE=;
b=H+VlWU05sgTTXLVRido/X8lcLk0G/iXiPqSLHeqejPH+YBAFHsTf51IcZgYhsW7UaJ
GYs2LfYjg7wiSNEvPijTZ5/1VvblZKKmNpnHVBNYICO8uKMukPFParMzl9dHOwutT816
pZ/zfha95WLzu1Y2HRnY1CXRFl1xv5SjI7Ugk5CgVv5pzfHgaAxVN6X2up4/lFXUsUVx
3lavDgsbKA+N4jZe2SV0PxZUAqVtoDH+xjKwsQFXZpgNPQBIBGo9/4Hcpzu+GFMR+yTr
3vfDwrf0an8KborZxRQH87dj0Ti9fu4GeQrQb/XWzvKvLWTjmrg9ujtnC9nvKvkjIJ/4
sR/g==;
darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
dkim=pass header.i=@mattcorallo.com header.s=1734297663 header.b=X2oSru07;
dkim=pass header.i=@clients.mail.as397444.net header.s=1734297665 header.b=UsIRUKtN;
spf=pass (google.com: domain of lf-lists@mattcorallo.com designates 2620:6e:a000:1::99 as permitted sender) smtp.mailfrom=lf-lists@mattcorallo.com;
dmarc=pass (p=NONE sp=REJECT dis=NONE) header.from=mattcorallo.com
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1734299824; x=1734904624; 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:subject:from:to:content-language:mime-version
:date:message-id:sender:from:to:cc:subject:date:message-id:reply-to;
bh=z0S2rwBAHUhTH3LrsQDyd79PUA5Ll2v68J2jk8rbNII=;
b=w/JLS/dK01TuTIZclZCfMIVH7+tICaEveMEmgksZIVE9UqdzlM2UaE+7dB/tW2Lj9/
5+nW/m8YEE8/T1T9K+bn2Ia46BQiLYkz3ukQ2aOtS7tedvDd3wmtVwRT3j4jh0ZsoNlI
eGGPEh6GuuT1MmXzAmq3Le7dapG9tHroAMpxyPBrMmYMBNTsKkKuQT8J42TtVNDaLxUd
BTq+k+ytkbIAMFRPLYo/a0/NCYDqyqZsq9Ry5Dd+KlKiy8AgrXruMdk47UHsPIbYol4t
Nb1MOTy64Mb5RLxU7tlDtQeo5V3HDRXaAG3CuQPDII176RlxEcLjdxJV8q03irJv1+a0
XPeQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1734299824; x=1734904624;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-authentication-results
:x-original-sender:subject:from:to:content-language:mime-version
:date:message-id:x-beenthere:x-gm-message-state:sender:from:to:cc
:subject:date:message-id:reply-to;
bh=z0S2rwBAHUhTH3LrsQDyd79PUA5Ll2v68J2jk8rbNII=;
b=gKsv3/zp3HbjeinVVPoAHOctMNe1pPq/rFS966HhbMiW3mHOxJuVAkNDBFUtSOQcSe
N+yJOakRVKL7Txy7kb79Czo8R81vHplLoK9CBkif29B8S8l6Y/Zbt5AojFgxBdKoCQg1
wy1mZ+KAU3IHJBgVoEvhE6ICCZ7lnsdxWa6czyNLY70caAZloAgqXKxr/HmModHOakpK
rOEj4N3kgxGJBUN9eSB7D8r8fVMJINQ5OijwrtZqYKLZ2jW+gnNfRk4V4OGyTixOcuSx
KaygZIsMkCUgN+KK+ode4wVMYHpvjlNw4LbjY+XZ9g4QqKE7Mb8gjuWztltM70e+NTwP
jeQQ==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCUIsUbY3VSRZlt+lfFnpNazqfAbHjRCkFdRH0T72BVnoYL0XIsnhRjePMzq8E5a6bUJFLXa2vtqUqaM@gnusha.org
X-Gm-Message-State: AOJu0Yy5X+8byYQmsu7fhdnUXCoL77b3vUOB56MEEgRhCQQ2Wiw9p6qy
Dp9jR3kTK2bh4HTj3QdbC4swGx/spwIfJsEAiEHlx0F6GzRKu28d
X-Google-Smtp-Source: AGHT+IG2VO/kfggRkflt/SXuJGIp3bZuabQuFTDfwRtW/n9968H0JqOBgHCaz5AE6kzxoCoUEOxMiQ==
X-Received: by 2002:a05:6870:9a25:b0:29e:6b27:72d with SMTP id 586e51a60fabf-2a3ac836332mr7048216fac.26.1734299823297;
Sun, 15 Dec 2024 13:57:03 -0800 (PST)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a05:6870:82a9:b0:29d:e970:3ca4 with SMTP id
586e51a60fabf-2a3af82415dls1076093fac.1.-pod-prod-02-us; Sun, 15 Dec 2024
13:57:00 -0800 (PST)
X-Received: by 2002:a05:6808:23d0:b0:3eb:3f93:7aaa with SMTP id 5614622812f47-3eba6822ed3mr5924587b6e.4.1734299820591;
Sun, 15 Dec 2024 13:57:00 -0800 (PST)
Received: by 2002:a05:6808:50:b0:3eb:31af:367e with SMTP id 5614622812f47-3eba55699a0msb6e;
Sun, 15 Dec 2024 13:43:03 -0800 (PST)
X-Received: by 2002:a17:903:174d:b0:216:3b31:56c2 with SMTP id d9443c01a7336-21892a62cdcmr177754535ad.53.1734298982471;
Sun, 15 Dec 2024 13:43:02 -0800 (PST)
ARC-Seal: i=1; a=rsa-sha256; t=1734298982; cv=none;
d=google.com; s=arc-20240605;
b=RP7YvWVvvymymvZQ6ix1LZDW7GS7LCHmc2knW3MVfXHGGUPIiNUq7rW8g5tGplSdrl
jFAcFvSa9Vqaq17nfbvDMYesh+aoYyTKKVsZ71SCnGO0ELjyTH77X3AJxB0Q0Oadn2s/
FrFZBNAiit9qQhRPxuyPQRdemv+J0T5JonuPIhGgMqit5FfnQdzusU5A2o7mvR8kAS4j
W+1pHST3mvuaX4vqu0eIbK3+diFBMWLeB7MHdyUrWImK4BblL9MyHmH4g8MqarcJ4kz/
FEWK7r+krh1rtxB7U9ROV8lUNck8PimV1uQncBx0ye2in1hUXu/DixDIqkn4AXqna3h0
EjkQ==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
h=content-transfer-encoding:subject:from:to:content-language
:mime-version:date:message-id:dkim-signature:dkim-signature;
bh=5Ki1b84VaHuDkdOiL4VmKSuL1PRkPBN+HjtHC1K9pGc=;
fh=DMP0F9ULS1guKiqimntQRCN8ZraraesEgQuVcn7F0Z0=;
b=cAjyDP9M5kMouKly1/jds0tEShvIfm14Y1Ssx+yjsramyCGZKsgcJjKQv9QlXc0LHp
/P/02v3mKV+Hxb3zo0j1OKRqc/AW60eglx14VGzFosoDj/lBM5DShJVKPykWSxJUyPyL
cf/kAHMpcJ3z4yh5V8FYTq+xSzIG0iZsrvDYsE9rysojwS2RWcbFtapsroIhutYDlaBq
E2sxCZHT1vC0fTc39iJf43DgVDy6basCyhPYpX8JFjXX26zPi8Jtc2Rclejs0zal5/co
K5+2G8Xn5eToJQsgyAtsQ5qmNc9TLiALCMHXIGD2ttJbz6CMzipjr/hI/bmIs4vK6FVh
H4xg==;
dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
dkim=pass header.i=@mattcorallo.com header.s=1734297663 header.b=X2oSru07;
dkim=pass header.i=@clients.mail.as397444.net header.s=1734297665 header.b=UsIRUKtN;
spf=pass (google.com: domain of lf-lists@mattcorallo.com designates 2620:6e:a000:1::99 as permitted sender) smtp.mailfrom=lf-lists@mattcorallo.com;
dmarc=pass (p=NONE sp=REJECT dis=NONE) header.from=mattcorallo.com
Received: from mail.as397444.net (mail.as397444.net. [2620:6e:a000:1::99])
by gmr-mx.google.com with ESMTPS id d9443c01a7336-218a1e14cf2si1829905ad.7.2024.12.15.13.43.02
for <bitcoindev@googlegroups.com>
(version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
Sun, 15 Dec 2024 13:43:02 -0800 (PST)
Received-SPF: pass (google.com: domain of lf-lists@mattcorallo.com designates 2620:6e:a000:1::99 as permitted sender) client-ip=2620:6e:a000:1::99;
X-DKIM-Note: Keys used to sign are likely public at
X-DKIM-Note: https://as397444.net/dkim/mattcorallo.com and
X-DKIM-Note: https://as397444.net/dkim/clients.mail.as397444.net
X-DKIM-Note: For more info, see https://as397444.net/dkim/
Received: by mail.as397444.net with esmtpsa (TLS1.3) (Exim)
(envelope-from <lf-lists@mattcorallo.com>)
id 1tMwOC-006ecj-2r for bitcoindev@googlegroups.com;
Sun, 15 Dec 2024 21:43:01 +0000
Message-ID: <c2684826-6c93-419b-9a96-c0f0a791c9ac@mattcorallo.com>
Date: Sun, 15 Dec 2024 16:42:59 -0500
MIME-Version: 1.0
Content-Language: en-US
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
From: Matt Corallo <lf-lists@mattcorallo.com>
Subject: [bitcoindev] Trivial QC signatures with clean upgrade path
Content-Type: text/plain; charset="UTF-8"; format=flowed
X-Original-Sender: lf-lists@mattcorallo.com
X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass
header.i=@mattcorallo.com header.s=1734297663 header.b=X2oSru07;
dkim=pass header.i=@clients.mail.as397444.net header.s=1734297665
header.b=UsIRUKtN; spf=pass (google.com: domain of lf-lists@mattcorallo.com
designates 2620:6e:a000:1::99 as permitted sender) smtp.mailfrom=lf-lists@mattcorallo.com;
dmarc=pass (p=NONE sp=REJECT dis=NONE) header.from=mattcorallo.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.8 (/)
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/c2684826-6c93-419b-9a96-c0f0a791c9ac%40mattcorallo.com.
|
