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
258
259
260
261
262
263
264
|
Delivery-date: Fri, 02 May 2025 12:09:14 -0700
Received: from mail-yb1-f192.google.com ([209.85.219.192])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBCJNLJPWXAIBBTNQ2TAAMGQEXRNJGUI@googlegroups.com>)
id 1uAvl3-0001Hv-2M
for bitcoindev@gnusha.org; Fri, 02 May 2025 12:09:14 -0700
Received: by mail-yb1-f192.google.com with SMTP id 3f1490d57ef6-e72a02f0e5esf2784602276.3
for <bitcoindev@gnusha.org>; Fri, 02 May 2025 12:09:13 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1746212947; x=1746817747; 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=U9CVPL5bzW2/UQeyRTzcErMBuYpD6+QynIsi6WRrVFw=;
b=KblY4sYuEfYimyhDl3K1gLkFBrRmYSlbhgA+978efUPb3qvP3x9qKpUt8RWDHGGybO
ZK6gH4wH/3YZ8H9gP4lJQeK49ik0m+T0SVNsindfzkVr5h6WpOmiftyab3j1qDKmF4zS
2AJfxxgPLvsPLBPE2xHOr2aj10SKnBJ9OTJl9cyNpXBa+6404bYoZ43KNil2Y8a5UQGx
hoWm/ZPz5Nr0MV5CLQGi3Pql1k8X9ouFn4q3RaEZRVNtB6+o5F3UKQhp/u90PrmpdUsG
kV4BJ4IATFVVGC44Yyp7swJbA14XHD3hRdwunz+u6h52WziLPyasgV03bnNIVRIVSNMG
MMZQ==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=gmail.com; s=20230601; t=1746212947; x=1746817747; 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=U9CVPL5bzW2/UQeyRTzcErMBuYpD6+QynIsi6WRrVFw=;
b=YtPtFzthtERFICV6qPqR+kPXnj5PModLMDRCppLENkycDRXRtZNhZMvAxmQw8WnZ5L
OpELoHx7JbIZCU7rHQzt6hDFlN2n/hZ4lUrR1nBiBUr0KiMYfxoGQsT4yECNVbk4SZ9K
j5DW0h9R3DAO+kzRzMI6gU5/3/WB4qMhMtoG7sO1oJZLy0zi4zrtvxL22M/PCJ1VykOz
VJneDTsEBR6Nr74Xx0I8g/OHRkfCDJYHBs7ArsVahUTFewTrl9TNZQ4QZix1zE9eTEem
f5X+furFrw8e5qyktFL/wgeh1gA5ohJVc1u1mFg5oMH6IqxQkULk3uTdLzvYrEuN+02B
MkfA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1746212947; x=1746817747;
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=U9CVPL5bzW2/UQeyRTzcErMBuYpD6+QynIsi6WRrVFw=;
b=Kqucia+Yv+HvuvceO3x2SRuBe9ioOCkSvi3amBT+PzT8TdU8hha+VAk8MVOgDgAHcp
AizyBnumFiny6Bo5mj8fwKSvH/cjrHHI5m8Oph2X+lP5A6dsFh38JIZRIJN9CpWgvu9+
Ap1VdFUjyn3WEjO6NvMjfpZ8Y5ZDAPuNk2x4/PFMV22RLYXphiUumN5P0KWI7OuuFXxX
2FCmt2ivfM0xfjwEz2u7J6Bwd8EZ1YnB7LQyf4Xr8EA1gH6AqaxzgKRkXGL6kwDLOGTL
M8vf17acziIUkatiNWNIpyPrYA6/3weygiX1d1wvZpwZt1Fm2EuZPy+M6J1Ur2bvibNA
ygEg==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCX/fG81dpY7y6HwbZQ6HUkJWgmb3gQM79Ciqo+d11WSG1FQ0FT1rz2hAQr1n26EhwkZAsOcjKmHX3wL@gnusha.org
X-Gm-Message-State: AOJu0Yw1FJhx73aEQy/dkm/S1iLS/r0c86Vm0vKbcCoz9epJTy+4PuVb
QXsuloj/JG76CIKaT2J5FmAjP2glOr71hA/qzHvCHeAxP9dteu3r
X-Google-Smtp-Source: AGHT+IEwg2aA4MtgKqZfG4rVSlnMB1zYxnfLhuG+rnPjzaCzjsBz5nzQdw5z5iilUYOHe9LmiDWcyw==
X-Received: by 2002:a05:6902:150a:b0:e72:8aca:d06b with SMTP id 3f1490d57ef6-e756557de61mr5165281276.25.1746212946796;
Fri, 02 May 2025 12:09:06 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=AVT/gBGVUra4Nt9NxNJTWp81T6mgriMoJskBCISpW9723JFwgw==
Received: by 2002:a25:e087:0:b0:e74:7ce7:2dd8 with SMTP id 3f1490d57ef6-e754b311c0cls782149276.2.-pod-prod-05-us;
Fri, 02 May 2025 12:09:01 -0700 (PDT)
X-Received: by 2002:a05:690c:700c:b0:6ef:7dde:bdef with SMTP id 00721157ae682-708cede5111mr59480877b3.23.1746212941096;
Fri, 02 May 2025 12:09:01 -0700 (PDT)
Received: by 2002:a81:d448:0:b0:706:b535:945d with SMTP id 00721157ae682-708cfda3e38ms7b3;
Fri, 2 May 2025 09:07:52 -0700 (PDT)
X-Received: by 2002:a81:be09:0:b0:708:16b0:59bf with SMTP id 00721157ae682-708cede5268mr38475787b3.26.1746202071504;
Fri, 02 May 2025 09:07:51 -0700 (PDT)
Date: Fri, 2 May 2025 09:07:50 -0700 (PDT)
From: Greg Maxwell <gmaxwell@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <69194329-4ce6-4272-acc5-fd913a7986f3n@googlegroups.com>
In-Reply-To: <CAPv7TjaDGr4HCdQ0rR6_ma5zh2umU9r3_529szdswn_GjjnuCw@mail.gmail.com>
References: <CAPv7TjaM0tfbcBTRa0_713Bk6Y9jr+ShOC1KZi2V3V2zooTXyg@mail.gmail.com>
<cc2dfa79-89f0-4170-9725-894ea189a0e2n@googlegroups.com>
<CAPv7TjaDGr4HCdQ0rR6_ma5zh2umU9r3_529szdswn_GjjnuCw@mail.gmail.com>
Subject: Re: [bitcoindev] Re: SwiftSync - smarter synchronization with hints
MIME-Version: 1.0
Content-Type: multipart/mixed;
boundary="----=_Part_60916_1045498522.1746202070906"
X-Original-Sender: gmaxwell@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_60916_1045498522.1746202070906
Content-Type: multipart/alternative;
boundary="----=_Part_60917_759758223.1746202070906"
------=_Part_60917_759758223.1746202070906
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
On Friday, May 2, 2025 at 11:01:10=E2=80=AFAM UTC Ruben Somsen wrote:
I don't see a practical way to do this without compromising the benefits of=
=20
SwiftSync because of the "later find them being spent" part. For one, it=20
would require doing a lookup for each input to see if it's in your UTXO=20
set, something we currently don't need to do at all. Secondly, it would=20
require blocks to be processed in order, limiting parallelization. The=20
space savings would also be negligible, considering the hint data is=20
already <100MB (compressed).
Doh. Right. Got too excited.
=20
I think most of the remaining optimization potential (other than the=20
engineering work to enable parallel validation) is in the hash=20
aggregate, like the midstate reuse. Is there a faster alternative to=20
sha256? Can we get away with 16 byte hashes? I could be mistaken, but in=20
theory it seems we could even get away with 4 byte hashes if we allowed for=
=20
a 1 in 4 billion chance of accidentally accepting an invalid chain. Leaving=
=20
consensus to chance feels philosophically improper, but it's a pretty safe=
=20
bet considering it also involves PoW to trigger and even then would only=20
affect one or two random unlucky people on Earth.
I think the problem isn't so much the size of the hash output, but rather=
=20
the property you need is that each salt gives you a different hash function=
=20
such that the attacker cannot predictably create collisions. The most=20
expedient way to get there is a cryptographic hash function, which limits=
=20
you lower performance choices. Your reduction function could just be xor=
=20
and if it is I doubt the output size itself matters much for performance...=
=20
and my guess is that e.g. xor with 32 byte hashes will have better=20
performance than addition with 16 bytes.
It doesn't need to be so in the initial implementation but ultimately it=20
may make sense for the host to benchmark available hashes and pick the=20
fastest. SHA-256 will easily be a winner on hardware with SHA-NI or=20
similar. But there are other cryptographic hashes in the codebase that=20
might be faster on systems without sha256 hardware support. =20
There are argument I can see to prove the security of simpler hashes that=
=20
only work if you assume that the attacker could only insert specific finite=
=20
numbers of bad changes... but they really have completely full control of=
=20
the hash function input except for the salt and that I think makes it hard=
=20
to say much positive about the security of any optimization except=20
truncating a secure hash (and I don't think truncating will win you much=20
security).
In terms of security keep in mind that a prospective attacker needs to=20
also perform POW to get their attack chain up to the users accepted chain=
=20
tip, which means that they have to do the work between the AV point and the=
=20
tip assuming the user isn't isolated. This fact could be used to justify a=
=20
rather weak hash function, but I think it's not really worth a lot of=20
analysis ahead of the initial functionality. I'm guessing that once this=
=20
is implemented, even if its with a quite expensive hash function that the=
=20
IBD performance will be heavily bottlenecked in network and parallelism=20
related issues and be far from the lowest hanging fruit for a while, =20
considering that this has eliminated the big sequential part and a number=
=20
of annoying to optimize components entirely.
--=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 visit https://groups.google.com/d/msgid/bitcoindev/=
69194329-4ce6-4272-acc5-fd913a7986f3n%40googlegroups.com.
------=_Part_60917_759758223.1746202070906
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div><div dir=3D"auto">On Friday, May 2, 2025 at 11:01:10=E2=80=AFAM UTC Ru=
ben Somsen wrote:<br /></div><blockquote style=3D"margin: 0px 0px 0px 0.8ex=
; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div dir=
=3D"ltr"><div>I don't see a practical way to do this without compromising t=
he benefits of SwiftSync because of the=C2=A0"later find them being spent" =
part. For one, it would require doing a lookup for each input to see if it'=
s in your UTXO set, something we currently don't need to do at all. Secondl=
y, it would require blocks to be processed in order, limiting parallelizati=
on. The space savings would also be negligible, considering the hint data i=
s already <100MB (compressed).</div></div></blockquote><div><br /></div>=
<div>Doh. Right. Got too excited.</div><div>=C2=A0<br /></div><blockquote s=
tyle=3D"margin: 0px 0px 0px 0.8ex; border-left: 1px solid rgb(204, 204, 204=
); padding-left: 1ex;"><div dir=3D"ltr"><div>I think most of the remaining =
optimization potential (other than the engineering work to enable parallel =
validation) is in the hash aggregate,=C2=A0like the midstate reuse. Is ther=
e a faster alternative to sha256? Can we get away with 16 byte hashes? I co=
uld be mistaken, but in theory it seems we could even get away with 4 byte =
hashes if we allowed for a 1 in 4 billion chance of accidentally accepting =
an invalid chain. Leaving consensus to chance feels philosophically imprope=
r, but it's a pretty safe bet considering it also involves PoW to trigger a=
nd even then would only affect one or two random unlucky people on=C2=A0Ear=
th.</div></div></blockquote><div><br /></div><div>I think the problem isn't=
so much the size of the hash output, but rather the property you need is t=
hat each salt gives you a different hash function such that the attacker ca=
nnot predictably create collisions. The most expedient way to get there is =
a cryptographic hash function, which limits you lower performance choices.=
=C2=A0 Your reduction function could just be xor and if it is I doubt the o=
utput size itself matters much for performance... and my guess is that e.g.=
xor with 32 byte hashes will have better performance than addition with 16=
bytes.</div><div><br /></div><div>It doesn't need to be so in the initial =
implementation but ultimately it may make sense for the host to benchmark a=
vailable hashes and pick the fastest.=C2=A0 SHA-256 will easily be a winner=
on hardware with SHA-NI or similar.=C2=A0 But there are other cryptographi=
c hashes in the codebase that might be faster on systems without sha256 har=
dware support.=C2=A0 <br /></div><div><br /></div><div>There are argument I=
can see to prove the security of simpler hashes that only work if you assu=
me that the attacker could only insert specific finite numbers of bad chang=
es... but they really have completely full control of the hash function inp=
ut except for the salt and that I think makes it hard to say much positive =
about the security of any optimization except truncating a secure hash (and=
I don't think truncating will win you much security).</div><div><br /></di=
v><div>=C2=A0In terms of security keep in mind that a prospective attacker =
needs to also perform POW to get their attack chain up to the users accepte=
d chain tip, which means that they have to do the work between the AV point=
and the tip assuming the user isn't isolated.=C2=A0 This fact could be use=
d to justify a rather weak hash function, but I think it's not really worth=
a lot of analysis ahead of the initial functionality.=C2=A0 I'm guessing t=
hat once this is implemented, even if its with a quite expensive hash funct=
ion that the IBD performance will be heavily bottlenecked in network and pa=
rallelism related issues and be far from the lowest hanging fruit for a whi=
le,=C2=A0 considering that this has eliminated the big sequential part and =
a number of annoying to optimize components entirely.</div><div><br /></div=
><div><br /></div><div><br /></div><div><br /></div><div><br /></div></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 visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/69194329-4ce6-4272-acc5-fd913a7986f3n%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/69194329-4ce6-4272-acc5-fd913a7986f3n%40googlegroups.com</a>.<br />
------=_Part_60917_759758223.1746202070906--
------=_Part_60916_1045498522.1746202070906--
|
