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
|
Return-Path: <jim.posen@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 9D137C75
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 5 Jun 2018 17:22:17 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-qt0-f178.google.com (mail-qt0-f178.google.com
[209.85.216.178])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 296546EE
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 5 Jun 2018 17:22:17 +0000 (UTC)
Received: by mail-qt0-f178.google.com with SMTP id s9-v6so3267171qtg.2
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 05 Jun 2018 10:22:17 -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=5wpSKXqSBrjmir9m9BvTJrEFLOzcqCa+yTYdQ1pGXO8=;
b=OfrgCcsg2cZMO3sVOCtLM8XHM8Jy9+pKFk3ApQvuxTp4SmYGzqTMkoaqehZCCdWCK5
Tp+Kj3RKnPiRlnwxxauo2HsDSw7/yl3TSKo64obqli1kpFDQ0+eyS49w7QX6rMggPqqK
ZWlCeaPzseAb2tOc8VokyqLJUkSq+J83OW9tE86C4BvuV+yEZxfBAOs868iq/jUUx2wY
Xv8nREV/k6r9EzHMgiK+sp0TOKAt0GyfP+luv+WcZm8D22+21CjCkdpmFL3Sr9tBu18S
2nlGftbgFYueaLVzbBqtEWRA4HefpIVZDQgw7SqrEDgEQmGu4uMnyXaV8iZ0a01KqLIi
zt1A==
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=5wpSKXqSBrjmir9m9BvTJrEFLOzcqCa+yTYdQ1pGXO8=;
b=JkQLHSd2+ogdnCgY0YwvjN3tm2Z3UZuWeyI44PrjYdAnI1I8U13iZawG5S9CpnRSrP
tG3ag8YlA0Rxx9G9a9SiBdcuJ7/HmNGt4hIcCT2fZYbOUnjewJ36AQERtb0y6XxLsYtV
3He2uYoZOVNdJ/HFZUjXuD011jEX0gBEZJAEwkH0zP28fx5xFGdnUz3brk+kRL4J1SgX
2WeS7tQ0Zv5F4VYPZHhc3qQ4R0Q4e6GUfT5mZRow3THpN1IAmiNK2TRrKim1xBMrtCT8
JJ/qMtmS0/t8DTDoWhWdOdoMj1JB4CKQY6HHJ8MgOVvCO425PDTdwWBQdo9yAmMvYod1
AP2g==
X-Gm-Message-State: APt69E0LGHNxK1OHBc3OaBNW+rl2dy2oEApTWIcDImPb55noxotUeKn3
gUcaHsKrzPRdNuRbNS4cP/HGfyaBbBVBqbpR4cM=
X-Google-Smtp-Source: ADUXVKIMknoZQVYTkXo4j3qfal0v9qmSfKvoAN+gHkhhSPzSpTjqjFVkoxqeND7U8ZIdf4ETJFJ9L0mOYSy4ZUA+vcA=
X-Received: by 2002:ac8:2f99:: with SMTP id
l25-v6mr24540263qta.166.1528219336206;
Tue, 05 Jun 2018 10:22:16 -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>
<CADZtCSjsZ=_C+cFUXbAim=56QG4p0UdE4HEo9ZKJtNgEH_DqhQ@mail.gmail.com>
<CALJw2w5FY3EoqtA4HTJr8CCwZ-Dyf=XVbO8Hd=TDjxBEgwLULQ@mail.gmail.com>
In-Reply-To: <CALJw2w5FY3EoqtA4HTJr8CCwZ-Dyf=XVbO8Hd=TDjxBEgwLULQ@mail.gmail.com>
From: Jim Posen <jim.posen@gmail.com>
Date: Tue, 5 Jun 2018 10:22:04 -0700
Message-ID: <CADZtCShgQ-Jho3kH2Gy+CCiCeNX01UF0oo5AGKMaRw=SaOfwmw@mail.gmail.com>
To: Karl Johan Alm <karljohan-alm@garage.co.jp>
Content-Type: multipart/alternative; boundary="000000000000ac700f056de84aa9"
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: Tue, 05 Jun 2018 17:38:31 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.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: Tue, 05 Jun 2018 17:22:17 -0000
--000000000000ac700f056de84aa9
Content-Type: text/plain; charset="UTF-8"
>
> I don't understand this comment. The bandwidth gains are not from
> address reuse, they are from the observed property that false
> positives are independent between two filters. I.e. clients that
> connect once a day will probably download 2-3 filters at most, if they
> had nothing relevant in the last ~144 blocks.
>
Your multi-layer digest proposal (https://bc-2.jp/bfd-profile.pdf) uses a
different type of filter which seems more like a compressed Bloom filter if
I understand it correctly. Appendix A shows how the FP rate increases with
the number of elements.
With the Golomb-Coded Sets, the filter size increases linearly in the
number of elements for a fixed FP rate. So currently we are targeting an
~1/2^20 rate (actually 1/784931 now), and filter sizes are ~20 bits * N for
N elements. With a 1-layer digest covering let's say 16 blocks, you could
drop the FP rate on the digest filters and the block filters each to ~10
bits per element, I think, to get the same FP rate for a given block by
your argument of independence. But the digest is only half the size of the
16 combined filters and there's a high probability of downloading the other
half anyway. So unless there is greater duplication of elements in the
digest filters, it's not clear to me that there are great bandwidth
savings. But maybe there are. Even so, I think we should just ship the
block filters and consider multi-layer digests later.
--000000000000ac700f056de84aa9
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_quote"><blockquote class=3D"gmail_quot=
e" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204)=
;padding-left:1ex">I don't understand this comment. The bandwidth gains=
are not from<br>
address reuse, they are from the observed property that false<br>
positives are independent between two filters. I.e. clients that<br>
connect once a day will probably download 2-3 filters at most, if they<br>
had nothing relevant in the last ~144 blocks.<br></blockquote><div><br></di=
v><div>Your multi-layer digest proposal (<a href=3D"https://bc-2.jp/bfd-pro=
file.pdf">https://bc-2.jp/bfd-profile.pdf</a>) uses a different type of fil=
ter which seems more like a compressed Bloom filter if I understand it corr=
ectly. Appendix A shows how the FP rate increases with the number of elemen=
ts.</div><div><br></div><div>With the Golomb-Coded Sets, the filter size in=
creases linearly in the number of elements for a fixed FP rate. So currentl=
y we are targeting an ~1/2^20 rate (actually 1/<span style=3D"color:rgb(34,=
34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant=
-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:n=
ormal;text-align:start;text-indent:0px;text-transform:none;white-space:norm=
al;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style=
:initial;text-decoration-color:initial;float:none;display:inline">784931 no=
w), and filter sizes are ~20 bits * N for N elements. With a 1-layer digest=
covering let's say 16 blocks, you could drop the FP rate on the digest=
filters and the block filters each to ~10 bits per element, I think, to ge=
t the same FP rate for a given block by your argument of independence. But =
the digest is only half the size of the 16 combined filters and there's=
a high probability of downloading the other half anyway. So unless there i=
s greater duplication of elements in the digest filters, it's not clear=
to me that there are great bandwidth savings. But maybe there are. Even so=
, I think we should just ship the block filters and consider multi-layer di=
gests later.</span></div></div></div>
--000000000000ac700f056de84aa9--
|
