[Bitcoin-development] Draft BIP for Bloom filtering

[Bitcoin-development] Draft BIP for Bloom filtering

[Mike Hearn]

I've written a draft BIP describing the bloom filtering protocol
extension developed by myself and Matt.

https://en.bitcoin.it/wiki/BIP_0037

(yes I know there's some kind of process around getting allocated a
number - it seems overkill for this).

Please read it and let me know if there are any missing details or
things which sound wrong.

Design-wise, it occurred to me as I wrote the BIP that the method of
delaying reception of invs is a bit ad-hoc. It may be better to have a
bloom filter be sent in the version message itself. On the other hand,
having a flag to delay invs means that the filter can be calculated in
parallel to bringing up the network connections. Whilst actually
making a Bloom filter is fast, with deterministic wallets you may need
to do a lot of calculations to find the keys to scan for.

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Pieter Wuille]

On Wed, Oct 24, 2012 at 05:56:07PM +0200, Mike Hearn wrote:
> I've written a draft BIP describing the bloom filtering protocol
> extension developed by myself and Matt.
> 
> https://en.bitcoin.it/wiki/BIP_0037
> 
> Please read it and let me know if there are any missing details or
> things which sound wrong.

Some questions:
* why limit the number of matching transactions to 255?
* what does "each hash and key in the output script" mean exactly? what about the output script in its entirety?
* is sharing parts of the merkle branches not worth it?

> Design-wise, it occurred to me as I wrote the BIP that the method of
> delaying reception of invs is a bit ad-hoc. It may be better to have a
> bloom filter be sent in the version message itself. On the other hand,
> having a flag to delay invs means that the filter can be calculated in
> parallel to bringing up the network connections. Whilst actually
> making a Bloom filter is fast, with deterministic wallets you may need
> to do a lot of calculations to find the keys to scan for.

I'm not in favor of stuffing too much into the version message, it already seems overloaded.
A byte with some bit-flags is fine by me - higher bits can later be added for other boolean
flags.

-- 
Pieter

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 446 bytes --]

> Some questions:
> * why limit the number of matching transactions to 255?

Copy/paste error in the does :(

> * what does "each hash and key in the output script" mean exactly? what
about the output script in its entirety?

It's an informal way to say data elements. If you insert a key then it
matches both single and multi sig outputs regardless of location.

> * is sharing parts of the merkle branches not worth it?

We think probably not.

[-- Attachment #2: Type: text/html, Size: 530 bytes --]

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Pieter Wuille]

On Wed, Oct 24, 2012 at 06:35:08PM +0200, Mike Hearn wrote:
> > * what does "each hash and key in the output script" mean exactly? what
> about the output script in its entirety?
> 
> It's an informal way to say data elements. If you insert a key then it
> matches both single and multi sig outputs regardless of location.

So all data push operations? Including or excluding 1-byte constants?

What about the entire output script? (if I want to match just one particular multisig output script)

> 
> > * is sharing parts of the merkle branches not worth it?
> 
> We think probably not.

I'm not sure. As soon as you have 129 transactions in a block (including coinbase), you need 8 path
entries for each included transaction, which requires more bytes than the transaction itself.

When you're including M out of N transactions of a block, you never need more than N-M path entries
in total to reconstruct the merkle root. With the proposed format, it requires M*ceil(log2(N)).

For a 1000-transaction block, when matching ~everything, you need >300 KiB of overhead, while almost
nothing is required.

-- 
Pieter

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Gavin Andresen]

RE: sharing parts of the merkle branches when returning a 'merkleblock' :

I think I agree that complicating the BIP for what should be a very
rare case (more than a handful of transactions in a block match the
transactions in your wallet) is the right decision.

I want to make sure I'm understanding this bit correctly:

"In addition, because a merkleblock message contains only a list of
transaction hashes, any transactions that the requesting node hasn't
either received or announced with an inv will be automatically sent as
well. This avoids a slow roundtrip that would otherwise be required
(receive hashes, didn't see some of these transactions yet, ask for
them)."

Requiring serving/relaying nodes to keep track of which transactions
they have or have not sent to their peers makes me nervous. I think
requiring an extra 'inv' round-trip would be simpler to implement and
less likely to lead to some kind of DoS attack.

-- 
--
Gavin Andresen

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Matt Corallo]

On Wed, 2012-10-24 at 14:54 -0400, Gavin Andresen wrote:
> RE: sharing parts of the merkle branches when returning a 'merkleblock' :
> 
> I think I agree that complicating the BIP for what should be a very
> rare case (more than a handful of transactions in a block match the
> transactions in your wallet) is the right decision.
I believe you meant NOT complicating?
> 
> I want to make sure I'm understanding this bit correctly:
> 
> "In addition, because a merkleblock message contains only a list of
> transaction hashes, any transactions that the requesting node hasn't
> either received or announced with an inv will be automatically sent as
> well. This avoids a slow roundtrip that would otherwise be required
> (receive hashes, didn't see some of these transactions yet, ask for
> them)."
> 
> Requiring serving/relaying nodes to keep track of which transactions
> they have or have not sent to their peers makes me nervous. I think
> requiring an extra 'inv' round-trip would be simpler to implement and
> less likely to lead to some kind of DoS attack.
> 
Sadly that requires (potentially) more DoS potential because you require
nodes to store each transaction that could be requested instead of just
going ahead and forwarding them.  I agree the BIP should not specify
that the sending node is required to keep track of which transactions
have been announced/sent to clients, however since the reference client
does so currently, that implementation is significantly simpler (note
that it is a bounded set in the reference client, so even the reference
client doesn't really fully comply with the BIP as stated here).  

Matt

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 1326 bytes --]

