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.