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
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
|
Return-Path: <eth3rs@gmail.com>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133])
by lists.linuxfoundation.org (Postfix) with ESMTP id 277B7C000E
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 9 Jul 2021 23:25:46 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp2.osuosl.org (Postfix) with ESMTP id 08BB240272
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 9 Jul 2021 23:25:46 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.1
X-Spam-Level:
X-Spam-Status: No, score=-2.1 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001]
autolearn=ham autolearn_force=no
Authentication-Results: smtp2.osuosl.org (amavisd-new);
dkim=pass (2048-bit key) header.d=gmail.com
Received: from smtp2.osuosl.org ([127.0.0.1])
by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id 7JBX4UzQSTF3
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 9 Jul 2021 23:25:44 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-ed1-x52a.google.com (mail-ed1-x52a.google.com
[IPv6:2a00:1450:4864:20::52a])
by smtp2.osuosl.org (Postfix) with ESMTPS id 930B24015F
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 9 Jul 2021 23:25:44 +0000 (UTC)
Received: by mail-ed1-x52a.google.com with SMTP id v1so16197403edt.6
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 09 Jul 2021 16:25:44 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to
:cc:content-transfer-encoding;
bh=l85IvvPuO+YkTJgFMR1IBr/bZpDuegKDME/neQkVzEg=;
b=bqNa+T4L9XTdHtNczp4aOR5TpoRaD4xepZSGiBHV3UCEAOqkI4ZX9Rj01xCTD+SuYc
dZjDHI1xhvJYffYT0aJ/l8WSlPnbGpX0fiBRf+P+ErCsO/NvuTh2IaJkTz6CMQ94LlFP
dzqXXt5xO9d8a1xxACSUp5h3Ujczo7EVjadlBCVDlhJu6i/iazyQS933ggT+DPEq1SvJ
GWPtyD5WOKBraFDer0keiC/PZrP1wxAgiyLwQ4+6rdH7JrmvzMdRBbYpuDRdQa4Kkf5u
W4IJQcXCJLmv7+RBaOYdytTy7R6cCzNRY+y7YhrmM71C8Y4uJUDPNSDuud5kT+TENjUP
fTLA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:references:in-reply-to:from:date
:message-id:subject:to:cc:content-transfer-encoding;
bh=l85IvvPuO+YkTJgFMR1IBr/bZpDuegKDME/neQkVzEg=;
b=XQmT9So4xiNV8M6RIRm2n2dqGmpsjU9fXnz4evqdHY1FrLZ4WUNazRHX1Tr1uj1AAh
fI/sbsh+ekhX2f/PbutIEoYPTl0P7ADgqwG0VG8pokEOZk+jhQI1BFy5yyhijBbsjLwF
on1hPMfDJaa2YHGUNRuglPf03WTuZh7V/eBdltceQ4GzgBn5toN+4Y+RVrm8pxjpIC/S
8mThz6Lyq5hXczkI1PJ4eX0gePbj09tkwfL+QAvLVjtIfGS6khcdhwo6UJ5YJudGxqq4
VG+bjDroYvTFrPjU0XS/aHaGf2gCBH0WYuniB8KsUTBCaldPsgWwp7khOK+WcWvtmhgP
p8qg==
X-Gm-Message-State: AOAM532N4DL6KWyVlne9SkpCSGJrZlhifJgpZ5l/w4d/i3cRmw5M1qJ0
4KaxT2u7UNE5nbZnPldeME3Qt6kzs5kz4/9XOig=
X-Google-Smtp-Source: ABdhPJzJ/Cljtbd0QxiW8oRGisHjPgQxca1DKhRadbTGEBuDdZ6loWen3dIG/xfomBsKWIVTjRfRdjzvUsAEZt2iGGo=
X-Received: by 2002:a05:6402:18c4:: with SMTP id
x4mr21502231edy.350.1625873142745;
Fri, 09 Jul 2021 16:25:42 -0700 (PDT)
MIME-Version: 1.0
References: <CAD5xwhgzR8e5r1e4H-5EH2mSsE1V39dd06+TgYniFnXFSBqLxw@mail.gmail.com>
<MAfz2o3-uf5SfGKfMwONmT4TH4cmcAEJGyx21_dRQWBuCZZzFSXg38xyRY7HiMYMFB5zuTPorf_LYrnjE2K__uP578h7MZypf68yM0xjU3w=@protonmail.com>
<CAEM=y+WkG9razw6uEhkXtNCgonaw2GHp9oGB3J7uf9N_JVdPoQ@mail.gmail.com>
<XFMgrCKhdCuJ7LJ2KLv-r8dAGNs89H3NkvZgio5X6evKQ506p54HUF0hyxq0kQ48QeNJzmc--fy5keaSrzUQ7ylteCxe9TJNXnqJvaDy_X4=@protonmail.com>
In-Reply-To: <XFMgrCKhdCuJ7LJ2KLv-r8dAGNs89H3NkvZgio5X6evKQ506p54HUF0hyxq0kQ48QeNJzmc--fy5keaSrzUQ7ylteCxe9TJNXnqJvaDy_X4=@protonmail.com>
From: Ethan Heilman <eth3rs@gmail.com>
Date: Fri, 9 Jul 2021 19:25:06 -0400
Message-ID: <CAEM=y+U4EsS+gLyEqtxkG-8pEDtmMV8NEug5uQ_q0niwDHmkEw@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was
CheckSigFromStack for Arithmetic Values]
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Fri, 09 Jul 2021 23:25:46 -0000
>To implement Winternitz we need some kind of limited-repeat construct, whi=
ch is not available in SCRIPT, but may be emulatable with enough `OP_IF` an=
d sheer brute force.
But what you gain in smaller signatures, you lose in a more complex
and longer SCRIPT, and there are limits to SCRIPT size (in order to
limit the processing done in each node).
Using depth 4 Winternitz would increase the number of instructions in
SCRIPT by 4*(signature bits/2) instructions, but decrease the
signature size by (signature bits/2) hash preimages. Given that
instructions are significantly smaller in size than the hash preimages
used, it seems like this would significantly reduce total size.
>Merkle signatures trade off shorter pubkeys for longer signatures (signatu=
res need to provide the hash of the *other* preimage you are not revealing)=
, but in the modern post-SegWit Bitcoin context both pubkeys and signatures=
are stored in the witness area, which have the same weight, thus it is act=
ually a loss compared to Lamport.
I wasn't proposing using plain merkle signatures, rather I was
thinking about something where if particular chunks of the message fit
a pattern you could release a seed higher in the commitment tree. For
instance 1,1,1 could be signed as by releasing H(01||H(01||H(01||x))),
H(11||H(11||H(11||x))), H(21||H(21||H(21||x))), or by releasing X.
However, you would want to only release X in that one specific case
(1,1,1) but no others. Again this would bloat the SCRIPT and decrease
signature size but at a favorable ratio.
I am not convinced anyone should do these things, but they are fun to
think about and I suspect with more thought such signature sizes and
SCRIPT sizes could be even further reduced.
On Fri, Jul 9, 2021 at 6:38 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
>
> Good morning Ethan,
>
> > > Yes, quite neat indeed, too bad Lamport signatures are so huge (a cou=
ple kilobytes)... blocksize increase cough
> >
> > Couldn't you significantly compress the signatures by using either
> > Winternitz OTS or by using OP_CAT to build a merkle tree so that the
> > full signature can be derived during script execution from a much
> > shorter set of seed values?
>
> To implement Winternitz we need some kind of limited-repeat construct, wh=
ich is not available in SCRIPT, but may be emulatable with enough `OP_IF` a=
nd sheer brute force.
> But what you gain in smaller signatures, you lose in a more complex and l=
onger SCRIPT, and there are limits to SCRIPT size (in order to limit the pr=
ocessing done in each node).
>
> Merkle signatures trade off shorter pubkeys for longer signatures (signat=
ures need to provide the hash of the *other* preimage you are not revealing=
), but in the modern post-SegWit Bitcoin context both pubkeys and signature=
s are stored in the witness area, which have the same weight, thus it is ac=
tually a loss compared to Lamport.
>
>
> So yes, maybe Winternitz (could be a replacement for the "trinary" Jeremy=
refers to), Merkle not so much.
>
> Regards,
> ZmnSCPxj
>
> > On Thu, Jul 8, 2021 at 4:12 AM ZmnSCPxj via bitcoin-dev
> > bitcoin-dev@lists.linuxfoundation.org wrote:
> >
> > > Good morning Jeremy,
> > > Yes, quite neat indeed, too bad Lamport signatures are so huge (a cou=
ple kilobytes)... blocksize increase cough
> > > Since a quantum computer can derive the EC privkey from the EC pubkey=
and this scheme is resistant to that, I think you can use a single well-kn=
own EC privkey, you just need a unique Lamport keypair for each UTXO (uniqu=
eness being mandatory due to Lamport requiring preimage revelation).
> > > Regards,
> > > ZmnSCPxj
> > >
> > > > Dear Bitcoin Devs,
> > > > As mentioned previously, OP_CAT (or similar operation) can be used =
to make Bitcoin "quantum safe" by signing an EC signature. This should work=
in both Segwit V0 and Tapscript, although you have to use HASH160 for it t=
o fit in Segwit V0.
> > > > See my blog for the specific construction, reproduced below.
> > > > Yet another entry to the "OP_CAT can do that too" list.
> > > > Best,
> > > >
> > > > Jeremy
> > > >
> > > > -------
> > > >
> > > > I recently published a blogpost about signing up to a5 byte value u=
sing Bitcoin script arithmetic and Lamport signatures.
> > > > By itself, this is neat, but a little limited. What if we could sig=
n longer
> > > > messages? If we can sign up to 20 bytes, we could sign a HASH160 di=
gest which
> > > > is most likely quantum safe...
> > > > What would it mean if we signed the HASH160 digest of a signature? =
What the
> > > > what? Why would we do that?
> > > > Well, as it turns out, even if a quantum computer were able to crac=
k ECDSA, it
> > > > would yield revealing the private key but not the ability to mallea=
te the
> > > > content of what was actually signed. I asked my good friend and cry=
ptographer
> > > > Madars Virza if my intuition was correct, and he
> > > > confirmed that it should be sufficient, but it's definitely worth c=
loser
> > > > analysis before relying on this. While the ECDSA signature can be m=
alleated to a
> > > > different, negative form, if the signature is otherwise made immall=
eable there
> > > > should only be one value the commitment can be opened to.
> > > > If we required the ECDSA signature be signed with a quantum proof s=
ignature
> > > > algorithm, then we'd have a quantum proof Bitcoin! And the 5 byte s=
igning scheme
> > > > we discussed previously is a Lamport signature, which is quantum se=
cure.
> > > > Unfortunately, we need at least 20 contiguous bytes... so we need s=
ome sort of
> > > > OP\_CAT like operation.
> > > > OP\_CAT can't be directly soft forked to Segwit v0 because it modif=
ies the
> > > > stack, so instead we'll (for simplicity) also show how to use a new=
opcode that
> > > > uses verify semantics, OP\_SUBSTRINGEQUALVERIFY that checks a splic=
e of a string
> > > > for equality.
> > > >
> > > > ... FOR j in 0..=3D5
> > > > <0>
> > > > ... FOR i in 0..=3D31
> > > > SWAP hash160 DUP <H(K_j_i_1)> EQUAL IF DROP <2**i> ADD =
ELSE <H(K_j_i_0)> EQUALVERIFY ENDIF
> > > > ... END FOR
> > > > TOALTSTACK
> > > > ... END FOR
> > > >
> > > > DUP HASH160
> > > >
> > > > ... IF CAT AVAILABLE
> > > > FROMALTSTACK
> > > > ... FOR j in 0..=3D5
> > > > FROMALTSTACK
> > > > CAT
> > > > ... END FOR
> > > > EQUALVERIFY
> > > > ... ELSE SUBSTRINGEQUALVERIFY AVAILABLE
> > > > ... FOR j in 0..=3D5
> > > > FROMALTSTACK <0+j*4> <4+j*4> SUBSTRINGEQUALVERIFY DROP =
DROP DROP
> > > > ... END FOR
> > > > DROP
> > > > ... END IF
> > > >
> > > > <pk> CHECKSIG
> > > >
> > > >
> > > > That's a long script... but will it fit? We need to verify 20 bytes=
of message
> > > > each bit takes around 10 bytes script, an average of 3.375 bytes pe=
r number
> > > > (counting pushes), and two 21 bytes keys =3D 55.375 bytes of progra=
m space and 21
> > > > bytes of witness element per bit.
> > > > It fits! `20*8*55.375 =3D 8860`, which leaves 1140 bytes less than =
the limit for
> > > > the rest of the logic, which is plenty (around 15-40 bytes required=
for the rest
> > > > of the logic, leaving 1100 free for custom signature checking). The=
stack size
> > > > is 160 elements for the hash gadget, 3360 bytes.
> > > > This can probably be made a bit more efficient by expanding to a te=
rnary
> > > > representation.
> > > >
> > > > SWAP hash160 DUP <H(K_j_i_0)> EQUAL IF DROP ELSE <3**=
i> SWAP DUP <H(K_j_i_T)> EQUAL IF DROP SUB ELSE <H(K_j_i_1)> EQUALVERIFY AD=
D ENDIF ENDIF
> > > >
> > > >
> > > > This should bring it up to roughly 85 bytes per trit, and there sho=
uld be 101
> > > > trits (`log(2**160)/log(3) =3D=3D 100.94`), so about 8560 bytes... =
a bit cheaper!
> > > > But the witness stack is "only" `2121` bytes...
> > > > As a homework exercise, maybe someone can prove the optimal choice =
of radix for
> > > > this protocol... My guess is that base 4 is optimal!
> > > >
> > > > Taproot?
> > > >
> > > > ---------
> > > >
> > > > What about Taproot? As far as I'm aware the commitment scheme (`Q =
=3D pG + hash(pG || m)G`) can be securely opened to m even with a quantum c=
omputer (finding `q`
> > > > such that `qG =3D Q` might be trivial, but suppose key path was dis=
abled, then
> > > > finding m and p such that the taproot equation holds should be diff=
icult because
> > > > of the hash, but I'd need to certify that claim better). Therefore =
this
> > > > script can nest inside of a Tapscript path -- Tapscript also does n=
ot impose a
> > > > length limit, 32 byte hashes could be used as well.
> > > > Further, to make keys reusable, there could be many Lamport keys co=
mitted inside
> > > > a taproot tree so that an address could be used for thousands of ti=
mes before
> > > > expiring. This could be used as a measure to protect accidental use=
rather than
> > > > to support it.
> > > > Lastly, Schnorr actually has a stronger non-malleability property t=
han ECDSA,
> > > > the signatures will be binding to the approved transaction and once=
Lamport
> > > > signed, even a quantum computer could not steal the funds.
> > > > --
> > > > @JeremyRubin
> > >
> > > bitcoin-dev mailing list
> > > bitcoin-dev@lists.linuxfoundation.org
> > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
|