Transaction fees serve two purposes. They pay for the marginal cost of verifying, propagating and storing the transaction, and they pay for the amortized cost of hashing to secure it and all the other transactions. In this post I will focus on the latter purpose.

The service of securing the transaction is done by the miner finding the block in which it is included, and by the miners finding the next few blocks. However, what the user pays for this service is collected by the first miner alone. This is both a conceptually perverse incentive structure, and can create real problems in some specific circumstances. Suppose someone makes an important transaction, and pays a hefty fee to make sure it is confirmed by several blocks as quickly as possible. It will be included in a block quickly enough; but suppose after that there is a quiet time with very few fee-paying transactions. Miners could be switching their hardware off or to other tasks, delaying the confirmations, even if the sender was willing to single-handedly sponsor them. (There are workarounds, e.g. sending dummy fee-paying transactions. But the fact that a workaround is necessary suggests something is amiss).

I suggest that instead of the transaction fee going just to the miner including the transaction, it will be distributed among him and all subsequent miners. Most generally, some function f will be chosen, and a total transaction fee of T will pay out T*f(n) to the nth miner (the sum of all f values is 1).

If f is an exponentially decaying function, we are relieved of the need to keep track of payment of all past transactions for every block. Some decay rate r (for example 20%) is chosen. Every transaction included will add its fee to a fee pool. Every block, a portion of r of the current fee pool is given to the miner of the block, and the rest carries over to the next block. So a transaction with fee T will pay out 0.2T to the first miner, 0.16T to the second miner, 0.128T to the third miner, and so on.

This can also work in a continuous way suitable for dynamic block times. A decay rate r is chosen; if the fee pool in a block (after putting in the fees of the included transactions) is P, then after the block the remaining pool will be P*e^(-w*r) where w is the weight of the block, and the rest is the miner's fee. More generally, some function f which integrates to 1 is chosen, and the fee paid to the miner which found a block of weight w after W weight units will be T times the integral from W to W+w of f.

Most users who send transactions are incentivized to keep r as high as possible, so they probably cannot be trusted to choose r themselves. It will either need to be hardcoded, or there should be a properly incentivized dynamic adjustment system.

Can you explain?

They will do it when the transaction fees become significant, which won't be very soon.

The transaction fees have been determined by the time the block header to be hashed is composed. When mining in a pool, in theory the pool doesn't need to disclose this information to the miners. But a fair pool rewards miners based on the current transaction fees at the time they submitted a share, so to be accountable for this they need to include this information in the getwork request, perhaps complete with the relevant Merkle branch. So whoever does the hashing will know at any point what are the current transaction fees.

Fairness in transaction rewards will become more important as the block reward reduces. Enabling something like this now will make miner payments fairer in the future.

I was trying to think how to pay someone for choosing to build on your block using what is currently available.

Including a tx that anyone can redeem doesn't work, that tx can just be put in a later block.

Unless you are meaning something I can't think of, anyone who sees the block that you desire to be built upon can take the tx out and put it in their own block regardless of whether they use your block or not. And they can spend it in the same block in which they include it.

Yes, I totally get the idea of passing some on as incentive to the next miner. I'm only wondering about what implementation is currently possible. I think if this does not require a protocol change it will happen on it's own (maybe in 20+ years).

Actually leaving out high fee tx as a treat for the next miner is super gross.

I expect building on the latest block will continue to be the norm, but for different reason (rollover payments) in the future.

In the future if some blocks offer rollover payments and some do not the ones that do will be built on, not the first ones to hit the network. My guess is that the rollover payment will be half of the fees in the block. If that was the norm then when faced with a choice between building on the previous block and getting half of its fees or re-mining the block, offering nothing (or less than half) in rollover fees and having your block ignored (by everyone who is expecting and already has available a version of that block that offers 50%) you will choose to build on the block.

I'm still not clear on how to accomplish a rollover payment.

Oh, I think I got it now. I was forgetting that fees earned are just like subsidy and was thinking that method could only be used to pass on up to all of the subsidy.

Can you help me see my contradiction in the first part? If miners know they'll be ignored if they don't pay half or more to the next block then if they are offered half they'll never try to remine since they'd have to pay out half anyway.

This doesn't make sense to me. Why would anyone choose the lower value strategy?