rbf.cpp
1 // Copyright (c) 2020-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 <node/mempool_args.h> 6 #include <policy/rbf.h> 7 #include <primitives/transaction.h> 8 #include <sync.h> 9 #include <test/fuzz/FuzzedDataProvider.h> 10 #include <test/fuzz/fuzz.h> 11 #include <test/fuzz/util.h> 12 #include <test/fuzz/util/mempool.h> 13 #include <test/util/setup_common.h> 14 #include <test/util/time.h> 15 #include <test/util/txmempool.h> 16 #include <txmempool.h> 17 #include <util/check.h> 18 #include <util/translation.h> 19 20 #include <cstdint> 21 #include <optional> 22 #include <string> 23 #include <vector> 24 25 namespace { 26 const BasicTestingSetup* g_setup; 27 } // namespace 28 29 const int NUM_ITERS = 10000; 30 31 std::vector<COutPoint> g_outpoints; 32 33 void initialize_rbf() 34 { 35 static const auto testing_setup = MakeNoLogFileContext<>(); 36 g_setup = testing_setup.get(); 37 } 38 39 void initialize_package_rbf() 40 { 41 static const auto testing_setup = MakeNoLogFileContext<>(); 42 g_setup = testing_setup.get(); 43 44 // Create a fixed set of unique "UTXOs" to source parents from 45 // to avoid fuzzer giving circular references 46 for (int i = 0; i < NUM_ITERS; ++i) { 47 g_outpoints.emplace_back(); 48 g_outpoints.back().n = i; 49 } 50 51 } 52 53 FUZZ_TARGET(rbf, .init = initialize_rbf) 54 { 55 SeedRandomStateForTest(SeedRand::ZEROS); 56 FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size()); 57 NodeClockContext clock_ctx{ConsumeTime(fuzzed_data_provider)}; 58 std::optional<CMutableTransaction> mtx = ConsumeDeserializable<CMutableTransaction>(fuzzed_data_provider, TX_WITH_WITNESS); 59 if (!mtx) { 60 return; 61 } 62 63 bilingual_str error; 64 CTxMemPool pool{MemPoolOptionsForTest(g_setup->m_node), error}; 65 Assert(error.empty()); 66 67 LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), NUM_ITERS) 68 { 69 const std::optional<CMutableTransaction> another_mtx = ConsumeDeserializable<CMutableTransaction>(fuzzed_data_provider, TX_WITH_WITNESS); 70 if (!another_mtx) { 71 break; 72 } 73 const CTransaction another_tx{*another_mtx}; 74 if (fuzzed_data_provider.ConsumeBool() && !mtx->vin.empty()) { 75 mtx->vin[0].prevout = COutPoint{another_tx.GetHash(), 0}; 76 } 77 LOCK2(cs_main, pool.cs); 78 if (!pool.GetIter(another_tx.GetHash())) { 79 TryAddToMempool(pool, ConsumeTxMemPoolEntry(fuzzed_data_provider, another_tx)); 80 } 81 } 82 const CTransaction tx{*mtx}; 83 if (fuzzed_data_provider.ConsumeBool()) { 84 LOCK2(cs_main, pool.cs); 85 if (!pool.GetIter(tx.GetHash())) { 86 TryAddToMempool(pool, ConsumeTxMemPoolEntry(fuzzed_data_provider, tx)); 87 } 88 } 89 { 90 LOCK(pool.cs); 91 (void)IsRBFOptIn(tx, pool); 92 } 93 } 94 95 FUZZ_TARGET(package_rbf, .init = initialize_package_rbf) 96 { 97 SeedRandomStateForTest(SeedRand::ZEROS); 98 FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size()); 99 NodeClockContext clock_ctx{ConsumeTime(fuzzed_data_provider)}; 100 101 // "Real" virtual size is not important for this test since ConsumeTxMemPoolEntry generates its own virtual size values 102 // so we construct small transactions for performance reasons. Child simply needs an input for later to perhaps connect to parent. 103 CMutableTransaction child; 104 child.vin.resize(1); 105 106 bilingual_str error; 107 CTxMemPool pool{MemPoolOptionsForTest(g_setup->m_node), error}; 108 Assert(error.empty()); 109 110 // Add a bunch of parent-child pairs to the mempool, and remember them. 111 std::vector<CTransaction> mempool_txs; 112 uint32_t iter{0}; 113 114 // Keep track of the total vsize of CTxMemPoolEntry's being added to the mempool to avoid overflow 115 // Add replacement_vsize since this is added to new diagram during RBF check 116 std::optional<CMutableTransaction> replacement_tx = ConsumeDeserializable<CMutableTransaction>(fuzzed_data_provider, TX_WITH_WITNESS); 117 if (!replacement_tx) { 118 return; 119 } 120 replacement_tx->vin.resize(1); 121 replacement_tx->vin[0].prevout = g_outpoints.at(iter++); 122 CTransaction replacement_tx_final{*replacement_tx}; 123 auto replacement_entry = ConsumeTxMemPoolEntry(fuzzed_data_provider, replacement_tx_final); 124 int32_t replacement_weight = replacement_entry.GetAdjustedWeight(); 125 // Ensure that we don't hit FeeFrac limits, as we store TxGraph entries in terms of FeePerWeight 126 int64_t running_vsize_total{replacement_entry.GetTxSize()}; 127 128 LOCK2(cs_main, pool.cs); 129 130 while (fuzzed_data_provider.ConsumeBool()) { 131 if (iter >= NUM_ITERS) break; 132 133 // Make sure txns only have one input, and that a unique input is given to avoid circular references 134 CMutableTransaction parent; 135 parent.vin.resize(1); 136 parent.vin[0].prevout = g_outpoints.at(iter++); 137 parent.vout.emplace_back(0, CScript()); 138 139 mempool_txs.emplace_back(parent); 140 const auto parent_entry = ConsumeTxMemPoolEntry(fuzzed_data_provider, mempool_txs.back()); 141 running_vsize_total += parent_entry.GetTxSize(); 142 if (running_vsize_total * WITNESS_SCALE_FACTOR > std::numeric_limits<int32_t>::max()) { 143 // We aren't adding this final tx to mempool, so we don't want to conflict with it 144 mempool_txs.pop_back(); 145 break; 146 } 147 assert(!pool.GetIter(parent_entry.GetTx().GetHash())); 148 TryAddToMempool(pool, parent_entry); 149 150 // It's possible that adding this to the mempool failed due to cluster 151 // size limits; if so bail out. 152 if(!pool.GetIter(parent_entry.GetTx().GetHash())) { 153 mempool_txs.pop_back(); 154 continue; 155 } 156 157 child.vin[0].prevout = COutPoint{mempool_txs.back().GetHash(), 0}; 158 mempool_txs.emplace_back(child); 159 const auto child_entry = ConsumeTxMemPoolEntry(fuzzed_data_provider, mempool_txs.back()); 160 running_vsize_total += child_entry.GetTxSize(); 161 if (running_vsize_total * WITNESS_SCALE_FACTOR > std::numeric_limits<int32_t>::max()) { 162 // We aren't adding this final tx to mempool, so we don't want to conflict with it 163 mempool_txs.pop_back(); 164 break; 165 } 166 if (!pool.GetIter(child_entry.GetTx().GetHash())) { 167 TryAddToMempool(pool, child_entry); 168 // Adding this transaction to the mempool may fail due to cluster 169 // size limits; if so bail out. 170 if(!pool.GetIter(child_entry.GetTx().GetHash())) { 171 mempool_txs.pop_back(); 172 continue; 173 } 174 } 175 176 if (fuzzed_data_provider.ConsumeBool()) { 177 pool.PrioritiseTransaction(mempool_txs.back().GetHash(), fuzzed_data_provider.ConsumeIntegralInRange<int32_t>(-100000, 100000)); 178 } 179 } 180 181 // Pick some transactions at random to be the direct conflicts 182 CTxMemPool::setEntries direct_conflicts; 183 for (auto& tx : mempool_txs) { 184 if (fuzzed_data_provider.ConsumeBool() && pool.GetIter(tx.GetHash())) { 185 direct_conflicts.insert(*pool.GetIter(tx.GetHash())); 186 } 187 } 188 189 // Calculate all conflicts: 190 CTxMemPool::setEntries all_conflicts; 191 for (auto& txiter : direct_conflicts) { 192 pool.CalculateDescendants(txiter, all_conflicts); 193 } 194 195 CAmount replacement_fees = ConsumeMoney(fuzzed_data_provider); 196 auto changeset = pool.GetChangeSet(); 197 for (auto& txiter : all_conflicts) { 198 changeset->StageRemoval(txiter); 199 } 200 changeset->StageAddition(replacement_entry.GetSharedTx(), replacement_fees, 201 replacement_entry.GetTime().count(), replacement_entry.GetHeight(), 202 replacement_entry.GetSequence(), replacement_entry.GetSpendsCoinbase(), 203 replacement_entry.GetSigOpCost(), replacement_entry.GetLockPoints()); 204 // Calculate the chunks for a replacement. 205 auto calc_results{changeset->CalculateChunksForRBF()}; 206 207 if (calc_results.has_value()) { 208 // Sanity checks on the chunks. 209 210 // Feerates are monotonically decreasing. 211 FeeFrac first_sum; 212 for (size_t i = 0; i < calc_results->first.size(); ++i) { 213 first_sum += calc_results->first[i]; 214 if (i) assert(ByRatio{calc_results->first[i - 1]} >= ByRatio{calc_results->first[i]}); 215 } 216 FeeFrac second_sum; 217 for (size_t i = 0; i < calc_results->second.size(); ++i) { 218 second_sum += calc_results->second[i]; 219 if (i) assert(ByRatio{calc_results->second[i - 1]} >= ByRatio{calc_results->second[i]}); 220 } 221 222 FeeFrac replaced; 223 for (auto txiter : all_conflicts) { 224 replaced.fee += txiter->GetModifiedFee(); 225 replaced.size += txiter->GetAdjustedWeight(); 226 } 227 // The total fee & size of the new diagram minus replaced fee & size should be the total 228 // fee & size of the old diagram minus replacement fee & size. 229 assert((first_sum - replaced) == (second_sum - FeeFrac{replacement_fees, replacement_weight})); 230 } 231 232 // If internals report error, wrapper should too 233 auto err_tuple{ImprovesFeerateDiagram(*changeset)}; 234 if (!calc_results.has_value()) { 235 assert(err_tuple.value().first == DiagramCheckError::UNCALCULABLE); 236 } else { 237 // Diagram check succeeded 238 auto old_sum = std::accumulate(calc_results->first.begin(), calc_results->first.end(), FeeFrac{}); 239 auto new_sum = std::accumulate(calc_results->second.begin(), calc_results->second.end(), FeeFrac{}); 240 if (!err_tuple.has_value()) { 241 // New diagram's final fee should always match or exceed old diagram's 242 assert(old_sum.fee <= new_sum.fee); 243 } else if (old_sum.fee > new_sum.fee) { 244 // Or it failed, and if old diagram had higher fees, it should be a failure 245 assert(err_tuple.value().first == DiagramCheckError::FAILURE); 246 } 247 } 248 }