Use rolling bloom filter of recent block txs for AlreadyHave() check #17951

sdaftuar commented at 5:22 PM on January 17, 2020: member

In order to determine whether to download or process a relayed transaction, we first try to check whether we already have the transaction -- either in the mempool, in our filter of recently rejected transactions, in our orphan pool, or already confirmed in a block.

Prior to this commit, the heuristic for checking whether a transaction was confirmed in a block is based on whether there's a coin cache entry corresponding to the 0- or 1-index vout of the tx. While that is a quick check, it is very imprecise (eg if those outputs were already spent in another block, we wouldn't detect that the transaction has already been confirmed) -- we can do better by just keeping a rolling bloom filter of the transactions in recent blocks, which will better capture the case of a transaction which has been confirmed and then fully spent.

This should reduce the bandwidth that we waste by requesting transactions which will not be accepted to the mempool.

To avoid relay problems for transactions which have been included in a recent block but then reorged out of the chain, we clear the bloom filter whenever a block is disconnected.

sdaftuar requested review from TheBlueMatt on Jan 17, 2020

DrahtBot commented at 5:28 PM on January 17, 2020: member

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#17477 (Remove the mempool's NotifyEntryAdded and NotifyEntryRemoved signals by jnewbery)
#15606 ([experimental] UTXO snapshots by jamesob)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

DrahtBot added the label P2P on Jan 17, 2020

