packages.cpp
1 // Copyright (c) 2021-present 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<Txid, 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.contains(input.prevout.hash)) { 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<Txid, 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.contains(input.prevout)) { 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) 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<Txid, 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 (!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<Txid, 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.contains(ptx->GetHash()); }); 134 } 135 136 bool IsChildWithParentsTree(const Package& package) 137 { 138 if (!IsChildWithParents(package)) return false; 139 std::unordered_set<Txid, 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.contains(input.prevout.hash)) return false; 146 } 147 return true; 148 }); 149 } 150 151 uint256 GetPackageHash(const std::vector<CTransactionRef>& transactions) 152 { 153 // Create a vector of the wtxids. 154 std::vector<Wtxid> wtxids_copy; 155 std::transform(transactions.cbegin(), transactions.cend(), std::back_inserter(wtxids_copy), 156 [](const auto& tx){ return tx->GetWitnessHash(); }); 157 158 // Sort in ascending order 159 std::sort(wtxids_copy.begin(), wtxids_copy.end(), [](const auto& lhs, const auto& rhs) { 160 return std::lexicographical_compare(std::make_reverse_iterator(lhs.end()), std::make_reverse_iterator(lhs.begin()), 161 std::make_reverse_iterator(rhs.end()), std::make_reverse_iterator(rhs.begin())); 162 }); 163 164 // Get sha256 hash of the wtxids concatenated in this order 165 HashWriter hashwriter; 166 for (const auto& wtxid : wtxids_copy) { 167 hashwriter << wtxid; 168 } 169 return hashwriter.GetSHA256(); 170 }