validation: fix coins disappearing mid-package evaluation

glozow commented at 1:04 pm on August 10, 2023: member

While we are evaluating a package, we split it into “subpackages” for evaluation (currently subpackages all have size 1 except the last one). If a subpackage has size 1, we may add a tx to mempool and call LimitMempoolSize(), which evicts transactions if the mempool gets full. We handle the case where the just-submitted transaction is evicted immediately, but we don’t handle the case in which a transaction from a previous subpackage (either just submitted or already in mempool) is evicted. Mainly, since the coins created by the evicted transaction are cached in m_view, we don’t realize the UTXO has disappeared until CheckInputsFromMempoolAndCache asserts that they exist. Also, the returned PackageMempoolAcceptResult reports that the transaction is in mempool even though it isn’t anymore.

Fix this by not calling LimitMempoolSize() until the very end, and editing the results map with “mempool full” if things fall out.

Pointed out by instagibbs in https://github.com/bitcoin/bitcoin/commit/faeed687e5cde5e32750d93818dd1d4add837f24 on top of the v3 PR.

glozow added the label Bug on Aug 10, 2023

glozow added the label Validation on Aug 10, 2023

DrahtBot commented at 1:04 pm on August 10, 2023: contributor

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

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	instagibbs
Concept ACK	fjahr

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#28453 (wallet: Receive silent payment transactions by achow101)
#28450 (WIP: Add package evaluation fuzzer by instagibbs)
#28368 (Fee Estimator updates from Validation Interface/CScheduler thread by ismaelsadeeq)

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.

glozow commented at 1:04 pm on August 10, 2023: member

cc @instagibbs

instagibbs commented at 1:17 pm on August 10, 2023: member

@sipa you might want to weigh in as well

in src/validation.cpp:1179 in c2c9dfe95b outdated

1183@@ -1184,32 +1184,21 @@ bool MemPoolAccept::SubmitPackage(const ATMPArgs& args, std::vector<Workspace>&
1184         }
1185     }
1186 
1187-    // It may or may not be the case that all the transactions made it into the mempool. Regardless,
1188-    // make sure we haven't exceeded max mempool size.
1189-    LimitMempoolSize(m_pool, m_active_chainstate.CoinsTip());

instagibbs commented at 3:54 pm on August 10, 2023:

Declaration comments for SubmitPackage should reflect that it doesn’t limit anymore, or just not mention limiting.

glozow commented at 3:21 pm on August 23, 2023:

Fixed, thanks

in src/validation.cpp:519 in c2c9dfe95b outdated

515@@ -516,7 +516,7 @@ class MemPoolAccept
516                             /* m_coins_to_uncache */ package_args.m_coins_to_uncache,
517                             /* m_test_accept */ package_args.m_test_accept,
518                             /* m_allow_replacement */ true,
519-                            /* m_package_submission */ false,
520+                            /* m_package_submission */ true, // do not LimitMempool

instagibbs commented at 3:58 pm on August 10, 2023:

was this always supposed to be true?

ariard commented at 3:44 am on August 11, 2023:

I think this could document more where the “do not LimitMempool” is applied, i.e in Finalize() L1123 which is itself called by AcceptSingleTransaction and the source of the bug. LimitMempoolSize() is called few times in validation.

glozow commented at 3:18 pm on August 11, 2023:

No, as it means skipping LimitMempoolSize within Finalize and we’re not always guaranteed to call SubmitPackage afterwards (e.g. if we quit early). It’s safe to make it true now because we always do a LimitMempoolSize within AcceptPackage

glozow commented at 12:44 pm on September 12, 2023:

Added “in Finalize()” to the comment

instagibbs commented at 3:59 pm on August 10, 2023: member

conditional ACK https://github.com/bitcoin/bitcoin/pull/28251/commits/c2c9dfe95b3c5b8332521d9a691725ee55ec3450

on having a test case catching the crash included. Tested with my own test case in https://github.com/bitcoin/bitcoin/pull/26403/commits/e3622f7ec944ec0e4c48ec3f29835d9f90d9d55c

in src/validation.cpp:560 in c2c9dfe95b outdated

