1 // Copyright (c) 2022-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/truc_policy.h>
6 7 #include <coins.h>
8 #include <consensus/amount.h>
9 #include <tinyformat.h>
10 #include <util/check.h>
11 12 #include <algorithm>
13 #include <numeric>
14 #include <vector>
15 16 /** Helper for PackageTRUCChecks: Returns a vector containing the indices of transactions (within
17 * package) that are direct parents of ptx. */
18 std::vector<size_t> FindInPackageParents(const Package& package, const CTransactionRef& ptx)
19 {
20 std::vector<size_t> in_package_parents;
21 22 std::set<Txid> possible_parents;
23 for (auto &input : ptx->vin) {
24 possible_parents.insert(input.prevout.hash);
25 }
26 27 for (size_t i{0}; i < package.size(); ++i) {
28 const auto& tx = package.at(i);
29 // We assume the package is sorted, so that we don't need to continue
30 // looking past the transaction itself.
31 if (&(*tx) == &(*ptx)) break;
32 if (possible_parents.contains(tx->GetHash())) {
33 in_package_parents.push_back(i);
34 }
35 }
36 return in_package_parents;
37 }
38 39 /** Helper for PackageTRUCChecks, storing info for a mempool or package parent. */
40 struct ParentInfo {
41 /** Txid used to identify this parent by prevout */
42 const Txid& m_txid;
43 /** Wtxid used for debug string */
44 const Wtxid& m_wtxid;
45 /** version used to check inheritance of TRUC and non-TRUC */
46 decltype(CTransaction::version) m_version;
47 /** If parent is in mempool, whether it has any descendants in mempool. */
48 bool m_has_mempool_descendant;
49 50 ParentInfo() = delete;
51 ParentInfo(const Txid& txid, const Wtxid& wtxid, decltype(CTransaction::version) version, bool has_mempool_descendant) :
52 m_txid{txid}, m_wtxid{wtxid}, m_version{version},
53 m_has_mempool_descendant{has_mempool_descendant}
54 {}
55 };
56 57 std::optional<std::string> PackageTRUCChecks(const CTxMemPool& pool, const CTransactionRef& ptx, int64_t vsize,
58 const Package& package,
59 const std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef>& mempool_parents)
60 {
61 AssertLockHeld(pool.cs);
62 // This function is specialized for these limits, and must be reimplemented if they ever change.
63 static_assert(TRUC_ANCESTOR_LIMIT == 2);
64 static_assert(TRUC_DESCENDANT_LIMIT == 2);
65 66 const auto in_package_parents{FindInPackageParents(package, ptx)};
67 68 // Now we have all parents, so we can start checking TRUC rules.
69 if (ptx->version == TRUC_VERSION) {
70 // SingleTRUCChecks should have checked this already.
71 if (!Assume(vsize <= TRUC_MAX_VSIZE)) {
72 return strprintf("version=3 tx %s (wtxid=%s) is too big: %u > %u virtual bytes",
73 ptx->GetHash().ToString(), ptx->GetWitnessHash().ToString(), vsize, TRUC_MAX_VSIZE);
74 }
75 76 if (mempool_parents.size() + in_package_parents.size() + 1 > TRUC_ANCESTOR_LIMIT) {
77 return strprintf("tx %s (wtxid=%s) would have too many ancestors",
78 ptx->GetHash().ToString(), ptx->GetWitnessHash().ToString());
79 }
80 81 if (mempool_parents.size()) {
82 if (pool.GetAncestorCount(mempool_parents[0]) + in_package_parents.size() + 1 > TRUC_ANCESTOR_LIMIT) {
83 return strprintf("tx %s (wtxid=%s) would have too many ancestors",
84 ptx->GetHash().ToString(), ptx->GetWitnessHash().ToString());
85 }
86 }
87 88 const bool has_parent{mempool_parents.size() + in_package_parents.size() > 0};
89 if (has_parent) {
90 // A TRUC child cannot be too large.
91 if (vsize > TRUC_CHILD_MAX_VSIZE) {
92 return strprintf("version=3 child tx %s (wtxid=%s) is too big: %u > %u virtual bytes",
93 ptx->GetHash().ToString(), ptx->GetWitnessHash().ToString(),
94 vsize, TRUC_CHILD_MAX_VSIZE);
95 }
96 97 // Exactly 1 parent exists, either in mempool or package. Find it.
98 const auto parent_info = [&] {
99 if (mempool_parents.size() > 0) {
100 const auto& mempool_parent = &mempool_parents[0].get();
101 return ParentInfo{mempool_parent->GetTx().GetHash(),
102 mempool_parent->GetTx().GetWitnessHash(),
103 mempool_parent->GetTx().version,
104 /*has_mempool_descendant=*/pool.GetDescendantCount(*mempool_parent) > 1};
105 } else {
106 auto& parent_index = in_package_parents.front();
107 auto& package_parent = package.at(parent_index);
108 return ParentInfo{package_parent->GetHash(),
109 package_parent->GetWitnessHash(),
110 package_parent->version,
111 /*has_mempool_descendant=*/false};
112 }
113 }();
114 115 // If there is a parent, it must have the right version.
116 if (parent_info.m_version != TRUC_VERSION) {
117 return strprintf("version=3 tx %s (wtxid=%s) cannot spend from non-version=3 tx %s (wtxid=%s)",
118 ptx->GetHash().ToString(), ptx->GetWitnessHash().ToString(),
119 parent_info.m_txid.ToString(), parent_info.m_wtxid.ToString());
120 }
121 122 for (const auto& package_tx : package) {
123 // Skip same tx.
124 if (&(*package_tx) == &(*ptx)) continue;
125 126 for (auto& input : package_tx->vin) {
127 // Fail if we find another tx with the same parent. We don't check whether the
128 // sibling is to-be-replaced (done in SingleTRUCChecks) because these transactions
129 // are within the same package.
130 if (input.prevout.hash == parent_info.m_txid) {
131 return strprintf("tx %s (wtxid=%s) would exceed descendant count limit",
132 parent_info.m_txid.ToString(),
133 parent_info.m_wtxid.ToString());
134 }
135 136 // This tx can't have both a parent and an in-package child.
137 if (input.prevout.hash == ptx->GetHash()) {
138 return strprintf("tx %s (wtxid=%s) would have too many ancestors",
139 package_tx->GetHash().ToString(), package_tx->GetWitnessHash().ToString());
140 }
141 }
142 }
143 144 if (parent_info.m_has_mempool_descendant) {
145 return strprintf("tx %s (wtxid=%s) would exceed descendant count limit",
146 parent_info.m_txid.ToString(), parent_info.m_wtxid.ToString());
147 }
148 }
149 } else {
150 // Non-TRUC transactions cannot have TRUC parents.
151 for (auto it : mempool_parents) {
152 if (it.get().GetTx().version == TRUC_VERSION) {
153 return strprintf("non-version=3 tx %s (wtxid=%s) cannot spend from version=3 tx %s (wtxid=%s)",
154 ptx->GetHash().ToString(), ptx->GetWitnessHash().ToString(),
155 it.get().GetSharedTx()->GetHash().ToString(), it.get().GetSharedTx()->GetWitnessHash().ToString());
156 }
157 }
158 for (const auto& index: in_package_parents) {
159 if (package.at(index)->version == TRUC_VERSION) {
160 return strprintf("non-version=3 tx %s (wtxid=%s) cannot spend from version=3 tx %s (wtxid=%s)",
161 ptx->GetHash().ToString(),
162 ptx->GetWitnessHash().ToString(),
163 package.at(index)->GetHash().ToString(),
164 package.at(index)->GetWitnessHash().ToString());
165 }
166 }
167 }
168 return std::nullopt;
169 }
170 171 std::optional<std::pair<std::string, CTransactionRef>> SingleTRUCChecks(const CTxMemPool& pool, const CTransactionRef& ptx,
172 const std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef>& mempool_parents,
173 const std::set<Txid>& direct_conflicts,
174 int64_t vsize)
175 {
176 AssertLockHeld(pool.cs);
177 // Check TRUC and non-TRUC inheritance.
178 for (const auto& entry_ref : mempool_parents) {
179 const auto& entry = &entry_ref.get();
180 if (ptx->version != TRUC_VERSION && entry->GetTx().version == TRUC_VERSION) {
181 return std::make_pair(strprintf("non-version=3 tx %s (wtxid=%s) cannot spend from version=3 tx %s (wtxid=%s)",
182 ptx->GetHash().ToString(), ptx->GetWitnessHash().ToString(),
183 entry->GetSharedTx()->GetHash().ToString(), entry->GetSharedTx()->GetWitnessHash().ToString()),
184 nullptr);
185 } else if (ptx->version == TRUC_VERSION && entry->GetTx().version != TRUC_VERSION) {
186 return std::make_pair(strprintf("version=3 tx %s (wtxid=%s) cannot spend from non-version=3 tx %s (wtxid=%s)",
187 ptx->GetHash().ToString(), ptx->GetWitnessHash().ToString(),
188 entry->GetSharedTx()->GetHash().ToString(), entry->GetSharedTx()->GetWitnessHash().ToString()),
189 nullptr);
190 }
191 }
192 193 // This function is specialized for these limits, and must be reimplemented if they ever change.
194 static_assert(TRUC_ANCESTOR_LIMIT == 2);
195 static_assert(TRUC_DESCENDANT_LIMIT == 2);
196 197 // The rest of the rules only apply to transactions with version=3.
198 if (ptx->version != TRUC_VERSION) return std::nullopt;
199 200 if (vsize > TRUC_MAX_VSIZE) {
201 return std::make_pair(strprintf("version=3 tx %s (wtxid=%s) is too big: %u > %u virtual bytes",
202 ptx->GetHash().ToString(), ptx->GetWitnessHash().ToString(), vsize, TRUC_MAX_VSIZE),
203 nullptr);
204 }
205 206 // Check that TRUC_ANCESTOR_LIMIT would not be violated.
207 if (mempool_parents.size() + 1 > TRUC_ANCESTOR_LIMIT) {
208 return std::make_pair(strprintf("tx %s (wtxid=%s) would have too many ancestors",
209 ptx->GetHash().ToString(), ptx->GetWitnessHash().ToString()),
210 nullptr);
211 }
212 213 // Remaining checks only pertain to transactions with unconfirmed ancestors.
214 if (mempool_parents.size() > 0) {
215 // Ensure that the in-mempool parent doesn't have any additional
216 // ancestors, as that would also be a violation.
217 if (pool.GetAncestorCount(mempool_parents[0]) + 1 > TRUC_ANCESTOR_LIMIT) {
218 return std::make_pair(strprintf("tx %s (wtxid=%s) would have too many ancestors",
219 ptx->GetHash().ToString(), ptx->GetWitnessHash().ToString()),
220 nullptr);
221 }
222 // If this transaction spends TRUC parents, it cannot be too large.
223 if (vsize > TRUC_CHILD_MAX_VSIZE) {
224 return std::make_pair(strprintf("version=3 child tx %s (wtxid=%s) is too big: %u > %u virtual bytes",
225 ptx->GetHash().ToString(), ptx->GetWitnessHash().ToString(), vsize, TRUC_CHILD_MAX_VSIZE),
226 nullptr);
227 }
228 229 // Check the descendant counts of in-mempool parents.
230 const auto& parent_entry = mempool_parents[0].get();
231 // If there are any parents, this is the only child allowed. The parent cannot have any
232 // other descendants. We handle the possibility of multiple children as that case is
233 // possible through a reorg.
234 CTxMemPool::setEntries descendants;
235 auto parent_it = pool.CalculateDescendants(parent_entry, descendants);
236 descendants.erase(parent_it);
237 // Don't double-count a transaction that is going to be replaced. This logic assumes that
238 // any descendant of the TRUC transaction is a direct child, which makes sense because a
239 // TRUC transaction can only have 1 descendant.
240 const bool child_will_be_replaced = !descendants.empty() &&
241 std::any_of(descendants.cbegin(), descendants.cend(),
242 [&direct_conflicts](const CTxMemPool::txiter& child){return direct_conflicts.contains(child->GetTx().GetHash());});
243 if (pool.GetDescendantCount(parent_entry) + 1 > TRUC_DESCENDANT_LIMIT && !child_will_be_replaced) {
244 // Allow sibling eviction for TRUC transaction: if another child already exists, even if
245 // we don't conflict inputs with it, consider evicting it under RBF rules. We rely on TRUC rules
246 // only permitting 1 descendant, as otherwise we would need to have logic for deciding
247 // which descendant to evict. Skip if this isn't true, e.g. if the transaction has
248 // multiple children or the sibling also has descendants due to a reorg.
249 const bool consider_sibling_eviction{pool.GetDescendantCount(parent_entry) == 2 &&
250 pool.GetAncestorCount(**descendants.begin()) == 2};
251 252 // Return the sibling if its eviction can be considered. Provide the "descendant count
253 // limit" string either way, as the caller may decide not to do sibling eviction.
254 return std::make_pair(strprintf("tx %u (wtxid=%s) would exceed descendant count limit",
255 parent_entry.GetSharedTx()->GetHash().ToString(),
256 parent_entry.GetSharedTx()->GetWitnessHash().ToString()),
257 consider_sibling_eviction ? (*descendants.begin())->GetSharedTx() : nullptr);
258 }
259 }
260 return std::nullopt;
261 }
262