From: Jim Posen <jim.posen@gmail•com>
To: Karl Johan Alm <karljohan-alm@garage•co.jp>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size
Date: Tue, 5 Jun 2018 10:22:04 -0700 [thread overview]
Message-ID: <CADZtCShgQ-Jho3kH2Gy+CCiCeNX01UF0oo5AGKMaRw=SaOfwmw@mail.gmail.com> (raw)
In-Reply-To: <CALJw2w5FY3EoqtA4HTJr8CCwZ-Dyf=XVbO8Hd=TDjxBEgwLULQ@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 1428 bytes --]
>
> 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.
[-- Attachment #2: Type: text/html, Size: 2134 bytes --]
next prev parent reply other threads:[~2018-06-05 17:22 UTC|newest]
Thread overview: 60+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-05-17 15:25 Matt Corallo
2018-05-17 15:43 ` Peter Todd
2018-05-17 15:46 ` Matt Corallo
2018-05-17 16:36 ` Gregory Maxwell
2018-05-17 16:59 ` Matt Corallo
2018-05-17 18:34 ` Gregory Maxwell
2018-05-17 18:34 ` Gregory Maxwell
2018-05-17 20:19 ` Jim Posen
2018-05-17 20:45 ` Gregory Maxwell
2018-05-17 21:27 ` Jim Posen
2018-05-19 3:12 ` Olaoluwa Osuntokun
2018-05-21 8:35 ` Johan Torås Halseth
2018-05-22 1:16 ` Olaoluwa Osuntokun
2018-05-22 9:23 ` Johan Torås Halseth
2018-05-23 0:42 ` Jim Posen
2018-05-23 7:38 ` Jim Posen
2018-05-23 8:16 ` Johan Torås Halseth
2018-05-23 17:28 ` Gregory Maxwell
2018-05-24 1:04 ` Conner Fromknecht
2018-05-24 3:48 ` Jim Posen
2018-05-28 18:18 ` Tamas Blummer
2018-05-28 18:28 ` Tamas Blummer
2018-05-28 19:24 ` Gregory Maxwell
2018-05-29 2:42 ` Jim Posen
2018-05-29 3:24 ` Gregory Maxwell
2018-05-29 4:01 ` Olaoluwa Osuntokun
2018-05-31 14:27 ` Tamas Blummer
2018-06-01 2:52 ` Olaoluwa Osuntokun
2018-06-01 4:15 ` Gregory Maxwell
[not found] ` <CAAS2fgSyVi0d_ixp-auRPPzPfFeffN=hsWhWT5=EzDO3O+Ue1g@mail.gmail.com>
2018-06-02 0:01 ` Olaoluwa Osuntokun
2018-06-02 0:22 ` Gregory Maxwell
2018-06-02 2:02 ` Jim Posen
2018-06-02 12:41 ` David A. Harding
2018-06-02 22:02 ` Tamas Blummer
2018-06-03 0:28 ` Gregory Maxwell
2018-06-03 5:14 ` Tamas Blummer
2018-06-03 6:11 ` Pieter Wuille
2018-06-03 16:44 ` Tamas Blummer
2018-06-03 16:50 ` Tamas Blummer
2018-06-08 5:03 ` Olaoluwa Osuntokun
2018-06-08 16:14 ` Gregory Maxwell
2018-06-08 23:35 ` Olaoluwa Osuntokun
2018-06-09 10:34 ` David A. Harding
2018-06-12 23:51 ` Olaoluwa Osuntokun
2018-06-09 15:45 ` Gregory Maxwell
2018-06-12 23:58 ` Olaoluwa Osuntokun
2018-05-18 8:46 ` Riccardo Casatta
2018-05-19 3:08 ` Olaoluwa Osuntokun
2018-05-19 2:57 ` Olaoluwa Osuntokun
2018-05-19 3:06 ` Pieter Wuille
2018-05-22 1:15 ` Olaoluwa Osuntokun
2018-05-18 6:28 ` Karl-Johan Alm
2018-06-04 8:42 ` Riccardo Casatta
2018-06-05 1:08 ` Jim Posen
2018-06-05 4:33 ` Karl-Johan Alm
2018-06-05 17:22 ` Jim Posen [this message]
2018-06-05 17:52 ` Gregory Maxwell
2018-06-06 1:12 ` Olaoluwa Osuntokun
2018-06-06 15:14 ` Riccardo Casatta
2018-05-19 2:51 ` Olaoluwa Osuntokun
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CADZtCShgQ-Jho3kH2Gy+CCiCeNX01UF0oo5AGKMaRw=SaOfwmw@mail.gmail.com' \
--to=jim.posen@gmail$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=karljohan-alm@garage$(echo .)co.jp \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox