Several performance and privacy improvements to inv/mempool handling #7840

sipa · 2016-04-08T13:39:12Z

As we're increasingly changing how block invs and tx invs are treated, bite the bullet and separate them into two separate queues. This makes sense, as they are subject to very different behaviour: we want blocks to relay as fast as possible, while transactions are subject to rate limiting, deduplication, and source obscurity.

Once this is done, we can turn the tx queue into a set, and use it to prevent the mempool command from leaking unannounced transactions. The handling of such commands is also moved to the send loop, sorted by dependency order, and made subject to trickling.

Based on top of #7805.

gmaxwell · 2016-04-08T18:01:59Z

src/main.cpp

+                    if (pto->minFeeFilter) {
+                        CFeeRate feeRate;
+                        mempool.lookupFeeRate(hash, feeRate);
+                        LOCK(pto->cs_feeFilter);


Perhaps the fee filter access should be hoisted out of this inner loop on transactions, and a local copy of the filter-limit made.

gmaxwell · 2016-04-08T18:06:38Z

This is a very good idea-- much better than my earlier ones around avoiding mempool requests breaking privacy.

Your commit message should explain that by eliminating queued entries from the mempool response and responding only at trickle time, this makes the mempool no longer leak transaction arrival order information (as the mempool itself is also sorted)-- at least no more than relay itself leaks it.

gmaxwell · 2016-04-08T19:06:55Z

src/main.cpp

            }
+
+            // Determine transactions to relay
            if (fSendTrickle) {


"&& vInv.size() < INVENTORY_BROADCAST_MAX" perhaps? otherwise when a mempool request has prefilled the INV it will waste time heapifying for no reason.

gmaxwell · 2016-04-09T00:32:30Z

I have a test-harness now thats sutiable for testing this, a little 13 node network. Seems to work, it caught that the conversion to use the STL heap broke the behavior: the stl heap is a max heap.

gmaxwell · 2016-04-09T03:15:34Z

@thanks for fixing, looking good so far.

We still get a tiny number of orphans in a network the consists of nothing but this code. Here is one reason why node A sends you Tx1. You getdata Tx1 Node B sends you Tx1 and Tx2 and Tx1 is a child of Tx1. You getdata Tx2 from node2. Node2 responds faster. Tx2 is now an orphan.

sipa · 2016-04-10T13:41:07Z

I added a commit to sort the response of mempool requests in dependency order, and renamed the PR to something more general.

dcousens · 2016-04-11T06:48:55Z

concept ACK

sdaftuar · 2016-04-11T19:07:12Z

src/main.cpp

-                    pto->PushMessage(NetMsgType::INV, vInv);
-                    vInv.clear();
+            // Determine transactions to relay
+            if (fSendTrickle && vInv.size() < INVENTORY_BROADCAST_MAX) {


INVENTORY_BROADCAST_MAX is supposed to apply to rate-limited transaction relay, while vInv at this point can be holding blocks, and/or any leftovers from the mempool command. This seems like it's not the right comparison.

sdaftuar · 2016-04-11T19:34:24Z

Concept ACK, will test.

sdaftuar · 2016-04-11T19:36:26Z

src/main.h

+/** Average delay between trickled inventory transmissions in seconds.
+ *  Blocks and whitelisted receivers bypass this, outbound peers get half this delay. */
+static const unsigned int INVENTORY_BROADCAST_INTERVAL = 5;
+/** Maximum number of inventor items to send per transmission.


"inventor" -> "inventory"

sipa · 2016-04-12T14:40:26Z

Added two commits to address the comments.

Mempool requests are now not filtered by vInventoryTxToSend, but instead every mempool inv sent as a response is removed from vInventoryTxToSend.

gmaxwell · 2016-04-12T21:30:24Z

In a test topology over 48 hours this reduced the addition of orphan transactions from 436/hr to 2.3/hr.

gmaxwell · 2016-04-12T21:40:32Z

Also, utack latest improvements.

dcousens · 2016-04-13T02:32:31Z

concept ACK, utACK 98305df

gmaxwell · 2016-04-19T07:05:33Z

@sipa: any squashing interest?

sipa · 2016-04-19T17:54:11Z

Rebased and squashed.

sipa · 2016-04-19T18:07:55Z

Also renamed the vInventoryTxToSend to setInventoryTxToSend, and restructured the tx send loop a bit to be less deeply nested.

This will avoid sending more pointless INVs around updates, and prevents using filter updates to timetag transactions. Also adds locking for fRelayTxes.

dcousens · 2016-04-21T04:08:42Z

@sipa could you update your original PR description with the full scope of this PR now? (for others)

gmaxwell · 2016-04-21T19:04:59Z

ACK.

jonasnick · 2016-04-22T08:08:58Z

Ack

sdaftuar · 2016-04-22T20:18:27Z

src/txmempool.cpp

+    DepthAndScoreComparator(CTxMemPool *mempool) : mp(mempool) {}
+    bool operator()(const uint256& a, const uint256& b) { return mp->CompareDepthAndScore(a, b); }
+};
+}


nit: What do you think of exposing the DepthAndScoreComparator defined here, and eliminating the CompareInvMempoolOrder object declared in main.cpp by moving the comparator it defines (which reverses the comparison) into this class?

The comparator over there sorts iterators to set items, so there is more difference.

I do think the comparator (or at least a base comparator) should be exposed here, which grabs the mempool lock etc. Perhaps the other comparator can then take a ref to the first one as an argument to add the reversing and set iterator dereferencing.

I was thinking that because the main.cpp comparator acts on different objects, it'd be easy to just move that function into this class (and explain in comments what the two comparators were for and why they are subtly different!), but your suggestion seems reasonable to me as well. I suppose its not awesome for the implementation details in main.cpp to leak into txmempool...

Even better would be for txmempool.h to expose an opaque SortedMempoolSet object, which takes a list of hashes as inputs, and maintains a sorted heap of iterators to the mempool entries themselves, in addition to the cs lock.

sdaftuar · 2016-04-22T20:24:49Z

ACK, apart from my question about whether we should combine the two comparators that are being introduced.

Couple notes:

RelayTransaction no longer requires a feerate, and AcceptToMemoryPool no longer needs to fill a feerate in. We can clean this up in a future PR.
I noticed while testing that CTxMemPool::queryHashes is what we use in the RPC call getrawmempool. It's hard for me to imagine anyone would care (and in fact the new sort order on the results seems handy!), but perhaps we should flag the change in the release notes?

gmaxwell · 2016-04-26T06:00:09Z

I've had this running in its various forms for two weeks on a couple of public nodes, as well as a seperate test topology that consisted of nothing but nodes running this code. What do we need to move this forward? I'm concerned that if I move to testing other PRs this will be forgotten.

…ool handling b559914 Move bloom and feerate filtering to just prior to tx sending. (Gregory Maxwell) 4578215 Return mempool queries in dependency order (Pieter Wuille) ed70683 Handle mempool requests in send loop, subject to trickle (Pieter Wuille) dc13dcd Split up and optimize transaction and block inv queues (Pieter Wuille) f2d3ba7 Eliminate TX trickle bypass, sort TX invs for privacy and priority. (Gregory Maxwell)

…nv/mempool handling b559914 Move bloom and feerate filtering to just prior to tx sending. (Gregory Maxwell) 4578215 Return mempool queries in dependency order (Pieter Wuille) ed70683 Handle mempool requests in send loop, subject to trickle (Pieter Wuille) dc13dcd Split up and optimize transaction and block inv queues (Pieter Wuille) f2d3ba7 Eliminate TX trickle bypass, sort TX invs for privacy and priority. (Gregory Maxwell)

Bitcoin bitcoin#7840 has split the INVs to send into block and TX and completely ignores non-tx/non-block items in PushInventory. This is fine for Bitcoin, as they only use it for blocks and TXs, but we also have a lot of MN related messages which also need to be relayed.

9b9c616 Fix missing zapwallettxes mode in wallet_hd.py functional test (furszy) d6d0ad9 [logs] fix zapwallettxes startup logs (John Newbery) 006c503 [wallet] fix zapwallettxes interaction with persistent mempool (John Newbery) c6d45c6 Adapting and connecting mempool_persist.py functional test to the test runner. (furszy) 4f26a4e Control mempool persistence using a command line parameter. (John Newbery) 5d949de [Qt] Do proper shutdown (Jonas Schnelli) e60da98 Allow shutdown during LoadMempool, dump only when necessary (Jonas Schnelli) c0a0e81 Moving TxMempoolInfo tx member to CTransactionRef (furszy) f0c2255 Add mempool.dat to doc/files.md (furszy) 8e52226 Add DumpMempool and LoadMempool (Pieter Wuille) 44c635d Add AcceptToMemoryPoolWithTime function (Pieter Wuille) 6bbc6a9 Add feedelta to TxMempoolInfo (Pieter Wuille) 9979f3d [mempool] move removed and conflicts transaction ref list to vector. (furszy) 4f672c2 Make removed and conflicted arguments optional to remove (Pieter Wuille) e51c4b8 Bypass removeRecursive in removeForReorg (Pieter Wuille) 54cf7c0 Get rid of CTxMempool::lookup() entirely (furszy) 35bc2a9 Finished the switch CTransaction storage in mempool to CTransactionRef and introduced the timeLastMempoolReq coming from btc#8080. (furszy) d10583b An adapted version of btc@b5599147533103efea896a1fc4ff51f2d3ad5808 (furszy) cb4fc6c An adapted version of btc@ed7068302c7490e8061cb3a558a0f83a465beeea (furszy) 9645775 Split up and optimize transaction and block inv queues (furszy) 68bc68f Don't do mempool lookups for "mempool" command without a filter (furszy) 7624823 mapNextTx: use pointer as key, simplify value (furszy) 191c62e Return mempool queries in dependency order (Pieter Wuille) 23c9f3e Eliminate TX trickle bypass, sort TX invs for privacy and priority. (furszy) 6ebfd17 tiny test fix for mempool_tests (Alex Morcos) 8c0016e Check all ancestor state in CTxMemPool::check() (furszy) 91c6096 Add ancestor feerate index to mempool (Suhas Daftuar) 64e84e2 Add ancestor tracking to mempool This implements caching of ancestor state to each mempool entry, similar to descendant tracking, but also including caching sigops-with-ancestors (as that metric will be helpful to future code that implements better transaction selection in CreatenewBlock). (furszy) 8325bb4 Fix mempool limiting for PrioritiseTransaction Redo the feerate index to be based on mining score, rather than fee. (furszy) 1fa40ac Remove work limit in UpdateForDescendants() The work limit served to prevent the descendant walking algorithm from doing too much work by marking the parent transaction as dirty. However to implement ancestor tracking, it's not possible to similarly mark those descendant transactions as dirty without having to calculate them to begin with. This commit removes the work limit altogether. With appropriate chain limits (-limitdescendantcount) the concern about doing too much work inside this function should be mitigated. (furszy) ba32375 Rename CTxMemPool::remove -> removeRecursive remove is no longer called non-recursively, so simplify the logic and eliminate an unnecessary parameter (furszy) c30fa16 CTxMemPool::removeForBlock now uses RemoveStaged (furszy) Pull request description: Ending up 2020 with a large PR :). Included a good number of performance and privacy improvements over the mempool and inv processing/sending areas + added mempool cache dump/load. Almost finishing with #1726 work, getting closer to 9725, and getting closer to be able to decouple the message processing thread <-> wallet and the wallet <-> GUI locks dependencies (which will be another long story.. but well, step by step). The final goal is clear, a much faster syncing process using pivx-qt (a good speed up for pivxd as well), smoother visual navigation when big wallets are syncing, less thread synchronization issues, among all of the improvements that will be coming with the backports adaptations. Adapted the following PRs to our sources: bitcoin#7062 —> only eb30666. bitcoin#7174 —> complete. bitcoin#7562 —> only c5d746a. bitcoin#7594 —> complete. bitcoin#7840 —> complete. bitcoin#7997 —> complete. bitcoin#8080 —> complete bitcoin#8126 —> except e9b4780 (we don't have the mapRelay) and c2a4724 (we don't have the relay expiration vector). bitcoin#8448 —> complete bitcoin#8515 —> complete bitcoin#9408 —> complete bitcoin#9966 —> complete bitcoin#10330 —> complete ACKs for top commit: random-zebra: ACK 9b9c616 Fuzzbawls: ACK 9b9c616 Tree-SHA512: 186bd09bbb19b55ec0d46dc27291663a0df2d60d8238c661a8c9b8cbf3677b6f8a92fa56bd7346a3cb5293712eeccc5d6542ee3c441d35a4f61e7d12e2ce489a

Bitcoin 0.14 locking PRs These are locking changes from upstream (bitcoin core) release 0.14, oldest to newest (when merged to the master branch). Each commit also includes a reference both to the PR and the upstream commit. - bitcoin/bitcoin#8472 - bitcoin/bitcoin#8606 - Excludes a lock move because we don't have bitcoin/bitcoin#7840 which this move was partially-reverting. - bitcoin/bitcoin#9230 - Only first commit (we don't have `LogTimestampStr` anymore). - bitcoin/bitcoin#9243 - Only the sixth commit, excluding `IsArgSet` locking (we haven't pulled that function in yet). - bitcoin/bitcoin#9626 - The cherry-picked commit does not match the upstream at all, but the resulting lock is useful. - bitcoin/bitcoin#9679 - bitcoin/bitcoin#9227 - bitcoin/bitcoin#9698 - Excludes change to `CConnman::PushMessage` in second commit (which we don't have yet). - bitcoin/bitcoin#9708 - bitcoin/bitcoin#9771

ZIP 239 preparations 2 Cherry-picked from the following upstream PRs: - bitcoin/bitcoin#6722 - Only the ancillary commits, not the mempool limiting commits (we have our own). - bitcoin/bitcoin#6898 - Only the first three commits (we'll cherry-pick the main content later). - bitcoin/bitcoin#7840

sipa force-pushed the splitinvtxblock branch 3 times, most recently from d1a6f0f to d9197de Compare April 8, 2016 13:57

gmaxwell reviewed Apr 8, 2016
View reviewed changes

gmaxwell mentioned this pull request Apr 8, 2016

Eliminate TX trickle bypass, sort TX invs for privacy and priority. #7805

Closed

sipa force-pushed the splitinvtxblock branch from 906e5c7 to 2569ffc Compare April 9, 2016 00:36

sipa force-pushed the splitinvtxblock branch from 2569ffc to 0cdc0fa Compare April 10, 2016 13:39

sipa changed the title ~~Split and optimize inv queues and improve mempool privacy~~ Several performance and privacy improvements to inv/mempool handling Apr 10, 2016

laanwj added P2P Privacy labels Apr 11, 2016

sipa mentioned this pull request Apr 11, 2016

Address mempool information leak and resource wasting attacks. #7093

Closed

sdaftuar reviewed Apr 11, 2016
View reviewed changes

sipa force-pushed the splitinvtxblock branch from 98305df to 7058b28 Compare April 19, 2016 17:52

sipa force-pushed the splitinvtxblock branch from 7058b28 to ce1d237 Compare April 19, 2016 18:04

Move bloom and feerate filtering to just prior to tx sending.

b559914

This will avoid sending more pointless INVs around updates, and prevents using filter updates to timetag transactions. Also adds locking for fRelayTxes.

sipa force-pushed the splitinvtxblock branch from cda0894 to b559914 Compare April 20, 2016 22:36

sdaftuar reviewed Apr 22, 2016
View reviewed changes

laanwj merged commit b559914 into bitcoin:master May 5, 2016

gmaxwell mentioned this pull request May 16, 2016

Remove unneeded feerate param from RelayTransaction/AcceptToMemoryPool. #8059

Merged

sdaftuar mentioned this pull request May 16, 2016

TODO for release notes 0.13.0 #7678

Closed

16 tasks

sipa mentioned this pull request Jun 13, 2016

Segregated witness #7910

Closed

7 tasks

furszy mentioned this pull request Aug 18, 2020

Up to CTransactionRef point back ports to do list. PIVX-Project/PIVX#1726

Closed

21 tasks

furszy mentioned this pull request Dec 31, 2020

[NET] Inv, mempool and validation improvements PIVX-Project/PIVX#2118

Merged

str4d mentioned this pull request Apr 1, 2021

Bitcoin 0.14 locking PRs zcash/zcash#5009

Merged

This was referenced Aug 5, 2021

ZIP 239 preparations 1 zcash/zcash#5265

Merged

ZIP 239 preparations 2 zcash/zcash#5269

Merged

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

Several performance and privacy improvements to inv/mempool handling #7840

Several performance and privacy improvements to inv/mempool handling #7840

Uh oh!

Conversation

sipa commented Apr 8, 2016

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

gmaxwell commented Apr 8, 2016

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

gmaxwell commented Apr 9, 2016

Uh oh!

gmaxwell commented Apr 9, 2016

Uh oh!

sipa commented Apr 10, 2016

Uh oh!

dcousens commented Apr 11, 2016

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sdaftuar commented Apr 11, 2016

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sipa commented Apr 12, 2016

Uh oh!

gmaxwell commented Apr 12, 2016

Uh oh!

gmaxwell commented Apr 12, 2016

Uh oh!

dcousens commented Apr 13, 2016

Uh oh!

gmaxwell commented Apr 19, 2016

Uh oh!

sipa commented Apr 19, 2016

Uh oh!

sipa commented Apr 19, 2016

Uh oh!

dcousens commented Apr 21, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

gmaxwell commented Apr 21, 2016

Uh oh!

jonasnick commented Apr 22, 2016

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 Apr 22, 2016 via email

Choose a reason for hiding this comment

Uh oh!

sdaftuar commented Apr 22, 2016

Uh oh!

gmaxwell commented Apr 26, 2016

Uh oh!

Uh oh!

dcousens commented Apr 21, 2016 •

edited

Loading