[bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Matt Corallo]

Peter: Since I stole most of this text from your old BIP, should I leave
you as an author?

BIP: ?
Title: NODE_BLOOM service bit
Author: Matt Corallo <bip@bluematt.me>, Peter Todd <pete@petertodd.org>
Type: Standards Track (draft)
Created: 20-08-2015

Abstract
========

This BIP extends BIP 37, Connection Bloom filtering, by defining a
service bit to allow peers to advertise that they support bloom filters
explicitly. It also bumps the protocol version to allow peers to
identify old nodes which allow bloom filtering of the connection despite
lacking the new service bit.


Motivation
==========

BIP 37 did not specify a service bit for the bloom filter service, thus
implicitly assuming that all nodes that serve peers data support it.
However, the connection filtering algorithm proposed in BIP 37, and
implemented in several clients today, has been shown to provide little
to no privacy, as well as being a large DoS risk on some nodes. Thus,
allowing node operators to disable connection bloom filtering is a
much-needed feature.


Specification
=============

The following protocol bit is added:

    NODE_BLOOM = (1 << 2)

Nodes which support bloom filters should set that protocol bit.
Otherwise it should remain unset. In addition the protocol version is
increased from 70002 to 70011 in the reference implementation. It is
often the case that nodes which have a protocol version smaller than
70011, but larger than 70000 support bloom filtered connections without
the NODE_BLOOM bit set, however clients which require bloom filtered
connections should avoid making this assumption.

NODE_BLOOM is distinct from NODE_NETWORK, and it is legal to advertise
NODE_BLOOM but not NODE_NETWORK (eg for nodes running in pruned mode
which, nonetheless, provide filtered access to the data which they do have).

If a node does not support bloom filters but receives a "filterload",
"filteradd", or "filterclear" message from a peer the node should
disconnect that peer immediately. For backwards compatibility, in
initial implementations, nodes may choose to only disconnect nodes which
have the new protocol version set and attempt to send a filter command.

While outside the scope of this BIP it is suggested that DNS seeds and
other peer discovery mechanisms support the ability to specify the
services required; current implementations simply check only that
NODE_NETWORK is set.


Design rational
===============

A service bit was chosen as applying a bloom filter is a service.

The increase in protocol version is for backwards compatibility. In
initial implementations, old nodes which are not yet aware of NODE_BLOOM
and use a protocol version < 70011 may still send filter* messages to a
node without NODE_BLOOM. This feature may be removed after there are
sufficient NODE_BLOOM nodes available and SPV clients have upgraded,
allowing node operators to fully close the bloom-related DoS vectors.


Reference Implementation
========================

https://github.com/bitcoin/bitcoin/pull/6579


Copyright
=========

This document is placed in the public domain.

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Peter Todd]

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

On Fri, Aug 21, 2015 at 04:46:17AM +0000, Matt Corallo wrote:
> Peter: Since I stole most of this text from your old BIP, should I leave
> you as an author?

That's fine by me.

> BIP: ?
> Title: NODE_BLOOM service bit
> Author: Matt Corallo <bip@bluematt.me>, Peter Todd <pete@petertodd.org>
> Type: Standards Track (draft)
> Created: 20-08-2015
> 
> Abstract
> ========
> 
> This BIP extends BIP 37, Connection Bloom filtering, by defining a
> service bit to allow peers to advertise that they support bloom filters
> explicitly. It also bumps the protocol version to allow peers to
> identify old nodes which allow bloom filtering of the connection despite
> lacking the new service bit.
> 
> 
> Motivation
> ==========
> 
> BIP 37 did not specify a service bit for the bloom filter service, thus
> implicitly assuming that all nodes that serve peers data support it.
> However, the connection filtering algorithm proposed in BIP 37, and
> implemented in several clients today, has been shown to provide little
> to no privacy, as well as being a large DoS risk on some nodes. Thus,
> allowing node operators to disable connection bloom filtering is a
> much-needed feature.

I'd reference that paper on bloom filters re: the "little to no privacy"
issue. There's also a post in the bitcoinj mailing list somewhere IIRC
talking about the default settings, and how they don't provide any
privacy.

> Specification
> =============
> 
> The following protocol bit is added:
> 
>     NODE_BLOOM = (1 << 2)
> 
> Nodes which support bloom filters should set that protocol bit.
> Otherwise it should remain unset. In addition the protocol version is
> increased from 70002 to 70011 in the reference implementation. It is
> often the case that nodes which have a protocol version smaller than
> 70011, but larger than 70000 support bloom filtered connections without
> the NODE_BLOOM bit set, however clients which require bloom filtered
> connections should avoid making this assumption.
> 
> NODE_BLOOM is distinct from NODE_NETWORK, and it is legal to advertise
> NODE_BLOOM but not NODE_NETWORK (eg for nodes running in pruned mode
> which, nonetheless, provide filtered access to the data which they do have).
> 
> If a node does not support bloom filters but receives a "filterload",
> "filteradd", or "filterclear" message from a peer the node should
> disconnect that peer immediately. For backwards compatibility, in
> initial implementations, nodes may choose to only disconnect nodes which
> have the new protocol version set and attempt to send a filter command.
> 
> While outside the scope of this BIP it is suggested that DNS seeds and
> other peer discovery mechanisms support the ability to specify the
> services required; current implementations simply check only that
> NODE_NETWORK is set.

Good to note Mike Hearn's Cartography seed protocol here.

> Design rational
> ===============
> 
> A service bit was chosen as applying a bloom filter is a service.
> 
> The increase in protocol version is for backwards compatibility. In
> initial implementations, old nodes which are not yet aware of NODE_BLOOM
> and use a protocol version < 70011 may still send filter* messages to a
> node without NODE_BLOOM. This feature may be removed after there are
> sufficient NODE_BLOOM nodes available and SPV clients have upgraded,
> allowing node operators to fully close the bloom-related DoS vectors.

Ah good! That solves the backwards compatibility quite nicely.

-- 
'peter'[:-1]@petertodd.org
00000000000000000402fe6fb9ad613c93e12bddfc6ec02a2bd92f002050594d

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Peter Todd]

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

On Thu, Aug 20, 2015 at 10:38:19PM -0700, Peter Todd via bitcoin-dev wrote:
> > Motivation
> > ==========
> > 
> > BIP 37 did not specify a service bit for the bloom filter service, thus
> > implicitly assuming that all nodes that serve peers data support it.
> > However, the connection filtering algorithm proposed in BIP 37, and
> > implemented in several clients today, has been shown to provide little
> > to no privacy, as well as being a large DoS risk on some nodes. Thus,
> > allowing node operators to disable connection bloom filtering is a
> > much-needed feature.
> 
> I'd reference that paper on bloom filters re: the "little to no privacy"
> issue. There's also a post in the bitcoinj mailing list somewhere IIRC
> talking about the default settings, and how they don't provide any
> privacy.

Oh, and we should also point out that Bloom filters have scaling issues,
as each application of the filter has to scan the whole blockchain -
with future blocksize increases these issues increase, in some proposals
quite dramatically. The underlying idea also conflicts with some
proposals to "shard" the blockchain, again suggesting that we need a bit
to handle future upgrades to more scalable designs.

-- 
'peter'[:-1]@petertodd.org
00000000000000000402fe6fb9ad613c93e12bddfc6ec02a2bd92f002050594d

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Matt Corallo]

Revised copy follows. re: mentioning the HTTP seeding stuff, I'm not
sure we want to encourage more people aside from bitcoinj to use
that...I thought about adding a DNS seed section to this bip, but
decided against it...still, I think we should add the option to select
service bits to DNS seeds ASAP.

Re: need to "shard" the blockchain: not sure what you're referring to
here. The bloom filter stuff requires you to download the chain
in-order, sure, but you have to do that for headers anyway, and
hopefully your total data isnt too much more than headers alone.

Anyone have the best reference for the DoS issues?

BIP: ?
Title: NODE_BLOOM service bit
Author: Matt Corallo <bip@bluematt.me>, Peter Todd <pete@petertodd.org>
Type: Standards Track (draft)
Created: 20-08-2015

Abstract
========

