References: <55D6AD19.10305@mattcorallo.com> <20150821053819.GA18176@muck>
	<20150821054219.GB18176@muck> <55D7662E.4090104@mattcorallo.com>
To: Gregory Maxwell <gmaxwell@gmail.com>
From: Matt Corallo <lf-lists@mattcorallo.com>
Message-ID: <55D7CBA1.7080606@mattcorallo.com>
Date: Sat, 22 Aug 2015 01:08:49 +0000
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101
	Thunderbird/38.1.0
MIME-Version: 1.0
In-Reply-To: <55D7662E.4090104@mattcorallo.com>
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: 7bit
Cc: bitcoin-dev@lists.linuxfoundation.org
Subject: Re: [bitcoin-dev] Revisiting NODE_BLOOM: Proposed BIP
Precedence: list

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
>