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
|
Return-Path: <yurisvb@pm.me>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133])
by lists.linuxfoundation.org (Postfix) with ESMTP id 7F6C9C0037
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 21 Dec 2023 16:07:52 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp2.osuosl.org (Postfix) with ESMTP id 5353D40A50
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 21 Dec 2023 16:07:52 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 5353D40A50
Authentication-Results: smtp2.osuosl.org;
dkim=pass (2048-bit key) header.d=pm.me header.i=@pm.me header.a=rsa-sha256
header.s=protonmail3 header.b=gWAcyuzP
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, RCVD_IN_MSPIKE_H5=0.001,
RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001]
autolearn=ham autolearn_force=no
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 HUOvgvNoysfv
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 21 Dec 2023 16:07:49 +0000 (UTC)
X-Greylist: delayed 172540 seconds by postgrey-1.37 at util1.osuosl.org;
Thu, 21 Dec 2023 16:07:48 UTC
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org C37A840645
Received: from mail-40131.protonmail.ch (mail-40131.protonmail.ch
[185.70.40.131])
by smtp2.osuosl.org (Postfix) with ESMTPS id C37A840645
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 21 Dec 2023 16:07:48 +0000 (UTC)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pm.me;
s=protonmail3; t=1703174865; x=1703434065;
bh=y3HuS8/fz37dllTU2DW6pwf+buc41/MpIpEkjvAeuJc=;
h=Date:To:From:Subject:Message-ID:In-Reply-To:References:
Feedback-ID:From:To:Cc:Date:Subject:Reply-To:Feedback-ID:
Message-ID:BIMI-Selector;
b=gWAcyuzPEDK18LPORy39WyOHhPjX2FneRReRaOFXOXA1WdQQ0e9zz00SwY70ErHlX
eHLW8vvNdZTswe1m2GARYAc4zPfgFkHdr5oqqNZR5Tp1YtgV25XMJ+ewEoubqDXMFo
1KSOnvKchFm0dBH1E9rEenBNJmtjPa+J6Rk5XatT0fpXwLpSOB5qO+/EtNUsZ/ny4B
TIe1/mZ0r9isUp+GPd10xawu1uwjRira00gl2+0x7rkF7GzcRaPIPeE2tdksaEbLi1
cJQ0aJ8DbX5vEep6XDVZ3IEgRYSVPJHLI96+3DFUT3aDWXqJIAa53Vhn/kN4H0MtNa
ycVKdjEFO23gQ==
Date: Thu, 21 Dec 2023 16:07:27 +0000
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
Nagaev Boris <bnagaev@gmail.com>
From: yurisvb@pm.me
Message-ID: <I11FZ_ZpfwpnQBh5hbBZMHsQt_cKwF9My49X4-MMRIYvaJEoIwta-GEaDNN1EtQxST4gQFAvqfOZElDvIpPrlAVknyN52IMnJKNy5kT8sUE=@pm.me>
In-Reply-To: <CAFC_Vt6vqZkeenfrsqSj4T3+4+L2KMam0o0FeWJ4VzBEWE=HfA@mail.gmail.com>
References: <nvbG12_Si7DVx9JbnnAvZbNdWk7hDQA23W1TXMkfYoU2iBA95Z1HzRnXgyiwFhDBmdi_rWL0dPllX1M9N9YZPDV47VgYADNd7CQA9CkAuX0=@pm.me>
<CAFC_Vt5xqhuXjNVeSGE2Pn=0N0MuB6pOnREzGhSQSpk+hTUUSg@mail.gmail.com>
<-lH1AcjRwuxfuqLPFOh_oga10Qm12fb7Se9imDeS5ft6CU3y8KTQa3tBP0twJJBFSHgj7FC8EIxvEser3oZdWvkeitRwERQl_cCdgAWtbTU=@pm.me>
<CAFC_Vt7B1oV0_uAwKe3NQLWE2jdQ_MF1W4fnVqkf8s=YHyfVyQ@mail.gmail.com>
<1aHuuO-k0Qo7Bt2-Hu5qPFHXi4RgRASpf9hWshaypHtdN-N9jkubcvmf-aUcFEA6-7L9FNXoilIyydCs41eK4v67GVflEd9WIuEF9t5rE8w=@pm.me>
<CAFC_Vt644Wqn7EcvoZwFscPMov8T5kO9ss_QRgNgVNir-bBA0Q@mail.gmail.com>
<ue8nChOuMtyW_JM-WxikLpWUSn9I99UHI5ukFVfLOEmQtCo4noetzyVKercbrwjr_EqNotDsR1QZ0oijMu11TO2jpEjlJF71OjLlNoZ-00Y=@pm.me>
<CAFC_Vt5PcqqcREJ67Jzcg=K+Agd02a9f5uSit8LwkYHshbvF7A@mail.gmail.com>
<HG9-9VDKRd3-0v0x9QP05_Cjyk9Y3UW-94A1RHsT3xMQYmb7Y6sk9-wTUlqVZzm6ACigM7aM-B6NB-z6jVCCXhQIGEYkEcBKryzP587FlIo=@pm.me>
<CAFC_Vt6vqZkeenfrsqSj4T3+4+L2KMam0o0FeWJ4VzBEWE=HfA@mail.gmail.com>
Feedback-ID: 15605746:user:proton
MIME-Version: 1.0
Content-Type: multipart/signed; protocol="application/pgp-signature";
micalg=pgp-sha256;
boundary="------9b7fbb3c401a05f102e5c176e10b8e6c03e9ab37b70a908bf81ce12be9ca316e";
charset=utf-8
X-Mailman-Approved-At: Fri, 22 Dec 2023 01:02:16 +0000
Subject: Re: [bitcoin-dev] Lamport scheme (not signature) to economize on L1
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, 21 Dec 2023 16:07:52 -0000
This is an OpenPGP/MIME signed message (RFC 4880 and 3156)
--------9b7fbb3c401a05f102e5c176e10b8e6c03e9ab37b70a908bf81ce12be9ca316e
Content-Type: multipart/mixed;boundary=---------------------988878b0db437c87187a08e65db1d5f7
-----------------------988878b0db437c87187a08e65db1d5f7
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;charset=utf-8
You are right to point out that my proposal was lacking defense against ra=
inbow-table, because there is a simple solution for it:
To take nonces from recent blocks, say, T0-6, ..., T0-13, for salting LSIG=
, and ECCPUB to salt LAMPPUB. Salts don't need to be secret, only unknown =
by the builder of rainbow table while they made it, which is the case, sin=
ce here we have 8*32=3D256 bits for LSIG, and the entropy of ECCPUB in the=
second.
With rainbow table out of our way, there is only brute-force analysis to m=
ind. Honestly, Guess I should find a less 'outrageously generous' upper bo=
und for adversary's model, than just assume they have a magic wand to conv=
ert SHA256 ASICS into CPU with the same hashrate for memory- and serial-wo=
rk-hard hashes (therefore giving away hash hardness). That's because with =
such 'magic wand' many mining pools would, not only be capable of cracking=
2^48 hashes far within the protocol's prescribed 48 hours, but also 2^64 =
within a block time, which would invalidate a lot of what is still in use =
today.
Please, allow me a few days to think that through.
YSVB
Sent with Proton Mail secure email.
On Wednesday, December 20th, 2023 at 10:33 PM, Nagaev Boris <bnagaev@gmail=
.com> wrote:
> On Tue, Dec 19, 2023 at 6:22=E2=80=AFPM yurisvb@pm.me wrote:
>
> > Thank you for putting yourself through the working of carefully analyz=
ing my proposition, Boris!
> >
> > 1) My demonstration concludes 12 bytes is still a very conservative fi=
gure for the hashes. I'm not sure where did you get the 14 bytes figure. T=
his is 2*(14-12) =3D 4 bytes less.
>
>
> I agree. It should have been 12.
>
> > 2) Thank you for pointing out that ECCPUB is necessary. That's exactly=
right and I failed to realize that. To lessen the exposure, and the risk =
of miner of LSIG, it can be left to be broadcast together with LAMPPRI.
> >
> > 3) I avail to advocate for economizing down the fingerprint to just 12=
8 bits for the weakest-link-principle, since 128 bits is a nearly ubiquito=
us standard, employed even by the majority of seeds. Not an argument again=
st plain Schnorr, because Schnorr keys could use it too, but, compared wit=
h current implementations, we have that would be 20-16=3D4 bytes less.
>
>
> I think that the digest size for hash should be 2x key size for
> symmetric encryption. To find a collision (=3D break) for a hash
> function with digest size 128 bits one needs to calculate ~ 2^64
> hashes because of the birthday paradox.
>
> > 4) [Again, argument against plain, because it cuts for both sides:] To=
economize even further, there is also the entropy-derivation cost trade-o=
ff of N times costlier derivation for log2(N) less bits. If applied to the=
Address, we could shave away another byte.
> >
> > 5) T0 is just the block height of burying of LSIG doesn't need to be b=
uried. T2 can perfectly be hard-coded to always be the block equivalent of=
T0 + 48 hours (a reasonable spam to prevent innocent defaulting on commit=
ment due to network unavailability). T1 is any value such as T0 < T1 < T2,=
(typically T1 <=3D T0+6) of user's choosing, to compromise between, on on=
e hand, the convenience of unfreezing UTXO and having TX mining completed =
ASAP and, on the other, avoiding the risk of blockchain forking causing LA=
MPPRI to be accidentally leaked in the same block height as LSIG, which al=
lows for signatures to be forged. So this is 16 bytes less.
> >
> > Miners would keep record of unconfirmed BL's, because of the reward of=
mining either possible outcome of it (successful transaction or execution=
of commitment). Everything is paid for.
> >
> > So, unless I'm forgetting something else, all other variables kept equ=
al, we have 20 bytes lighter than Schnorr; and up to 25 bytes less the cur=
rent implementation of Schnorr, if items 3 and 4 are implemented too. Alre=
ady we have a reduction of between 21% and 26%, while, so far, nobody in t=
he mailing list has disputed how 'outrageously' conservative the 12 bytes =
figure is.
>
>
> 26% reduction of block space utilization would be great, but the price
> of relying on 12 bytes hashes (only need 2^48 hashes to find a
> collision) is too much for that, IMHO.
>
> Another consideration is about 12 byte hashes. Let's try to figure out
> if they are resistant to rainbow table attack by a large organization.
> Let's assume that the rainbow table has a chain length of 1024^3 (billio=
n).
> What storage size is needed? 2^96 * 12 / 1024^3 =3D 900 exabytes.
> Both chain length and storage size seems prohibitively high for today,
> but tomorrow the hash function can be optimized, memory can be
> optimized, storage can become cheaper etc. And this attack may be
> affordable for state level attackers.
>
> > Any other objections?
> >
> > YSVB
>
>
>
> --
> Best regards,
> Boris Nagaev
-----------------------988878b0db437c87187a08e65db1d5f7
Content-Type: application/pgp-keys; filename="publickey - yurisvb@pm.me - 0x535F445D.asc"; name="publickey - yurisvb@pm.me - 0x535F445D.asc"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="publickey - yurisvb@pm.me - 0x535F445D.asc"; name="publickey - yurisvb@pm.me - 0x535F445D.asc"
LS0tLS1CRUdJTiBQR1AgUFVCTElDIEtFWSBCTE9DSy0tLS0tCgp4c0JOQkYySmpSWUJDQUM1MXlo
K0s0MmF0c0V5MGdCTmgvaklXR1hzQnRFLzdJOGFuUmZkZTcvcWdHeXkKbEx4TXFZRE1OelUwN3c5
Z3VINllKRDdWdzNaUmxTVGVqNU9Hc2laOFJ2OUp4YXBYc0MxeDMrdHhOQkFQClYyVml1MVpsMnhK
Y29sTDkrem9SUmhmU25lVDVaZm1IQlpBSklKbmhOdU80ajhrRi9iNDRFaEZ3NkwvTgpGbE9rK1VC
SkVvS0FFQWttd09aWWpVTDd6MStRdzJBZkJIVGVwNFMzYmY4SmZMNDFOUVJsRnBSa3MrSkMKTjNa
c0ozZmZhNURjWjVqTGgyK2k5Mlg2eE8yVW5nM0hLYXhJYTVtbzB3cGVvQ1JQdUxNRjE2cjVQelJ4
CjJmNldzZVlUbWVmZWVYUGUzZEhyTTR4ai9ndHpBRGNxaFd6VVZLM21ZNTdPTXhVYjJ4MWdqZ1Z6
QUJFQgpBQUhOSFhsMWNtbHpkbUpBY0cwdWJXVWdQSGwxY21semRtSkFjRzB1YldVK3dzQjFCQkFC
Q0FBZkJRSmQKaVkwV0Jnc0pCd2dEQWdRVkNBb0NBeFlDQVFJWkFRSWJBd0llQVFBS0NSQXYzelY4
UzhOTVZkTkRCLzlRCnZRRlpZNkRzR3FMOTlkKzI2QjdHYmRCb0VjenUxL2NqTVpNdE9QeW9nSElF
eXllalR3R1RVN3ZYNEpWZQozRHZnbnd4U2xIYjQ2dDU2VGV3OU5rZ2V4MmFIb0hGRnJBd3MraTVa
ajdZN2lhL2l2RVozZE1KR3dNSUoKeVlQS08rdG1ockxNYWlSSFdnUnhtSG5mRnhUY1dFQ1dSZEk3
dDRJWFp3Rm9QN2Z3TVVVVXQrV3NTbzJSCnJhUVZEL3NTL2F2TlF5T2h6YTlLcVBQNjBZY3B2RUtj
UXArL2hyTjRRcFhVSkxiaDFZMVlqeUhlbDhnQgpRa3p2QzUwUjVxTzRlY2xxSy9FMEhESnlDWmZN
TThkV2o0REJrTWN2SzlsYjB5b3ZRMDFFTXp1NkU1NEcKYjZ0VFp1bktQTVpVd1J1SW5FY0hHMjV0
azdWUEM4clJTU0hqeDhTT3pzQk5CRjJKalJZQkNBQ3RiUWdNCldRSnMvTVdZbDR2THRLSlhYbFlS
T2h1YkVWbjRjTFdZSmVFWHpzSllCQWRlNWh0QlEzc212UjJ2NnVJegptejJpaXFsSkVVdmYwY2xM
WS9QVExoSGVTbWE5VTRodzRaRDNZKzV6WWxINURza2l1N3lLZTdIVmpEVmkKd1FJN25acWRvanJs
dDhCZENiOVNMaXRNaFRvR1crS2E1VCtUOWNmbWthMk1qa3pRSFBNTEJtdVJ6a2V2ClBkZFF6M0xB
MjMzZDNHREVTZklCYy91OC9YelBUNkZTZ3MzSEh4OEFJbFdQbEJaYmh6WmpQNlRLclRNRQpOSEtK
cmxTRlZKclErL25QU28ya0VSL0VDczF0aUJEY0JkamVPYWx6LzdRVWN0Rnp3NGdjS0RtMGpUeEkK
cVhWVlV3a2tuRkM4NDZMTjNBT2p0UWRyOVV3czVsTzhkeXBGQUJFQkFBSEN3RjhFR0FFSUFBa0ZB
bDJKCmpSWUNHd3dBQ2drUUw5ODFmRXZEVEZXS2VBZ0FxRXN1QXJMZFprYXBvZDI3K2hpcHZZNUcr
eVRLQW1NMApIVlhmQzJiMVdtNXQwQXhOVXVkMlJ1OTE1MHA3V09CRXpXYkxnNXdzOTc1M296dlZi
cFpIQU9uVGZOeXoKUUR5QWhmZ1hNQjIvdzRERXEwT2tlQVBRNXhsQWtISDZpUW1hSkZiYy9FRjRX
ZWZWeE92MnNRNDlRNks5Ci9Bb1FROG54RVh1RzRidXVrclEwTGVlTVAzNEdMWUhYK2JvWENHQmxI
MGhiZm5kc3VQbEdqYnBnWVErdQplclJGTlB4N1JtSWtnQjJ0WmhwZkZ3VGtid1c2TVFmWDM5Z3F1
SitwVEVKUnA5UmpJVjFZU2txSjZJUkgKQkc4eFBocGgzT3huaWJyWkdlbGdtakpNM2QwM1k5OSs3
OXBvdTRlY09BeWYyTHMrMVVTY2NDTzA2YnI4CldlcjJ3cmI0WXc9PQo9aHJheAotLS0tLUVORCBQ
R1AgUFVCTElDIEtFWSBCTE9DSy0tLS0tCg==
-----------------------988878b0db437c87187a08e65db1d5f7--
--------9b7fbb3c401a05f102e5c176e10b8e6c03e9ab37b70a908bf81ce12be9ca316e
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"
-----BEGIN PGP SIGNATURE-----
Version: ProtonMail
wsBzBAEBCAAnBYJlhGKeCZAv3zV8S8NMVRYhBFNfRF3t6Z4/pmFJQy/fNXxL
w0xVAADHBQf/ftQ7PWwKqJh1C5E5RA0Xcpd7G5mHyn/tMV1RDyU2fm+pIdUM
9HDJISW7HZ2JMNd5EBvSLGERGY7707ArFm/+IQgYtkaXrXX4hPQ0awa8lKAz
3nKwWkpfXtQd0NJarqB4R9+ks6/VoxoTLwYoI6aKP6pTMNo5KdsUxDuxWdvu
ijo1HvZmsidbB47vpUx12Nck1NOjivi60E9LHy4xKE9Tbj6uQiMovR2c324i
cY2+bwZA0H5CzK3Qvp9U24C+0P2ZP53MX1289CD4gMTTVI7+jkN5iu9F5AgB
Qnfs4rhBusXFd14MEZePaxgQ4JtwzQWaVkW/iZHI9hvdu51eusmCGw==
=7+Rr
-----END PGP SIGNATURE-----
--------9b7fbb3c401a05f102e5c176e10b8e6c03e9ab37b70a908bf81ce12be9ca316e--
|