This BIP extends BIP 37, Connection Bloom filtering, by defining a
service bit to allow peers to advertise that they support bloom filters
explicitly. It also bumps the protocol version to allow peers to
identify old nodes which allow bloom filtering of the connection despite
lacking the new service bit.


Motivation
==========

BIP 37 did not specify a service bit for the bloom filter service, thus
implicitly assuming that all nodes that serve peers data support it.
However, the connection filtering algorithm proposed in BIP 37, and
implemented in several clients today, has been shown to provide little
to no privacy[1], as well as being a large DoS risk on some nodes[2].
Thus, allowing node operators to disable connection bloom filtering is a
much-needed feature.


Specification
=============

The following protocol bit is added:

    NODE_BLOOM = (1 << 2)

Nodes which support bloom filters should set that protocol bit.
Otherwise it should remain unset. In addition the protocol version is
increased from 70002 to 70011 in the reference implementation. It is
often the case that nodes which have a protocol version smaller than
70011, but larger than 70000 support bloom filtered connections without
the NODE_BLOOM bit set, however clients which require bloom filtered
connections should avoid making this assumption.

NODE_BLOOM is distinct from NODE_NETWORK, and it is legal to advertise
NODE_BLOOM but not NODE_NETWORK (eg for nodes running in pruned mode
which, nonetheless, provide filtered access to the data which they do have).

If a node does not support bloom filters but receives a "filterload",
"filteradd", or "filterclear" message from a peer the node should
disconnect that peer immediately. For backwards compatibility, in
initial implementations, nodes may choose to only disconnect nodes which
have the new protocol version set and attempt to send a filter command.

While outside the scope of this BIP it is suggested that DNS seeds and
other peer discovery mechanisms support the ability to specify the
services required; current implementations simply check only that
NODE_NETWORK is set.


Design rational
===============

A service bit was chosen as applying a bloom filter is a service.

The increase in protocol version is for backwards compatibility. In
initial implementations, old nodes which are not yet aware of NODE_BLOOM
and use a protocol version < 70011 may still send filter* messages to a
node without NODE_BLOOM. This feature may be removed after there are
sufficient NODE_BLOOM nodes available and SPV clients have upgraded,
allowing node operators to fully close the bloom-related DoS vectors.


Reference Implementation
========================

https://github.com/bitcoin/bitcoin/pull/6579


Copyright
=========

This document is placed in the public domain.


References
==========

[1] http://eprint.iacr.org/2014/763
[2] ???? is one example where the issues were found, though others
independently discovered issues as well. Sample DoS exploit code
available at https://github.com/petertodd/bloom-io-attack.



On 08/21/15 05:42, Peter Todd wrote:
> On Thu, Aug 20, 2015 at 10:38:19PM -0700, Peter Todd via bitcoin-dev wrote:
>>> Motivation
>>> ==========
>>>
>>> BIP 37 did not specify a service bit for the bloom filter service, thus
>>> implicitly assuming that all nodes that serve peers data support it.
>>> However, the connection filtering algorithm proposed in BIP 37, and
>>> implemented in several clients today, has been shown to provide little
>>> to no privacy, as well as being a large DoS risk on some nodes. Thus,
>>> allowing node operators to disable connection bloom filtering is a
>>> much-needed feature.
>>
>> I'd reference that paper on bloom filters re: the "little to no privacy"
>> issue. There's also a post in the bitcoinj mailing list somewhere IIRC
>> talking about the default settings, and how they don't provide any
>> privacy.
> 
> Oh, and we should also point out that Bloom filters have scaling issues,
> as each application of the filter has to scan the whole blockchain -
> with future blocksize increases these issues increase, in some proposals
> quite dramatically. The underlying idea also conflicts with some
> proposals to "shard" the blockchain, again suggesting that we need a bit
> to handle future upgrades to more scalable designs.
> 

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Peter Todd]

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

On Fri, Aug 21, 2015 at 05:55:58PM +0000, Matt Corallo wrote:
> Revised copy follows. re: mentioning the HTTP seeding stuff, I'm not
> sure we want to encourage more people aside from bitcoinj to use
> that...I thought about adding a DNS seed section to this bip, but
> decided against it...still, I think we should add the option to select
> service bits to DNS seeds ASAP.

Well, in general relying on seeds every time you start your node is a
really bad idea; doing so much be carefully weighed against the
downsides and should be used only as a last resort. Nodes should be
doing caching and proper gossip protocol participation whenever
possible. (note how bitcoinj nodes *do* rely on centralized servers,
implemented with an unauthenticated, unencrypted, protocol - the worst
of all possible solutions with many possible MITM vectors and privacy
security holes)

To that end, I'd be inclined to leave the DNS seed protocol as it is and
let others solve the centralized server use-case, for which Cartographer
isn't all that bad of a load balancing mechanism. Also as gmaxwell noted
on IRC, adding flag bits does have privacy implications.

> Re: need to "shard" the blockchain: not sure what you're referring to
> here. The bloom filter stuff requires you to download the chain
> in-order, sure, but you have to do that for headers anyway, and
> hopefully your total data isnt too much more than headers alone.

Any protocol change that would split blocks themselves into multiples.
Not an easy problem to solve, but given the inherent O(n^2) scaling of
global consensus blockchains, it's the only kind of solution that could
in the future make the blockchain itself have reasonable scalability.

> Anyone have the best reference for the DoS issues?

Well actually, we can reference the DoS attacks that Bitcoin XT nodes
are undergoing right now - part of the attack is repeated Bloom filter
requests to soak up disk IO bandwidth. I've CC'd Gavin and Mike - as far
as I know they haven't published details of those attacks - a write-up
would be very helpful.

While so far those are being directed only at XT nodes, obviously this
is a potential issue for Core nodes as well. Like I mentioned last time
around, it's critical that miners aren't affected by these attacks -
nodes simply serving SPV wallet clients are much less latency sensitive,
so a good DoS attack mitigation strategy would be to have the two
classes of nodes out there "in the wild"

> BIP: ?
> Title: NODE_BLOOM service bit
> Author: Matt Corallo <bip@bluematt.me>, Peter Todd <pete@petertodd.org>
> Type: Standards Track (draft)
> Created: 20-08-2015
> 
> Abstract
> ========
> 
> This BIP extends BIP 37, Connection Bloom filtering, by defining a
> service bit to allow peers to advertise that they support bloom filters
> explicitly. It also bumps the protocol version to allow peers to
> identify old nodes which allow bloom filtering of the connection despite
> lacking the new service bit.
> 
> 
> Motivation
> ==========
> 
> BIP 37 did not specify a service bit for the bloom filter service, thus
> implicitly assuming that all nodes that serve peers data support it.
> However, the connection filtering algorithm proposed in BIP 37, and
> implemented in several clients today, has been shown to provide little
> to no privacy[1], as well as being a large DoS risk on some nodes[2].
> Thus, allowing node operators to disable connection bloom filtering is a
> much-needed feature.
> 
> 
> Specification
> =============
> 
> The following protocol bit is added:
> 
>     NODE_BLOOM = (1 << 2)
> 
> Nodes which support bloom filters should set that protocol bit.
> Otherwise it should remain unset. In addition the protocol version is
> increased from 70002 to 70011 in the reference implementation. It is
> often the case that nodes which have a protocol version smaller than
> 70011, but larger than 70000 support bloom filtered connections without
> the NODE_BLOOM bit set, however clients which require bloom filtered
> connections should avoid making this assumption.
> 
> NODE_BLOOM is distinct from NODE_NETWORK, and it is legal to advertise
> NODE_BLOOM but not NODE_NETWORK (eg for nodes running in pruned mode
> which, nonetheless, provide filtered access to the data which they do have).
> 
> If a node does not support bloom filters but receives a "filterload",
> "filteradd", or "filterclear" message from a peer the node should
> disconnect that peer immediately. For backwards compatibility, in
> initial implementations, nodes may choose to only disconnect nodes which
> have the new protocol version set and attempt to send a filter command.
> 
> While outside the scope of this BIP it is suggested that DNS seeds and
> other peer discovery mechanisms support the ability to specify the
> services required; current implementations simply check only that
> NODE_NETWORK is set.
> 
> 
> Design rational
> ===============
> 
> A service bit was chosen as applying a bloom filter is a service.
> 
> The increase in protocol version is for backwards compatibility. In
> initial implementations, old nodes which are not yet aware of NODE_BLOOM
> and use a protocol version < 70011 may still send filter* messages to a
> node without NODE_BLOOM. This feature may be removed after there are
> sufficient NODE_BLOOM nodes available and SPV clients have upgraded,
> allowing node operators to fully close the bloom-related DoS vectors.
> 
> 
> Reference Implementation
> ========================
> 
> https://github.com/bitcoin/bitcoin/pull/6579
> 
> 
> Copyright
> =========
> 
> This document is placed in the public domain.
> 
> 
> References
> ==========
> 
> [1] http://eprint.iacr.org/2014/763
> [2] ???? is one example where the issues were found, though others
> independently discovered issues as well. Sample DoS exploit code
> available at https://github.com/petertodd/bloom-io-attack.

