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 #ifndef BITCOIN_NODE_MINI_MINER_H
6 #define BITCOIN_NODE_MINI_MINER_H
7 8 #include <attributes.h>
9 #include <consensus/amount.h>
10 #include <primitives/transaction.h>
11 12 #include <cstdint>
13 #include <map>
14 #include <optional>
15 #include <set>
16 #include <vector>
17 18 class CFeeRate;
19 class CTxMemPool;
20 21 namespace node {
22 23 // Container for tracking updates to ancestor feerate as we include ancestors in the "block"
24 class MiniMinerMempoolEntry
25 {
26 const CTransactionRef tx;
27 const int64_t vsize_individual;
28 int64_t vsize_with_ancestors;
29 const CAmount fee_individual;
30 CAmount fee_with_ancestors;
31 32 // This class must be constructed while holding mempool.cs. After construction, the object's
33 // methods can be called without holding that lock.
34 35 public:
36 explicit MiniMinerMempoolEntry(const CTransactionRef& tx_in,
37 int64_t vsize_self,
38 int64_t vsize_ancestor,
39 CAmount fee_self,
40 CAmount fee_ancestor):
41 tx{tx_in},
42 vsize_individual{vsize_self},
43 vsize_with_ancestors{vsize_ancestor},
44 fee_individual{fee_self},
45 fee_with_ancestors{fee_ancestor}
46 { }
47 48 CAmount GetModifiedFee() const { return fee_individual; }
49 CAmount GetModFeesWithAncestors() const { return fee_with_ancestors; }
50 int64_t GetTxSize() const { return vsize_individual; }
51 int64_t GetSizeWithAncestors() const { return vsize_with_ancestors; }
52 const CTransaction& GetTx() const LIFETIMEBOUND { return *tx; }
53 void UpdateAncestorState(int64_t vsize_change, CAmount fee_change) {
54 vsize_with_ancestors += vsize_change;
55 fee_with_ancestors += fee_change;
56 }
57 };
58 59 // Comparator needed for std::set<MockEntryMap::iterator>
60 struct IteratorComparator
61 {
62 template<typename I>
63 bool operator()(const I& a, const I& b) const
64 {
65 return a->first < b->first;
66 }
67 };
68 69 /** A minimal version of BlockAssembler, using the same ancestor set scoring algorithm. Allows us to
70 * run this algorithm on a limited set of transactions (e.g. subset of mempool or transactions that
71 * are not yet in mempool) instead of the entire mempool, ignoring consensus rules.
72 * Callers may use this to:
73 * - Calculate the "bump fee" needed to spend an unconfirmed UTXO at a given feerate
74 * - "Linearize" a list of transactions to see the order in which they would be selected for
75 * inclusion in a block
76 */
77 class MiniMiner
78 {
79 // When true, a caller may use CalculateBumpFees(). Becomes false if we failed to retrieve
80 // mempool entries (i.e. cluster size too large) or bump fees have already been calculated.
81 bool m_ready_to_calculate{true};
82 83 // Set once per lifetime, fill in during initialization.
84 // txids of to-be-replaced transactions
85 std::set<Txid> m_to_be_replaced;
86 87 // If multiple argument outpoints correspond to the same transaction, cache them together in
88 // a single entry indexed by txid. Then we can just work with txids since all outpoints from
89 // the same tx will have the same bumpfee. Excludes non-mempool transactions.
90 std::map<Txid, std::vector<COutPoint>> m_requested_outpoints_by_txid;
91 92 // Txid to a number representing the order in which this transaction was included (smaller
93 // number = included earlier). Transactions included in an ancestor set together have the same
94 // sequence number.
95 std::map<Txid, uint32_t> m_inclusion_order;
96 // What we're trying to calculate. Outpoint to the fee needed to bring the transaction to the target feerate.
97 std::map<COutPoint, CAmount> m_bump_fees;
98 99 // The constructed block template
100 std::set<Txid> m_in_block;
101 102 // Information on the current status of the block
103 CAmount m_total_fees{0};
104 int32_t m_total_vsize{0};
105 106 /** Main data structure holding the entries, can be indexed by txid */
107 std::map<Txid, MiniMinerMempoolEntry> m_entries_by_txid;
108 using MockEntryMap = decltype(m_entries_by_txid);
109 110 /** Vector of entries, can be sorted by ancestor feerate. */
111 std::vector<MockEntryMap::iterator> m_entries;
112 113 /** Map of txid to its descendants. Should be inclusive. */
114 std::map<Txid, std::vector<MockEntryMap::iterator>> m_descendant_set_by_txid;
115 116 /** Consider this ancestor package "mined" so remove all these entries from our data structures. */
117 void DeleteAncestorPackage(const std::set<MockEntryMap::iterator, IteratorComparator>& ancestors);
118 119 /** Perform some checks. */
120 void SanityCheck() const;
121 122 public:
123 /** Returns true if CalculateBumpFees may be called, false if not. */
124 bool IsReadyToCalculate() const { return m_ready_to_calculate; }
125 126 /** Build a block template until the target feerate is hit. If target_feerate is not given,
127 * builds a block template until all transactions have been selected. */
128 void BuildMockTemplate(std::optional<CFeeRate> target_feerate);
129 130 /** Returns set of txids in the block template if one has been constructed. */
131 std::set<Txid> GetMockTemplateTxids() const { return m_in_block; }
132 133 /** Constructor that takes a list of outpoints that may or may not belong to transactions in the
134 * mempool. Copies out information about the relevant transactions in the mempool into
135 * MiniMinerMempoolEntrys.
136 */
137 MiniMiner(const CTxMemPool& mempool, const std::vector<COutPoint>& outpoints);
138 139 /** Constructor in which the MiniMinerMempoolEntry entries have been constructed manually.
140 * It is assumed that all entries are unique and their values are correct, otherwise results
141 * computed by MiniMiner may be incorrect. Callers should check IsReadyToCalculate() after
142 * construction.
143 * @param[in] descendant_caches A map from each transaction to the set of txids of this
144 * transaction's descendant set, including itself. Each tx in
145 * manual_entries must have a corresponding entry in this map, and
146 * all of the txids in a descendant set must correspond to a tx in
147 * manual_entries.
148 */
149 MiniMiner(const std::vector<MiniMinerMempoolEntry>& manual_entries,
150 const std::map<Txid, std::set<Txid>>& descendant_caches);
151 152 /** Construct a new block template and, for each outpoint corresponding to a transaction that
153 * did not make it into the block, calculate the cost of bumping those transactions (and their
154 * ancestors) to the minimum feerate. Returns a map from outpoint to bump fee, or an empty map
155 * if they cannot be calculated. */
156 std::map<COutPoint, CAmount> CalculateBumpFees(const CFeeRate& target_feerate);
157 158 /** Construct a new block template and, calculate the cost of bumping all transactions that did
159 * not make it into the block to the target feerate. Returns the total bump fee, or std::nullopt
160 * if it cannot be calculated. */
161 std::optional<CAmount> CalculateTotalBumpFees(const CFeeRate& target_feerate);
162 163 /** Construct a new block template with all of the transactions and calculate the order in which
164 * they are selected. Returns the sequence number (lower = selected earlier) with which each
165 * transaction was selected, indexed by txid, or an empty map if it cannot be calculated.
166 */
167 std::map<Txid, uint32_t> Linearize();
168 };
169 } // namespace node
170 171 #endif // BITCOIN_NODE_MINI_MINER_H
172