Merge #21142: fuzz: Add tx_pool fuzz target

faa9ef49d18da9223220afcc263ac91a74c291a6 fuzz: Add tx_pool fuzz targets (MarcoFalke)

Pull request description:

ACKs for top commit:
  AnthonyRonning:
    reACK faa9ef49d18da9223220afcc263ac91a74c291a6
  practicalswift:
    Tested ACK faa9ef49d18da9223220afcc263ac91a74c291a6
  glozow:
    code review ACK faa9ef49d18da9223220afcc263ac91a74c291a6, a bunch of comments but non blocking

Tree-SHA512: 8d404398faa46d8e7bf93060a2fe9afd5c0c2bd6e549ff6588d2f3dd1b912dff6c5416d5477c18edecc2e85b00db4fdf4790c3e6597a5149b0d40c9d5014d82f

5 files changed, 381 insertions, 6 deletions

diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index 7ed0eafb14..e00f17a83f 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -297,6 +297,7 @@ test_fuzz_fuzz_SOURCES = \
  test/fuzz/transaction.cpp \
  test/fuzz/tx_in.cpp \
  test/fuzz/tx_out.cpp \
+ test/fuzz/tx_pool.cpp \
  test/fuzz/txrequest.cpp \
  test/fuzz/validation_load_mempool.cpp \
  test/fuzz/versionbits.cpp
