Add package acceptance logic to mempool #16401

sdaftuar · 2019-07-16T20:16:12Z

Accepting a single transaction to the mempool only succeeds if (among other things) the feerate of the transaction is greater than both the min relay fee and the mempool min fee. Consequently, a transaction below the minimum fee may not be accepted to the mempool, even if we later learn of a transaction with a high fee that depends on it.

This PR adds code to validation that will accept a package of transactions to the mempool under the following conditions:

All package transactions must be direct parents of the final transaction.
This is a simple heuristic for ensuring that a candidate list of transactions
is in fact a package (we wouldn't want arbitrary transactions to be paying
for random low feerate transactions)
The feerate of the package, as a whole, exceeds the mempool min fee and the
min relay fee.
No transactions in the mempool conflict with any transactions in the package.
This is a simplification that makes the logic easier to write. Without this
requirement, we would need to do additional checks to ensure that no parent
transaction would evict a transaction from the mempool that some other child
depends on.
The ancestor/descendant size limits are calculated assuming that any mempool
ancestor of any candidate transaction is an ancestor of all the candidate
transactions.
This allows for doing simpler calculations to ensure that we're staying
within the mempool's package limits. If we eliminated this, we would need to
do much more careful package calculations for each candidate transaction and each
in-mempool ancestor.

This PR also adds code to net_processing that will attempt to process transaction packages in one narrow case: if a transaction fails to get into the mempool due to insufficient fee, but has an orphan in the orphan pool, then we will try to process the pair together to see if they can be accepted as a package.

This PR is definitely WIP, but I'm opening it as a proof-of-concept motivation for refactoring ATMP (#16400).

DrahtBot · 2019-07-16T22:33:17Z

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#17985 (net: Remove forcerelay of rejected txs by MarcoFalke)
#17399 (validation: Templatize ValidationState instead of subclassing by jkczyz)
#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.

ajtowns

I think this works as a proof of concept.

src/validation.h

src/net_processing.cpp

src/validation.cpp

ajtowns · 2019-07-25T02:12:17Z

src/validation.cpp


+    // Make sure all transactions are ancestors of the last one.
+    // For now, just check that the last transaction has all prior transactions
+    // as direct inputs. We can relax this in the future for bigger packages.


This check could be done first, before even setting up the workspaces, as far as I can see.

ajtowns · 2019-07-25T02:17:43Z

src/validation.cpp

+        // not fail unless there's a logic bug in our script validation, but if
+        // it somehow were to fail on some child tx, we would potentially be
+        // allowing parents into the mempool with this logic.
+        if (!ConsensusScriptChecks(args, *wit, txdata[i])) return false;


This seems like it would be a good case for the CHECK macro from #16136 (if it logged failures, anyway)...

ajtowns · 2019-07-25T02:18:13Z

src/validation.cpp