in src/net_processing.cpp:155 in 1e9697bed8 outdated

 147 | @@ -148,6 +148,14 @@ namespace {
 148 |      std::unique_ptr<CRollingBloomFilter> recentRejects GUARDED_BY(cs_main);
 149 |      uint256 hashRecentRejectsChainTip GUARDED_BY(cs_main);
 150 |  
 151 | +    /**
 152 | +     * Filter for transactions that have been recently confirmed.
 153 | +     * We use this to avoid requesting transactions that have already been
 154 | +     * confirnmed.
 155 | +     */

TheBlueMatt commented at 6:36 PM on January 17, 2020:

nit: I presume this makes some kind of doc tools unhappy cause they will add docs to the cs and not the var.

sipa commented at 8:21 PM on January 26, 2020:

Yeah, if you want to make a non-doxygen generic comment, use "/*" rather than "/**".

sdaftuar commented at 6:49 PM on January 27, 2020:

Done.

TheBlueMatt approved

TheBlueMatt commented at 6:59 PM on January 17, 2020: member

utACK 1e9697bed83332f6aa1d2579dc7638fdb4785477 with or without a nit fix.

Binh0103 approved

in src/net_processing.cpp:1126 in 1e9697bed8 outdated

1122 | @@ -1115,6 +1123,7 @@ PeerLogicValidation::PeerLogicValidation(CConnman* connmanIn, BanMan* banman, CS
1123 |  {
1124 |      // Initialize global variables that cannot be constructed at startup.
1125 |      recentRejects.reset(new CRollingBloomFilter(120000, 0.000001));
1126 | +    recent_confirmed_transactions.reset(new CRollingBloomFilter(24000, 0.000001));

paymog commented at 8:30 PM on January 18, 2020:

should the parameters to the bloom filter be tunnable with commandline args?

sdaftuar commented at 12:01 AM on January 19, 2020:

I can't imagine why anyone would need to customize this parameter (it's not like we offered the ability to customize how many outputs we'd check in the cache, or the ability to customize the recentRejects filter).

sipa commented at 8:27 PM on January 26, 2020:

Add some comments to explain the parameter selection?

sdaftuar commented at 6:48 PM on January 27, 2020:

Done.

in src/net_processing.cpp:157 in 1e9697bed8 outdated

 152 | +     * Filter for transactions that have been recently confirmed.
 153 | +     * We use this to avoid requesting transactions that have already been
 154 | +     * confirnmed.
 155 | +     */
 156 | +    RecursiveMutex cs_recent_confirmed_transactions;
 157 | +    std::unique_ptr<CRollingBloomFilter> recent_confirmed_transactions GUARDED_BY(cs_recent_confirmed_transactions);

MarcoFalke commented at 2:10 AM on January 19, 2020:

nit: Globals should start with g_ otherwise it might incorrectly look like they live on the stack (as opposed to the heap)

MarcoFalke approved

MarcoFalke commented at 2:11 AM on January 19, 2020: member

ACK 1e9697bed83332f6aa1d2579dc7638fdb4785477 💮

<details><summary>Show signature and timestamp</summary>

Signature:

Timestamp of file with hash b397d76b2d70800a76d30579868ff63848d4b1c37cd53dced87c6ab01cd89fd7 -

</details>

sdaftuar requested review from sipa on Jan 19, 2020

sipa commented at 3:52 PM on January 19, 2020: member

Is clearing when disconnecting necessary? The disconnected transactions are at least considered for re-inclusing into the mempool, so even if they don't make it in, wouldn't it make sense to keep considering them "known"?

I agree that clearing when disconnecting is the safe bet if we're not entirely sure about this.

MarcoFalke commented at 4:37 PM on January 19, 2020: member

A reorg might change MTP and some mempool checks might depend on that time. So if the reorg changes MTP and "forgets" to include a tx that was previously included in a block, it is now neither in the chain, nor in the mempool, nor can it be relayed.

sdaftuar commented at 5:08 PM on January 19, 2020: member

@sipa Yes I think something like @MarcoFalke's example is right, or even for a simple example of something that is added back to the mempool as part of the reorg but then evicted when the mempool is trimmed (due to feerate). Unlike the recentRejects filter which is cleared every block, the recent_confirmed_transactions is (otherwise) never cleared, so something that gets inadvertently stuck in it will interfere with relay for an extended period of time, depending on the size of the filter.

It's worth noting that if there is a false positive, it may persist for many blocks (unlike in the recentRejects filter). My thought was that because this would not be a synchronized event over the network that this is ok... But perhaps the choice of false positive rate is worth further thought?

in src/net_processing.cpp:1193 in 1e9697bed8 outdated

1209 | +    // then another block reconnected), our filter will drop to having only one
1210 | +    // block's worth of transactions in it, but that should be fine, since
1211 | +    // presumably the most common case of relaying a confirmed transaction
1212 | +    // should be just after a new block containing it is found.
1213 | +    LOCK(cs_recent_confirmed_transactions);
1214 | +    recent_confirmed_transactions->reset();

ariard commented at 10:53 PM on January 21, 2020:

To avoid the same false positive hitting most of the network at once, why not randomly clear recent_confirmed_transactions ? Or this should happen more or less with current rate of 1-block reorgs?

sdaftuar commented at 1:55 PM on January 22, 2020:

The goal is to not clear this filter, so that we have the last N (6-12?) blocks' worth of transactions in the filter, to avoid wasting bandwidth.

False positives should already not be synchronized across the network because every filter is seeded with randomness, so no two nodes have the same filter calculations.

ariard approved

ariard commented at 10:55 PM on January 21, 2020: member

Code review ACK 1e9697b

Is AlreadyHave currently covered by the test framework ?

sdaftuar commented at 1:51 PM on January 22, 2020: member

Discussed this a bit with @marcofalke yesterday, and after further thought, I think the false positive rate for this filter should be fine. The only use case that I think could be somewhat materially impacted would be if you have a bitcoind node acting as a gateway to the network, and a wallet behind it that is broadcasting transactions through it, then it's possible that a false positive in this filter would prevent transaction relay for several blocks, which seems unfortunate.

However, in thinking about this, transaction relay in this situation appears to already be broken in the case of a false positive in the recentRejects filter, because ever since #8082 I believe we never actually relay anything not in our mempool, breaking relay of transactions from whitelisted peers that are supposed to go out even if not accepted to our mempool. So if we want this behavior, we should separately fix it for both the reject filter and this new filter. (Note: I haven't actually tested to verify that claim, but just from looking at the code, I can't see how it could possibly work. Maybe someone else can corroborate this view?)

in src/net_processing.cpp:1196 in 1e9697bed8 outdated

1203 | +void PeerLogicValidation::BlockDisconnected(const std::shared_ptr<const CBlock> &block, const CBlockIndex* pindex)
1204 | +{
1205 | +    // To avoid relay problems with transactions that were previously
1206 | +    // confirmed, clear our filter of recently confirmed transactions whenever
1207 | +    // there's a reorg.
1208 | +    // This means that in a 1-block reorg (where 1 block is disconnected and

sipa commented at 8:25 PM on January 26, 2020:

It seems possible to instead of wiping the filter entirely, there could be a way to "eagerly" delete the disconnected block's transactions from the filter (where eagerly implies that it will randomly delete too much - but that's still better than wiping entirely).

I'm slightly uncomfortable still with reorgs having the ability to blow this cache away entirely, but don't see a way to use it in an attack, so not a blocker.

sdaftuar commented at 3:07 PM on January 27, 2020:

Hm, I was trying to think what this might mean -- for a filter with N elements, I suppose one approach would be to just re-add the last (say) 1.5N transactions that appear in the most recent blocks leading to the tip back to the filter, in order to wipe the reorged block(s) out of the filter, without making the filter useless?

It'd be a bit annoying to do that, since only the last block is in memory; but I guess we could do this in the future if we felt like this was a problem. Is there a smarter way to achieve this effect that I'm overlooking?

sipa commented at 5:08 PM on January 27, 2020:

I mean going through the disconnected block's transaction, and setting all their bits to 0 in the filter.

gmaxwell commented at 12:23 AM on January 28, 2020:

You can do the thing where you store rank.s When you insert you increase the rank of each bit to the current. When you query you ignore bits whos rank is too low. When the rank counter wraps, you make a pass over to adjust the ranks. E.g. say your counter is 8 bits and you want to remember the last 10 blocks. You start with all the data zeros. You start on rank 11, so every value has too low a rank to be considered set. Every block you increase your rank and only consider the last 10 to be set. When you overflow you map the last 10 ranks to 0-10 and you start again at 11. There are a bunch of variations on this that amortize the erasure.

gmaxwell commented at 8:44 PM on January 26, 2020: contributor

These low FP rate bloom filters are pretty slow, how much does this slow down block acceptance?

Might it just be better to keep a limited map of txids recently removed entirely from the txout set?

jamesob commented at 3:15 PM on January 27, 2020: member

how much does this slow down block acceptance?

Shouldn't slow down block acceptance at all since this is being run on the validation interface thread.

sdaftuar commented at 3:48 PM on January 27, 2020: member

These low FP rate bloom filters are pretty slow, how much does this slow down block acceptance? @gmaxwell My thought was that the speed shouldn't be a big deal because the BlockConnected callback happens in a background thread, out of the critical path of block acceptance.

Might it just be better to keep a limited map of txids recently removed entirely from the txout set?

Possibly, though I just want to clarify your suggestion -- this seems like an idea for a data structure that would be used in conjunction with the utxo cache for determining whether we've seen a transaction?

I'd like to remove querying the utxo set altogether from this logic, in preparation for proposing that we switch to wtxid-based INV messages (to solve the long-running problem we have that segwit transactions don't get added to our reject filter, due to possible malleability, see #8279 for background). Using a data structure that completely captures the idea of "is this transaction already confirmed" seems preferable for moving in this direction, as my next proposal would be to expand the txid-based lookup in such data structure to have a wtxid-based lookup as well. (However, I would not propose adding a wtxid-based lookup to the utxo cache itself, as that seems absurd to me.)

So rather than propose a limited map of recently fully spent transactions as an alternative here, I think I would say we could consider instead just using a limited map for all recently confirmed transactions (to which we could add a wtxid-based key as well in the future).

I think that could be fine, and it seems to me the choice would be a memory tradeoff between a bloom filter and limited map. I don't feel strongly what direction we go; I think the limited map approach is easier to reason about correctness of, because it's nice to eliminate any concerns about false positives interfering with relay, but I don't think this approach should be too bad either after giving it some thought.

But I'd be happy to switch directions and use a limited map of all recently confirmed transactions instead if people think that makes more sense...

sdaftuar commented at 6:48 PM on January 27, 2020: member

Pushed a fixup commit to address the comment nits (and a second commit to fix the naming nit, which I missed the first time).

Use rolling bloom filter of recent block tx's for AlreadyHave() check

In order to determine whether to download or process a relayed transaction, we
try to determine if we already have the transaction, either in the mempool, in
our recently rejected filter, in our orphan pool, or already confirmed in the
chain itself.

Prior to this commit, the heuristic for checking the chain is based on whether
there's an output corresponding to the 0- or 1-index vout in our coin cache.
While that is a quick check, it is very imprecise (say if those outputs were
already spent in a block) -- we can do better by just keeping a rolling bloom
filter of the transactions in recent blocks, which will capture the case of a
transaction which has been confirmed and then fully spent already.

To avoid relay problems for transactions which have been included in a recent
block but then reorged out of the chain, we clear the bloom filter whenever a
block is disconnected.

a029e18c2b

sdaftuar force-pushed on Jan 29, 2020

sdaftuar commented at 2:40 PM on January 29, 2020: member

Squashed the nit commits. I'm inclined to leave the resetting of the filter on a reorg alone, as I think what is proposed here should be fine; please let me know if there's anything else I should address (particularly if the bloom filter approach seems problematic overall for some reason?).

MarcoFalke commented at 7:13 PM on January 29, 2020: member

Will try to test this a bit in the next week or so.

re-ACK a029e18c2b only stylistic and comment fixups 🍴

<details><summary>Show signature and timestamp</summary>

Signature:

Timestamp of file with hash 5c3cef17120e5f7c54fb4bc112dfe230bdc9da289456a63dcc006e7b806e1f36 -

</details>

in src/net_processing.cpp:1135 in a029e18c2b

1130 | +    // seeing getdata requests more than an hour after initial announcement, we
1131 | +    // can increase this number.
1132 | +    // The false positive rate of 1/1M should come out to less than 1
1133 | +    // transaction per day that would be inadvertently ignored (which is the
1134 | +    // same probability that we have in the reject filter).
1135 | +    g_recent_confirmed_transactions.reset(new CRollingBloomFilter(24000, 0.000001));

JeremyRubin commented at 9:35 PM on January 30, 2020:

This computes to a size that is above the max filter size FYI (maybe we should have a typesafe CRollingBloomFilter that compile time checks this, or allow passing in a custom max).

sipa commented at 9:43 PM on January 30, 2020:

What max filter size are you talking about?

JeremyRubin commented at 10:17 PM on January 30, 2020:

static const unsigned int MAX_BLOOM_FILTER_SIZE = 36000; // bytes

JeremyRubin commented at 10:20 PM on January 30, 2020:

ooops, I based my review on CBloomFilter... need to go back and re-check the right class

JeremyRubin commented at 9:46 PM on January 30, 2020: contributor

General concept ACK.

To address concerns with the RollingBloomFilter:

It would take up a bit more space, but this can also be a good place to reuse the cuckoocache.

The original uses ((ceil(-1.0 * 20 * (24000/2*3) / log(1.0 - exp(log(0.000001) / 20))) +63)>>6)<<1 = 32350 bytes

Cuckoocache would need: 6400032.25/(32350) = 24x more space, but still under a megabyte.

Using the cuckoocache would have a more graceful delete functionality and can also "age" things more gracefully if the filter looks full. We can then also use a read/write lock and:

write when inserting read when reading read when erasing

This enables more concurrency down the line if we erase everything in parallel.

It should also be a fair bit faster because CuckooCache only needs to hash a single sha256 rather than a bunch of murmurs (if I calculated right, we're doing 20 hashes?).

jonatack commented at 10:40 PM on January 30, 2020: member

Code review ACK a029e18c2bf67dd00552b0f4bbc85fa2fa5b973b also built/ran tests and am running bitcoind with mempool debug logging and custom logging. Looked a bit into CRollingBloomFilter and also the mempool median time past checks mentioned above; I don't have a deep understanding of those areas yet but the concept here and changes LGTM. Tests and other optimisations could be added as a follow-up. In favor of seeing this move forward if no major immediate concerns.

gmaxwell commented at 12:27 AM on January 31, 2020: contributor

@sdaftuar okay, if its not on a critical path for mining a subsequent block my concern is withdrawn. I spent a half hour trying to figure out if it was but wasn't able to trace all the indirect control flow well enough to be confident. @JeremyRubin why not instantiate the the cuckoo filter with a more similar FP rate? then the memory overhead would be less and the other advantages would remain. I expect that in the long run the low FP rate bloom filters would all eventually get replaced with cuckoo filters because memory speeds increase slowly compared to cpu speed and memory capacity... and those low FP rate bloom filters make a lot of random memory accesses.

sipa commented at 12:29 AM on January 31, 2020: member

utACK a029e18c2bf67dd00552b0f4bbc85fa2fa5b973b

JeremyRubin commented at 12:57 AM on January 31, 2020: contributor

@gmaxwell

Good point. The cuckoo cache only does at most 8 memory accesses to read (and it's biased a bit towards it being less -- let's say EV is 2 or 3 rather than 4, v.s. 20 for the bloom. That seems like a win.

Turning up the False Positive is not possible for the cuckoocache as a true response is always true. There isn't an obvious way to add false positives to the current design (we'd never want them for the signature cache).

What you can tune up is the false negative rate, by just allocating a smaller table. But given your point, we may want to allocate a bigger table (say 1MB - 1.5MB) because the 3 Random Accesses are pretty cheap independent of size.

Someone could also implement an actual false-positive cuckoo filter, but I'm not as familiar with that data structure/it doesn't exist in core already.

gmaxwell commented at 1:49 AM on January 31, 2020: contributor

@JeremyRubin use a shorter hash, if it collides you have a FP. You can also turn down the number of parallel memory access for this case, as there isn't so much need to run the table at 90% full esp if the entries are short. 32 bit cells should still give a massifly lower FP rate...

JeremyRubin commented at 4:07 AM on January 31, 2020: contributor

Good point, didn't occur to me to use collisions in the input hash.

In this case I would recommend taking 4 chunks of 16 bits (from siphash or from truncated sha256) and storing that per element.

16 bits is sufficient for 6 blocks worth of 4000 transactions (by sufficient I mean it can address a table of up to 65536 elements)

You then have 4 hash locations any element can be at, and given early location biasing (which improves the more oversized the table is) I think the EV of memory access would be something like 2 random accesses (e.g., (1+2+3+4)/4 < 2.5).

6*4000*8.25/(32350) = 6.12 times bigger than the equivalent bloom filter, but with 10x fewer expected random memory accesses and (using salted siphash) 20x less hashing.

Seems like a reasonable tradeoff; when I have time I'm happy to prepare a filter based on this. I think it'd be OK to be a follow up to this as it seems the base PR is OK as is.

jonasschnelli referenced this in commit d104aa0ace on Jan 31, 2020

jonasschnelli merged this on Jan 31, 2020

jonasschnelli closed this on Jan 31, 2020

Fabcien referenced this in commit 1d95857cbc on Dec 23, 2020

DrahtBot locked this on Feb 15, 2022