diff --git a/src/test/fuzz/tx_pool.cpp b/src/test/fuzz/tx_pool.cpp
new file mode 100644
index 0000000000..2a9363a7c3
--- /dev/null
+++ b/src/test/fuzz/tx_pool.cpp
@@ -0,0 +1,284 @@
+// Copyright (c) 2021 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <consensus/validation.h>
+#include <test/fuzz/FuzzedDataProvider.h>
+#include <test/fuzz/fuzz.h>
+#include <test/fuzz/util.h>
+#include <test/util/mining.h>
+#include <test/util/script.h>
+#include <test/util/setup_common.h>
+#include <util/rbf.h>
+#include <validation.h>
+#include <validationinterface.h>
+
+namespace {
+
+const TestingSetup* g_setup;
+std::vector<COutPoint> g_outpoints_coinbase_init;
+
+struct MockedTxPool : public CTxMemPool {
+    void RollingFeeUpdate()
+    {
+        lastRollingFeeUpdate = GetTime();
+        blockSinceLastRollingFeeBump = true;
+    }
+};
+
+void initialize_tx_pool()
+{
+    static const auto testing_setup = MakeNoLogFileContext<const TestingSetup>();
+    g_setup = testing_setup.get();
+
+    for (int i = 0; i < 2 * COINBASE_MATURITY; ++i) {
+        CTxIn in = MineBlock(g_setup->m_node, P2WSH_OP_TRUE);
+        // Remember the txids to avoid expensive disk acess later on
+        g_outpoints_coinbase_init.push_back(in.prevout);
+    }
+    SyncWithValidationInterfaceQueue();
+}
+
+struct TransactionsDelta final : public CValidationInterface {
+    std::set<CTransactionRef>& m_removed;
+    std::set<CTransactionRef>& m_added;
+
+    explicit TransactionsDelta(std::set<CTransactionRef>& r, std::set<CTransactionRef>& a)
+        : m_removed{r}, m_added{a} {}
+
+    void TransactionAddedToMempool(const CTransactionRef& tx, uint64_t /* mempool_sequence */) override
+    {
+        Assert(m_added.insert(tx).second);
+    }
+
+    void TransactionRemovedFromMempool(const CTransactionRef& tx, MemPoolRemovalReason reason, uint64_t /* mempool_sequence */) override
+    {
+        Assert(m_removed.insert(tx).second);
+    }
+};
+
+void SetMempoolConstraints(ArgsManager& args, FuzzedDataProvider& fuzzed_data_provider)
+{
+    args.ForceSetArg("-limitancestorcount",
+                     ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 50)));
+    args.ForceSetArg("-limitancestorsize",
+                     ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 202)));
+    args.ForceSetArg("-limitdescendantcount",
+                     ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 50)));
+    args.ForceSetArg("-limitdescendantsize",
+                     ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 202)));
+    args.ForceSetArg("-maxmempool",
+                     ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 200)));
+    args.ForceSetArg("-mempoolexpiry",
+                     ToString(fuzzed_data_provider.ConsumeIntegralInRange<unsigned>(0, 999)));
+}
+
+FUZZ_TARGET_INIT(tx_pool_standard, initialize_tx_pool)
+{
+    FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
+    const auto& node = g_setup->m_node;
+    auto& chainstate = node.chainman->ActiveChainstate();
+
+    SetMockTime(ConsumeTime(fuzzed_data_provider));
+    SetMempoolConstraints(*node.args, fuzzed_data_provider);
+
+    // All RBF-spendable outpoints
+    std::set<COutPoint> outpoints_rbf;
+    // All outpoints counting toward the total supply (subset of outpoints_rbf)
+    std::set<COutPoint> outpoints_supply;
+    for (const auto& outpoint : g_outpoints_coinbase_init) {
+        Assert(outpoints_supply.insert(outpoint).second);
+        if (outpoints_supply.size() >= COINBASE_MATURITY) break;
+    }
+    outpoints_rbf = outpoints_supply;
+
+    // The sum of the values of all spendable outpoints
+    constexpr CAmount SUPPLY_TOTAL{COINBASE_MATURITY * 50 * COIN};
+
+    CTxMemPool tx_pool_{/* estimator */ nullptr, /* check_ratio */ 1};
+    MockedTxPool& tx_pool = *(MockedTxPool*)&tx_pool_;
+
+    // Helper to query an amount
+    const CCoinsViewMemPool amount_view{WITH_LOCK(::cs_main, return &chainstate.CoinsTip()), tx_pool};
+    const auto GetAmount = [&](const COutPoint& outpoint) {
+        Coin c;
+        amount_view.GetCoin(outpoint, c);
+        Assert(!c.IsSpent());
+        return c.out.nValue;
+    };
+
+    while (fuzzed_data_provider.ConsumeBool()) {
+        {
+            // Total supply is the mempool fee + all outpoints
+            CAmount supply_now{WITH_LOCK(tx_pool.cs, return tx_pool.GetTotalFee())};
+            for (const auto& op : outpoints_supply) {
+                supply_now += GetAmount(op);
+            }
+            Assert(supply_now == SUPPLY_TOTAL);
+        }
+        Assert(!outpoints_supply.empty());
+
+        // Create transaction to add to the mempool
+        const CTransactionRef tx = [&] {
+            CMutableTransaction tx_mut;
+            tx_mut.nVersion = CTransaction::CURRENT_VERSION;
+            tx_mut.nLockTime = fuzzed_data_provider.ConsumeBool() ? 0 : fuzzed_data_provider.ConsumeIntegral<uint32_t>();
+            const auto num_in = fuzzed_data_provider.ConsumeIntegralInRange<int>(1, outpoints_rbf.size());
+            const auto num_out = fuzzed_data_provider.ConsumeIntegralInRange<int>(1, outpoints_rbf.size() * 2);
+
+            CAmount amount_in{0};
+            for (int i = 0; i < num_in; ++i) {
+                // Pop random outpoint
+                auto pop = outpoints_rbf.begin();
+                std::advance(pop, fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0, outpoints_rbf.size() - 1));
+                const auto outpoint = *pop;
+                outpoints_rbf.erase(pop);
+                amount_in += GetAmount(outpoint);
+
+                // Create input
+                const auto sequence = ConsumeSequence(fuzzed_data_provider);
+                const auto script_sig = CScript{};
+                const auto script_wit_stack = std::vector<std::vector<uint8_t>>{WITNESS_STACK_ELEM_OP_TRUE};
+                CTxIn in;
+                in.prevout = outpoint;
+                in.nSequence = sequence;
+                in.scriptSig = script_sig;
+                in.scriptWitness.stack = script_wit_stack;
+
+                tx_mut.vin.push_back(in);
+            }
+            const auto amount_fee = fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(-1000, amount_in);
+            const auto amount_out = (amount_in - amount_fee) / num_out;
+            for (int i = 0; i < num_out; ++i) {
+                tx_mut.vout.emplace_back(amount_out, P2WSH_OP_TRUE);
+            }
+            const auto tx = MakeTransactionRef(tx_mut);
+            // Restore previously removed outpoints
+            for (const auto& in : tx->vin) {
+                Assert(outpoints_rbf.insert(in.prevout).second);
+            }
+            return tx;
+        }();
+
+        if (fuzzed_data_provider.ConsumeBool()) {
+            SetMockTime(ConsumeTime(fuzzed_data_provider));
+        }
+        if (fuzzed_data_provider.ConsumeBool()) {
+            SetMempoolConstraints(*node.args, fuzzed_data_provider);
+        }
+        if (fuzzed_data_provider.ConsumeBool()) {
+            tx_pool.RollingFeeUpdate();
+        }
+        if (fuzzed_data_provider.ConsumeBool()) {
+            const auto& txid = fuzzed_data_provider.ConsumeBool() ?
+                                   tx->GetHash() :
+                                   PickValue(fuzzed_data_provider, outpoints_rbf).hash;
+            const auto delta = fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(-50 * COIN, +50 * COIN);
+            tx_pool.PrioritiseTransaction(txid, delta);
+        }
+
+        // Remember all removed and added transactions
+        std::set<CTransactionRef> removed;
+        std::set<CTransactionRef> added;
+        auto txr = std::make_shared<TransactionsDelta>(removed, added);
+        RegisterSharedValidationInterface(txr);
+        const bool bypass_limits = fuzzed_data_provider.ConsumeBool();
+        ::fRequireStandard = fuzzed_data_provider.ConsumeBool();
+        const auto res = WITH_LOCK(::cs_main, return AcceptToMemoryPool(chainstate, tx_pool, tx, bypass_limits));
+        const bool accepted = res.m_result_type == MempoolAcceptResult::ResultType::VALID;
+        SyncWithValidationInterfaceQueue();
+        UnregisterSharedValidationInterface(txr);
+
+        Assert(accepted != added.empty());
+        Assert(accepted == res.m_state.IsValid());
+        Assert(accepted != res.m_state.IsInvalid());
+        if (accepted) {
+            Assert(added.size() == 1); // For now, no package acceptance
+            Assert(tx == *added.begin());
+        } else {
+            // Do not consider rejected transaction removed
+            removed.erase(tx);
+        }
+
+        // Helper to insert spent and created outpoints of a tx into collections
+        using Sets = std::vector<std::reference_wrapper<std::set<COutPoint>>>;
+        const auto insert_tx = [](Sets created_by_tx, Sets consumed_by_tx, const auto& tx) {
+            for (size_t i{0}; i < tx.vout.size(); ++i) {
+                for (auto& set : created_by_tx) {
+                    Assert(set.get().emplace(tx.GetHash(), i).second);
+                }
+            }
+            for (const auto& in : tx.vin) {
+                for (auto& set : consumed_by_tx) {
+                    Assert(set.get().insert(in.prevout).second);
+                }
+            }
+        };
+        // Add created outpoints, remove spent outpoints
+        {
+            // Outpoints that no longer exist at all
+            std::set<COutPoint> consumed_erased;
+            // Outpoints that no longer count toward the total supply
+            std::set<COutPoint> consumed_supply;
+            for (const auto& removed_tx : removed) {
+                insert_tx(/* created_by_tx */ {consumed_erased}, /* consumed_by_tx */ {outpoints_supply}, /* tx */ *removed_tx);
+            }
+            for (const auto& added_tx : added) {
+                insert_tx(/* created_by_tx */ {outpoints_supply, outpoints_rbf}, /* consumed_by_tx */ {consumed_supply}, /* tx */ *added_tx);
+            }
+            for (const auto& p : consumed_erased) {
+                Assert(outpoints_supply.erase(p) == 1);
+                Assert(outpoints_rbf.erase(p) == 1);
+            }
+            for (const auto& p : consumed_supply) {
+                Assert(outpoints_supply.erase(p) == 1);
+            }
+        }
+    }
+    WITH_LOCK(::cs_main, tx_pool.check(chainstate));
+    const auto info_all = tx_pool.infoAll();
+    if (!info_all.empty()) {
+        const auto& tx_to_remove = *PickValue(fuzzed_data_provider, info_all).tx;
+        WITH_LOCK(tx_pool.cs, tx_pool.removeRecursive(tx_to_remove, /* dummy */ MemPoolRemovalReason::BLOCK));
+        std::vector<uint256> all_txids;
+        tx_pool.queryHashes(all_txids);
+        assert(all_txids.size() < info_all.size());
+        WITH_LOCK(::cs_main, tx_pool.check(chainstate));
+    }
+    SyncWithValidationInterfaceQueue();
+}
+
+FUZZ_TARGET_INIT(tx_pool, initialize_tx_pool)
+{
+    FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
+    const auto& node = g_setup->m_node;
+
+    std::vector<uint256> txids;
+    for (const auto& outpoint : g_outpoints_coinbase_init) {
+        txids.push_back(outpoint.hash);
+        if (txids.size() >= COINBASE_MATURITY) break;
+    }
+    for (int i{0}; i <= 3; ++i) {
+        // Add some immature and non-existent outpoints
+        txids.push_back(g_outpoints_coinbase_init.at(i).hash);
+        txids.push_back(ConsumeUInt256(fuzzed_data_provider));
+    }
+
+    CTxMemPool tx_pool{/* estimator */ nullptr, /* check_ratio */ 1};
+
+    while (fuzzed_data_provider.ConsumeBool()) {
+        const auto mut_tx = ConsumeTransaction(fuzzed_data_provider, txids);
+
+        const auto tx = MakeTransactionRef(mut_tx);
+        const bool bypass_limits = fuzzed_data_provider.ConsumeBool();
+        ::fRequireStandard = fuzzed_data_provider.ConsumeBool();
+        const auto res = WITH_LOCK(::cs_main, return AcceptToMemoryPool(node.chainman->ActiveChainstate(), tx_pool, tx, bypass_limits));
+        const bool accepted = res.m_result_type == MempoolAcceptResult::ResultType::VALID;
+        if (accepted) {
+            txids.push_back(tx->GetHash());
+        }
+
+        SyncWithValidationInterfaceQueue();
+    }
+}
+} // namespace
diff --git a/src/test/fuzz/util.cpp b/src/test/fuzz/util.cpp
index 0a541e4186..93418ab1ff 100644
--- a/src/test/fuzz/util.cpp
+++ b/src/test/fuzz/util.cpp
@@ -3,8 +3,11 @@
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
 #include <test/fuzz/util.h>