Bitcoin already keeps track of which nodes have seen what to avoid
redundant inv announcements.

I think if you are approaching most transactions in a block matching the
filter then you would just request full blocks and do all the filtering
client side
On Oct 24, 2012 8:54 PM, "Gavin Andresen" <gavinandresen@gmail.com> wrote:

> RE: sharing parts of the merkle branches when returning a 'merkleblock' :
>
> I think I agree that complicating the BIP for what should be a very
> rare case (more than a handful of transactions in a block match the
> transactions in your wallet) is the right decision.
>
> I want to make sure I'm understanding this bit correctly:
>
> "In addition, because a merkleblock message contains only a list of
> transaction hashes, any transactions that the requesting node hasn't
> either received or announced with an inv will be automatically sent as
> well. This avoids a slow roundtrip that would otherwise be required
> (receive hashes, didn't see some of these transactions yet, ask for
> them)."
>
> Requiring serving/relaying nodes to keep track of which transactions
> they have or have not sent to their peers makes me nervous. I think
> requiring an extra 'inv' round-trip would be simpler to implement and
> less likely to lead to some kind of DoS attack.
>
> --
> --
> Gavin Andresen
>

[-- Attachment #2: Type: text/html, Size: 1685 bytes --]

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Gavin Andresen]

On Wed, Oct 24, 2012 at 3:10 PM, Mike Hearn <mike@plan99.net> wrote:
> Bitcoin already keeps track of which nodes have seen what to avoid redundant
> inv announcements.

Oops, right. That memory usage is bounded right now by bounds on the
memory pool size, though, right? (I'm being lazy and not digging into
that code)

What is the worst-case for an attacker interested in trying to get you
to saturate your upstream bandwidth or use lots of memory?  Set a
bloom filter that matches everything, and then start requesting old
blocks in the chain? It would be nice if the worst-case was no worse
than the worst-case we've got now (... requesting full, old
blocks...).

-- 
--
Gavin Andresen

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Mike Hearn]

> What is the worst-case for an attacker interested in trying to get you
> to saturate your upstream bandwidth or use lots of memory?  Set a
> bloom filter that matches everything, and then start requesting old
> blocks in the chain?

It would be slightly worse than shipping a full block but not seriously so.

If you just want to saturate bandwidth or disk IOPS you could probably
just request random blocks over and over again.

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Jeff Garzik]

On Wed, Oct 24, 2012 at 4:29 PM, Gavin Andresen <gavinandresen@gmail.com> wrote:
> Oops, right. That memory usage is bounded right now by bounds on the
> memory pool size, though, right? (I'm being lazy and not digging into
> that code)

Correct me if I'm wrong but...  I do not think there is any bound on
mempool size.

My proposal to age-out long-unconfirmed transactions is related, but
does not completely solve the unbounded-size issue.

-- 
Jeff Garzik
exMULTI, Inc.
jgarzik@exmulti.com

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Gregory Maxwell]

On Wed, Oct 24, 2012 at 11:56 AM, Mike Hearn <mike@plan99.net> wrote:
> I've written a draft BIP describing the bloom filtering protocol
> extension developed by myself and Matt.
>
> https://en.bitcoin.it/wiki/BIP_0037

Thanks for taking the time to write this up.

I still don't understand what purpose the apparently gratuitous
inefficiency of constantly resending common tree fragments. There are
many points of complexity in this protocol— handling premature
disconnections without missing blocks, the actual implementation of
the hash functions for the filter, validation of the hash tree, etc.
Presumably these components will just get implemented a few times in
some carefully constructed library code, so I don't see an
implementation complexity argument here— except the fact that it isn't
what Matt has implemented so far.

The current design can cause massive overhead compared to pulling an
unfiltered block should a filter be somewhat overboard and also makes
this filtering useless for applications which would select a small but
not tiny subset of the transactions (e.g. 10%).

Also, it's not mentioned in the page— but the hash function used is
not cryptographically strong,  so what prevents a complexity (well,
bandwidth in this case) attack?  someone could start using txids and
txouts that collide with the maximum number of other existing txouts
in order to waste bandwidth for people.  Is this avenue of attack not
a concern?

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Gregory Maxwell]

On Thu, Oct 25, 2012 at 12:56 PM, Gregory Maxwell <gmaxwell@gmail.com> wrote:
> I still don't understand what purpose the apparently gratuitous
> inefficiency of constantly resending common tree fragments.

Sorry for the rapid additional comment, but I should also have
mentioned that the in efficiency is at odds with the privacy argument
for the particular mechanism... if the filter is not set at least
somewhat too broadly then it will uniquely identify the user. The
inefficiency, however, argues for setting the filter as narrowly as
possible because there is much more bandwidth used for a wider filter
than would be otherwise.

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Mike Hearn]

> Presumably these components will just get implemented a few times in
> some carefully constructed library code, so I don't see an
> implementation complexity argument here— except the fact that it isn't
> what Matt has implemented so far.

Well, yes, that is basically the implementation complexity argument :)
Engineering time isn't free.

I don't feel I understand the effort required to do some kind of
partial tree encoding. Having a kind of custom compression whereby
branches are represented as varint indexes into a dictionary, I can
feel how much work that involves and maybe I can make time over the
next few weeks to implement it. Has anyone got example code for
representing partial Merkle trees?

> Also, it's not mentioned in the page— but the hash function used is
> not cryptographically strong,  so what prevents a complexity (well,
> bandwidth in this case) attack?  someone could start using txids and
> txouts that collide with the maximum number of other existing txouts
> in order to waste bandwidth for people.  Is this avenue of attack not
> a concern?

