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
|
Return-Path: <ZmnSCPxj@protonmail.com>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137])
by lists.linuxfoundation.org (Postfix) with ESMTP id C06BFC000E
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 9 Jul 2021 22:38:34 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp4.osuosl.org (Postfix) with ESMTP id AEC544014C
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 9 Jul 2021 22:38:34 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.599
X-Spam-Level:
X-Spam-Status: No, score=-1.599 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,
FROM_LOCAL_NOVOWEL=0.5, RCVD_IN_MSPIKE_H3=0.001,
RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001]
autolearn=ham autolearn_force=no
Authentication-Results: smtp4.osuosl.org (amavisd-new);
dkim=pass (1024-bit key) header.d=protonmail.com
Received: from smtp4.osuosl.org ([127.0.0.1])
by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id EPCOyoEDPotm
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 9 Jul 2021 22:38:32 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0
Received: from mail-4318.protonmail.ch (mail-4318.protonmail.ch [185.70.43.18])
by smtp4.osuosl.org (Postfix) with ESMTPS id 9AA6140443
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 9 Jul 2021 22:38:32 +0000 (UTC)
Date: Fri, 09 Jul 2021 22:38:18 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com;
s=protonmail; t=1625870309;
bh=X0HtAW+uNZuNGwL3cmBzaVtsxk0Nk8fboAS8nTh0qoY=;
h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References:From;
b=CWJ77NLfNKvNUuSw2B5DinaGbkOcc9/0U1/Qm48hW1M5fDZv3I6wYCA/MaclrFz3Y
1CmNSxuj9vClgVvZtyiRgft6eVp2cW7CMFNo7v9ERtM0jftW8SINt8TrfoxoclLRMs
OW5n7UXYnmTSrrw//dTMZj3n6DKo4HWKd2CylJS0=
To: Ethan Heilman <eth3rs@gmail.com>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <XFMgrCKhdCuJ7LJ2KLv-r8dAGNs89H3NkvZgio5X6evKQ506p54HUF0hyxq0kQ48QeNJzmc--fy5keaSrzUQ7ylteCxe9TJNXnqJvaDy_X4=@protonmail.com>
In-Reply-To: <CAEM=y+WkG9razw6uEhkXtNCgonaw2GHp9oGB3J7uf9N_JVdPoQ@mail.gmail.com>
References: <CAD5xwhgzR8e5r1e4H-5EH2mSsE1V39dd06+TgYniFnXFSBqLxw@mail.gmail.com>
<MAfz2o3-uf5SfGKfMwONmT4TH4cmcAEJGyx21_dRQWBuCZZzFSXg38xyRY7HiMYMFB5zuTPorf_LYrnjE2K__uP578h7MZypf68yM0xjU3w=@protonmail.com>
<CAEM=y+WkG9razw6uEhkXtNCgonaw2GHp9oGB3J7uf9N_JVdPoQ@mail.gmail.com>
MIME-Version: 1.0
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 22:38:34 -0000
Good morning Ethan,
> > Yes, quite neat indeed, too bad Lamport signatures are so huge (a coupl=
e 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, whic=
h is not available in SCRIPT, but may be emulatable with enough `OP_IF` and=
sheer brute force.
But what you gain in smaller signatures, you lose in a more complex and lon=
ger SCRIPT, and there are limits to SCRIPT size (in order to limit the proc=
essing done in each node).
Merkle signatures trade off shorter pubkeys for longer signatures (signatur=
es 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 actu=
ally a loss compared to Lamport.
So yes, maybe Winternitz (could be a replacement for the "trinary" Jeremy r=
efers 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 coupl=
e kilobytes)... blocksize increase cough
> > Since a quantum computer can derive the EC privkey from the EC pubkey a=
nd this scheme is resistant to that, I think you can use a single well-know=
n EC privkey, you just need a unique Lamport keypair for each UTXO (uniquen=
ess 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 i=
n both Segwit V0 and Tapscript, although you have to use HASH160 for it to =
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 usi=
ng Bitcoin script arithmetic and Lamport signatures.
> > > By itself, this is neat, but a little limited. What if we could sign =
longer
> > > messages? If we can sign up to 20 bytes, we could sign a HASH160 dige=
st which
> > > is most likely quantum safe...
> > > What would it mean if we signed the HASH160 digest of a signature? Wh=
at the
> > > what? Why would we do that?
> > > Well, as it turns out, even if a quantum computer were able to crack =
ECDSA, it
> > > would yield revealing the private key but not the ability to malleate=
the
> > > content of what was actually signed. I asked my good friend and crypt=
ographer
> > > Madars Virza if my intuition was correct, and he
> > > confirmed that it should be sufficient, but it's definitely worth clo=
ser
> > > analysis before relying on this. While the ECDSA signature can be mal=
leated to a
> > > different, negative form, if the signature is otherwise made immallea=
ble there
> > > should only be one value the commitment can be opened to.
> > > If we required the ECDSA signature be signed with a quantum proof sig=
nature
> > > algorithm, then we'd have a quantum proof Bitcoin! And the 5 byte sig=
ning scheme
> > > we discussed previously is a Lamport signature, which is quantum secu=
re.
> > > Unfortunately, we need at least 20 contiguous bytes... so we need som=
e sort of
> > > OP\_CAT like operation.
> > > OP\_CAT can't be directly soft forked to Segwit v0 because it modifie=
s the
> > > stack, so instead we'll (for simplicity) also show how to use a new o=
pcode that
> > > uses verify semantics, OP\_SUBSTRINGEQUALVERIFY that checks a splice =
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 EL=
SE <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 DR=
OP DROP
> > > ... END FOR
> > > DROP
> > > ... END IF
> > >
> > > <pk> CHECKSIG
> > >
> > >
> > > That's a long script... but will it fit? We need to verify 20 bytes o=
f message
> > > each bit takes around 10 bytes script, an average of 3.375 bytes per =
number
> > > (counting pushes), and two 21 bytes keys =3D 55.375 bytes of program =
space and 21
> > > bytes of witness element per bit.
> > > It fits! `20*8*55.375 =3D 8860`, which leaves 1140 bytes less than th=
e limit for
> > > the rest of the logic, which is plenty (around 15-40 bytes required f=
or the rest
> > > of the logic, leaving 1100 free for custom signature checking). The s=
tack size
> > > is 160 elements for the hash gadget, 3360 bytes.
> > > This can probably be made a bit more efficient by expanding to a tern=
ary
> > > 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 ADD =
ENDIF ENDIF
> > >
> > >
> > > This should bring it up to roughly 85 bytes per trit, and there shoul=
d 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 comp=
uter (finding `q`
> > > such that `qG =3D Q` might be trivial, but suppose key path was disab=
led, then
> > > finding m and p such that the taproot equation holds should be diffic=
ult because
> > > of the hash, but I'd need to certify that claim better). Therefore th=
is
> > > script can nest inside of a Tapscript path -- Tapscript also does not=
impose a
> > > length limit, 32 byte hashes could be used as well.
> > > Further, to make keys reusable, there could be many Lamport keys comi=
tted inside
> > > a taproot tree so that an address could be used for thousands of time=
s before
> > > expiring. This could be used as a measure to protect accidental use r=
ather than
> > > to support it.
> > > Lastly, Schnorr actually has a stronger non-malleability property tha=
n ECDSA,
> > > the signatures will be binding to the approved transaction and once L=
amport
> > > 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
|
