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
|
Delivery-date: Tue, 30 Apr 2024 07:23:00 -0700
Received: from mail-oa1-f58.google.com ([209.85.160.58])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBAABBPP5YOYQMGQE5EPQ4FQ@googlegroups.com>)
id 1s1oNo-0007it-M0
for bitcoindev@gnusha.org; Tue, 30 Apr 2024 07:23:00 -0700
Received: by mail-oa1-f58.google.com with SMTP id 586e51a60fabf-23c436ee1ccsf2480098fac.1
for <bitcoindev@gnusha.org>; Tue, 30 Apr 2024 07:23:00 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1714486974; cv=pass;
d=google.com; s=arc-20160816;
b=M6xe4B3HY3kcv9jRrjPIDrwTZdWFqPF+gmg9MBxC/7U2fXp2xQ8vqAyJ31+pkppGvA
+cqClo4tGNcFAbhZXUtA89a0KFyilk3ZRUkjDbietjofsdy2D0l094JXhcBqGL4XV1uV
J1jgypD3Te46UTkSbRv+fNpFG+aBR2IkahU1e7qi9p27golP9Qu9r82FmXTQBT84rBFC
RWEkdXdWbjG1/mIJARw8ueRwjyztXA14hHVfemZkp1vGbkQeruLHzVBw6nEz+GAiC6FW
RDCQaq1uXE383P8HaQRKr8xH25BDxK3X5M+V+94BRXJmnmwE+6sVSgAUtKTyXZW5GwbR
c9uw==
ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816;
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=WAHB5lWQ8J3/cUOUscSzz0/kFyy0CVaK7ZqnnRwh6do=;
fh=YVDvoCWtl+BaHy1XYszROR14Cw6wt1X3ywQ9SS9nEMc=;
b=wXrNgqeTquvkYcFeiYBDmxCk5/9/IbnDC7i1GmX+gsUi3CavXX/qUbWDDUmS5wZ3ih
1o2BBkCZi8i5y6DiI9GaTTEkgxuGH1y1Ki9xdTUAOUxti1AYbxt4MHjEQaymRWep2FdQ
hJBg4STJwA+pGxDff3csyQNOF5Tr02afAxVy1wePGXhEnluGSxTT4d818m18izXRW2fr
O3kUlxgi3GNgkpn3VUt6Y05nqXwuX2kZupJ7Gpr1AgrM8sUzTnDYvv8zyL11R9T6gO6W
DQ2iFn2Sg+BRMpqF8pZ6lbKxL+MjX6EY/YSfqqSqf9ICI7bEN/sn9eO8JVySL3UY/85M
YQdQ==;
darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
dkim=pass header.i=@mail.wpsoftware.net header.s=default header.b=KH5mTXWo;
spf=pass (google.com: domain of apoelstra@wpsoftware.net designates 66.183.0.205 as permitted sender) smtp.mailfrom=apoelstra@wpsoftware.net;
dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=wpsoftware.net
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1714486974; x=1715091774; 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=WAHB5lWQ8J3/cUOUscSzz0/kFyy0CVaK7ZqnnRwh6do=;
b=KJ45kBVVXPSYUbCCd49WrayZ5IoqLe6L+iPsJ0BiDSjhmpR0vEbtFk7UU2gcg1/aEv
j+kSvAEPK1RaBUEimIBFpFuHnAH/GhdbxUxvUdAkJcGtWYVJOjdWm9I/AurpB+/zNJZ5
GwZ6xrL2bMRGcXY10kwbWkhRMBQLAW3FUV14JXe3muSgVb952N2eoTsdzkptkBqN4p3y
B/n+JPD8ip5qIGWpm5oxhVShkrwW7u/Ton8UCdAsu7xh+J7j0aUZak5G9408gb4r+g4B
ZlCq5qK3+qWHFamWmD1ipYduVyVJdit7CHpDNA4KKFnUU5okf0Nfa57Tki1/8i0woE6L
eVdQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1714486974; x=1715091774;
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=WAHB5lWQ8J3/cUOUscSzz0/kFyy0CVaK7ZqnnRwh6do=;
b=rydx0Jc2DvgJYdmS3F9QBJwje2RrLAq7xEXfb+A99Qhiezq7P/JSyty40xUl2h+df8
zkjHHPwxSRNCtEFjyxkJqyHtzAZehzFfOiV3Xu2yVaRG+wgoWw1uo16r7fTVBDWQQo4Q
eD4E+F9TvM+WHlZbcXYtvltx1l3oF2Q28yjLf+nBbub1Y/H9yWwH4o957PkKJjfNy+5i
EKsSJm5jxySL7ul9+xWp7ECUZAAztxEgTFT8Tx5XeSGa7lBW0Pqs/gj71LA6aHKUb23j
ivGWKRX7ZD0VD7EV/ITn+OsRcqDlmUKkNQSGQ2Rt8PwC5cZkGH/xOH1tK6J5o+uIQwEE
wXzA==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCWkLq1aWLO3QTDak0622u/yeUFchI180YPsYlTkIZ9xet5uM87BMhHmubMWAf6AAlPKs91jkLyeDYnIcYadxbemdrgixhs=
X-Gm-Message-State: AOJu0YxPGF2eCoNMwSdr+Yjh+UlfoLhQQzUnLpaBUSqxJ356oRpsbr1S
r1XYxez74zBX/lGkNzCOOlYtN2I91V6gGoAoWzUI33ZTPHdF5uui
X-Google-Smtp-Source: AGHT+IFzr5W21E0c49L7JxYCgQc71Fu1/U44TZzgxufVekSlHPzvAnW89ERNXFK75jweha+kpaFuXQ==
X-Received: by 2002:a05:6871:6510:b0:22e:de21:e084 with SMTP id rl16-20020a056871651000b0022ede21e084mr15579212oab.9.1714486974591;
Tue, 30 Apr 2024 07:22:54 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a05:6870:2492:b0:23a:6680:6036 with SMTP id
586e51a60fabf-23b422f4240ls4328870fac.2.-pod-prod-07-us; Tue, 30 Apr 2024
07:22:53 -0700 (PDT)
X-Forwarded-Encrypted: i=2; AJvYcCUbUOs1BZkkr7hjrD3z5BdY44/QEAc8xxez60YYRqgsbySf7m0/ceiyFI0ERXri7ovFL+w7syFI9kenOUKubEiolEQN3GrfAGHt5xY=
X-Received: by 2002:a05:6871:339f:b0:229:7ea3:7242 with SMTP id ng31-20020a056871339f00b002297ea37242mr738889oac.9.1714486973116;
Tue, 30 Apr 2024 07:22:53 -0700 (PDT)
Received: by 2002:a05:6808:1909:b0:3c7:2efe:13c8 with SMTP id 5614622812f47-3c855234df0msb6e;
Tue, 30 Apr 2024 07:21:45 -0700 (PDT)
X-Forwarded-Encrypted: i=2; AJvYcCWnd19haoenaQCUWIhg4KvwfvPc0CyOQPP7JOqjhkrohTTVxBXMLx+/+9RtqcrVKAehxHDIt5f++/HaOL0wt6ZvauoUdwsrQIU4JAg=
X-Received: by 2002:a05:6602:13cf:b0:7de:ce69:59b3 with SMTP id o15-20020a05660213cf00b007dece6959b3mr8451744iov.0.1714486904108;
Tue, 30 Apr 2024 07:21:44 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1714486904; cv=none;
d=google.com; s=arc-20160816;
b=XX3jzBSIjSsbF1krs+Kndn/aOshF31bJdb1ggP3G9LHbi2LcI1bUAxkfPhZVsk/EbU
1yCocV1hPsxovDceaFuHyRw7VGhnIGuwQ05YJLVKJFwIA7xUhIpLVkvI12gTuN70bhw9
loFqsck0j+PSkYkgQZjWQ+9irYdGDzeQNV8hJH7PqPxW9sWY7XNBblZNwHV/IzAfpgjC
mZ8ngcV1FjUqTIId5eUD/jl6ZoqVPdxmSep+DxsVNAmYwr/nQYvLaF1xj0IXbSeGuRxT
XsAD59JmHcZhPzGzM1ukGITU1+VOtVySlUNVcHsWoiX7Y8HrXS36q7LOYuahZumMjUHC
RdQg==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816;
h=in-reply-to:content-disposition:mime-version:references:message-id
:subject:cc:to:from:date:dkim-signature;
bh=huahnpPsdftWHoy9pAy5+9Yk+Q+zk409uusVHnxUBns=;
fh=BjIDVxpOvugBULxmWHhejF5MP/45cWrxFRfbz6qmqXk=;
b=T1r2XzOIi9DoEP5jEHA2frMGcKGEwTP0YnErMtMiOFiPlAvY3cnYbjkQYT+9SDVtSH
Nl0g/mADfJf+tAW7mB5eUga6pD4GlflK+s+z4DoXDMz7CuXaB1zhLWezSHY3I9mfg6Iq
z5DrpFEm3xJTmBBzLF2RHEj0kB5iCq7yVK/yx627Y4i1LFp78q4Bb8lv2bx/XBGDp+Ln
KM6NH4534s87YmDF8PlQH8SQ2f5zZ2eutIcJo0YWjTK1ghMMM3nIinB3Wj/BxJYNNszd
Dwj0VTSmQEYA7PonMM/QnJL91xjN+Opmg/s/YWrSmC/emBmmoO5IYuDPuuA2W7B0mKG9
rd/A==;
dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
dkim=pass header.i=@mail.wpsoftware.net header.s=default header.b=KH5mTXWo;
spf=pass (google.com: domain of apoelstra@wpsoftware.net designates 66.183.0.205 as permitted sender) smtp.mailfrom=apoelstra@wpsoftware.net;
dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=wpsoftware.net
Received: from mail.wpsoftware.net ([66.183.0.205])
by gmr-mx.google.com with ESMTP id v1-20020a5d9481000000b007deac6f33d6si572626ioj.4.2024.04.30.07.21.43
for <bitcoindev@googlegroups.com>;
Tue, 30 Apr 2024 07:21:43 -0700 (PDT)
Received-SPF: pass (google.com: domain of apoelstra@wpsoftware.net designates 66.183.0.205 as permitted sender) client-ip=66.183.0.205;
Received: from camus (camus-andrew.lan [192.168.0.190])
by mail.wpsoftware.net (Postfix) with ESMTPSA id F371C400ED;
Tue, 30 Apr 2024 14:21:41 +0000 (UTC)
Date: Tue, 30 Apr 2024 14:21:40 +0000
From: Andrew Poelstra <apoelstra@wpsoftware.net>
To: Matthew Zipkin <pinheadmz@gmail.com>
Cc: Ethan Heilman <eth3rs@gmail.com>,
Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport
Signatures (no changes needed)
Message-ID: <ZjD-dMMGxoGNgzIg@camus>
References: <CAEM=y+XyW8wNOekw13C5jDMzQ-dOJpQrBC+qR8-uDot25tM=XA@mail.gmail.com>
<CA+x5asTOTai_4yNGEgtKEqAchuWJ0jGDEgMqHFYDwactPnrgyw@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="Lwd7sZ5ieIwUBdMT"
Content-Disposition: inline
In-Reply-To: <CA+x5asTOTai_4yNGEgtKEqAchuWJ0jGDEgMqHFYDwactPnrgyw@mail.gmail.com>
X-Original-Sender: apoelstra@wpsoftware.net
X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass
header.i=@mail.wpsoftware.net header.s=default header.b=KH5mTXWo;
spf=pass (google.com: domain of apoelstra@wpsoftware.net designates
66.183.0.205 as permitted sender) smtp.mailfrom=apoelstra@wpsoftware.net;
dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=wpsoftware.net
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 (/)
--Lwd7sZ5ieIwUBdMT
Content-Type: text/plain; charset="UTF-8"
Content-Disposition: inline
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.
>
> 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=1 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.)
--
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
--
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 on the web visit https://groups.google.com/d/msgid/bitcoindev/ZjD-dMMGxoGNgzIg%40camus.
--Lwd7sZ5ieIwUBdMT
Content-Type: application/pgp-signature; name="signature.asc"
-----BEGIN PGP SIGNATURE-----
iQEzBAEBCAAdFiEEkPnKPD7Je+ki35VexYjWPOQbl8EFAmYw/nQACgkQxYjWPOQb
l8EVRgf9Fr5cFPc7iiH1Pni22OgASDmDFNYK/KQipJJ5UtfhFk12DO77L25u74OU
jCZFmhCWUs8JtBetekxCs4Tv7tfVMGSd9XAi1l0IBNn+8iV6iu89NBAmDbuaCV4j
TgJAFtPjMlf8IufRd8uZGoq4XnvoINqDZe2o2h1qiFrGFzwyra6oNxM4OLSalWIL
JMz6+5yu0XdGbRxj1V0pZ0KY8v02q5KRVy5enAhdkquklUKk1fefmbRm7UZrrefM
dxdgOF15car2RaNZKqDYenwOhpDP32HYqEqT7HBuKj5PIKeVa6Iv/lhSnIdvnCuZ
nXOhOLRbrw9rV6bTOxAagL6cAPCL9g==
=bcrp
-----END PGP SIGNATURE-----
--Lwd7sZ5ieIwUBdMT--
|
