Keep track of recently rejected transactions with a rolling bloom filter #6452

petertodd · 2015-07-17T10:55:40Z

@Marcos's #6450, but with a rolling bloom filter instead of a limitedmap. The number of rejected txids saved has been greatly improved, which should help in some attack scenarios. In addition the filter is now cleared every time the chaintip changes, rather than based on a timeout, to better match the cases where a previously rejected transaction would now be valid. (nLockTime, double-spends, etc.)

sipa · 2015-07-17T18:30:03Z

Untested ACK. I was thinking about implementing something like this myself while working on the mempool limitation.

Given the false positive rate and the amount of memory usage, I think this approach is better than #6450.

ajweiss · 2015-07-17T20:48:59Z

If I've done the math right, I think it would only take about a million rejects to push the false positive rate on this near 98%. At 1000 txn/sec, this is somewhere on the order of 20 minutes. It only takes a few hundred thousand to push it into low, yet still problematic double digit false positive territory.

I also don't fully understand the comment in the code that claims this uses 1.7MB. I calculated the filter size myself using the parameters from the code and I get about 430k each, for around 960k total.

It's worth noting that the attack surface here involves filling up the bloom filter and causing a high false positive rate which can blind nodes to incoming transactions. If a bloom filter is used here, I think it needs to be larger. (Maybe that was the intention?)

Thoughts?

ajweiss · 2015-07-17T21:03:47Z

Ahh, I see nevermind. I didn't catch that the rolling stuff allocates filters at 2x size, and rotates them when they're half full making the fprate never go above the specified value (1e-6).

The sizes add up now too...

Looks good.

laanwj · 2015-07-18T07:18:12Z

src/main.cpp

Not sure if this should be insecure_rand. insecure_rand is meant for high-performance low-security use.

No performance constraints: this is done once, at initialization time

If this value could be guessed by an adversary, there is additional DoS risk.

Also, the spread between nodes should be as uniform as possible to make sure that if false positives happen, they are at least as non-consistent as possible.
So IMO let's use the normal GetRand.

What I am also slightly worried about here is the static global initialization. Random generators will not have been initialized at that time.

Changed to GetRand()

The other CRollingBloom filter use is in net.cpp, which also uses insecure_rand() - might be worth it to fix that too.

Re: static global initialization, it'd be possible to change the seed here every time the bloom filter is cleared; dunno what's the best way to actually do that in C++ though.

GetRand() relies on openssl being initialized, so something very bad could happen if things are executed in the wrong order.
Thus I'd prefer an explicit initialization. Possibly make recentRejects a pointer and explicitly allocate/deallocate it.
Setting a new tweak every time the filter is cleared may be overkill, I don't know.
Agree re: net.cpp, although that structure is per-peer so there's not as much scope for monkey tricks.

At what point can we actually guarantee OpenSSL is initialized? Remember that the capcity of the filter has to be pretty large - 120,000 transactions - so it could take a long time before it gets rolled over if a bad initialization is an issue.

Regardless of how it gets initialized, only 1/1,000,000 txs will be affected. Sure an attacker might be able to pick-and-choose that subset, but I can't think of any example other than zeroconf crap where that actually matters.

laanwj · 2015-07-18T07:19:42Z

utACK apart from randomness nit.

Edit: as using randomness during static initialization seems error prone.

petertodd · 2015-07-19T20:26:17Z

@laanwj As per @sipa's suggestion I added a reset() method that resets nTweak as well, and went even further to change the CRollingBloomFilter to handle setting nTweak for you. This is a bigger patch that changes addrKnown a bit as well, but overall this should simplify all uses by ensuring the default behavior is a secure RNG source.

morcos · 2015-07-20T00:53:48Z

src/main.cpp

I didn't realize you changed this. For whatever reason the previous behavior was to relay transactions we rejected (even for reasons other than we already had them) if we received them from a white listed peer. It might be better to leave this unchanged. Although orphan transactions are already not relayed, so its not quite consistent as is.

Given that relaying invalid txs can get you banned, seems like a vulnerability waiting to be exploited... Sure this is for whitelisted peers only, but there's many shades of grey in white. :)

I think there are some companies that rely on the current behavior that peers that have you whitelisted relay all your transactions. E.g. they use a bitcoin node as border router.
Agree that it's a grey area, but changing this without announcement is a bad idea.

I think the behaviour should be to relay every valid transaction received from a whitelisted peer (including when it was in the mempool already).

I don't think we should relay invalid transactions from whitelisted peers (especially not things tha would otherwise trigger DoS score), but instead yell loudly that some whitelisted peer is broken.

Concept ACK here, though.

Fair enough - reverted and added a FIXME for a future patch to fix.

sipa · 2015-07-24T18:33:54Z

ACK

morcos · 2015-07-27T15:46:30Z

See comments here, I'll just rebase #6470 on this when it's merged and/or finished.

While CBloomFilter is usually used with an explicitly set nTweak, CRollingBloomFilter is only used internally. Requiring every caller to set nTweak is error-prone and redundant; better to have the class handle that for you with a high-quality randomness source. Additionally when clearing the filter it makes sense to change nTweak as well to recover from a bad setting, e.g. due to insufficient randomness at initialization, so the clear() method is replaced by a reset() method that sets a new, random, nTweak value.

sipa · 2015-07-27T17:26:54Z