553@@ -554,6 +554,16 @@ class MemPoolAccept
554     */
555     PackageMempoolAcceptResult AcceptMultipleTransactions(const std::vector<CTransactionRef>& txns, ATMPArgs& args) EXCLUSIVE_LOCKS_REQUIRED(cs_main);
556 
557+    /**
558+     * Submission of a subpackage.  If only 1 transaction exists in subpackage, calls
559+     * AcceptSingleTransaction() with adjusted ATMPArgs to avoid additional package policy
560+     * restrictions like PackageMempoolChecks() and disabled RBF, and creates a

ariard commented at 3:21 am on August 11, 2023:

The “disabled RBF” can sound as confusing. There is no nsequence opted-out of the transaction candidate targeted by a replacement, it sounds rather to mean the m_allow_replacement of ATMPArgs which is true for SingleInPackageAccept and false for PackageChildWithParents.

glozow commented at 12:26 pm on September 12, 2023:

Edited comment

in src/validation.cpp:1333 in c2c9dfe95b outdated

1324@@ -1326,6 +1325,23 @@ PackageMempoolAcceptResult MemPoolAccept::AcceptMultipleTransactions(const std::
1325     return PackageMempoolAcceptResult(package_state, std::move(results));
1326 }
1327 
1328+PackageMempoolAcceptResult MemPoolAccept::AcceptSubPackage(const std::vector<CTransactionRef>& subpackage, ATMPArgs& args)
1329+{
1330+    ATMPArgs single_args = ATMPArgs::SingleInPackageAccept(args);
1331+    AssertLockHeld(::cs_main);
1332+    AssertLockHeld(m_pool.cs);
1333+    if (subpackage.size() > 1) {

ariard commented at 3:47 am on August 11, 2023:

I think this check doesn’t have test coverage as tx are individually validated in AcceptPackage.

glozow commented at 3:21 pm on August 23, 2023:

No, AcceptPackage also calls this for txns_package_eval which can have multiple transactions.

ariard commented at 2:44 am on August 30, 2023:

I think there is confusion, my comment is about the test coverage of the exact code path in the first half of AcceptSubPackage not of the second usage of AccetSubPackage().

From a quick look on the tests at c2c9dfe9, it was uncertain.

ariard commented at 3:53 am on August 11, 2023: contributor

Note the code path affected by the bug is under the submitpackage RPC, which is clearly indicated as an experimental RPC with an unstable interface.

More test coverage sounds good.

in src/validation.cpp:1341 in 0678df31d5 outdated

1335@@ -1326,6 +1336,23 @@ PackageMempoolAcceptResult MemPoolAccept::AcceptMultipleTransactions(const std::
1336     return PackageMempoolAcceptResult(package_state, std::move(results));
1337 }
1338 
1339+PackageMempoolAcceptResult MemPoolAccept::AcceptSubPackage(const std::vector<CTransactionRef>& subpackage, ATMPArgs& args)
1340+{
1341+    ATMPArgs single_args = ATMPArgs::SingleInPackageAccept(args);

fjahr commented at 5:53 pm on August 18, 2023:

In the AcceptMultipleTransactions this is unused, to maybe move it down?

glozow commented at 3:21 pm on August 23, 2023:

Moved

fjahr commented at 6:10 pm on August 18, 2023: contributor

Concept ACK, will do a full review once the test has been added.

glozow commented at 1:16 pm on August 22, 2023: member

Pushed a test - it should fail on master with the assertion.

Generally, the conditions to hit the case are:

An almost-full mempool.
mempool_evicted_tx (parent) A to-be-evicted tx that is submitted ahead of time. Has a very low feerate and is evicted immediately when mempool overflows. It has an output coin_to_disappear
A package consisting of:
- cpfp_parent (child_a) parent that spends coin_to_disappear and fails a check that requires its input to be loaded and makes it eligible for reconsideration (e.g. below mempool minimum feerate).
- high-feerate parent (child_b), high feerate so that they are submitted individually and trigger eviction.
  - I’ve used 6 high-feerate parents in this test to make it easy to trigger overflow.
  - In the EA test, child_b triggers eviction due to proactive trimming of the sponsorless parent instead of mempool overflow.
- package_child (child_c) spending the above parents.
  - The child must pay a fee high enough to CPFP the low-feerate parent.
- Additional requirements:
  - The low-feerate parent needs to be checked before the higher-feerate parents so that its inputs are loaded before the eviction happens. Otherwise it will just hit missing-inputs. This also means that as a side effect of the fee-based linearization in #26711 (which would put the low-feerate parent at the end), this test won’t trigger. But I don’t think the linearization is an adequate solution to this problem.
  - To make the test interesting, it should be low enough that the to-be-evicted tx is evicted regardless of when the eviction happens.

Timeline of what happens:

mempool is almost full
mempool_evicted_tx is submitted to mempool
AcceptPackage(package):
1. AcceptSingleTransaction(cpfp_parent). This loads coin_to_disappear into m_view . After the fee is checked, the tx fails and we continue onto the next transactions.
2. for each of the n high-feerate parents, AcceptSingleTransaction(tx). These succeed and, in Finalize(), the transactions are submitted.
  1. (Without PR’s changes) this also calls LimitMempool() which evicts by descendant score until the mempool is within size limits again.
  2. This kicks out mempool_evicted_tx, which means the m_viewmempool will no longer have a coin for coin_to_disappear. However, the coin has already been cached in m_view and it doesn’t know this.
3. AcceptSingleTransaction(package_child) fails due to missing inputs.
4. AcceptMultipleTransactions([cpfp_parent, package_child])
  1. PreChecks looks for the inputs of each transaction, including the now-nonexistent coin_to_disappear. This succeeds because m_view has a coin for it.
  2. The CPFP works, so both transactions are submitted in SubmitPackage() , which calls ConsensusScriptChecks() which calls CheckInputsFromMempoolAndCache() which asserts that the coins all exist.
    1. We can’t find the coin in the mempool (which is where it used to be).
    2. So we assume we will find it in the UTXO set. We call AccessCoin() and assert !coinFromUTXOSet.IsSpent(). This fails because the coin does not exist (which is the same as isspent).

DrahtBot added the label CI failed on Aug 22, 2023

glozow force-pushed on Aug 22, 2023

instagibbs commented at 2:38 pm on August 22, 2023: member

the above test description sounds right. The eldest ancestor gets trimmed due to size limitations, then things go wonky without this change

DrahtBot removed the label CI failed on Aug 22, 2023

in test/functional/mempool_limit.py:167 in 3729ee4836 outdated

172+
173+        # Evicted transaction and its descendants must not be in mempool.
174+        resulting_mempool_txids = node.getrawmempool()
175+        assert mempool_evicted_tx["txid"] not in resulting_mempool_txids
176+        assert cpfp_parent["txid"] not in resulting_mempool_txids
177+        assert child["txid"] not in resulting_mempool_txids

instagibbs commented at 4:58 pm on August 22, 2023:

should assert all 3 parents are in the mempool

glozow commented at 3:21 pm on August 23, 2023:

Added this and the comment fixups

in test/functional/mempool_limit.py:115 in 3729ee4836 outdated

118+        assert mempool_evicted_tx["txid"] in node.getrawmempool()
119+
120+        # This parent spends the above mempool transaction that exists when its inputs are first
121+        # looked up, but disappears later. It is rejected for being too low fee (but eligible for
122+        # reconsideration), and its inputs are cached. When the mempool transaction is evicted, its
123+        # coin is no longer available, but the cache could still contains the tx.

instagibbs commented at 5:26 pm on August 22, 2023:

0        # coin is no longer available, but the cache could still contain the tx.

in test/functional/mempool_limit.py:97 in 3729ee4836 outdated

 99+        current_info = node.getmempoolinfo()
100+        mempoolmin_feerate = current_info["mempoolminfee"]
101+        assert_greater_than(mempoolmin_feerate, get_first_eviction_score(node))
102+
103+        package_hex = []
104+        parent_utxos = []

instagibbs commented at 5:28 pm on August 22, 2023:

0        parent_utxos = [] # utxos to be spent by the ultimate child transaction

in test/functional/mempool_limit.py:150 in 3729ee4836 outdated

145+            package_hex.append(parent["hex"])
146+            package_txids.append(parent["txid"])
147+            # There is room for each of these transactions independently
148+            assert node.testmempoolaccept([parent["hex"]])[0]["allowed"]
149+
150+        # Create a child spending everything, CPFPing the low-feerate parent just above mempool

instagibbs commented at 5:32 pm on August 22, 2023:

0        # Create a child spending everything, CPFPing the low-feerate cpfp_parent just above mempool

in test/functional/mempool_limit.py:91 in 3729ee4836 outdated

84@@ -84,13 +85,105 @@ def fill_mempool(self):
85         assert_equal(node.getmempoolinfo()['minrelaytxfee'], Decimal('0.00001000'))
86         assert_greater_than(node.getmempoolinfo()['mempoolminfee'], Decimal('0.00001000'))
87 
88+    def test_mid_package_eviction(self):
89+        node = self.nodes[0]
90+        self.log.info("Check a package where each parent passes the current mempoolminfee but would cause eviction")

instagibbs commented at 5:34 pm on August 22, 2023:

0        self.log.info("Check a package where each parent passes the current mempoolminfee but would cause eviction before package submission terminates")

glozow commented at 1:01 pm on August 25, 2023:

added

instagibbs approved

instagibbs commented at 5:37 pm on August 22, 2023: member

ACK https://github.com/bitcoin/bitcoin/pull/28251/commits/3729ee483688da8427c9228de01407777d4e4691

The newly added test, while slightly obscure to trigger it, makes sense and triggers the crash bug when the fix is not applied.

glozow force-pushed on Aug 23, 2023

glozow commented at 3:29 pm on August 23, 2023: member

Updated the approach + added a test for replacement case.

There are now 2 fixes: (1) Clear any non-chainstate coins at the end of AcceptSubPackage so they can’t be used in a different AcceptSubPackage. (2) Don’t trim in the middle of package evaluation.

Technically (1) is sufficient, but I think (2) is also beneficial as it avoids changing the mempool minimum feerate (which affects how we group transactions) mid-package evaluation. It would be sad if a CPFP package contains a parent that’s just barely above mempool minimum feerate, so we submit it, then evict it (due to later parent), then can’t submit the child… when we could have just submitted all of them and evicted something else.

glozow renamed this:
~~validation: avoid mempool eviction mid-package evaluation~~
validation: fix coins disappearing mid-package evaluation
on Aug 23, 2023

in src/txmempool.cpp:985 in a5a029c779 outdated

981@@ -982,6 +982,7 @@ bool CCoinsViewMemPool::GetCoin(const COutPoint &outpoint, Coin &coin) const {
982     if (ptx) {
983         if (outpoint.n < ptx->vout.size()) {
984             coin = Coin(ptx->vout[outpoint.n], MEMPOOL_HEIGHT, false);
985+            m_non_base_coins.emplace(outpoint);

instagibbs commented at 4:11 pm on August 23, 2023:

this side-effect should be noted in the declaration comments

glozow commented at 9:44 am on August 25, 2023:

Added

in src/txmempool.h:844 in a5a029c779 outdated

838@@ -839,6 +839,12 @@ class CCoinsViewMemPool : public CCoinsViewBacked
839     * validation, since we can access transaction outputs without submitting them to mempool.
840     */
841     std::unordered_map<COutPoint, Coin, SaltedOutpointHasher> m_temp_added;
842+
843+    /**
844+     * Set of all coins that have been fetched from mempool (not base). Used to internally track

instagibbs commented at 4:13 pm on August 23, 2023:

0     * Set of all coins that have been fetched from mempool or package (not base). Used to internally track

glozow commented at 9:47 am on August 25, 2023:

added

in src/txmempool.cpp:1004 in a5a029c779 outdated

 999     }
1000 }
1001+std::unordered_set<COutPoint, SaltedOutpointHasher> CCoinsViewMemPool::GetNonBaseCoins() const
1002+{
1003+    std::unordered_set<COutPoint, SaltedOutpointHasher> non_base_coins(m_non_base_coins.cbegin(), m_non_base_coins.cend());
1004+    for (const auto& [coin, _] : m_temp_added) {

instagibbs commented at 4:20 pm on August 23, 2023:

why is this necessary after PackageAddTransaction changes https://github.com/bitcoin/bitcoin/pull/28251/files#diff-c065d4cd2398ad0dbcef393c5dfc53f465bf44723348892395fffd2fb3bac522R998 ; shouldn’t non_base_coins be a superset of m_temp_added?

glozow commented at 9:46 am on August 25, 2023:

Yes. I’ve changed this to just return m_non_base_coins.

in test/functional/mempool_limit.py:223 in a5a029c779 outdated

226+
227+        # Create a child spending everything, CPFPing the low-feerate parent.
228+        approx_child_vsize = self.wallet.create_self_transfer_multi(utxos_to_spend=parent_utxos)["tx"].get_vsize()
229+        cpfp_fee = (2 * mempoolmin_feerate / 1000) * (cpfp_parent["tx"].get_vsize() + approx_child_vsize) - cpfp_parent["fee"]
230+        child = self.wallet.create_self_transfer_multi(utxos_to_spend=parent_utxos, fee_per_output=int(cpfp_fee * COIN))
231+        package_hex = [cpfp_parent["hex"], replacement_tx["hex"], child["hex"]]

instagibbs commented at 4:42 pm on August 23, 2023:

Should have a note that the importance of the submission order is paramount to the test catching the issue.

i.e. something like this passes without the fix:

0package_hex = [replacement_tx["hex"], cpfp_parent["hex"], child["hex"]]

glozow commented at 11:19 am on August 25, 2023:

Added a note

instagibbs commented at 4:51 pm on August 23, 2023: member

Ifirst pass on most recent fix to https://github.com/bitcoin/bitcoin/pull/28251/commits/a5a029c7799cb1f972e3fddc896bf009068cd8db

approach ack on fixes, would be flakey to trim things within packages prematurely.

DrahtBot added the label CI failed on Aug 24, 2023

in src/validation.cpp:1375 in a5a029c779 outdated

1361+        // We also need to manually delete these coins from m_view because it has cached copies
1362+        // of the coins it fetched from m_viewmempool when they were connected.
1363+        m_view.Uncache(outpoint);
1364+    }
1365+    m_viewmempool.Reset();
1366+    return result;

maflcko commented at 7:40 am on August 24, 2023:

0validation.cpp:1369:12: error: constness of 'result' prevents automatic move [performance-no-automatic-move,-warnings-as-errors]
1    return result;

glozow commented at 10:41 am on August 25, 2023:

thanks, fixed

in src/validation.cpp:1350 in a5a029c779 outdated

1340+        if (single_res.m_result_type != MempoolAcceptResult::ResultType::VALID) {
1341+            package_state_wrapped.Invalid(PackageValidationResult::PCKG_TX, "transaction failed");
1342+        }
1343+        return PackageMempoolAcceptResult(package_state_wrapped, {{tx->GetWitnessHash(), single_res}});
1344+    }();
1345+    // There are 3 kinds of coins in m_view:

instagibbs commented at 3:15 pm on August 24, 2023:

0    // This is an optimization to not re-fetch chainstate coins into the cache. There are 3 kinds of coins in m_view:

glozow commented at 10:41 am on August 25, 2023:

added more detail to this comment block

in src/validation.cpp:1508 in a98da1a984 outdated

1529-        submission_result.m_tx_results.insert(individual_results_nonfinal.cbegin(),
1530-                                              individual_results_nonfinal.cend());
1531-        Assume(submission_result.m_tx_results.size() == package.size());
1532-    }
1533-    return submission_result;
1534+    auto final_submission_result = quit_early || txns_package_eval.empty() ? PackageMempoolAcceptResult(package_state_quit_early, {}) :

instagibbs commented at 6:16 pm on August 24, 2023:

commit message “[refactor] back-fill m_tx_results in AcceptPackage” is old; should be results_final?

glozow commented at 10:42 am on August 25, 2023:

changed

in src/validation.cpp:1543 in a98da1a984 outdated

1543+            results_final.emplace(wtxid, final_submission_result.m_tx_results.at(wtxid));
1544+        } else if (const auto it{results_final.find(wtxid)}; it != results_final.end()) {
1545+            // Already-in-mempool transaction.
1546+            Assume(it->second.m_result_type != MempoolAcceptResult::ResultType::INVALID);
1547+            Assume(individual_results_nonfinal.count(wtxid) == 0);
1548+        } else if (const auto it{individual_results_nonfinal.find(wtxid)}; it != individual_results_nonfinal.end()) {

instagibbs commented at 6:27 pm on August 24, 2023:

Looks like we’re considering individual_results_nonfinal after the subpackage one, contrary to the description of individual_results_nonfinal which says that in the event of multiple failures, the individual result is reported. Looks like there’s no test coverage of this case; how important is it?

glozow commented at 11:16 am on August 25, 2023:

I’ve changed the comment above results_final and individual_results_nonfinal to be accurate to this PR and to #26711.

This is most relevant when we otherwise don’t have a result for this tx. From P2P it will be helpful for rejection caching and MaybePunish to know whenever there was a problem with any transaction. In this case where we override the result with “mempool full”, it’s the same result anyway (TX_MEMPOOL_POLICY).

instagibbs commented at 4:00 pm on August 25, 2023:

clearer the way it is now, thanks!

in src/validation.cpp:516 in 4cd3b8f2ed outdated

515@@ -516,7 +516,7 @@ class MemPoolAccept
516                             /* m_coins_to_uncache */ package_args.m_coins_to_uncache,

