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