aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/policy/packages.cpp100
-rw-r--r--src/policy/packages.h23
-rw-r--r--src/test/txpackage_tests.cpp47
-rw-r--r--src/validation.cpp6
4 files changed, 137 insertions, 39 deletions
diff --git a/src/policy/packages.cpp b/src/policy/packages.cpp
index 47a9274a31..3660995bc8 100644
--- a/src/policy/packages.cpp
+++ b/src/policy/packages.cpp
@@ -6,16 +6,77 @@
#include <policy/policy.h>
#include <primitives/transaction.h>
#include <uint256.h>
-#include <util/hasher.h>
+#include <util/check.h>
#include <algorithm>
#include <cassert>
#include <iterator>
#include <memory>
#include <numeric>
-#include <unordered_set>
-bool CheckPackage(const Package& txns, PackageValidationState& state)
+/** IsTopoSortedPackage where a set of txids has been pre-populated. The set is assumed to be correct and
+ * is mutated within this function (even if return value is false). */
+bool IsTopoSortedPackage(const Package& txns, std::unordered_set<uint256, SaltedTxidHasher>& later_txids)
+{
+ // Avoid misusing this function: later_txids should contain the txids of txns.
+ Assume(txns.size() == later_txids.size());
+
+ // later_txids always contains the txids of this transaction and the ones that come later in
+ // txns. If any transaction's input spends a tx in that set, we've found a parent placed later
+ // than its child.
+ 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.
+ return false;
+ }
+ }
+ // Avoid misusing this function: later_txids must contain every tx.
+ Assume(later_txids.erase(tx->GetHash()) == 1);
+ }
+
+ // Avoid misusing this function: later_txids should have contained the txids of txns.
+ Assume(later_txids.empty());
+ return true;
+}
+
+bool IsTopoSortedPackage(const Package& txns)
+{
+ 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(); });
+
+ return IsTopoSortedPackage(txns, later_txids);
+}
+
+bool IsConsistentPackage(const Package& txns)
+{
+ // Don't allow any conflicting transactions, i.e. spending the same inputs, in a package.
+ std::unordered_set<COutPoint, SaltedOutpointHasher> inputs_seen;
+ for (const auto& tx : txns) {
+ if (tx->vin.empty()) {
+ // This function checks consistency based on inputs, and we can't do that if there are
+ // no inputs. Duplicate empty transactions are also not consistent with one another.
+ // This doesn't create false negatives, as unconfirmed transactions are not allowed to
+ // have no inputs.
+ return false;
+ }
+ for (const auto& input : tx->vin) {
+ if (inputs_seen.find(input.prevout) != inputs_seen.end()) {
+ // This input is also present in another tx in the package.
+ return false;
+ }
+ }
+ // Batch-add all the inputs for a tx at a time. If we added them 1 at a time, we could
+ // catch duplicate inputs within a single tx. This is a more severe, consensus error,
+ // and we want to report that from CheckTransaction instead.
+ std::transform(tx->vin.cbegin(), tx->vin.cend(), std::inserter(inputs_seen, inputs_seen.end()),
+ [](const auto& input) { return input.prevout; });
+ }
+ return true;
+}
+
+bool CheckPackage(const Package& txns, PackageValidationState& state, bool require_sorted)
{
const unsigned int package_count = txns.size();
@@ -30,10 +91,6 @@ bool CheckPackage(const Package& txns, PackageValidationState& state)
return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-too-large");
}
- // 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).
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(); });
@@ -44,30 +101,17 @@ bool CheckPackage(const Package& txns, PackageValidationState& state)
return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-contains-duplicates");
}
- 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.
- return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-not-sorted");
- }
- }
- later_txids.erase(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).
+ if (require_sorted && !IsTopoSortedPackage(txns, later_txids)) {
+ return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-not-sorted");
}
// Don't allow any conflicting transactions, i.e. spending the same inputs, in a package.
- std::unordered_set<COutPoint, SaltedOutpointHasher> inputs_seen;
- for (const auto& tx : txns) {
- for (const auto& input : tx->vin) {
- if (inputs_seen.find(input.prevout) != inputs_seen.end()) {
- // This input is also present in another tx in the package.
- return state.Invalid(PackageValidationResult::PCKG_POLICY, "conflict-in-package");
- }
- }
- // Batch-add all the inputs for a tx at a time. If we added them 1 at a time, we could
- // catch duplicate inputs within a single tx. This is a more severe, consensus error,
- // and we want to report that from CheckTransaction instead.
- std::transform(tx->vin.cbegin(), tx->vin.cend(), std::inserter(inputs_seen, inputs_seen.end()),
- [](const auto& input) { return input.prevout; });
+ if (!IsConsistentPackage(txns)) {
+ return state.Invalid(PackageValidationResult::PCKG_POLICY, "conflict-in-package");
}
return true;
}
diff --git a/src/policy/packages.h b/src/policy/packages.h
index cf37857e4b..1ca1a962ba 100644
--- a/src/policy/packages.h
+++ b/src/policy/packages.h
@@ -9,8 +9,10 @@
#include <consensus/validation.h>
#include <policy/policy.h>
#include <primitives/transaction.h>
+#include <util/hasher.h>
#include <cstdint>
+#include <unordered_set>
#include <vector>
/** Default maximum number of transactions in a package. */
@@ -49,13 +51,32 @@ using Package = std::vector<CTransactionRef>;
class PackageValidationState : public ValidationState<PackageValidationResult> {};
+/** If any direct dependencies exist between transactions (i.e. a child spending the output of a
+ * parent), checks that all parents appear somewhere in the list before their respective children.
+ * No other ordering is enforced. This function cannot detect indirect dependencies (e.g. a
+ * transaction's grandparent if its parent is not present).
+ * @returns true if sorted. False if any tx spends the output of a tx that appears later in txns.
+ */
+bool IsTopoSortedPackage(const Package& txns);
+
+/** Checks that these transactions don't conflict, i.e., spend the same prevout. This includes
+ * checking that there are no duplicate transactions. Since these checks require looking at the inputs
+ * of a transaction, returns false immediately if any transactions have empty vin.
+ *
+ * Does not check consistency of a transaction with oneself; does not check if a transaction spends
+ * the same prevout multiple times (see bad-txns-inputs-duplicate in CheckTransaction()).
+ *
+ * @returns true if there are no conflicts. False if any two transactions spend the same prevout.
+ * */
+bool IsConsistentPackage(const Package& txns);
+
/** Context-free package policy checks:
* 1. The number of transactions cannot exceed MAX_PACKAGE_COUNT.
* 2. The total weight cannot exceed MAX_PACKAGE_WEIGHT.
* 3. If any dependencies exist between transactions, parents must appear before children.
* 4. Transactions cannot conflict, i.e., spend the same inputs.
*/
-bool CheckPackage(const Package& txns, PackageValidationState& state);
+bool CheckPackage(const Package& txns, PackageValidationState& state, bool require_sorted);
/** 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.
diff --git a/src/test/txpackage_tests.cpp b/src/test/txpackage_tests.cpp
index 4d9a5ef7f3..39ae727729 100644
--- a/src/test/txpackage_tests.cpp
+++ b/src/test/txpackage_tests.cpp
@@ -9,6 +9,7 @@
#include <primitives/transaction.h>
#include <script/script.h>
#include <test/util/random.h>
+#include <test/util/script.h>
#include <test/util/setup_common.h>
#include <validation.h>
@@ -47,7 +48,7 @@ BOOST_FIXTURE_TEST_CASE(package_sanitization_tests, TestChain100Setup)
package_too_many.emplace_back(create_placeholder_tx(1, 1));
}
PackageValidationState state_too_many;
- BOOST_CHECK(!CheckPackage(package_too_many, state_too_many));
+ BOOST_CHECK(!CheckPackage(package_too_many, state_too_many, /*require_sorted=*/true));
BOOST_CHECK_EQUAL(state_too_many.GetResult(), PackageValidationResult::PCKG_POLICY);
BOOST_CHECK_EQUAL(state_too_many.GetRejectReason(), "package-too-many-transactions");
@@ -62,7 +63,7 @@ BOOST_FIXTURE_TEST_CASE(package_sanitization_tests, TestChain100Setup)
}
BOOST_CHECK(package_too_large.size() <= MAX_PACKAGE_COUNT);
PackageValidationState state_too_large;
- BOOST_CHECK(!CheckPackage(package_too_large, state_too_large));
+ BOOST_CHECK(!CheckPackage(package_too_large, state_too_large, /*require_sorted=*/true));
BOOST_CHECK_EQUAL(state_too_large.GetResult(), PackageValidationResult::PCKG_POLICY);
BOOST_CHECK_EQUAL(state_too_large.GetRejectReason(), "package-too-large");
@@ -73,9 +74,39 @@ BOOST_FIXTURE_TEST_CASE(package_sanitization_tests, TestChain100Setup)
package_duplicate_txids_empty.emplace_back(MakeTransactionRef(empty_tx));
}
PackageValidationState state_duplicates;
- BOOST_CHECK(!CheckPackage(package_duplicate_txids_empty, state_duplicates));
+ BOOST_CHECK(!CheckPackage(package_duplicate_txids_empty, state_duplicates, /*require_sorted=*/true));
BOOST_CHECK_EQUAL(state_duplicates.GetResult(), PackageValidationResult::PCKG_POLICY);
BOOST_CHECK_EQUAL(state_duplicates.GetRejectReason(), "package-contains-duplicates");
+ BOOST_CHECK(!IsConsistentPackage(package_duplicate_txids_empty));
+
+ // Packages can't have transactions spending the same prevout
+ CMutableTransaction tx_zero_1;
+ CMutableTransaction tx_zero_2;
+ COutPoint same_prevout{InsecureRand256(), 0};
+ tx_zero_1.vin.emplace_back(same_prevout);
+ tx_zero_2.vin.emplace_back(same_prevout);
+ // Different vouts (not the same tx)
+ tx_zero_1.vout.emplace_back(CENT, P2WSH_OP_TRUE);
+ tx_zero_2.vout.emplace_back(2 * CENT, P2WSH_OP_TRUE);
+ Package package_conflicts{MakeTransactionRef(tx_zero_1), MakeTransactionRef(tx_zero_2)};
+ BOOST_CHECK(!IsConsistentPackage(package_conflicts));
+ // Transactions are considered sorted when they have no dependencies.
+ BOOST_CHECK(IsTopoSortedPackage(package_conflicts));
+ PackageValidationState state_conflicts;
+ BOOST_CHECK(!CheckPackage(package_conflicts, state_conflicts, /*require_sorted=*/true));
+ BOOST_CHECK_EQUAL(state_conflicts.GetResult(), PackageValidationResult::PCKG_POLICY);
+ BOOST_CHECK_EQUAL(state_conflicts.GetRejectReason(), "conflict-in-package");
+
+ // IsConsistentPackage only cares about conflicts between transactions, not about a transaction
+ // conflicting with itself (i.e. duplicate prevouts in vin).
+ CMutableTransaction dup_tx;
+ const COutPoint rand_prevout{InsecureRand256(), 0};
+ dup_tx.vin.emplace_back(rand_prevout);
+ dup_tx.vin.emplace_back(rand_prevout);
+ Package package_with_dup_tx{MakeTransactionRef(dup_tx)};
+ BOOST_CHECK(IsConsistentPackage(package_with_dup_tx));
+ package_with_dup_tx.emplace_back(create_placeholder_tx(1, 1));
+ BOOST_CHECK(IsConsistentPackage(package_with_dup_tx));
}
BOOST_FIXTURE_TEST_CASE(package_validation_tests, TestChain100Setup)
@@ -157,8 +188,8 @@ BOOST_FIXTURE_TEST_CASE(noncontextual_package_tests, TestChain100Setup)
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(CheckPackage({tx_parent, tx_child}, state, /*require_sorted=*/true));
+ BOOST_CHECK(!CheckPackage({tx_child, tx_parent}, state, /*require_sorted=*/true));
BOOST_CHECK_EQUAL(state.GetResult(), PackageValidationResult::PCKG_POLICY);
BOOST_CHECK_EQUAL(state.GetRejectReason(), "package-not-sorted");
BOOST_CHECK(IsChildWithParents({tx_parent, tx_child}));
@@ -186,7 +217,7 @@ BOOST_FIXTURE_TEST_CASE(noncontextual_package_tests, TestChain100Setup)
package.push_back(MakeTransactionRef(child));
PackageValidationState state;
- BOOST_CHECK(CheckPackage(package, state));
+ BOOST_CHECK(CheckPackage(package, state, /*require_sorted=*/true));
BOOST_CHECK(IsChildWithParents(package));
BOOST_CHECK(IsChildWithParentsTree(package));
@@ -224,8 +255,8 @@ BOOST_FIXTURE_TEST_CASE(noncontextual_package_tests, TestChain100Setup)
BOOST_CHECK(!IsChildWithParentsTree({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(CheckPackage({tx_parent, tx_parent_also_child, tx_child}, state, /*require_sorted=*/true));
+ BOOST_CHECK(!CheckPackage({tx_parent_also_child, tx_parent, tx_child}, state, /*require_sorted=*/true));
BOOST_CHECK_EQUAL(state.GetResult(), PackageValidationResult::PCKG_POLICY);
BOOST_CHECK_EQUAL(state.GetRejectReason(), "package-not-sorted");
}
diff --git a/src/validation.cpp b/src/validation.cpp
index c72188d581..e2873e8b4e 100644
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -1258,7 +1258,7 @@ PackageMempoolAcceptResult MemPoolAccept::AcceptMultipleTransactions(const std::
// These context-free package limits can be done before taking the mempool lock.
PackageValidationState package_state;
- if (!CheckPackage(txns, package_state)) return PackageMempoolAcceptResult(package_state, {});
+ if (!CheckPackage(txns, package_state, /*require_sorted=*/true)) return PackageMempoolAcceptResult(package_state, {});
std::vector<Workspace> workspaces{};
workspaces.reserve(txns.size());
@@ -1405,7 +1405,9 @@ PackageMempoolAcceptResult MemPoolAccept::AcceptPackage(const Package& package,
// transactions and thus won't return any MempoolAcceptResults, just a package-wide error.
// Context-free package checks.
- if (!CheckPackage(package, package_state_quit_early)) return PackageMempoolAcceptResult(package_state_quit_early, {});
+ if (!CheckPackage(package, package_state_quit_early, /*require_sorted=*/true)) {
+ return PackageMempoolAcceptResult(package_state_quit_early, {});
+ }
// 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.
generated by cgit v1.2.3 (git 2.26.2) at 2025-01-09 01:15:00 +0000