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). */
19bool 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
43bool 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
52bool 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
79bool 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
119bool 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
136bool 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
151uint256 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