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

046e8ff264be6b888c0f9a9d822e32aa74e19b78 [unit test] package submission (glozow)
e12fafda2dfbbdf63f125e5af797ecfaa6488f66 [validation] de-duplicate package transactions already in mempool (glozow)
8310d942e046c5a9b6bd90afdcd3af68dd91e081 [packages] add sanity checks for package vs mempool limits (glozow)
be3ff151a1f9665720cdf70d072b098a2f9726a9 [validation] full package accept + mempool submission (glozow)
144a29099a865ac1dc3e5291d9529fbcca9c83a4 [policy] require submitted packages to be child-with-unconfirmed-parents (glozow)
d59ddc5c3d1c035474d7bc9fa9f8a0eeb1c8498c [packages/doc] define and document package rules (glozow)
ba26169f6035c238378a3c9647213328a006fa23 [unit test] context-free package checks (glozow)
9b2fdca7f03911ac40fe0f8a0b5da534bee4554b [packages] add static IsChildWithParents function (glozow)

Pull request description:

  This is 1 chunk of [Package Mempool Accept](https://gist.github.com/glozow/dc4e9d5c5b14ade7cdfac40f43adb18a); it restricts packages to 1 child with its parents, doesn't allow conflicts, and doesn't have CPFP (yet).  Future PRs (see #22290) will add RBF and CPFP within packages.

ACKs for top commit:
  laanwj:
    Code review ACK 046e8ff264be6b888c0f9a9d822e32aa74e19b78

Tree-SHA512: 37dbba37d527712f8efef71ee05c90a8308992615af35f5e0cfeafc60d859cc792737d125aac526e37742fe7683ac8c155ac24af562426213904333c01260c95

9 files changed, 567 insertions, 21 deletions

diff --git a/doc/README.md b/doc/README.md
index f737fd8a86..2800937d30 100644
--- a/doc/README.md
+++ b/doc/README.md
@@ -83,6 +83,7 @@ The Bitcoin repo's [root README](/README.md) contains relevant information on th
 - [Reduce Memory](reduce-memory.md)
 - [Reduce Traffic](reduce-traffic.md)
 - [Tor Support](tor.md)
+- [Transaction Relay Policy](policy/README.md)
 - [ZMQ](zmq.md)
 
 License
diff --git a/doc/policy/README.md b/doc/policy/README.md
new file mode 100644
index 0000000000..9c83f4b56e
--- /dev/null
+++ b/doc/policy/README.md
@@ -0,0 +1,10 @@
+# Transaction Relay Policy
+
+Policy is a set of validation rules, in addition to consensus, enforced for unconfirmed
+transactions.
+
+This documentation is not an exhaustive list of all policy rules.
+
+- [Packages](packages.md)
+
+
diff --git a/doc/policy/packages.md b/doc/policy/packages.md
new file mode 100644
index 0000000000..07698f2af2
--- /dev/null
+++ b/doc/policy/packages.md
@@ -0,0 +1,59 @@
+# Package Mempool Accept
+
+## Definitions
+
+A **package** is an ordered list of transactions, representable by a connected Directed Acyclic
+Graph (a directed edge exists between a transaction that spends the output of another transaction).
+
+For every transaction `t` in a **topologically sorted** package, if any of its parents are present
+in the package, they appear somewhere in the list before `t`.
+
+A **child-with-unconfirmed-parents** package is a topologically sorted package that consists of
+exactly one child and all of its unconfirmed parents (no other transactions may be present).
+The last transaction in the package is the child, and its package can be canonically defined based
+on the current state: each of its inputs must be available in the UTXO set as of the current chain
+tip or some preceding transaction in the package.
+
+## Package Mempool Acceptance Rules
+
+The following rules are enforced for all packages:
+
+* Packages cannot exceed `MAX_PACKAGE_COUNT=25` count and `MAX_PACKAGE_SIZE=101KvB` total size
+   (#20833)
+
+   - *Rationale*: This is already enforced as mempool ancestor/descendant limits. If
+     transactions in a package are all related, exceeding this limit would mean that the package
+     can either be split up or it wouldn't pass individual mempool policy.
+
+   - Note that, if these mempool limits change, package limits should be reconsidered. Users may
+     also configure their mempool limits differently.
+
+* Packages must be topologically sorted. (#20833)
+
+* Packages cannot have conflicting transactions, i.e. no two transactions in a package can spend
+   the same inputs. Packages cannot have duplicate transactions. (#20833)
+
+* No transaction in a package can conflict with a mempool transaction. BIP125 Replace By Fee is
+  currently disabled for packages. (#20833)
+
+   - Package RBF may be enabled in the future.
+
+* When packages are evaluated against ancestor/descendant limits, the union of all transactions'
+  descendants and ancestors is considered. (#21800)
+
+   - *Rationale*: This is essentially a "worst case" heuristic intended for packages that are
+     heavily connected, i.e. some transaction in the package is the ancestor or descendant of all
+     the other transactions.
+
+The following rules are only enforced for packages to be submitted to the mempool (not enforced for
+test accepts):
+
+* Packages must be child-with-unconfirmed-parents packages. This also means packages must contain at
+  least 2 transactions. (#22674)
+
+   - *Rationale*: This allows for fee-bumping by CPFP. Allowing multiple parents makes it possible
+     to fee-bump a batch of transactions. Restricting packages to a defined topology is easier to
+     reason about and simplifies the validation logic greatly.
+
+   - Warning: Batched fee-bumping may be unsafe for some use cases. Users and application developers
+     should take caution if utilizing multi-parent packages.
diff --git a/src/policy/packages.cpp b/src/policy/packages.cpp
index cfd0539965..21f5488816 100644
--- a/src/policy/packages.cpp
+++ b/src/policy/packages.cpp
@@ -60,3 +60,20 @@ bool CheckPackage(const Package& txns, PackageValidationState& state)
     }
     return true;
 }
+
+bool IsChildWithParents(const Package& package)
+{
+    assert(std::all_of(package.cbegin(), package.cend(), [](const auto& tx){return tx != nullptr;}));
+    if (package.size() < 2) return false;
+
+    // The package is expected to be sorted, so the last transaction is the child.
+    const auto& child = package.back();
+    std::unordered_set<uint256, SaltedTxidHasher> input_txids;
+    std::transform(child->vin.cbegin(), child->vin.cend(),
+                   std::inserter(input_txids, input_txids.end()),
+                   [](const auto& input) { return input.prevout.hash; });
+
+    // Every transaction must be a parent of the last transaction in the package.
+    return std::all_of(package.cbegin(), package.cend() - 1,
+                       [&input_txids](const auto& ptx) { return input_txids.count(ptx->GetHash()) > 0; });
+}
diff --git a/src/policy/packages.h b/src/policy/packages.h
index 6b7ac3e450..d2744f1265 100644
--- a/src/policy/packages.h
+++ b/src/policy/packages.h
@@ -41,4 +41,10 @@ class PackageValidationState : public ValidationState<PackageValidationResult> {
  */
 bool CheckPackage(const Package& txns, PackageValidationState& state);
 
+/** Context-free check that a package is exactly one child and its parents; not all parents need to
+ * be present, but the package must not contain any transactions that are not the child's parents.
+ * It is expected to be sorted, which means the last transaction must be the child.
+ */
+bool IsChildWithParents(const Package& package);
+
 #endif // BITCOIN_POLICY_PACKAGES_H
diff --git a/src/rpc/rawtransaction.cpp b/src/rpc/rawtransaction.cpp
index f2e8104e14..9be5c82311 100644
--- a/src/rpc/rawtransaction.cpp
+++ b/src/rpc/rawtransaction.cpp
@@ -1028,6 +1028,8 @@ static RPCHelpMan testmempoolaccept()
             continue;
         }
         const auto& tx_result = it->second;
+        // Package testmempoolaccept doesn't allow transactions to already be in the mempool.
+        CHECK_NONFATAL(tx_result.m_result_type != MempoolAcceptResult::ResultType::MEMPOOL_ENTRY);
         if (tx_result.m_result_type == MempoolAcceptResult::ResultType::VALID) {
             const CAmount fee = tx_result.m_base_fees.value();
             // Check that fee does not exceed maximum fee
diff --git a/src/test/txpackage_tests.cpp b/src/test/txpackage_tests.cpp
index 2193e21780..6f78b43826 100644
--- a/src/test/txpackage_tests.cpp
+++ b/src/test/txpackage_tests.cpp
@@ -114,4 +114,217 @@ BOOST_FIXTURE_TEST_CASE(package_validation_tests, TestChain100Setup)
     // Check that mempool size hasn't changed.
     BOOST_CHECK_EQUAL(m_node.mempool->size(), initialPoolSize);
 }
+
+BOOST_FIXTURE_TEST_CASE(noncontextual_package_tests, TestChain100Setup)
+{
+    // The signatures won't be verified so we can just use a placeholder
+    CKey placeholder_key;
+    placeholder_key.MakeNewKey(true);
+    CScript spk = GetScriptForDestination(PKHash(placeholder_key.GetPubKey()));
+    CKey placeholder_key_2;
+    placeholder_key_2.MakeNewKey(true);
+    CScript spk2 = GetScriptForDestination(PKHash(placeholder_key_2.GetPubKey()));
+
+    // Parent and Child Package
+    {
+        auto mtx_parent = CreateValidMempoolTransaction(m_coinbase_txns[0], 0, 0, coinbaseKey, spk,
+                                                        CAmount(49 * COIN), /* submit */ false);
+        CTransactionRef tx_parent = MakeTransactionRef(mtx_parent);
+
+        auto mtx_child = CreateValidMempoolTransaction(tx_parent, 0, 101, placeholder_key, spk2,
+                                                       CAmount(48 * COIN), /* submit */ false);
+        CTransactionRef tx_child = MakeTransactionRef(mtx_child);
+
+        PackageValidationState state;
+        BOOST_CHECK(CheckPackage({tx_parent, tx_child}, state));
+        BOOST_CHECK(!CheckPackage({tx_child, tx_parent}, state));
+        BOOST_CHECK_EQUAL(state.GetResult(), PackageValidationResult::PCKG_POLICY);
+        BOOST_CHECK_EQUAL(state.GetRejectReason(), "package-not-sorted");
+        BOOST_CHECK(IsChildWithParents({tx_parent, tx_child}));
+    }
+
+    // 24 Parents and 1 Child
+    {
+        Package package;
+        CMutableTransaction child;
+        for (int i{0}; i < 24; ++i) {
+            auto parent = MakeTransactionRef(CreateValidMempoolTransaction(m_coinbase_txns[i + 1],
+                                             0, 0, coinbaseKey, spk, CAmount(48 * COIN), false));
+            package.emplace_back(parent);
+            child.vin.push_back(CTxIn(COutPoint(parent->GetHash(), 0)));
+        }
+        child.vout.push_back(CTxOut(47 * COIN, spk2));
+
+        // The child must be in the package.
+        BOOST_CHECK(!IsChildWithParents(package));
+
+        // The parents can be in any order.
+        FastRandomContext rng;
+        Shuffle(package.begin(), package.end(), rng);
+        package.push_back(MakeTransactionRef(child));
+
+        PackageValidationState state;
+        BOOST_CHECK(CheckPackage(package, state));
+        BOOST_CHECK(IsChildWithParents(package));
+
+        package.erase(package.begin());
+        BOOST_CHECK(IsChildWithParents(package));
+
+        // The package cannot have unrelated transactions.
+        package.insert(package.begin(), m_coinbase_txns[0]);
+        BOOST_CHECK(!IsChildWithParents(package));
+    }
+
+    // 2 Parents and 1 Child where one parent depends on the other.
+    {
+        CMutableTransaction mtx_parent;
+        mtx_parent.vin.push_back(CTxIn(COutPoint(m_coinbase_txns[0]->GetHash(), 0)));
+        mtx_parent.vout.push_back(CTxOut(20 * COIN, spk));
+        mtx_parent.vout.push_back(CTxOut(20 * COIN, spk2));
+        CTransactionRef tx_parent = MakeTransactionRef(mtx_parent);
+
+        CMutableTransaction mtx_parent_also_child;
+        mtx_parent_also_child.vin.push_back(CTxIn(COutPoint(tx_parent->GetHash(), 0)));
+        mtx_parent_also_child.vout.push_back(CTxOut(20 * COIN, spk));
+        CTransactionRef tx_parent_also_child = MakeTransactionRef(mtx_parent_also_child);
+
+        CMutableTransaction mtx_child;
+        mtx_child.vin.push_back(CTxIn(COutPoint(tx_parent->GetHash(), 1)));
+        mtx_child.vin.push_back(CTxIn(COutPoint(tx_parent_also_child->GetHash(), 0)));
+        mtx_child.vout.push_back(CTxOut(39 * COIN, spk));
+        CTransactionRef tx_child = MakeTransactionRef(mtx_child);
+
+        PackageValidationState state;
+        BOOST_CHECK(IsChildWithParents({tx_parent, tx_parent_also_child}));
+        BOOST_CHECK(IsChildWithParents({tx_parent, tx_child}));
+        BOOST_CHECK(IsChildWithParents({tx_parent, tx_parent_also_child, tx_child}));
+        // IsChildWithParents does not detect unsorted parents.
+        BOOST_CHECK(IsChildWithParents({tx_parent_also_child, tx_parent, tx_child}));
+        BOOST_CHECK(CheckPackage({tx_parent, tx_parent_also_child, tx_child}, state));
+        BOOST_CHECK(!CheckPackage({tx_parent_also_child, tx_parent, tx_child}, state));
+        BOOST_CHECK_EQUAL(state.GetResult(), PackageValidationResult::PCKG_POLICY);
+        BOOST_CHECK_EQUAL(state.GetRejectReason(), "package-not-sorted");
+    }
+}
+
+BOOST_FIXTURE_TEST_CASE(package_submission_tests, TestChain100Setup)
+{
+    LOCK(cs_main);
+    unsigned int expected_pool_size = m_node.mempool->size();
+    CKey parent_key;
+    parent_key.MakeNewKey(true);
+    CScript parent_locking_script = GetScriptForDestination(PKHash(parent_key.GetPubKey()));
+
+    // Unrelated transactions are not allowed in package submission.
+    Package package_unrelated;
+    for (size_t i{0}; i < 10; ++i) {
+        auto mtx = CreateValidMempoolTransaction(/* input_transaction */ m_coinbase_txns[i + 25], /* vout */ 0,
+                                                 /* input_height */ 0, /* input_signing_key */ coinbaseKey,
+                                                 /* output_destination */ parent_locking_script,
+                                                 /* output_amount */ CAmount(49 * COIN), /* submit */ false);
+        package_unrelated.emplace_back(MakeTransactionRef(mtx));
+    }
+    auto result_unrelated_submit = ProcessNewPackage(m_node.chainman->ActiveChainstate(), *m_node.mempool,
+                                                     package_unrelated, /* test_accept */ false);
+    BOOST_CHECK(result_unrelated_submit.m_state.IsInvalid());
+    BOOST_CHECK_EQUAL(result_unrelated_submit.m_state.GetResult(), PackageValidationResult::PCKG_POLICY);
+    BOOST_CHECK_EQUAL(result_unrelated_submit.m_state.GetRejectReason(), "package-not-child-with-parents");
+    BOOST_CHECK_EQUAL(m_node.mempool->size(), expected_pool_size);
+
+    // Parent and Child (and Grandchild) Package
+    Package package_parent_child;
+    Package package_3gen;
+    auto mtx_parent = CreateValidMempoolTransaction(/* input_transaction */ m_coinbase_txns[0], /* vout */ 0,
+                                                    /* input_height */ 0, /* input_signing_key */ coinbaseKey,
+                                                    /* output_destination */ parent_locking_script,
+                                                    /* output_amount */ CAmount(49 * COIN), /* submit */ false);
+    CTransactionRef tx_parent = MakeTransactionRef(mtx_parent);
+    package_parent_child.push_back(tx_parent);
+    package_3gen.push_back(tx_parent);
+
+    CKey child_key;
+    child_key.MakeNewKey(true);
+    CScript child_locking_script = GetScriptForDestination(PKHash(child_key.GetPubKey()));
+    auto mtx_child = CreateValidMempoolTransaction(/* input_transaction */ tx_parent, /* vout */ 0,
+                                                   /* input_height */ 101, /* input_signing_key */ parent_key,
+                                                   /* output_destination */ child_locking_script,
+                                                   /* output_amount */ CAmount(48 * COIN), /* submit */ false);
+    CTransactionRef tx_child = MakeTransactionRef(mtx_child);
+    package_parent_child.push_back(tx_child);
+    package_3gen.push_back(tx_child);
+
+    CKey grandchild_key;
+    grandchild_key.MakeNewKey(true);
+    CScript grandchild_locking_script = GetScriptForDestination(PKHash(grandchild_key.GetPubKey()));
+    auto mtx_grandchild = CreateValidMempoolTransaction(/* input_transaction */ tx_child, /* vout */ 0,
+                                                       /* input_height */ 101, /* input_signing_key */ child_key,
+                                                       /* output_destination */ grandchild_locking_script,
+                                                       /* output_amount */ CAmount(47 * COIN), /* submit */ false);
+    CTransactionRef tx_grandchild = MakeTransactionRef(mtx_grandchild);
+    package_3gen.push_back(tx_grandchild);
+
+    // 3 Generations is not allowed.
+    {
+        auto result_3gen_submit = ProcessNewPackage(m_node.chainman->ActiveChainstate(), *m_node.mempool,
+                                                    package_3gen, /* test_accept */ false);
+        BOOST_CHECK(result_3gen_submit.m_state.IsInvalid());
+        BOOST_CHECK_EQUAL(result_3gen_submit.m_state.GetResult(), PackageValidationResult::PCKG_POLICY);
+        BOOST_CHECK_EQUAL(result_3gen_submit.m_state.GetRejectReason(), "package-not-child-with-parents");
+        BOOST_CHECK_EQUAL(m_node.mempool->size(), expected_pool_size);
+    }
+
+    // Child with missing parent.
+    mtx_child.vin.push_back(CTxIn(COutPoint(package_unrelated[0]->GetHash(), 0)));
+    Package package_missing_parent;
+    package_missing_parent.push_back(tx_parent);
+    package_missing_parent.push_back(MakeTransactionRef(mtx_child));
+    {
+        const auto result_missing_parent = ProcessNewPackage(m_node.chainman->ActiveChainstate(), *m_node.mempool,
+                                                             package_missing_parent, /* test_accept */ false);
+        BOOST_CHECK(result_missing_parent.m_state.IsInvalid());
+        BOOST_CHECK_EQUAL(result_missing_parent.m_state.GetResult(), PackageValidationResult::PCKG_POLICY);
+        BOOST_CHECK_EQUAL(result_missing_parent.m_state.GetRejectReason(), "package-not-child-with-unconfirmed-parents");
+        BOOST_CHECK_EQUAL(m_node.mempool->size(), expected_pool_size);
+
+    }
+
+    // Submit package with parent + child.
+    {
+        const auto submit_parent_child = ProcessNewPackage(m_node.chainman->ActiveChainstate(), *m_node.mempool,
+                                                           package_parent_child, /* test_accept */ false);
+        expected_pool_size += 2;
+        BOOST_CHECK_MESSAGE(submit_parent_child.m_state.IsValid(),
+                            "Package validation unexpectedly failed: " << submit_parent_child.m_state.GetRejectReason());
+        auto it_parent = submit_parent_child.m_tx_results.find(tx_parent->GetWitnessHash());
+        auto it_child = submit_parent_child.m_tx_results.find(tx_child->GetWitnessHash());
+        BOOST_CHECK(it_parent != submit_parent_child.m_tx_results.end());
+        BOOST_CHECK(it_parent->second.m_state.IsValid());
+        BOOST_CHECK(it_child != submit_parent_child.m_tx_results.end());
+        BOOST_CHECK(it_child->second.m_state.IsValid());
+
+        BOOST_CHECK_EQUAL(m_node.mempool->size(), expected_pool_size);
+        BOOST_CHECK(m_node.mempool->exists(GenTxid::Txid(tx_parent->GetHash())));
+        BOOST_CHECK(m_node.mempool->exists(GenTxid::Txid(tx_child->GetHash())));
+    }
+
+    // Already-in-mempool transactions should be detected and de-duplicated.
+    {
+        const auto submit_deduped = ProcessNewPackage(m_node.chainman->ActiveChainstate(), *m_node.mempool,
+                                                      package_parent_child, /* test_accept */ false);
+        BOOST_CHECK_MESSAGE(submit_deduped.m_state.IsValid(),
+                            "Package validation unexpectedly failed: " << submit_deduped.m_state.GetRejectReason());
+        auto it_parent_deduped = submit_deduped.m_tx_results.find(tx_parent->GetWitnessHash());
+        auto it_child_deduped = submit_deduped.m_tx_results.find(tx_child->GetWitnessHash());
+        BOOST_CHECK(it_parent_deduped != submit_deduped.m_tx_results.end());
+        BOOST_CHECK(it_parent_deduped->second.m_state.IsValid());
+        BOOST_CHECK(it_parent_deduped->second.m_result_type == MempoolAcceptResult::ResultType::MEMPOOL_ENTRY);
+        BOOST_CHECK(it_child_deduped != submit_deduped.m_tx_results.end());
+        BOOST_CHECK(it_child_deduped->second.m_state.IsValid());
+        BOOST_CHECK(it_child_deduped->second.m_result_type == MempoolAcceptResult::ResultType::MEMPOOL_ENTRY);
+
+        BOOST_CHECK_EQUAL(m_node.mempool->size(), expected_pool_size);
+        BOOST_CHECK(m_node.mempool->exists(GenTxid::Txid(tx_parent->GetHash())));
+        BOOST_CHECK(m_node.mempool->exists(GenTxid::Txid(tx_child->GetHash())));
+    }
+}
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/validation.cpp b/src/validation.cpp
index 1aac71fb0f..446c21e118 100644
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -465,6 +465,11 @@ public:
          * any transaction spending the same inputs as a transaction in the mempool is considered
          * a conflict. */
         const bool m_allow_bip125_replacement;
+        /** When true, the mempool will not be trimmed when individual transactions are submitted in
+         * Finalize(). Instead, limits should be enforced at the end to ensure the package is not
+         * partially submitted.
+         */
+        const bool m_package_submission;
 
         /** Parameters for single transaction mempool validation. */
         static ATMPArgs SingleAccept(const CChainParams& chainparams, int64_t accept_time,
@@ -476,6 +481,7 @@ public:
                             /* m_coins_to_uncache */ coins_to_uncache,
                             /* m_test_accept */ test_accept,
                             /* m_allow_bip125_replacement */ true,
+                            /* m_package_submission */ false,
             };
         }
 
@@ -488,9 +494,22 @@ public:
                             /* m_coins_to_uncache */ coins_to_uncache,
                             /* m_test_accept */ true,
                             /* m_allow_bip125_replacement */ false,
+                            /* m_package_submission */ false, // not submitting to mempool
             };
         }
 
+        /** Parameters for child-with-unconfirmed-parents package validation. */
+        static ATMPArgs PackageChildWithParents(const CChainParams& chainparams, int64_t accept_time,
+                                                std::vector<COutPoint>& coins_to_uncache) {
+            return ATMPArgs{/* m_chainparams */ chainparams,
+                            /* m_accept_time */ accept_time,
+                            /* m_bypass_limits */ false,
+                            /* m_coins_to_uncache */ coins_to_uncache,
+                            /* m_test_accept */ false,
+                            /* m_allow_bip125_replacement */ false,
+                            /* m_package_submission */ true,
+            };
+        }
         // No default ctor to avoid exposing details to clients and allowing the possibility of
         // mixing up the order of the arguments. Use static functions above instead.
         ATMPArgs() = delete;
@@ -500,12 +519,18 @@ public:
     MempoolAcceptResult AcceptSingleTransaction(const CTransactionRef& ptx, ATMPArgs& args) EXCLUSIVE_LOCKS_REQUIRED(cs_main);
 
     /**
-    * Multiple transaction acceptance. Transactions may or may not be interdependent,
-    * but must not conflict with each other. Parents must come before children if any
-    * dependencies exist.
+    * Multiple transaction acceptance. Transactions may or may not be interdependent, but must not
+    * conflict with each other, and the transactions cannot already be in the mempool. Parents must
+    * come before children if any dependencies exist.
     */
     PackageMempoolAcceptResult AcceptMultipleTransactions(const std::vector<CTransactionRef>& txns, ATMPArgs& args) EXCLUSIVE_LOCKS_REQUIRED(cs_main);
 
+    /**
+     * Package (more specific than just multiple transactions) acceptance. Package must be a child
+     * with all of its unconfirmed parents, and topologically sorted.
+     */
+    PackageMempoolAcceptResult AcceptPackage(const Package& package, ATMPArgs& args) EXCLUSIVE_LOCKS_REQUIRED(cs_main);
+
 private:
     // All the intermediate state that gets passed between the various levels
     // of checking a given transaction.
@@ -578,6 +603,14 @@ private:
     // limiting is performed, false otherwise.
     bool Finalize(const ATMPArgs& args, Workspace& ws) EXCLUSIVE_LOCKS_REQUIRED(cs_main, m_pool.cs);
 
+    // Submit all transactions to the mempool and call ConsensusScriptChecks to add to the script
+    // cache - should only be called after successful validation of all transactions in the package.
+    // The package may end up partially-submitted after size limitting; returns true if all
+    // transactions are successfully added to the mempool, false otherwise.
+    bool FinalizePackage(const ATMPArgs& args, std::vector<Workspace>& workspaces, PackageValidationState& package_state,
+                         std::map<const uint256, const MempoolAcceptResult>& results)
+         EXCLUSIVE_LOCKS_REQUIRED(cs_main, m_pool.cs);
+
     // Compare a package's feerate against minimum allowed.
     bool CheckFeeRate(size_t package_size, CAmount package_fee, TxValidationState& state) EXCLUSIVE_LOCKS_REQUIRED(cs_main, m_pool.cs)
     {
@@ -899,6 +932,10 @@ bool MemPoolAccept::PackageMempoolChecks(const std::vector<CTransactionRef>& txn
     AssertLockHeld(cs_main);
     AssertLockHeld(m_pool.cs);
 
+    // CheckPackageLimits expects the package transactions to not already be in the mempool.
+    assert(std::all_of(txns.cbegin(), txns.cend(), [this](const auto& tx)
+                       { return !m_pool.exists(GenTxid::Txid(tx->GetHash()));}));
+
     std::string err_string;
     if (!m_pool.CheckPackageLimits(txns, m_limit_ancestors, m_limit_ancestor_size, m_limit_descendants,
                                    m_limit_descendant_size, err_string)) {
@@ -991,13 +1028,18 @@ bool MemPoolAccept::Finalize(const ATMPArgs& args, Workspace& ws)
     // - it's not being re-added during a reorg which bypasses typical mempool fee limits
     // - the node is not behind
     // - the transaction is not dependent on any other transactions in the mempool
-    bool validForFeeEstimation = !bypass_limits && IsCurrentForFeeEstimation(m_active_chainstate) && m_pool.HasNoInputsOf(tx);
+    // - it's not part of a package. Since package relay is not currently supported, this
+    // transaction has not necessarily been accepted to miners' mempools.
+    bool validForFeeEstimation = !bypass_limits && !args.m_package_submission && IsCurrentForFeeEstimation(m_active_chainstate) && m_pool.HasNoInputsOf(tx);
 
     // Store transaction in memory
     m_pool.addUnchecked(*entry, ws.m_ancestors, validForFeeEstimation);
 
     // trim mempool and check if tx was trimmed
-    if (!bypass_limits) {
+    // If we are validating a package, don't trim here because we could evict a previous transaction
+    // in the package. LimitMempoolSize() should be called at the very end to make sure the mempool
+    // is still within limits and package submission happens atomically.
+    if (!args.m_package_submission && !bypass_limits) {
         LimitMempoolSize(m_pool, m_active_chainstate.CoinsTip(), gArgs.GetIntArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000, std::chrono::hours{gArgs.GetIntArg("-mempoolexpiry", DEFAULT_MEMPOOL_EXPIRY)});
         if (!m_pool.exists(GenTxid::Txid(hash)))
             return state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY, "mempool full");
@@ -1005,6 +1047,69 @@ bool MemPoolAccept::Finalize(const ATMPArgs& args, Workspace& ws)
     return true;
 }
 
+bool MemPoolAccept::FinalizePackage(const ATMPArgs& args, std::vector<Workspace>& workspaces,
+                                    PackageValidationState& package_state,
+                                    std::map<const uint256, const MempoolAcceptResult>& results)
+{
+    AssertLockHeld(cs_main);
+    AssertLockHeld(m_pool.cs);
+    bool all_submitted = true;
+    // ConsensusScriptChecks adds to the script cache and is therefore consensus-critical;
+    // CheckInputsFromMempoolAndCache asserts that transactions only spend coins available from the
+    // mempool or UTXO set. Submit each transaction to the mempool immediately after calling
+    // ConsensusScriptChecks to make the outputs available for subsequent transactions.
+    for (Workspace& ws : workspaces) {
+        if (!ConsensusScriptChecks(args, ws)) {
+            results.emplace(ws.m_ptx->GetWitnessHash(), MempoolAcceptResult::Failure(ws.m_state));
+            // Since PolicyScriptChecks() passed, this should never fail.
+            all_submitted = Assume(false);
+        }
+
+        // Re-calculate mempool ancestors to call addUnchecked(). They may have changed since the
+        // last calculation done in PreChecks, since package ancestors have already been submitted.
+        std::string err_string;
+        if(!m_pool.CalculateMemPoolAncestors(*ws.m_entry, ws.m_ancestors, m_limit_ancestors,
+                                             m_limit_ancestor_size, m_limit_descendants,
+                                             m_limit_descendant_size, err_string)) {
+            results.emplace(ws.m_ptx->GetWitnessHash(), MempoolAcceptResult::Failure(ws.m_state));
+            // Since PreChecks() and PackageMempoolChecks() both enforce limits, this should never fail.
+            all_submitted = Assume(false);
+        }
+        // If we call LimitMempoolSize() for each individual Finalize(), the mempool will not take
+        // the transaction's descendant feerate into account because it hasn't seen them yet. Also,
+        // we risk evicting a transaction that a subsequent package transaction depends on. Instead,
+        // allow the mempool to temporarily bypass limits, the maximum package size) while
+        // submitting transactions individually and then trim at the very end.
+        if (!Finalize(args, ws)) {
+            results.emplace(ws.m_ptx->GetWitnessHash(), MempoolAcceptResult::Failure(ws.m_state));
+            // Since LimitMempoolSize() won't be called, this should never fail.
+            all_submitted = Assume(false);
+        }
+    }
+
+    // It may or may not be the case that all the transactions made it into the mempool. Regardless,
+    // make sure we haven't exceeded max mempool size.
+    LimitMempoolSize(m_pool, m_active_chainstate.CoinsTip(),
+                     gArgs.GetIntArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000,
+                     std::chrono::hours{gArgs.GetIntArg("-mempoolexpiry", DEFAULT_MEMPOOL_EXPIRY)});
+    if (!all_submitted) return false;
+
+    // Find the wtxids of the transactions that made it into the mempool. Allow partial submission,
+    // but don't report success unless they all made it into the mempool.
+    for (Workspace& ws : workspaces) {
+        if (m_pool.exists(GenTxid::Wtxid(ws.m_ptx->GetWitnessHash()))) {
+            results.emplace(ws.m_ptx->GetWitnessHash(),
+                MempoolAcceptResult::Success(std::move(ws.m_replaced_transactions), ws.m_vsize, ws.m_base_fees));
+            GetMainSignals().TransactionAddedToMempool(ws.m_ptx, m_pool.GetAndIncrementSequence());
+        } else {
+            all_submitted = false;
+            ws.m_state.Invalid(TxValidationResult::TX_MEMPOOL_POLICY, "mempool full");
+            results.emplace(ws.m_ptx->GetWitnessHash(), MempoolAcceptResult::Failure(ws.m_state));
+        }
+    }
+    return all_submitted;
+}
+
 MempoolAcceptResult MemPoolAccept::AcceptSingleTransaction(const CTransactionRef& ptx, ATMPArgs& args)
 {
     AssertLockHeld(cs_main);
@@ -1090,9 +1195,114 @@ PackageMempoolAcceptResult MemPoolAccept::AcceptMultipleTransactions(const std::
         }
     }
 
+    if (args.m_test_accept) return PackageMempoolAcceptResult(package_state, std::move(results));
+
+    if (!FinalizePackage(args, workspaces, package_state, results)) {
+        package_state.Invalid(PackageValidationResult::PCKG_TX, "submission failed");
+        return PackageMempoolAcceptResult(package_state, std::move(results));
+    }
+
     return PackageMempoolAcceptResult(package_state, std::move(results));
 }
 
+PackageMempoolAcceptResult MemPoolAccept::AcceptPackage(const Package& package, ATMPArgs& args)
+{
+    AssertLockHeld(cs_main);
+    PackageValidationState package_state;
+
+    // Check that the package is well-formed. If it isn't, we won't try to validate any of the
+    // transactions and thus won't return any MempoolAcceptResults, just a package-wide error.
+
+    // Context-free package checks.
+    if (!CheckPackage(package, package_state)) return PackageMempoolAcceptResult(package_state, {});
+
+    // All transactions in the package must be a parent of the last transaction. This is just an
+    // opportunity for us to fail fast on a context-free check without taking the mempool lock.
+    if (!IsChildWithParents(package)) {
+        package_state.Invalid(PackageValidationResult::PCKG_POLICY, "package-not-child-with-parents");
+        return PackageMempoolAcceptResult(package_state, {});
+    }
+
+    const auto& child = package[package.size() - 1];
+    // The package must be 1 child with all of its unconfirmed parents. The package is expected to
+    // be sorted, so the last transaction is the child.
+    std::unordered_set<uint256, SaltedTxidHasher> unconfirmed_parent_txids;
+    std::transform(package.cbegin(), package.end() - 1,
+                   std::inserter(unconfirmed_parent_txids, unconfirmed_parent_txids.end()),
+                   [](const auto& tx) { return tx->GetHash(); });
+
+    // All child inputs must refer to a preceding package transaction or a confirmed UTXO. The only
+    // way to verify this is to look up the child's inputs in our current coins view (not including
+    // mempool), and enforce that all parents not present in the package be available at chain tip.
+    // Since this check can bring new coins into the coins cache, keep track of these coins and
+    // uncache them if we don't end up submitting this package to the mempool.
+    const CCoinsViewCache& coins_tip_cache = m_active_chainstate.CoinsTip();
+    for (const auto& input : child->vin) {
+        if (!coins_tip_cache.HaveCoinInCache(input.prevout)) {
+            args.m_coins_to_uncache.push_back(input.prevout);
+        }
+    }
+    // Using the MemPoolAccept m_view cache allows us to look up these same coins faster later.
+    // This should be connecting directly to CoinsTip, not to m_viewmempool, because we specifically
+    // require inputs to be confirmed if they aren't in the package.
+    m_view.SetBackend(m_active_chainstate.CoinsTip());
+    const auto package_or_confirmed = [this, &unconfirmed_parent_txids](const auto& input) {
+         return unconfirmed_parent_txids.count(input.prevout.hash) > 0 || m_view.HaveCoin(input.prevout);
+    };
+    if (!std::all_of(child->vin.cbegin(), child->vin.cend(), package_or_confirmed)) {
+        package_state.Invalid(PackageValidationResult::PCKG_POLICY, "package-not-child-with-unconfirmed-parents");
+        return PackageMempoolAcceptResult(package_state, {});
+    }
+    // Protect against bugs where we pull more inputs from disk that miss being added to
+    // coins_to_uncache. The backend will be connected again when needed in PreChecks.
+    m_view.SetBackend(m_dummy);
+
+    LOCK(m_pool.cs);
+    std::map<const uint256, const MempoolAcceptResult> results;
+    // As node operators are free to set their mempool policies however they please, it's possible
+    // for package transaction(s) to already be in the mempool, and we don't want to reject the
+    // entire package in that case (as that could be a censorship vector).  Filter the transactions
+    // that are already in mempool and add their information to results, since we already have them.
+    std::vector<CTransactionRef> txns_new;
+    for (const auto& tx : package) {
+        const auto& wtxid = tx->GetWitnessHash();
+        const auto& txid = tx->GetHash();
+        // There are 3 possibilities: already in mempool, same-txid-diff-wtxid already in mempool,
+        // or not in mempool. An already confirmed tx is treated as one not in mempool, because all
+        // we know is that the inputs aren't available.
+        if (m_pool.exists(GenTxid::Wtxid(wtxid))) {
+            // Exact transaction already exists in the mempool.
+            auto iter = m_pool.GetIter(wtxid);
+            assert(iter != std::nullopt);
+            results.emplace(wtxid, MempoolAcceptResult::MempoolTx(iter.value()->GetTxSize(), iter.value()->GetFee()));
+        } else if (m_pool.exists(GenTxid::Txid(txid))) {
+            // Transaction with the same non-witness data but different witness (same txid,
+            // different wtxid) already exists in the mempool.
+            //
+            // We don't allow replacement transactions right now, so just swap the package
+            // transaction for the mempool one. Note that we are ignoring the validity of the
+            // package transaction passed in.
+            // TODO: allow witness replacement in packages.
+            auto iter = m_pool.GetIter(wtxid);
+            assert(iter != std::nullopt);
+            results.emplace(txid, MempoolAcceptResult::MempoolTx(iter.value()->GetTxSize(), iter.value()->GetFee()));
+        } else {
+            // Transaction does not already exist in the mempool.
+            txns_new.push_back(tx);
+        }
+    }
+
+    // Nothing to do if the entire package has already been submitted.
+    if (txns_new.empty()) return PackageMempoolAcceptResult(package_state, std::move(results));
+    // Validate the (deduplicated) transactions as a package.
+    auto submission_result = AcceptMultipleTransactions(txns_new, args);
+    // Include already-in-mempool transaction results in the final result.
+    for (const auto& [wtxid, mempoolaccept_res] : results) {
+        submission_result.m_tx_results.emplace(wtxid, mempoolaccept_res);
+    }
+    return submission_result;
+}
+
 } // anon namespace
 
 MempoolAcceptResult AcceptToMemoryPool(CChainState& active_chainstate, const CTransactionRef& tx,
@@ -1125,19 +1335,31 @@ PackageMempoolAcceptResult ProcessNewPackage(CChainState& active_chainstate, CTx
                                                    const Package& package, bool test_accept)
 {
     AssertLockHeld(cs_main);
-    assert(test_accept); // Only allow package accept dry-runs (testmempoolaccept RPC).
     assert(!package.empty());
     assert(std::all_of(package.cbegin(), package.cend(), [](const auto& tx){return tx != nullptr;}));
 
     std::vector<COutPoint> coins_to_uncache;
     const CChainParams& chainparams = Params();
-    auto args = MemPoolAccept::ATMPArgs::PackageTestAccept(chainparams, GetTime(), coins_to_uncache);
-    const PackageMempoolAcceptResult result = MemPoolAccept(pool, active_chainstate).AcceptMultipleTransactions(package, args);
+    const auto result = [&]() EXCLUSIVE_LOCKS_REQUIRED(cs_main) {
+        AssertLockHeld(cs_main);
+        if (test_accept) {
+            auto args = MemPoolAccept::ATMPArgs::PackageTestAccept(chainparams, GetTime(), coins_to_uncache);
+            return MemPoolAccept(pool, active_chainstate).AcceptMultipleTransactions(package, args);
+        } else {
+            auto args = MemPoolAccept::ATMPArgs::PackageChildWithParents(chainparams, GetTime(), coins_to_uncache);
+            return MemPoolAccept(pool, active_chainstate).AcceptPackage(package, args);
+        }
+    }();
 
     // Uncache coins pertaining to transactions that were not submitted to the mempool.
-    for (const COutPoint& hashTx : coins_to_uncache) {
-        active_chainstate.CoinsTip().Uncache(hashTx);
+    // Ensure the coins cache is still within limits.
+    if (test_accept || result.m_state.IsInvalid()) {
+        for (const COutPoint& hashTx : coins_to_uncache) {
+            active_chainstate.CoinsTip().Uncache(hashTx);
+        }
     }
+    BlockValidationState state_dummy;
+    active_chainstate.FlushStateToDisk(state_dummy, FlushStateMode::PERIODIC);
     return result;
 }
 
diff --git a/src/validation.h b/src/validation.h
index 534df9bc87..ddfc8df939 100644
--- a/src/validation.h
+++ b/src/validation.h
@@ -60,6 +60,16 @@ static const unsigned int DEFAULT_ANCESTOR_SIZE_LIMIT = 101;
 static const unsigned int DEFAULT_DESCENDANT_LIMIT = 25;
 /** Default for -limitdescendantsize, maximum kilobytes of in-mempool descendants */
 static const unsigned int DEFAULT_DESCENDANT_SIZE_LIMIT = 101;
+
+// If a package is submitted, it must be within the mempool's ancestor/descendant limits. Since a
+// submitted package must be child-with-unconfirmed-parents (all of the transactions are an ancestor
+// of the child), package limits are ultimately bounded by mempool package limits. Ensure that the
+// defaults reflect this constraint.
+static_assert(DEFAULT_DESCENDANT_LIMIT >= MAX_PACKAGE_COUNT);
+static_assert(DEFAULT_ANCESTOR_LIMIT >= MAX_PACKAGE_COUNT);
+static_assert(DEFAULT_ANCESTOR_SIZE_LIMIT >= MAX_PACKAGE_SIZE);
+static_assert(DEFAULT_DESCENDANT_SIZE_LIMIT >= MAX_PACKAGE_SIZE);
+
 /** Default for -mempoolexpiry, expiration time for mempool transactions in hours */
 static const unsigned int DEFAULT_MEMPOOL_EXPIRY = 336;
 /** Maximum number of dedicated script-checking threads allowed */
@@ -151,17 +161,19 @@ struct MempoolAcceptResult {
     enum class ResultType {
         VALID, //!> Fully validated, valid.
         INVALID, //!> Invalid.
+        MEMPOOL_ENTRY, //!> Valid, transaction was already in the mempool.
     };
     const ResultType m_result_type;
     const TxValidationState m_state;
 
-    // The following fields are only present when m_result_type = ResultType::VALID
+    // The following fields are only present when m_result_type = ResultType::VALID or MEMPOOL_ENTRY
     /** Mempool transactions replaced by the tx per BIP 125 rules. */
     const std::optional<std::list<CTransactionRef>> m_replaced_transactions;
     /** Virtual size as used by the mempool, calculated using serialized size and sigops. */
     const std::optional<int64_t> m_vsize;
     /** Raw base fees in satoshis. */
     const std::optional<CAmount> m_base_fees;
+
     static MempoolAcceptResult Failure(TxValidationState state) {
         return MempoolAcceptResult(state);
     }
@@ -170,6 +182,10 @@ struct MempoolAcceptResult {
         return MempoolAcceptResult(std::move(replaced_txns), vsize, fees);
     }
 
+    static MempoolAcceptResult MempoolTx(int64_t vsize, CAmount fees) {
+        return MempoolAcceptResult(vsize, fees);
+    }
+
 // Private constructors. Use static methods MempoolAcceptResult::Success, etc. to construct.
 private:
     /** Constructor for failure case */
@@ -182,6 +198,10 @@ private:
     explicit MempoolAcceptResult(std::list<CTransactionRef>&& replaced_txns, int64_t vsize, CAmount fees)
         : m_result_type(ResultType::VALID),
         m_replaced_transactions(std::move(replaced_txns)), m_vsize{vsize}, m_base_fees(fees) {}
+
+    /** Constructor for already-in-mempool case. It wouldn't replace any transactions. */
+    explicit MempoolAcceptResult(int64_t vsize, CAmount fees)
+        : m_result_type(ResultType::MEMPOOL_ENTRY), m_vsize{vsize}, m_base_fees(fees) {}
 };
 
 /**
@@ -191,7 +211,7 @@ struct PackageMempoolAcceptResult
 {
     const PackageValidationState m_state;
     /**
-    * Map from wtxid to finished MempoolAcceptResults. The client is responsible
+    * Map from (w)txid to finished MempoolAcceptResults. The client is responsible
     * for keeping track of the transaction objects themselves. If a result is not
     * present, it means validation was unfinished for that transaction. If there
     * was a package-wide error (see result in m_state), m_tx_results will be empty.
@@ -225,16 +245,12 @@ MempoolAcceptResult AcceptToMemoryPool(CChainState& active_chainstate, const CTr
     EXCLUSIVE_LOCKS_REQUIRED(cs_main);
 
 /**
-* Atomically test acceptance of a package. If the package only contains one tx, package rules still
-* apply. Package validation does not allow BIP125 replacements, so the transaction(s) cannot spend
-* the same inputs as any transaction in the mempool.
-* @param[in]    txns                Group of transactions which may be independent or contain
-*                                   parent-child dependencies. The transactions must not conflict
-*                                   with each other, i.e., must not spend the same inputs. If any
-*                                   dependencies exist, parents must appear anywhere in the list
-*                                   before their children.
+* Validate (and maybe submit) a package to the mempool. See doc/policy/packages.md for full details
+* on package validation rules.
+* @param[in]    test_accept     When true, run validation checks but don't submit to mempool.
 * @returns a PackageMempoolAcceptResult which includes a MempoolAcceptResult for each transaction.
-* If a transaction fails, validation will exit early and some results may be missing.
+* If a transaction fails, validation will exit early and some results may be missing. It is also
+* possible for the package to be partially submitted.
 */
 PackageMempoolAcceptResult ProcessNewPackage(CChainState& active_chainstate, CTxMemPool& pool,
                                                    const Package& txns, bool test_accept)