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