Implement Mini version of BlockAssembler to calculate mining scores #27021

pull murchandamus wants to merge 4 commits into bitcoin:master from murchandamus:add-mini-miner changing 8 files +1215 −2
  1. murchandamus commented at 0:25 am on February 2, 2023: contributor

    Implement Mini version of BlockAssembler to calculate mining scores

    Run the mining algorithm on a subset of the mempool, only disturbing the mempool to copy out fee information for relevant entries. Intended to be used by wallet to calculate amounts needed for fee-bumping unconfirmed transactions.

    From comments of sipa and glozow below:

    In what way does the code added here differ from the real block assembly code?

    • Only operates on the relevant transactions rather than full mempool
    • Has the ability to remove transactions that will be replaced so they don’t impact their ancestors
    • Does not hold mempool lock outside of the constructor, makes copies of the entries it needs instead (though I’m not sure if this has an effect in practice)
    • Doesn’t do the sanity checks like keeping weight within max block weight and IsFinalTx()
    • After the block template is built, additionally calculates fees to bump remaining ancestor packages to target feerate
  2. DrahtBot commented at 0:25 am on February 2, 2023: contributor

    The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

    Reviews

    See the guideline for information on the review process.

    Type Reviewers
    ACK achow101, furszy, theStack
    Concept ACK glozow
    Stale ACK LarryRuane

    If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

    Conflicts

    No conflicts as of last run.

  3. glozow commented at 7:50 pm on February 2, 2023: member
    Wrote some more tests for this, please feel free to take: https://github.com/glozow/bitcoin/commit/6761c5935c34079fdd55904e025c9e19d80955d8
  4. murchandamus force-pushed on Feb 2, 2023
  5. glozow added the label Mempool on Feb 3, 2023
  6. in src/txmempool.cpp:1182 in daf023a49c outdated
    1180+            for (const CTxMemPoolEntry& parent_entry : cluster.at(i)->GetMemPoolParentsConst()) {
    1181+                const auto parent_it = mapTx.iterator_to(parent_entry);
    1182+                if (!visited(parent_it)) {
    1183+                    cluster.push_back(parent_it);
    1184+                    // we still need to process this
    1185+                    ++to_process_count;
    


    glozow commented at 10:43 am on February 3, 2023:
    (IIRC we discussed this offline a while ago) We probably want to check here that to_process_count doesn’t get too large. It’s not really feasible to run MiniMiner with a cluster == entire mempool… Perhaps add a check here so that if we see a cluster size > 1000 (or something), we maybe want to tell the wallet to calculate bump fees in batches, maybe look at fewer UTXOS, or some kind of safe fallback.

    glozow commented at 10:31 am on March 1, 2023:
    Marking as resolved as this has been implemented
  7. dergoegge commented at 3:41 pm on February 3, 2023: member

    I wrote a fuzz test for the MiniMiner and it crashes on some of the Assumes: https://github.com/dergoegge/bitcoin/tree/2023-01-fuzz-mini-miner

    0$ echo "AQEWCQEBAAEACf//////////////CBwAAgAAlRwB7QEA/wAAAAL7AAEAAAEB7QEA/wAAAAL7AAAA
    1AAAAXAD//w==" | base64 -d > mini_miner_crash.input
    2$ FUZZ=mini_miner ./src/test/fuzz/fuzz ./mini_miner_crash.input
    

    Now that could just mean that my assumptions about what should be passed into the MiniMiner are wrong (i.e. my fuzz target is using the MiniMiner incorrectly). In that case it might make sense to add documentation that outlines what is expected from a MiniMiner user.

    Two questions:

    • Are the assumptions (i.e. Assumes in mini_miner.cpp) internal to the MiniMiner or do they rely on external assumptions as well? e.g. Does the mini miner expect the mempool it receives in its constructor to only hold transactions that passed out ATMP checks?
    • Since this is a “mini” version of the BlockAssembler, would it be possible to differentially fuzz the two? Or using one as an oracle to test the other? e.g. Checking if transactions bumped with the help of MiniMiner make it into the next block constructed by the actual BlockAssembler.
  8. sipa commented at 4:13 pm on February 3, 2023: member
    In what way does the code added here differ from the real block assembly code?
  9. glozow commented at 4:14 pm on February 3, 2023: member

    Thanks for fuzzing :100: It’s fully possible the crashing is due to real bugs, I hit a crash yesterday while testing as well. I think there is something wrong with the way it’s handling to-be-replaced outputs.

    Does the mini miner expect the mempool it receives in its constructor to only hold transactions that passed out ATMP checks?

    Actually no. It just uses what’s cached in the mempool entries. The fees don’t even need to match inputs - outputs, and mini miner definitely doesn’t require ATMP checks.

    Since this is a “mini” version of the BlockAssembler, would it be possible to differentially fuzz the two?

    Differential fuzzing is perfect for this really.MiniMiner::BuildMockTemplate(target_feerate) is supposed to do the exact same thing as BlockAssembler::addPackageTxs with blockmintxfee = target feerate.

    Checking if transactions bumped with the help of MiniMiner make it into the next block constructed by the actual BlockAssembler.

    That would also be a really good way of testing the results (after the wallet stuff is added?). Add the bumping tx, mine another block with the target feerate as min feerate, and see that they all get mined.

  10. glozow commented at 4:21 pm on February 3, 2023: member

    In what way does the code added here differ from the real block assembly code?

    • Only operates on the relevant transactions rather than full mempool
    • Has the ability to remove transactions that will be replaced so they don’t impact their ancestors
    • Does not hold mempool lock outside of the constructor, makes copies of the entries it needs instead (though I’m not sure if this has an effect in practice)
    • Doesn’t do the sanity checks like keeping weight within max block weight and IsFinalTx()
    • After the block template is built, additionally calculates fees to bump remaining ancestor packages to target feerate
  11. murchandamus commented at 9:29 pm on February 3, 2023: contributor
    Added tests from glozow’s branch
  12. murchandamus force-pushed on Feb 3, 2023
  13. glozow commented at 10:14 am on February 6, 2023: member
    Is there a reason to leave the CalculateTotalBumpFee commit out of this PR?
  14. murchandamus commented at 10:26 pm on February 6, 2023: contributor
    Oh good point, that just grew organically, but really it could be part of the mini-miner changes. I’ll squash it in there.
  15. murchandamus force-pushed on Feb 8, 2023
  16. murchandamus commented at 4:58 pm on February 8, 2023: contributor
    I’ve amended this branch to include the CalculateTotalBumpFee method from #26152 in the mini-miner code here.
  17. murchandamus force-pushed on Feb 8, 2023
  18. murchandamus force-pushed on Feb 8, 2023
  19. glozow force-pushed on Feb 16, 2023
  20. glozow force-pushed on Feb 16, 2023
  21. glozow commented at 4:06 pm on February 16, 2023: member

    I pushed some changes (with @Xekyo’s permission, thanks):

    • Capped traversal at 500 items in CalculateCluster(). Number is arbitrary, open for commentary
    • Fixed up a few things in the MiniMiner implementation, mostly shuffling things around and updating comments
    • Dropped the chain interface changes (I think those can go in #26152)
    • Expanded unit tests
    • Added a fuzzer (expanded from @dergoegge’s, thanks)
    • Added a fuzzer to differentially test block templates built by BlockAssembler and MiniMiner. Hopefully this gives reviewers a bit more confidence that they are doing the same thing even if the implementations are difficult to review/compare.
  22. murchandamus force-pushed on Feb 16, 2023
  23. murchandamus commented at 9:29 pm on February 16, 2023: contributor

    Awesome, thanks for the reworking this, @glozow, and the work on the fuzzer, @dergoegge. I’ve fixed a minor tidy issue and I’ll pick the chain interface changes into #26152 and rebase on this shortly.

    Ready for review

  24. murchandamus marked this as ready for review on Feb 16, 2023
  25. murchandamus force-pushed on Feb 16, 2023
  26. murchandamus commented at 10:26 pm on February 16, 2023: contributor
    Pushed again to provide signed commits
  27. glozow commented at 4:19 pm on February 17, 2023: member
    review-beg-pinging @LarryRuane @josibake @stickies-v who have looked at MiniMiner previously
  28. LarryRuane commented at 5:53 pm on February 17, 2023: contributor
    For anyone wanting to review this PR and would like some help with basic mempool concepts, I made a video: https://youtu.be/sQ05azzTp9o – it mentions 26152 but I think would be helpful for reviewers here as well.
  29. glozow added this to the milestone 25.0 on Feb 23, 2023
  30. achow101 commented at 9:25 pm on February 23, 2023: member
    ACK ce882ef0cf338d390733dd85e339a1c0da73072c
  31. in src/txmempool.cpp:910 in ce882ef0cf outdated
    905+    std::vector<txiter> ret;
    906+    ret.reserve(txids.size());
    907+    for (const auto& txid : txids) {
    908+        const auto it{GetIter(txid)};
    909+        if (!it) return {};
    910+        ret.push_back(*it);
    


    LarryRuane commented at 5:57 pm on February 27, 2023:

    nit

    0        ret.push_back(it.value());
    

    This may help the reader know that it is a std::optional; at first, I thought GetIter() may be returning a pointer. But if you prefer *, which is more concise, that’s fine too.


    murchandamus commented at 10:42 pm on March 2, 2023:
    I’d probably prefer using .value() for new code I’d write, but the asterisk-variant seems prevalent throughout this code.
  32. in src/txmempool.cpp:902 in ce882ef0cf outdated
    898@@ -898,6 +899,19 @@ CTxMemPool::setEntries CTxMemPool::GetIterSet(const std::set<uint256>& hashes) c
    899     return ret;
    900 }
    901 
    902+std::vector<CTxMemPool::txiter> CTxMemPool::GetIterVec(const std::vector<uint256>& txids) const
    


    LarryRuane commented at 6:05 pm on February 27, 2023:
    0std::optional<std::vector<CTxMemPool::txiter>> CTxMemPool::GetIterVec(const std::vector<uint256>& txids) const
    

    Would this be better than giving a special meaning to an empty vector? I’m unsure, but may be worth considering.


    murchandamus commented at 10:41 pm on March 2, 2023:
    Yes, agreed using an optional would be more explicit, however handling the optional return value would touch a bunch of lines here, and given that the result should never be empty unless something went wrong or the function got called with an empty txids input, I feel it’s a bit of a cosmetic improvement here.
  33. in src/txmempool.cpp:1157 in ce882ef0cf outdated
    1152@@ -1140,3 +1153,49 @@ std::string RemovalReasonToString(const MemPoolRemovalReason& r) noexcept
    1153     }
    1154     assert(false);
    1155 }
    1156+
    1157+std::vector<CTxMemPool::txiter> CTxMemPool::CalculateCluster(const std::vector<uint256>& txids) const
    


    LarryRuane commented at 6:07 pm on February 27, 2023:
    0std::optional<std::vector<CTxMemPool::txiter>> CTxMemPool::CalculateCluster(const std::vector<uint256>& txids) const
    

    murchandamus commented at 10:50 pm on March 2, 2023:
    As above with GetIterVec(), an empty vector is not a valid outcome for a call, so I tend to leave as is.
  34. in src/txmempool.cpp:1165 in aad0c09ab6 outdated
    1159+    AssertLockHeld(cs);
    1160+    std::vector<txiter> cluster{GetIterVec(txids)};
    1161+    if (cluster.size() != txids.size()) {
    1162+        // We can't continue because the caller specified a tx that doesn't exist in the mempool.
    1163+        // Return an empty vector to let them know this failed.
    1164+        return {};
    


    LarryRuane commented at 6:28 pm on February 27, 2023:
    Should this function return std::nullopt instead?

    murchandamus commented at 10:54 pm on March 2, 2023:
    Thanks, will consider, change but feel it’s okay at this time.
  35. in src/txmempool.cpp:1170 in ce882ef0cf outdated
    1165+    }
    1166+    // Reserve total ancestor + descendant counts of each transaction.  This is an approximation; it
    1167+    // may overestimate because transactions may share ancestors/descendants, and may underestimate
    1168+    // because the cluster may include more than just ancestors and descendants.
    1169+    cluster.reserve(std::accumulate(cluster.cbegin(), cluster.cend(), 0, [](size_t sum, const auto it) {
    1170+        return sum + it->GetCountWithAncestors() + it->GetCountWithDescendants() - 1; }));
    


    LarryRuane commented at 7:20 pm on February 27, 2023:

    I’m concerned about the possible over-estimation here. In theory, there could be a combinatorial explosion if the DAG is highly interconnected and deep. I would consider removing this code, because vector push_back() is highly optimized when growth is needed. Or at least make sure there’s a problem before adding this optimization.

    If you do keep this, consider calling cluster.shrink_to_fit() before returning, so at least any high memory usage is temporary.


    glozow commented at 10:30 am on March 1, 2023:
    I agree it might just be better to not reserve anything. We have no idea what the cluster size is going to be, so might as well let the stdlib magic do its work.

    murchandamus commented at 9:48 pm on March 2, 2023:
    I’ve removed the reserve(…) call here.
  36. LarryRuane commented at 7:35 pm on February 27, 2023: contributor
    ce882ef0cf338d390733dd85e339a1c0da73072c Some comments for the first commit only (I’ll review the other commits soon). Suggestion, mention the name CalculateCluster() in this first commit’s first line, or somewhere within the commit comment. Also, it might make sense to move the CalculateCluster unit test from the third commit to this commit.
  37. in src/node/mini_miner.cpp:1 in ce882ef0cf outdated
    0@@ -0,0 +1,321 @@
    1+// Copyright (c) 2022 The Bitcoin Core developers
    


    LarryRuane commented at 6:00 pm on February 28, 2023:
    0// Copyright (c) 2023 The Bitcoin Core developers
    

    murchandamus commented at 7:11 pm on March 3, 2023:
    Updated
  38. in src/node/mini_miner.cpp:52 in ce882ef0cf outdated
    47+            auto it = m_requested_outpoints_by_txid.find(outpoint.hash);
    48+            if (it != m_requested_outpoints_by_txid.end()) {
    49+                it->second.push_back(outpoint);
    50+            } else {
    51+                std::vector<COutPoint> outpoints_of_tx({outpoint});
    52+                m_requested_outpoints_by_txid.emplace(outpoint.hash, outpoints_of_tx);
    


    LarryRuane commented at 11:58 pm on February 28, 2023:

    Nit, more efficient to not make a copy

    0                std::vector<COutPoint> outpoints_of_tx({outpoint});
    1                m_requested_outpoints_by_txid.emplace(outpoint.hash, std::move(outpoints_of_tx));
    

    or (I didn’t test this, but I’m pretty sure that since the vector argument is an rvalue, the compiler will do a move)

    0                m_requested_outpoints_by_txid.emplace(outpoint.hash, std::vector<COutPoint>{outpoint});
    

    murchandamus commented at 10:16 pm on March 3, 2023:
    Thanks, I’m not going to interfere here, because outpoints are tiny anyway, and it seems more readable without the move or constructor.
  39. in src/node/mini_miner.cpp:53 in ce882ef0cf outdated
    48+            if (it != m_requested_outpoints_by_txid.end()) {
    49+                it->second.push_back(outpoint);
    50+            } else {
    51+                std::vector<COutPoint> outpoints_of_tx({outpoint});
    52+                m_requested_outpoints_by_txid.emplace(outpoint.hash, outpoints_of_tx);
    53+            }
    


    LarryRuane commented at 0:22 am on March 1, 2023:

    Nit, simpler. I don’t know if the comment is necessary (the reader is expected to know this about maps), but it may help to document that we’re taking advantage of that behavior.

    The developer notes do say not to use the std::map [] syntax, but only for reading.

    0            // This creates the map entry if it doesn't already exist.
    1            m_requested_outpoints_by_txid[outpoint.hash].push_back(outpoint);
    

    murchandamus commented at 8:05 pm on March 3, 2023:
    Thanks that’s much nicer
  40. in src/node/mini_miner.h:63 in ce882ef0cf outdated
    63+    // Original outpoints requested
    64+    std::vector<COutPoint> m_requested_outpoints;
    65+
    66+    // Set once per lifetime, fill in during initialization.
    67+    // txids of to-be-replaced transactions
    68+    std::set<uint256> m_to_be_replaced;
    


    LarryRuane commented at 1:05 am on March 1, 2023:

    Not a bug, but I noticed that the only reference to m_to_be_replaced outside the constructor is an Assume in SanityCheck(), I wonder if it’s worth m_to_be_replaced being a class member. If we give up the Assume, which doesn’t seem to be doing that much heavy lifting, then m_to_be_replaced could be a local variable in the constructor.

    Another nice thing about making m_to_be_replaced a local variable is that its entries can be pointers to transactions, instead of entire txid hashes. I wanted to make sure that would work, so here’s a patch that does that and passes the tests. (It includes my other suggestions for the constructor, because I wanted to test all of them.)

     0--- a/src/node/mini_miner.cpp
     1+++ b/src/node/mini_miner.cpp
     2@@ -21,6 +21,7 @@ MiniMiner::MiniMiner(const CTxMemPool& mempool, const std::vector<COutPoint>& ou
     3 {
     4     LOCK(mempool.cs);
     5     m_requested_outpoints = outpoints;
     6+    std::set<const CTransaction*> to_be_replaced;
     7     // Find which outpoints to calculate bump fees for.
     8     // Anything that's spent by the mempool is to-be-replaced
     9     // Anything otherwise unavailable just has a bump fee of 0
    10@@ -32,25 +33,19 @@ MiniMiner::MiniMiner(const CTxMemPool& mempool, const std::vector<COutPoint>& ou
    11             // ancestors bump fees (added to m_requested_outpoints_by_txid below), but after
    12             // removing the to-be-replaced entries. Note that this is only calculating bump fees.
    13             // RBF fee rules should be handled separately.
    14-            m_to_be_replaced.insert(ptx->GetHash());
    15+            to_be_replaced.insert(ptx);
    16             // Remove descendants because they will be replaced as well. This case should be rare
    17             // as the wallet won't normally attempt to replace transactions with descendants.
    18             CTxMemPool::setEntries descendants;
    19             mempool.CalculateDescendants(mempool.GetIter(ptx->GetHash()).value(), descendants);
    20             for (const auto& desc_txiter : descendants) {
    21-                m_to_be_replaced.insert(desc_txiter->GetTx().GetHash());
    22+                to_be_replaced.insert(&desc_txiter->GetTx());
    23             }
    24         }
    25 
    26         if (mempool.exists(GenTxid::Txid(outpoint.hash))) {
    27             // This UTXO is unconfirmed and in the mempool.
    28-            auto it = m_requested_outpoints_by_txid.find(outpoint.hash);
    29-            if (it != m_requested_outpoints_by_txid.end()) {
    30-                it->second.push_back(outpoint);
    31-            } else {
    32-                std::vector<COutPoint> outpoints_of_tx({outpoint});
    33-                m_requested_outpoints_by_txid.emplace(outpoint.hash, outpoints_of_tx);
    34-            }
    35+            m_requested_outpoints_by_txid[outpoint.hash].push_back(outpoint);
    36         } else {
    37             // This UTXO is either confirmed or not yet submitted to mempool.
    38             // If it's confirmed, no bump fee is required.
    39@@ -77,7 +72,7 @@ MiniMiner::MiniMiner(const CTxMemPool& mempool, const std::vector<COutPoint>& ou
    40 
    41     // Add every entry to m_entries_by_txid and m_entries, except the ones that will be replaced.
    42     for (const auto& txiter : cluster) {
    43-        if (m_to_be_replaced.find(txiter->GetTx().GetHash()) == m_to_be_replaced.end()) {
    44+        if (to_be_replaced.find(&txiter->GetTx()) == to_be_replaced.end()) {
    45             auto [mapiter, success] = m_entries_by_txid.emplace(txiter->GetTx().GetHash(), MiniMinerMempoolEntry(txiter));
    46             m_entries.push_back(mapiter);
    47         } else {
    48@@ -95,18 +90,19 @@ MiniMiner::MiniMiner(const CTxMemPool& mempool, const std::vector<COutPoint>& ou
    49 
    50     // Build the m_descendant_set_by_txid cache.
    51     for (const auto& txiter : cluster) {
    52-        const auto& txid = txiter->GetTx().GetHash();
    53+        const CTransaction& tx{txiter->GetTx()};
    54+        const auto& txid{tx.GetHash()};
    55         // Cache descendants for future use. Unlike the real mempool, a descendant MiniMinerMempoolEntry
    56         // will not exist without its ancestor MiniMinerMempoolEntry, so these sets won't be invalidated.
    57         std::vector<MockEntryMap::iterator> cached_descendants;
    58-        const bool remove = m_to_be_replaced.find(txid) != m_to_be_replaced.end();
    59+        const bool remove{to_be_replaced.find(&tx) != to_be_replaced.end()};
    60         CTxMemPool::setEntries descendants;
    61         mempool.CalculateDescendants(txiter, descendants);
    62         Assume(descendants.find(txiter) != descendants.end());
    63         for (const auto& desc_txiter : descendants) {
    64-            const auto txid_desc = desc_txiter->GetTx().GetHash();
    65-            const bool remove_desc = m_to_be_replaced.find(txid_desc) != m_to_be_replaced.end();
    66-            auto desc_it{m_entries_by_txid.find(txid_desc)};
    67+            const CTransaction& tx_desc{desc_txiter->GetTx()};
    68+            const bool remove_desc{to_be_replaced.find(&tx_desc) != to_be_replaced.end()};
    69+            auto desc_it{m_entries_by_txid.find(tx_desc.GetHash())};
    70             Assume((desc_it == m_entries_by_txid.end()) == remove_desc);
    71             if (remove) Assume(remove_desc);
    72             // It's possible that remove=false but remove_desc=true.
    73@@ -194,9 +190,6 @@ void MiniMiner::SanityCheck() const
    74     Assume(std::all_of(m_entries.begin(), m_entries.end(), [](const auto& entry) {
    75         return entry->second.GetSizeWithAncestors() >= entry->second.GetTxSize() &&
    76                entry->second.GetModFeesWithAncestors() >= entry->second.GetModifiedFee();}));
    77-    // None of the entries should be to-be-replaced transactions
    78-    Assume(std::all_of(m_to_be_replaced.begin(), m_to_be_replaced.end(),
    79-        [&](const auto& txid){return m_entries_by_txid.find(txid) == m_entries_by_txid.end();}));
    80 }
    81 
    82 void MiniMiner::BuildMockTemplate(const CFeeRate& target_feerate)
    

    murchandamus commented at 10:17 pm on March 3, 2023:
    Thanks for the suggestion, going to think about this some more, but don’t feel very strongly about it.

    murchandamus commented at 10:13 pm on March 6, 2023:
    I decided to leave it as is for now.
  41. in src/node/mini_miner.cpp:58 in ce882ef0cf outdated
    58+            m_bump_fees.emplace(outpoint, 0);
    59+        }
    60+    }
    61+
    62+    // No unconfirmed UTXOs, so nothing mempool-related needs to be calculated.
    63+    if (m_requested_outpoints_by_txid.empty()) return;
    


    LarryRuane commented at 5:52 am on March 1, 2023:

    Can we remove this code? (I prefer avoiding special cases.) The only effect difference I can see by eliminating this is that, with it, m_ready_to_calculate will remain true, whereas without it, it will be false. Does that matter? I’m unsure of the purpose of m_ready_to_calculate (in this PR it’s only used by test code, although I understand it may be used in the follow-on PR). Seems like once the constructor runs, it should be ready to calculate, no matter what. There’s nothing else that can be done to make it ready to calculate.

    Is m_ready_to_calculate an error indication, since it seems it can be false only If we hit the DoS limit? If so, how might it used? I think in this case we recover by just not bumping any fees, which is not the end of the world (it’s what happens today). The error indication may be useful in tests (to verify that we hit the DoS limit when expected), but then maybe it should have a better name, like dos_limit_reached.

    But it may be better still to just test the actual effect, i.e., that all the bump fees are zero.


    murchandamus commented at 10:17 pm on March 3, 2023:
    I’ll have to revisit this one.

    glozow commented at 11:20 am on March 6, 2023:

    Is m_ready_to_calculate an error indication, since it seems it can be false only If we hit the DoS limit?

    No it’s not just for indicating DoS limit reached, notice that it is also set to false after BuildMockTemplate is called. It prevents somebody from constructing a MiniMiner and calling CalculateBumpFees() or CalculateTotalBumpFees() multiple times, which could result in very incorrect results if the target feerate changes.

  42. in src/txmempool.cpp:1177 in ce882ef0cf outdated
    1176+            visited(it);
    1177+        }
    1178+        // i = index of where the list of entries to process starts
    1179+        for (size_t i{0}, to_process_count{txids.size()}; i < to_process_count; ++i) {
    1180+            // DoS protection: if not finished after processing 500 entries, just quit.
    1181+            if (to_process_count > 500) return {};
    


    LarryRuane commented at 6:01 am on March 1, 2023:
    Maybe this 500 can be a constexpr in the MiniMiner class? I probably wouldn’t suggest this if this is the only place it occurs, but the tests specify this value too. It might be nice to be able to change this limit by changing a single line of code.

    glozow commented at 10:38 am on March 1, 2023:
    Disagree with txmempool getting this value from mini_miner, as that would create a circular dependency. This kind of constant should live in src/kernel/mempool_options.h.

    murchandamus commented at 7:10 pm on March 3, 2023:
    I’m not sure in how far this needs to be widely visible, since it only affects one function and the corresponding tests.

    LarryRuane commented at 6:57 pm on March 14, 2023:
    That’s fine, suggestion withdrawn :)
  43. in src/node/mini_miner.h:68 in ce882ef0cf outdated
    68+    std::set<uint256> m_to_be_replaced;
    69+
    70+    // If multiple argument outpoints correspond to the same transaction, cache them together in
    71+    // a single entry indexed by txid. Then we can just work with txids since all outpoints from
    72+    // the same tx will have the same bumpfee. Excludes non-mempool transactions.
    73+    std::map<uint256, std::vector<COutPoint>> m_requested_outpoints_by_txid;
    


    LarryRuane commented at 6:32 am on March 1, 2023:

    This isn’t a very efficient data structure, because each entry’s key, the txid, is repeated in all of its vector’s entries (because a COutPoint includes the txid). All you need is the index (COutPoint::n) So this could be:

    0    std::map<uint256, std::vector<uint32_t>> m_requested_outpoints_by_txid;
    

    although the name would be wrong, it’s no longer “requested outpoints”. Elsewhere in the code where you need a COutPoint (I think there are only two places), you can construct it from the key (txid) and this index.


    murchandamus commented at 8:54 pm on March 3, 2023:
    While true, it seems more readable to use the type in the value that I later want than to remember reconstructing it later.
  44. in src/node/mini_miner.cpp:80 in ce882ef0cf outdated
    75+        return;
    76+    }
    77+
    78+    // Add every entry to m_entries_by_txid and m_entries, except the ones that will be replaced.
    79+    for (const auto& txiter : cluster) {
    80+        if (m_to_be_replaced.find(txiter->GetTx().GetHash()) == m_to_be_replaced.end()) {
    


    LarryRuane commented at 6:38 am on March 1, 2023:
    0        if (!m_to_be_replaced.count(txiter->GetTx().GetHash())) {
    

    glozow commented at 10:27 am on March 1, 2023:
    Can you explain why using count is better?

    murchandamus commented at 8:18 pm on March 3, 2023:
    It seems to me that if we don’t use the result of find, it’s clearer that we just care about whether a key is present instead of where in the sequence it appears
  45. in src/node/mini_miner.cpp:102 in ce882ef0cf outdated
     97+    for (const auto& txiter : cluster) {
     98+        const auto& txid = txiter->GetTx().GetHash();
     99+        // Cache descendants for future use. Unlike the real mempool, a descendant MiniMinerMempoolEntry
    100+        // will not exist without its ancestor MiniMinerMempoolEntry, so these sets won't be invalidated.
    101+        std::vector<MockEntryMap::iterator> cached_descendants;
    102+        const bool remove = m_to_be_replaced.find(txid) != m_to_be_replaced.end();
    


    LarryRuane commented at 6:40 am on March 1, 2023:
    0        const bool remove{m_to_be_replaced.count(txid) > 0};
    

    murchandamus commented at 8:49 pm on March 3, 2023:
    Thanks, adopted
  46. in src/node/mini_miner.cpp:108 in ce882ef0cf outdated
    103+        CTxMemPool::setEntries descendants;
    104+        mempool.CalculateDescendants(txiter, descendants);
    105+        Assume(descendants.find(txiter) != descendants.end());
    106+        for (const auto& desc_txiter : descendants) {
    107+            const auto txid_desc = desc_txiter->GetTx().GetHash();
    108+            const bool remove_desc = m_to_be_replaced.find(txid_desc) != m_to_be_replaced.end();
    


    LarryRuane commented at 6:42 am on March 1, 2023:
    0            const bool remove_desc{to_be_replaced.count(&tx_desc) > 0};
    

    murchandamus commented at 8:52 pm on March 3, 2023:
    Thanks
  47. in src/node/mini_miner.cpp:105 in ce882ef0cf outdated
    100+        // will not exist without its ancestor MiniMinerMempoolEntry, so these sets won't be invalidated.
    101+        std::vector<MockEntryMap::iterator> cached_descendants;
    102+        const bool remove = m_to_be_replaced.find(txid) != m_to_be_replaced.end();
    103+        CTxMemPool::setEntries descendants;
    104+        mempool.CalculateDescendants(txiter, descendants);
    105+        Assume(descendants.find(txiter) != descendants.end());
    


    LarryRuane commented at 6:44 am on March 1, 2023:
    0        Assume(descendants.count(txiter) > 0);
    

    murchandamus commented at 8:49 pm on March 3, 2023:
    Thanks
  48. LarryRuane commented at 6:46 am on March 1, 2023: contributor
    Here are a few more, but I’m going to continue to review.
  49. in src/test/fuzz/mini_miner.cpp:65 in ce882ef0cf outdated
    62+            if (fuzzed_data_provider.ConsumeBool()) {
    63+                available_coins.push_front(COutPoint{tx->GetHash(), n});
    64+            } else {
    65+                available_coins.push_back(COutPoint{tx->GetHash(), n});
    66+            }
    67+        }
    


    dergoegge commented at 11:02 am on March 1, 2023:

    The mini_miner target will always produce a cluster of 500 txs right now, because we always add outputs to available_coins. So my suggestion would be to let the fuzzer choose which outputs are added to available_coins.

    0        for (uint32_t n{0}; n < num_outputs; ++n) {
    1            if (fuzzed_data_provider.ConsumeBool()) {
    2                available_coins.push_back(COutPoint{tx->GetHash(), n});
    3            }
    4        }
    

    dergoegge commented at 12:01 pm on March 1, 2023:
    Alternatively, the LIMITED_WHILE condition could be changed.

    dergoegge commented at 12:04 pm on March 1, 2023:

    Also, with my suggested modification there is a crash, which I don’t think is the modifications fault:

    0/wCqamFv0GgmkfHCTmPQeMXAul83pioRsGwGcWUbQCYRX/BcVADDAQm0wQAAAAAAAAAAAAAPAAAA
    1AAAAAA8AAAAAAAAAAAAAAGPQeMXAul83pioRsGwGcWUbKUAGcWUbQCYRX/BcVADDAQm0wQAAAAAA
    2AAAAAAAPAAAAAAAAAA8AAAAAAAAAAAAAAGPQeMXAul83pioRsGwGcWUbKUAmEV/wVFwAwwG0CQAA
    3AAAAAAAA//////+mKhGwbAZxZRtAJhFf8FRcAMMBCbTBAAAAAAAAAAAAAA///////////////2Zm
    4ZmZmZmZmZmZmZgAAAAAAAFw=
    

    glozow commented at 11:55 am on March 2, 2023:
    This input produces an outpoints vector with 2 of the same outpoint, which is what causes it to crash on the line assert(bump_fees.size() == outpoints.size().

    murchandamus commented at 9:13 pm on March 3, 2023:
    Thanks, I changed it to use outpoints only sometimes depending on the consumed boolean as @dergoegge suggested.
  50. in src/test/fuzz/mini_miner.cpp:125 in ce882ef0cf outdated
    120+
    121+        // First 2 outputs are available to spend. The rest are added to outpoints to calculate bumpfees.
    122+        // There is no overlap between spendable coins and outpoints passed to MiniMiner because the
    123+        // MiniMiner interprets spent coins as to-be-replaced and excludes them.
    124+        for (uint32_t n{0}; n < num_outputs - 1; ++n) {
    125+            if (fuzzed_data_provider.ConsumeBool() && fuzzed_data_provider.ConsumeBool()) {
    


    dergoegge commented at 11:10 am on March 1, 2023:
    0            if (fuzzed_data_provider.ConsumeBool()) {
    

    Shouldn’t really make a difference since the fuzzer picks both bools.


    murchandamus commented at 9:25 pm on March 3, 2023:
    Removed second boolean
  51. dergoegge commented at 11:44 am on March 1, 2023: member
    The fuzz targets are looking good but I think we can/should improve the performance. Right now, the input parsing appears to be the bottleneck.
  52. in src/test/fuzz/mini_miner.cpp:77 in ce882ef0cf outdated
    72+                                          (uint32_t)fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0, tx->vout.size())});
    73+        } else {
    74+            // Add some random outpoint (will be interpreted as confirmed or not yet submitted
    75+            // to mempool).
    76+            auto outpoint = ConsumeDeserializable<COutPoint>(fuzzed_data_provider);
    77+            if (outpoint) outpoints.push_back(*outpoint);
    


    glozow commented at 11:53 am on March 2, 2023:

    Sorry ignore my previous review, it was wrong. But this should work:

    0            if (outpoint.has_value() && std::find(outpoints.begin(), outpoints.end(), *outpoint) == outpoints.end()) {
    1                outpoints.push_back(*outpoint);
    2            }
    

    murchandamus commented at 9:17 pm on March 3, 2023:
    Thanks for finding this!
  53. in src/node/mini_miner.cpp:23 in ce882ef0cf outdated
    18+namespace node {
    19+
    20+MiniMiner::MiniMiner(const CTxMemPool& mempool, const std::vector<COutPoint>& outpoints)
    21+{
    22+    LOCK(mempool.cs);
    23+    m_requested_outpoints = outpoints;
    


    glozow commented at 11:57 am on March 2, 2023:
    Just noticed this was added for CalculateTotalBumpFees() - it is redundant with m_requested_outpoints_by_txid, so I think you should remove it and have CalculateTotalBumpFees() iterate through m_requested_outpoints_by_txid’s keys instead.

    murchandamus commented at 7:46 pm on March 3, 2023:
    Removed m_requested_outpoints
  54. in src/test/fuzz/mini_miner.cpp:88 in ce882ef0cf outdated
    83+    assert(mini_miner.IsReadyToCalculate());
    84+    const CFeeRate target_feerate{CFeeRate{ConsumeMoney(fuzzed_data_provider, /*max=*/MAX_MONEY/1000)}};
    85+    if (fuzzed_data_provider.ConsumeBool()) {
    86+        const auto bump_fees = mini_miner.CalculateBumpFees(target_feerate);
    87+        assert(bump_fees.size() == outpoints.size());
    88+        for (const auto& [outpoint, fee] : bump_fees) assert(fee >= 0);
    


    glozow commented at 12:41 pm on March 2, 2023:

    This is more precise than making sure the lengths are the same (and would also fix the crash):

    0        for (const auto& outpoint : outpoints) {
    1            auto it = bump_fees.find(outpoint);
    2            assert(it != bump_fees.end());
    3            assert(it->second >= 0);
    4        }
    

    murchandamus commented at 9:17 pm on March 3, 2023:
    Thanks, adopted your suggestion.
  55. murchandamus commented at 10:28 pm on March 3, 2023: contributor

    Changes since https://github.com/bitcoin/bitcoin/commit/ce882ef0cf338d390733dd85e339a1c0da73072c:

    • rename CalculateCluster(…) to GatherClusters(…), mention function name in commit message
    • clarify that GatherClusters(…) collects all transactions pertaining to multiple clusters, not just one
    • simplified outpoint addition to m_requested_outpoints_by_txid in MiniMiner as suggested by @LarryRuane
    • prefer count over find in some spots when we only want to know whether an element appears in a sequence
    • fix crash in fuzzer due to creating two identical outpoints
    • Remove size reservation for clustered_txs when we in fact cannot predict how large it will be
  56. murchandamus force-pushed on Mar 3, 2023
  57. in src/txmempool.cpp:1157 in 5ee6f89e40 outdated
    1153@@ -1154,43 +1154,43 @@ std::string RemovalReasonToString(const MemPoolRemovalReason& r) noexcept
    1154     assert(false);
    1155 }
    1156 
    1157-std::vector<CTxMemPool::txiter> CTxMemPool::CalculateCluster(const std::vector<uint256>& txids) const
    1158+std::vector<CTxMemPool::txiter> CTxMemPool::GatherClusters(const std::vector<uint256>& txids) const
    


    glozow commented at 11:59 am on March 6, 2023:
    nit: It seems the rename to GatherClusters should have been squashed into efeee8b51d, but is in 5ee6f89e40 instead?

    murchandamus commented at 6:44 pm on March 6, 2023:
    Yeah, the rename was meant to be in the first commit. Thanks
  58. glozow commented at 12:27 pm on March 6, 2023: member
    fwiw, “ACK.” I have reviewed the code including the latest changes and been running the fuzzers for a couple days
  59. in src/txmempool.cpp:1178 in efeee8b51d outdated
    1187+                if (!visited(child_it)) {
    1188+                    cluster.push_back(child_it);
    1189+                    // we still need to process this
    1190+                    ++to_process_count;
    1191+                }
    1192+            }
    


    furszy commented at 4:28 pm on March 6, 2023:

    nit:

    0const txiter& tx_iter = clustered_txs.at(i);
    1for (const auto& entries : {tx_iter->GetMemPoolParentsConst(), tx_iter->GetMemPoolChildrenConst()}) {
    2     for (const CTxMemPoolEntry& entry : entries) {
    3          const auto entry_it = mapTx.iterator_to(entry);
    4          if (!visited(entry_it)) {
    5              clustered_txs.push_back(entry_it);
    6              ++to_process_count;  // we still need to process this
    7           }
    8     }
    9}
    

    murchandamus commented at 9:49 pm on March 6, 2023:
    Great, thanks
  60. in src/txmempool.cpp:1161 in efeee8b51d outdated
    1152@@ -1140,3 +1153,44 @@ std::string RemovalReasonToString(const MemPoolRemovalReason& r) noexcept
    1153     }
    1154     assert(false);
    1155 }
    1156+
    1157+std::vector<CTxMemPool::txiter> CTxMemPool::CalculateCluster(const std::vector<uint256>& txids) const
    1158+{
    1159+    AssertLockHeld(cs);
    1160+    std::vector<txiter> cluster{GetIterVec(txids)};
    1161+    if (cluster.size() != txids.size()) {
    


    furszy commented at 4:31 pm on March 6, 2023:
    nit: this can just be cluster.empty()

    murchandamus commented at 9:56 pm on March 6, 2023:
    Good catch
  61. in src/txmempool.cpp:1160 in efeee8b51d outdated
    1152@@ -1140,3 +1153,44 @@ std::string RemovalReasonToString(const MemPoolRemovalReason& r) noexcept
    1153     }
    1154     assert(false);
    1155 }
    1156+
    1157+std::vector<CTxMemPool::txiter> CTxMemPool::CalculateCluster(const std::vector<uint256>& txids) const
    1158+{
    1159+    AssertLockHeld(cs);
    1160+    std::vector<txiter> cluster{GetIterVec(txids)};
    


    furszy commented at 4:35 pm on March 6, 2023:

    Could add above this line an early return:

    0if (txids.size > 500) return {};
    

    murchandamus commented at 9:57 pm on March 6, 2023:
    Okay, added
  62. in src/node/mini_miner.cpp:61 in 5ee6f89e40 outdated
    56+    // No unconfirmed UTXOs, so nothing mempool-related needs to be calculated.
    57+    if (m_requested_outpoints_by_txid.empty()) return;
    58+
    59+    // Calculate the cluster and construct the entry map.
    60+    std::vector<uint256> txids_needed;
    61+    for (const auto& [txid, outpoints]: m_requested_outpoints_by_txid) {
    


    furszy commented at 4:41 pm on March 6, 2023:

    ‘outpoints’ naming shadows the function’s arg. Could

    0for (const auto& [txid, _] : m_requested_outpoints_by_txid) {
    

    murchandamus commented at 9:58 pm on March 6, 2023:
    You’re right, fixed
  63. in src/txmempool.h:596 in efeee8b51d outdated
    591@@ -585,6 +592,10 @@ class CTxMemPool
    592         const Limits& limits,
    593         bool fSearchForParents = true) const EXCLUSIVE_LOCKS_REQUIRED(cs);
    594 
    595+    /** Get entire list of connected transactions for all transactions in txids. All txids must
    596+     * correspond to transactions in the mempool, otherwise this returns an empty vector. */
    


    mzumsande commented at 4:51 pm on March 6, 2023:
    I think that it would be good to mention the 500 entries DoS limit here, plus the fact that we also return an empty vector if that is limit is breached - since that’s something possible future users of this function would want to know about.

    murchandamus commented at 9:14 pm on March 14, 2023:
    I’ve updated the comment to mention the 500 entry limit and the resulting empty vector.
  64. dergoegge commented at 5:36 pm on March 6, 2023: member

    Another crash from the mini_miner target:

    0YFxlvAD6+fv7+/8BAADYAAAPZWVlZWVlZV9lZWVlZWVlZWVlZWVlZWVlZWVlZWVlZWVlZWVlZWVl
    1ZWVlZWVlZWUgAGVlEWQX7AjobniKnjZtdcp6KPeFnFv/C89XAtDnqxwRFkNlZWVlZWVlZWVlZWVl
    2ZWVlZWVlZWVlZWVlZWVlZWVlZSVlZWVlZWVlY2VlZWVlZWVlZWVlZWVlZWVlZWVlZWVlZWVlZWVl
    3ZWVlZWVlZWVlZWVlZ2VlZWVlZWVlZWVlZWVlZWVlZWVlZWVlZWVlZWNtZWVlZWXNUm8gQwAAAGVl
    4ZWVlZWVlZWVlZWVlZWVlZWVlZWVclwAAtf//ZWVlAAAAAAY=
    
  65. murchandamus force-pushed on Mar 6, 2023
  66. murchandamus commented at 6:50 pm on March 6, 2023: contributor
    Moved rename of GatherClusters(…) to the right commit. Looking into the crash of the fuzzer.
  67. furszy commented at 7:40 pm on March 6, 2023: member
    Just started, need to go over it in more detail still. Left few nits.
  68. murchandamus force-pushed on Mar 6, 2023
  69. murchandamus commented at 10:15 pm on March 6, 2023: contributor

    Changes since https://github.com/bitcoin/bitcoin/commit/32123cfc11ad22cdd7fe5ef26ac0550e1ab2fe7b:

    • Addressed remaining review from @LarryRuane
    • Fixed renaming of GatherClusters(…) being in the wrong commit
    • Fixed crash bug surfaced by @dergoegge
    • Addressed review by @furszy
  70. murchandamus force-pushed on Mar 7, 2023
  71. murchandamus commented at 12:20 pm on March 7, 2023: contributor
    Added myself as co-author to some commits per invitation of @glozow
  72. in src/test/miniminer_tests.cpp:182 in 5eb0158470 outdated
    177+            BOOST_CHECK_EQUAL(it1_unspent->second, 0);
    178+        } else {
    179+            // Difference is fee to bump tx1 from current to target feerate.
    180+            BOOST_CHECK_EQUAL(it1_unspent->second,
    181+                target_feerate.GetFee(tx_vsizes.find(tx1->GetHash())->second) - tx_modified_fees.find(tx1->GetHash())->second);
    182+    }
    


    mzumsande commented at 9:10 pm on March 7, 2023:
    Indentation is broken, here and below (I initially thought the for loop ended here).
  73. in src/node/mini_miner.h:20 in a0d54e6b8f outdated
    15+
    16+// Container for tracking updates to ancestor feerate as we include ancestors in the "block"
    17+class MiniMinerMempoolEntry
    18+{
    19+    const CAmount fee_individual;
    20+    const CTransaction tx;
    


    furszy commented at 1:23 pm on March 9, 2023:

    This can be a CTransactionRef (aka shared_ptr) and not a plain tx copy. Transaction data never changes.

    Just need to adapt the constructor to call GetSharedTx instead.


    murchandamus commented at 10:42 pm on March 14, 2023:
    Thanks, I adopted your suggestion.
  74. in src/node/mini_miner.cpp:34 in a0d54e6b8f outdated
    29+            // We assume that the caller wants to replace this transaction (and its descendants).
    30+            // If the outpoint is from a mempool transaction, we still need to calculate its
    31+            // ancestors bump fees (added to m_requested_outpoints_by_txid below), but after
    32+            // removing the to-be-replaced entries. Note that this is only calculating bump fees.
    33+            // RBF fee rules should be handled separately.
    34+            m_to_be_replaced.insert(ptx->GetHash());
    


    furszy commented at 2:00 pm on March 9, 2023:

    In a0d54e6b:

    mempool.CalculateDescendants returns the base parent transaction. So you could remove this line and add a comment to remember it.


    murchandamus commented at 9:16 pm on March 14, 2023:
    Good catch. I’ve removed the line and amended the comment to clarify that the transaction is part of the descendants.
  75. in src/node/mini_miner.cpp:53 in a0d54e6b8f outdated
    48+        } else {
    49+            // This UTXO is either confirmed or not yet submitted to mempool.
    50+            // If it's confirmed, no bump fee is required.
    51+            // If it's not yet submitted, we have no information, so return 0.
    52+            m_bump_fees.emplace(outpoint, 0);
    53+        }
    


    furszy commented at 2:17 pm on March 9, 2023:

    In https://github.com/bitcoin/bitcoin/commit/a0d54e6b8f8afab070de48911f3b11d4cdf289ff:

    nit: Could prevent extra GetConflictTx calls by moving the conflicting tx block of code inside the mempool.exists block. e.g.

     0for (const auto& outpoint : outpoints) {
     1     if (!mempool.exists(GenTxid::Txid(outpoint.hash))) {
     2         // This UTXO is either confirmed or not yet submitted to mempool.
     3         // If it's confirmed, no bump fee is required.
     4         // If it's not yet submitted, we have no information, so return 0.
     5         m_bump_fees.emplace(outpoint, 0);
     6         continue;
     7     }
     8
     9     // UXTO is created by transaction in mempool, add to map.
    10     // Note: This will either create a missing entry or add the outpoint to an existing entry
    11     m_requested_outpoints_by_txid[outpoint.hash].push_back(outpoint);
    12
    13     if (const auto ptx{mempool.GetConflictTx(outpoint)}) {
    14         // This outpoint is already being spent by another transaction in the mempool.
    15         // We assume that the caller wants to replace this transaction (and its descendants).
    16         // If the outpoint is from a mempool transaction, we still need to calculate its
    17         // ancestors bump fees (added to m_requested_outpoints_by_txid below), but after
    18         // removing the to-be-replaced entries. Note that this is only calculating bump fees.
    19         // RBF fee rules should be handled separately.
    20         
    21         // Remove conflicting tx and descendants because they will be replaced as well. This case should be rare
    22         // as the wallet won't normally attempt to replace transactions with descendants.
    23         CTxMemPool::setEntries descendants;
    24         mempool.CalculateDescendants(mempool.GetIter(ptx->GetHash()).value(), descendants);
    25         for (const auto& desc_txiter : descendants) {
    26                m_to_be_replaced.insert(desc_txiter->GetTx().GetHash());
    27           }
    28     }
    29}
    

    murchandamus commented at 9:17 pm on March 14, 2023:
    Thanks, I’ve adopted your suggestion and moved !mempool.exists first.
  76. in src/node/mini_miner.cpp:102 in a0d54e6b8f outdated
     95+        std::vector<MockEntryMap::iterator> cached_descendants;
     96+        const bool remove{m_to_be_replaced.count(txid) > 0};
     97+        CTxMemPool::setEntries descendants;
     98+        mempool.CalculateDescendants(txiter, descendants);
     99+        Assume(descendants.count(txiter) > 0);
    100+        for (const auto& desc_txiter : descendants) {
    


    furszy commented at 9:19 pm on March 9, 2023:

    This has been puzzling me for a while.

    It is not clear to me why need to calculate the descendants once more if the information is available in the cluster (it is just not accesible because data is unordered). Couldn’t return from GatherCluster a map of tx id and its descendants instead? Like first going up into the DAG, starting with the highest parents, and then build the map<tx_id, vector> with a recursive children call. It looks like a heavy waste to recalculate the same twice.

    or well.. it is not that heavy because you set the 500 entries limit. hmm.. it still is duplicated work but it has a limit.

    Another point is why continue traversing the children when the parent was marked to be removed? To double assert that the previous loop worked as expected? (if that is the case, what about decoupling the previous loop into a separate function and adding unit test coverage instead of all the runtime Assume calls?).


    murchandamus commented at 11:05 pm on March 14, 2023:
    I see how this might be a performance improvement, but I don’t think this is going to be heavy enough to warrant this level of rewrite at this stage in the PR. Perhaps this could be done in a follow-up.
  77. furszy commented at 9:30 pm on March 9, 2023: member
    I’m still wrapping my head around this work but left few comments on the way.
  78. in src/node/mini_miner.cpp:157 in d227d394cd outdated
    141+            return a_feerate > b_feerate;
    142+        }
    143+        // Compare by txid
    144+        return a->first < b->first;
    145+    }
    146+};
    


    LarryRuane commented at 0:08 am on March 10, 2023:

    This may be easier to comprehend:

     0// Compare by min(ancestor feerate, individual feerate), then iterator.
     1//
     2// The ancestor feerate of a high-feerate tx should be reduced by its
     3// low-feerate ancestors, but the ancestor feerate of a low-feerate tx
     4// should not be increased by its high-feerate ancestors.
     5struct AncestorFeerateComparator
     6{
     7    template<typename I>
     8    bool operator()(const I& a, const I& b) const {
     9        auto min_feerate = [](const MiniMinerMempoolEntry& e) -> CFeeRate {
    10            const CAmount afee{e.GetModFeesWithAncestors()};
    11            const int64_t asize{e.GetSizeWithAncestors()};
    12            const CAmount fee{e.GetModifiedFee()};
    13            const int64_t size{e.GetTxSize()};
    14            // Comparing ancestor feerate with individual feerate:
    15            //     afee / asize <= fee / size
    16            // Avoid division and possible loss of precision by
    17            // multiplying both sides by the sizes:
    18            return afee * size < fee * asize ?
    19                       CFeeRate(afee, asize) :
    20                       CFeeRate(fee, size);
    21        };
    22        CFeeRate a_feerate{min_feerate(a->second)};
    23        CFeeRate b_feerate{min_feerate(b->second)};
    24        if (a_feerate != b_feerate) {
    25            return a_feerate > b_feerate;
    26        }
    27        // Compare by txid
    28        return a->first < b->first;
    29    }
    30};
    

    murchandamus commented at 10:31 pm on March 14, 2023:
    Thanks I took your suggestion with slightly more elaborate variable names.
  79. murchandamus force-pushed on Mar 10, 2023
  80. murchandamus commented at 2:03 am on March 10, 2023: contributor
    Thanks, I’m just seeing the review comments, I will continue looking into them tomorrow. I just pushed a documentation change for CalculateBumpFees(…), after I spent large parts of the day figuring out why the fuzzer had produced a crash and convincing myself that the fix was actually correct.
  81. in src/test/fuzz/mini_miner.cpp:85 in cf1636078f outdated
    80+    }
    81+
    82+    node::MiniMiner mini_miner{pool, outpoints};
    83+    assert(mini_miner.IsReadyToCalculate());
    84+    const CFeeRate target_feerate{CFeeRate{ConsumeMoney(fuzzed_data_provider, /*max=*/MAX_MONEY/1000)}};
    85+    if (fuzzed_data_provider.ConsumeBool()) {
    


    mzumsande commented at 4:40 am on March 12, 2023:
    I was curious about a possible relation between sum(CalculateBumpFees) over all outpoints, and CalculateTotalBumpFees for the same outpoints / target feerate. My naive thought was that taking the sum over CalculateBumpFees might overestimate the total bump fee by counting the bumping of some mempool txs twice if there is a shared ancestry, and that the quantities should be equal if there is no shared ancestry. As a result, CalculateTotalBumpFees should never be larger than the sum of CalculateBumpFees. But when I tried to test this hypothesis by changing the fuzz test here to not calculate just one but both quantities in each run (using two mini miners, see https://github.com/mzumsande/bitcoin/commit/e690c11a4c8e1d2d23037cc5439366ce722a9ef2) and then asserting that the above relation holds, it quickly fails - so where did I go wrong?

    murchandamus commented at 8:55 pm on March 13, 2023:
    Thanks, that’s unexpected. I would also expect that CalculateTotalBumpFees(…) always is equal or smaller to the sum of individual bump fees. I’ll check it out.

    mzumsande commented at 8:18 pm on March 14, 2023:
    I commented below for this. After fixing this, the fuzzer doesn’t crash anymore (at least not immediately, haven’t run it for long). I wonder if it might make sense to adjust the fuzz test permanently similar to my branch above and assert sum(CalculateBumpFees) >= CalculateTotalBumpFees(), if that is really the expectation - in general, I like it if fuzz tests contain asserts that test actual non-trivial high-level expectations we have for the code, and don’t just run over the code “blindly”.

    murchandamus commented at 10:52 pm on March 14, 2023:
    Thanks, this improves the fuzzer. I’ve adopted your suggested change.
  82. in src/txmempool.cpp:1177 in cf1636078f outdated
    1172+            visited(it);
    1173+        }
    1174+        // i = index of where the list of entries to process starts
    1175+        for (size_t i{0}, to_process_count{txids.size()}; i < to_process_count; ++i) {
    1176+            // DoS protection: if not finished after processing 500 entries, just quit.
    1177+            if (to_process_count > 500) return {};
    


    LarryRuane commented at 6:51 pm on March 14, 2023:
    nit, it would be more logical for this check to be just after to_process_count is incremented below.

    murchandamus commented at 7:33 pm on March 27, 2023:
    Since I’ve removed the special casing that makes us bail if we start with 500 in the first place, I have left it at the start of the loop.
  83. in src/txmempool.cpp:1175 in cf1636078f outdated
    1170+        WITH_FRESH_EPOCH(m_epoch);
    1171+        for (const auto& it : clustered_txs) {
    1172+            visited(it);
    1173+        }
    1174+        // i = index of where the list of entries to process starts
    1175+        for (size_t i{0}, to_process_count{txids.size()}; i < to_process_count; ++i) {
    


    LarryRuane commented at 6:53 pm on March 14, 2023:

    nit, I think you could eliminate the to_process_count variable, and just use the vector size instead.

    0        for (size_t i{0}; i < clustered_txs.size(); ++i) {
    

    murchandamus commented at 7:34 pm on March 27, 2023:
    I’ve adopted your suggestion, thanks
  84. in src/txmempool.cpp:1166 in cf1636078f outdated
    1161+    std::vector<txiter> clustered_txs{GetIterVec(txids)};
    1162+    if (clustered_txs.empty()) {
    1163+        // We can't continue because the caller specified a tx that doesn't exist in the mempool.
    1164+        // Return an empty vector to let them know this failed.
    1165+        return {};
    1166+    }
    


    LarryRuane commented at 6:54 pm on March 14, 2023:
    nit, I think you can remove this code. (It’s nice to eliminate special-case code, not only for simplicity, but to reduce testing.)

    murchandamus commented at 7:36 pm on March 27, 2023:
    Right, if txids is empty, we already return an empty vector anyway, and the 500 limit is already checked at the start of the loop. Sorry, @furszy, I changed my mind about your prior suggestion to add an early exit.
  85. in src/node/mini_miner.cpp:354 in 82d068ea0e outdated
    349+            to_process.erase(iter);
    350+        }
    351+    }
    352+    const auto ancestor_package_size = std::accumulate(ancestors.cbegin(), ancestors.cend(), 0,
    353+        [](int64_t sum, const auto it) {return sum + it->second.GetTxSize();});
    354+    const auto ancestor_package_fee = std::accumulate(ancestors.cbegin(), ancestors.cend(), 0,
    


    mzumsande commented at 8:09 pm on March 14, 2023:
    The init value should be CAmount{0}, not 0 which would convert the summed items to int, see std::accumulate under “Common mistakes”. This caused the unexpected fuzzer behavior I saw, because the int could overflow. Also, for ancestor_package_size, the init value should be int64_t{0};

    murchandamus commented at 10:34 pm on March 14, 2023:
    Uff, great catch, thanks!
  86. murchandamus commented at 10:56 pm on March 14, 2023: contributor

    Changes between e5b382a3db5167c118329f1885660d16e0192d22 and https://github.com/bitcoin/bitcoin/commit/730bff20c1f76c46a7ab6c8d981126fe3ad2cec9:

    • Addressed review comments by @furszy, @LarryRuane, and @mzumsande. Thanks!
    • Added more documentation to CalculateBumpFee()
    • Moved mempool.exists check to the front to reduce potential calls to GetConflictTx()
    • Fixed overflow bug in ancestor_package_size accumulator
    • Elaborate on AncestorFeerateComparator
    • Build MiniMinerMempoolEntries with CTransactionRefs instead of copies
    • Check in fuzzer that CalculateTotalBumpFees() <= sum(CalculateBumpFees())
    • Improved documentation for GatherClusters()
  87. murchandamus force-pushed on Mar 14, 2023
  88. murchandamus force-pushed on Mar 14, 2023
  89. murchandamus commented at 3:17 pm on March 15, 2023: contributor
    I’ve run both of the fuzz targets for 48-CPU-hours last night, and have not seen another crash bug.
  90. theStack commented at 7:50 am on March 16, 2023: contributor

    Concept ACK

    I’m wondering if there’s a strong need to put zero-bump entries into the m_bump_fees map for UTXOs which are not relevant for further processing (i.e. if they are confirmed / not yet submitted to mempool / outputs of a to-be-replaced tx)? If not, here’s a suggestion for simplification (note that the used variant of std::map::erase doesn’t do any harm if the passed key doesn’t exist), non-blocking of course:

     0diff --git a/src/node/mini_miner.cpp b/src/node/mini_miner.cpp
     1index a41c8610b..87ee488d9 100644
     2--- a/src/node/mini_miner.cpp
     3+++ b/src/node/mini_miner.cpp
     4@@ -27,8 +27,7 @@ MiniMiner::MiniMiner(const CTxMemPool& mempool, const std::vector<COutPoint>& ou
     5         if (!mempool.exists(GenTxid::Txid(outpoint.hash))) {
     6             // This UTXO is either confirmed or not yet submitted to mempool.
     7             // If it's confirmed, no bump fee is required.
     8-            // If it's not yet submitted, we have no information, so return 0.
     9-            m_bump_fees.emplace(outpoint, 0);
    10+            // If it's not yet submitted, we have no information.
    11             continue;
    12         }
    13 
    14@@ -76,15 +75,9 @@ MiniMiner::MiniMiner(const CTxMemPool& mempool, const std::vector<COutPoint>& ou
    15             auto [mapiter, success] = m_entries_by_txid.emplace(txiter->GetTx().GetHash(), MiniMinerMempoolEntry(txiter));
    16             m_entries.push_back(mapiter);
    17         } else {
    18-            auto outpoints_it = m_requested_outpoints_by_txid.find(txiter->GetTx().GetHash());
    19-            if (outpoints_it != m_requested_outpoints_by_txid.end()) {
    20-                // This UTXO is the output of a to-be-replaced transaction. Bump fee is 0; spending
    21-                // this UTXO is impossible as it will no longer exist after the replacement.
    22-                for (const auto& outpoint : outpoints_it->second) {
    23-                    m_bump_fees.emplace(outpoint, 0);
    24-                }
    25-                m_requested_outpoints_by_txid.erase(outpoints_it);
    26-            }
    27+            // This UTXO is the output of a to-be-replaced transaction. Spending
    28+            // this UTXO is impossible as it will no longer exist after the replacement.
    29+            m_requested_outpoints_by_txid.erase(txiter->GetTx().GetHash());
    30         }
    31     }
    32 
    33diff --git a/src/test/miniminer_tests.cpp b/src/test/miniminer_tests.cpp
    34index 1f4c1862a..3e066d621 100644
    35--- a/src/test/miniminer_tests.cpp
    36+++ b/src/test/miniminer_tests.cpp
    37@@ -153,12 +153,7 @@ BOOST_FIXTURE_TEST_CASE(miniminer_1p1c, TestChain100Setup)
    38         auto bump_fees = mini_miner.CalculateBumpFees(feerate);
    39         BOOST_CHECK(!mini_miner.IsReadyToCalculate());
    40         BOOST_CHECK(sanity_check(all_transactions, bump_fees));
    41-        BOOST_CHECK(bump_fees.size() == nonexistent_outpoints.size());
    42-        for (const auto& outpoint: nonexistent_outpoints) {
    43-            auto it = bump_fees.find(outpoint);
    44-            BOOST_CHECK(it != bump_fees.end());
    45-            BOOST_CHECK_EQUAL(it->second, 0);
    46-        }
    47+        BOOST_CHECK(bump_fees.size() == 0);
    48     }
    49 
    50     // Gather bump fees for all available UTXOs.
    
  91. murchandamus commented at 8:17 pm on March 16, 2023: contributor
    @theStack: Thanks for the suggestion. I tried implementing this and found that it does save the six lines here, but it also required special casing two places downstream in my follow-up PR. While the fixes were simple, I feel that it makes the interface slightly worse for the downstream consumer, so I’m ambivalent on the change.
  92. glozow requested review from theStack on Mar 21, 2023
  93. glozow requested review from furszy on Mar 21, 2023
  94. glozow requested review from LarryRuane on Mar 21, 2023
  95. glozow removed review request from LarryRuane on Mar 21, 2023
  96. glozow requested review from achow101 on Mar 21, 2023
  97. glozow requested review from LarryRuane on Mar 21, 2023
  98. achow101 commented at 8:30 pm on March 21, 2023: member
    ACK 730bff20c1f76c46a7ab6c8d981126fe3ad2cec9
  99. DrahtBot removed review request from achow101 on Mar 21, 2023
  100. DrahtBot removed review request from LarryRuane on Mar 21, 2023
  101. in src/node/mini_miner.h:43 in ad34243f15 outdated
    38+    int64_t GetTxSize() const { return vsize_individual; }
    39+    int64_t GetSizeWithAncestors() const { return vsize_with_ancestors; }
    40+    const CTransaction& GetTx() const LIFETIMEBOUND { return *tx; }
    41+};
    42+
    43+void UpdateForMinedAncestor(const MiniMinerMempoolEntry& ancestor, const MiniMinerMempoolEntry& descendant);
    


    furszy commented at 8:09 pm on March 22, 2023:
    Unimplemented function

    murchandamus commented at 6:41 pm on March 27, 2023:
    Removed unimplemented function
  102. in src/node/mini_miner.cpp:174 in ad34243f15 outdated
    168+        // Each entry’s descendant set includes itself
    169+        Assume(it != m_descendant_set_by_txid.end());
    170+        for (auto& descendant : it->second) {
    171+            // If these fail, we must be double-deducting.
    172+            Assume(descendant->second.GetModFeesWithAncestors() >= anc->second.GetModifiedFee());
    173+            Assume(descendant->second.vsize_with_ancestors >= anc->second.GetTxSize());
    


    furszy commented at 8:21 pm on March 22, 2023:

    Strictly speaking, the descendant size can only be greater than the ancestor size.

    0            Assume(descendant->second.vsize_with_ancestors > anc->second.GetTxSize());
    

    furszy commented at 8:28 pm on March 22, 2023:
    As the ancestors structure is a set and we are merely looping over it, I don’t see how this can realistically happen. Two different iterators pointing to the same object? (if that is the worry, then the problem is with the iterators usage approach)

    murchandamus commented at 3:10 pm on March 27, 2023:

    I am not sure I follow. For historical reasons, transactions are included in their own ancestor set and their own descendant set. So while we are iterating over descendants, we could be evaluating a transaction itself that has no ancestors left after they were picked into our “virtual block”. If the evaluated transaction doesn’t have ancestors left, and we get its size with ancestors, we are comparing its own size with its own size in this inequality. Therefore, same size must be permitted.

    I tested my expectation that this would cause failures by turning the Assume into an assert and then running with either >= or >. The assert is triggered for >.


    murchandamus commented at 3:26 pm on March 27, 2023:
    See response on prior comment
  103. in src/node/mini_miner.cpp:190 in ad34243f15 outdated
    184+        Assume(anc->second.GetSizeWithAncestors() == 0);
    185+        auto vec_it = std::find(m_entries.begin(), m_entries.end(), anc);
    186+        Assume(vec_it != m_entries.end());
    187+        m_entries.erase(vec_it);
    188+        m_entries_by_txid.erase(anc);
    189+    }
    


    furszy commented at 8:49 pm on March 22, 2023:

    What is the reason behind this separate removal loop? Couldn’t we merge it with the loop that is above?

    Are you worry about the ancestors set having a parent and a child so if first removes the child then the parent will not find it and then crash?


    murchandamus commented at 3:42 pm on March 27, 2023:
    Yeah, it felt safer to first update everything, then to start deleting things. I did try combining the loops and it did not break anything, though. Still deciding, maybe this could be a follow-up.
  104. furszy commented at 9:09 pm on March 22, 2023: member
    left few questions, will keep moving
  105. in src/node/mini_miner.cpp:351 in ad34243f15 outdated
    346+            to_process.insert(iter);
    347+            ancestors.insert(iter);
    348+        }
    349+        while (!to_process.empty()) {
    350+            auto iter = to_process.begin();
    351+            assert(iter != to_process.end());
    


    furszy commented at 4:41 pm on March 23, 2023:
    nit: isn’t this assertion redundant? If iter would be equal to end(), then to_process.empty() would be true. Which breaks the loop.

    murchandamus commented at 6:36 pm on March 27, 2023:
    Yeah, agreed. Gonna remove it
  106. in src/node/mini_miner.cpp:338 in ad34243f15 outdated
    333+    // Build a block template until the target feerate is hit.
    334+    BuildMockTemplate(target_feerate);
    335+
    336+    // All remaining ancestors that are not part of m_in_block must be bumped, but no other relatives
    337+    std::set<MockEntryMap::iterator, IteratorComparator> ancestors;
    338+    {
    


    theStack commented at 10:08 pm on March 23, 2023:
    nit: Seems like this pair of curly-braces and the extra-indent is a left-over from earlier code (probably involving a LOCK?) and can just be removed.

    murchandamus commented at 3:43 pm on March 27, 2023:
    Thanks, removed extraneous curly braces
  107. in src/test/miniminer_tests.cpp:204 in 5bcc04c5c0 outdated
    199+            tx_modified_fees.find(tx5->GetHash())->second + tx_modified_fees.find(tx6->GetHash())->second,
    200+            tx_vsizes.find(tx5->GetHash())->second + tx_vsizes.find(tx6->GetHash())->second);
    201+        auto it5_unspent = bump_fees.find(COutPoint{tx5->GetHash(), 1});
    202+        BOOST_CHECK(it5_unspent != bump_fees.end());
    203+        if (target_feerate <= tx5_feerate) {
    204+            // As long as target feerate is below tx4's ancestor feerate, there is no bump fee.
    


    murchandamus commented at 10:13 pm on March 23, 2023:
    0            // As long as target feerate is below tx6's ancestor feerate, there is no bump fee.
    
  108. in src/test/miniminer_tests.cpp:47 in 5bcc04c5c0 outdated
    40+                                const std::map<COutPoint, CAmount>& bumpfees)
    41+{
    42+    // No negative bumpfees.
    43+    for (const auto& [outpoint, fee] : bumpfees) {
    44+        if (fee < 0) return false;
    45+    }
    


    theStack commented at 10:29 pm on March 23, 2023:

    minor suggestion: in the unit test’s sanity_check function, could also check that all (positive) bumpfee entries refer to one of the passed tx’s:

    0    // No negative bumpfees. All positive bumpfees must refer to one of the passed tx's outputs.
    1    for (const auto& [outpoint, fee] : bumpfees) {
    2        if (fee < 0) return false;
    3        if (fee == 0) continue;
    4        auto outpoint_ = outpoint; // structured bindings can't be captured in C++17, so we need to use a variable
    5        const bool found = std::any_of(transactions.cbegin(), transactions.cend(), [&](const auto& tx) {
    6            return outpoint_.hash == tx->GetHash() && outpoint_.n < tx->vout.size();
    7        });
    8        if (!found) return false;
    9    }
    

    (unfortunately a bit ugly with this extra variable needed… C++20 fixes this).


    murchandamus commented at 7:44 pm on March 27, 2023:
    Thanks that sounds like a good idea.
  109. in src/test/miniminer_tests.cpp:216 in 5bcc04c5c0 outdated
    198+        const auto tx5_feerate = CFeeRate(
    199+            tx_modified_fees.find(tx5->GetHash())->second + tx_modified_fees.find(tx6->GetHash())->second,
    200+            tx_vsizes.find(tx5->GetHash())->second + tx_vsizes.find(tx6->GetHash())->second);
    201+        auto it5_unspent = bump_fees.find(COutPoint{tx5->GetHash(), 1});
    202+        BOOST_CHECK(it5_unspent != bump_fees.end());
    203+        if (target_feerate <= tx5_feerate) {
    


    furszy commented at 10:35 pm on March 23, 2023:

    This is just a nit but I wouldn’t call this tx5_feerate, it’s the tx5_tx6_package_feerate.

    At least in my head, when we talk about certain tx feerate, we talk about the relation between the tx ancestors fee and their size (including the tx itself). Which does not include the descendants (in this case, tx6)


    murchandamus commented at 8:56 pm on March 27, 2023:
    I’ve renamed the variable and better explained what’s going on here.
  110. in src/test/miniminer_tests.cpp:136 in 5bcc04c5c0 outdated
    131+    std::map<uint256, int64_t> tx_vsizes;
    132+    std::map<uint256, CAmount> tx_modified_fees;
    133+    std::map<uint256, CFeeRate> tx_feerates;
    134+    for (const auto& tx : all_transactions) {
    135+        const auto entry = pool.GetIter(tx->GetHash()).value();
    136+        all_entries.push_back(entry);
    


    furszy commented at 10:36 pm on March 23, 2023:
    all_entries is not used anywhere.

    murchandamus commented at 7:59 pm on March 27, 2023:
    I’ve removed all_entries. Thanks for catching that
  111. furszy commented at 11:31 pm on March 23, 2023: member

    Left few more comments.

    Plus, while was checking the 1p1c test, couldn’t resist myself and made it more friendly https://github.com/furszy/bitcoin-core/commit/5dc4b8957c7a65746666cb5f3e7bd6270b21f8c2. Feel free to take it if you like it.

  112. in src/test/miniminer_tests.cpp:217 in 5bcc04c5c0 outdated
    204+            // As long as target feerate is below tx4's ancestor feerate, there is no bump fee.
    205+            BOOST_CHECK_EQUAL(it5_unspent->second, 0);
    206+        } else {
    207+            // Difference is fee to bump tx5 from current to target feerate, without tx6.
    208+            BOOST_CHECK_EQUAL(it5_unspent->second,
    209+                target_feerate.GetFee(tx_vsizes.find(tx5->GetHash())->second) - tx_modified_fees.find(tx5->GetHash())->second);
    


    theStack commented at 1:26 am on March 24, 2023:
    This else-branch is currently dead code (as can easily be verified by putting an assert(false) inside); due to the huge modified fee-rate of tx6, tx5/tx6 are way above all of the tested fee-rate-targets (>1000sats/vbyte) and always get mini-mined, i.e. no fee-bump happens. See also review comment below.

    murchandamus commented at 7:57 pm on March 27, 2023:
    Thanks for catching that. I amended the above fee and tested that this else-branch now is executed.
  113. in src/test/miniminer_tests.cpp:89 in 5bcc04c5c0 outdated
    84+    pool.addUnchecked(entry.Fee(low_fee).FromTx(tx5));
    85+    const auto tx6 = make_tx({COutPoint{tx5->GetHash(), 0}}, /*num_outputs=*/1);
    86+    pool.addUnchecked(entry.Fee(low_fee).FromTx(tx6));
    87+    // Make tx6's modified fee much higher than its base fee. This should cause it to pass
    88+    // the fee-related checks despite being low-feerate.
    89+    pool.PrioritiseTransaction(tx6->GetHash(), COIN);
    


    theStack commented at 1:32 am on March 24, 2023:
    This fee delta seems excessive (leading to a fee-rate of >1 million sats/vbyte for tx6), I guess just using one of {high,normal,low}_fee should also be fine? Then the testing code-path of getting a bumpfee for tx5/tx6 would be hit (see also comment above).

    murchandamus commented at 7:58 pm on March 27, 2023:
    Thanks, I’ve reduced the fee used here and verified that the else branch mentioned below now gets traversed
  114. in src/test/miniminer_tests.cpp:28 in 5bcc04c5c0 outdated
    23+    for (size_t i = 0; i < inputs.size(); ++i) {
    24+        tx.vin[i].prevout = inputs[i];
    25+        // Add a witness so wtxid != txid
    26+        CScriptWitness witness;
    27+        witness.stack.push_back(std::vector<unsigned char>(i + 10));
    28+        tx.vin[i].scriptWitness = witness;
    


    theStack commented at 1:45 am on March 24, 2023:

    nit: Not that it harms in any way, but wtxid seems not to be relevant for these unit tests, so could remove this.


    murchandamus commented at 8:57 pm on March 27, 2023:
    Thanks, I’ve removed the unnecessary definitions here
  115. LarryRuane commented at 9:57 pm on March 24, 2023: contributor
    A few small things, I’ll continue to review…
  116. in src/test/miniminer_tests.cpp:412 in 5bcc04c5c0 outdated
    407+        BOOST_CHECK_EQUAL(tx8_bumpfee->second, 0);
    408+    }
    409+}
    410+BOOST_FIXTURE_TEST_CASE(calculate_cluster, TestChain100Setup)
    411+{
    412+    FastRandomContext det_rand{true};
    


    theStack commented at 7:06 pm on March 25, 2023:

    nit: unused variable, can be removed


    murchandamus commented at 7:54 pm on March 27, 2023:
    Thanks, removed
  117. in src/test/miniminer_tests.cpp:442 in 5bcc04c5c0 outdated
    437+
    438+    // Zig Zag cluster:
    439+    // txp0     txp1     txp2    ...  txp48  txp49
    440+    //    \    /    \   /   \            \   /
    441+    //     txc0     txc1    txc2  ...    txc48
    442+    // Note that each transaction's ancestor size is 2 or 3, and each descendant size is 2 or 3.
    


    theStack commented at 7:10 pm on March 25, 2023:

    pedantic-nit:

    0    // Note that each transaction's ancestor size is 1 or 3, and each descendant size is 1, 2 or 3.
    

    The descendant count of 2 is the rare case here, only applying for parent-txs txp0 and txp49 (for the fun of it, created a functional test for verifying this: https://github.com/theStack/bitcoin/blob/functional_test_mempool_zigzag_playground/test/functional/mempool_zigzag.py).


    murchandamus commented at 7:55 pm on March 27, 2023:
    Thanks, you are most correct!
  118. [mempool] find connected mempool entries with GatherClusters(…)
    We limit GatherClusters’s result to a maximum of 500 transactions as
    clusters can be made arbitrarily large by third parties.
    
    Co-authored-by: Murch <murch@murch.one>
    56484f0fdc
  119. murchandamus commented at 9:37 pm on March 27, 2023: contributor

    Addressed feedback of Larry, Furszy, and theStack

    • Removed unnecessary curly braces, unimplemented method header, unnecessary variables in test and code • Improved explanation around tx5+tx6 in tests • Removed unnecessary special casing in GatherClusters

  120. murchandamus force-pushed on Mar 27, 2023
  121. murchandamus commented at 11:05 pm on March 27, 2023: contributor

    Left few more comments.

    Plus, while was checking the 1p1c test, couldn’t resist myself and made it more friendly furszy@5dc4b89. Feel free to take it if you like it.

    Sorry, I was just going through the commits one by one and only rediscovered this suggestion this evening. It looks like there is some good stuff there. I’ll aim to incorporate it shortly, but it might not be tonight.

  122. in src/txmempool.cpp:1166 in fa8432aeec outdated
    1161+    // Use epoch: visiting an entry means we have added it to the clustered_txs vector. It does not
    1162+    // necessarily mean the entry has been processed.
    1163+    WITH_FRESH_EPOCH(m_epoch);
    1164+    for (const auto& it : clustered_txs) {
    1165+        visited(it);
    1166+    }
    


    LarryRuane commented at 6:21 pm on March 28, 2023:
    Just a note to other reviews who also think this looks weird: it is a const reference being passed to visited() so you’d think it (or what it points to) can’t be modified, so seems like visited() must have no effect. Yet we’re ignoring its return value. The answer is that visited() does modify it->m_epoch_marker but that member is mutable. To me, it seems like this shouldn’t be marked mutable because it does change the state of *it in a way that affects behavior, not just caching or locking (the usual use cases for mutable). Anyway, nothing wrong with the PR, just wanted to mention it in case others were confused as well.
  123. in src/node/mini_miner.h:59 in fa8432aeec outdated
    54+ * mempool transactions, ignoring consensus rules, to calculate mining scores. */
    55+class MiniMiner
    56+{
    57+    // When true, a caller may use CalculateBumpFees(). Becomes false if we failed to retrieve
    58+    // mempool entries (i.e. cluster size too large) or bump fees have already been calculated.
    59+    bool m_ready_to_calculate{true};
    


    LarryRuane commented at 7:22 pm on March 28, 2023:

    This comment is for a possible follow-up PR, not suggesting any change here, just wanted to document this thought.

    As an alternative to this flag, it might be more natural to use “chained methods” so you could write something like:

    0std::map<COutPoint, CAmount> node::MiniMiner(pool, outpoints)
    1        .BuildMockTemplate(target_feerate)
    2        .CalculateBumpFees();
    

    (This technique is used here for example, and is common in more modern languages like Rust).

    BuildMockTemplate() would return *this instead of void.

    Of course, CalculateBumpFees() and CalculateTotalBumpFees() would not call BuildMockTemplate() as they currently do. We’d also need BuildMockTemplate() to save the feerate in the object for either of the calculate functions to us; we don’t want the caller to have to specify the same value twice. The feerate should probably be accessible using a getter.

    A nice property of this approach is that for testing, the results of each “stage” could be instantiated into variables, and inspection methods or SanityCheck() could be called on them.

    It should then be possible to make the two calculate methods const, which is intuitive – calculating from an object shouldn’t need to mutate it.

    One other more subtle thing we’d want to do is handle the case where BuildMockTemplate() is called more than once – it would be nice to allow that even if initially only for testing. That is, the caller might do something like:

    0node::MiniMiner miner(pool, outpoints);
    1miner.BuildMockTemplate(feerate1);
    2miner.BuildMockTemplate(feerate2);
    3results = miner.CalculateBumpFees();
    

    The effect you’d expect is for the bump fees to be based on feerate2. But the first call to BuildMockTemplate() would modify the object in such a way that, if nothing special is done, would mess up the second call to BuildMockTemplate().

    I think the best way to deal with this is that when BuildMockTemplate() begins, it checks if there’s already a feerate set in the object (maybe m_feerate is type std::optional<CFeeRate>). If so, it resets of the object’s state to as it was after the constructor ran. (It shouldn’t need to actually re-run the constructor code; that may be a possible design but seems less elegant.)

    One last thing, what would this do? (Note, BuildMockTemplate() isn’t called)

    0results = node::MiniMiner(pool, outpoints).CalculateBumpFees();
    

    I think what would be natural here is that all the bump fees would be zero, as if the target feerate is zero. In other words, the “default” target feerate is zero; BuildMockTemplate() simply modifies the feerate from zero.

    Zero bump fees is also what can happen if we hit the cluster-too-large limit. We wouldn’t bump any fees, but that’s no worse than today. (I think this is what happens with the PR?)

  124. LarryRuane commented at 5:17 am on March 29, 2023: contributor
    ACK fa8432aeeca39641da6e9bbb9fbf1c52ec5efa72 I code-reviewed pretty carefully, the unit tests pass, but I didn’t study the unit or fuzz tests in detail, I’ll continue with that (but this PR can merge as is). I also ran both fuzzers on 16 cores each for 8 hours, and had no failures.
  125. DrahtBot requested review from achow101 on Mar 29, 2023
  126. in src/node/mini_miner.cpp:61 in fa8432aeec outdated
    56+
    57+    // No unconfirmed UTXOs, so nothing mempool-related needs to be calculated.
    58+    if (m_requested_outpoints_by_txid.empty()) return;
    59+
    60+    // Calculate the cluster and construct the entry map.
    61+    std::vector<uint256> txids_needed;
    


    glozow commented at 11:46 am on March 30, 2023:

    https://cirrus-ci.com/task/4526522288046080:

    0/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/node/mini_miner.cpp:63:9: error: 'push_back' is called inside a loop; consider pre-allocating the container capacity before the loop [performance-inefficient-vector-operation,-warnings-as-errors]
    1        txids_needed.push_back(txid);
    

    seems like the tidy job wants you to add this:

    0    std::vector<uint256> txids_needed;
    1    txids_needed.reserve(m_requested_outpoints_by_txid.size());
    
  127. Implement Mini version of BlockAssembler to calculate mining scores
    Rewrite the same algo instead of reusing BlockAssembler because we have
    a few extra requirements that would make the changes invasive and
    difficult to review:
    
    - Only operate on the relevant transactions rather than full mempool
    - Remove transactions that will be replaced so they can't bump their ancestors
    - Don't hold mempool lock outside of the constructor
    - Skip things like max block weight and IsFinalTx
    - Additionally calculate fees to bump remaining ancestor packages to target feerate
    
    Co-authored-by: Murch <murch@murch.one>
    59afcc8354
  128. murchandamus force-pushed on Mar 30, 2023
  129. murchandamus commented at 9:26 pm on March 30, 2023: contributor

    Pushed the change to make tidy happy. @furszy: I put my take on your suggested changes in https://github.com/Xekyo/bitcoin/commits/furszy-minmintests, but I haven’t been able to bring myself to merge it yet, because I was hoping to keep the changes small with the feature freeze on Saturday. Haven’t given up the hope completely yet. (^_^)/ If I have to touch it up a bit more, I’m thinking to do it, but otherwise maybe in a follow-up?


    Edit: Ah whatever, #27021 doesn’t do much without #26152 anyway, so I’ve pushed the changes inspired by furszy’s refactor of the miniminer-tests as well, since I just touched the file to fix the tidy check anyway.

    So relevant changes are therefore: https://github.com/bitcoin/bitcoin/compare/fa8432aeeca39641da6e9bbb9fbf1c52ec5efa72..b6e4dafa8de15d97927c4d807091c82b0557c104

  130. murchandamus force-pushed on Mar 30, 2023
  131. glozow commented at 10:47 am on April 5, 2023: member

    Edit: Ah whatever, #27021 doesn’t do much without #26152 anyway

    Seeing as this has missed the feature freeze date, I’m removing both from 25.0 milestone (sorry :cry: )

  132. glozow removed this from the milestone 25.0 on Apr 5, 2023
  133. murchandamus force-pushed on Apr 6, 2023
  134. murchandamus commented at 7:09 pm on April 6, 2023: contributor
    Fixed co-authorship attribution to @furszy, no other changes.
  135. [unit test] GatherClusters and MiniMiner unit tests
    Co-authored-by: Murch <murch@murch.one>
    Co-authored-by: theStack <sebastian.falbesoner@gmail.com>
    Co-authored-by: furszy <matiasfurszyfer@protonmail.com>
    3f3f2d59ea
  136. [fuzz] Add MiniMiner target + diff fuzz against BlockAssembler
    Co-authored-by: dergoegge <n.goeggi@gmail.com>
    Co-authored-by: mzumsande <mzumsande@gmail.com>
    Co-authored-by: Murch <murch@murch.one>
    6b605b91c1
  137. murchandamus force-pushed on Apr 6, 2023
  138. achow101 commented at 6:27 pm on May 3, 2023: member
    ACK 6b605b91c1faf2c7f7cc0c9d39b4fcfd66dc2965
  139. DrahtBot removed review request from achow101 on May 3, 2023
  140. DrahtBot requested review from LarryRuane on May 3, 2023
  141. glozow requested review from theStack on May 8, 2023
  142. glozow requested review from dergoegge on May 8, 2023
  143. glozow requested review from furszy on May 8, 2023
  144. furszy approved
  145. furszy commented at 3:24 pm on May 8, 2023: member

    ACK 6b605b91 modulo miniminer_overlap test.

    Not really blocking, I’m planning to go deeper later. And probably add some explanatory comments and code simplifications. I think that has a readability barrier that will be a maintenance issue moving forward.

  146. DrahtBot removed review request from LarryRuane on May 8, 2023
  147. DrahtBot requested review from LarryRuane on May 8, 2023
  148. DrahtBot removed review request from LarryRuane on May 8, 2023
  149. DrahtBot requested review from LarryRuane on May 8, 2023
  150. in src/node/mini_miner.cpp:12 in 59afcc8354 outdated
     7+#include <consensus/amount.h>
     8+#include <policy/feerate.h>
     9+#include <primitives/transaction.h>
    10+#include <timedata.h>
    11+#include <util/check.h>
    12+#include <util/moneystr.h>
    


    theStack commented at 4:20 pm on May 9, 2023:

    nit: unused includes

    0#include <util/check.h>
    

    murchandamus commented at 8:19 pm on June 9, 2023:
    I am removing the unused includes.
  151. in src/node/mini_miner.cpp:174 in 59afcc8354 outdated
    169+        // Each entry’s descendant set includes itself
    170+        Assume(it != m_descendant_set_by_txid.end());
    171+        for (auto& descendant : it->second) {
    172+            // If these fail, we must be double-deducting.
    173+            Assume(descendant->second.GetModFeesWithAncestors() >= anc->second.GetModifiedFee());
    174+            Assume(descendant->second.vsize_with_ancestors >= anc->second.GetTxSize());
    


    theStack commented at 4:37 pm on May 9, 2023:
    nit: seems odd to sometimes access MiniMinerMempoolEntry entrie’s ancestor-set information via method (.GetModFeesWithAncestors(...)), and sometimes directly by member variable (.vsize_with_ancestors). Would suggest to be consistent here and either move the {fee,vsize}_with_ancestors fields to the private: section (i.e. the getter methods have to be always used) or remove the methods completely and hence always use field access.

    murchandamus commented at 7:36 pm on June 12, 2023:
    Addressed in #26152 by introducing a method to update the Ancestor set state.
  152. in src/test/miniminer_tests.cpp:334 in 3f3f2d59ea outdated
    329+    // tx4's feerate is lower than tx3's. same fee, different weight.
    330+    BOOST_CHECK(tx3_feerate > tx4_feerate);
    331+    const auto tx4_anc_feerate = CFeeRate(low_fee + med_fee + high_fee, tx_vsizes[0] + tx_vsizes[1] + tx_vsizes[3]);
    332+    const auto tx5_feerate = CFeeRate(high_fee, tx_vsizes[4]);
    333+    const auto tx7_anc_feerate = CFeeRate(low_fee + med_fee, tx_vsizes[5] + tx_vsizes[6]);
    334+    const auto tx8_anc_feerate = CFeeRate(low_fee + high_fee, tx_vsizes[5] + tx_vsizes[7]);
    


    theStack commented at 4:53 pm on May 9, 2023:

    nit, follow-up material: I think the {tx5,tx7,tx8}_anc_feerates are all off here as they forget to account for their own tx’s vsize/fee. Probably it would even make sense to check against the fee-rate calculated with the “real” values gathered from CTxMemPool with some checks like this:

    0-    const auto tx4_anc_feerate = CFeeRate(low_fee + med_fee + high_fee, tx_vsizes[0] + tx_vsizes[1] + tx_vsizes[3]);
    1+    const auto tx4_anc_feerate = CFeeRate(low_fee + med_fee + high_fee + high_fee, tx_vsizes[0] + tx_vsizes[1] + tx_vsizes[2] + tx_vsizes[3]);
    2+    const auto tx4_iter = pool.GetIter(tx4->GetHash());
    3+    BOOST_CHECK(tx4_anc_feerate == CFeeRate(tx4_iter.value()->GetModFeesWithAncestors(), tx4_iter.value()->GetSizeWithAncestors()));
    

    murchandamus commented at 8:19 pm on June 9, 2023:
    I think that is a misunderstanding caused by the vector fields being number 0–7 and the txs being numbered 1–8. I’ve got a draft where I change the names of the transactions to start with number 0.

    murchandamus commented at 8:13 pm on June 12, 2023:
    Oh, I get what you mean. You’re right, the ancestor set feerates were incorrectly excluding some of the high_fee transactions. I amended the calculations and added the proposed additional checks. Thanks for catching that!
  153. in src/test/miniminer_tests.cpp:327 in 3f3f2d59ea outdated
    322+        COutPoint{tx7->GetHash(), 0},
    323+        COutPoint{tx8->GetHash(), 0}
    324+    });
    325+    for (const auto& outpoint : all_unspent_outpoints) BOOST_CHECK(!pool.isSpent(outpoint));
    326+
    327+    const auto tx3_feerate = CFeeRate(high_fee, tx_vsizes[2]);
    


    theStack commented at 5:40 pm on May 9, 2023:
    For better readability and maintainability, would be nice to start naming the txs with index zero, to avoid the off-by-one relation (txN <-> tx_vsizes[N-1]).

    murchandamus commented at 8:19 pm on June 9, 2023:
    Great idea, will do.

    murchandamus commented at 7:38 pm on June 12, 2023:
    Implemented in #26152
  154. theStack commented at 5:41 pm on May 9, 2023: contributor

    Looks good to me overall, planning to do another review round within the next days.

    For the miniminer_overlap test, I crafted some diagram and (ancestor) fee-rate calculation notes to get a better picture what’s going on there in the mempool; will just dump it here, maybe it helps other reviewers or it even makes sense to include the diagram in a follow-up.

     0Tx graph for `miniminer_overlap` unit test:
     1
     2   coinbase_tx [mined]        ... block-chain
     3-------------------------------------------------
     4    /   |   \          \      ... mempool
     5   /    |    \         |
     6 tx1   tx2   tx3      tx5
     7[low] [med] [high]   [high]
     8   \    |    /         |
     9    \   |   /         tx6
    10     \  |  /         [low]
    11       tx4          /     \
    12      [high]       tx7    tx8
    13                  [med]  [high]
    14
    15NOTE:
    16-> "low"/"med"/"high" denote the _absolute_ fee of each tx
    17-> tx4 has 3 unspent ouputs, all other txs have 1 unspent output
    18-> tx4's fee-rate is lower than tx3's, as tx4 has more weight (due to having more outputs)
    19
    20-> tx3_FR = high / tx3_vsize
    21-> tx4_FR = high / tx4_vsize
    22-> tx4_ASFR = (low+med+high+high) / (tx1_vsize + tx2_vsize + tx3_vsize + tx4_vsize)
    23-> tx5_FR = high / tx5_vsize
    24-> tx7_ASFR = (high+low+med) / (tx5_vsize + tx6_vsize + tx7_vsize)
    25-> tx8_ASFR = (high+low+high) / (tx5_vsize + tx6_vsize + tx8_vsize)
    

    Also left some nits below.

  155. DrahtBot removed review request from LarryRuane on May 9, 2023
  156. DrahtBot requested review from LarryRuane on May 9, 2023
  157. DrahtBot removed review request from LarryRuane on May 9, 2023
  158. DrahtBot requested review from LarryRuane on May 9, 2023
  159. theStack approved
  160. theStack commented at 3:02 pm on May 16, 2023: contributor
    Code-review ACK 6b605b91c1faf2c7f7cc0c9d39b4fcfd66dc2965
  161. DrahtBot removed review request from LarryRuane on May 16, 2023
  162. DrahtBot requested review from LarryRuane on May 16, 2023
  163. murchandamus commented at 11:42 pm on May 16, 2023: contributor

    Super, thanks for the review, @theStack. As I already have a follow-up PR with #26152, since this PR has three ACKs now, and all the open comments are nits, I would like to include those changes as a new commit in the follow-up #26152.

    What do you think, @glozow?

  164. DrahtBot removed review request from LarryRuane on May 16, 2023
  165. DrahtBot requested review from LarryRuane on May 16, 2023
  166. DrahtBot removed review request from LarryRuane on May 17, 2023
  167. DrahtBot requested review from LarryRuane on May 17, 2023
  168. murchandamus commented at 2:26 am on May 17, 2023: contributor

    ACK 6b605b9 modulo miniminer_overlap test.

    Not really blocking, I’m planning to go deeper later. And probably add some explanatory comments and code simplifications. I think that has a readability barrier that will be a maintenance issue moving forward.

    Perhaps we can address that in #26152 as well

  169. DrahtBot removed review request from LarryRuane on May 17, 2023
  170. DrahtBot requested review from LarryRuane on May 17, 2023
  171. fanquake assigned glozow on May 17, 2023
  172. furszy commented at 1:10 pm on May 17, 2023: member

    ACK 6b605b9 modulo miniminer_overlap test. Not really blocking, I’m planning to go deeper later. And probably add some explanatory comments and code simplifications. I think that has a readability barrier that will be a maintenance issue moving forward.

    Perhaps we can address that in #26152 as well

    Absolutely. Loved @theStack diagram.

  173. DrahtBot removed review request from LarryRuane on May 17, 2023
  174. DrahtBot requested review from LarryRuane on May 17, 2023
  175. glozow merged this on May 19, 2023
  176. glozow closed this on May 19, 2023

  177. glozow commented at 2:28 pm on May 19, 2023: member

    As I already have a follow-up PR with #26152, since this PR has three ACKs now, and all the open comments are nits, I would like to include those changes as a new commit in the follow-up #26152.

    Yep, I’ll look for these in #26152: #27021 (review) #27021 (review) #27021 (review) #27021 (review) #27021#pullrequestreview-1417018318

  178. sidhujag referenced this in commit dbb3e9a78b on May 19, 2023
  179. sidhujag referenced this in commit 0f6d450b2b on May 19, 2023
  180. maflcko commented at 11:10 am on May 30, 2023: member
  181. murchandamus commented at 8:14 pm on June 12, 2023: contributor
    I think that all follow-ups from #27021 have now been addressed in #26152.
  182. murchandamus referenced this in commit 9f0965f656 on Jun 12, 2023
  183. murchandamus referenced this in commit d207f0c956 on Jun 12, 2023
  184. murchandamus referenced this in commit d2fe456fd2 on Jun 12, 2023
  185. murchandamus referenced this in commit 9daf105bf5 on Jun 12, 2023
  186. murchandamus deleted the branch on Jun 13, 2023
  187. murchandamus referenced this in commit 0c4ff49210 on Jul 3, 2023
  188. murchandamus referenced this in commit 3016245bab on Jul 3, 2023
  189. murchandamus referenced this in commit b49a193005 on Jul 3, 2023
  190. murchandamus referenced this in commit a3b178f3c0 on Jul 3, 2023
  191. murchandamus referenced this in commit db9b480c76 on Aug 11, 2023
  192. murchandamus referenced this in commit 803bb8bd8f on Aug 11, 2023
  193. murchandamus referenced this in commit 8e59d5c990 on Aug 11, 2023
  194. murchandamus referenced this in commit 8711ab7fd7 on Aug 11, 2023
  195. murchandamus referenced this in commit 63baf6f8e3 on Aug 12, 2023
  196. murchandamus referenced this in commit 7aad9f8067 on Aug 12, 2023
  197. murchandamus referenced this in commit 5f4b6ab5cf on Aug 12, 2023
  198. murchandamus referenced this in commit 2f3e8ded03 on Aug 12, 2023
  199. murchandamus referenced this in commit 0d17f47a47 on Aug 17, 2023
  200. murchandamus referenced this in commit d2deb63e31 on Aug 17, 2023
  201. murchandamus referenced this in commit f57b64bb1e on Aug 17, 2023
  202. murchandamus referenced this in commit 22466132c4 on Aug 17, 2023
  203. murchandamus referenced this in commit 9b76e5a2fa on Aug 18, 2023
  204. murchandamus referenced this in commit 3742bf72ce on Aug 18, 2023
  205. murchandamus referenced this in commit f11f089410 on Aug 18, 2023
  206. murchandamus referenced this in commit 447644234f on Aug 18, 2023
  207. murchandamus referenced this in commit 1b925380d9 on Aug 29, 2023
  208. murchandamus referenced this in commit 1809b37de1 on Aug 29, 2023
  209. murchandamus referenced this in commit d79d62e42a on Aug 29, 2023
  210. murchandamus referenced this in commit 49a8595ef1 on Aug 29, 2023
  211. murchandamus referenced this in commit 1eb4ed3c69 on Aug 30, 2023
  212. murchandamus referenced this in commit 8ca1523162 on Aug 30, 2023
  213. murchandamus referenced this in commit 797b259185 on Aug 30, 2023
  214. murchandamus referenced this in commit 29704e5601 on Aug 30, 2023
  215. murchandamus referenced this in commit a1f7d986e0 on Sep 13, 2023
  216. murchandamus referenced this in commit d2f90c31ef on Sep 13, 2023
  217. murchandamus referenced this in commit ac6030e4d8 on Sep 13, 2023
  218. murchandamus referenced this in commit c24851be94 on Sep 13, 2023
  219. achow101 referenced this in commit 459272d639 on Sep 14, 2023
  220. Retropex referenced this in commit c719053682 on Oct 4, 2023
  221. Retropex referenced this in commit cc4077a184 on Oct 4, 2023
  222. Retropex referenced this in commit 221c4f871c on Oct 4, 2023
  223. Retropex referenced this in commit 602dac8dc6 on Oct 4, 2023
  224. bitcoin locked this on Jun 12, 2024

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-11-23 09:12 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me