Optimal transaction packing

[leijurv]

In the future, when transactions start to compete in blocks, what algorithm(s) will/should miners use to optimally determine what transactions they should include to get maximum transaction fees while keeping the block size below 1MB?

[1714045696]

1714045696

[1714045696]

1714045696

[1714045696]

1714045696

[gmaxwell]

A simple greedy fill in terms of fees per KB (profitablity) does pretty well so long as transactions are small relative to the block-size.

Actually "optimal" selection is NP-HARD.  If you have an effectively infinite number of every kind (profitability) of transaction then you can use dynamic programming to optimally select the transactions. There is an approximation to the optimal solution which works by rounding off the profitability to varying precision in order to create a sub-problem which can be solved in polynomial time, and I believe there is some proof that doing this is optimal to within some factor of the rounding relative to the total profit. ... but really, no one will bother, a dumb greedy solution is almost certainly good enough.

[leijurv]

By a "greedy fill", does that mean that miners will add the transaction which has the most fees per kilobyte, but will still fit in the block?
On average, how much better will the NP-HARD algorithm be? Would it be worth the computation time?

Also, is there an algorithm that can decide what the best thing to do would be when a new transaction arrives (add it to the block and maybe boot some other transactions off, or save for later)? I believe if you used the "greedy algorithm", you would need to just do the whole calculation over. Also, if it's not profitable to add a given transaction to the block now, will it ever become profitable to add it later?The only case I can think of when it would be profitable is when there is just a tiny bit of space left over and this is the only transaction that would fit.

[mustyoshi]

Don't you just line them up in order of fee per kb, then put the largest fee per kb ones in the order they are?

[leijurv]

Don't you just line them up in order of fee per kb, then put the largest fee per kb ones in the order they are?

That's the "greedy algorithm" that gmaxwell mentioned. There's apparently an optimal-er solution that's NP-HARD.

[mustyoshi]

Don't you just line them up in order of fee per kb, then put the largest fee per kb ones in the order they are?

That's the "greedy algorithm" that gmaxwell mentioned. There's apparently an optimal-er solution that's NP-HARD.

Isn't the greedy algorithm the best though? Since you're trying to get the most money out of it?

[leijurv]

Don't you just line them up in order of fee per kb, then put the largest fee per kb ones in the order they are?

That's the "greedy algorithm" that gmaxwell mentioned. There's apparently an optimal-er solution that's NP-HARD.

Isn't the greedy algorithm the best though? Since you're trying to get the most money out of it?

Apparently not, according to gmaxwell:

A simple greedy fill in terms of fees per KB (profitablity) does pretty well so long as transactions are small relative to the block-size.

Actually "optimal" selection is NP-HARD.  If you have an effectively infinite number of every kind (profitability) of transaction then you can use dynamic programming to optimally select the transactions. There is an approximation to the optimal solution which works by rounding off the profitability to varying precision in order to create a sub-problem which can be solved in polynomial time, and I believe there is some proof that doing this is optimal to within some factor of the rounding relative to the total profit. ... but really, no one will bother, a dumb greedy solution is almost certainly good enough.

I also thought that greedy would be best, but it makes sense that there is a better possibility sometimes.

[gmaxwell]

Isn't the greedy algorithm the best though? Since you're trying to get the most money out of it?

No.

Say you can fit either  transaction {A}  or {B and C}.  A has sightly higher fees per byte than B or C, but it's smaller than the two combined but big enough that you can't fit any more after A.  You would earn more if you mine {B and C} instead of A but the greedy approach picks A.

You might even have a small transaction D available that you could fit with A: {A and D} but if D is lower profit than B and C by enough it won't make up for the preference of A.

But if a single transaction is only a small fraction of the maximum block size then you'd only expect at worse small fraction loss from the greedy approach, because the loss comes from a small portion of the block that you leave unfilled or filled with less profitable transactions.

I could run a bunch of numbers for different solvers using transaction data— but I don't know that the distribution of transaction sizes and fees today really tells us much about the distributions of transaction sizes and fees in the future where there is significant block space competition, so I don't know that that time would be well spent.   Might be a fun science project for someone more interested in it than I am (google something like 'binary knapsack maximization problem').

[mustyoshi]

Isn't the greedy algorithm the best though? Since you're trying to get the most money out of it?

No.

Say you can fit either  transaction {A}  or {B and C}.  A has sightly higher fees per byte than B or C, but it's smaller than the two combined but big enough that you can't fit any more after A.  You would earn more if you mine {B and C} instead of A but the greedy approach picks A.

You might even have a D available that you could fit with a: {A and D} but D is lower profit than B and C and still doesn't make up for the preference of A.

But if a single transaction is only a small fraction of the maximum block size then you'd only expect at worse small fraction loss from the greedy approach.

I could run a bunch of numbers for different solvers using transaction data— but I don't know that the distribution of transaction sizes and fees today really tells us much about the distributions of transaction sizes and fees in the future where there is significant block space competition, so I don't know that that time would be well spent.   Might be a fun science project for someone more interested in it than I am (google something like 'binary knapsack maximization problem').

Ah, I see what you're saying.

[DannyHamilton]

Miners really need to start considering "child pays for parent" when determining the "fees per KB".  It would make it much easier for a receiver to deal with situations where a sender fails to include a sufficient fee.

[TierNolan]

Isn't the greedy algorithm the best though? Since you're trying to get the most money out of it?

Maybe, imagine you have 1 kB of space and 3 transactions

A) 1BTC: 750 bytes (1.3 BTC / kB)
B) 0.6BTX: 500 bytes (1.2 BTC / kB)
C) 0.5BTX: 500 bytes (1.0 BTC / kB)

The greedy algorithm will sort A, B and then C.  It will then add A to the block and have no more space for B.  This gives 1BTC in tx fees.

However, a better solution is to include B and C instead, the block will then be worth 1.1BTC. 

If you have lots of transactions, then solving that requires checking lots of combinations.  However, in practice, if there are lots of small transactions, then you aren't going to lose much anyway.  You might end up with a block having 0.999 MB, when you could have had one at 0.9995 MB and more fees.

[leijurv]

Also, is there an algorithm that can decide what the best thing to do would be when a new transaction arrives (add it to the block and maybe boot some other transactions off, or save for later)? I believe if you used the "greedy algorithm", you would need to just do the whole calculation over. Also, if it's not profitable to add a given transaction to the block now, will it ever become profitable to add it later? The only case I can think of when it would be profitable is when there is just a tiny bit of space left over and this is the only transaction that would fit.

[DannyHamilton]

Also, is there an algorithm that can decide what the best thing to do would be when a new transaction arrives (add it to the block and maybe boot some other transactions off, or save for later)? I believe if you used the "greedy algorithm", you would need to just do the whole calculation over.

If the miner (or pool) keeps a list of unconfirmed transactions sorted by fees-per-byte, and stores the number of bytes along with each entry in the list, then it wouldn't be necessary to recalculate every transaction when a new transaction is received.  They'd just have to calculate the fees-per-byte for the new transaction, and add it to the appropriate place in the sorted list.  Anytime they issue new work, they can just grab the transactions working their way down the list until they reach the block size limit.

Also, if it's not profitable to add a given transaction to the block now, will it ever become profitable to add it later? The only case I can think of when it would be profitable is when there is just a tiny bit of space left over and this is the only transaction that would fit.

If it's not profitable to add a transaction, then it is time to stop mining completely.  The cost to mine a block does not increase with additional transactions, so each transaction increases revenue without increasing cost.

Eventually when the block subsidy gets small and a larger portion of the block reward consists of the transaction fees, miners may configure their rigs to shut down whenever their aren't enough transaction fees to cover the mining costs, and start back up when a few transactions with large fees show up.  Pools will probably have to find ways to keep miners mining during the periods of low fees.

[justusranvier]

The cost to mine a block does not increase with additional transactions, so each transaction increases revenue without increasing cost.

You're not accounting for orphan risk.

[leijurv]

If it's not profitable to add a transaction, then it is time to stop mining completely.

Hmm. What if you already have a ton of transactions which will give you a lot in fees, but takes up the whole block? Then a big transaction with a small fee comes along. It wouldn't be profitable to add it, but you definitely should keep in mining for the reward...
I think you should keep on mining even if a unprofitable transaction comes along.

The cost to mine a block does not increase with additional transactions, so each transaction increases revenue without increasing cost.

