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
|
Return-Path: <bnagaev@gmail.com>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137])
by lists.linuxfoundation.org (Postfix) with ESMTP id DAC0FC0037
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 20 Dec 2023 21:34:36 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp4.osuosl.org (Postfix) with ESMTP id A8E3142177
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 20 Dec 2023 21:34:36 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org A8E3142177
Authentication-Results: smtp4.osuosl.org;
dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
header.a=rsa-sha256 header.s=20230601 header.b=DEUB6nsR
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Level:
X-Spam-Status: No, score=-2.099 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,
RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001]
autolearn=ham autolearn_force=no
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 Zmg68s2iUDYN
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 20 Dec 2023 21:34:35 +0000 (UTC)
Received: from mail-il1-x12f.google.com (mail-il1-x12f.google.com
[IPv6:2607:f8b0:4864:20::12f])
by smtp4.osuosl.org (Postfix) with ESMTPS id 791B640984
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 20 Dec 2023 21:34:35 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 791B640984
Received: by mail-il1-x12f.google.com with SMTP id
e9e14a558f8ab-35fc5ebb4aaso481975ab.2
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 20 Dec 2023 13:34:35 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=gmail.com; s=20230601; t=1703108074; x=1703712874;
darn=lists.linuxfoundation.org;
h=content-transfer-encoding:cc:to:subject:message-id:date:from
:in-reply-to:references:mime-version:from:to:cc:subject:date
:message-id:reply-to;
bh=KtGvh9gFN2GDXrdR597QwaPtZauislAlh+kdCNS9Mmw=;
b=DEUB6nsRUJHH5lE3TGkaTv1PvsDuoFYm2fcdixLlsAcWHzj+PLHQU+50JpW3SBrtDH
1EL4ZrAMc2Pz+uIqZz0bp1qHfyvhS71xXSXUFosKAHoiB5HTw6didwKpCj3l+bzaS69f
wFPNOEmqu5MLL0edCaNwxI+vD7T9P0EMErcsUrJkXvRQL5YMwFFD8FJ40P1vRo8ugzRB
fuhlLJ94qc+u0uDMgkExpldJQs9t9hmnUGehqeMNbV95jNySTF8z59faQQrAqqVbfl4z
zEY9GA9/rRYeiflYUXXmSCQpw01XXzCsi0ch0k1sOTkEesZG2P3lmZlo1/zr/b+A3QUW
gEog==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1703108074; x=1703712874;
h=content-transfer-encoding:cc:to:subject:message-id:date:from
:in-reply-to:references:mime-version:x-gm-message-state:from:to:cc
:subject:date:message-id:reply-to;
bh=KtGvh9gFN2GDXrdR597QwaPtZauislAlh+kdCNS9Mmw=;
b=jmpWjJwF4Jlm4GZ5j4H/xwNaelBVR5vSd0EJ960WfBWLRjxpRLQ+4cimgMcGSeWtwH
jKZjIPprNSG0QFoSSZIzKea5LbV/7kByVp0uFk84EZMAowmHaKlbr2G2sI+ThAuBzZdw
VmA6JxOoHy6866hdRmF2373yO2bKoiDNa+uBZVunE1rvs1YzJurSQJqG79PM9whDlHLo
MWkgouI9QT+rgdiAg2XNRbHGVM5Dl8ahuDzMi7gV1N8eADqcZaJu/jOEEo8slWH8dCv7
QhfeWxFOld6QrzSj6Y5c/a1udt8KTqEGB27nlRoelb1D8u895LShu3UDFkGsBwM33Ias
iThQ==
X-Gm-Message-State: AOJu0Yykf4kr15poYkkdwRDQKihHicwe4wocYBNt7GHBfYtPiz/INjnI
WWu+Ib3xGT77wU/fRMt6pMOfoncKkFhTOaYeFiz+uqWWe23larx7
X-Google-Smtp-Source: AGHT+IGSSx60iG6TlURBBxs56ZNy5+ot4pzgW6WxO1nU2zZJQXkLMUrJxmfQYZ8e0cndNjLyrEIISXbOiR37XlTiJww=
X-Received: by 2002:a05:6e02:221a:b0:35f:cdbc:46e9 with SMTP id
j26-20020a056e02221a00b0035fcdbc46e9mr1336738ilf.40.1703108073996; Wed, 20
Dec 2023 13:34:33 -0800 (PST)
MIME-Version: 1.0
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>
In-Reply-To: <HG9-9VDKRd3-0v0x9QP05_Cjyk9Y3UW-94A1RHsT3xMQYmb7Y6sk9-wTUlqVZzm6ACigM7aM-B6NB-z6jVCCXhQIGEYkEcBKryzP587FlIo=@pm.me>
From: Nagaev Boris <bnagaev@gmail.com>
Date: Wed, 20 Dec 2023 18:33:56 -0300
Message-ID: <CAFC_Vt6vqZkeenfrsqSj4T3+4+L2KMam0o0FeWJ4VzBEWE=HfA@mail.gmail.com>
To: yurisvb@pm.me
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Mailman-Approved-At: Fri, 22 Dec 2023 01:02:15 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
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: Wed, 20 Dec 2023 21:34:37 -0000
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 analyzing=
my proposition, Boris!
>
> 1) My demonstration concludes 12 bytes is still a very conservative figur=
e for the hashes. I'm not sure where did you get the 14 bytes figure. This =
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 ri=
ght and I failed to realize that. To lessen the exposure, and the risk of m=
iner of LSIG, it can be left to be broadcast together with LAMPPRI.
>
> 3) I avail to advocate for economizing down the fingerprint to just 128 b=
its for the weakest-link-principle, since 128 bits is a nearly ubiquitous s=
tandard, employed even by the majority of seeds. Not an argument against pl=
ain Schnorr, because Schnorr keys could use it too, but, compared with curr=
ent 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 ec=
onomize even further, there is also the entropy-derivation cost trade-off o=
f N times costlier derivation for log2(N) less bits. If applied to the Addr=
ess, we could shave away another byte.
>
> 5) T0 is just the block height of burying of LSIG doesn't need to be buri=
ed. T2 can perfectly be hard-coded to always be the block equivalent of T0 =
+ 48 hours (a reasonable spam to prevent innocent defaulting on commitment =
due to network unavailability). T1 is any value such as T0 < T1 < T2, (typi=
cally T1 <=3D T0+6) of user's choosing, to compromise between, on one hand,=
the convenience of unfreezing UTXO and having TX mining completed ASAP and=
, on the other, avoiding the risk of blockchain forking causing LAMPPRI to =
be accidentally leaked in the same block height as LSIG, which allows for s=
ignatures to be forged. So this is 16 bytes less.
>
> Miners would keep record of unconfirmed BL's, because of the reward of mi=
ning 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 equal,=
we have 20 bytes lighter than Schnorr; and up to 25 bytes less the current=
implementation of Schnorr, if items 3 and 4 are implemented too. Already w=
e have a reduction of between 21% and 26%, while, so far, nobody in the mai=
ling 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 (billion).
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
>
--=20
Best regards,
Boris Nagaev
|
