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 }
171