Yes, but only if there's extra space leftover in the block.

The cost to mine a block does not increase with additional transactions, so each transaction increases revenue without increasing cost.

You're not accounting for orphan risk.

Orphan risk is fairly constant, and I don't see how it would go up when you add new transactions.

[DannyHamilton]

The cost to mine a block does not increase with additional transactions, so each transaction increases revenue without increasing cost.

You're not accounting for orphan risk.

Given the fact that it is impossible to tell exactly how long it will take you to successfully mine a particular block ahead of time, it's impossible to calculate the cost of adding a transaction to a precision that could be used to compare with not adding that transaction.  As such the cost of the incredibly small increase in orphan risk from a slightly larger block is lost in the much larger cost of the random nature of block timing.  As such, I suppose it would have been more accurate for me to say "The cost to mine a block does not significantly increase with additional transactions, so each transaction increases revenue without noticeably increasing cost."

[justusranvier]

Given the fact that it is impossible to tell exactly how long it will take you to successfully mine a particular block ahead of time, it's impossible to calculate the cost of adding a transaction to a precision that could be used to compare with not adding that transaction.  As such the cost of the incredibly small increase in orphan risk from a slightly larger block is lost in the much larger cost of the random nature of block timing.  As such, I suppose it would have been more accurate for me to say "The cost to mine a block does not significantly increase with additional transactions, so each transaction increases revenue without noticeably increasing cost."

It's not impossible to estimate to a high enough degree of certainty, given enough data. The easiest way to start would be to look at every known example of orphaned blocked and see what relationship, if any, exists between the probability of being orphaned and the size of a block. The effect will probably be small at this scale, but it shouldn't be zero and it will become more significant as blocks increase in size.

[DannyHamilton]

If it's not profitable to add a transaction, then it is time to stop mining completely.

Hmm. What if you already have a ton of transactions which will give you a lot in fees, but takes up the whole block? Then a big transaction with a small fee comes along. It wouldn't be profitable to add it, but you definitely should keep in mining for the reward...

It would only be un-profitable to add it if you removed higher paying transactions in order to fit the new transaction in the block.  Since the question referred to a "greedy fill", it was already assumed that once the block was filled with higher paying blocks, no additional transactions would be added unless they payed a higher fee-per-byte than the transactions that would be removed.  Furthermore, the question was "will it ever become profitable to add it later".  That seemed to imply future blocks that aren't full, not the current full block.

The cost to mine a block does not increase with additional transactions, so each transaction increases revenue without increasing cost.

Yes, but only if there's extra space leftover in the block.

See my previous comment about "greedy fill" and "ever become profitable to add it later".

The cost to mine a block does not increase with additional transactions, so each transaction increases revenue without increasing cost.

You're not accounting for orphan risk.

Orphan risk is constant, and won't go up when you add new transactions.

Many people believe that orphan risk increases ever so slightly with a larger block.  If you solve a block that is 1 MB in size, at the exact same moment that someone else solves a block that is 400 bytes in size (because they included less transactions in their block), then theoretically, their block might propagate through the network faster, and therefore more miners will be building on top of their block instead of yours.  This additional hash power working on their block increases the risk that your block will be orphaned instead of theirs.

This increase in risk is so small, that it doesn't take much in fees to make it profitable to add additional transactions to your block.  I suppose a really large transaction (in terms of bytes) that only paid a 1 satoshi fee *might* reduce profitability due to the increase in orphan rate, but if you a large pool and are well connected it might not.
 

[DannyHamilton]

It's not impossible to estimate to a high enough degree of certainty, given enough data.

Go ahead.  Try it.  I think you'll find it impossible to find the signal in all the noise generated by the randomness of the block solving timing and the variations in network hashing power and difficulty as well as the variation in bandwidth and connectivity that each miner and pool has.

[TierNolan]

It's pretty much:

propagation time = [(block size) / (bandwidth) + (transactions * verification time)] * (hops to miners)

Your orphan probability is (propagation time) / (average block rate).

Adding extra transactions slows things down due to bandwidth and the fact that each node must verify before forwarding.

When transaction fees are significant, mining pools will have to create blocks as fast as possible.  Atm, you could distribute a new coinbase only block immediately, and transmit updated headers as you expand your block.  You still have potential orphan risk though.