If you just want to waste bandwidth of nodes you can connect to nodes
and repeatedly download blocks, or fill the network with fake nodes
that spam random generated transactions to whoever connects. I don't
see how to avoid that  so it seems odd to worry about a much more
complicated attack.

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Gregory Maxwell]

On Fri, Oct 26, 2012 at 10:01 AM, Mike Hearn <mike@plan99.net> wrote:
> If you just want to waste bandwidth of nodes you can connect to nodes
> and repeatedly download blocks, or fill the network with fake nodes
> that spam random generated transactions to whoever connects. I don't
> see how to avoid that  so it seems odd to worry about a much more
> complicated attack.

Because I can potentially waste bandwidth of all nodes forever (well as long
as users are still scanning blocks with my transactions in them) with O(1) work.

Though I'm not sure how much of a threat is vs just paying 1e-8 btc to lots of
addresses which would only be less bad by some constant factor as worse.
I guess I should try to attack it and see how bad the pollution I can construct
should be. (offline, of course)

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Mike Hearn]

> Because I can potentially waste bandwidth of all nodes forever (well as long
> as users are still scanning blocks with my transactions in them) with O(1) work.

And this gets you what?

Users who have active wallets will have their bandwidth wasted for as
long as you keep up the attack. Once you stop active wallets won't be
rescanning that part of the chain and new users won't be scanning it
either, as they skip blocks before their earliest key time using
getheaders. So basically you can waste the bandwidth of active users
for a while, by spamming transactions. This is not a new attack.

Anyway, it's trivial to DoS the entire Bitcoin network today. It
hasn't ever happened. Maybe one day it will, but the only rationale
people can come up with for such an attack beyond random griefing is
governments, and complexity attacks are really not their style. Much
easier to just pass a law.

I'm not saying DoS should be ignored, but I do feel there are limits
to how far down that rabbithole it's worth going.

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Gregory Maxwell]

On Fri, Oct 26, 2012 at 10:21 AM, Mike Hearn <mike@plan99.net> wrote:
> Anyway, it's trivial to DoS the entire Bitcoin network today. It
> hasn't ever happened. Maybe one day it will, but the only rationale
> people can come up with for such an attack beyond random griefing is

Which happens and is a concern. Altcoins have been attacked on things
we fixed. For example, litecoin nodes were being run out of disk space
through addr.dat flooding.

I think we've been generally fortunate that the level of griefing is
low (though not non-existent).  But part of the reason its been low is
that it's probably harder to DOS attack bitcoin than you believe. In
the reference client a lot of work has gone in to removing attacks
with sublinear cost for the attackers.

That people aren't attacking much now is not an argument to accept a
new vulnerability much less a _normative_ vulnerability in the
protocol.

That it's no big deal even attacked would be a fine argument to me, so
I'll go try to convince myself of that.

> governments,

Please don't put that kind of black helicopter junk in my mouth. I
agree with you the point that these aren't a source of concern for me.

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Pieter Wuille]

On Fri, Oct 26, 2012 at 04:01:58PM +0200, Mike Hearn wrote:
> I don't feel I understand the effort required to do some kind of
> partial tree encoding. Having a kind of custom compression whereby
> branches are represented as varint indexes into a dictionary, I can
> feel how much work that involves and maybe I can make time over the
> next few weeks to implement it. Has anyone got example code for
> representing partial Merkle trees?

I've implemented code for efficient representation of partial merkle
trees: see https://github.com/sipa/bitcoin/commits/partialmerkle

The encoding/decoding algorithm uses a depth-first traversal of the tree, at
each node outputting whether anything relevant is beneath, and if not, storing
its hash and not descending into the children.

Furthermore, thanks to some properties of the tree, some hard upper bounds on
the size of the serialized structures are guaranteed. See the comments in the
code for details.

Unit tests are included to verify that
1) encoding and decoding a subset of transactions is an identity
2) the calculated merkle root matches the merkle root calculated by the existing merkle algorithm in the source code
3) the calculated merkle root actually depends on all hashes in the data structure.
4) serialization/deserialization is an identity
5) bounds on the size of the serialization are respected

Hope it is clear enough to port to other languages.

-- 
Pieter

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Pieter Wuille]

On Wed, Oct 24, 2012 at 05:56:07PM +0200, Mike Hearn wrote:
> I've written a draft BIP describing the bloom filtering protocol
> extension developed by myself and Matt.
> 
> https://en.bitcoin.it/wiki/BIP_0037

Two comments I made on the pullreq page, which are probably better discussed here:
* The 0xFFFFFFFF/(n-1)*i seed value seems intended to result in large bit
  differences between the different hash function's seeds. Together with the tweak,
  however, the first and the last now get seeds tweak and tweak-1. I think
  something simpler like k1*i+k2*n+tweak is better (with k1 and k2 arbitrary large
  odd 32-bit integers).
* I feel uneasy about the arbitrary filter parameters used for the implicitly
  created filter when sending filteradd without filterload. The server cannot be
  expected to make a reasonable guess how the client is going to use the filter,
  and the client still has to track how large the server-side filter grows anyway.
  I'd prefer to make this simply illegal (DoS 100): filteradd always requires an
  active filter. Maybe the actual filter data in filterload can be made optional:
  if it is omitted, it's assumed to be all zeroes (though that would mean the size
  has to be specified).

-- 
Pieter

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Matt Corallo]

