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
|
Delivery-date: Wed, 08 May 2024 17:37:26 -0700
Received: from mail-yb1-f185.google.com ([209.85.219.185])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBDAOTO4QXEFBBPVV6CYQMGQESI5DXTA@googlegroups.com>)
id 1s4rmo-0001d3-2R
for bitcoindev@gnusha.org; Wed, 08 May 2024 17:37:26 -0700
Received: by mail-yb1-f185.google.com with SMTP id 3f1490d57ef6-de468af2b73sf622041276.0
for <bitcoindev@gnusha.org>; Wed, 08 May 2024 17:37:25 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1715215039; x=1715819839; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-sender:mime-version
:subject:references:in-reply-to:message-id:to:from:date:sender:from
:to:cc:subject:date:message-id:reply-to;
bh=kti8PQ1sH0PD5vZh1UeacUZlgebA3UoNsfs3+kVOvFI=;
b=SOmARHTKYXkIHJ8sQbcED9bvmO1LExQfXWOfN+wKBktE7FqXu9v+Og2Bhs+t1bXPB/
9JYyi/1Ts5V8sAD0Mq2c+sD3/bz5qtsrhwR550yGjft8ANC1EZNYdBFToMOZr57A4UUA
9Y/+9Pk6ZvQCe5wXBd3GQ7PzBU3tfz72kDRAdvbFSNO4zbv0mtewiLY6ifY7iHUXjnQv
sJ8ZO8A9f3UZBtBi+JZrISxR9BbO00YKwOQDUTRY2PhJxMBuz8sPN0EixAwBT0wxZhqK
yRd8BHVemJHyORZf5O6qddS0Q0XEgfGjJoDe7CkLnx1911AMw4jCw92QhvROu/f4pLJh
g81A==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=gmail.com; s=20230601; t=1715215039; x=1715819839; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-sender:mime-version
:subject:references:in-reply-to:message-id:to:from:date:from:to:cc
:subject:date:message-id:reply-to;
bh=kti8PQ1sH0PD5vZh1UeacUZlgebA3UoNsfs3+kVOvFI=;
b=JKYzj3J+sMMwuAAkaY/jHyQZ6RqlXBoKBZCBHDShqylLxRgw+GAHW23Y4/GiDeETW4
MZlknjng67tajJiCKI8SQMrfov+AqtAhwMLfinIGjIypMnObrC54viR7x1fDI+5+bhpF
I7XRToGknWLDERYoCDu0orgiyBX67Fp3/fdTJ8ow3dmKMjNIJWEq9tZc8bpLFTk+N7TB
EQw1aX4L6ZR6HxIKlA17WxuUP9QJYKwcoMQkeaZOaosQDBqIBZDo6//oCClXgpmcgiVw
jftoERy38suYUnfxM5qZX83igdbFaHEzdFZI8L4z7o5+RHzqh901YexVHA6ZuwGDaLAh
WgJg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1715215039; x=1715819839;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-sender:mime-version
:subject:references:in-reply-to:message-id:to:from:date:x-beenthere
:x-gm-message-state:sender:from:to:cc:subject:date:message-id
:reply-to;
bh=kti8PQ1sH0PD5vZh1UeacUZlgebA3UoNsfs3+kVOvFI=;
b=Z0rGERyOg4L5s7y8tC666fj091jyh2MSfUweDYgnabfeUu3fbePVh/a6G1O1/q6mAQ
SgT78ATmsum3OtmCsimhyOw43BSTSmQdySDBd655IOfwnJbNKdZYLvCPLd/qYEgS1rOF
9MS23jerAt3z3Pk6C+Sni35d3wdxM5oszJY+yAEjJVa2BNX1RIOuVZQE0mFXYT94IRyw
0mLpMNAz3bsIHAAep4J4fYBMd2JS7H6l8BdbyYOVaI/40eEjHIyDafekfeFWg/8ZW6jO
BIQEN7iVYf7A6bGwet33V65C34C2BuVBGbaCyWh/qFm6SIj2GpSH4hqxAUBsRc+HiXwu
Uw+g==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCV0ooCdMO392dCNVvXlU4tqR/vDiSzzYnRp10PhjLXJwiahY2mKw7JEE6UKyrDaMo9EBgtHjP7Yep6sMbfSdd/PYZKN8qU=
X-Gm-Message-State: AOJu0Yz+6nxs2gYDvEF3kscreLXZtNZY++CyBF1n2jNOjRzl4h4cx0zU
Ztf0nMJ5f2ujQzvHigxA1IuPqrryVyIBKzndw93CJZa7bf3A8oV/
X-Google-Smtp-Source: AGHT+IGk6e3Oh9eIZ57wWxvcEdrXmn3hAMx9WsiH6RrmCzEbXDhQs6xr9Q8sddToq65Ztkds4hxZMw==
X-Received: by 2002:a25:cec7:0:b0:de6:17aa:e711 with SMTP id 3f1490d57ef6-debb9cde0d6mr5572260276.7.1715215039552;
Wed, 08 May 2024 17:37:19 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a25:ad45:0:b0:de5:a88f:94bd with SMTP id 3f1490d57ef6-debd087c4afls530768276.1.-pod-prod-08-us;
Wed, 08 May 2024 17:37:17 -0700 (PDT)
X-Received: by 2002:a25:9e11:0:b0:de5:1b63:9ee5 with SMTP id 3f1490d57ef6-debb9da66d2mr1211632276.7.1715215037830;
Wed, 08 May 2024 17:37:17 -0700 (PDT)
Received: by 2002:a05:690c:dcf:b0:620:26bb:319f with SMTP id 00721157ae682-62086722468ms7b3;
Wed, 8 May 2024 17:31:19 -0700 (PDT)
X-Received: by 2002:a0d:e2cb:0:b0:61a:f3ea:3994 with SMTP id 00721157ae682-620993b8121mr3099657b3.3.1715214678624;
Wed, 08 May 2024 17:31:18 -0700 (PDT)
Date: Wed, 8 May 2024 17:31:18 -0700 (PDT)
From: Ben Carman <benthecarman1@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <b50b6b09-4d13-46ab-9776-f6b8a02aa2e0n@googlegroups.com>
In-Reply-To: <ZjD-dMMGxoGNgzIg@camus>
References: <CAEM=y+XyW8wNOekw13C5jDMzQ-dOJpQrBC+qR8-uDot25tM=XA@mail.gmail.com>
<CA+x5asTOTai_4yNGEgtKEqAchuWJ0jGDEgMqHFYDwactPnrgyw@mail.gmail.com>
<ZjD-dMMGxoGNgzIg@camus>
Subject: Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport
Signatures (no changes needed)
MIME-Version: 1.0
Content-Type: multipart/mixed;
boundary="----=_Part_85989_269653429.1715214678205"
X-Original-Sender: benthecarman1@gmail.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.5 (/)
------=_Part_85989_269653429.1715214678205
Content-Type: multipart/alternative;
boundary="----=_Part_85990_406851706.1715214678205"
------=_Part_85990_406851706.1715214678205
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
I think it is possible to get past the 201 op code limit doing it in=20
tapscript. I don't think it would have the same quantum security but could=
=20
maybe be a path to covenants. My understanding is that you're using the=20
OP_SIZE of the sig to basically decide to verify if the bit is a 0 or a 1,=
=20
then do that verification. You could do the same trick with schnorr sigs,=
=20
just for 0 bits don't include the sighash_all flag, and for 1 bits include=
=20
it. This would allow you to get around all the resource limits that taproot=
=20
lifted. This still should be safe since the the signature commits to if it=
=20
is SIGHASH_DEFAULT vs SIGHASH_ALL. I am not sure if this will enable very=
=20
complex things or just let you do it on 1 bit of information in tapscript.
Best,
benthecarman
On Tuesday, April 30, 2024 at 9:22:54=E2=80=AFAM UTC-5 Andrew Poelstra wrot=
e:
> On Tue, Apr 30, 2024 at 08:32:42AM -0400, Matthew Zipkin wrote:
> > > if an attacker managed to grind a 23-byte r-value at a cost of 2^72
> > computations, it would provide the attacker some advantage.
> >=20
> > If we are assuming discrete log is still hard, why do we need Lamport
> > signatures at all? In a post-quantum world, finding k such that r is 21
> > bytes or less is efficient for the attacker.
> >
>
> Aside from Ethan's point that a variant of this technique is still
> secure in the case that discrete log is totally broken (or even
> partially broken...all we need is that _somebody_ is able to find the
> discrete log of the x=3D1 point and for them to publish this).
>
> Another reason this is useful is that if you have a Lamport signature on
> the stack which is composed of SIZE values, all of which are small
> enough to be manipulated with the numeric script opcodes, then you can
> do covenants in Script.
>
> (Sadly(?), I think none of this works in the context of the 201-opcode
> limit...and absent BitVM challenge-response tricks it's unlikely you can
> do much in the context of the 4MWu block size limit..), but IMO it's a
> pretty big deal that size limits are now the only reason that Bitcoin
> doesn't have covenants.)
>
> --=20
> Andrew Poelstra
> Director, Blockstream Research
> Email: apoelstra at wpsoftware.net
> Web: https://www.wpsoftware.net/andrew
>
> The sun is always shining in space
> -Justin Lewis-Webster
>
>
--=20
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 e=
mail to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/=
bitcoindev/b50b6b09-4d13-46ab-9776-f6b8a02aa2e0n%40googlegroups.com.
------=_Part_85990_406851706.1715214678205
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div>I think it is possible to get past the 201 op code limit doing it in t=
apscript. <span style=3D"text-overflow: unset;">I don't think it would have=
the same quantum security but could maybe be a path to covenants. My unde=
rstanding is that you're using the OP_SIZE of the sig to basically decide t=
o verify if the bit is a 0 or a 1, then do that verification. You could do =
the same trick with schnorr sigs, just for 0 bits don't include the sighash=
_all flag, and for 1 bits include it.
This would allow you to get around all the resource limits that taproot lif=
te</span>d. This still should be safe since the the signature commits to if=
it is SIGHASH_DEFAULT vs SIGHASH_ALL. I am not sure if this will enable ve=
ry complex things or just let you do it on 1 bit of information in tapscrip=
t.</div><div><br /></div><div>Best,</div><div>benthecarman<br /></div><div>=
<br /></div><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_att=
r">On Tuesday, April 30, 2024 at 9:22:54=E2=80=AFAM UTC-5 Andrew Poelstra w=
rote:<br/></div><blockquote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.=
8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">On Tue,=
Apr 30, 2024 at 08:32:42AM -0400, Matthew Zipkin wrote:
<br>> > if an attacker managed to grind a 23-byte r-value at a cost o=
f 2^72
<br>> computations, it would provide the attacker some advantage.
<br>>=20
<br>> If we are assuming discrete log is still hard, why do we need Lamp=
ort
<br>> signatures at all? In a post-quantum world, finding k such that r =
is 21
<br>> bytes or less is efficient for the attacker.
<br>>
<br>
<br>Aside from Ethan's point that a variant of this technique is still
<br>secure in the case that discrete log is totally broken (or even
<br>partially broken...all we need is that _somebody_ is able to find the
<br>discrete log of the x=3D1 point and for them to publish this).
<br>
<br>Another reason this is useful is that if you have a Lamport signature o=
n
<br>the stack which is composed of SIZE values, all of which are small
<br>enough to be manipulated with the numeric script opcodes, then you can
<br>do covenants in Script.
<br>
<br>(Sadly(?), I think none of this works in the context of the 201-opcode
<br>limit...and absent BitVM challenge-response tricks it's unlikely yo=
u can
<br>do much in the context of the 4MWu block size limit..), but IMO it'=
s a
<br>pretty big deal that size limits are now the only reason that Bitcoin
<br>doesn't have covenants.)
<br>
<br>--=20
<br>Andrew Poelstra
<br>Director, Blockstream Research
<br>Email: apoelstra at <a href=3D"http://wpsoftware.net" target=3D"_blank"=
rel=3D"nofollow" data-saferedirecturl=3D"https://www.google.com/url?hl=3De=
n&q=3Dhttp://wpsoftware.net&source=3Dgmail&ust=3D17153008146390=
00&usg=3DAOvVaw3wIDzlUj1wqXmVV4RyaQhz">wpsoftware.net</a>
<br>Web: <a href=3D"https://www.wpsoftware.net/andrew" target=3D"_blank" =
rel=3D"nofollow" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den=
&q=3Dhttps://www.wpsoftware.net/andrew&source=3Dgmail&ust=3D171=
5300814639000&usg=3DAOvVaw1ZlDWyULQOphaSgTZFgrBT">https://www.wpsoftwar=
e.net/andrew</a>
<br>
<br>The sun is always shining in space
<br> -Justin Lewis-Webster
<br>
<br></blockquote></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/d/msgid/bitcoindev/b50b6b09-4d13-46ab-9776-f6b8a02aa2e0n%40googlegroups.=
com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msg=
id/bitcoindev/b50b6b09-4d13-46ab-9776-f6b8a02aa2e0n%40googlegroups.com</a>.=
<br />
------=_Part_85990_406851706.1715214678205--
------=_Part_85989_269653429.1715214678205--
|
