1  // Copyright (c) 2021-2022 The Bitcoin Core developers
  2  // Distributed under the MIT software license, see the accompanying
  3  // file COPYING or http://www.opensource.org/licenses/mit-license.php.
  4  
  5  #include <policy/packages.h>
  6  #include <policy/policy.h>
  7  #include <primitives/transaction.h>
  8  #include <uint256.h>
  9  #include <util/check.h>
 10  
 11  #include <algorithm>
 12  #include <cassert>
 13  #include <iterator>
 14  #include <memory>
 15  #include <numeric>
 16  
 17  /** IsTopoSortedPackage where a set of txids has been pre-populated. The set is assumed to be correct and
 18   * is mutated within this function (even if return value is false). */
 19  bool IsTopoSortedPackage(const Package& txns, std::unordered_set<uint256, SaltedTxidHasher>& later_txids)
 20  {
 21      // Avoid misusing this function: later_txids should contain the txids of txns.
 22      Assume(txns.size() == later_txids.size());
 23  
 24      // later_txids always contains the txids of this transaction and the ones that come later in
 25      // txns. If any transaction's input spends a tx in that set, we've found a parent placed later
 26      // than its child.
 27      for (const auto& tx : txns) {
 28          for (const auto& input : tx->vin) {
 29              if (later_txids.find(input.prevout.hash) != later_txids.end()) {
 30                  // The parent is a subsequent transaction in the package.
 31                  return false;
 32              }
 33          }
 34          // Avoid misusing this function: later_txids must contain every tx.
 35          Assume(later_txids.erase(tx->GetHash()) == 1);
 36      }
 37  
 38      // Avoid misusing this function: later_txids should have contained the txids of txns.
 39      Assume(later_txids.empty());
 40      return true;
 41  }
 42  
 43  bool IsTopoSortedPackage(const Package& txns)
 44  {
 45      std::unordered_set<uint256, SaltedTxidHasher> later_txids;
 46      std::transform(txns.cbegin(), txns.cend(), std::inserter(later_txids, later_txids.end()),
 47                     [](const auto& tx) { return tx->GetHash(); });
 48  
 49      return IsTopoSortedPackage(txns, later_txids);
 50  }
 51  
 52  bool IsConsistentPackage(const Package& txns)
 53  {
 54      // Don't allow any conflicting transactions, i.e. spending the same inputs, in a package.
 55      std::unordered_set<COutPoint, SaltedOutpointHasher> inputs_seen;
 56      for (const auto& tx : txns) {
 57          if (tx->vin.empty()) {
 58              // This function checks consistency based on inputs, and we can't do that if there are
 59              // no inputs. Duplicate empty transactions are also not consistent with one another.
 60              // This doesn't create false negatives, as unconfirmed transactions are not allowed to
 61              // have no inputs.
 62              return false;
 63          }
 64          for (const auto& input : tx->vin) {
 65              if (inputs_seen.find(input.prevout) != inputs_seen.end()) {
 66                  // This input is also present in another tx in the package.
 67                  return false;
 68              }
 69          }
 70          // Batch-add all the inputs for a tx at a time. If we added them 1 at a time, we could
 71          // catch duplicate inputs within a single tx.  This is a more severe, consensus error,
 72          // and we want to report that from CheckTransaction instead.
 73          std::transform(tx->vin.cbegin(), tx->vin.cend(), std::inserter(inputs_seen, inputs_seen.end()),
 74                         [](const auto& input) { return input.prevout; });
 75      }
 76      return true;
 77  }
 78  
 79  bool IsWellFormedPackage(const Package& txns, PackageValidationState& state, bool require_sorted)
 80  {
 81      const unsigned int package_count = txns.size();
 82  
 83      if (package_count > MAX_PACKAGE_COUNT) {
 84          return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-too-many-transactions");
 85      }
 86  
 87      const int64_t total_weight = std::accumulate(txns.cbegin(), txns.cend(), 0,
 88                                 [](int64_t sum, const auto& tx) { return sum + GetTransactionWeight(*tx); });
 89      // If the package only contains 1 tx, it's better to report the policy violation on individual tx weight.
 90      if (package_count > 1 && total_weight > MAX_PACKAGE_WEIGHT) {
 91          return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-too-large");
 92      }
 93  
 94      std::unordered_set<uint256, SaltedTxidHasher> later_txids;
 95      std::transform(txns.cbegin(), txns.cend(), std::inserter(later_txids, later_txids.end()),
 96                     [](const auto& tx) { return tx->GetHash(); });
 97  
 98      // Package must not contain any duplicate transactions, which is checked by txid. This also
 99      // includes transactions with duplicate wtxids and same-txid-different-witness transactions.
100      if (later_txids.size() != txns.size()) {
101          return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-contains-duplicates");
102      }
103  
104      // Require the package to be sorted in order of dependency, i.e. parents appear before children.
105      // An unsorted package will fail anyway on missing-inputs, but it's better to quit earlier and
106      // fail on something less ambiguous (missing-inputs could also be an orphan or trying to
107      // spend nonexistent coins).
108      if (require_sorted && !IsTopoSortedPackage(txns, later_txids)) {
109          return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-not-sorted");
110      }
111  
112      // Don't allow any conflicting transactions, i.e. spending the same inputs, in a package.
113      if (!IsConsistentPackage(txns)) {
114          return state.Invalid(PackageValidationResult::PCKG_POLICY, "conflict-in-package");
115      }
116      return true;
117  }
118  
119  bool IsChildWithParents(const Package& package)
120  {
121      assert(std::all_of(package.cbegin(), package.cend(), [](const auto& tx){return tx != nullptr;}));
122      if (package.size() < 2) return false;
123  
124      // The package is expected to be sorted, so the last transaction is the child.
125      const auto& child = package.back();
126      std::unordered_set<uint256, SaltedTxidHasher> input_txids;
127      std::transform(child->vin.cbegin(), child->vin.cend(),
128                     std::inserter(input_txids, input_txids.end()),
129                     [](const auto& input) { return input.prevout.hash; });
130  
131      // Every transaction must be a parent of the last transaction in the package.
132      return std::all_of(package.cbegin(), package.cend() - 1,
133                         [&input_txids](const auto& ptx) { return input_txids.count(ptx->GetHash()) > 0; });
134  }
135  
136  bool IsChildWithParentsTree(const Package& package)
137  {
138      if (!IsChildWithParents(package)) return false;
139      std::unordered_set<uint256, SaltedTxidHasher> parent_txids;
140      std::transform(package.cbegin(), package.cend() - 1, std::inserter(parent_txids, parent_txids.end()),
141                     [](const auto& ptx) { return ptx->GetHash(); });
142      // Each parent must not have an input who is one of the other parents.
143      return std::all_of(package.cbegin(), package.cend() - 1, [&](const auto& ptx) {
144          for (const auto& input : ptx->vin) {
145              if (parent_txids.count(input.prevout.hash) > 0) return false;
146          }
147          return true;
148      });
149  }