Some suggested changes: https://github.com/sipa/bitcoin/commits/recent-rejects-rolling-bloom

laanwj · 2015-07-28T09:03:25Z

Code review ACK on sipa's changes

Nodes can have divergent policies on which transactions they will accept and relay. This can cause you to repeatedly request and reject the same tx after its inved to you from various peers which have accepted it. Here we add rolling bloom filter to keep track of such rejections, clearing the filter every time the chain tip changes. Credit goes to Alex Morcos, who created the patch that this code is based on. Original code by Peter Todd. Refactored to not construct the filter at startup time by Pieter Wuille.

petertodd · 2015-07-28T19:53:32Z

ACK sipa's changes as well, updated this pull-req to them.

I'll note there is a chance that petertodd@d741371 could lead to intermittent unit test failures.

jtimon · 2015-07-29T11:21:52Z

I still don't understand why can't we reuse the same cache for rejections and #6077 (what I wanted to do in jtimon@935ee1e to make 0-size mempools safe).
Does anybody have any answer (I failed to get it on IRC)?

laanwj · 2015-07-31T10:08:19Z

Error in Travis during the Python unit tests:

bitcoind: /home/travis/build/bitcoin/bitcoin/depends/i686-pc-linux-gnu/include/boost/smart_ptr/scoped_ptr.hpp:99: T* boost::scoped_ptr<T>::operator->() const [with T = CRollingBloomFilter]: Assertion `px != 0' failed.
Unexpected exception caught during testing: ''

I'll note there is a chance that petertodd/bitcoin@d741371 could lead to intermittent unit test failures.

The above failure does not seem related to the value of the tweak.

Edit: I can reproduce the same problem locally, consistently, when I start e.g. wallet.py.
Adding assertions:

bitcoind: main.cpp:3700: bool AlreadyHave(const CInv&): Assertion `recentRejects' failed.

Either

a race between initialization of recentRejects and AlreadyHave
initialization of recentRejects in InitBlockIndex() is never reached

laanwj · 2015-07-31T12:29:16Z

This can be solved by moving

    // Initialize global variables that cannot be constructed at startup.
    recentRejects.reset(new CRollingBloomFilter(120000, 0.000001));

~~to before if (!reIndex) {...~~

Edit: Hm no... that doesn't do it either. It needs to go all the way to the beginning of the function, after locking cs_main.

laanwj · 2015-07-31T16:32:01Z

Continued in #6498

dcousens · 2015-10-04T23:28:36Z

edit: moved comments to #6498

petertodd mentioned this pull request Jul 17, 2015

Keep track of recently rejected transactions #6450

Closed

petertodd force-pushed the recent-rejects-rolling-bloom branch 2 times, most recently from 305e61b to 5250f5f Compare July 17, 2015 12:08

laanwj added the P2P label Jul 17, 2015

sipa mentioned this pull request Jul 17, 2015

Limited mempool + floating relay fee + rejection caching + mempool expiry #6455

Closed

laanwj reviewed Jul 18, 2015
View reviewed changes

petertodd force-pushed the recent-rejects-rolling-bloom branch 3 times, most recently from 3cff511 to fb09181 Compare July 19, 2015 20:23

petertodd force-pushed the recent-rejects-rolling-bloom branch 3 times, most recently from c3ae483 to 767e536 Compare July 19, 2015 20:35

morcos reviewed Jul 20, 2015
View reviewed changes

petertodd force-pushed the recent-rejects-rolling-bloom branch from 767e536 to 65c4c69 Compare July 20, 2015 15:20

petertodd and others added 4 commits July 27, 2015 18:37

Add uint256 support to CRollingBloomFilter

bbe4108

Reuse vector hashing code for uint256

a3d65fe

Only use randomly created nonces in CRollingBloomFilter.

d741371

petertodd force-pushed the recent-rejects-rolling-bloom branch from 65c4c69 to 0847d9c Compare July 28, 2015 19:50

laanwj mentioned this pull request Jul 31, 2015

Keep track of recently rejected transactions with a rolling bloom filter (cont'd) #6498

Merged

laanwj closed this Jul 31, 2015

paveljanik mentioned this pull request Oct 1, 2015

rejected txs and blocks get re-downloaded when seen again #1195

Closed

bitcoin locked as resolved and limited conversation to collaborators Sep 8, 2021

Keep track of recently rejected transactions with a rolling bloom filter #6452

Keep track of recently rejected transactions with a rolling bloom filter #6452

Uh oh!

Conversation

petertodd commented Jul 17, 2015

Uh oh!

sipa commented Jul 17, 2015

Uh oh!

ajweiss commented Jul 17, 2015

Uh oh!

ajweiss commented Jul 17, 2015

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

laanwj commented Jul 18, 2015

Uh oh!

petertodd commented Jul 19, 2015

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sipa commented Jul 24, 2015

Uh oh!

morcos commented Jul 27, 2015

Uh oh!

sipa commented Jul 27, 2015

Uh oh!

laanwj commented Jul 28, 2015

Uh oh!

petertodd commented Jul 28, 2015

Uh oh!

jtimon commented Jul 29, 2015

Uh oh!

laanwj commented Jul 31, 2015

Uh oh!

laanwj commented Jul 31, 2015

Uh oh!

laanwj commented Jul 31, 2015

Uh oh!

dcousens commented Oct 4, 2015

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants