# UNDF: UNDF-2026-000000357
# bitcoin-0001: MiniMiner DeleteAncestorPackage O(A×E) std::find in Outer Loop

## Classification
- **CWE**: CWE-407 (Inefficient Algorithmic Complexity)
- **Severity**: MEDIUM
- **Component**: Bitcoin Core wallet / bump-fee calculation
- **Location**: `src/node/mini_miner.cpp`, `MiniMiner::DeleteAncestorPackage()`, ~line 218

## Description

`MiniMiner::BuildMockTemplate()` repeatedly calls `DeleteAncestorPackage()` in a
`while (!m_entries_by_txid.empty())` loop to simulate mining transactions in
ancestor-feerate order. Inside `DeleteAncestorPackage()`, for each ancestor `anc`
in the ancestor set, the code does a linear `std::find` scan over `m_entries`
(a `std::vector<MockEntryMap::iterator>`) to find and erase the entry.

Complexity breakdown:
- Outer `while` loop: O(T/A) iterations where T = total transactions, A = avg ancestors
- Per `DeleteAncestorPackage` call: O(A) ancestors × O(E) for `std::find` where E = entries remaining
- Total: O(T × E_avg) ≈ O(T²) in worst case (single-tx ancestor packages)

`m_entries_by_txid` (a `std::map<Txid, MiniMinerMempoolEntry>`) already exists
and provides O(log T) lookup by txid, but is not used to locate entries in the
`m_entries` vector.

This path is exercised every time a wallet user calls `BumpFee` or `PSBT`
operations that need to estimate ancestor fees for a potentially large in-mempool
cluster.

## Defective Code

```cpp
// src/node/mini_miner.cpp ~line 218
// Delete these entries.
for (const auto& anc : ancestors) {                         // O(A) loop
    m_descendant_set_by_txid.erase(anc->first);
    // ...
    auto vec_it = std::find(m_entries.begin(), m_entries.end(), anc);  // O(E) scan
    Assume(vec_it != m_entries.end());
    m_entries.erase(vec_it);                                // O(E) shift
    m_entries_by_txid.erase(anc);
}
```

Called from `BuildMockTemplate()` inside:
```cpp
while (!m_entries_by_txid.empty()) {          // O(T) outer while
    // ... ancestor calculation ...
    DeleteAncestorPackage(ancestors);         // O(A × E) per call
}
```

## Fix

Replace `m_entries` (a `std::vector` used for sorting + random-access deletion)
with a combination: keep the vector for sorting, but maintain a parallel
`std::unordered_set` (or `std::unordered_map<Txid, size_t>`) of iterator
positions to enable O(1) lookup during deletion.

Simplest correct fix — index `m_entries` by txid pointer:

```cpp
// Add to MiniMiner private members (mini_miner.h):
// std::unordered_map<Txid, std::vector<MockEntryMap::iterator>::iterator,
//                    SaltedTxidHasher> m_entries_index;

// Build index when entries are added (in the constructor):
for (auto it = m_entries.begin(); it != m_entries.end(); ++it) {
    m_entries_index.emplace((*it)->first, it);
}

// In DeleteAncestorPackage, replace std::find:
for (const auto& anc : ancestors) {
    m_descendant_set_by_txid.erase(anc->first);
    auto idx_it = m_entries_index.find(anc->first);     // O(1)
    Assume(idx_it != m_entries_index.end());
    m_entries.erase(idx_it->second);                    // O(E) shift still, but find is O(1)
    m_entries_index.erase(idx_it);
    m_entries_by_txid.erase(anc);
}
```

For a more complete fix, swap-and-pop to also eliminate the O(E) erase shift:

```cpp
// Swap-and-pop: O(1) removal from unsorted vector
auto idx_it = m_entries_index.find(anc->first);
auto vec_pos = idx_it->second;
// Update index for the entry that will be moved to vec_pos
if (*vec_pos != m_entries.back()) {
    m_entries_index[m_entries.back()->first] = vec_pos;
}
std::iter_swap(vec_pos, m_entries.end() - 1);
m_entries.pop_back();
m_entries_index.erase(idx_it);
```

Note: if swap-and-pop is used, the sort at the top of `BuildMockTemplate`'s
while loop already re-sorts on each iteration, so ordering is not a concern.

## Complexity

| Operation | Before | After (find only) | After (swap+pop) |
|-----------|--------|-------------------|-----------------|
| Find entry in vector | O(E) | O(1) | O(1) |
| Delete from vector | O(E) | O(E) shift | O(1) |
| Per DeleteAncestorPackage | O(A × E) | O(A × E) erase | O(A) |
| Full BuildMockTemplate | O(T²) | O(T² / A) | O(T log T) |

## Speedup Estimate

At T=1000 single-parent transactions (realistic for a congested mempool with
fee bumping):
- Before: ~500,000 comparisons in std::find (triangular sum)
- After (find only): ~1,000 index lookups
- Ratio: ~500x

At T=200:
- Before: ~20,000 comparisons
- After: ~200 lookups
- Ratio: ~100x