+    // Add everything to the mempool, and make sure the last transaction makes
+    // it in.
+    size_t i=0;
+    for (auto wit = tx_workspaces.begin(); wit != tx_workspaces.end(); ++wit, ++i) {


Would be nice if C++11 had a "zip" iterator... FWIW, you could do this as:

struct WorkspaceAndTxData { Workspace ws; PrecomputedTransactionData* ptxdata; }; std::list<WorkspaceAndTxData> tx_workspaces; ... for (auto& wstxd : tx_workspaces) { txdata.emplace_back(*wstxd.ws.m_ptx); wstxd.ptxdata = &txdata.back(); }

and only have to loop over tx_workspaces, but it's probably not worth the hassle.

ajtowns · 2019-07-25T02:30:42Z

src/validation.cpp

-    GetMainSignals().TransactionAddedToMempool(ptx);
+    // In case we have no in-mempool ancestors, we must check the transaction
+    // package itself.
+    if (total_size > m_limit_descendant_size) {


Might as well do this test before looping over all_ancestors

ajtowns · 2019-07-25T03:22:18Z

src/validation.cpp

+}
+
+
+bool MemPoolAccept::AcceptMultipleTransactions(std::list<CTransactionRef> tx_list, ATMPArgs& args)


I think once this is more baked, it'd be good to pull sections of this out into their own private MemPoolAccept:: methods so the overall logic in this function is as clear as the logic in AcceptSingleTransaction

NicolasDorier · 2019-09-30T08:21:36Z

src/txmempool.h

@@ -751,8 +751,12 @@ class CTxMemPool
 */
 class CCoinsViewMemPool : public CCoinsViewBacked
 {
+public:
+    void AddPotentialTransaction(const CTransactionRef& ptx) { package_tx.emplace(ptx->GetHash(), ptx); }


As far as I see, in the current code code paths, the max number of elements in package_tx is two.
But maybe there should be a hard limit, even if high, at this level just in case?

etscrivner · 2019-10-01T14:57:05Z

src/validation.cpp

+            std::string dummy_string;
+            // Don't worry about the return value here; it must pass based on
+            // the checks above. TODO: assert on passing?
+            m_pool.CalculateMemPoolAncestors(*(wit->m_entry), wit->m_ancestors, m_limit_ancestors, m_limit_ancestor_size, m_limit_descendants, m_limit_descendant_size, dummy_string);


This is probably also a good spot for a DCHECK just to ensure that the assumption - "this must pass based on the checks above" - holds here.

pinheadmz · 2019-10-02T13:37:22Z

test/functional/feature_package_relay.py

+        self.nodes[1].generate(101)
+        self.sync_all(self.nodes[0:2])
+
+        # On node1, generate a 0-fee transaction, and then a 2-satoshi-per-byte


I might be misunderstanding, but it looks like the first tx fee rate is set to 2 sat/kB (actual total fee on this tx comes out to a single sat) and the second tx fee rate is set to 50000 (actual total fee ~0.000083)?

etscrivner · 2019-10-02T14:34:27Z

Agree with others that I think this works as a proof-of-concept. In my opinion, this still needs more work on tests, more extensive testing, and generalization beyond 2 transaction packages (up to some maximum package size).

fjahr

This works for me as a proof of concept. Obviously the tests still need some work but thanks for the extensive commenting in the code.

fjahr · 2019-10-02T16:22:52Z

src/net_processing.cpp

+            // one parent.
+            // Try to process the pair as a package.
+            bool added_as_package = false;
+            if (state.GetRejectCode() == REJECT_INSUFFICIENTFEE) {


Maybe also add a check for g_orphan_list.size() > 0 here? But I am not experienced with the orphan pool so it may be fair to leave it out if the orphan pool is populated 99% of the time.

jonatack

Concept/approach ACK cd8f11a, tests pass here as well as rebased on master, node running since a few hours with net logging. The code documentation is helpful. Am still reviewing the code, logic, and test, particularly the checks to satisfy and the complexity introduced in AcceptMultipleTransactions().

Suggestion to reviewers: It may be helpful to review merged PR #16400 and issue #14895 before this one.

Given that this PR is labelled Draft and the ATMP refactoring in #16400 has been merged, what are your plans going forward beyond concept/approach ACKs? For example, continue refactoring the p2p protocol for package relay computational efficiency/simplicity/multiparents, or moving forward with a standalone PoC implementation like this one?

pinheadmz · 2019-10-02T17:26:42Z

test/functional/feature_package_relay.py

+
+        # Delivering tx2 should result it being in the orphan pool, and then
+        # delivering tx should cause both to be accepted.
+        p2p = self.nodes[0].add_p2p_connection(BaseNode())


Couldn't this p2p variable be defined up on line 67?

etscrivner · 2019-10-02T17:55:46Z

Add some additional tests in this gist and have also addressed the TODO item: https://gist.github.com/etscrivner/19d5f942a973940aaaeb397bc5e0e0d9

ariard

Reviewed only mempool/validation change for now.

No transactions in the mempool conflict with any transactions in the package.
This is a simplification that makes the logic easier to write. Without this
requirement, we would need to do additional checks to ensure that no parent
transaction would evict a transaction from the mempool that some other child
depends on.

I assume we can still RBF both parents or CPFP child in case our package txn are still stucking in the mempool? It shouldn't be an issue as after acceptance txn are normal mempool txn, assuming we don't have package garbage value for ancestors/descendants.

The ancestor/descendant size limits are calculated assuming that any mempool
ancestor of any candidate transaction is an ancestor of all the candidate
transactions.

It should be fine for LN as unconfirmed ancestors should be limited to 2 (commitment tx and CPFP) unless people batch their commitment txn with one CPFP.

ariard · 2019-10-31T22:53:00Z

src/validation.cpp

@@ -311,6 +308,14 @@ bool CheckSequenceLocks(const CTxMemPool& pool, const CTransaction& tx, int flag
    return EvaluateSequenceLocks(index, lockPair);
 }

+bool CheckSequenceLocks(const CTxMemPool& pool, const CTransaction& tx, int flags, LockPoints* lp, bool useExistingLockPoints)


I think the new wrapper doesn't do what the removed comment intended? Can't we pass coins_cache defined above instead of defining a new one, would work too in removeForReorg ? Also isn't this a behavior change as coin is fetched from UTXO set instead from mempool?

This change is may worth its own commit.

ariard · 2019-10-31T22:58:05Z

src/validation.cpp

@@ -239,10 +239,9 @@ bool TestLockPointValidity(const LockPoints* lp)
    return true;
 }

-bool CheckSequenceLocks(const CTxMemPool& pool, const CTransaction& tx, int flags, LockPoints* lp, bool useExistingLockPoints)
+static bool CheckSequenceLocks(CCoinsViewCache &view, const CTransaction& tx, int flags, LockPoints* lp, bool useExistingLockPoints=false) EXCLUSIVE_LOCKS_REQUIRED(cs_main)


EXCLUSIVE_LOCKS_REQUIRED(pool.cs, cs_main)? (wrapper and AcceptMultipleTransactions too)

ariard · 2019-10-31T23:03:52Z

src/validation.cpp

-    // No transactions are allowed below minRelayTxFee except from disconnected
-    // blocks
+    // No transactions are allowed below minRelayTxFee/mempool min fee except
+    // from disconnected blocks


"or being CPFP'ed by another tx"

ariard · 2019-10-31T23:23:41Z

src/txmempool.h

 protected:
    const CTxMemPool& mempool;
+    std::map<uint256, const CTransactionRef> package_tx;


Could have a better name like package_pool just to underscore we have multiple pending txn. I didn't get the rational at first read, I think you can explain given we have mempool locked and can't write until we have the whole set of tx, we need this temporary buffer to find outpoints of package txn after first row of parents. If this to work assuming topological ordering it should be documented?

ariard · 2019-10-31T23:48:52Z

src/validation.cpp

+        if (!PreChecks(args, ws)) return false;
+
+        // For now, do not allow replacements in package transactions. If we
+        // relax this, we would need to check that no child transaction depends


+1 for conflicts isolation for now. But IMO we may have to solve child conflicts in a way or another if people start to use one CPFP to bump multiple multi-party txn, like Alice broadcast commitment tx 1 + CPFP child tx, txn get into mempool, now she have to broadcast commitment tx 2 but doesn't have another UTXO available and can't CPFP output as going beyond carve-out relaxation..

ariard · 2019-11-01T00:35:46Z

src/validation.cpp

+    // This package should be accepted except possibly for failing in
+    // TrimToSize(), which we can't exercise without actually adding to the
+    // mempool and seeing what would happen. Note that we are not adding
+    // these transactions to the script cache, unlike in the single-tx case.


ariard

It should be made really clear for off-chain protocol devs to always rebroadcast the whole package instead of only the parent or the child. I'm worrying about scenarii where a a commitment tx is broadcast, don't get into the mempool neither orphan one, latter the high-fee child is broadcast at the application logic and get into the orphan, an attacker overfulfill the orphan pool to discard the child, the application logic rebroadcast the parent tx but not the CPFP assuming it's already there...

That's said, I think the P2P work on principle but could be made more robust and tests should include multiple bumped childs and orphan pool overflow.

ariard · 2019-11-01T16:50:35Z

src/net_processing.cpp

@@ -748,6 +748,20 @@ void RequestTx(CNodeState* state, const uint256& txid, std::chrono::microseconds
    peer_download_state.m_tx_process_time.emplace(process_time, txid);
 }

+// Add to a peer's orphan_work_set after processing a given transaction.
+void UpdateOrphanWorkSet(const CTransaction& tx, CNode *peer) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans)


Can be reused too in ProcessOrphanTx

ariard · 2019-11-01T17:33:17Z

src/net_processing.cpp

+                    }
+                }
+                if (!orphans_missing_this_tx.empty()) {
+                    const COrphanTx &orphan_tx = orphans_missing_this_tx.front()->second;


If I broadcast a second CPFP due to to the first one being still too low but this one still being in the orphan pool, you need to iter and try with the whole set not only picking up the first transaction ? That would be a DoS vector bounded by the size of the orphan pool, and maybe it can be mitigate by caching the package already-tried.

ariard · 2019-11-01T18:09:20Z

src/net_processing.cpp

+
+                        // Recursively process any orphan transactions that depended on these
+                        ProcessOrphanTx(connman, pfrom->orphan_work_set, lRemovedTxn);
+                    }


