Can Miners Really Tackle the Knapsack Problem?

Do miners really use tools like Gurobi to solve the knapsack problem for picking the most profitable transactions? I'm just curious about how honest miners maximize their profits.

Knapsack problem? Never heard of that before. Did some digging and it seems to relate to block sizes. But with Bitcoin, you can't just pick and choose transactions to include while mining, right? Unless you’re a pool with a ton of hashrate.

Not sure how they do it, honestly. Each miner has unique software, and it’s tough to know what’s going on. You can check the usual implementations, but it’s hard to validate since you can’t access the same mempool as the miners.

Interesting point! The 100 kvB limit is there to help miners make this decision. When transactions get too close to the block size, figuring out the best combo of transactions becomes a real headache.

Yep, I bet most pools rely on Bitcoin Core's getblocktemplate function, which is pretty straightforward. It just sorts by fee rates and considers CPFP transactions. You can find more about it on GitHub if you're interested.

Right, but getblocktemplate is just a basic method. Finding the perfect solution is tough since it’s NP-hard. You can’t always know what the best set of transactions is.

Good point about the sigops cost. Miners have to keep that under control too. If they don’t, they could end up with an invalid block, like what happened with F2Pool last year.

I hadn’t heard about that F2Pool incident before, but it makes sense. They’re known for censoring transactions, so if they messed up the code, it’s kind of poetic justice.

Knapsack problem is all about maximizing value. Miners can definitely boost profits by selecting high-fee transactions based on size.

Yeah, but the greedy approach can be hit or miss. The challenge is figuring out which transactions fit into a limited block size. There’s more to it than just picking the highest fees.

Forget sigops for a sec. If we ignore dependencies, a simple greedy method is to sort transactions by fee rate and take the highest ones. If it fills the block just right, you’ve got an optimal solution.

Not every pool operates the same. Some are transparent about their methods, while others are secretive. Unless you remove transactions from your mempool, you can't prep a set beforehand.

I get your point, but wouldn’t running a solver even after getting a solution from getblocktemplate be beneficial? It could find something better while the other one runs.

F2Pool and Ocean pools really stand out. F2Pool's got a political agenda, and Ocean's got their own quirks. Other pools with acceleration services also have some sketchy selections.

I thought it was just MARA doing that. Kinda sad to see others following suit. But yeah, delays in block mining can cause transactions to be missed too.

I’ve been checking mempool health indicators: Kano.is is at 99.92%, while Oceanpool is lagging behind at 87.66%. Not sure how much that tells us, though.

100 blocks of backlog isn’t that big, really. A regular ILP solver can find optimal solutions pretty fast, at least compared to the time needed for new block templates.

Saw that recent merge about the new cluster-based mempool algorithm. Changes are coming!

Yeah, and it’s been looked at by 0xB10C. Wild that F2Pool didn’t update their software after their first invalid block incident. You’d think they’d be more careful.