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

2 files changed, 23 insertions, 0 deletions

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