On Wed, 2012-11-21 at 16:15 +0100, Pieter Wuille wrote:
> On Wed, Oct 24, 2012 at 05:56:07PM +0200, Mike Hearn wrote:
> > I've written a draft BIP describing the bloom filtering protocol
> > extension developed by myself and Matt.
> > 
> > https://en.bitcoin.it/wiki/BIP_0037
> 
> Two comments I made on the pullreq page, which are probably better discussed here:
> * The 0xFFFFFFFF/(n-1)*i seed value seems intended to result in large bit
>   differences between the different hash function's seeds. Together with the tweak,
>   however, the first and the last now get seeds tweak and tweak-1. I think
>   something simpler like k1*i+k2*n+tweak is better (with k1 and k2 arbitrary large
>   odd 32-bit integers).
Meh, sure, whatever...I dont really think the seed values matter
significantly (Murmur3 isnt that bad of a hash function...) (and the
original algorithm wont result in a significant bit difference between
the seeds in many cases).
> * I feel uneasy about the arbitrary filter parameters used for the implicitly
>   created filter when sending filteradd without filterload. The server cannot be
>   expected to make a reasonable guess how the client is going to use the filter,
>   and the client still has to track how large the server-side filter grows anyway.
>   I'd prefer to make this simply illegal (DoS 100): filteradd always requires an
>   active filter.
I think there is some consensus here, and I have no problem doing it
this way (in large part, filteradd should not be used at all).
> Maybe the actual filter data in filterload can be made optional:
>   if it is omitted, it's assumed to be all zeroes (though that would mean the size
>   has to be specified).
> 
I'm not sure here, if you are sending a filter just to use filteradd to
add things to it manually, you are doing something very, very, very
wrong... Though we could certainly do some kind of compressed bloom
filter encoding to allow for small filter loads (loading the few things
you need to filteradd right away) where you anticipate adding
significantly more filter elements down the road (can anyone even come
up with a case where you anticipate doing this?), the filter is small
enough (max 36kB) that I see little benefit for the large increase in
complexity (or is this another repeat of the merkle branch discussion?)

Matt

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Pieter Wuille]

On Wed, Nov 21, 2012 at 01:38:37PM -0500, Matt Corallo wrote:
> On Wed, 2012-11-21 at 16:15 +0100, Pieter Wuille wrote:
> > On Wed, Oct 24, 2012 at 05:56:07PM +0200, Mike Hearn wrote:
> > > I've written a draft BIP describing the bloom filtering protocol
> > > extension developed by myself and Matt.
> > > 
> > > https://en.bitcoin.it/wiki/BIP_0037
> > 
> > Two comments I made on the pullreq page, which are probably better discussed here:
> > * The 0xFFFFFFFF/(n-1)*i seed value seems intended to result in large bit
> >   differences between the different hash function's seeds. Together with the tweak,
> >   however, the first and the last now get seeds tweak and tweak-1. I think
> >   something simpler like k1*i+k2*n+tweak is better (with k1 and k2 arbitrary large
> >   odd 32-bit integers).
> Meh, sure, whatever...I dont really think the seed values matter
> significantly (Murmur3 isnt that bad of a hash function...) (and the
> original algorithm wont result in a significant bit difference between
> the seeds in many cases).

Sure, it's nothing important, but it seems like it fails to do what it was intended for.

How about just this: tweak + i*0xFBA4C795 (number optimized to give large seed
differences for every tweak). If you want variation when changing the number of hash
functions, just choose a different seed. 

> > Maybe the actual filter data in filterload can be made optional:
> >   if it is omitted, it's assumed to be all zeroes (though that would mean the size
> >   has to be specified).
> > 
> I'm not sure here, if you are sending a filter just to use filteradd to
> add things to it manually, you are doing something very, very, very
> wrong... Though we could certainly do some kind of compressed bloom
> filter encoding to allow for small filter loads (loading the few things
> you need to filteradd right away) where you anticipate adding
> significantly more filter elements down the road (can anyone even come
> up with a case where you anticipate doing this?), the filter is small
> enough (max 36kB) that I see little benefit for the large increase in
> complexity (or is this another repeat of the merkle branch discussion?)

It's probably not worth it for something that is max 36 kilobytes. If ever
necessary, we can define a new message type that just lists a number of bits to
be set in the server-side filter.

For now, I agree that you should just send the filter as intended, and not expect to
do many filteradds (though you should take the implicitly-added txids into
accounted when computing the filter size).

-- 
Pieter

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Mike Hearn]

Here's a quick update on where we're up to.

Thanks to Matts excellent work, I was able to test his bitcoinj and
bitcoin-qt work together today. There are a few minor tweaks needed,
but I feel like we're maybe a week away from having all the code in a
mergeable state. Here is the remaining work:

- There are a couple of bugfixes needed on the bitcoinj side: the
fallback to downloading full blocks is problematic and needs to be
deleted, there's an API change we want

- Adjust the default FP rate requested by BCJ to be 0.0001, this is
appropriate for the latest blocks in the chain and yields 0-5 false
positives per block

- Introduce a new part to the filter protocol that allows clients to
control auto-expansion. This turned out to be very volatile, we saw
jumps from 0-3 FPs per block to 500 in the space of 1 block, perhaps
if a SatoshiDice transaction got into the filter. A simple yes/no flag
can suffice for now, but a better solution would be for the client to
submit templates for output scripts that would trigger auto-adding the
matched outpoint - autoexpansion is only needed in the case where the
input script doesn't contain any predictable data. For pay-to-address
and P2SH it does, so expansion doesn't help. Matt said he'd hopefully
try to look at this soon.

With auto-expansion disabled, the FP rate adjusted and a bugfix on the
bcj side I was able to sync a wallet using a bloom filtered chain.

Although it's tight, I think this work should go into 0.8 - it'll be
much more compelling to advertise it this way, we can say "Upgrade to
0.8 and help network performance for everyone". And in the case that
we discover a showstopper problem, we just don't deploy the code that
uses the new messages into clients.

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Matt Corallo]

