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 AddToMempool(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 AddToMempool(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_vsize = replacement_entry.GetTxSize(); 124 int64_t running_vsize_total{replacement_vsize}; 125 126 LOCK2(cs_main, pool.cs); 127 128 while (fuzzed_data_provider.ConsumeBool()) { 129 if (iter >= NUM_ITERS) break; 130 131 // Make sure txns only have one input, and that a unique input is given to avoid circular references 132 CMutableTransaction parent; 133 parent.vin.resize(1); 134 parent.vin[0].prevout = g_outpoints.at(iter++); 135 parent.vout.emplace_back(0, CScript()); 136 137 mempool_txs.emplace_back(parent); 138 const auto parent_entry = ConsumeTxMemPoolEntry(fuzzed_data_provider, mempool_txs.back()); 139 running_vsize_total += parent_entry.GetTxSize(); 140 if (running_vsize_total > std::numeric_limits<int32_t>::max()) { 141 // We aren't adding this final tx to mempool, so we don't want to conflict with it 142 mempool_txs.pop_back(); 143 break; 144 } 145 assert(!pool.GetIter(parent_entry.GetTx().GetHash())); 146 AddToMempool(pool, parent_entry); 147 if (fuzzed_data_provider.ConsumeBool()) { 148 child.vin[0].prevout = COutPoint{mempool_txs.back().GetHash(), 0}; 149 } 150 mempool_txs.emplace_back(child); 151 const auto child_entry = ConsumeTxMemPoolEntry(fuzzed_data_provider, mempool_txs.back()); 152 running_vsize_total += child_entry.GetTxSize(); 153 if (running_vsize_total > std::numeric_limits<int32_t>::max()) { 154 // We aren't adding this final tx to mempool, so we don't want to conflict with it 155 mempool_txs.pop_back(); 156 break; 157 } 158 if (!pool.GetIter(child_entry.GetTx().GetHash())) { 159 AddToMempool(pool, child_entry); 160 } 161 162 if (fuzzed_data_provider.ConsumeBool()) { 163 pool.PrioritiseTransaction(mempool_txs.back().GetHash().ToUint256(), fuzzed_data_provider.ConsumeIntegralInRange<int32_t>(-100000, 100000)); 164 } 165 } 166 167 // Pick some transactions at random to be the direct conflicts 168 CTxMemPool::setEntries direct_conflicts; 169 for (auto& tx : mempool_txs) { 170 if (fuzzed_data_provider.ConsumeBool()) { 171 direct_conflicts.insert(*pool.GetIter(tx.GetHash())); 172 } 173 } 174 175 // Calculate all conflicts: 176 CTxMemPool::setEntries all_conflicts; 177 for (auto& txiter : direct_conflicts) { 178 pool.CalculateDescendants(txiter, all_conflicts); 179 } 180 181 CAmount replacement_fees = ConsumeMoney(fuzzed_data_provider); 182 auto changeset = pool.GetChangeSet(); 183 for (auto& txiter : all_conflicts) { 184 changeset->StageRemoval(txiter); 185 } 186 changeset->StageAddition(replacement_entry.GetSharedTx(), replacement_fees, 187 replacement_entry.GetTime().count(), replacement_entry.GetHeight(), 188 replacement_entry.GetSequence(), replacement_entry.GetSpendsCoinbase(), 189 replacement_entry.GetSigOpCost(), replacement_entry.GetLockPoints()); 190 // Calculate the chunks for a replacement. 191 auto calc_results{changeset->CalculateChunksForRBF()}; 192 193 if (calc_results.has_value()) { 194 // Sanity checks on the chunks. 195 196 // Feerates are monotonically decreasing. 197 FeeFrac first_sum; 198 for (size_t i = 0; i < calc_results->first.size(); ++i) { 199 first_sum += calc_results->first[i]; 200 if (i) assert(!(calc_results->first[i - 1] << calc_results->first[i])); 201 } 202 FeeFrac second_sum; 203 for (size_t i = 0; i < calc_results->second.size(); ++i) { 204 second_sum += calc_results->second[i]; 205 if (i) assert(!(calc_results->second[i - 1] << calc_results->second[i])); 206 } 207 208 FeeFrac replaced; 209 for (auto txiter : all_conflicts) { 210 replaced.fee += txiter->GetModifiedFee(); 211 replaced.size += txiter->GetTxSize(); 212 } 213 // The total fee & size of the new diagram minus replaced fee & size should be the total 214 // fee & size of the old diagram minus replacement fee & size. 215 assert((first_sum - replaced) == (second_sum - FeeFrac{replacement_fees, replacement_vsize})); 216 } 217 218 // If internals report error, wrapper should too 219 auto err_tuple{ImprovesFeerateDiagram(*changeset)}; 220 if (!calc_results.has_value()) { 221 assert(err_tuple.value().first == DiagramCheckError::UNCALCULABLE); 222 } else { 223 // Diagram check succeeded 224 auto old_sum = std::accumulate(calc_results->first.begin(), calc_results->first.end(), FeeFrac{}); 225 auto new_sum = std::accumulate(calc_results->second.begin(), calc_results->second.end(), FeeFrac{}); 226 if (!err_tuple.has_value()) { 227 // New diagram's final fee should always match or exceed old diagram's 228 assert(old_sum.fee <= new_sum.fee); 229 } else if (old_sum.fee > new_sum.fee) { 230 // Or it failed, and if old diagram had higher fees, it should be a failure 231 assert(err_tuple.value().first == DiagramCheckError::FAILURE); 232 } 233 } 234 }