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
|
Delivery-date: Mon, 16 Dec 2024 04:35:54 -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+bncBDBNTKFG4EDRBIF5QC5QMGQEMNIVXUI@googlegroups.com>)
id 1tNAKH-0005LF-Is
for bitcoindev@gnusha.org; Mon, 16 Dec 2024 04:35:54 -0800
Received: by mail-qt1-f189.google.com with SMTP id d75a77b69052e-467905ab1bbsf145003101cf.1
for <bitcoindev@gnusha.org>; Mon, 16 Dec 2024 04:35:53 -0800 (PST)
ARC-Seal: i=2; a=rsa-sha256; t=1734352547; cv=pass;
d=google.com; s=arc-20240605;
b=Rq2QIAYnDA186wVDtt2qRe173+Cd7anYkuvmlxApo8WpmYVvvrfLs90nIt5oe57lmH
fupW8+fsiw1GraqcYF8OfUzLjFKHMTw+yvgyzbX/UFQOr+R56E5FNyh9tmCectImEAgr
6O8WD8xU0q3fgGB0eD+5tbVF1G077Oi3Hm8pyTIAFc78AcSzunDmpbIeQKRdVir1OLog
JJ4Ih48Weq97NDI8HoPBqDVM3xO0TbKS8f+EehdDhscf5sG4H6ijcishnVnxWoq/qTkw
P9U5uPR2Fr+SZwGM+0F9EigPby9oBOcJmvQU0Q1TToYo3N0zJ1nrKKH6LmWHn+4t+nqR
fX3Q==
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:content-disposition
:mime-version:references:message-id:subject:cc:to:from:date:sender
:dkim-signature;
bh=RpdMT04vOcR1h7W02+FdlXXF5g8GFTLKM5xsgih9mwQ=;
fh=yD3Rbq7WrvoUPrKKQUlrP2WXZW2DC5d4dmwod5c98g8=;
b=lfb0TcSOZf5KKY3fCTfrbBgmuXbhZcjiOlKZSUW+78kp041MwQX+iHldmHUXe1vSqr
QhDOt04IVs8xC26UOyC2OtRWn2tj0yyldJWbfrQic7A3nBdsN2SsVkF1qJ3Uq9ewkFxp
p2YmFs9A1mlPYh/mLMkqh/4QpUYIKcX3HxzX6ycL4dfrTF5carq8ZM0PT57Asz9R0XqO
s18vRog5rw6AWlbs2owoWZ3KdslO6x/RMB+JFgs2aZshXBqHYjKWQ3b8tKYEqmBQd1zW
GLKZQ8I+bkJKpkiOthEmrTSI8i3/H3ed35uMDPMk7pc3UwXpnKlbdzN8sPh7+DS8WewE
K5Zw==;
darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
spf=pass (google.com: domain of aj@erisian.com.au designates 172.104.61.193 as permitted sender) smtp.mailfrom=aj@erisian.com.au
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1734352547; x=1734957347; 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:content-disposition:mime-version
:references:message-id:subject:cc:to:from:date:sender:from:to:cc
:subject:date:message-id:reply-to;
bh=RpdMT04vOcR1h7W02+FdlXXF5g8GFTLKM5xsgih9mwQ=;
b=on2lLkKSSuyH1YPPlg1P16G56YIFGhrqxWIrm1ST2z/faz3cfd2mz+5Fk2UoavtHc1
UJmlAlgQP15GkQETgScarKN0oDog136aQ6y5ihWnRefAIIFCUNaicm2/wV6bUmtXVXme
59bKlQaYsQEvGmkWOZtx3LQs05TjotsPdkvVUoAU7hQht+oEJ0sBx/RiS0PS5HX6OnKR
MhSq9/96qkdJfairM2sQe0f+oxw/7zT5vB+HMp+WCwe4mGZiZgs99ZmbCPEDMaJt80Sc
CXQx3z1q4ponpEG0V7WBSdcCRVAB/eS5ZCFXNke5CTMh1/p6COe1VRonzNaPm+Z+B6Le
6IjA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1734352547; x=1734957347;
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:content-disposition:mime-version
:references:message-id:subject:cc:to:from:date:x-beenthere
:x-gm-message-state:sender:from:to:cc:subject:date:message-id
:reply-to;
bh=RpdMT04vOcR1h7W02+FdlXXF5g8GFTLKM5xsgih9mwQ=;
b=pgo99QewvBcEojDvoTepFHuqQ/YlHgm0o6ACjpJrDpNOWl8kEyVI+Zk4MihmTj9ohB
ZWlsgt8kqTdEtT3NdVuNT8mW9y1VEJyvu7+CjrxuegFM+nmR8rSOiUiVqdaHrXTw7KGk
rYy2K8KIy6dcGDhGa0gMi5KR/L+eYaEjtV8nKrfB7IWtgcIs6JQZIcICO/OfTEUmkfAd
QMBky1dBIYiwZlA5b5SoX5+GEXOxzDcZGQaP7OooUsbkkDE7TJWCK//MRv166E81c34Z
rN96bZY1yWvQ+xbpAAOWsEohJap39ikA59OcMpAzo2xFkKXwYLRdPu4RmT4TiRt01qzW
ObKQ==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCXGK/qMc340/Tu18Doq2Rs4+ynd2GhlehXphQbnIqKDl3QybYVtOtpQsw3+e/npgAe5LtbrVn4AuTII@gnusha.org
X-Gm-Message-State: AOJu0YzBBaGmKUs868ydnVwqo4JWDOZk2PSUl6KRVmDUZCGdaE1QyUzW
MtGWolkTXdJFgIIWovdF+w87taIjL72wGzbBjzFPYacN1Va732nz
X-Google-Smtp-Source: AGHT+IFoVtKTT99Qk4slUIZFUS5VBtWVWOidmkUwTfwKfLeeWDEagSgfJ9KDvnG2M/Yepo2ktN3BUw==
X-Received: by 2002:ac8:7f52:0:b0:467:6e87:99e8 with SMTP id d75a77b69052e-467a58523b3mr250284771cf.52.1734352547088;
Mon, 16 Dec 2024 04:35:47 -0800 (PST)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a05:622a:181b:b0:467:5082:daee with SMTP id
d75a77b69052e-467a6764998ls55478781cf.2.-pod-prod-04-us; Mon, 16 Dec 2024
04:35:44 -0800 (PST)
X-Received: by 2002:a05:620a:2989:b0:7b6:6a3b:53af with SMTP id af79cd13be357-7b6fbee7c41mr1960059185a.14.1734352544323;
Mon, 16 Dec 2024 04:35:44 -0800 (PST)
Received: by 2002:a05:620a:34c:b0:7b6:67a8:4fcd with SMTP id af79cd13be357-7b6fa749338ms85a;
Mon, 16 Dec 2024 03:14:40 -0800 (PST)
X-Received: by 2002:ad4:5968:0:b0:6d4:139c:cef0 with SMTP id 6a1803df08f44-6dc8ca93ab5mr166254486d6.22.1734347679102;
Mon, 16 Dec 2024 03:14:39 -0800 (PST)
ARC-Seal: i=1; a=rsa-sha256; t=1734347679; cv=none;
d=google.com; s=arc-20240605;
b=cbQQABGaMZmE+ErpwfXs3zr+CqarL93a9rKNJH1R+NLLCEQtlbrs1Rx4PVzFXZxllz
2ZORa8e5Wpi5/y4BARYUfq9j7hce8RJDWEds/KaGUV1OBqE3fCjLAmihnIHDPy0bWsTw
p0fghSVPSudb94jTaImWQCK9eOhMnrizeUMxZk124+YaCAfKn85IY2cS+Cud0mUIQBnK
i5AnVZ4ClIyId49G61QLc6A5FAmPFQT/ipr2rpt6SFLXpxGqJeWB6hkFL+xKwIOl41s7
C5A5osRVx5hkNUu+0tGlw+1tgyPJyuNd2DxWZb1qWK77+e31yAhb2UvVESEWGEE35XaM
gR+g==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
h=in-reply-to:content-disposition:mime-version:references:message-id
:subject:cc:to:from:date;
bh=s7DChqPpJbGyjAUV37kZXBcYfwA6h6r5Om3TowXxUVo=;
fh=xW8bxyqQYHE1uH3XvdCMfZVppoYs0vQZCdqgnVz97es=;
b=k9kuqC52zlvd2KNkmG5lh3onnF8YOgXQ0GRX1G+WTJg3DuKot5shV6KCRoRgf4GrAo
wocuhu71aWb/D2ue7ywmk9qpQZZwS+4oGxZgk9KCL2bxEuouc38WYUNsh316x7g9slvP
UiI1S4S2drj4Gp45k3ASHfoxzhQqeAGjc9t6vmDZ8ZMjKoJv9WnZGrEBXnkCFm489wGB
kOJLVjOBHCR1KgUbEG07Iwqq9AKjkK5eiRTpqCM5UszSCiDJ5ZxGV+V9C6O8BHxxON+9
Zl+0Xlr3peWGMkbvAjGA6fnjspjtytLNFuUm1GAeg+WzTrM6Y/3ADfgSDtOjaXJxtD2g
KAnA==;
dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
spf=pass (google.com: domain of aj@erisian.com.au designates 172.104.61.193 as permitted sender) smtp.mailfrom=aj@erisian.com.au
Received: from cerulean.erisian.com.au (azure.erisian.com.au. [172.104.61.193])
by gmr-mx.google.com with ESMTPS id 6a1803df08f44-6dccd33aad0si1831326d6.5.2024.12.16.03.14.38
for <bitcoindev@googlegroups.com>
(version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
Mon, 16 Dec 2024 03:14:38 -0800 (PST)
Received-SPF: pass (google.com: domain of aj@erisian.com.au designates 172.104.61.193 as permitted sender) client-ip=172.104.61.193;
Received: from aj@azure.erisian.com.au
by cerulean.erisian.com.au with esmtpsa (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
(Exim 4.94.2)
(envelope-from <aj@erisian.com.au>)
id 1tN93Y-00030C-Ag; Mon, 16 Dec 2024 21:14:34 +1000
Received: by email (sSMTP sendmail emulation); Mon, 16 Dec 2024 21:14:28 +1000
Date: Mon, 16 Dec 2024 21:14:28 +1000
From: Anthony Towns <aj@erisian.com.au>
To: Matt Corallo <lf-lists@mattcorallo.com>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Trivial QC signatures with clean upgrade path
Message-ID: <Z2ALlBGIyZLVbfVG@erisian.com.au>
References: <c2684826-6c93-419b-9a96-c0f0a791c9ac@mattcorallo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Disposition: inline
In-Reply-To: <c2684826-6c93-419b-9a96-c0f0a791c9ac@mattcorallo.com>
X-Spam_score: -0.0
X-Spam_bar: /
X-Original-Sender: aj@erisian.com.au
X-Original-Authentication-Results: gmr-mx.google.com; spf=pass
(google.com: domain of aj@erisian.com.au designates 172.104.61.193 as
permitted sender) smtp.mailfrom=aj@erisian.com.au
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 (/)
On Sun, Dec 15, 2024 at 04:42:59PM -0500, Matt Corallo wrote:
> 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.
Some downsides of this approach:
- "OP_SPHINCS" signatures would be very large, at 8kB to 50kB. That
reduces inputs spent per block to a maximum of between 500 and 80,
given the existing constraints on witness data. Compared to bitcoin
blocks today, as I write, tx cf6391ca [0] is targetting the next block
and spends over 600 inputs on its own, while taking up only about 4%
of a block, so this seems like a big limitation. Probably better to
either pick something with much smaller signatures (which probably
means risky cryptographic assumptions, or single-use-pubkeys), or
to increase the block size in one way or another, eg as cryptoquick
proposes [1].
[0] cf6391ca2f3c361b666937fe7ae3e283850c9b81682755b7f5ab64bfd4c9503a
[1] https://github.com/cryptoquick/bips/blob/p2qrh/bip-p2qrh.mediawiki
- There's a fair bit of bikeshedding you could do about OP_SPHINCS,
including choosing different parameters for SPHINCS+, different
encoding of pubkeys, different "sighash" selectors for what is to
be signed, and different PQ schemes entirely. Without real quantum
computers to optimise against, many of those variables probably can't
be chosen objectively.
- Adding in secret OP_SPHINCS spend paths prior to an OP_SPHINCS
consensus change being active (or at least locked-in) seems very risky:
- it provides a way for insiders to cause you to lose all your
funds (prior to activation, selling your SPHINCS pubkey to a miner
allows the miner to claim all the funds), with little ability to
do a k-of-n multisig-like approach to prevent a single bad actor
from causing problems
- if the parameters that are actually activated are different to
what you assumed, then your script path might be unspendable
anyway; if different groups are proposing different parameters,
and only one gets activated, their funds are accessible while
everyone else's isn't
- Disabling key path taproot spends via soft-fork is extremely
confiscatory -- for the consensus cleanup, we worry about even the
possibility of destroying funds due to transaction patterns never
seen on the network; here, shutting down key path spends would be
knowingly destroying an enormous range of utxos.
- If you're avoiding the confiscatory approach by adding a hard-fork
in order to make keypath (and potentially ECDSA) funds accessible
to their owners via some post-quantum mechanism, then there's little
benefit to having an explicit script path method in advance.
- This approach probably isn't compatible with smart contracts,
particularly if pre-signed transactions are involved. Probably the
only way to deal with that is to hope you will have enough warning
to say "in X months, all your smart contracts are broken, so shut
them down now". There probably isn't any feasible way to do anything
better than that, though.
> (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.
I don't think this paragraph makes sense? In a post-quantum world,
a legitimate key-path spend could likely be replaced by an attacker
while it was sitting in the mempool, same as for a tx spending a p2pkh
or p2wpkh output. Also, a script-path isn't a point at all, so having
it be a NUMS point doesn't make much sense. Having it be unspendable
can make sense, and is already recommended in BIP 341 (search for
"unspendable"). Conditional key-path spends for taproot outputs is
probably most sensibly done as a hard fork; though it could be done as
a soft fork if the "condition" data was added somewhere other than in
the witness.
What about a different way of allowing wallets to pre-commit to a
post-quantum pubkey? eg, rather than generating a pubkey P directly from
an xprv/xpub and committing to a script path with their post-quantum
pubkey Q; wallets could generate the pubkey as R = P+H(P,Q)*G. At that
point, a hard-fork could be made to allow "R CHECKSIG" (or key path spends
where R is the sPK) to be satisfied via "<Qsig> <Q> <P>", validated
by checking that P+H(P,Q)*G=R, and that Qsig is a valid post-quantum
signature based on Q.
That retains many of the drawbacks above and is only useful if enabled
via a hard fork, however it removes these drawbacks:
- insiders can steal your funds if you adopt it prior to it becoming
consensus
- it marginally increases the size of non-post-quantum spends
- it breaks complicated scripts even without pre-signed transactions
Cheers,
aj
--
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/Z2ALlBGIyZLVbfVG%40erisian.com.au.
|