On Thu, 2013-01-10 at 16:21 +0100, Mike Hearn wrote:
> Here's a quick update on where we're up to.
> 
> Thanks to Matts excellent work, I was able to test his bitcoinj and
> bitcoin-qt work together today. There are a few minor tweaks needed,
> but I feel like we're maybe a week away from having all the code in a
> mergeable state. Here is the remaining work:
> 
> - There are a couple of bugfixes needed on the bitcoinj side: the
> fallback to downloading full blocks is problematic and needs to be
> deleted, there's an API change we want
First of the two is done.
> 
> - Adjust the default FP rate requested by BCJ to be 0.0001, this is
> appropriate for the latest blocks in the chain and yields 0-5 false
> positives per block
Is a part of the larger API changes mentioned above.
> 
> - Introduce a new part to the filter protocol that allows clients to
> control auto-expansion. This turned out to be very volatile, we saw
> jumps from 0-3 FPs per block to 500 in the space of 1 block, perhaps
> if a SatoshiDice transaction got into the filter. A simple yes/no flag
> can suffice for now, but a better solution would be for the client to
> submit templates for output scripts that would trigger auto-adding the
> matched outpoint - autoexpansion is only needed in the case where the
> input script doesn't contain any predictable data. For pay-to-address
> and P2SH it does, so expansion doesn't help. Matt said he'd hopefully
> try to look at this soon.
The flags mentioned have been implemented, both to disable
autoexpansion, enable it for all outputs, enable for only pay to pubkey
outputs (the most likely use-case), or use a set of templates.  The
matched templates part isn't properly tested and I would like comments
on that part (see the last few commits at
https://github.com/bitcoin/bitcoin/pull/1795).
> 
> With auto-expansion disabled, the FP rate adjusted and a bugfix on the
> bcj side I was able to sync a wallet using a bloom filtered chain.
> 
> Although it's tight, I think this work should go into 0.8 - it'll be
> much more compelling to advertise it this way, we can say "Upgrade to
> 0.8 and help network performance for everyone". And in the case that
> we discover a showstopper problem, we just don't deploy the code that
> uses the new messages into clients.
Ive been missing lately, when is 0.8 targeted for freeze?

Matt

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Jeff Garzik]

On Thu, Jan 10, 2013 at 10:59 PM, Matt Corallo <bitcoin-list@bluematt.me> wrote:
> Ive been missing lately, when is 0.8 targeted for freeze?

0.8rc1 will probably happen when the core ultraprune/leveldb stuff is stable.

-- 
Jeff Garzik
exMULTI, Inc.
jgarzik@exmulti.com

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Mike Hearn]

I did some very rough initial performance tests.

Syncing from a local peer gives me about 50 blocks per second in the
later parts of the chain (post SD), which is about a 10-20x speedup
over what I could do before. This is on a MacBook Pro. But at those
points it's clearly bottlenecked by bitcoind which has saturated its
CPU core. This makes sense - the filtering is much more server than
client intensive because every transaction in every block has to be
loaded and checked.

I think filtering can be fairly well parallelized on the server side.
So the current 10-20x speedup could potentially be larger if the
server becomes more efficient at scanning and filtering blocks. It's
still a very nice win for now, especially bandwidth wise. And if Matt
makes the mempool command filtered it solves a common usability
problem as well.

Once we get this code in, merged and rolled out I think what we need
for bloom v2 is clear:

 - Multi-thread the filtering process in bitcoind so transactions can
be checked in parallel. A 4-core server would then get 4x faster at
filtering blocks and assuming it's not too busy doing other stuff we
could maybe sync at more like 200 blocks per second, which is cool ...
more than a days worth of history for each second of syncing.

 - Make the client smarter so the FP rate is adapted during the sync
process. An FP rate that makes sense post-SD results in no false
positives pre-SD, more or less.

 - Make the client shard its wallet keys over multiple peers, for
better privacy.

 - Make the client suck down filtered blocks in parallel from multiple
peers, for better speed.

As it seems the bottleneck for chain sync is now CPU time, the latter
point may be the most important from a practical perspective.

On Fri, Jan 11, 2013 at 6:02 AM, Jeff Garzik <jgarzik@exmulti.com> wrote:
> On Thu, Jan 10, 2013 at 10:59 PM, Matt Corallo <bitcoin-list@bluematt.me> wrote:
>> Ive been missing lately, when is 0.8 targeted for freeze?
>
> 0.8rc1 will probably happen when the core ultraprune/leveldb stuff is stable.
>
> --
> Jeff Garzik
> exMULTI, Inc.
> jgarzik@exmulti.com

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Mike Hearn]

Oh, one last stat - syncing the entire chain with a wallet containing
two keys and a 0.0001 FP rate (one or two FPs every 5 blocks or so)
resulted in a download of about 46mb of data.

