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
|
Return-Path: <tamas.blummer@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 81727BBC
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 21 Sep 2019 21:16:31 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wr1-f51.google.com (mail-wr1-f51.google.com
[209.85.221.51])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 9ED83108
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 21 Sep 2019 21:16:30 +0000 (UTC)
Received: by mail-wr1-f51.google.com with SMTP id b9so10121632wrs.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 21 Sep 2019 14:16:30 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=from:mime-version:subject:date:references:to:in-reply-to:message-id;
bh=MASqr6PVxHzyo4ZLMZqjBjiuusAssUBmJKr4yUtHoM4=;
b=Qc4c7RJamaECkRq/uxtPd5SaHRPMiW/XkrQ8T6ZtvamHKZmQLrnHV+9rXp1RP2b8Db
nmgks4pFL42ToHxM9JLqKBwH286P9UIkY59lRvdxZDHVh2Igr9e6iDyx3g6RsasvV/5k
LwdAhrNCaWlLUlnuw9wF257ajSaciOBBpGDfFj2GM+26Q4Yj1vPX4xN9Sa8fyBdVzh8i
0LGWP3+jesIAof9uYOj4u6RqCbG4Et2HjS/X8yJS3V4n2EvZ2ICEtQ36rwzHhfjlq2va
AwYcZOUXggngJYWnW7vIC6yCbGYYvRxv5oxaN9UzWoCW94cpBQbkLcCNA15bxT2iNxg9
g3OQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:from:mime-version:subject:date:references:to
:in-reply-to:message-id;
bh=MASqr6PVxHzyo4ZLMZqjBjiuusAssUBmJKr4yUtHoM4=;
b=IBYXOL4amBxMaVKGdGNeboqO+l5hwTrJzfh5fmOKIQSTO91cfg13TKclM5BKEDDVmz
HqDa0fqaedS+cjBynan1mPKvfMHhBtTLUHIgSVv3lASZiPyAPhkXHGOKEHNVLt7YP4nU
Gbk3dE9NuKZ3kLwbNGVEpGCARKKwAXqBOOqkCSrg/av0Y7KvOJ3GXvwL+qfxlgVo3o4g
ZJf1sphaDO6wj2gSrwI+HGTkguKLMgGUQbE6Nca5svqYPhaKM2XDHqromRWw72s4jDUe
0STMg7FitcuYMsHvRKe+aTlZXdztojViEF4lZBr7zaFWARmBQXr+NKD2SKM3izJJVETX
ql4A==
X-Gm-Message-State: APjAAAWwNyOO+EHQW69Ll5f77yRQgQ/Thl/Iw2e8bp1R+sYwLM7BORqr
yladXO0s+PP5H67TdK9vu3kLAoRJywY=
X-Google-Smtp-Source: APXvYqx4oLCcfR7yWCsxeuuo5YMm+O8ibzCqWzc9h2K1sEr0jOkWRl/95eKy9kr8e/6BCZscGJGiLw==
X-Received: by 2002:a5d:6704:: with SMTP id o4mr3942172wru.365.1569100588570;
Sat, 21 Sep 2019 14:16:28 -0700 (PDT)
Received: from p200300dd671264687411f8965abf20e0.dip0.t-ipconnect.de
(p200300DD671264687411F8965ABF20E0.dip0.t-ipconnect.de.
[2003:dd:6712:6468:7411:f896:5abf:20e0])
by smtp.gmail.com with ESMTPSA id
v2sm12773894wmf.18.2019.09.21.14.16.27
(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
Sat, 21 Sep 2019 14:16:27 -0700 (PDT)
From: Tamas Blummer <tamas.blummer@gmail.com>
Content-Type: multipart/alternative;
boundary="Apple-Mail=_67460D2A-3269-4541-9006-18E24DCBEF89"
Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.11\))
Date: Sat, 21 Sep 2019 23:16:25 +0200
References: <236E3AB2-4035-4F51-84EE-6F7F57298777@bitaps.com>
To: "admin@bitaps.com" <admin@bitaps.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
In-Reply-To: <236E3AB2-4035-4F51-84EE-6F7F57298777@bitaps.com>
Message-Id: <1ACE761E-A91B-45C7-A0EB-BD66FE3AD7BD@gmail.com>
X-Mailer: Apple Mail (2.3445.104.11)
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Sat, 21 Sep 2019 21:39:42 +0000
Subject: Re: [bitcoin-dev] Block Batch Filters for Light Clients
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
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: Sat, 21 Sep 2019 21:16:31 -0000
--Apple-Mail=_67460D2A-3269-4541-9006-18E24DCBEF89
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
charset=utf-8
Hi Aleksey,
Yes, BIP158 uses the block hash to seed the hash function, which makes =
distinct block filters non-aggregatable=20
for common values. Aggregate fiters on ranges of blocks would have to =
use some other seed and then=20
achive significant savings using the same design.
I think that the most likely use of filters is to decide if a newly =
announced block should be downloaded and=20
not scanning over the entire chain, where aggregate filters would help. =
I also suspect that whole chain=20
scans would be better served with plain sequential reads in map-reduce =
style.
Typical clients do not care of filters for blocks before the birth date =
of their wallet=E2=80=99s keys, so they skip over the=20
majority of history which is a bigger saving than any aggregate filter.
I wish we get a filter committed as commitment would unlock more utility =
than any marginal savings through
more elaborate design.
Tamas Blummer
> On Sep 19, 2019, at 19:20, admin--- via bitcoin-dev =
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>=20
> Hello list,=20
>=20
> Here is a link for a draft of a BIP for compact probabilistic block =
filters alternative of BIP 158
>=20
> =
https://docs.google.com/document/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZzmgkEb_z0qSx=
v80ik/edit?usp=3Dsharing =
<https://docs.google.com/document/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZzmgkEb_z0qS=
xv80ik/edit?usp=3Dsharing>
>=20
> Summary:
>=20
> - BIP 158 false positive rate is low, we can achieve lower bandwidth =
with higher false positive rate filter while sync blockchain
>=20
> - BIP 158 not do not support filter batching by design of used =
parameters for siphash and Golomb coding optimal parameters
>=20
> - Alternative compression with delta coding and splitting data to 2 =
bit string sequences. First for data without prefixes, second one for =
information about bit length written to first sequence.
> Second sequence have a lot of duplicates, compressed with 2 round =
of Huffman algorithm. (Effectivity about 98% vs Golomb with optimal =
parameters)
>=20
> - Block filters batching reduce filter size significantly
>=20
> - Separation of filters by address type allows lite client not to =
download redundant information without compromising privacy.
>=20
> - Lite client filters download strategy: get biggest filter (smallest =
blocks/size rate) for blocks range, in case positive test -> get medium =
filters to reduce blocks range -> get block filters for affected range =
-> download affected blocks over TOR=20
>=20
> Implementation (python): =
https://github.com/bitaps-com/pybtc/blob/bugfix/pybtc/functions/filters.py=
#L172 =
<https://github.com/bitaps-com/pybtc/blob/bugfix/pybtc/functions/filters.p=
y#L172>
>=20
> Exactly information from mainnet about size for separated filters by =
address types and batch size will be added within few days.
>=20
> Thanks for any feedback.
> Aleksey Karpov
>=20
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
--Apple-Mail=_67460D2A-3269-4541-9006-18E24DCBEF89
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
charset=utf-8
<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html; =
charset=3Dutf-8"></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; line-break: after-white-space;" class=3D"">Hi =
Aleksey,<div class=3D""><br class=3D""></div><div class=3D"">Yes, BIP158 =
uses the block hash to seed the hash function, which makes distinct =
block filters non-aggregatable </div><div class=3D"">for common =
values. Aggregate fiters on ranges of blocks would have to use some =
other seed and then </div><div class=3D"">achive significant =
savings using the same design.</div><div class=3D""><br =
class=3D""></div><div class=3D"">I think that the most likely use of =
filters is to decide if a newly announced block should be downloaded =
and </div><div class=3D"">not scanning over the entire chain, where =
aggregate filters would help. I also suspect that whole =
chain </div><div class=3D"">scans would be better served with plain =
sequential reads in map-reduce style.</div><div class=3D""><br =
class=3D""></div><div class=3D"">Typical clients do not care of filters =
for blocks before the birth date of their wallet=E2=80=99s keys, so they =
skip over the </div><div class=3D"">majority of history which is a =
bigger saving than any aggregate filter.</div><div class=3D""><br =
class=3D""></div><div class=3D"">I wish we get a filter committed as =
commitment would unlock more utility than any marginal savings =
through</div><div class=3D"">more elaborate design.</div><div =
class=3D""><br class=3D""></div><div class=3D"">Tamas Blummer</div><div =
class=3D""><br class=3D""></div><div class=3D""><div><blockquote =
type=3D"cite" class=3D""><div class=3D"">On Sep 19, 2019, at 19:20, =
admin--- via bitcoin-dev <<a =
href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" =
class=3D"">bitcoin-dev@lists.linuxfoundation.org</a>> wrote:</div><br =
class=3D"Apple-interchange-newline"><div class=3D""><meta =
http-equiv=3D"Content-Type" content=3D"text/html; charset=3Dus-ascii" =
class=3D""><div style=3D"word-wrap: break-word; -webkit-nbsp-mode: =
space; line-break: after-white-space;" class=3D"">Hello list, <div =
class=3D""><br class=3D""></div><span class=3D"">Here is a link for a =
draft of a BIP for compact probabilistic block filters alternative =
of BIP 158</span><div class=3D""><br class=3D""></div><div class=3D""><a =
href=3D"https://docs.google.com/document/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZzmgk=
Eb_z0qSxv80ik/edit?usp=3Dsharing" =
class=3D"">https://docs.google.com/document/d/1jH9tEUyb9w2OZd4-kxfGuyNIIZz=
mgkEb_z0qSxv80ik/edit?usp=3Dsharing</a></div><div class=3D""><br =
class=3D""></div><div class=3D"">Summary:</div><div class=3D""><br =
class=3D""></div><div class=3D""> - BIP 158 false positive =
rate is low, we can achieve lower bandwidth with higher false positive =
rate filter while sync blockchain</div><div class=3D""><br =
class=3D""></div><div class=3D""> - BIP 158 not do not support =
filter batching by design of used parameters for siphash and Golomb =
coding optimal parameters</div><div class=3D""><br class=3D""></div><div =
class=3D""> - Alternative compression with delta coding and =
splitting data to 2 bit string sequences. First for data without =
prefixes, second one for information about bit length written to =
first sequence.</div><div class=3D""> Second sequence have a =
lot of duplicates, compressed with 2 round of Huffman algorithm. =
(Effectivity about 98% vs Golomb with optimal parameters)</div><div =
class=3D""><br class=3D""></div><div class=3D""> - Block filters =
batching reduce filter size significantly</div><div class=3D""><br =
class=3D""></div><div class=3D"">- Separation of filters by address type =
allows lite client not to download redundant information without =
compromising privacy.</div><div class=3D""><br class=3D""></div><div =
class=3D"">- Lite client filters download strategy: get biggest filter =
(smallest blocks/size rate) for blocks range, in case positive test =
-> get medium filters to reduce blocks range -> get =
block filters for affected range -> download affected blocks over =
TOR </div><div class=3D""><br class=3D""></div><div =
class=3D"">Implementation (python): <a =
href=3D"https://github.com/bitaps-com/pybtc/blob/bugfix/pybtc/functions/fi=
lters.py#L172" =
class=3D"">https://github.com/bitaps-com/pybtc/blob/bugfix/pybtc/functions=
/filters.py#L172</a></div><div class=3D""><br class=3D""></div><div =
class=3D"">Exactly information from mainnet about size for =
separated filters by address types and batch size will be added within =
few days.</div><div class=3D""><br class=3D""></div><div class=3D"">Thanks=
for any feedback.</div><div class=3D""> Aleksey =
Karpov</div><div class=3D""><div class=3D""><span class=3D""><br =
class=3D""></span></div></div></div>______________________________________=
_________<br class=3D"">bitcoin-dev mailing list<br class=3D""><a =
href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" =
class=3D"">bitcoin-dev@lists.linuxfoundation.org</a><br =
class=3D"">https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev<=
br class=3D""></div></blockquote></div><br class=3D""></div></body></html>=
--Apple-Mail=_67460D2A-3269-4541-9006-18E24DCBEF89--
|
