Keep track of recently rejected transactions with a rolling bloom filter

petertodd commented at 10:55 am on July 17, 2015: contributor

@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.)

petertodd force-pushed on Jul 17, 2015

laanwj added the label P2P on Jul 17, 2015

sipa commented at 6:30 pm on July 17, 2015: member

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 commented at 8:48 pm on July 17, 2015: contributor

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 commented at 9:03 pm on July 17, 2015: contributor

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.

in src/main.cpp: in 5250f5fbcb outdated

172+     * million to make it highly unlikely for users to have issues with this
173+     * filter.
174+     *
175+     * Memory used: 1.7MB
176+     */
177+    CRollingBloomFilter recentRejects(120000, 0.000001, insecure_rand());

laanwj commented at 7:18 am on July 18, 2015:

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.

petertodd commented at 7:46 am on July 18, 2015:

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.

laanwj commented at 7:59 am on July 18, 2015:

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.

petertodd commented at 8:12 am on July 18, 2015:

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 commented at 7:19 am on July 18, 2015: member

utACK apart from randomness nit.

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

petertodd force-pushed on Jul 18, 2015

petertodd force-pushed on Jul 19, 2015

petertodd commented at 8:26 pm on July 19, 2015: contributor

@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.

petertodd force-pushed on Jul 19, 2015

in src/main.cpp: in 767e5366a1 outdated

4320+            // already in the mempool; if the tx isn't in the mempool that
4321+            // means it was rejected and we shouldn't ask for it again.
4322+            if (!mempool.exists(tx.GetHash())) {
4323+                recentRejects.insert(tx.GetHash());
4324+            }
4325+            else if (pfrom->fWhitelisted) {

morcos commented at 0:53 am on July 20, 2015:

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.

petertodd commented at 11:25 am on July 20, 2015:

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. :)

laanwj commented at 2:37 pm on July 20, 2015:

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.

sipa commented at 3:21 pm on July 20, 2015:

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.

petertodd commented at 3:21 pm on July 20, 2015:

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

in src/bloom.h: in 767e5366a1 outdated