On Fri, Jan 11, 2013 at 3:11 PM, Mike Hearn <mike@plan99.net> wrote:
> I did some very rough initial performance tests.
>
> Syncing from a local peer gives me about 50 blocks per second in the
> later parts of the chain (post SD), which is about a 10-20x speedup
> over what I could do before. This is on a MacBook Pro. But at those
> points it's clearly bottlenecked by bitcoind which has saturated its
> CPU core. This makes sense - the filtering is much more server than
> client intensive because every transaction in every block has to be
> loaded and checked.
>
> I think filtering can be fairly well parallelized on the server side.
> So the current 10-20x speedup could potentially be larger if the
> server becomes more efficient at scanning and filtering blocks. It's
> still a very nice win for now, especially bandwidth wise. And if Matt
> makes the mempool command filtered it solves a common usability
> problem as well.
>
> Once we get this code in, merged and rolled out I think what we need
> for bloom v2 is clear:
>
>  - Multi-thread the filtering process in bitcoind so transactions can
> be checked in parallel. A 4-core server would then get 4x faster at
> filtering blocks and assuming it's not too busy doing other stuff we
> could maybe sync at more like 200 blocks per second, which is cool ...
> more than a days worth of history for each second of syncing.
>
>  - Make the client smarter so the FP rate is adapted during the sync
> process. An FP rate that makes sense post-SD results in no false
> positives pre-SD, more or less.
>
>  - Make the client shard its wallet keys over multiple peers, for
> better privacy.
>
>  - Make the client suck down filtered blocks in parallel from multiple
> peers, for better speed.
>
> As it seems the bottleneck for chain sync is now CPU time, the latter
> point may be the most important from a practical perspective.
>
> On Fri, Jan 11, 2013 at 6:02 AM, Jeff Garzik <jgarzik@exmulti.com> wrote:
>> On Thu, Jan 10, 2013 at 10:59 PM, Matt Corallo <bitcoin-list@bluematt.me> wrote:
>>> Ive been missing lately, when is 0.8 targeted for freeze?
>>
>> 0.8rc1 will probably happen when the core ultraprune/leveldb stuff is stable.
>>
>> --
>> Jeff Garzik
>> exMULTI, Inc.
>> jgarzik@exmulti.com

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Mike Hearn]

Matts latest code has been tested by Andreas and seems to work
correctly. He had to extend the client a bit to refresh the filter
every 25k blocks because even with the extra flag, eventually the
filter degrades into uselessness, but it did still improve the
situation quite a bit.

Because it's unit tested, been reviewed by me several times, has an
interoperable implementation that has also been tested by Andreas in a
build of his smartphone app,  I'm going to ACK the current code and
request that it be merged in to 0.8. What do you say Gavin?

The next step after that would be profiling. It's a big performance
improvement for SPV clients already, but not as much as I anticipated.
I suspect there's a simple bottleneck or missed optimization
somewhere. But that can obviously come post-0.8

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Matt Corallo]

Actually, there is one more minor algorithmic change I would like to
make to the way the hash function is computed really quick before it
gets merged, I'll have that finished up by the end of today.

Matt

On Wed, 2013-01-16 at 11:43 +0100, Mike Hearn wrote:
> Matts latest code has been tested by Andreas and seems to work
> correctly. He had to extend the client a bit to refresh the filter
> every 25k blocks because even with the extra flag, eventually the
> filter degrades into uselessness, but it did still improve the
> situation quite a bit.
> 
> Because it's unit tested, been reviewed by me several times, has an
> interoperable implementation that has also been tested by Andreas in a
> build of his smartphone app,  I'm going to ACK the current code and
> request that it be merged in to 0.8. What do you say Gavin?
> 
> The next step after that would be profiling. It's a big performance
> improvement for SPV clients already, but not as much as I anticipated.
> I suspect there's a simple bottleneck or missed optimization
> somewhere. But that can obviously come post-0.8

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Mike Hearn]

I'm thinking we should actually make the change we talked about before
and have the filtered block sent before the transaction data.

For one, it's not intuitive (API wise) that you'd get a callback
saying "new pending tx" immediately before another callback saying "tx
was confirmed", but that's what the current setup makes most natural.
To fix it we'd have to notice that a tx message wasn't requested by
us, buffer it, and wait for the corresponding filteredblock message.
It seems cleaner to receive a filteredblock and then for any tx that
matches it, attach it to the FilteredBlock object and wait until it is
full up, then pass it to the wallet code all at once.

Another issue is that to risk analyze unconfirmed transactions you
really have to download all dependencies. That has to be triggered by
seeing an unconfirmed transaction. It's dumb to start this process for
a tx that is actually in the chain, so you need to have some notion of
whether it came from a filtered block anyway. I only realized this
today.

I think when we discussed this before, the justification for having it
work the current way was that it was simpler to integrate with the SPV
client code if it was done this way around. But I don't think it's
really simpler. There are enough odd side effects of doing it this
way, that I feel it'd be better to tweak the protocol now whilst we
have the chance.

On Wed, Jan 16, 2013 at 4:00 PM, Matt Corallo <bitcoin-list@bluematt.me> wrote:
> Actually, there is one more minor algorithmic change I would like to
> make to the way the hash function is computed really quick before it
> gets merged, I'll have that finished up by the end of today.
>
> Matt
>
> On Wed, 2013-01-16 at 11:43 +0100, Mike Hearn wrote:
>> Matts latest code has been tested by Andreas and seems to work
>> correctly. He had to extend the client a bit to refresh the filter
>> every 25k blocks because even with the extra flag, eventually the
>> filter degrades into uselessness, but it did still improve the
>> situation quite a bit.
>>
>> Because it's unit tested, been reviewed by me several times, has an
>> interoperable implementation that has also been tested by Andreas in a
>> build of his smartphone app,  I'm going to ACK the current code and
>> request that it be merged in to 0.8. What do you say Gavin?
>>
>> The next step after that would be profiling. It's a big performance
>> improvement for SPV clients already, but not as much as I anticipated.
>> I suspect there's a simple bottleneck or missed optimization
>> somewhere. But that can obviously come post-0.8
>
>

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Andreas Schildbach]

Matt, I saw your commit and immediately started using it for testing.
Now I think the bitcoinj side needs some love because not one
transaction is being confirmed (all just pending) when replaying the
blockchain.