-- 
'peter'[:-1]@petertodd.org
00000000000000000402fe6fb9ad613c93e12bddfc6ec02a2bd92f002050594d

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Matt Corallo]

On 08/21/15 22:06, Peter Todd wrote:
> On Fri, Aug 21, 2015 at 05:55:58PM +0000, Matt Corallo wrote:
>> Revised copy follows. re: mentioning the HTTP seeding stuff, I'm not
>> sure we want to encourage more people aside from bitcoinj to use
>> that...I thought about adding a DNS seed section to this bip, but
>> decided against it...still, I think we should add the option to select
>> service bits to DNS seeds ASAP.
> 
> Well, in general relying on seeds every time you start your node is a
> really bad idea; doing so much be carefully weighed against the
> downsides and should be used only as a last resort. Nodes should be
> doing caching and proper gossip protocol participation whenever
> possible. (note how bitcoinj nodes *do* rely on centralized servers,
> implemented with an unauthenticated, unencrypted, protocol - the worst
> of all possible solutions with many possible MITM vectors and privacy
> security holes)
>
> To that end, I'd be inclined to leave the DNS seed protocol as it is and
> let others solve the centralized server use-case, for which Cartographer
> isn't all that bad of a load balancing mechanism. Also as gmaxwell noted
> on IRC, adding flag bits does have privacy implications.

Had a discussion on IRC and with Pieter, and I kinda agree that the more
optimal way is for DNS seeds to, instead of returning NODE_NETWORK
nodes, return any node which responds to getaddr, allowing clients to
connect to a few DNS seeds by name, do a getaddr, then disconnect (like
Bitcoin Core does now if you're using Tor). They can then select the
peers they want based on nServices.

>> Re: need to "shard" the blockchain: not sure what you're referring to
>> here. The bloom filter stuff requires you to download the chain
>> in-order, sure, but you have to do that for headers anyway, and
>> hopefully your total data isnt too much more than headers alone.
> 
> Any protocol change that would split blocks themselves into multiples.
> Not an easy problem to solve, but given the inherent O(n^2) scaling of
> global consensus blockchains, it's the only kind of solution that could
> in the future make the blockchain itself have reasonable scalability.

Meh, whatever, justification is already provided well enough without
having to go into "but if we did this long into the future"  arguments.

>> Anyone have the best reference for the DoS issues?
> 
> Well actually, we can reference the DoS attacks that Bitcoin XT nodes
> are undergoing right now - part of the attack is repeated Bloom filter
> requests to soak up disk IO bandwidth. I've CC'd Gavin and Mike - as far
> as I know they haven't published details of those attacks - a write-up
> would be very helpful.
> 
> While so far those are being directed only at XT nodes, obviously this
> is a potential issue for Core nodes as well. Like I mentioned last time
> around, it's critical that miners aren't affected by these attacks -
> nodes simply serving SPV wallet clients are much less latency sensitive,
> so a good DoS attack mitigation strategy would be to have the two
> classes of nodes out there "in the wild"

Ehh, I was going more for the oldest mention.

>> BIP: ?
>> Title: NODE_BLOOM service bit
>> Author: Matt Corallo <bip@bluematt.me>, Peter Todd <pete@petertodd.org>
>> Type: Standards Track (draft)
>> Created: 20-08-2015
>>
>> Abstract
>> ========
>>
>> This BIP extends BIP 37, Connection Bloom filtering, by defining a
>> service bit to allow peers to advertise that they support bloom filters
>> explicitly. It also bumps the protocol version to allow peers to
>> identify old nodes which allow bloom filtering of the connection despite
>> lacking the new service bit.
>>
>>
>> Motivation
>> ==========
>>
>> BIP 37 did not specify a service bit for the bloom filter service, thus
>> implicitly assuming that all nodes that serve peers data support it.
>> However, the connection filtering algorithm proposed in BIP 37, and
>> implemented in several clients today, has been shown to provide little
>> to no privacy[1], as well as being a large DoS risk on some nodes[2].
>> Thus, allowing node operators to disable connection bloom filtering is a
>> much-needed feature.
>>
>>
>> Specification
>> =============
>>
>> The following protocol bit is added:
>>
>>     NODE_BLOOM = (1 << 2)
>>
>> Nodes which support bloom filters should set that protocol bit.
>> Otherwise it should remain unset. In addition the protocol version is
>> increased from 70002 to 70011 in the reference implementation. It is
>> often the case that nodes which have a protocol version smaller than
>> 70011, but larger than 70000 support bloom filtered connections without
>> the NODE_BLOOM bit set, however clients which require bloom filtered
>> connections should avoid making this assumption.
>>
>> NODE_BLOOM is distinct from NODE_NETWORK, and it is legal to advertise
>> NODE_BLOOM but not NODE_NETWORK (eg for nodes running in pruned mode
>> which, nonetheless, provide filtered access to the data which they do have).
>>
>> If a node does not support bloom filters but receives a "filterload",
>> "filteradd", or "filterclear" message from a peer the node should
>> disconnect that peer immediately. For backwards compatibility, in
>> initial implementations, nodes may choose to only disconnect nodes which
>> have the new protocol version set and attempt to send a filter command.
>>
>> While outside the scope of this BIP it is suggested that DNS seeds and
>> other peer discovery mechanisms support the ability to specify the
>> services required; current implementations simply check only that
>> NODE_NETWORK is set.
>>
>>
>> Design rational
>> ===============
>>
>> A service bit was chosen as applying a bloom filter is a service.
>>
>> The increase in protocol version is for backwards compatibility. In
>> initial implementations, old nodes which are not yet aware of NODE_BLOOM
>> and use a protocol version < 70011 may still send filter* messages to a
>> node without NODE_BLOOM. This feature may be removed after there are
>> sufficient NODE_BLOOM nodes available and SPV clients have upgraded,
>> allowing node operators to fully close the bloom-related DoS vectors.
>>
>>
>> Reference Implementation
>> ========================
>>
>> https://github.com/bitcoin/bitcoin/pull/6579
>>
>>
>> Copyright
>> =========
>>
>> This document is placed in the public domain.
>>
>>
>> References
>> ==========
>>
>> [1] http://eprint.iacr.org/2014/763
>> [2] ???? is one example where the issues were found, though others
>> independently discovered issues as well. Sample DoS exploit code
>> available at https://github.com/petertodd/bloom-io-attack.
> 

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Peter Todd]

