summaryrefslogtreecommitdiff
path: root/e5/3ea258ad6b5b6df88481d92863d7514b68e97f
blob: 3a5259cc0bb2755bb56bb3c570631869240c7fd5 (plain)
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
Return-Path: <ZmnSCPxj@protonmail.com>
Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 8B772C000E
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  8 Jul 2021 08:12:13 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp1.osuosl.org (Postfix) with ESMTP id 7384083104
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  8 Jul 2021 08:12:13 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: 0.4
X-Spam-Level: 
X-Spam-Status: No, score=0.4 tagged_above=-999 required=5
 tests=[BAYES_20=-0.001, 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_H4=0.001,
 RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001,
 URIBL_SBL_A=0.1] autolearn=ham autolearn_force=no
Authentication-Results: smtp1.osuosl.org (amavisd-new);
 dkim=pass (1024-bit key) header.d=protonmail.com
Received: from smtp1.osuosl.org ([127.0.0.1])
 by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id mMb8ZcgsdojT
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  8 Jul 2021 08:12:10 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0
Received: from mail-4324.protonmail.ch (mail-4324.protonmail.ch [185.70.43.24])
 by smtp1.osuosl.org (Postfix) with ESMTPS id D45F382F6F
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  8 Jul 2021 08:12:09 +0000 (UTC)
Date: Thu, 08 Jul 2021 08:12:01 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com;
 s=protonmail; t=1625731926;
 bh=LqyRtd/90F1VNDq832MSuVP5f968NbeoRR4FEM4X610=;
 h=Date:To:From:Reply-To:Subject:In-Reply-To:References:From;
 b=j7moGfRymXOMhpYHucrXZe4O86WKSG3f1qwFWN5e6FGDdiwEXuN6N1m7GHi9tc6hY
 3PRd4hmkCRTygZBtR+vP7K/E4vlX4EX7L8NpVkMRhQnhZrg68t5eXay/JKCCvYBgGd
 2sCuRIlTrlRSGmVxH447ra5PaYkALMak6qHJZV+4=
To: Jeremy <jlrubin@mit.edu>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <MAfz2o3-uf5SfGKfMwONmT4TH4cmcAEJGyx21_dRQWBuCZZzFSXg38xyRY7HiMYMFB5zuTPorf_LYrnjE2K__uP578h7MZypf68yM0xjU3w=@protonmail.com>
In-Reply-To: <CAD5xwhgzR8e5r1e4H-5EH2mSsE1V39dd06+TgYniFnXFSBqLxw@mail.gmail.com>
References: <CAD5xwhgzR8e5r1e4H-5EH2mSsE1V39dd06+TgYniFnXFSBqLxw@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
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: Thu, 08 Jul 2021 08:12:13 -0000


Good morning Jeremy,

Yes, quite neat indeed, too bad Lamport signatures are so huge (a couple ki=
lobytes)... blocksize increase *cough*

