From: Gregory Maxwell <greg@xiph•org>
To: bfd@cock•lu
Cc: Bitcoin Dev <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Committed bloom filters for improved wallet performance and SPV security
Date: Mon, 9 May 2016 08:57:08 +0000 [thread overview]
Message-ID: <CAAS2fgTG6AKDVMMe6kZC5YbZhAkoNiYLh16mfodUR3=Pc_3AyA@mail.gmail.com> (raw)
In-Reply-To: <71d822e413ac457a530e1c367811cc24@cock.lu>
On Mon, May 9, 2016 at 8:26 AM, bfd--- via bitcoin-dev
<bitcoin-dev@lists•linuxfoundation.org> wrote:
> We introduce several concepts that rework the lightweight Bitcoin
> client model in a manner which is secure, efficient and privacy
> compatible.
[...]
> A Bloom Filter Digest is deterministically created of every block
I think this is a fantastic idea.
Some napkin work shows that it has pretty good communications
bandwidth so long as you assume that the wallet has many keys (e.g.
more than the number of the outputs in the block)-- otherwise BIP37
uses less bandwidth, but you note its terrible privacy problems.
You should be aware that when the filter is transmitted but not
updated, as it is in these filtering applications, the bloom filter is
not the most communication efficient data structure.
The most efficient data structure is similar to a bloom filter, but
you use more bits and only one hash function. The result will be
mostly zero bits. Then you entropy code it using RLE+Rice coding or an
optimal binomial packer (e.g.
https://people.xiph.org/~greg/binomial_codec.c). This is about 45%
more space efficient than a bloom filter. ... it's just a PITA to
update, though that is inapplicable here. Entropy coding for this can
be quite fast, if many lookups are done the decompression could even
be faster than having to use two dozen hash functions for each lookup.
The intuition is that this kind of simple hash-bitmap is great, but
space inefficient if you don't have compression since most of the bits
are 0 you end up spending a bit to send less than a bit of
information. A bloom filter improve the situation by using the
multiple filters to increase the ones density to 50%, but the
increased collisions create overhead. This is important when its a
in-memory data-structure that you're updating often, but not here.
One thing to do with matching blocks is after finding the matches the
node could potentially consult some PIR to get the blocks it cares
about... thus preventing a leak of which blocks it was interested in,
but not taking PIR costs for the whole chain or requiring the
implementation of PIR tree search (which is theoretically simple but
in practice hard to implement).
next prev parent reply other threads:[~2016-05-09 8:57 UTC|newest]
Thread overview: 34+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-05-09 8:26 bfd
2016-05-09 8:57 ` Gregory Maxwell [this message]
2016-05-11 20:06 ` Bob McElrath
2016-05-11 20:29 ` Bob McElrath
2016-07-28 21:07 ` Leo Wandersleb
2017-01-06 22:07 ` Erik Aronesty
2017-01-03 20:24 ` bfd
[not found] ` <77b6dd25-0603-a0bd-6a9e-38098e5cb19d@jonasschnelli.ch>
2017-01-03 20:18 ` bfd
2017-01-03 22:18 ` Aaron Voisine
2017-01-03 22:28 ` bfd
2017-01-03 23:06 ` adiabat
2017-01-03 23:46 ` Aaron Voisine
2017-01-04 0:10 ` bfd
2017-01-04 0:36 ` Aaron Voisine
2017-01-04 6:06 ` Eric Voskuil
2017-01-04 16:13 ` Leo Wandersleb
2017-01-04 7:47 ` Jonas Schnelli
2017-01-04 8:56 ` Aaron Voisine
2017-01-04 10:13 ` Jorge Timón
2017-01-04 11:00 ` Adam Back
2017-01-06 2:15 ` bfd
2017-01-06 7:07 ` Aaron Voisine
2017-01-05 7:06 ` Chris Priest
2017-01-05 7:45 ` Eric Voskuil
2017-01-05 14:48 ` Christian Decker
2017-01-06 20:15 ` Chris Priest
2017-01-06 21:35 ` James MacWhyte
2017-01-06 21:50 ` Eric Voskuil
2017-01-06 2:04 ` bfd
2017-03-15 22:36 ` Tom Harding
2017-03-16 0:25 ` bfd
2017-03-16 15:05 ` Tom Harding
2017-02-17 0:28 ` Chris Belcher
2017-04-01 23:49 ` bfd
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='CAAS2fgTG6AKDVMMe6kZC5YbZhAkoNiYLh16mfodUR3=Pc_3AyA@mail.gmail.com' \
--to=greg@xiph$(echo .)org \
--cc=bfd@cock$(echo .)lu \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/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