[-- Attachment #1.1: Type: text/plain, Size: 1222 bytes --]

On Sat, Aug 22, 2015 at 01:08:13AM +0000, Matt Corallo wrote:
> > Well actually, we can reference the DoS attacks that Bitcoin XT nodes
> > are undergoing right now - part of the attack is repeated Bloom filter
> > requests to soak up disk IO bandwidth. I've CC'd Gavin and Mike - as far
> > as I know they haven't published details of those attacks - a write-up
> > would be very helpful.
> > 
> > While so far those are being directed only at XT nodes, obviously this
> > is a potential issue for Core nodes as well. Like I mentioned last time
> > around, it's critical that miners aren't affected by these attacks -
> > nodes simply serving SPV wallet clients are much less latency sensitive,
> > so a good DoS attack mitigation strategy would be to have the two
> > classes of nodes out there "in the wild"
> 
> Ehh, I was going more for the oldest mention.

One of the oldest mentions is the to-be-published-later portion of my
Litecoin Audit report; attached.

(see http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-July/003044.html
for the original report/timestamping/verification)

-- 
'peter'[:-1]@petertodd.org
00000000000000000939524874a2896a46ea96bf59776ed869ccff95679cb087

[-- Attachment #1.2: security.txt --]
[-- Type: text/plain, Size: 5701 bytes --]

Security vulnerabilities related to the Litecoin v0.8.3.6 release
=================================================================

Nonce: c0854ae01b1ed8526af3bb6fb82550ff
Date:  Jul 29 2013

To be released in full on January 29, 2014 to the public.


LevelDB
=======

Something not well appreciated outside of the Bitcoin developers is that the
temporary limits on block size and complexity introduced in response to the
fork, automatically removed on May 15th, were simply voluntary measures to
protect against accidental triggering of the fork. The measures did not protect
against malicious attempts to trigger the the fork.

Litecoin is no different. Because of that I strongly recomend that miners be
encouraged to transition to v0.8.3.6 as soon as possible to ensure as much
hashing power as possible is consolidated on one version. Transitioning for
users/merchants is also important, however with sufficient mining power on the
new version it would be difficult to pull off a double-spend attack against an
older version simply because it would take so long to get the required number
of confirmations.

The development team may want to clarify this point to the Litecoin community
and encourage users to be suspicious if it takes an especially long time to get
confirmations. Merchants with automatic systems should use fail-safes triggered
by unusually long confirmation times, and as always ensure that total possible
losses are limited. It would be good if popular "blockchain information" sites
upgraded to v0.8.3.6 along with miners to give users accurate information on
the state of the blockchain. In any case users and merchants should take this
advice in general regardless of specific threats.

I would not be surprised to see someone deliberately attempt to fork Litecoin
by exploiting the issue; there is a lot of hostility torwards and within the
alt-coins.


SPV and network-wide DoS attacks
================================

Bitcoin is quite vulnerable currently to network-wide DoS attacks due to the
maximum connections limits; we do not have any form of filtering on incoming
connections so an attack can be made simply by making sufficient connections to
all nodes that they hit that incoming connections limit. This is public
knowledge, as is the suggestion to stop the attack by having concepts of peer
"usefullness" so that "useless" peers can be dropped. Of course SPV nodes are
badly impacted by such measures.

What isn't as well-known publicly is that Litecoin will make this attack
significantly less costly to the attacker in v0.8.3.6 by adding support for
bloom filters. That support allows the attacker to reduce their bandwidth
consumption to a minimum, making the attack easier to pull off on a wide scale.

The Bitcoin team is aware of the issue. Our plans in the event of an attack are
to ensure that large pools and merchants connect to each other via a private
"darknet" while fixes are implemented. These plans are also useful in the event
of an attack exploiting the vulnerability discussed below.


Bloom filters and disk IO
=========================

However it gets worse: there is nothing limiting peers from requesting blocks.
Without bloom filters bandwidth is a natural limit, however with bloom filters
a malicious peer can simply set the filter to match almost nothing and simply
submit getdata messages to the target requesting all blocks. The target will do
an extremely large amount of disk IO at almost no cost to the attacker.

To quote one core developer in a private conversation regarding bloom filtering
"I think we didn't think hard enough before implementing this"

A good first measure would be to assign a service bit to advertise bloom filter
support:

 /** nServices flags */
 enum
 {
     NODE_NETWORK = (1 << 0),
+    NODE_BLOOM_FILTER = (1 << 1),
 };

Secondly add a command line switch that allows bloom filtering to be turned on
or off entirely. I would suggest that the next version of Litecoin be released
soon and have bloom filters *disabled* by default unless the user specifically
turns them on.

There is a *very* good chance of an attack being launched targetting this
vulnerability by people using it as a way to show their opinion of Mike Hearn;
lots of people strongly dislike him for what they regard as very poor judgement
on security and scalability issues and would be happy to show that a design he
promoted is flawed.

Disabling bloom filering does of course cause problems for SPV clients, however
in the Litecoin realm such clients are non-existent. In the long run DNS seeds
should allow for the specification of desired service bits and rate limiting of
getdata operations implemented. However given that attacks are likely imminent
I strongly suggest a quick solution.

Bitcoin should have done bloom filtering as a service bit on day one; not doing
so was a mistake.

The Bitcoin team is aware of this issue. Please contact me to discuss the
release process for a fix; I will also be happy to review it. Unfortunately due
to the impact on SPV clients this issue is political as well as technical on
the Bitcoin side of things.


CHECKMULTISIG dummy value
=========================

The AreInputsStandard() test does not check the contents of the dummy value
required to spend a BIP11 CHECKMULTISIG scriptPubKey; anything that be put in
that space as a way to get data into the blockchain. Less well appreciated is
that because scriptSigs are unsigned any node, even a non-miner, can change the
txid of a CHECKMULTISIG transaction by modifying the dummy value.

This issue will probably be fixed in Bitcoin soon, not to mention revealed
publically; I'm only including it for the sake of completeness.

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Tom Harding]

On 8/21/2015 3:06 PM, Peter Todd via bitcoin-dev wrote:
> On Fri, Aug 21, 2015 at 05:55:58PM +0000, Matt Corallo wrote:
>> Anyone have the best reference for the DoS issues?
> Well actually, we can reference the DoS attacks that Bitcoin XT nodes
> are undergoing right now - part of the attack is repeated Bloom filter
> requests to soak up disk IO bandwidth.

So, to summarize, someone is attacking Mike Hearn's bitcoin fork. 
Therefore, now is the perfect time to write a BIP and author changes
that begin the process of dropping support for the most broadly
successful class of wallets, which Mike Hearn's SPV client library enables.

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Matt Corallo]

I'll just quote what I said on github:

Neither this pull nor the BIP has any stated intention of phasing out
bloom filtering support in the protocol. As much as I'd love to, I 100%
agree with @mikehearn here, that would break any ability of SPV clients
to operate on the P2P network (either as a way to double-check
centralized servers, or otherwise), and that is really not a good idea
without a replacement in place. This pull/BIP DOES suggest we phase out
REQUIRED bloom filtering support in the protocol - thereby fixing the
peer selection of SPV clients in the face of btcd with some flags/many
patched versions of Core/etc peers, providing a remedy for a potential
DoS attack, etc.

Matt

On 08/24/15 15:19, Tom Harding via bitcoin-dev wrote:
> On 8/21/2015 3:06 PM, Peter Todd via bitcoin-dev wrote:
>> On Fri, Aug 21, 2015 at 05:55:58PM +0000, Matt Corallo wrote:
>>> Anyone have the best reference for the DoS issues?
>> Well actually, we can reference the DoS attacks that Bitcoin XT nodes
>> are undergoing right now - part of the attack is repeated Bloom filter
>> requests to soak up disk IO bandwidth.
> 
> So, to summarize, someone is attacking Mike Hearn's bitcoin fork. 
> Therefore, now is the perfect time to write a BIP and author changes
> that begin the process of dropping support for the most broadly
> successful class of wallets, which Mike Hearn's SPV client library enables.
> 
> 
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Matt Corallo]

BIP Editor: Can I get a BIP # for this?

