rpc: permit any ancestor package through submitpackage

glozow commented at 2:20 pm on November 7, 2023: member

After #26711, validation should be able to handle any ancestor package properly. We can remove the child-with-unconfirmed-parents restriction and the IsTree restriction.

In draft while #26711 is still open.

[refactor] use Wtxid for m_wtxids_fee_calculations 5c786a026a

[validation] add TxValidationResult::TX_RECONSIDERABLE, TX_UNKNOWN

With package validation rules, transactions that fail individually may
sometimes be eligible for reconsideration if submitted as part of a
(different) package. For now, that includes trasactions that failed for
being too low feerate.  Add a new TxValidationResult type to distinguish
these failures from others.  In the next commits, we will abort package
validation if a tx fails for any other reason. In the future, we will
also decide whether to cache failures in recent_rejects based on this
result (we won't want to reject a package containing a transaction that
was rejected previously for being low feerate).

Package validation also sometimes elects to skip some transactions when
it knows the package will not be submitted in order to quit sooner. Add
a result to specify this situation; we also don't want to cache these
as rejections.

3979f1afcb

[test] use CheckPackageMempoolAcceptResult in previous tests

Increases test coverage (check every result field) and makes it easier
to test the changes in the next commit.

10dd9f2441

[validation] change package-fee-too-low, return wtxid(s) and effective feerate

With subpackage evaluation and de-duplication, it's not always the
entire package that is used in CheckFeerate. To be more helpful to the
caller, specify which transactions were included in the evaluation and
what the feerate was.

Instead of PCKG_POLICY (which is supposed to be for package-wide
errors), use PCKG_TX.

1147e00e59

[txpackages] add AncestorPackage for linearizing packages

We cannot require that peers send topologically sorted lists, because we
cannot check for this property without ensuring we have the same chain
tip and ensuring we have the full ancestor set. Instead, add the ability
to handle arbitrarily ordered transaction lists.
The AncestorPackage ctor linearizes the transactions topologically. If
fee and vsize information is added, it uses MiniMiner to refine the
linearization using the ancestor score-based algorithm.

2bef0ef036

[unit test] AncestorPackage 81833d8848

[bench] AncestorPackage and linearization using fees 0b5041600d

[fuzz] AncestorPackage topological sorting and skipping 099200fb2f

[refactor] AcceptPackage loop using AncestorPackage and switch statement

Adds usage of AncestorPackage to linearize transactions and skip ones
that are submitted or already in mempool. This linearization is just
topological for now, but a subsequent commit will add logic to gather
fee information and use that to refine the linearization. Even though
packages are currently required to be sorted, the order may be changed,
since AncestorPackage can produce a different but valid topological
sort.

Use a switch statement to ensure we are handling all possible
TxValidationResults. Also simplifies the diff of later commits.

53558aa011

[validation] linearize using fees + submit ancestor subpackages

General algorithm:
1. Basic sanitization to ensure package is well formed and not too big
   to work on.
2. Linearize (based on topological sort).
3. PreChecks loop: call PreChecks on all transactions to get fees and
   vsizes, and to find obvious errors for which we should skip parts of
   the package or abort validation altogether.
4. Linearize (based on ancestor set score).
5. For each transaction in the new linearized order, submit with its
   subpackage (or skip if subpackage/individual feerate is too low).
6. Limit mempool size and backfill map of MempoolAcceptResults.

Q: What's so great about doing a fee-based linearization?
Linearization helps us understand which transactions need to be grouped
together as CPFPs. This helps us skip the low feerate parent and wait
until we see it in the high feerate child's ancestor package; another
approach would be to retry submission with another grouping, but we want
to avoid repeated validation. Linearization also helps us try to accept
the highest feerate subset of the package when we don't don't have room
for all of it. For example, if each of the transactions in the package
share an ancestor whose descendant limits only permit one, we should try
the highest feerate transaction(s) first.

Q: Why use PreChecks to get fees and vsize?
We need the fee and vsize of each transaction, which requires looking up
inputs. While some of the work done in PreChecks might not be necessary,
it applies fail-fast anti-DoS checks that we definitely want (e.g. a
transaction that is too big could thus cause us to load too many UTXOs).
In the future, we may also be interested in using information like the
transaction's mempool conflicts and ancestor set (calculated in
PreChecks) in the linearization or quit early logic. So PreChecks is
best for this purpose.

Q: We don't know if txns have valid signatures yet, so if something is
invalid, we might have a suboptimal linearization/grouping. Should we
regroup or retry in that case?
No. If the peer maliciously constructs a package this way, there isn't
much we can do to find the "optimal subset" without doing a ton of work.
Generally, we hope to only validate each transaction 1 time.
Instead, we just hope we have another honest peer that will send us the
"normal" package.

d9e8b967ab

[unit test] subpackage evaluation and package linearization

- package_ppfp shows benefit of assessing subpackages
- 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
- package_needs_reorder shows necessity of linearizing using ancestor
  set scoring. If we used the original order, we would reject
everything, even if we submit subpackages.
- package_desc_limits shows that linearization can help us pick the
  most incentive-compatible tx to accept when transactions affect each
other's eligibility (descendant package limits)
- package_confirmed_parent shows benefit of treating
  txns-already-known as "in mempool" tx
- package_with_rbf tests existing behavior that shouldn't change. Even
  though package RBF is not enabled, it's important that submitting a
transaction as part of a package does not block it from doing a normal
replacement. Otherwise we may blind ourselves to a replacement simply
because it has a child and we happened to download it as a package.

Co-authored-by: Andrew Chow <achow101@gmail.com>

22c073bae3

[rpc] permit any ancestor package, not just child-with-unconfirmed-parents

We can safely allow any ancestor package since AncestorPackage can
linearize and group things into ancestor subsets. Remove the check that
"all unconfirmed parents are present" because, even if a tx is missing
inputs, the other transactions may be worth validating.

254dccb8f2

delete unused IsChildWithParents* functions 4f693b3ed6

glozow added the label RPC/REST/ZMQ on Nov 7, 2023

DrahtBot commented at 2:20 pm on November 7, 2023: contributor

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. A summary of reviews will appear here.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#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)
#26711 (validate package transactions with their in-package ancestor sets by glozow)

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 closed this on Nov 10, 2023

rpc: permit any ancestor package through submitpackage #28813

Code Coverage

Reviews

Conflicts