Bitcoin Core  27.99.0
P2P Digital Currency
packages.cpp
Go to the documentation of this file.
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>
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 
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 }
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 }
#define Assume(val)
Assume is the identity function.
Definition: check.h:89
A writer stream (for serialization) that computes a 256-bit hash.
Definition: hash.h:101
uint256 GetSHA256()
Compute the SHA256 hash of all data written to this object.
Definition: hash.h:126
bool Invalid(Result result, const std::string &reject_reason="", const std::string &debug_message="")
Definition: validation.h:105
256-bit opaque blob.
Definition: uint256.h:106
volatile double sum
Definition: examples.cpp:10
bool IsChildWithParents(const Package &package)
Context-free check that a package is exactly one child and its parents; not all parents need to be pr...
Definition: packages.cpp:119
bool IsConsistentPackage(const Package &txns)
Checks that these transactions don't conflict, i.e., spend the same prevout.
Definition: packages.cpp:52
bool IsWellFormedPackage(const Package &txns, PackageValidationState &state, bool require_sorted)
Context-free package policy checks:
Definition: packages.cpp:79
bool IsChildWithParentsTree(const Package &package)
Context-free check that a package IsChildWithParents() and none of the parents depend on each other (...
Definition: packages.cpp:136
uint256 GetPackageHash(const std::vector< CTransactionRef > &transactions)
Get the hash of these transactions' wtxids, concatenated in lexicographical order (treating the wtxid...
Definition: packages.cpp:151
bool IsTopoSortedPackage(const Package &txns, std::unordered_set< uint256, SaltedTxidHasher > &later_txids)
IsTopoSortedPackage where a set of txids has been pre-populated.
Definition: packages.cpp:19
std::vector< CTransactionRef > Package
A package is an ordered list of transactions.
Definition: packages.h:50
static constexpr uint32_t MAX_PACKAGE_WEIGHT
Default maximum total weight of transactions in a package in weight to allow for context-less checks.
Definition: packages.h:24
static constexpr uint32_t MAX_PACKAGE_COUNT
Default maximum number of transactions in a package.
Definition: packages.h:19
@ PCKG_POLICY
The package itself is invalid (e.g. too many transactions).
assert(!tx.IsCoinBase())