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. */
18std::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. */
40struct 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
57std::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
171std::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};