If package wasn't accepted (like a high-fee invalid orphan tx), and if inputs are not missing, if orphan_tx is invalid we may punish peer, or at least erase it for not being standard or insufficient fee?

Accepting a single transaction to the mempool only succeeds if (among other things) the feerate of the transaction is greater than both the min relay fee and the mempool min fee. Consequently, a transaction below the minimum fee may not be accepted to the mempool, even if we later learn of a transaction with a high relay fee that depends on it. This commit adds a function that will accept a package of transactions to the mempool, with the following restrictions: - All package transactions must be direct parents of the final transaction. This is a simple heuristic for ensuring that a candidate list of transactions is in fact a package (we wouldn't want arbitrary transactions to be paying for random low feerate transactions) - The feerate of the package, as a whole, exceeds the mempool min fee and the min relay fee. - No transactions in the mempool conflict with any transactions in the package. This is a simplification that makes the logic easier to write. Without this requirement, we would need to do additional checks to ensure that no parent transaction would evict a transaction from the mempool that some other child depends on. - The ancestor/descendant size limits are calculated assuming that any mempool ancestor of any candidate transaction is an ancestor of all the candidate transactions. This allows for doing simpler calculations to ensure that we're staying within the mempool's package limits. If we eliminated this, we would need to do much more careful package calculations for each candidate transaction and each in-mempool ancestor. This commit does not include any accessor function for utilizing this logic (eg by exposing this function at the p2p or rpc layer).

ariard · 2020-01-09T01:35:15Z

In fact worry described here holds, I've modified the new test a bit to overflow the orphan pool with dumb-but-valid orphan pools and it succeeds to evict high-fee child tx easily, even with a low number of malicious orphans (200) : ariard@e20ad2a

Exposes a simple use case for package relay -- if we receive a child transaction that is missing a parent, then we request the parent from our peers. If a peer responds with a transaction that is rejected from the mempool due to feerate, we have an opportunity to accept that parent along with the child, if the child's feerate is sufficiently high and the child is missing no other parents.

sdaftuar · 2020-01-09T04:01:38Z

It should be made really clear for off-chain protocol devs to always rebroadcast the whole package instead of only the parent or the child. I'm worrying about scenarii where a a commitment tx is broadcast, don't get into the mempool neither orphan one, latter the high-fee child is broadcast at the application logic and get into the orphan, an attacker overfulfill the orphan pool to discard the child, the application logic rebroadcast the parent tx but not the CPFP assuming it's already there...

@ariard It wasn't my goal in this PR to deploy a new p2p package relay scheme that is resilient to DoS attack; instead I wanted to take a smaller use case (resolving orphan transactions missing a single low fee parent) to motivate adding the package acceptance logic.

I think once we have the mempool package acceptance logic in, we could then improve the p2p layer further to allow fancier relay schemes. (See also my comment in #14895 (comment).)

I'll update the title of the PR to make this more clear.

ariard · 2020-01-09T17:10:22Z

Thanks for clarifying scope of this PR. I do think too it's good to split this project in multi-parts to focus on new mempool acceptance logic, specially what the worst width/depth of a chain of messy transactions we select as a package submission DoS bound.

That's said, we may reduce the risks of mempool CPU DoS by implementing the right measures at the p2p level like rate-limiting per-peer package reception. Also if we have different p2p package relay mechanisms (receiver-initiated, sender p2p messages, ...) we need to think how we coordinate them between different releases to avoid applications relying on the wrong ones for their uses cases and falsely assuming they are secure.

sdaftuar · 2020-01-29T14:55:24Z

I'm starting to think that perhaps the use case here isn't really worth it -- I tried to split off what I thought would be a simple use case (of processing some orphan transactions as packages with their rejected parents), but it turns out to be a bit trickier than I expected, and given that we'd just throw this away if we implemented an actual package relay protocol anyway this seems like wasted effort.

sdaftuar mentioned this pull request Jul 16, 2019

refactor: Rewrite AcceptToMemoryPoolWorker() using smaller parts #16400

Merged

DrahtBot added Mempool P2P Tests Validation labels Jul 17, 2019

sdaftuar force-pushed the 2019-07-package-relay branch from dddfe51 to 149930d Compare July 24, 2019 18:31

ajtowns reviewed Jul 25, 2019

View reviewed changes

sdaftuar force-pushed the 2019-07-package-relay branch from 6938af6 to 779debf Compare July 31, 2019 14:27

ajtowns mentioned this pull request Sep 11, 2019

Continue relaying transactions after they expire from mapRelay #16851

Merged

sdaftuar force-pushed the 2019-07-package-relay branch from 779debf to cd8f11a Compare September 19, 2019 14:28

jonatack mentioned this pull request Sep 22, 2019

Future PRs bitcoin-core-review-club/website#14

Closed

NicolasDorier reviewed Sep 30, 2019

View reviewed changes

etscrivner reviewed Oct 1, 2019

View reviewed changes

pinheadmz reviewed Oct 2, 2019

View reviewed changes

fjahr reviewed Oct 2, 2019

View reviewed changes

jonatack reviewed Oct 2, 2019

View reviewed changes

pinheadmz reviewed Oct 2, 2019

View reviewed changes

halseth mentioned this pull request Oct 10, 2019

Add anchor output to the commitment transaction lightningnetwork/lnd#3587

Closed

ariard reviewed Nov 1, 2019

View reviewed changes

sdaftuar marked this pull request as ready for review January 8, 2020 20:47

DrahtBot added the Needs rebase label Jan 8, 2020

sdaftuar force-pushed the 2019-07-package-relay branch from cd8f11a to 6a3bdba Compare January 9, 2020 03:56

sdaftuar changed the title ~~Package relay~~ Add package acceptance logic to mempool Jan 9, 2020

DrahtBot removed the Needs rebase label Jan 9, 2020

oleganza mentioned this pull request Jan 23, 2020

zkvm: fees mechanism stellar/slingshot#398

Open

9 tasks

sdaftuar closed this Jan 29, 2020

jonatack mentioned this pull request Apr 27, 2020

Newsletter 95 (2020-04-29) bitcoinops/bitcoinops.github.io#394

Merged

5 tasks

ariard mentioned this pull request Jul 29, 2020

[RFC] Package-relay: sender-initiated #19621

Closed

This was referenced Jan 5, 2021

locks and docs in ATMP and CheckInputsFromMempoolAndCache #20834

Merged

rpc/validation: enable packages through testmempoolaccept #20833

Merged

ariard mentioned this pull request Aug 24, 2021

validation: mempool validation and submission for packages of 1 child + parents #22674

Merged

bitcoin locked as resolved and limited conversation to collaborators Feb 15, 2022

		}


		bool MemPoolAccept::AcceptMultipleTransactions(std::list<CTransactionRef> tx_list, ATMPArgs& args)

Add package acceptance logic to mempool #16401

Add package acceptance logic to mempool #16401

Uh oh!

Conversation

Uh oh!

Uh oh!

Uh oh!

Conflicts

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

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!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

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!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

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!

Choose a reason for hiding this comment

Uh oh!

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!

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!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!