validate package transactions with their in-package ancestor sets #26711

This contains everything to make mempool/validation logic ready for package relay (see #27463).

Design goals:

• Be able to gracefully deal with any arbitrary list of transactions (these come from p2p)
• Validate any ancestor package so that the incentive-compatible transactions end up in our mempool.
  • If the transactions would be accepted individually, they should also be accepted through AcceptPackage. We don’t want to accidentally reject things just because we happened to download them as a package.
  • Bug prior to these changes: we required IsChildWithParents but if there were dependencies between the parents, we could end up (1) accepting a low-feerate child or (2) rejecting a high-feerate parent CPFPing another parent. See the “interdependent parents” test case for a specific example.
• Be DoS-resistant.
  • Avoid quadratic validation costs.
  • Avoid loading a lot of stuff from disk, or loading repeatedly.

There are 2 main improvements to package evaluation here: (1) We submit transactions with their in-package ancestor sets. - See unit test package_ppfp: without this change, we would reject everything. - See unit test package_ppfc: shows that this doesn’t let us do “parent pays for child;” we only do this when the individual and ancestor feerates meet mempool minimum feerate (2) We linearize the package transactions based on ancestor set scoring. - See unit test package_needs_reorder: without this change, if we use the original order of transactions, we would only accept 1 grandparent, even if we submit subpackages. - See unit test package_desc_limits: without this change, we accept one of the lower-feerate transactions (a bit more of a “nice to have” than a “must have” example).

A description of the package validation logic (originally #26711 (comment)):

• Basic sanitization. Quit if it’s too big, inconsistent, etc.
• Linearize (Topological sort only)
• PreChecks loop For each tx, grab UTXOs to calculate fees and filter out anything we should skip:
  • If already in mempool (or same txid in mempool), mark as skip
  • If missing inputs or conflict, record this failure and mark this and all descendants as skip.
  • If no failures or TX_SINGLE_FAILURE, continue
  • For some failures that we expect due to differing chainstates, skip these transactions and their descendants, but continue.
  • Otherwise, record this failure and mark that we will quit_early (i.e. not do the Subpackage validation loop).
• Refine our linearization using the fee information.
• Subpackage validation loop For each transaction in the new linearized order:
  • Get the transaction’s ancestor subpackage.
  • If the feerate of this transaction is insufficient, continue;
  • If the feerate of this subpackage is insufficient, continue;
  • Otherwise, try to submit the subpackage, using AcceptSingleTransaction() if it’s just 1 tx
  • if at any point we get a non-fee-related error, abort all.
• Call LimitMempoolSize
• Backfill results:
  • If the transaction was in mempool, check to see if it’s still there in case it was trimmed in LimitMempoolSize.
  • Try to use results from the subpackage validation loop.
  • If that doesn’t exist (i.e. we quit early), use results from prechecks loop.
  • If that doesn’t exist (i.e. we quit early and we hadn’t found a failure with it yet), fill with TX_UNKNOWN.

This means we will call PreChecks for each transaction 2 times (fewer if we quit early), and run all other validation checks at most 1 time. A transaction shouldn’t be validated in the subpackage validation loop more than once.

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

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

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:

• #28813 (rpc: permit any ancestor package through submitpackage by glozow)
• #28690 (build: Introduce internal kernel library by TheCharlatan)
• #28455 (refactor: share and use GenerateRandomKey helper by theStack)
• #28391 (refactor: Simplify CTxMempool/BlockAssembler fields, remove some external mapTx access by TheCharlatan)

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.

Last bit of nitting:

AcceptPackage -> AcceptAncestorPackage AcceptMultipleTransactions -> AcceptSubPackage

With BIP331 I think maybe knowing what an ancestor package is and how it fits into this code may become clearer?

I am trying to get a feel for how big of a problem it is that this PR solves. In Lightning the problem is very real and potentially exposing lots of users to coin loss because of the combination of pre-signed transactions and time sensitivity, but the topology is of the simplest kind. I am not sure if the wallet example that you give is of the same order because RBF is also an option and timing may not be as critical?

Of course it is great to support as many patterns as possible, but it also makes the system more complex to reason about and maintain. Maybe #27609 takes away 90% of the pain at 10% of the cost?

ACK https://github.com/bitcoin/bitcoin/pull/26711/commits/b234f993da3caa16f7716948fbcd16ab1a500180

modulo magic numbers in tests (sorry). Ran the fuzzer for a while again, no issues this time.

I’ve discussed some of the concerns here with @instagibbs, though haven’t reviewed the code or read all the discussion.

As I understand it, there are (at least) these two issues to be addressed:

• If a package is received, but its overall feerate is too low, it may still be the case that there are acceptable subpackages (at the top of the graph) we would have liked to accept (and this could happen when e.g. we missed the initial announcement of those subpackages). This is a regression compared to the current non-package relay, as orphan handling may resolve such cases today, though it’s not clear to me how serious this is.
• It’s also possible that the feerate of the overall package is sufficient to be accepted, but it contains a low-feerate subset (at the “bottom” of the graph) that is actually too low, and we would ideally avoid accepting (possibly while still accepting the rest), to avoid cases where low feerate stuff makes it into our mempool (accidentally or maliciously) through the package relay mechanism.

My belief is that the second problem, deciding whether a low-feerate subset exists in a package, is actually equivalent to the cluster linearization/chunking problem (see #27677). A special case is a single leaf transaction in the package that’s low-fee, but the more general question is much harder.

If the “accepting low-fee stuff” is considered a problem (as it appears to be, as you’re trying to detect it for the last transaction in the package), then my thinking is that we actually may want to address it through a cluster linearization lens (independent of actually making the mempool cluster-based):

• Run some linearization algorithm on the received package (it may be a very dumb one, like just sorting topologically, or the ancestor set feerate based one that the current mempool mining logic is using, or possibly later a much more intelligent one). Given that you’re inherently limited to (I think) 25 transaction packages anyway, this ought to be very fast, even for ancestor sets). I’m happy to provide code to do this (I’ve been working on this problem the past few weeks anyway). The smarter the linearization is, the more capable it’ll be at detecting sneaking-in, but even dumb topological sort is sufficient to detect the “single last bad transaction” case.
• Run chunking on the linearization. This is a very simple O(n) algorithm that partitions the linearization into chunks, with the property that the combined feerate of the transactions in each consecutive chunk goes down.
• Consider feerate checks of mempool insertion for every chunk separately, and abort as soon as one fails (possibly keeping the previous chunks, if that’s easily doable). Given that chunk feerates are monotonously decreasing, if one fails for feerate reasons, the later ones will fail too.

This approach does not deal well with (transient) failures for non-feerate reasons, because if some transactions fails checks, if you’ve already linearized, everything after it may possibly depend on the failing one. It’s possible in that case to go back and relinearize, but perhaps it’s okay to just give up then?

As I understand it, there are (at least) these two issues to be addressed:

Yes, essentially “the package contains valid transactions, but we should only accept a subset of it due to fees.” The first one can happen normally if we just came out of IBD or our peer has a lower minfeerate than we do - this PR was initially to address that. It was also to address “the package contains some invalid transactions, and we should take the subset that is valid” but I now think of that as a distinct concern.

For the second, I believe the worst concerns are due to problems with eviction (i.e. fixed with cluster mempool). But it’s also such a waste to validate, accept, and potentially relay them, so I think we should try to reject it as soon as possible.

Most problems with this PR boil down to how it groups transactions together (each time, just take the not-yet-submitted ancestor set of each tx). It’s not smart enough to, for example, find a parent+2children group since every grouping is ancestor set-shaped. It also seems that its retry attempts (specifically the O(n^2) PreChecks) are a dealbreaker, so being able to decide on groups earlier is important.

My belief is that the second problem, deciding whether a low-feerate subset exists in a package, is actually equivalent to the cluster linearization/chunking problem

Yes! I think using ancestor feerate linearization + chunking method would be a much better way to divide the package into subgroups before validation. I also spent some time whiteboarding whether package RBF could be feasible for non-v3 this way. I haven’t found anything I’m happy with yet, but I think incorporating “cost to RBF conflicts” into the chunking algorithm could be a start.

One thing I want to preserve from the current approach is minimizing groups when we can. For example, when the “top” of the package is above minimum feerate, we’ll try it by itself before grouping. One goal of that is to prevent any potential regression from legacy orphan handling. Another problem is around granularity of checking ancestor/descendant limits: imagine a diamond shape (grandparent, 2 parents, 1 child) where grandparent has 23 in-mempool ancestors. The child won’t make it regardless of fee, since it would have 26 ancestors. So if it’s not necessary to chunk all 4 together (i.e. no need to CPFP), we shouldn’t. [1]

So I think we’d want to use the linearization/chunking algo, but favor smaller chunks whenever possible. And preserve the behavior where, when every transaction’s feerate is above our minimums, we just call AcceptSingleTransaction on each one. This also allows RBF.

This approach does not deal well with (transient) failures for non-feerate reasons, because if some transactions fails checks, if you’ve already linearized, everything after it may possibly depend on the failing one. It’s possible in that case to go back and relinearize, but perhaps it’s okay to just give up then?

I still believe the answer to this is to give up and ensure we do not block an honest peer from relaying it to us later. If a peer is stuffing invalid transactions into a package, we don’t waste any time and imo it’s reasonable to wait for an honest peer to send the real package to us.

I’ve been wondering if we should still try the transactions that are not descendants of the transaction(s) that failed. It seems a shame to just skip validation for a transaction we downloaded and has no dependencies on things we deemed invalid. But this does leave room for weird behavior… for example, we can only take 1 of 2 transactions before hitting descendant limits, so stuffing the package with high-feerate invalid txns can make us accept the lower-feerate one first if we don’t re-linearize after we see the invalid tx. One idea is, when something is invalid for non-fee reasons, we skip its descendants but do a re-linearization that’s topo-only and randomly tie-broken for everything else? But maybe this is unrealistic and not worth thinking about.

Anyway, to summarize, the approach I’m going with now is:

1. Basic sanitization. Topological sort.
2. Grab UTXOs and calculate fees. Deduplicate txns already in mempool or seemingly just-confirmed. Drop things with missing inputs.
3. Refine our linearization using the fee information.
4. If each transaction passes CheckFeeRate by themselves, just call AcceptSingleTransaction(tx) for each tx -> return
5. Chunkify, favoring smaller chunks (i.e. don’t chunk together if possible)
6. For each chunk, AcceptPackageWrappingSingle(chunk) -> return

Will see what can be borrowed from the cluster mempool code - thanks!!

[1] Similarly, since PackageMempoolChecks would overestimate each parent’s ancestor count the way it’s currently implemented (it was written with the assumption that inputs would be tx + ancestors), we should be willing to take one parent and not the other.

One goal of that is to prevent any potential regression from legacy orphan handling

Sorry can you motivate the issue here explicitly? How would this issue not arise in cluster mempool world?

favoring smaller chunks over larger ones.

I think it’d be good to be explicit what “favoring” means here. Is this just individual submissions, then the full chunk on the rest of the chunk on an individual failure?

Refine our linearization using the fee information.

Any thoughts on what algo here? IIUC Pieter should have ancestor-set rate code ready to go so maybe that could be used as good enough for mvp.

I also spent some time whiteboarding whether package RBF could be feasible for non-v3 this way. I haven’t found anything I’m happy with yet, but I think incorporating “cost to RBF conflicts” into the chunking algorithm could be a start.

I haven’t thought hard about this, but package RBF sounds a whole lot more complex - and that’s probably something that actually becomes easier to reason about in a post-clustermempool world.

One thing I want to preserve from the current approach is minimizing groups when we can. For example, when the “top” of the package is above minimum feerate, we’ll try it by itself before grouping. One goal of that is to prevent any potential regression from legacy orphan handling. Another problem is around granularity of checking ancestor/descendant limits: imagine a diamond shape (grandparent, 2 parents, 1 child) where grandparent has 23 in-mempool ancestors. The child won’t make it regardless of fee, since it would have 26 ancestors. So if it’s not necessary to chunk all 4 together (i.e. no need to CPFP), we shouldn’t. [1]

Interesting; ancestor set size limits do complicate things, and do factor into this. Ideally, I think the linearization and chunking just take these limits (including those impacted by existing in-mempool transactions) into account, but that’s a lot less trivial. However, for specifically this concern a possibility is just weeding out transactions from the package whose ancestor set size would exceed the limit, before even invoking linearization, because ancestor set size of a transaction is a static property that does not depend on whatever else may be included. They can be ignored, as they’re never going to be acceptable, so they shouldn’t affect the order of other things that can be. It may be an independently useful optimization.

So I think we’d want to use the linearization/chunking algo, but favor smaller chunks whenever possible. And preserve the behavior where, when every transaction’s feerate is above our minimums, we just call AcceptSingleTransaction on each one. This also allows RBF.

About minimizing groupings in general, you’re right. Chunking (as I had in mind) is actually too aggressive, and it’s better to only group things as necessary. I don’t think you need to special case individual transactions even, actually. Instead, use this, instead of chunking:

• Start with an empty group of transactions to process.
• Go through the transactions in linearized order, one by one:
  • Add transaction to the group of transactions to process.
  • Compute the combined feerate of that group (total fees divided by total size).
    • If that feerate is sufficiently high, process the transactions in the group, and clear the group.
    • If that feerate is not high enough, just leave the transaction in the group and continue with the next one.
• If the final group is above the acceptable rate, process it. If not, discard it.

This will, I think, in most cases just process the transactions one by one, once. Only situations like a CPFP of which the parent alone isn’t sufficient will trigger a grouped validation.

I still believe the answer to this is to give up and ensure we do not block an honest peer from relaying it to us later. If a peer is stuffing invalid transactions into a package, we don’t waste any time and imo it’s reasonable to wait for an honest peer to send the real package to us.

I agree. The goal isn’t to make sure that all imaginable unacceptable packages with some acceptable subpackage get considered. If the peer is sending bad things, we’re allowed to just give up, as long as we make sure that in honest situations it’s recoverable.

Anyway, to summarize, the approach I’m going with now is:

…

I’d modify step 4-6 to instead use the lazy grouping I described above, and use single transaction processing whenever the group happens to be a single transaction.

I don’t think you need to special case individual transactions even, actually. Instead, use this, instead of chunking:

I’m not sure about using a group’s aggregate feerate without checking their spending relationships, as it may allow unrelated transactions to pay for each other. For example:

0A(1)  B(3)
1   ^   ^ 
2  C(100)

Where minfeerate is 2sat/vB. Imagine C is invalid (e.g. a fake child created to connect A and B). The ancestor score-based linearization I was imagining (i.e. the current BlockAssembler algorithm) would be selecting them as part of C’s ancestor set, so the result could be ABC or BAC. If the linearization is ABC: A is below feerate, but A+B is ok. We’ve allowed B to “pay for” A but they’re unrelated. If the linearization is BAC we’re fine.

I think whatever linearization is given out, we should probably ensure that each remaining prefix of the ancestor package is an ancestor package itself, before attempting submission to the mempool. Skip the entry if it’s not.

We could do lazy grouping but only try groups that are connected (e.g. n-parents-1-child or 1-parent-2-children, etc)? Requiring them to be ancestor set-shaped would miss e.g. the 1-parent-2-children case.

Maybe we can linearize the selected ancestor sets themselves to guarantee that, in this kind of situation, we’d always look at B before A? I think that would address the “only one can fit in package limits” problem as well.

Nothing is perfect, but a linearizer would ideally pick B before A, yes. So you might get:

B, A, C or B, C, A

depending on if the strategy is greedy. “topo” sort may miss this, which is why we should probably be smarter than that?

@glozow You’re right; I didn’t think this through. @instagibbs To a limited extent better linearization can help here (though within-chunk optimization isn’t something I’ve been looking at, as it doesn’t matter for mining/eviction) but I think you can construct more complex examples where even a “perfect” linearization results in grouping of things that should not pay for each other.

I’m starting to think that something closer to your idea here is right: trying ancestor sets of every transaction in the linearization in order, if the ancestor set feerate is suffiicently high. This indeed won’t deal with multiple-children-pay-for-parent cases perfectly, but including everything connected may be too much as well. I’ll try to think about this more.

I’m starting to think that something closer to your idea here is right: trying ancestor sets of every transaction in the linearization in order, if the ancestor set feerate is suffiicently high. This indeed won’t deal with multiple-children-pay-for-parent cases perfectly, but including everything connected may be too much as well. I’ll try to think about this more.

I don’t think handling multiple-children-pay-for-parent cases perfectly should be a goal here – we’re not fixing eviction (or changing the mining algo) at this point, so we’ll still have imperfect corner cases anyway. Just getting “high feerate child pays for below minfee ancestors” mostly working, without introducing a DoS or breaking existing functional tx patterns, should be enough of a win IMO.

@ajtowns Yes, I don’t think we have any requirement or even strong desire to go beyond ancestor-set-based linearization quality (= sufficient for single child pay for parent) in general, so anything beyond that would be “extra”. Just trying ancestor sets of consecutive linearization elements (whenever their joint feerate is high enough) sounds sufficient to me, but I’m still wondering about:

• whether something simpler is possible that’s equally good.
• whether there is a more general way to think about this - imagine we have access to an optimal linearization algorithm, is there are tractable optimal solution to this problem too? If so, that may inform how to think about this.

I’m starting to think that something closer to your idea here is right: trying ancestor sets of every transaction in the linearization in order, if the ancestor set feerate is suffiicently high. This indeed won’t deal with multiple-children-pay-for-parent cases perfectly, but including everything connected may be too much as well.

I don’t think handling multiple-children-pay-for-parent cases perfectly should be a goal here

I agree that the non-ancestor-set-shaped submission is not something we should try to do right now.

Outline of approach I’ve just pushed (lmk what y’all think?):

• Basic sanitization. Linearize (Topological sort only)
• PreChecks loop For each tx, grab UTXOs to calculate fees and filter out anything we should skip:
  • If already in mempool (or same txid in mempool), mark as skip
  • If missing inputs or conflict [2], record this failure and mark this and all descendants as skip.
  • If no failures or TX_SINGLE_FAILURE [3], continue
  • Otherwise, record this failure and mark that we will quit_early.
• Refine our linearization using the fee information [4]
• Subpackage validation loop For each transaction in the new linearized order:
  • Get the transaction’s ancestor subpackage.
  • If the feerate of this transaction is insufficient, continue; [5]
  • If the feerate of this subpackage is insufficient, continue;
  • Otherwise, try to submit the subpackage, using AcceptSingleTransaction() if it’s just 1 tx [6]
  • if at any point we get a non-fee-related error, abort all.
• Backfill results:
  • Try to use results from the subpackage validation loop.
  • If that doesn’t exist (i.e. we quit early), use results from prechecks loop.
  • If that doesn’t exist (i.e. it depends on something missing inputs), fill with TX_UNKNOWN.

This means we will call PreChecks for each transaction 2 times (fewer if we quit early), and run all other validation checks at most 1 time. A transaction shouldn’t be validated in the subpackage validation loop more than once. Note that UTXOs are cached in m_view so there is not repeated loading the second time we call PreChecks.

[1] I’m using PreChecks for this in order to keep the anti-DoS fail-fast checks. These checks are very cheap and I don’t think we should skip them before loading UTXOs. For example, something larger than max standard size could cause us to load a lot of UTXOs. But we could discuss using something more minimal than PreChecks. I also think the things done in PreChecks() like calculating ancestors and in-mempool conflicts can be used to refine some of the logic. For example, we could quickly see that a tx conflicts with something it can’t replace and skip it. [2] i.e. TX_MISSING_INPUTS or TX_CONFLICT. This includes missing inputs and txn-already-known (something we guess is already confirmed). I special case’d these as something we should be more tolerant of (i.e. skip instead of abort) because I can imagine them happening in honest cases when we have a different chainstate from our peer, and it’s fairly easy to skip over them. [3] This includes fee-related errors, but only the ones that can be bypassed by package validation. Unless we remove the rule from #26933, something below min relay feerate would not fall in this category. And since we have no package RBF, not meeting fee-related RBF requirements is not in this category. I’ve documented these in the code. [4] I’m using a slightly modified MiniMiner here to get the order in which these transactions would be mined. It does not pull the mempool ancestors/cluster since there is no limit to how large that cluster might be. [5] This naturally resolves the “package feerate is ok but the bottom tx isn’t” issue. [6] Rationale #26711 (comment)