On 08/21/15 17:55, Matt Corallo via bitcoin-dev wrote:
> Revised copy follows. re: mentioning the HTTP seeding stuff, I'm not
> sure we want to encourage more people aside from bitcoinj to use
> that...I thought about adding a DNS seed section to this bip, but
> decided against it...still, I think we should add the option to select
> service bits to DNS seeds ASAP.
> 
> Re: need to "shard" the blockchain: not sure what you're referring to
> here. The bloom filter stuff requires you to download the chain
> in-order, sure, but you have to do that for headers anyway, and
> hopefully your total data isnt too much more than headers alone.
> 
> Anyone have the best reference for the DoS issues?
> 
> BIP: ?
> Title: NODE_BLOOM service bit
> Author: Matt Corallo <bip@bluematt.me>, Peter Todd <pete@petertodd.org>
> Type: Standards Track (draft)
> Created: 20-08-2015
> 
> Abstract
> ========
> 
> This BIP extends BIP 37, Connection Bloom filtering, by defining a
> service bit to allow peers to advertise that they support bloom filters
> explicitly. It also bumps the protocol version to allow peers to
> identify old nodes which allow bloom filtering of the connection despite
> lacking the new service bit.
> 
> 
> Motivation
> ==========
> 
> BIP 37 did not specify a service bit for the bloom filter service, thus
> implicitly assuming that all nodes that serve peers data support it.
> However, the connection filtering algorithm proposed in BIP 37, and
> implemented in several clients today, has been shown to provide little
> to no privacy[1], as well as being a large DoS risk on some nodes[2].
> Thus, allowing node operators to disable connection bloom filtering is a
> much-needed feature.
> 
> 
> Specification
> =============
> 
> The following protocol bit is added:
> 
>     NODE_BLOOM = (1 << 2)
> 
> Nodes which support bloom filters should set that protocol bit.
> Otherwise it should remain unset. In addition the protocol version is
> increased from 70002 to 70011 in the reference implementation. It is
> often the case that nodes which have a protocol version smaller than
> 70011, but larger than 70000 support bloom filtered connections without
> the NODE_BLOOM bit set, however clients which require bloom filtered
> connections should avoid making this assumption.
> 
> NODE_BLOOM is distinct from NODE_NETWORK, and it is legal to advertise
> NODE_BLOOM but not NODE_NETWORK (eg for nodes running in pruned mode
> which, nonetheless, provide filtered access to the data which they do have).
> 
> If a node does not support bloom filters but receives a "filterload",
> "filteradd", or "filterclear" message from a peer the node should
> disconnect that peer immediately. For backwards compatibility, in
> initial implementations, nodes may choose to only disconnect nodes which
> have the new protocol version set and attempt to send a filter command.
> 
> While outside the scope of this BIP it is suggested that DNS seeds and
> other peer discovery mechanisms support the ability to specify the
> services required; current implementations simply check only that
> NODE_NETWORK is set.
> 
> 
> Design rational
> ===============
> 
> A service bit was chosen as applying a bloom filter is a service.
> 
> The increase in protocol version is for backwards compatibility. In
> initial implementations, old nodes which are not yet aware of NODE_BLOOM
> and use a protocol version < 70011 may still send filter* messages to a
> node without NODE_BLOOM. This feature may be removed after there are
> sufficient NODE_BLOOM nodes available and SPV clients have upgraded,
> allowing node operators to fully close the bloom-related DoS vectors.
> 
> 
> Reference Implementation
> ========================
> 
> https://github.com/bitcoin/bitcoin/pull/6579
> 
> 
> Copyright
> =========
> 
> This document is placed in the public domain.
> 
> 
> References
> ==========
> 
> [1] http://eprint.iacr.org/2014/763
> [2] ???? is one example where the issues were found, though others
> independently discovered issues as well. Sample DoS exploit code
> available at https://github.com/petertodd/bloom-io-attack.
> 
> 
> 
> On 08/21/15 05:42, Peter Todd wrote:
>> On Thu, Aug 20, 2015 at 10:38:19PM -0700, Peter Todd via bitcoin-dev wrote:
>>>> Motivation
>>>> ==========
>>>>
>>>> BIP 37 did not specify a service bit for the bloom filter service, thus
>>>> implicitly assuming that all nodes that serve peers data support it.
>>>> However, the connection filtering algorithm proposed in BIP 37, and
>>>> implemented in several clients today, has been shown to provide little
>>>> to no privacy, as well as being a large DoS risk on some nodes. Thus,
>>>> allowing node operators to disable connection bloom filtering is a
>>>> much-needed feature.
>>>
>>> I'd reference that paper on bloom filters re: the "little to no privacy"
>>> issue. There's also a post in the bitcoinj mailing list somewhere IIRC
>>> talking about the default settings, and how they don't provide any
>>> privacy.
>>
>> Oh, and we should also point out that Bloom filters have scaling issues,
>> as each application of the filter has to scan the whole blockchain -
>> with future blocksize increases these issues increase, in some proposals
>> quite dramatically. The underlying idea also conflicts with some
>> proposals to "shard" the blockchain, again suggesting that we need a bit
>> to handle future upgrades to more scalable designs.
>>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Jeff Garzik]

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

If this is widely deployed + enabled, what is the impact to current wallets
in use?


On Fri, Aug 21, 2015 at 12:46 AM, Matt Corallo via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Peter: Since I stole most of this text from your old BIP, should I leave
> you as an author?
>
> BIP: ?
> Title: NODE_BLOOM service bit
> Author: Matt Corallo <bip@bluematt.me>, Peter Todd <pete@petertodd.org>
> Type: Standards Track (draft)
> Created: 20-08-2015
>
> Abstract
> ========
>
> This BIP extends BIP 37, Connection Bloom filtering, by defining a
> service bit to allow peers to advertise that they support bloom filters
> explicitly. It also bumps the protocol version to allow peers to
> identify old nodes which allow bloom filtering of the connection despite
> lacking the new service bit.
>
>
> Motivation
> ==========
>
> BIP 37 did not specify a service bit for the bloom filter service, thus
> implicitly assuming that all nodes that serve peers data support it.
> However, the connection filtering algorithm proposed in BIP 37, and
> implemented in several clients today, has been shown to provide little
> to no privacy, as well as being a large DoS risk on some nodes. Thus,
> allowing node operators to disable connection bloom filtering is a
> much-needed feature.
>
>
> Specification
> =============
>
> The following protocol bit is added:
>
>     NODE_BLOOM = (1 << 2)
>
> Nodes which support bloom filters should set that protocol bit.
> Otherwise it should remain unset. In addition the protocol version is
> increased from 70002 to 70011 in the reference implementation. It is
> often the case that nodes which have a protocol version smaller than
> 70011, but larger than 70000 support bloom filtered connections without
> the NODE_BLOOM bit set, however clients which require bloom filtered
> connections should avoid making this assumption.
>
> NODE_BLOOM is distinct from NODE_NETWORK, and it is legal to advertise
> NODE_BLOOM but not NODE_NETWORK (eg for nodes running in pruned mode
> which, nonetheless, provide filtered access to the data which they do
> have).
>
> If a node does not support bloom filters but receives a "filterload",
> "filteradd", or "filterclear" message from a peer the node should
> disconnect that peer immediately. For backwards compatibility, in
> initial implementations, nodes may choose to only disconnect nodes which
> have the new protocol version set and attempt to send a filter command.
>
> While outside the scope of this BIP it is suggested that DNS seeds and
> other peer discovery mechanisms support the ability to specify the
> services required; current implementations simply check only that
> NODE_NETWORK is set.
>
>
> Design rational
> ===============
>
> A service bit was chosen as applying a bloom filter is a service.
>
> The increase in protocol version is for backwards compatibility. In
> initial implementations, old nodes which are not yet aware of NODE_BLOOM
> and use a protocol version < 70011 may still send filter* messages to a
> node without NODE_BLOOM. This feature may be removed after there are
> sufficient NODE_BLOOM nodes available and SPV clients have upgraded,
> allowing node operators to fully close the bloom-related DoS vectors.
>
>
> Reference Implementation
> ========================
>
> https://github.com/bitcoin/bitcoin/pull/6579
>
>
> Copyright
> =========
>
> This document is placed in the public domain.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Peter Todd]

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

On Fri, Aug 21, 2015 at 01:48:23AM -0400, Jeff Garzik via bitcoin-dev wrote:
> If this is widely deployed + enabled, what is the impact to current wallets
> in use?

