From 13650fe2e527bf0cf5d977bf5f3f1563b853ecdc Mon Sep 17 00:00:00 2001
From: glozow <gzhao408@berkeley.edu>
Date: Mon, 5 Apr 2021 13:15:56 -0700
Subject: [policy] detect unsorted packages

---
 src/validation.cpp | 26 ++++++++++++++++++++++----
 1 file changed, 22 insertions(+), 4 deletions(-)

(limited to 'src/validation.cpp')

diff --git a/src/validation.cpp b/src/validation.cpp
index 07308aab39..ebe88ba04d 100644
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -42,6 +42,7 @@
 #include <uint256.h>
 #include <undo.h>
 #include <util/check.h> // For NDEBUG compile time check
+#include <util/hasher.h>
 #include <util/moneystr.h>
 #include <util/rbf.h>
 #include <util/strencodings.h>
@@ -1093,12 +1094,29 @@ PackageMempoolAcceptResult MemPoolAccept::AcceptMultipleTransactions(const std::
         return PackageMempoolAcceptResult(package_state, {});
     }
 
+    // Construct workspaces and check package policies.
     std::vector<Workspace> workspaces{};
     workspaces.reserve(package_count);
-    std::transform(txns.cbegin(), txns.cend(), std::back_inserter(workspaces), [](const auto& tx) {
-        return Workspace(tx);
-    });
-
+    {
+        std::unordered_set<uint256, SaltedTxidHasher> later_txids;
+        std::transform(txns.cbegin(), txns.cend(), std::inserter(later_txids, later_txids.end()),
+                       [](const auto& tx) { return tx->GetHash(); });
+        // Require the package to be sorted in order of dependency, i.e. parents appear before children.
+        // An unsorted package will fail anyway on missing-inputs, but it's better to quit earlier and
+        // fail on something less ambiguous (missing-inputs could also be an orphan or trying to
+        // spend nonexistent coins).
+        for (const auto& tx : txns) {
+            for (const auto& input : tx->vin) {
+                if (later_txids.find(input.prevout.hash) != later_txids.end()) {
+                    // The parent is a subsequent transaction in the package.
+                    package_state.Invalid(PackageValidationResult::PCKG_POLICY, "package-not-sorted");
+                    return PackageMempoolAcceptResult(package_state, {});
+                }
+            }
+            later_txids.erase(tx->GetHash());
+            workspaces.emplace_back(Workspace(tx));
+        }
+    }
     std::map<const uint256, const MempoolAcceptResult> results;
     {
         // Don't allow any conflicting transactions, i.e. spending the same inputs, in a package.
-- 
cgit v1.2.3