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
|
Return-Path: <laolu32@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 8548089B
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 6 Jun 2018 01:13:09 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f50.google.com (mail-wm0-f50.google.com [74.125.82.50])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 8CB9E71A
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 6 Jun 2018 01:13:08 +0000 (UTC)
Received: by mail-wm0-f50.google.com with SMTP id j15-v6so8685032wme.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 05 Jun 2018 18:13:08 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to
:cc; bh=0W5Eyv3IYPZ52+lKYVEamWjuKQvNz7Iy58fwaUeyIfY=;
b=UrVDxN2ZSuG8e2xqcm42dryTLgJF148c4PPuL8LNeCI68TD2oc9H+vy7p03EIc1Ona
sX+NgxyN25pJAUoRip+gXNfNRHClqXYp7lz/wLTFK9vScQ/gubb2PjNYbpl0Ex2qIk1E
pz5WBM/1/kfCvJC0GyiiESGhtBHnECdpf1OZXqLZ+bFmNt0WQyKcEAqrVkgxSU+qc3WJ
ySSJfOCAt7kO3OIOLiHna6C5zqrsi1xhWVf7FoOKW3oKIl9OjdkCADWhZ3kFLBzwE362
dURTNwPxmIef181cFDSvYq4T53zYWVIdzjJen/pXvNYjyZSehCRolf2eXwoDlnqPIQXh
SIrg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:references:in-reply-to:from:date
:message-id:subject:to:cc;
bh=0W5Eyv3IYPZ52+lKYVEamWjuKQvNz7Iy58fwaUeyIfY=;
b=OeuJMSXi4jWYf+e4QzZIJ2SYoAxcdLJFfdTiUdXL/wPDAtGfvaa1fy0np4qHqlFk2G
e4MaGodd8S9K9FDDu1QqbFyTzcYswC9DxOl3ZtFa3lvpQ2BOm2tU1Df/T9ZoJNUlo7nW
6jeJeTmghrylBFEhwLZFdpUjHeaQUj1OI9omoBXqqHeSQL60xnpvaETDn8L2046yRsOL
tP9W+fcAn4F0icJPRnIi+3c4wweYC8eoityVT+pT/168Q/t/bUkL9gvWLffUrn3srsCj
BQIgqpkA15pfoTuGgUaNTZIAKwVVtRxy1tkvSHV/7+Q3JJlVc46/+NeEgTu+LVJ/5NVi
i8Fw==
X-Gm-Message-State: APt69E16q0bX7aC/smW82RwNFbO9BZkDpSjp6Sympn+ZFheK1PJQpWOn
BBo57bEOL/EA2pZtTGl2zSa/b8iee9h02UHBvQA=
X-Google-Smtp-Source: ADUXVKJp/cwpwo52/PiCO2otiURzPprXlUrMSUhfwmtZb2N7INfY5wSBex4dr4eXWr4I8JglzhAbfnNmXQ6SlTfan8I=
X-Received: by 2002:a50:b6bc:: with SMTP id
d57-v6mr1310845ede.250.1528247587152;
Tue, 05 Jun 2018 18:13:07 -0700 (PDT)
MIME-Version: 1.0
References: <d43c6082-1b2c-c95b-5144-99ad0021ea6c@mattcorallo.com>
<CALJw2w7+VUYtMtdTexW6iE3mc0DsS9DME_ynP8skg_+-bv_tPA@mail.gmail.com>
<CADabwBDG2_2syU0AnjbEfqTL=5ERRQkL6NOyVN7gAyJTAaf7UA@mail.gmail.com>
In-Reply-To: <CADabwBDG2_2syU0AnjbEfqTL=5ERRQkL6NOyVN7gAyJTAaf7UA@mail.gmail.com>
From: Olaoluwa Osuntokun <laolu32@gmail.com>
Date: Tue, 5 Jun 2018 18:12:55 -0700
Message-ID: <CAO3Pvs9tXte=_1UBPvLmrci+PD9QVbiKHu4R_6igpAEuQLJ3Wg@mail.gmail.com>
To: Riccardo Casatta <riccardo.casatta@gmail.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000008fa85b056deede81"
X-Spam-Status: No, score=-1.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID,DKIM_VALID_AU,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,
HTML_MESSAGE,RCVD_IN_DNSWL_NONE autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size
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: Wed, 06 Jun 2018 01:13:09 -0000
--0000000000008fa85b056deede81
Content-Type: text/plain; charset="UTF-8"
It isn't being discussed atm (but was discussed 1 year ago when the BIP
draft was originally published), as we're in the process of removing items
or filters that aren't absolutely necessary. We're now at the point where
there're no longer any items we can remove w/o making the filters less
generally useful which signals a stopping point so we can begin widespread
deployment.
In terms of a future extension, BIP 158 already defines custom filter types,
and BIP 157 allows filters to be fetched in batch based on the block height
and numerical range. The latter feature can later be modified to return a
single composite filter rather than several individual filters.
-- Laolu
On Mon, Jun 4, 2018 at 7:28 AM Riccardo Casatta via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> I was wondering why this multi-layer multi-block filter proposal isn't
> getting any comment,
> is it because not asking all filters is leaking information?
>
> Thanks
>
> Il giorno ven 18 mag 2018 alle ore 08:29 Karl-Johan Alm via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> ha scritto:
>
>> On Fri, May 18, 2018 at 12:25 AM, Matt Corallo via bitcoin-dev
>> <bitcoin-dev@lists.linuxfoundation.org> wrote:
>> > In general, I'm concerned about the size of the filters making existing
>> > SPV clients less willing to adopt BIP 158 instead of the existing bloom
>> > filter garbage and would like to see a further exploration of ways to
>> > split out filters to make them less bandwidth intensive. Some further
>> > ideas we should probably play with before finalizing moving forward is
>> > providing filters for certain script templates, eg being able to only
>> > get outputs that are segwit version X or other similar ideas.
>>
>> There is also the idea of multi-block filters. The idea is that light
>> clients would download a pair of filters for blocks X..X+255 and
>> X+256..X+511, check if they have any matches and then grab pairs for
>> any that matched, e.g. X..X+127 & X+128..X+255 if left matched, and
>> iterate down until it ran out of hits-in-a-row or it got down to
>> single-block level.
>>
>> This has an added benefit where you can accept a slightly higher false
>> positive rate for bigger ranges, because the probability of a specific
>> entry having a false positive in each filter is (empirically speaking)
>> independent. I.e. with a FP probability of 1% in the 256 range block
>> and a FP probability of 0.1% in the 128 range block would mean the
>> probability is actually 0.001%.
>>
>> Wrote about this here: https://bc-2.jp/bfd-profile.pdf (but the filter
>> type is different in my experiments)
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>
>
> --
> Riccardo Casatta - @RCasatta <https://twitter.com/RCasatta>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
--0000000000008fa85b056deede81
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>It isn't being discussed atm (but was discussed 1=
year ago when the BIP</div><div>draft was originally published), as we'=
;re in the process of removing items</div><div>or filters that aren't a=
bsolutely necessary. We're now at the point where</div><div>there'r=
e no longer any items we can remove w/o making the filters less</div><div>g=
enerally useful which signals a stopping point so we can begin widespread</=
div><div>deployment.=C2=A0=C2=A0</div><div><br></div><div>In terms of a fut=
ure extension, BIP 158 already defines custom filter types,</div><div>and B=
IP 157 allows filters to be fetched in batch based on the block height</div=
><div>and numerical range. The latter feature can later be modified to retu=
rn a</div><div>single composite filter rather than several individual filte=
rs.</div><div><br></div><div>-- Laolu</div><div><br></div><br><div class=3D=
"gmail_quote"><div dir=3D"ltr">On Mon, Jun 4, 2018 at 7:28 AM Riccardo Casa=
tta via bitcoin-dev <<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation=
.org">bitcoin-dev@lists.linuxfoundation.org</a>> wrote:<br></div><blockq=
uote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc =
solid;padding-left:1ex"><div dir=3D"ltr"><div class=3D"gmail_default" style=
=3D"font-size:small">I was wondering why this multi-layer multi-block filte=
r proposal isn't getting any comment,</div><div class=3D"gmail_default"=
style=3D"font-size:small">is it because not asking all filters is leaking =
information?</div><div class=3D"gmail_default" style=3D"font-size:small"><b=
r></div><div class=3D"gmail_default" style=3D"font-size:small">Thanks</div>=
</div><br><div class=3D"gmail_quote"><div dir=3D"ltr">Il giorno ven 18 mag =
2018 alle ore 08:29 Karl-Johan Alm via bitcoin-dev <<a href=3D"mailto:bi=
tcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.li=
nuxfoundation.org</a>> ha scritto:<br></div><blockquote class=3D"gmail_q=
uote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1e=
x">On Fri, May 18, 2018 at 12:25 AM, Matt Corallo via bitcoin-dev<br>
<<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_bla=
nk">bitcoin-dev@lists.linuxfoundation.org</a>> wrote:<br>
> In general, I'm concerned about the size of the filters making exi=
sting<br>
> SPV clients less willing to adopt BIP 158 instead of the existing bloo=
m<br>
> filter garbage and would like to see a further exploration of ways to<=
br>
> split out filters to make them less bandwidth intensive. Some further<=
br>
> ideas we should probably play with before finalizing moving forward is=
<br>
> providing filters for certain script templates, eg being able to only<=
br>
> get outputs that are segwit version X or other similar ideas.<br>
<br>
There is also the idea of multi-block filters. The idea is that light<br>
clients would download a pair of filters for blocks X..X+255 and<br>
X+256..X+511, check if they have any matches and then grab pairs for<br>
any that matched, e.g. X..X+127 & X+128..X+255 if left matched, and<br>
iterate down until it ran out of hits-in-a-row or it got down to<br>
single-block level.<br>
<br>
This has an added benefit where you can accept a slightly higher false<br>
positive rate for bigger ranges, because the probability of a specific<br>
entry having a false positive in each filter is (empirically speaking)<br>
independent. I.e. with a FP probability of 1% in the 256 range block<br>
and a FP probability of 0.1% in the 128 range block would mean the<br>
probability is actually 0.001%.<br>
<br>
Wrote about this here: <a href=3D"https://bc-2.jp/bfd-profile.pdf" rel=3D"n=
oreferrer" target=3D"_blank">https://bc-2.jp/bfd-profile.pdf</a> (but the f=
ilter<br>
type is different in my experiments)<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div><br clear=3D"all"><div><br></div>-- <br><div dir=3D"ltr"=
class=3D"m_-7236474083222447233gmail_signature" data-smartmail=3D"gmail_si=
gnature"><div dir=3D"ltr">Riccardo Casatta - <a href=3D"https://twitter.com=
/RCasatta" target=3D"_blank">@RCasatta</a></div></div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div></div>
--0000000000008fa85b056deede81--
|
