Replace setInventoryKnown with a rolling bloom filter (rebase of #7100) #7133

pull sipa wants to merge 6 commits into bitcoin:master from sipa:known_bloom changing 8 files +16 −166

sipa commented at 12:31 PM on November 30, 2015: member

No description provided.

Replace setInventoryKnown with a rolling bloom filter.

Mruset setInventoryKnown was reduced to a remarkably small 1000
 entries as a side effect of sendbuffer size reductions in 2012.

This removes setInventoryKnown filtering from merkleBlock responses
 because false positives there are especially unattractive and
 also because I'm not sure if there aren't race conditions around
 the relay pool that would cause some transactions there to
 be suppressed. (Also, ProcessGetData was accessing
 setInventoryKnown without taking the required lock.)

ec73ef37ec

Remove mruset as it is no longer used. e20672479e
Rename setInventoryKnown filterInventoryKnown 6b849350ab

Only use filterInventoryKnown with MSG_TX inventory messages.

Previously this logic could erroneously filter a MSG_BLOCK inventory message.

b6a0da45db

Actually only use filterInventoryKnown with MSG_TX inventory messages.
Previously this logic could erroneously filter a MSG_BLOCK inventory message.
d41e44c9ac
When not filtering blocks, getdata sends more in one test aa4b0c26b0
sipa cross-referenced this on Nov 30, 2015 from issue Replace global trickle node with random delays by sipa
sipa cross-referenced this on Nov 30, 2015 from issue Replace setInventoryKnown with a rolling bloom filter. by gmaxwell
jtimon commented at 3:30 PM on November 30, 2015: contributor

utACK
gmaxwell commented at 12:05 AM on December 2, 2015: contributor

ACK

in src/net.cpp:None in aa4b0c26b0

2341 | @@ -2342,7 +2342,7 @@ unsigned int SendBufferSize() { return 1000*GetArg("-maxsendbuffer", DEFAULT_MAX
2342 |  CNode::CNode(SOCKET hSocketIn, const CAddress& addrIn, const std::string& addrNameIn, bool fInboundIn) :
2343 |      ssSend(SER_NETWORK, INIT_PROTO_VERSION),
2344 |      addrKnown(5000, 0.001),
2345 | -    setInventoryKnown(SendBufferSize() / 1000)
2346 | +    filterInventoryKnown(50000, 0.000001)

dcousens commented at 2:37 AM on December 2, 2015:

Why 50000 OOI? Should this be a named constant?

dcousens commented at 2:38 AM on December 2, 2015: contributor

utACK
dcousens commented at 2:41 AM on December 2, 2015: contributor

Also ACK on FP ratio of 0.000001:1
petertodd commented at 10:43 AM on December 3, 2015: contributor

utACK
laanwj merged this on Dec 3, 2015
laanwj closed this on Dec 3, 2015
laanwj referenced this in commit 8843676621 on Dec 3, 2015
laanwj commented at 12:17 PM on December 3, 2015: member

utACK
gmaxwell referenced this in commit f31955d9da on Dec 4, 2015
morcos commented at 3:42 PM on December 11, 2015: member

posthumous utACK. nice.
dgenr8 cross-referenced this on Dec 29, 2015 from issue Further work on thin blocks by dagurval
dgenr8 cross-referenced this on Mar 2, 2016 from issue Don't send full transactions with a merkleblock if already known by dgenr8
laanwj added the label P2P on Jul 18, 2016
str4d cross-referenced this on Jul 14, 2017 from issue Bitcoin 0.12 P2P/Net PRs 1 by str4d
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
str4d cross-referenced this on Feb 19, 2021 from issue Replace setInventoryKnown with a rolling bloom filter by str4d
zkbot referenced this in commit 9dd55615d0 on Feb 22, 2021
zkbot referenced this in commit 2aa9fbbdfe on Mar 5, 2021
zkbot referenced this in commit a7e877a350 on Aug 13, 2021
bitcoin locked this on Sep 8, 2021

Contributors

Labels

Linked (view graph)

#7100 Replace setInventoryKnown with a rolling bloom filter.#7125 Replace global trickle node with random delays