Repository: bitcoin/bitcoin (language: cpp)

Issue:
fuzz: mini_miner_selection: ASSERT: mock_template_txids.size() <= blocktemplate->block.vtx.size()
https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=69957

https://github.com/bitcoin/bitcoin/blob/2f6dca4d1c01ee47275a4292f128d714736837a1/src/test/fuzz/mini_miner.cpp#L192


Discussion / hints:

```
$ echo 'AyABAAAAACAg/wAAAAAA/yD/AQAAAAAg/yCu/w==' | base64 --decode > /tmp/oss-fuzz-crash 
$ FUZZ=mini_miner_selection ./src/test/fuzz/fuzz /tmp/oss-fuzz-crash

cc @glozow @murchandamus (in case you missed it) would be nice to have this fixed and also have an explanation of the actual bug, since it is somewhat of a mystery why it's so hard to find
Ooh fun, this found a difference between `MiniMiner` and `CTxMemPool`'s comparators , which boils down to a lack of precision in `CFeeRate`.

Debugging, the 3 entries in mempool are

A <- B <- C
A: 1sat/264vB
B: 0sat/178vB
C:1sat/178vB

The minimum feerate, i.e. `target_feerate` or `blockMinFeeRate` is 1sat/vB.

`BlockAssembler` selects A. `MiniMiner` selects ABC. They are both wrong to do so, since all transactions have a feerate below 1sat/vB. This is because `CFeeRate` rounds `minfeerate.GetFee(packagesize)` up to 1sat, and the `if` condition succeeds. But this isn't the bug that was hit by the fuzzer.

The actual bug is in the comparators:
`CompareTxMemPoolentryByAncestorFee` in `CTxMemPool` casts everything to `double`s and doesn't compare using `CFeeRate` objects. It can see that A's feerate is 1/264=0.0038sat/vB, while C's ancestor feerate is 2/260=0.0032sat/vB, and orders A before C.

`CFeeRate` only stores satoshis per KvB, so `CFeerate(1, 264)` and `CFeeRate(2, 260)` both become `CFeerate(nSatoshisPerK=3)`, i.e. 0.003sat/vB.

The `AncestorFeerateComparator` in  `MiniMiner` compares `CFeeRate`s and basically sees that 3 == 3, tiebreaks using txid, and selects package ABC first. You can observe that the fuzz input in this issue succeeds if you multiply all fees by 10 before passing them to the `CFeeRate` constructors in `AncestorFeerateComparator` (then it's comparing 32 and 38).
I can open a PR to change `MiniMiner` to store/compare `FeeFrac`s, which by itself would fix the imprecision bug, though I'm not sure if that'll make it identical to txmempool.

Changing txmempool seems less important imo since there is no current imprecision bug, and perhaps cluster mempool plans to do this anyway.

Fix patch:
diff --git a/src/node/mini_miner.cpp b/src/node/mini_miner.cpp
index 58422c4439482..d7d15554b3254 100644
--- a/src/node/mini_miner.cpp
+++ b/src/node/mini_miner.cpp
@@ -174,7 +174,7 @@ MiniMiner::MiniMiner(const std::vector<MiniMinerMempoolEntry>& manual_entries,
     SanityCheck();
 }
 
-// Compare by min(ancestor feerate, individual feerate), then iterator
+// Compare by min(ancestor feerate, individual feerate), then txid
 //
 // Under the ancestor-based mining approach, high-feerate children can pay for parents, but high-feerate
 // parents do not incentive inclusion of their children. Therefore the mining algorithm only considers
@@ -183,21 +183,13 @@ struct AncestorFeerateComparator
 {
     template<typename I>
     bool operator()(const I& a, const I& b) const {
-        auto min_feerate = [](const MiniMinerMempoolEntry& e) -> CFeeRate {
-            const CAmount ancestor_fee{e.GetModFeesWithAncestors()};
-            const int64_t ancestor_size{e.GetSizeWithAncestors()};
-            const CAmount tx_fee{e.GetModifiedFee()};
-            const int64_t tx_size{e.GetTxSize()};
-            // Comparing ancestor feerate with individual feerate:
-            //     ancestor_fee / ancestor_size <= tx_fee / tx_size
-            // Avoid division and possible loss of precision by
-            // multiplying both sides by the sizes:
-            return ancestor_fee * tx_size < tx_fee * ancestor_size ?
-                       CFeeRate(ancestor_fee, ancestor_size) :
-                       CFeeRate(tx_fee, tx_size);
+        auto min_feerate = [](const MiniMinerMempoolEntry& e) -> FeeFrac {
+            FeeFrac self_feerate(e.GetModifiedFee(), e.GetTxSize());
+            FeeFrac ancestor_feerate(e.GetModFeesWithAncestors(), e.GetSizeWithAncestors());
+            return std::min(ancestor_feerate, self_feerate);
         };
-        CFeeRate a_feerate{min_feerate(a->second)};
-        CFeeRate b_feerate{min_feerate(b->second)};
+        FeeFrac a_feerate{min_feerate(a->second)};
+        FeeFrac b_feerate{min_feerate(b->second)};
         if (a_feerate != b_feerate) {
             return a_feerate > b_feerate;
         }


Test patch:
diff --git a/src/test/fuzz/mini_miner.cpp b/src/test/fuzz/mini_miner.cpp
index 3a1663364fd03..51de4d0166df6 100644
--- a/src/test/fuzz/mini_miner.cpp
+++ b/src/test/fuzz/mini_miner.cpp
@@ -188,9 +188,9 @@ FUZZ_TARGET(mini_miner_selection, .init = initialize_miner)
     auto mock_template_txids = mini_miner.GetMockTemplateTxids();
     // MiniMiner doesn't add a coinbase tx.
     assert(mock_template_txids.count(blocktemplate->block.vtx[0]->GetHash()) == 0);
-    mock_template_txids.emplace(blocktemplate->block.vtx[0]->GetHash());
-    assert(mock_template_txids.size() <= blocktemplate->block.vtx.size());
-    assert(mock_template_txids.size() >= blocktemplate->block.vtx.size());
+    auto [iter, new_entry] = mock_template_txids.emplace(blocktemplate->block.vtx[0]->GetHash());
+    assert(new_entry);
+
     assert(mock_template_txids.size() == blocktemplate->block.vtx.size());
     for (const auto& tx : blocktemplate->block.vtx) {
         assert(mock_template_txids.count(tx->GetHash()));