On 01/18/2013 05:38 PM, Mike Hearn wrote:
> I'm thinking we should actually make the change we talked about before
> and have the filtered block sent before the transaction data.
> 
> For one, it's not intuitive (API wise) that you'd get a callback
> saying "new pending tx" immediately before another callback saying "tx
> was confirmed", but that's what the current setup makes most natural.
> To fix it we'd have to notice that a tx message wasn't requested by
> us, buffer it, and wait for the corresponding filteredblock message.
> It seems cleaner to receive a filteredblock and then for any tx that
> matches it, attach it to the FilteredBlock object and wait until it is
> full up, then pass it to the wallet code all at once.
> 
> Another issue is that to risk analyze unconfirmed transactions you
> really have to download all dependencies. That has to be triggered by
> seeing an unconfirmed transaction. It's dumb to start this process for
> a tx that is actually in the chain, so you need to have some notion of
> whether it came from a filtered block anyway. I only realized this
> today.
> 
> I think when we discussed this before, the justification for having it
> work the current way was that it was simpler to integrate with the SPV
> client code if it was done this way around. But I don't think it's
> really simpler. There are enough odd side effects of doing it this
> way, that I feel it'd be better to tweak the protocol now whilst we
> have the chance.
> 
> On Wed, Jan 16, 2013 at 4:00 PM, Matt Corallo <bitcoin-list@bluematt.me> wrote:
>> Actually, there is one more minor algorithmic change I would like to
>> make to the way the hash function is computed really quick before it
>> gets merged, I'll have that finished up by the end of today.
>>
>> Matt
>>
>> On Wed, 2013-01-16 at 11:43 +0100, Mike Hearn wrote:
>>> Matts latest code has been tested by Andreas and seems to work
>>> correctly. He had to extend the client a bit to refresh the filter
>>> every 25k blocks because even with the extra flag, eventually the
>>> filter degrades into uselessness, but it did still improve the
>>> situation quite a bit.
>>>
>>> Because it's unit tested, been reviewed by me several times, has an
>>> interoperable implementation that has also been tested by Andreas in a
>>> build of his smartphone app,  I'm going to ACK the current code and
>>> request that it be merged in to 0.8. What do you say Gavin?
>>>
>>> The next step after that would be profiling. It's a big performance
>>> improvement for SPV clients already, but not as much as I anticipated.
>>> I suspect there's a simple bottleneck or missed optimization
>>> somewhere. But that can obviously come post-0.8
>>
>>
> 
> ------------------------------------------------------------------------------
> Master HTML5, CSS3, ASP.NET, MVC, AJAX, Knockout.js, Web API and
> much more. Get web development skills now with LearnDevNow -
> 350+ hours of step-by-step video tutorials by Microsoft MVPs and experts.
> SALE $99.99 this month only -- learn more at:
> http://p.sf.net/sfu/learnmore_122812
> 

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 2034 bytes --]

Andreas has uploaded Android builds that use the new bloom filtering and
peer selection code (also, dependency analysis of transactions).

The performance gain is very cool. The app feels dramatically faster to
start up and sync. Because the app syncs on charge when I opened it around
lunchtime it had only 7 hours of data to sync (42 blocks) and it brought up
6 peer connections, found a 0.7.99 node and synced all in <2 seconds. That
was on wifi.

The next lowest hanging perf fruit is almost certainly to optimize disk
accesses. Flash on Android devices seems to be much slower than laptop
flash storage, and current bitcoinj is very inefficient in how it writes
(one write per block header!). This matters a lot when doing fast catchup
for first time users.

The BIP is now a little bit stale, but only slightly.


On Wed, Jan 16, 2013 at 4:00 PM, Matt Corallo <bitcoin-list@bluematt.me>wrote:

> Actually, there is one more minor algorithmic change I would like to
> make to the way the hash function is computed really quick before it
> gets merged, I'll have that finished up by the end of today.
>
> Matt
>
> On Wed, 2013-01-16 at 11:43 +0100, Mike Hearn wrote:
> > Matts latest code has been tested by Andreas and seems to work
> > correctly. He had to extend the client a bit to refresh the filter
> > every 25k blocks because even with the extra flag, eventually the
> > filter degrades into uselessness, but it did still improve the
> > situation quite a bit.
> >
> > Because it's unit tested, been reviewed by me several times, has an
> > interoperable implementation that has also been tested by Andreas in a
> > build of his smartphone app,  I'm going to ACK the current code and
> > request that it be merged in to 0.8. What do you say Gavin?
> >
> > The next step after that would be profiling. It's a big performance
> > improvement for SPV clients already, but not as much as I anticipated.
> > I suspect there's a simple bottleneck or missed optimization
> > somewhere. But that can obviously come post-0.8
>
>
>

[-- Attachment #2: Type: text/html, Size: 2693 bytes --]

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 2533 bytes --]

Sorry, to clarify, these are test builds available here:


https://code.google.com/p/bitcoin-wallet/downloads/detail?name=bitcoin-wallet-2.39_bitcoinj0.7.apk&can=2&q=

It's not on the Play store yet. It probably makes sense to release after
some more testing and after Bitcoin 0.8 comes out, as otherwise there's a
risk that 0.7 snapshot nodes will get overloaded.


On Wed, Jan 30, 2013 at 12:09 PM, Mike Hearn <mike@plan99.net> wrote:

