Branch data Line data Source code
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 : 35 : 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 : 35 : 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 [ + + ]: 135 : for (const auto& tx : txns) {
28 [ + + ]: 1229 : for (const auto& input : tx->vin) {
29 [ + + ]: 1129 : 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 : 100 : Assume(later_txids.erase(tx->GetHash()) == 1);
36 : : }
37 : :
38 : : // Avoid misusing this function: later_txids should have contained the txids of txns.
39 : 33 : Assume(later_txids.empty());
40 : 33 : return true;
41 : : }
42 : :
43 : 1 : bool IsTopoSortedPackage(const Package& txns)
44 : : {
45 : 1 : std::unordered_set<uint256, SaltedTxidHasher> later_txids;
46 [ + - ]: 1 : std::transform(txns.cbegin(), txns.cend(), std::inserter(later_txids, later_txids.end()),
47 : 2 : [](const auto& tx) { return tx->GetHash(); });
48 : :
49 [ + - ]: 1 : return IsTopoSortedPackage(txns, later_txids);
50 : 1 : }
51 : :
52 : 36 : bool IsConsistentPackage(const Package& txns)
53 : : {
54 : : // Don't allow any conflicting transactions, i.e. spending the same inputs, in a package.
55 : 36 : std::unordered_set<COutPoint, SaltedOutpointHasher> inputs_seen;
56 [ + + ]: 137 : for (const auto& tx : txns) {
57 [ + + ]: 104 : 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 [ + + ]: 1233 : for (const auto& input : tx->vin) {
65 [ + + ]: 1132 : 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 [ + - ]: 101 : std::transform(tx->vin.cbegin(), tx->vin.cend(), std::inserter(inputs_seen, inputs_seen.end()),
74 : 1130 : [](const auto& input) { return input.prevout; });
75 : : }
76 : : return true;
77 : 36 : }
78 : :
79 : 37 : bool IsWellFormedPackage(const Package& txns, PackageValidationState& state, bool require_sorted)
80 : : {
81 [ + + ]: 37 : const unsigned int package_count = txns.size();
82 : :
83 [ + + ]: 37 : if (package_count > MAX_PACKAGE_COUNT) {
84 [ + - + - ]: 1 : return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-too-many-transactions");
85 : : }
86 : :
87 : 36 : const int64_t total_weight = std::accumulate(txns.cbegin(), txns.cend(), 0,
88 : 110 : [](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 [ + + ]: 36 : if (package_count > 1 && total_weight > MAX_PACKAGE_WEIGHT) {
91 [ + - + - ]: 1 : return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-too-large");
92 : : }
93 : :
94 : 35 : std::unordered_set<uint256, SaltedTxidHasher> later_txids;
95 [ + - ]: 35 : std::transform(txns.cbegin(), txns.cend(), std::inserter(later_txids, later_txids.end()),
96 : 106 : [](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 [ + + ]: 35 : if (later_txids.size() != txns.size()) {
101 [ + - + - : 1 : 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 [ + - + - : 34 : if (require_sorted && !IsTopoSortedPackage(txns, later_txids)) {
+ + ]
109 [ + - + - : 2 : 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 [ + - + + ]: 32 : if (!IsConsistentPackage(txns)) {
114 [ + - + - : 1 : return state.Invalid(PackageValidationResult::PCKG_POLICY, "conflict-in-package");
+ - ]
115 : : }
116 : : return true;
117 : 35 : }
118 : :
119 : 34 : bool IsChildWithParents(const Package& package)
120 : : {
121 [ - + - + : 130 : assert(std::all_of(package.cbegin(), package.cend(), [](const auto& tx){return tx != nullptr;}));
- + - + -
+ - + - +
- + ]
122 [ + - ]: 34 : if (package.size() < 2) return false;
123 : :
124 : : // The package is expected to be sorted, so the last transaction is the child.
125 : 34 : const auto& child = package.back();
126 : 34 : std::unordered_set<uint256, SaltedTxidHasher> input_txids;
127 [ + - ]: 34 : std::transform(child->vin.cbegin(), child->vin.cend(),
128 : : std::inserter(input_txids, input_txids.end()),
129 : 133 : [](const auto& input) { return input.prevout.hash; });
130 : :
131 : : // Every transaction must be a parent of the last transaction in the package.
132 [ + - ]: 34 : return std::all_of(package.cbegin(), package.cend() - 1,
133 [ + + - + : 56 : [&input_txids](const auto& ptx) { return input_txids.count(ptx->GetHash()) > 0; });
- + - + -
+ + + -
+ ]
134 : 34 : }
135 : :
136 : 3 : bool IsChildWithParentsTree(const Package& package)
137 : : {
138 [ + - ]: 3 : if (!IsChildWithParents(package)) return false;
139 : 3 : std::unordered_set<uint256, SaltedTxidHasher> parent_txids;
140 [ + - ]: 3 : std::transform(package.cbegin(), package.cend() - 1, std::inserter(parent_txids, parent_txids.end()),
141 : 27 : [](const auto& ptx) { return ptx->GetHash(); });
142 : : // Each parent must not have an input who is one of the other parents.
143 [ + - ]: 30 : return std::all_of(package.cbegin(), package.cend() - 1, [&](const auto& ptx) {
144 [ + + ]: 53 : for (const auto& input : ptx->vin) {
145 [ + + ]: 27 : if (parent_txids.count(input.prevout.hash) > 0) return false;
146 : : }
147 : : return true;
148 : : });
149 : 3 : }
150 : :
151 : 16 : uint256 GetPackageHash(const std::vector<CTransactionRef>& transactions)
152 : : {
153 : : // Create a vector of the wtxids.
154 : 16 : std::vector<Wtxid> wtxids_copy;
155 [ + - ]: 16 : std::transform(transactions.cbegin(), transactions.cend(), std::back_inserter(wtxids_copy),
156 : 35 : [](const auto& tx){ return tx->GetWitnessHash(); });
157 : :
158 : : // Sort in ascending order
159 : 48 : std::sort(wtxids_copy.begin(), wtxids_copy.end(), [](const auto& lhs, const auto& rhs) {
160 : 32 : return std::lexicographical_compare(std::make_reverse_iterator(lhs.end()), std::make_reverse_iterator(lhs.begin()),
161 : 32 : 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 [ + - ]: 16 : HashWriter hashwriter;
166 [ + + ]: 51 : for (const auto& wtxid : wtxids_copy) {
167 [ + - ]: 70 : hashwriter << wtxid;
168 : : }
169 [ + - ]: 32 : return hashwriter.GetSHA256();
170 : 16 : }
|
