Block producer transaction inclusion logic is incorrect, can lose money

[enolan]

It computes the budget for a block by taking the sum of the fees for all user commands in the pool and subtracting the sum of the fees for all snark bundles that can be applied in the current block. First, this is wrong because the pool may be bigger than the transaction capacity, second this is wrong because including a transaction may cost the block producer more in snark fees than it gets in transaction fees. A block producer should never pay more in snark fees inclusive of the cost of fee transfers, to include a transaction than it gets in transaction fees. The fee transfers make it a global optimization problem, it might be in NP, I'd have to think about it some more. If finding an optimal solution is intractable then a greedy approximation would probably be adequate (though it must be safe in adversarial scenarios, both computationally and in terms of results).

[enolan]

err, mispoke. It might be NP-hard. Everything is in NP, that's how the hierarchy works.

[imeckler]

To clarify, this is to say our block production algorithm is not optimal in terms of profit-maximization.