+#include <test/util/script.h>
+#include <util/rbf.h>
 #include <version.h>
 
+
 void FillNode(FuzzedDataProvider& fuzzed_data_provider, CNode& node, bool init_version) noexcept
 {
     const ServiceFlags remote_services = ConsumeWeakEnum(fuzzed_data_provider, ALL_SERVICE_FLAGS);
@@ -23,3 +26,78 @@ void FillNode(FuzzedDataProvider& fuzzed_data_provider, CNode& node, bool init_v
         node.m_tx_relay->fRelayTxes = filter_txs;
     }
 }
+
+CMutableTransaction ConsumeTransaction(FuzzedDataProvider& fuzzed_data_provider, const std::optional<std::vector<uint256>>& prevout_txids, const int max_num_in, const int max_num_out) noexcept
+{
+    CMutableTransaction tx_mut;
+    const auto p2wsh_op_true = fuzzed_data_provider.ConsumeBool();
+    tx_mut.nVersion = fuzzed_data_provider.ConsumeBool() ?
+                          CTransaction::CURRENT_VERSION :
+                          fuzzed_data_provider.ConsumeIntegral<int32_t>();
+    tx_mut.nLockTime = fuzzed_data_provider.ConsumeIntegral<uint32_t>();
+    const auto num_in = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, max_num_in);
+    const auto num_out = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, max_num_out);
+    for (int i = 0; i < num_in; ++i) {
+        const auto& txid_prev = prevout_txids ?
+                                    PickValue(fuzzed_data_provider, *prevout_txids) :
+                                    ConsumeUInt256(fuzzed_data_provider);
+        const auto index_out = fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(0, max_num_out);
+        const auto sequence = ConsumeSequence(fuzzed_data_provider);
+        const auto script_sig = p2wsh_op_true ? CScript{} : ConsumeScript(fuzzed_data_provider);
+        CScriptWitness script_wit;
+        if (p2wsh_op_true) {
+            script_wit.stack = std::vector<std::vector<uint8_t>>{WITNESS_STACK_ELEM_OP_TRUE};
+        } else {
+            script_wit = ConsumeScriptWitness(fuzzed_data_provider);
+        }
+        CTxIn in;
+        in.prevout = COutPoint{txid_prev, index_out};
+        in.nSequence = sequence;
+        in.scriptSig = script_sig;
+        in.scriptWitness = script_wit;
+
+        tx_mut.vin.push_back(in);
+    }
+    for (int i = 0; i < num_out; ++i) {
+        const auto amount = fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(-10, 50 * COIN + 10);
+        const auto script_pk = p2wsh_op_true ?
+                                   P2WSH_OP_TRUE :
+                                   ConsumeScript(fuzzed_data_provider, /* max_length */ 128, /* maybe_p2wsh */ true);
+        tx_mut.vout.emplace_back(amount, script_pk);
+    }
+    return tx_mut;
+}
+
+CScriptWitness ConsumeScriptWitness(FuzzedDataProvider& fuzzed_data_provider, const size_t max_stack_elem_size) noexcept
+{
+    CScriptWitness ret;
+    const auto n_elements = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0, max_stack_elem_size);
+    for (size_t i = 0; i < n_elements; ++i) {
+        ret.stack.push_back(ConsumeRandomLengthByteVector(fuzzed_data_provider));
+    }
+    return ret;
+}
+
+CScript ConsumeScript(FuzzedDataProvider& fuzzed_data_provider, const size_t max_length, const bool maybe_p2wsh) noexcept
+{
+    const std::vector<uint8_t> b = ConsumeRandomLengthByteVector(fuzzed_data_provider);
+    CScript r_script{b.begin(), b.end()};
+    if (maybe_p2wsh && fuzzed_data_provider.ConsumeBool()) {
+        uint256 script_hash;
+        CSHA256().Write(&r_script[0], r_script.size()).Finalize(script_hash.begin());
+        r_script.clear();
+        r_script << OP_0 << ToByteVector(script_hash);
+    }
+    return r_script;
+}
+
+uint32_t ConsumeSequence(FuzzedDataProvider& fuzzed_data_provider) noexcept
+{
+    return fuzzed_data_provider.ConsumeBool() ?
+               fuzzed_data_provider.PickValueInArray({
+                   CTxIn::SEQUENCE_FINAL,
+                   CTxIn::SEQUENCE_FINAL - 1,
+                   MAX_BIP125_RBF_SEQUENCE,
+               }) :
+               fuzzed_data_provider.ConsumeIntegral<uint32_t>();
+}
diff --git a/src/test/fuzz/util.h b/src/test/fuzz/util.h
index cdddad82b3..df459fe60d 100644
--- a/src/test/fuzz/util.h
+++ b/src/test/fuzz/util.h
@@ -48,6 +48,16 @@ void CallOneOf(FuzzedDataProvider& fuzzed_data_provider, Callables... callables)
     return ((i++ == call_index ? callables() : void()), ...);
 }
 