See my comment on the recently-opened issue, reproduced below. In short,
not all that much, especially if we adopt my suggestion of having the
Core implementation accept and respond to bloom filter requests from
non-upgraded clients regardless of whether or not NODE_BLOOM was set
until some fixed upgrade deadline in the future.


    Note that since the last time NODE_BLOOM was proposed, the landcape for
    (lite-)SPV clients has changed significantly in a few key ways:

    1) @mikehearn's [Cartographer](https://github.com/mikehearn/httpseed)
    seed protocol has been created and deployed in production to allow
    (lite-)SPV clients to find nodes supporting arbitrary service bits,
    notable NODE_GETUTXOs.

    2) Bloom filter usage has declined significantly, as lite-SPV clients
    are moving towards using centralized, trusted, servers run by the wallet
    authors. For instance
    [Mycelium](https://github.com/mycelium-com/wallet),
    [GreenBits](https://github.com/greenaddress/GreenBits),
    [AirBitz](https://www.reddit.com/r/Bitcoin/comments/3etohn/whats_wrong_with_breadwallet/ctirou5),
    and [Electrum](https://electrum.org/#home) all fall in this category.

    3) Bloom filters [have been found](http://eprint.iacr.org/2014/763) to
    have severe privacy issues, offering essentially no privacy at all.
    Under many threat models a small number of trusted servers pose less
    privacy security risk than connecting to random, sybil-attackable, peers
    using unencrypted connections and giving those peers very accurate
    wallet contents information.

    4) Finally, Bloom filters still have [unsolved DoS attack
    issues](https://www.reddit.com/r/Bitcoin/comments/3hjak7/the_hard_work_of_core_devs_not_xt_makes_bitcoin/cu9xntf?context=3),
    that will get significantly worse under upcoming blocksize increase
    proposals.

    Re: service bit identifier, I'd just pick 1<<3

    -https://github.com/bitcoin/bitcoin/issues/6578#issuecomment-133226943

-- 
'peter'[:-1]@petertodd.org
00000000000000000402fe6fb9ad613c93e12bddfc6ec02a2bd92f002050594d

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Jeff Garzik]

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

I don't see any link to data backing up "Bloom filter usage has declined
significantly"

Is there actual data showing this feature's use is declining or
non-existent?


On Fri, Aug 21, 2015 at 1:55 AM, Peter Todd <pete@petertodd.org> wrote:

> On Fri, Aug 21, 2015 at 01:48:23AM -0400, Jeff Garzik via bitcoin-dev
> wrote:
> > If this is widely deployed + enabled, what is the impact to current
> wallets
> > in use?
>
> See my comment on the recently-opened issue, reproduced below. In short,
> not all that much, especially if we adopt my suggestion of having the
> Core implementation accept and respond to bloom filter requests from
> non-upgraded clients regardless of whether or not NODE_BLOOM was set
> until some fixed upgrade deadline in the future.
>
>
>     Note that since the last time NODE_BLOOM was proposed, the landcape for
>     (lite-)SPV clients has changed significantly in a few key ways:
>
>     1) @mikehearn's [Cartographer](https://github.com/mikehearn/httpseed)
>     seed protocol has been created and deployed in production to allow
>     (lite-)SPV clients to find nodes supporting arbitrary service bits,
>     notable NODE_GETUTXOs.
>
>     2) Bloom filter usage has declined significantly, as lite-SPV clients
>     are moving towards using centralized, trusted, servers run by the
> wallet
>     authors. For instance
>     [Mycelium](https://github.com/mycelium-com/wallet),
>     [GreenBits](https://github.com/greenaddress/GreenBits),
>     [AirBitz](
> https://www.reddit.com/r/Bitcoin/comments/3etohn/whats_wrong_with_breadwallet/ctirou5
> ),
>     and [Electrum](https://electrum.org/#home) all fall in this category.
>
>     3) Bloom filters [have been found](http://eprint.iacr.org/2014/763) to
>     have severe privacy issues, offering essentially no privacy at all.
>     Under many threat models a small number of trusted servers pose less
>     privacy security risk than connecting to random, sybil-attackable,
> peers
>     using unencrypted connections and giving those peers very accurate
>     wallet contents information.
>
>     4) Finally, Bloom filters still have [unsolved DoS attack
>     issues](
> https://www.reddit.com/r/Bitcoin/comments/3hjak7/the_hard_work_of_core_devs_not_xt_makes_bitcoin/cu9xntf?context=3
> ),
>     that will get significantly worse under upcoming blocksize increase
>     proposals.
>
>     Re: service bit identifier, I'd just pick 1<<3
>
>     -https://github.com/bitcoin/bitcoin/issues/6578#issuecomment-133226943
>
> --
> 'peter'[:-1]@petertodd.org
> 00000000000000000402fe6fb9ad613c93e12bddfc6ec02a2bd92f002050594d
>

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

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Peter Todd]

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

On Fri, Aug 21, 2015 at 02:01:06AM -0400, Jeff Garzik wrote:
> I don't see any link to data backing up "Bloom filter usage has declined
> significantly"
> 
> Is there actual data showing this feature's use is declining or
> non-existent?

I run a number of high speed nodes and while I don't have historical
logs handy over time, I've noticed a drop from about %5-%10 SPV clients
at any one time to closer to %1 (Matt: you have a few TB of logs saved
don't you?)

Also, as I mentioned, just look at the popularity of wallets such as
Mycelium that are not adopting bloom filters, but going with SPV
verification of block headers w/ lookup servers.

Anyway, look at the analogous implementation of NODE_GETUTXO's, which
helpfully has provided the infrastructure for wallets that need bloom
filters to find appropriate nodes to connect too - we certainely aren't
seeing any shortages of nodes for those wallets to use.

-- 
'peter'[:-1]@petertodd.org
00000000000000000402fe6fb9ad613c93e12bddfc6ec02a2bd92f002050594d

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Chris Pacia]

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

On Aug 21, 2015 2:07 AM, "Peter Todd via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Also, as I mentioned, just look at the popularity of wallets such as
> Mycelium that are not adopting bloom filters, but going with SPV
> verification of block headers w/ lookup servers.

Related I recently had a conversation with a Mycelium employee who told me
they were considering moving to spv/bloom because of the server issues
Andreas mentioned.

I don't know any more about their plans, but I wouldn't assume the above
statement to be correct.

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

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Peter Todd]

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

On Fri, Aug 21, 2015 at 06:15:16PM -0400, Chris Pacia wrote:
> On Aug 21, 2015 2:07 AM, "Peter Todd via bitcoin-dev" <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> > Also, as I mentioned, just look at the popularity of wallets such as
> > Mycelium that are not adopting bloom filters, but going with SPV
> > verification of block headers w/ lookup servers.
> 
> Related I recently had a conversation with a Mycelium employee who told me
> they were considering moving to spv/bloom because of the server issues
> Andreas mentioned.
> 
> I don't know any more about their plans, but I wouldn't assume the above
> statement to be correct.

That'd be a foolish design decision to move exclusively over; their
wallet was safe to use during the recent fork, unlike Android Wallet,
precisely because of their existing design.

In any case, regardless of whether we're wrong about the popularity
issue, I've yet to see any issues raised with implementing NODE_BLOOM
that will adversely affect such wallets - we've certainly got no
shortage of node capacity to go around.

-- 
'peter'[:-1]@petertodd.org
00000000000000000402fe6fb9ad613c93e12bddfc6ec02a2bd92f002050594d

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Tom Harding]

On 8/20/2015 11:07 PM, Peter Todd via bitcoin-dev wrote:

> I run a number of high speed nodes and while I don't have historical
> logs handy over time, I've noticed a drop from about %5-%10 SPV
> clients at any one time tocloser to %1


Just checked mine and found 20.4% bitcoinj connections.

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Mike Hearn]

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

NACK: stated rationales are invalid: both privacy and DoS (see below for
experimental data).


1 - Bloom filtering doesn't add privacy for node operators, it adds privacy
for lightweight wallets. And in fact, with a high FP rate it does do that.
Most users want both low bandwidth usage *and* query scrambling, which is
harder to do but not impossible. There is a clear roadmap for how to
implement that with smarter clients: no protocol changes are needed.

So the first stated rationale is spurious: disabling Bloom filtering
doesn't improve privacy for anyone. It can only hurt.



2 - SPV usage is rising, not falling.

Peter's data is flawed because he ignored the fact that SPV clients tend to
connect, sync, then disconnect. They don't remain connected all the time.
So merely examining a random snapshot of what's connected at a single point
in time will give wildly varying and almost random results.

A more scientifically valid approach is to check the number of actual
connections over a long span of time. Here's the data from my node:

