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
|
Return-Path: <riccardo.casatta@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 842BFDA3
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 4 Jun 2018 08:42:23 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f53.google.com (mail-it0-f53.google.com
[209.85.214.53])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 13B34136
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 4 Jun 2018 08:42:23 +0000 (UTC)
Received: by mail-it0-f53.google.com with SMTP id j186-v6so9199034ita.5
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 04 Jun 2018 01:42:22 -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=jTKO/ZM1/bIQ2vg/DOnIpOuDINM7/DKZolNZgLHA/pQ=;
b=nrsyib+Np6idpTtJmJTFtGLnTubB6W0YdSiZIzYAHjsfIiJn5bHrC61g2Mezh7NRLi
x1I+R3YZN07Ou5X98h0Bxg/vc6B3Dx+uxb3t5qVoxO9n+5ya3eeVNsbLdaoUBuAacVV/
W4Qu85l9dquckTzXYn4tCSvbPFaMzAVEGxW8nIDb852+TYvy93iq+UyAIGpgT3F1AONS
wt5UtPa8E8REHAtDbPjKFIpDkKWaqwEtjHSCuLbH1yC7499olxV8vB3/8GlkDAYHDkbv
0ROxgnh1IuAtweM9lkQOJG4zEDoVPdBnNrMrPCdt5rxvBAIT6KmhFuaP2MpBEblN7M00
9a1g==
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=jTKO/ZM1/bIQ2vg/DOnIpOuDINM7/DKZolNZgLHA/pQ=;
b=YcnmMjxQSXVTIRRRhPIWiMz1RM3E0YpZJxnoybzALzr+6ytqJ5qqS1oWQ8QjZGgxlb
3Bn1znxZpCfObczRAvcywe+wddeqBf1svwRG1ru60LUndk+6zGXVeT78Eb3Mv9cs7ECc
Bt71jXq5pFQRkk20ijHDHrhZLsX1c5rl1jKa4UK/dHKzKdauVZDSWe9MxAeR2MOqOF/p
+JUZfor5h5fX+8YKORQQMWkxX5XhPrgHC6aKbPnqi0+dLPGEnZHJpy6+e2nSTQJUzE5b
HRVqT/79L2Y8b4iummQ8Zwb21SbVod+vQrJL5IXBCANIJQJZuNJ7ScmQA5W/OMis6hZs
/vaA==
X-Gm-Message-State: APt69E0ahc6ND7Vp+CXvO9++EfytYM4pWsaG6hAQy+zxi3ElDvamrU3l
PTmP8RA+tPM+3mKG3Ni2LrmuP6IwKwQ+d13MmG0=
X-Google-Smtp-Source: ADUXVKLtBQ8pKcZ8lCJmlLmSXcKe0Vn6aKfybQXHDc9fIjp65INDMCjCJN7jdpWU0UD+AW5tgCm5EalXfIVVHU/9MCo=
X-Received: by 2002:a24:5112:: with SMTP id
s18-v6mr10566062ita.151.1528101742343;
Mon, 04 Jun 2018 01:42:22 -0700 (PDT)
MIME-Version: 1.0
References: <d43c6082-1b2c-c95b-5144-99ad0021ea6c@mattcorallo.com>
<CALJw2w7+VUYtMtdTexW6iE3mc0DsS9DME_ynP8skg_+-bv_tPA@mail.gmail.com>
In-Reply-To: <CALJw2w7+VUYtMtdTexW6iE3mc0DsS9DME_ynP8skg_+-bv_tPA@mail.gmail.com>
From: Riccardo Casatta <riccardo.casatta@gmail.com>
Date: Mon, 4 Jun 2018 10:42:10 +0200
Message-ID: <CADabwBDG2_2syU0AnjbEfqTL=5ERRQkL6NOyVN7gAyJTAaf7UA@mail.gmail.com>
To: karljohan-alm@garage.co.jp,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000887cf9056dcce976"
X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,RCVD_IN_DNSWL_LOW
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: Mon, 04 Jun 2018 14:26:50 +0000
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: Mon, 04 Jun 2018 08:42:23 -0000
--000000000000887cf9056dcce976
Content-Type: text/plain; charset="UTF-8"
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>
--000000000000887cf9056dcce976
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_default" style=3D"font-size:small">I w=
as wondering why this multi-layer multi-block filter proposal isn't get=
ting any comment,</div><div class=3D"gmail_default" style=3D"font-size:smal=
l">is it because not asking all filters is leaking information?</div><div c=
lass=3D"gmail_default" style=3D"font-size:small"><br></div><div class=3D"gm=
ail_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:bitcoin-dev@lists.linuxfou=
ndation.org">bitcoin-dev@lists.linuxfoundation.org</a>> ha scritto:<br><=
/div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-le=
ft:1px #ccc solid;padding-left:1ex">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"gmail_signature" data-smartmail=3D"gmail_signature"><div dir=3D"l=
tr">Riccardo Casatta - <a href=3D"https://twitter.com/RCasatta" target=3D"_=
blank">@RCasatta</a></div></div>
--000000000000887cf9056dcce976--
|