+template <typename Collection>
+const auto& PickValue(FuzzedDataProvider& fuzzed_data_provider, const Collection& col)
+{
+    const auto sz = col.size();
+    assert(sz >= 1);
+    auto it = col.begin();
+    std::advance(it, fuzzed_data_provider.ConsumeIntegralInRange<decltype(sz)>(0, sz - 1));
+    return *it;
+}
+
 [[nodiscard]] inline std::vector<uint8_t> ConsumeRandomLengthByteVector(FuzzedDataProvider& fuzzed_data_provider, const size_t max_length = 4096) noexcept
 {
     const std::string s = fuzzed_data_provider.ConsumeRandomLengthString(max_length);
@@ -125,11 +135,13 @@ template <typename WeakEnumType, size_t size>
     return fuzzed_data_provider.ConsumeIntegralInRange<int64_t>(time_min, time_max);
 }
 
-[[nodiscard]] inline CScript ConsumeScript(FuzzedDataProvider& fuzzed_data_provider) noexcept
-{
-    const std::vector<uint8_t> b = ConsumeRandomLengthByteVector(fuzzed_data_provider);
-    return {b.begin(), b.end()};
-}
+[[nodiscard]] CMutableTransaction ConsumeTransaction(FuzzedDataProvider& fuzzed_data_provider, const std::optional<std::vector<uint256>>& prevout_txids, const int max_num_in = 10, const int max_num_out = 10) noexcept;
+
+[[nodiscard]] CScriptWitness ConsumeScriptWitness(FuzzedDataProvider& fuzzed_data_provider, const size_t max_stack_elem_size = 32) noexcept;
+
+[[nodiscard]] CScript ConsumeScript(FuzzedDataProvider& fuzzed_data_provider, const size_t max_length = 4096, const bool maybe_p2wsh = false) noexcept;
+
+[[nodiscard]] uint32_t ConsumeSequence(FuzzedDataProvider& fuzzed_data_provider) noexcept;
 
 [[nodiscard]] inline CScriptNum ConsumeScriptNum(FuzzedDataProvider& fuzzed_data_provider) noexcept
 {
diff --git a/src/txmempool.h b/src/txmempool.h
index 9d4ea760e7..c3a9bd851d 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -476,7 +476,7 @@ enum class MemPoolRemovalReason {
  */
 class CTxMemPool
 {
-private:
+protected:
     const int m_check_ratio; //!< Value n means that 1 times in n we check.
     std::atomic<unsigned int> nTransactionsUpdated{0}; //!< Used by getblocktemplate to trigger CreateNewBlock() invocation
     CBlockPolicyEstimator* minerPolicyEstimator;