Since a quantum computer can derive the EC privkey from the EC pubkey and t=
his scheme is resistant to that, I think you can use a single well-known EC=
 privkey, you just need a unique Lamport keypair for each UTXO (uniqueness =
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 mak=
e Bitcoin "quantum safe" by signing an EC signature. This should work in bo=
th Segwit V0 and Tapscript, although you have to use HASH160 for it to fit =
in Segwit V0.
>
> See [my blog](https://rubin.io/blog/2021/07/06/quantum-bitcoin/) for the =
specific construction, reproduced below.
>
> Yet another entry to the "OP_CAT can do that too" list.
>
> Best,
>
> Jeremy
> -----
>
> I recently published [a blog
> post](https://rubin.io/blog/2021/07/02/signing-5-bytes/) about signing up=
 to a
> 5 byte value using Bitcoin script arithmetic and Lamport signatures.
>
> By itself, this is neat, but a little limited. What if we could sign long=
er
> messages? If we can sign up to 20 bytes, we could sign a HASH160 digest w=
hich
> is most likely quantum safe...
>
> What would it mean if we signed the HASH160 digest of a signature? What t=
he
> what? Why would we do that?
>
> Well, as it turns out, even if a quantum computer were able to crack ECDS=
A, it
> would yield revealing the private key but not the ability to malleate the
> content of what was actually signed.=C2=A0 I asked my good friend and cry=
ptographer
> [Madars Virza](https://madars.org/) if my intuition was correct, and he
> confirmed that it should be sufficient, but it's definitely worth closer
> analysis before relying on this. While the ECDSA signature can be malleat=
ed to a
> different, negative form, if the signature is otherwise made immalleable =
there
> should only be one value the commitment can be opened to.
>
> If we required the ECDSA signature be signed with a quantum proof signatu=
re
> algorithm, then we'd have a quantum proof Bitcoin! And the 5 byte signing=
 scheme
> we discussed previously is a Lamport signature, which is quantum secure.
> Unfortunately, we need at least 20 contiguous bytes... so we need some so=
rt of
> OP\_CAT like operation.
>
> OP\_CAT can't be directly soft forked to Segwit v0 because it modifies th=
e
> stack, so instead we'll (for simplicity) also show how to use a new opcod=
e that
> uses verify semantics, OP\_SUBSTRINGEQUALVERIFY that checks a splice of a=
 string
> for equality.
>
> ```
> ... FOR j in 0..=3D5
> =C2=A0 =C2=A0 <0>
> =C2=A0 =C2=A0 ... FOR i in 0..=3D31
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 SWAP hash160 DUP <H(K_j_i_1)> EQUAL IF DROP <=
2**i> ADD ELSE <H(K_j_i_0)> EQUALVERIFY ENDIF
> =C2=A0 =C2=A0 ... END FOR
> =C2=A0 =C2=A0 TOALTSTACK
> ... END FOR
>
> DUP HASH160
>
> ... IF CAT AVAILABLE
> =C2=A0 =C2=A0 FROMALTSTACK
> =C2=A0 =C2=A0 ... FOR j in 0..=3D5
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 FROMALTSTACK
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 CAT
> =C2=A0 =C2=A0 ... END FOR
> =C2=A0 =C2=A0 EQUALVERIFY
> ... ELSE SUBSTRINGEQUALVERIFY AVAILABLE
> =C2=A0 =C2=A0 ... FOR j in 0..=3D5
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 FROMALTSTACK <0+j*4> <4+j*4> SUBSTRINGEQUALVE=
RIFY DROP DROP DROP
> =C2=A0 =C2=A0 ...=C2=A0 END FOR
> =C2=A0 =C2=A0 DROP
> ... END IF
>
> <pk> CHECKSIG
> ```
>
> That's a long script... but will it fit? We need to verify 20 bytes of me=
ssage
> each bit takes around 10 bytes script, an average of 3.375 bytes per numb=
er
> (counting pushes), and two 21 bytes keys =3D 55.375 bytes of program spac=
e and 21
> bytes of witness element per bit.
>
> It fits! `20*8*55.375 =3D 8860`, which leaves 1140 bytes less than the li=
mit for
> the rest of the logic, which is plenty (around 15-40 bytes required for t=
he 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 ternary
> representation.
>
> ```
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 SWAP hash160 DUP <H(K_j_i_0)> EQUAL =C2=A0IF =
DROP =C2=A0ELSE <3**i> SWAP DUP <H(K_j_i_T)> EQUAL IF DROP SUB ELSE <H(K_j_=
i_1)> EQUALVERIFY ADD =C2=A0ENDIF ENDIF
> ```
>
> This should bring it up to roughly 85 bytes per trit, and there should 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 rad=
ix 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 computer (findin=
g `q`
> such that `qG =3D Q` might be trivial, but suppose key path was disabled,=
 then
> finding m and p such that the taproot equation holds should be difficult =
because
> of the hash, but I'd need to certify that claim better).=C2=A0 Therefore =
this
> script can nest inside of a Tapscript path -- Tapscript also does not imp=
ose a
> length limit, 32 byte hashes could be used as well.
>
> Further, to make keys reusable, there could be many Lamport keys comitted=
 inside
> a taproot tree so that an address could be used for thousands of times be=
fore
> expiring. This could be used as a measure to protect accidental use rathe=
r than
> to support it.
>
> Lastly, Schnorr actually has a stronger non-malleability property than EC=
DSA,
> the signatures will be binding to the approved transaction and once Lampo=
rt
> signed, even a quantum computer could not steal the funds.
>
> --
> @JeremyRubin