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

pull laanwj wants to merge 6 commits into bitcoin:master from laanwj:2015_07_recent-rejects-rolling-bloom changing 5 files +109 −23

laanwj commented at 4:30 PM on July 31, 2015: member

Peter Todd is on holiday, so continued from #6452 Added a commit that moves recentRejects initialization to the top of InitBlockIndex to avoid not initializing it under some conditions.
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

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

Move recentRejects initialization to top of InitBlockIndex

This avoids that premature return in the condition that a new chain is initialized
results in NULL pointer errors due to recentReject not being constructed.

Also add assertions where it is used.

a8d0407c4f

laanwj added the label P2P on Jul 31, 2015
laanwj cross-referenced this on Jul 31, 2015 from issue Keep track of recently rejected transactions with a rolling bloom filter by petertodd
sipa commented at 5:44 PM on August 3, 2015: member

ACK (tested as part of #6470).
laanwj merged this on Aug 3, 2015
laanwj closed this on Aug 3, 2015
laanwj referenced this in commit 219b916545 on Aug 3, 2015
morcos cross-referenced this on Aug 5, 2015 from issue Super Duper MemPool Limiter by morcos
dgenr8 cross-referenced this on Aug 25, 2015 from issue Track recently rejected transactions; don't reprocess by dgenr8
petertodd cross-referenced this on Oct 2, 2015 from issue Recent rejects backport to v0.11 by petertodd

in src/main.cpp:None in a8d0407c4f

 171 | +     * Without this filter we'd be re-requesting txs from each of our peers,
 172 | +     * increasing bandwidth consumption considerably. For instance, with 100
 173 | +     * peers, half of which relay a tx we don't accept, that might be a 50x
 174 | +     * bandwidth increase. A flooding attacker attempting to roll-over the
 175 | +     * filter using minimum-sized, 60byte, transactions might manage to send
 176 | +     * 1000/sec if we have fast peers, so we pick 120,000 to give our peers a

dcousens commented at 11:28 PM on October 4, 2015:

Pick 120,000 what?

in src/main.cpp:None in a8d0407c4f
```
 176 | +     * 1000/sec if we have fast peers, so we pick 120,000 to give our peers a
 177 | +     * two minute window to send invs to us.
 178 | +     *
 179 | +     * Decreasing the false positive rate is fairly cheap, so we pick one in a
 180 | +     * million to make it highly unlikely for users to have issues with this
 181 | +     * filter.
```
dcousens commented at 11:28 PM on October 4, 2015:

Decreasing the false positive rate [for a valid transaction?] is fairly cheap, so we pick one in [a] million [1/1e6, what is this unit?] to make it highly unlikely for users [legitimate transactions?] to have issues with this [passing this?] filter.

Could this be clarified a little? I marked my assumptions/questions in [ ].

edit: if I can get clarifications to the above to cement my own understanding, I'll happily make the change/PR
dcousens commented at 11:29 PM on October 4, 2015: contributor

concept ACK
Fuzzbawls cross-referenced this on Jun 23, 2020 from issue [Net] Pre-requirements for network encapsulation by Fuzzbawls
random-zebra referenced this in commit 8bbc0650e6 on Jul 1, 2020
bitcoin locked this on Sep 8, 2021

Contributors

Labels

Linked (view graph)

#6452 Keep track of recently rejected transactions with a rolling bloom filter #6470 Super Duper MemPool Limiter #6750 Recent rejects backport to v0.11