mike@plan99:~/.bitcoin$ grep -Po 'receive version message: ([^:]*):'
debug.log |sort |uniq -c|sort -n|tac|head -n 10
  11027 receive version message: /getaddr.bitnodes.io:
   6264 receive version message: /bitcoinseeder:
   4944 receive version message: /bitcoinj:
   2531 receive version message: /Snoopy:
   2362 receive version message: /breadwallet:
   1127 receive version message: /Satoshi:
    204 receive version message: /Bitcoin XT:
    128 receive version message: /BitCoinJ:
     97 receive version message: /Bither1.3.8/:
     82 receive version message: /Bitaps:

Once crawlers are removed, SPV wallets (bitcoinj, breadwallet) make up the
bulk of all P2P clients. This is very far from 1% and falling, as Todd
wrongly suggests.



3 - It is said that there is a DoS attack possible. This claim does not
seem to have been researched.

I decided to test it out for real, so I implemented a DoS attack similar to
the one we've seen against XT nodes: it sends getdata for large (1mb)
filtered blocks over and over again as fast as possible.

As was reported and makes sense, CPU usage goes to 100%. However I couldn't
see any other effects. RPCs still react immediately, the Qt GUI is fully
responsive, I was even able to sync another SPV client to that node and it
proceeded at full speed. It's actually pretty nice to see how well it held
up.

Most importantly transactions and blocks continued to be relayed without
delay. I saw my VPS node receive a block only eight seconds after my local
node, which is well within normal propagation delays.

There's another very important point here: I profiled my local node whilst
it was under this attack. It turns out that Bloom filtering is extremely
fast. 90% of the CPU time is spent on loading and deserializing the data
from disk. Only 10% of the CPU time was spent actually filtering.

Thus you can easily trigger exactly the same DoS attack by just using
regular getdata requests on large blocks over and over. You don't need
Bloom filtering. If you don't want to actually download the blocks just
don't TCP ACK the packets and then FIN after a few seconds .... the data
will all have been loaded and be sitting in the send buffers.

So even if I refine the attack and find a way to actually deny service to
someone, the fix would have to apply to regular non-filtered block fetches
too, which cannot be disabled.


In summary: this BIP doesn't solve anything, but does create a big upgrade
headache.

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

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Andreas Schildbach]

On 08/21/2015 07:55 AM, Peter Todd via bitcoin-dev wrote:

>     2) Bloom filter usage has declined significantly, as lite-SPV clients
>     are moving towards using centralized, trusted, servers run by the wallet
>     authors. For instance
>     [Mycelium](https://github.com/mycelium-com/wallet),
>     [GreenBits](https://github.com/greenaddress/GreenBits),
>     [AirBitz](https://www.reddit.com/r/Bitcoin/comments/3etohn/whats_wrong_with_breadwallet/ctirou5),
>     and [Electrum](https://electrum.org/#home) all fall in this category.

None of these wallets (except Electrum maybe) could gain a significant
amount of new users during the last year or so, if you look at the stats
of Google Play.

Specifically Mycelium lost a significant amount of users during the last
stress test when their centralized infrastructure was overloaded. As a
consenquence, their developer announced on Reddit to try moving the
wallet to SPV.

https://www.reddit.com/r/Bitcoin/comments/3db7qr/mycelium_servers_down/

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Matt Corallo]

The proposal will not break any existing clients in the first release.
After sufficient time to upgrade SPV clients, a new version will be
released which will result in older SPV clients finding themselves
disconnected from peers when they send filter* commands, so they can go
find other peers which do support bloom filtering.

On 08/21/15 05:48, Jeff Garzik wrote:
> If this is widely deployed + enabled, what is the impact to current
> wallets in use?
> 
> 
> On Fri, Aug 21, 2015 at 12:46 AM, Matt Corallo via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org
> <mailto:bitcoin-dev@lists.linuxfoundation.org>> wrote:
> 
>     Peter: Since I stole most of this text from your old BIP, should I leave
>     you as an author?
> 
>     BIP: ?
>     Title: NODE_BLOOM service bit
>     Author: Matt Corallo <bip@bluematt.me <mailto:bip@bluematt.me>>,
>     Peter Todd <pete@petertodd.org <mailto:pete@petertodd.org>>
>     Type: Standards Track (draft)
>     Created: 20-08-2015
> 
>     Abstract
>     ========
> 
>     This BIP extends BIP 37, Connection Bloom filtering, by defining a
>     service bit to allow peers to advertise that they support bloom filters
>     explicitly. It also bumps the protocol version to allow peers to
>     identify old nodes which allow bloom filtering of the connection despite
>     lacking the new service bit.
> 
> 
>     Motivation
>     ==========
> 
>     BIP 37 did not specify a service bit for the bloom filter service, thus
>     implicitly assuming that all nodes that serve peers data support it.
>     However, the connection filtering algorithm proposed in BIP 37, and
>     implemented in several clients today, has been shown to provide little
>     to no privacy, as well as being a large DoS risk on some nodes. Thus,
>     allowing node operators to disable connection bloom filtering is a
>     much-needed feature.
> 
> 
>     Specification
>     =============
> 
>     The following protocol bit is added:
> 
>         NODE_BLOOM = (1 << 2)
> 
>     Nodes which support bloom filters should set that protocol bit.
>     Otherwise it should remain unset. In addition the protocol version is
>     increased from 70002 to 70011 in the reference implementation. It is
>     often the case that nodes which have a protocol version smaller than
>     70011, but larger than 70000 support bloom filtered connections without
>     the NODE_BLOOM bit set, however clients which require bloom filtered
>     connections should avoid making this assumption.
> 
>     NODE_BLOOM is distinct from NODE_NETWORK, and it is legal to advertise
>     NODE_BLOOM but not NODE_NETWORK (eg for nodes running in pruned mode
>     which, nonetheless, provide filtered access to the data which they
>     do have).
> 
>     If a node does not support bloom filters but receives a "filterload",
>     "filteradd", or "filterclear" message from a peer the node should
>     disconnect that peer immediately. For backwards compatibility, in
>     initial implementations, nodes may choose to only disconnect nodes which
>     have the new protocol version set and attempt to send a filter command.
> 
>     While outside the scope of this BIP it is suggested that DNS seeds and
>     other peer discovery mechanisms support the ability to specify the
>     services required; current implementations simply check only that
>     NODE_NETWORK is set.
> 
> 
>     Design rational
>     ===============
> 
>     A service bit was chosen as applying a bloom filter is a service.
> 
>     The increase in protocol version is for backwards compatibility. In
>     initial implementations, old nodes which are not yet aware of NODE_BLOOM
>     and use a protocol version < 70011 may still send filter* messages to a
>     node without NODE_BLOOM. This feature may be removed after there are
>     sufficient NODE_BLOOM nodes available and SPV clients have upgraded,
>     allowing node operators to fully close the bloom-related DoS vectors.
> 
> 
>     Reference Implementation
>     ========================
> 
>     https://github.com/bitcoin/bitcoin/pull/6579
> 
> 
>     Copyright
>     =========
> 
>     This document is placed in the public domain.
>     _______________________________________________
>     bitcoin-dev mailing list
>     bitcoin-dev@lists.linuxfoundation.org
>     <mailto:bitcoin-dev@lists.linuxfoundation.org>
>     https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 
> 

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Wladimir J. van der Laan]

> NODE_BLOOM is distinct from NODE_NETWORK, and it is legal to advertise
> NODE_BLOOM but not NODE_NETWORK (eg for nodes running in pruned mode
> which, nonetheless, provide filtered access to the data which they do have).

But is this useful without having decided on a way to signal which blocks pruned nodes do have?

It looks like the part between paranthesis is speculation and should be left to a future BIP. 

Wladimir

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Matt Corallo]

Its more of a statement of "in the future, we expect things to happen
which would make this an interesting thing to do, so we state here that
it is not against spec to do so". Could reword it as "NODE_BLOOM is
distinct from NODE_NETWORK, and it is legal to advertise NODE_BLOOM but
not NODE_NETWORK (though there is little reason to do so now, some
proposals may make this more useful in the future)"?

Matt

On 08/24/15 15:29, Wladimir J. van der Laan wrote:
>> NODE_BLOOM is distinct from NODE_NETWORK, and it is legal to advertise
>> NODE_BLOOM but not NODE_NETWORK (eg for nodes running in pruned mode
>> which, nonetheless, provide filtered access to the data which they do have).
> 
> But is this useful without having decided on a way to signal which blocks pruned nodes do have?
> 
> It looks like the part between paranthesis is speculation and should be left to a future BIP. 
> 
> Wladimir
> 

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Wladimir J. van der Laan]