103@@ -103,7 +104,11 @@ class CBloomFilter
104 
105 /**
106  * RollingBloomFilter is a probabilistic "keep track of most recently inserted" set.
107- * Construct it with the number of items to keep track of, and a false-positive rate.
108+ * Construct it with the number of items to keep track of, and a false-positive
109+ * rate. Unlike CBloomFilter, by default nTweak is set to a cryptographically
110+ * secure random value for you. Similarly rather than clear() the method

sipa commented at 3:13 pm on July 20, 2015:

I wonder whether claiming that a 32-bit random integer can be cryptographically secure…

petertodd commented at 3:22 pm on July 20, 2015:

Well yes! It’s cryptographically secure if there are 32-bits of randomness unknown to the attacker; the point is the attacker has no insight into what the value is, which is what we need for this application.

sipa commented at 3:25 pm on July 20, 2015:

Fair enough.

laanwj commented at 3:42 pm on July 20, 2015:

Right - 32 bit seems to be enough for this application. Trying to somehow enumerate them by probing for false positives would require a ton of probing, and be a DoS in the first place, which should be handled by other means.

sipa commented at 6:23 pm on July 24, 2015:

I’m not saying this is a problem, only that calling a random 32-bit number cryptographic is a bit grey area. I would just call it secure, because something of cryptographic strength isn’t necessary here.

in src/bloom.cpp: in 767e5366a1 outdated

276+}
277+
278+void CRollingBloomFilter::reset(unsigned int nNewTweak)
279+{
280+    if (!nNewTweak)
281+        nNewTweak = GetRand(std::numeric_limits<unsigned int>::max());

sipa commented at 3:15 pm on July 20, 2015:

If a global CRollingBloomFilter object is constructed, this GetRand() call will still happen before the OpenSSL PRNG is initialized.

petertodd commented at 3:31 pm on July 20, 2015:

Perhaps, but that sounds like a fundemental API flaw in GetRand() - it should fail hard under that circumstance.

According to https://www.openssl.org/docs/crypto/RAND_bytes.html “An error occurs if the PRNG has not been seeded with enough randomness to ensure an unpredictable byte sequence.”, and we do check that the underlying RAND_bytes() returns success. If we trust OpenSSL, then the fact that Bitcoin Core isn’t failing at startup with this code implies everything is working and the filter is getting initialized with genuine randomness.

Of course, that may be all a pile of bullshit… but lets see if we can fix the underlying issue first.

sipa commented at 3:37 pm on July 20, 2015:

I’d say it’s a fundamental flaw in C++ wrt initialization of globals.

sipa commented at 3:39 pm on July 20, 2015:

Oh, I’m not talking about OpenSSL giving out bad randomness. I’m more talking about having the proper thread locking in place for OpenSSL to not cause crashes, or other startup things we do there.

petertodd commented at 3:42 pm on July 20, 2015:

Notice how rust is designed such that no code is executed prior to main()…

Right, so you’re worried that I may have introduced an occasional crashing bug or something? Maybe we need a GetRandButItsOkIfSometimesItDoesntWork() that doesn’t crash if RAND_bytes() fails :/

petertodd commented at 4:19 pm on July 20, 2015:

Equally, would it be fair to say that by the time recentRejects actually gets used after startup, we can safely assume that OpenSSL has been initialized?

sipa commented at 4:25 pm on July 20, 2015:

Yes.

You could just fail at insert() when no tweak was passed at creation, and no reset was called yet.

Or we could not bother, because it won’t hurt in practice with the above code…

petertodd commented at 5:16 pm on July 20, 2015:

By “not bother”, you mean leave the code exactly as it is and wait to see if there’s a platform where OpenSSL crashes on us? It’ll at least be a pretty clear failure…

sipa commented at 6:01 pm on July 24, 2015:

By not bother, I mean that I am reasonably confident that the current code will not cause any problems, as the global initialization is done single-threaded.

Despite that, I think it’s cleaner to not consume randomness in the constructor.

petertodd commented at 6:18 pm on July 24, 2015:

Randomness isn’t something that is consumed with well-designed PRNGs; it’s not like calling GetRand() makes subsequent calls to GetRand() return secrets that are more knowable to the attacker.

sipa commented at 6:21 pm on July 24, 2015:

I fully agree.

s/consume randomness/call GetRand()/

laanwj commented at 11:35 am on July 27, 2015:

I don’t like using 0 as a special marker value here - wouldn’t 0 be a perfectly good tweak value? Maybe add an explicit method resetWithRandomTweak() (or even move the use of randomness to the caller site)?

petertodd commented at 12:10 pm on July 27, 2015:

On Mon, Jul 27, 2015 at 04:35:45AM -0700, Wladimir J. van der Laan wrote:

{
b1.clear();

b2.clear();

if (nInsertions < nBloomSize / 2) {
   return b2.contains(hash);
}

return b1.contains(hash); +}
+void CRollingBloomFilter::reset(unsigned int nNewTweak) +{
if (!nNewTweak)
   nNewTweak = GetRand(std::numeric_limits<unsigned int>::max());
I don’t like using 0 as a special marker value here - wouldn’t 0 be a perfectly good tweak value? Maybe add an explicit method resetWithRandomTweak()?

Well, I’m expecting people to always be using the random tweak provided except in testing.

Why would you need a specific tweak given the internal use-case?

laanwj commented at 3:07 pm on July 27, 2015:

I’ve been bitten in the past by these kind of ‘special values’ unexpectedly turning up, so I’m just cautious and trying to avoid technical debt. If it’s really only for testing, maybe the method that takes an explicit tweak should be the explicitly named one. Eg.

0void CRollingBloomFilter::reset()
1{
2    resetWithTweak(GetRand(std::numeric_limits<unsigned int>::max()));
3}
4void CRollingBloomFilter::resetWithTweak(unsigned int nNewTweak)
5{
6    ...
7}

petertodd force-pushed on Jul 20, 2015

sipa commented at 6:33 pm on July 24, 2015: member

ACK

morcos commented at 3:46 pm on July 27, 2015: member

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

Add uint256 support to CRollingBloomFilter bbe41088c6

Reuse vector hashing code for uint256 a3d65fedaa

Make CRollingBloomFilter set nTweak for you

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.

d2d7ee0e86

Only use randomly created nonces in CRollingBloomFilter. d741371d7d

sipa commented at 5:26 pm on July 27, 2015: member

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

laanwj commented at 9:03 am on July 28, 2015: member

Code review ACK on sipa’s changes

Keep track of recently rejected transactions

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.

0847d9cb5f

petertodd force-pushed on Jul 28, 2015

petertodd commented at 7:53 pm on July 28, 2015: contributor

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

I’ll note there is a chance that https://github.com/petertodd/bitcoin/commit/d741371d7d27e228aa64c618c50b23fb5449c3e1 could lead to intermittent unit test failures.

jtimon commented at 11:21 am on July 29, 2015: contributor

I still don’t understand why can’t we reuse the same cache for rejections and #6077 (what I wanted to do in https://github.com/jtimon/bitcoin/commit/935ee1ec875308f27339418363c787ec061d335f to make 0-size mempools safe). Does anybody have any answer (I failed to get it on IRC)?

laanwj commented at 10:08 am on July 31, 2015: member

Error in Travis during the Python unit tests:

0bitcoind: /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.
1Unexpected exception caught during testing: ''

I’ll note there is a chance that petertodd@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:

0bitcoind: 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 commented at 12:29 pm on July 31, 2015: member

This can be solved by moving

0    // Initialize global variables that cannot be constructed at startup.
1    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 commented at 4:32 pm on July 31, 2015: member

Continued in #6498

laanwj closed this on Jul 31, 2015

dcousens commented at 11:28 pm on October 4, 2015: contributor

edit: moved comments to #6498

MarcoFalke locked this on Sep 8, 2021

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