1  // Copyright (c) 2016-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/rbf.h>
  6  
  7  #include <consensus/amount.h>
  8  #include <kernel/mempool_entry.h>
  9  #include <policy/feerate.h>
 10  #include <primitives/transaction.h>
 11  #include <sync.h>
 12  #include <tinyformat.h>
 13  #include <txmempool.h>
 14  #include <uint256.h>
 15  #include <util/check.h>
 16  #include <util/moneystr.h>
 17  #include <util/rbf.h>
 18  
 19  #include <limits>
 20  #include <vector>
 21  
 22  #include <compare>
 23  
 24  RBFTransactionState IsRBFOptIn(const CTransaction& tx, const CTxMemPool& pool)
 25  {
 26      AssertLockHeld(pool.cs);
 27  
 28      // First check the transaction itself.
 29      if (SignalsOptInRBF(tx)) {
 30          return RBFTransactionState::REPLACEABLE_BIP125;
 31      }
 32  
 33      // If this transaction is not in our mempool, then we can't be sure
 34      // we will know about all its inputs.
 35      if (!pool.exists(GenTxid::Txid(tx.GetHash()))) {
 36          return RBFTransactionState::UNKNOWN;
 37      }
 38  
 39      // If all the inputs have nSequence >= maxint-1, it still might be
 40      // signaled for RBF if any unconfirmed parents have signaled.
 41      const auto& entry{*Assert(pool.GetEntry(tx.GetHash()))};
 42      auto ancestors{pool.AssumeCalculateMemPoolAncestors(__func__, entry, CTxMemPool::Limits::NoLimits(),
 43                                                          /*fSearchForParents=*/false)};
 44  
 45      for (CTxMemPool::txiter it : ancestors) {
 46          if (SignalsOptInRBF(it->GetTx())) {
 47              return RBFTransactionState::REPLACEABLE_BIP125;
 48          }
 49      }
 50      return RBFTransactionState::FINAL;
 51  }
 52  
 53  RBFTransactionState IsRBFOptInEmptyMempool(const CTransaction& tx)
 54  {
 55      // If we don't have a local mempool we can only check the transaction itself.
 56      return SignalsOptInRBF(tx) ? RBFTransactionState::REPLACEABLE_BIP125 : RBFTransactionState::UNKNOWN;
 57  }
 58  
 59  std::optional<std::string> GetEntriesForConflicts(const CTransaction& tx,
 60                                                    CTxMemPool& pool,
 61                                                    const CTxMemPool::setEntries& iters_conflicting,
 62                                                    CTxMemPool::setEntries& all_conflicts)
 63  {
 64      AssertLockHeld(pool.cs);
 65      const uint256 txid = tx.GetHash();
 66      uint64_t nConflictingCount = 0;
 67      for (const auto& mi : iters_conflicting) {
 68          nConflictingCount += mi->GetCountWithDescendants();
 69          // Rule #5: don't consider replacing more than MAX_REPLACEMENT_CANDIDATES
 70          // entries from the mempool. This potentially overestimates the number of actual
 71          // descendants (i.e. if multiple conflicts share a descendant, it will be counted multiple
 72          // times), but we just want to be conservative to avoid doing too much work.
 73          if (nConflictingCount > MAX_REPLACEMENT_CANDIDATES) {
 74              return strprintf("rejecting replacement %s; too many potential replacements (%d > %d)\n",
 75                               txid.ToString(),
 76                               nConflictingCount,
 77                               MAX_REPLACEMENT_CANDIDATES);
 78          }
 79      }
 80      // Calculate the set of all transactions that would have to be evicted.
 81      for (CTxMemPool::txiter it : iters_conflicting) {
 82          pool.CalculateDescendants(it, all_conflicts);
 83      }
 84      return std::nullopt;
 85  }
 86  
 87  std::optional<std::string> HasNoNewUnconfirmed(const CTransaction& tx,
 88                                                 const CTxMemPool& pool,
 89                                                 const CTxMemPool::setEntries& iters_conflicting)
 90  {
 91      AssertLockHeld(pool.cs);
 92      std::set<uint256> parents_of_conflicts;
 93      for (const auto& mi : iters_conflicting) {
 94          for (const CTxIn& txin : mi->GetTx().vin) {
 95              parents_of_conflicts.insert(txin.prevout.hash);
 96          }
 97      }
 98  
 99      for (unsigned int j = 0; j < tx.vin.size(); j++) {
100          // Rule #2: We don't want to accept replacements that require low feerate junk to be
101          // mined first.  Ideally we'd keep track of the ancestor feerates and make the decision
102          // based on that, but for now requiring all new inputs to be confirmed works.
103          //
104          // Note that if you relax this to make RBF a little more useful, this may break the
105          // CalculateMempoolAncestors RBF relaxation which subtracts the conflict count/size from the
106          // descendant limit.
107          if (!parents_of_conflicts.count(tx.vin[j].prevout.hash)) {
108              // Rather than check the UTXO set - potentially expensive - it's cheaper to just check
109              // if the new input refers to a tx that's in the mempool.
110              if (pool.exists(GenTxid::Txid(tx.vin[j].prevout.hash))) {
111                  return strprintf("replacement %s adds unconfirmed input, idx %d",
112                                   tx.GetHash().ToString(), j);
113              }
114          }
115      }
116      return std::nullopt;
117  }
118  
119  std::optional<std::string> EntriesAndTxidsDisjoint(const CTxMemPool::setEntries& ancestors,
120                                                     const std::set<Txid>& direct_conflicts,
121                                                     const uint256& txid)
122  {
123      for (CTxMemPool::txiter ancestorIt : ancestors) {
124          const Txid& hashAncestor = ancestorIt->GetTx().GetHash();
125          if (direct_conflicts.count(hashAncestor)) {
126              return strprintf("%s spends conflicting transaction %s",
127                               txid.ToString(),
128                               hashAncestor.ToString());
129          }
130      }
131      return std::nullopt;
132  }
133  
134  std::optional<std::string> PaysMoreThanConflicts(const CTxMemPool::setEntries& iters_conflicting,
135                                                   CFeeRate replacement_feerate,
136                                                   const uint256& txid)
137  {
138      for (const auto& mi : iters_conflicting) {
139          // Don't allow the replacement to reduce the feerate of the mempool.
140          //
141          // We usually don't want to accept replacements with lower feerates than what they replaced
142          // as that would lower the feerate of the next block. Requiring that the feerate always be
143          // increased is also an easy-to-reason about way to prevent DoS attacks via replacements.
144          //
145          // We only consider the feerates of transactions being directly replaced, not their indirect
146          // descendants. While that does mean high feerate children are ignored when deciding whether
147          // or not to replace, we do require the replacement to pay more overall fees too, mitigating
148          // most cases.
149          CFeeRate original_feerate(mi->GetModifiedFee(), mi->GetTxSize());
150          if (replacement_feerate <= original_feerate) {
151              return strprintf("rejecting replacement %s; new feerate %s <= old feerate %s",
152                               txid.ToString(),
153                               replacement_feerate.ToString(),
154                               original_feerate.ToString());
155          }
156      }
157      return std::nullopt;
158  }
159  
160  std::optional<std::string> PaysForRBF(CAmount original_fees,
161                                        CAmount replacement_fees,
162                                        size_t replacement_vsize,
163                                        CFeeRate relay_fee,
164                                        const uint256& txid)
165  {
166      // Rule #3: The replacement fees must be greater than or equal to fees of the
167      // transactions it replaces, otherwise the bandwidth used by those conflicting transactions
168      // would not be paid for.
169      if (replacement_fees < original_fees) {
170          return strprintf("rejecting replacement %s, less fees than conflicting txs; %s < %s",
171                           txid.ToString(), FormatMoney(replacement_fees), FormatMoney(original_fees));
172      }
173  
174      // Rule #4: The new transaction must pay for its own bandwidth. Otherwise, we have a DoS
175      // vector where attackers can cause a transaction to be replaced (and relayed) repeatedly by
176      // increasing the fee by tiny amounts.
177      CAmount additional_fees = replacement_fees - original_fees;
178      if (additional_fees < relay_fee.GetFee(replacement_vsize)) {
179          return strprintf("rejecting replacement %s, not enough additional fees to relay; %s < %s",
180                           txid.ToString(),
181                           FormatMoney(additional_fees),
182                           FormatMoney(relay_fee.GetFee(replacement_vsize)));
183      }
184      return std::nullopt;
185  }
186  
187  std::optional<std::pair<DiagramCheckError, std::string>> ImprovesFeerateDiagram(CTxMemPool& pool,
188                                                  const CTxMemPool::setEntries& direct_conflicts,
189                                                  const CTxMemPool::setEntries& all_conflicts,
190                                                  CAmount replacement_fees,
191                                                  int64_t replacement_vsize)
192  {
193      // Require that the replacement strictly improve the mempool's feerate diagram.
194      std::vector<FeeFrac> old_diagram, new_diagram;
195  
196      const auto diagram_results{pool.CalculateFeerateDiagramsForRBF(replacement_fees, replacement_vsize, direct_conflicts, all_conflicts)};
197  
198      if (!diagram_results.has_value()) {
199          return std::make_pair(DiagramCheckError::UNCALCULABLE, util::ErrorString(diagram_results).original);
200      }
201  
202      if (!std::is_gt(CompareFeerateDiagram(diagram_results.value().second, diagram_results.value().first))) {
203          return std::make_pair(DiagramCheckError::FAILURE, "insufficient feerate: does not improve feerate diagram");
204      }
205      return std::nullopt;
206  }