instagibbs commented at 6:52 pm on August 24, 2023:

from commit message in 4cd3b8f2edb3176fef4dbc6109188d62e7dd2ba6

“- We cache a coin from a mempool transaction in m_view, but the coin disappears due to eviction.”

No longer true with the AcceptSubPackage changes in place

glozow commented at 1:01 pm on August 25, 2023:

removed

in src/validation.cpp:1536 in 4cd3b8f2ed outdated

1525+            // have been evicted due to LimitMempoolSize() above. Check by txid to include the
1526+            // same-txid-different-witness case.
1527             Assume(it->second.m_result_type != MempoolAcceptResult::ResultType::INVALID);
1528             Assume(individual_results_nonfinal.count(wtxid) == 0);
1529+            if (!m_pool.exists(GenTxid::Txid(tx->GetHash()))) {
1530+                package_state_final.Invalid(PackageValidationResult::PCKG_TX, "transaction failed");

instagibbs commented at 7:12 pm on August 24, 2023:

0                package_state_final.Invalid(PackageValidationResult::PCKG_TX, "transaction failed");
1                results_final.emplace(wtxid, MempoolAcceptResult::Failure(mempool_full_state));

?

glozow commented at 10:43 am on August 25, 2023:

Bad rebase. Fixed

glozow force-pushed on Aug 25, 2023

DrahtBot removed the label CI failed on Aug 25, 2023

in src/txmempool.h:859 in c3b552925d outdated

854+     * coin is not fetched from base. */
855     bool GetCoin(const COutPoint &outpoint, Coin &coin) const override;
856     /** Add the coins created by this transaction. These coins are only temporarily stored in
857      * m_temp_added and cannot be flushed to the back end. Only used for package validation. */
858     void PackageAddTransaction(const CTransactionRef& tx);
859+    /** Get all coins in m_non_base_coins and m_temp_added. */

instagibbs commented at 3:55 pm on August 25, 2023:

nit: m_temp_added isn’t involved

glozow commented at 12:22 pm on September 12, 2023:

Fixed comment

instagibbs approved

instagibbs commented at 4:04 pm on August 25, 2023: member

ACK https://github.com/bitcoin/bitcoin/pull/28251/commits/22fe13e3526b582170c05f823395dba0a3c9c99a

in test/functional/mempool_limit.py:91 in 22fe13e352 outdated

101+
102+        # Restarting the node resets mempool minimum feerate
103+        assert_equal(node.getmempoolinfo()['minrelaytxfee'], Decimal('0.00001000'))
104+        assert_equal(node.getmempoolinfo()['mempoolminfee'], Decimal('0.00001000'))
105+
106+        self.fill_mempool()

ariard commented at 3:19 am on August 30, 2023:

As I understand one of the condition to hit the case is a full mempool and when we call LimitMempool(), one interesting variation of the test case could be to limit the mempool size to the subpackage only. It might be a tricky one, though boundary conditions are always nice to exercise.

glozow commented at 12:18 pm on September 12, 2023:

Yes, full mempool is one of the conditions (i.e. the one tested in test_mid_package_eviction). It’s not strictly necessary though, the coin can also disappear due to replacement.

one interesting variation of the test case could be to limit the mempool size to the subpackage only

Do you mean setting the mempool’s maximum memory to something very tiny?

ariard commented at 3:23 am on August 30, 2023: contributor

Thanks for the in-depth explanation of the conditions to hit the case. Will review more the code and test coverage as high-prio.

in src/validation.cpp:653 in 22fe13e352 outdated

649@@ -639,10 +650,9 @@ class MemPoolAccept
650 
651     // Submit all transactions to the mempool and call ConsensusScriptChecks to add to the script
652     // cache - should only be called after successful validation of all transactions in the package.
653-    // The package may end up partially-submitted after size limiting; returns true if all
654-    // transactions are successfully added to the mempool, false otherwise.
655+    // Does not call LimitMempool(), so maximum size may be temporarily exceeded.

ariard commented at 1:05 am on September 2, 2023:

nit: I think it can be commented as max_size_bytes to make clear which mempool limits is bypassed, to dissociate from ancestor / descendant one.

glozow commented at 12:49 pm on September 12, 2023:

mentioned

in src/validation.cpp:559 in 22fe13e352 outdated

553@@ -554,6 +554,17 @@ class MemPoolAccept
554     */
555     PackageMempoolAcceptResult AcceptMultipleTransactions(const std::vector<CTransactionRef>& txns, ATMPArgs& args) EXCLUSIVE_LOCKS_REQUIRED(cs_main);
556 
557+    /**
558+     * Submission of a subpackage. If only 1 transaction exists in subpackage, calls
559+     * AcceptSingleTransaction() with adjusted ATMPArgs to avoid additional package policy

ariard commented at 1:20 am on September 2, 2023:

Here it can be say “adjusted ATMPArgs” (ATMPArgs::SingleInPackageAccept).

glozow commented at 10:11 am on September 4, 2023:

I think this is already the case? “calls AcceptSingleTransaction() with adjusted ATMPArgs”

glozow commented at 12:54 pm on September 12, 2023:

Resolving this comment but lmk if you meant something different

in src/validation.cpp:1192 in 22fe13e352 outdated

1193     std::transform(workspaces.cbegin(), workspaces.cend(), std::back_inserter(all_package_wtxids),
1194                    [](const auto& ws) { return ws.m_ptx->GetWitnessHash(); });
1195-    // Find the wtxids of the transactions that made it into the mempool. Allow partial submission,
1196-    // but don't report success unless they all made it into the mempool.
1197+
1198+    // Add successful results. The returned results may change later if LimitMempool() evicts them.

ariard commented at 1:27 am on September 2, 2023:

s/LimitMempool()/LimitMempoolSize()/g

glozow commented at 12:48 pm on September 12, 2023:

Thanks, changed

in src/validation.cpp:1357 in 22fe13e352 outdated

1352+    //
1353+    // (1) Temporary coins need to be removed, regardless of whether the transaction was submitted.
1354+    // If the transaction was submitted to the mempool, m_viewmempool will be able to fetch them from
1355+    // there. If it wasn't submitted to mempool, it is incorrect to keep them - future calls may try
1356+    // to spend those coins that don't actually exist.
1357+    // (2) Mempool coins also need to be removed. If the mempool contents have changed, coins

ariard commented at 1:59 am on September 2, 2023:

Currently, we take LOCK(m_pool.cs) L1431 in AcceptPackage() and the two calls to AcceptSubPackage() happens L1475 and L1504, where lock should still be held and mempool contents not have changed ?

glozow commented at 10:10 am on September 4, 2023:

I mean the contents have changed because we submitted transaction(s), not due to another thread’s actions.

glozow commented at 12:27 pm on September 12, 2023:

Clarified this comment

in src/validation.cpp:1432 in 22fe13e352 outdated

1442-    ATMPArgs single_args = ATMPArgs::SingleInPackageAccept(args);
1443-    // Results from individual validation. "Nonfinal" because if a transaction fails by itself but
1444-    // succeeds later (i.e. when evaluated with a fee-bumping child), the result changes (though not
1445-    // reflected in this map). If a transaction fails more than once, we want to return the first
1446-    // result, when it was considered on its own. So changes will only be from invalid -> valid.
1447+    // Stores "final" results from which we will create the returned PackageMempoolAcceptResult.

ariard commented at 2:07 am on September 2, 2023:

Finality is already an existent notion related to transaction validation (IsFinalTx in src/consensus/tx_verify.cpp). Maybe it can be called results_nondefinitive or results_partial.

glozow commented at 12:30 pm on September 12, 2023:

removed the word “final”

glozow commented at 12:53 pm on September 12, 2023:

I agree renaming wouldn’t be a bad idea, but perhaps the best time to do it is after #26711 (which changes the way this map is used) with a scripted-diff.

DrahtBot added the label CI failed on Sep 4, 2023

DrahtBot removed the label CI failed on Sep 5, 2023

glozow commented at 2:29 pm on September 6, 2023: member

Concept ACK, will do a full review once the test has been added.

ping @fjahr :)

ariard commented at 11:41 pm on September 8, 2023: contributor

If one wanna test the crash on master to check new test coverage, skipping the new fix branch here: https://github.com/ariard/bitcoin/commit/cf0b24ce0b7034ac6e344db7b04012f5b430d4a1

instagibbs commented at 2:12 pm on September 11, 2023: member

Built a fuzzer which also caught this issue very quickly on my wimpy laptop: https://github.com/bitcoin/bitcoin/pull/28450

glozow force-pushed on Sep 12, 2023

glozow commented at 12:51 pm on September 12, 2023: member

Incorporated suggestions. All documentation-related so should be trivial to re-ack.

instagibbs commented at 12:55 pm on September 12, 2023: member

reACK https://github.com/bitcoin/bitcoin/pull/28251/commits/a929cab981688dae88f1ae692a6a322328da12b0

trivial comment updates

DrahtBot added the label CI failed on Sep 12, 2023

DrahtBot commented at 11:53 am on September 13, 2023: contributor

fuzz CI:

0validation.cpp:1538 AcceptPackage: Assertion `it->second.m_result_type != MempoolAcceptResult::ResultType::INVALID' failed.

glozow commented at 12:24 pm on September 13, 2023: member

Thanks! Reproduced, debugging

glozow force-pushed on Sep 13, 2023

[policy] check for duplicate txids in package

Duplicates of normal transactions would be found by looking for
conflicting inputs, but this doesn't catch identical empty transactions.
These wouldn't be valid but exiting early is good and AcceptPackage's
result sanity checks assume non-duplicate transactions.

7d7f7a1189

[CCoinsViewMemPool] track non-base coins and allow Reset

Temporary coins should not be available in separate subpackage submissions.
Any mempool coins that are cached in m_view should be removed whenever
mempool contents change, as they may be spent or no longer exist.

3f01a3dab1

[validation] add AcceptSubPackage to delegate Accept* calls and clean up m_view

(1) Call AcceptSingleTransaction when there is only 1 transaction in the
  subpackage. This avoids calling PackageMempoolChecks() which enforces
rules that don't need to be applied for a single transaction, i.e.
disabling CPFP carve out.
There is a slight change in the error type returned, as shown in the
txpackage_tests change.  When a transaction is the last one left in the
package and its fee is too low, this returns a PCKG_TX instead of
PCKG_POLICY. This interface is clearer; "package-fee-too-low" for 1
transaction would be a bit misleading.

(2) Clean up m_view and m_viewmempool so that coins created in this
sub-package evaluation are not available for other sub-package
evaluations. The contents of the mempool may change, so coins that are
available now might not be later.

03b87c11ca

[validation] make PackageMempoolAcceptResult members mutable

After the PackageMempoolAcceptResult is returned from
AcceptMultipleTransactions, leave room for results to change due to
LimitMempool() eviction.

8ad7ad3392

[refactor] back-fill results in AcceptPackage

Instead of populating the last PackageMempoolAcceptResult with stuff
from results_final and individual_results_nonfinal, fill results_final
and create a PackageMempoolAcceptResult using that one.

A future commit will add LimitMempoolSize() which may change the status
of each of these transactions from "already in mempool" or "submitted to
mempool" to "no longer in mempool". We will change those transactions'
results here.

A future commit also gets rid of the last AcceptSubPackage outside of
the loop. It makes more sense to use results_final as the place where
all results end up.

9698b81828

[validation] return correct result when already-in-mempool tx gets evicted

Bug fix: a transaction may be in the mempool when package evaluation
begins (so it is added to results_final with MEMPOOL_ENTRY or
DIFFERENT_WITNESS), but get evicted due to another transaction
submission.

d227b7234c

[validation] don't LimitMempoolSize in any subpackage submissions

Don't do any mempool evictions until package validation is done,
preventing the mempool minimum feerate from changing. Whether we submit
transactions separately or as a package depends on whether they meet the
mempool minimum feerate threshold, so it's best that the value not
change while we are evaluating a package.
This avoids a situation where we have a CPFP package in which
the parents meet the mempool minimum feerate and are submitted by
themselves, but they are evicted before we have submitted the child.

3ea71feb11

[test framework] add ability to spend only confirmed utxos

Useful to ensure that the topologies of packages/transactions are as
expected, preventing bugs caused by having unexpected mempool ancestors.

d08696120e

[refactor] split setup in mempool_limit test

We want to be able to re-use fill_mempool so that none of the tests
affect each other.

Change the logs from info to debug because they are otherwise repeated
many times in the test output.

a67f460c3f

[test] mempool coins disappearing mid-package evaluation

Test for scenario(s) outlined in PR 28251.
Test what happens when a package transaction spends a mempool coin which
is fetched and then disappears mid-package evaluation due to eviction or
replacement.

32c1dd1ad6

glozow force-pushed on Sep 13, 2023

instagibbs commented at 4:24 pm on September 13, 2023: member

reACK https://github.com/bitcoin/bitcoin/pull/28251/commits/32c1dd1ad65af0ad4d36a56d2ca32a8481237e68

inclusion of https://github.com/bitcoin/bitcoin/pull/28251/commits/7d7f7a1189432b1b6245ba25df572229870567cb duplicate-txid check in CheckPackage which prevents the assertion being hit for the 2nd of the duplicate txids

DrahtBot removed the label CI failed on Sep 13, 2023

fanquake merged this on Sep 13, 2023

fanquake closed this on Sep 13, 2023

Frank-GER referenced this in commit 74c256e798 on Sep 19, 2023

glozow referenced this in commit 6619d6a8dc on Sep 28, 2023

Frank-GER referenced this in commit 461bf19b50 on Oct 5, 2023

Fabcien referenced this in commit 8de49c3ef8 on Jul 12, 2024

bitcoin locked this on Sep 12, 2024

bitcoin unlocked this on Oct 23, 2024

sdaftuar commented at 9:31 pm on October 23, 2024: member

I’m reviewing this PR more carefully, after seeing @instagibbs’ comment here: #31122 (review)

As I understand it, I think there are two key behaviors introduced in this PR:

Clearing state between subpackage evaluations (specifically, clearing the coins in m_viewmempool)
Deferring mempool limiting until the end of package validation

However, the specific issue that @glozow described above (https://github.com/bitcoin/bitcoin/pull/28251#issuecomment-1688170869), where we need to ensure that package validation fails if an input is evicted mid-validation, seems to be completely mitigated by behavior (1). And this behavior is tested in the mempool_limit test introduced in this PR.

As far as I can tell from reviewing 3ea71fe (#28251), behavior (2) is designed to allow package validation to succeed in a case where we have, say, a child C with two parents A and B, and we submit a package [A, B, C] and potentially trigger this outcome:

A is accepted singly
B is accepted singly, but the mempool overflows and A is trimmed
C is rejected for missing inputs

So by preventing mempool limiting from taking place mid-package, the choice of what to evict from the mempool is deferred until after C is able to make it in, potentially changing the lowest-descendant-score transaction in the mempool from A to something else (as A’s descendant score might be pretty high after C is accepted).

However, I don’t think this PR introduced any test for this second behavior, of ensuring success is possible even if an earlier parent might be trimmed mid-validation.

Does this summary sound right to others? Have I overlooked other behavior changes/bugfixes that were introduced here?

glozow commented at 0:26 am on October 25, 2024: member

As I understand it, I think there are two key behaviors introduced in this PR

However, the specific issue that @glozow described above (https://github.com/bitcoin/bitcoin/pull/28251#issuecomment-1688170869), where we need to ensure that package validation fails if an input is evicted mid-validation, seems to be completely mitigated by behavior (1).

As far as I can tell from reviewing 3ea71fe (#28251), behavior (2) is designed to allow package validation to succeed in a case where…

However, I don’t think this PR introduced any test for this second behavior,

This looks accurate to me. I’ve looked a little at the tests (it’s been a while :sweat_smile:) and can’t really point to one for deferring evictions. Will review #31152.

glozow deleted the branch on Oct 25, 2024

validation: fix coins disappearing mid-package evaluation #28251

Reviews

Conflicts