[tromp]

Many miners require a minimum fee-per-byte for including a transaction in their memory pool of transactions awaiting inclusion in a block. So they would for instance ignore a transaction of B bytes if its fee is less than B * 100 satoshi (at 10^-8 BTC, the smallest unit of account). Then the miner will often find that its entire memory pool fits inside the 1MB block limit, and the knapsack problem disappears (still leaving the NP-hard conflict resolution problem).

[nullc]

> Then the miner will often find that its entire memory pool fits inside the 1MB block limit, and the knapsack problem disappears

That isn't true except on weekends, at least not for the last two years... there is usually a pretty healthy backlog available: https://people.xiph.org/~greg/temp/fee_avail4.png which is important for long term stability: https://medium.com/@bergealex4/bitcoin-is-unstable-without-t...

> and the knapsack problem disappears

Just cutting off low fee TX is a worse result than even the most approximate knapsack solver you could use. :) (Take transactions in order of fee per unit-limit, skip ones that won't fit, until you're full or you've skipped too many times sequentially-- which is what we do... with a too many threshold of a few thousand IIRC)

The reason for the floor is primarily to avoid wasting resources trying to verify transactions which are never going to confirm.

The floor rate used in the network today is 1e-8 BTC per byte, though it automatically goes up if the backlog of transactions gets large (over about 150MB of transactions). That limiting works by nodes keeping 150MB of transactions and if they gain more they drop the lowest feerate transaction and set their minimum to that value. The minimum then decays back to 1e-8 BTC/byte at a speed which depends on how much below the limit the node is...

[ these parameters don't need to be completely consistent in the network, nodes will tell their peers what fee levels they're willing to process]

> NP-hard conflict resolution problem

That is ignored in Bitcoin implementations today because double spends are rare, interesting ones are extra rare with complex dependency graphs, and there is a social good to behaving in simple an explicable ways.

[Retric]

Considering how centralized Bitcoin has become minors are incentivized to raise the threshold for inclusion in a block even if they make less per block in the short term artificial scarcity can become extremely valuable in the mid term.

[TD-Linux]

The conflict resolution problem was traditionally solved just by taking the first seen valid transaction and disregarding any subsequent conflicting transactions. That of course is not necessarily profit maximizing, so current implementations generally allow replacing the transaction as long as it pays an incrementally higher fee than the one it's replacing (the increment usually being the same as the minimum fee you mentioned).

Non-mining nodes have to implement a similar policy, as it's also used for preventing DoS on the P2P network.