> Andreas has uploaded Android builds that use the new bloom filtering and
> peer selection code (also, dependency analysis of transactions).
>
> The performance gain is very cool. The app feels dramatically faster to
> start up and sync. Because the app syncs on charge when I opened it around
> lunchtime it had only 7 hours of data to sync (42 blocks) and it brought up
> 6 peer connections, found a 0.7.99 node and synced all in <2 seconds. That
> was on wifi.
>
> The next lowest hanging perf fruit is almost certainly to optimize disk
> accesses. Flash on Android devices seems to be much slower than laptop
> flash storage, and current bitcoinj is very inefficient in how it writes
> (one write per block header!). This matters a lot when doing fast catchup
> for first time users.
>
> The BIP is now a little bit stale, but only slightly.
>
>
> On Wed, Jan 16, 2013 at 4:00 PM, Matt Corallo <bitcoin-list@bluematt.me>wrote:
>
>> Actually, there is one more minor algorithmic change I would like to
>> make to the way the hash function is computed really quick before it
>> gets merged, I'll have that finished up by the end of today.
>>
>> Matt
>>
>> On Wed, 2013-01-16 at 11:43 +0100, Mike Hearn wrote:
>> > Matts latest code has been tested by Andreas and seems to work
>> > correctly. He had to extend the client a bit to refresh the filter
>> > every 25k blocks because even with the extra flag, eventually the
>> > filter degrades into uselessness, but it did still improve the
>> > situation quite a bit.
>> >
>> > Because it's unit tested, been reviewed by me several times, has an
>> > interoperable implementation that has also been tested by Andreas in a
>> > build of his smartphone app,  I'm going to ACK the current code and
>> > request that it be merged in to 0.8. What do you say Gavin?
>> >
>> > The next step after that would be profiling. It's a big performance
>> > improvement for SPV clients already, but not as much as I anticipated.
>> > I suspect there's a simple bottleneck or missed optimization
>> > somewhere. But that can obviously come post-0.8
>>
>>
>>
>

[-- Attachment #2: Type: text/html, Size: 3620 bytes --]

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 2765 bytes --]

Can somebody please unlock the BIP wiki page? I don't know why it was
locked but it's stale.


On Wed, Jan 30, 2013 at 12:13 PM, Mike Hearn <mike@plan99.net> wrote:

> Sorry, to clarify, these are test builds available here:
>
>
> https://code.google.com/p/bitcoin-wallet/downloads/detail?name=bitcoin-wallet-2.39_bitcoinj0.7.apk&can=2&q=
>
> It's not on the Play store yet. It probably makes sense to release after
> some more testing and after Bitcoin 0.8 comes out, as otherwise there's a
> risk that 0.7 snapshot nodes will get overloaded.
>
>
> On Wed, Jan 30, 2013 at 12:09 PM, Mike Hearn <mike@plan99.net> wrote:
>
>> Andreas has uploaded Android builds that use the new bloom filtering and
>> peer selection code (also, dependency analysis of transactions).
>>
>> The performance gain is very cool. The app feels dramatically faster to
>> start up and sync. Because the app syncs on charge when I opened it around
>> lunchtime it had only 7 hours of data to sync (42 blocks) and it brought up
>> 6 peer connections, found a 0.7.99 node and synced all in <2 seconds. That
>> was on wifi.
>>
>> The next lowest hanging perf fruit is almost certainly to optimize disk
>> accesses. Flash on Android devices seems to be much slower than laptop
>> flash storage, and current bitcoinj is very inefficient in how it writes
>> (one write per block header!). This matters a lot when doing fast catchup
>> for first time users.
>>
>> The BIP is now a little bit stale, but only slightly.
>>
>>
>> On Wed, Jan 16, 2013 at 4:00 PM, Matt Corallo <bitcoin-list@bluematt.me>wrote:
>>
>>> Actually, there is one more minor algorithmic change I would like to
>>> make to the way the hash function is computed really quick before it
>>> gets merged, I'll have that finished up by the end of today.
>>>
>>> Matt
>>>
>>> On Wed, 2013-01-16 at 11:43 +0100, Mike Hearn wrote:
>>> > Matts latest code has been tested by Andreas and seems to work
>>> > correctly. He had to extend the client a bit to refresh the filter
>>> > every 25k blocks because even with the extra flag, eventually the
>>> > filter degrades into uselessness, but it did still improve the
>>> > situation quite a bit.
>>> >
>>> > Because it's unit tested, been reviewed by me several times, has an
>>> > interoperable implementation that has also been tested by Andreas in a
>>> > build of his smartphone app,  I'm going to ACK the current code and
>>> > request that it be merged in to 0.8. What do you say Gavin?
>>> >
>>> > The next step after that would be profiling. It's a big performance
>>> > improvement for SPV clients already, but not as much as I anticipated.
>>> > I suspect there's a simple bottleneck or missed optimization
>>> > somewhere. But that can obviously come post-0.8
>>>
>>>
>>>
>>
>

[-- Attachment #2: Type: text/html, Size: 4133 bytes --]

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Gregory Maxwell]

On Wed, Feb 6, 2013 at 8:33 AM, Mike Hearn <mike@plan99.net> wrote:
> Can somebody please unlock the BIP wiki page? I don't know why it was locked
> but it's stale.

I asked for permissions to unlock it but haven't heard back— will prod.

Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 564 bytes --]

I paid the new anti-spam deposit and updated the BIP 37 page to the latest
version of the protocol, then marked it as accepted. High fives all round,
but especially to Matt for doing the heavy lifting on this feature.


On Wed, Feb 6, 2013 at 5:45 PM, Gregory Maxwell <gmaxwell@gmail.com> wrote:

> On Wed, Feb 6, 2013 at 8:33 AM, Mike Hearn <mike@plan99.net> wrote:
> > Can somebody please unlock the BIP wiki page? I don't know why it was
> locked
> > but it's stale.
>
> I asked for permissions to unlock it but haven't heard back— will prod.
>

[-- Attachment #2: Type: text/html, Size: 947 bytes --]