On Mon, Aug 24, 2015 at 05:37:51PM +0000, Matt Corallo wrote:
> Its more of a statement of "in the future, we expect things to happen
> which would make this an interesting thing to do, so we state here that
> it is not against spec to do so". Could reword it as "NODE_BLOOM is
> distinct from NODE_NETWORK, and it is legal to advertise NODE_BLOOM but
> not NODE_NETWORK (though there is little reason to do so now, some
> proposals may make this more useful in the future)"?

Yes, it makes sense to not explicitly exclude it. 
Looks good to me.

Wladimir

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Eric Lombrozo]

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

When I was working on mSIGNA I became a little torn on the whole filtering
mechanism. I fully support connection filtering...but in practice always
run my own full node instances to connect to due to the three fatal flaws:
1) no mechanism for short proofs of tx nonexclusion, txout unspentness,
block validity, nor the ability to find the first instance of the use of a
scriptPubKey without full blockchain scanning, 2) poor privacy, 3) lack of
incentives to run servers.

I always felt that BIP37 was necessarily a step towards a client/server
architecture.

Having said that, I have found the filter mechanism useful, if only because
no "special" server is required. However, in practice I'd rather make the
distinction between trustless peers and a client/server model more explicit.

On Mon, Aug 24, 2015, 10:41 AM Wladimir J. van der Laan via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Mon, Aug 24, 2015 at 05:37:51PM +0000, Matt Corallo wrote:
> > Its more of a statement of "in the future, we expect things to happen
> > which would make this an interesting thing to do, so we state here that
> > it is not against spec to do so". Could reword it as "NODE_BLOOM is
> > distinct from NODE_NETWORK, and it is legal to advertise NODE_BLOOM but
> > not NODE_NETWORK (though there is little reason to do so now, some
> > proposals may make this more useful in the future)"?
>
> Yes, it makes sense to not explicitly exclude it.
> Looks good to me.
>
> Wladimir
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Peter Todd]

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

On Mon, Aug 24, 2015 at 05:37:51PM +0000, Matt Corallo via bitcoin-dev wrote:
> Its more of a statement of "in the future, we expect things to happen
> which would make this an interesting thing to do, so we state here that
> it is not against spec to do so". Could reword it as "NODE_BLOOM is
> distinct from NODE_NETWORK, and it is legal to advertise NODE_BLOOM but
> not NODE_NETWORK (though there is little reason to do so now, some
> proposals may make this more useful in the future)"?

ACK

-- 
'peter'[:-1]@petertodd.org
000000000000000008aa6cf51dfde20be1d54e671494a44fb7f252fd4e913162

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Matt Corallo]

BIP 111 was assigned, pull request (with the proposed changes) available
at https://github.com/bitcoin/bips/pull/183

Matt

On 08/24/15 18:00, Peter Todd wrote:
> On Mon, Aug 24, 2015 at 05:37:51PM +0000, Matt Corallo via bitcoin-dev wrote:
>> Its more of a statement of "in the future, we expect things to happen
>> which would make this an interesting thing to do, so we state here that
>> it is not against spec to do so". Could reword it as "NODE_BLOOM is
>> distinct from NODE_NETWORK, and it is legal to advertise NODE_BLOOM but
>> not NODE_NETWORK (though there is little reason to do so now, some
>> proposals may make this more useful in the future)"?
> 
> ACK
> 

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Eric Lombrozo]

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

It would be very useful to not only be able to switch filtering on and off
globally...but to be able to switch on a per-connection basis. But then
again, perhaps it would be smarter to ditch the whole bloom filter thing in
favor of an actual client/server architecture with proper authentication
and access controls.

The RPC was supposed to be this client/server architecture...but in
practice it sucks so bad for doing anything beyond administering a node
instance you fully control yourself that I eschewed it entirely in my
wallet design.

On Mon, Aug 24, 2015, 11:07 AM Matt Corallo via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> BIP 111 was assigned, pull request (with the proposed changes) available
> at https://github.com/bitcoin/bips/pull/183
>
> Matt
>
> On 08/24/15 18:00, Peter Todd wrote:
> > On Mon, Aug 24, 2015 at 05:37:51PM +0000, Matt Corallo via bitcoin-dev
> wrote:
> >> Its more of a statement of "in the future, we expect things to happen
> >> which would make this an interesting thing to do, so we state here that
> >> it is not against spec to do so". Could reword it as "NODE_BLOOM is
> >> distinct from NODE_NETWORK, and it is legal to advertise NODE_BLOOM but
> >> not NODE_NETWORK (though there is little reason to do so now, some
> >> proposals may make this more useful in the future)"?
> >
> > ACK
> >
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Matt Corallo]

On 08/24/15 18:15, Eric Lombrozo wrote:
> It would be very useful to not only be able to switch filtering on and
> off globally...but to be able to switch on a per-connection basis.

I'm not sure what your reasoning for this is? If your concern is that
someone starts DoS attacking you with bloom-based attacks, you should
just disconnect them as an attacker, and announce that you support bloom
filtering globally. If you want to serve your own nodes, then I dont
think this BIP doesnt allow you to do so, just needs an implementation.

> But
> then again, perhaps it would be smarter to ditch the whole bloom filter
> thing in favor of an actual client/server architecture with proper
> authentication and access controls.

Trustless (and non-privacy-losing) proposals welcome :)

> The RPC was supposed to be this client/server architecture...but in
> practice it sucks so bad for doing anything beyond administering a node
> instance you fully control yourself that I eschewed it entirely in my
> wallet design.
> 
> 
> On Mon, Aug 24, 2015, 11:07 AM Matt Corallo via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org
> <mailto:bitcoin-dev@lists.linuxfoundation.org>> wrote:
> 
>     BIP 111 was assigned, pull request (with the proposed changes) available
>     at https://github.com/bitcoin/bips/pull/183
> 
>     Matt
> 
>     On 08/24/15 18:00, Peter Todd wrote:
>     > On Mon, Aug 24, 2015 at 05:37:51PM +0000, Matt Corallo via
>     bitcoin-dev wrote:
>     >> Its more of a statement of "in the future, we expect things to happen
>     >> which would make this an interesting thing to do, so we state
>     here that
>     >> it is not against spec to do so". Could reword it as "NODE_BLOOM is
>     >> distinct from NODE_NETWORK, and it is legal to advertise
>     NODE_BLOOM but
>     >> not NODE_NETWORK (though there is little reason to do so now, some
>     >> proposals may make this more useful in the future)"?
>     >
>     > ACK
>     >
>     _______________________________________________
>     bitcoin-dev mailing list
>     bitcoin-dev@lists.linuxfoundation.org
>     <mailto:bitcoin-dev@lists.linuxfoundation.org>
>     https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Wladimir J. van der Laan]

On Mon, Aug 24, 2015 at 06:15:39PM +0000, Eric Lombrozo via bitcoin-dev wrote:
> It would be very useful to not only be able to switch filtering on and off
> globally...but to be able to switch on a per-connection basis. But then

You don't necessarily need to send everyone the same nServices bits.
E.g. you could give whitelisted peers special privileges.

But only advertize the intersection of your supported services (eg those you offer to the general public) in `addr` messages.

Wladimir

Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP

[Eric Lombrozo]

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

Indeed, so I don't really have a problem with this proposal.

On Mon, Aug 24, 2015, 11:30 AM Wladimir J. van der Laan <laanwj@gmail.com>
wrote:

> On Mon, Aug 24, 2015 at 06:15:39PM +0000, Eric Lombrozo via bitcoin-dev
> wrote:
> > It would be very useful to not only be able to switch filtering on and
> off
> > globally...but to be able to switch on a per-connection basis. But then
>
> You don't necessarily need to send everyone the same nServices bits.
> E.g. you could give whitelisted peers special privileges.
>
> But only advertize the intersection of your supported services (eg those
> you offer to the general public) in `addr` messages.
>
> Wladimir
>

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