You should have a market at this point, where some number of transactions never happen because they aren't willing to pay a fee. So you get some equilibrium of price going on. I proactively want to see this happen because we don't know what fees should be until we run the experiment and see what prices end up being. For this to happen, wallets have to do price setting in some way. For the most part they presently don't. I am going to talk about how they can be made to do that.

First some groundrules, I am only talking about consumer wallets. There are other actors in the ecosystem that might want to handle fees in various ways. Also there's no microchannels, microchannels should be supported eventually but I'm dealing with the simpler case where a wallet is trying to make payments. Also I am assuming that replace-by-fee is in effect. This whole thing doesn't work without replace-by-fee. The way that you need to do payments is pretty broken unless you can replace-by-fee. You need aggressive replace-by-fee. Also you need an anti-dos mechanism, where you don't have an increase-by-epsilon every single time. They must increase it by a certain minimum amount to prevent denial-of-service on the whole network. The conclusion I come to here is that the replacement shouldn't be based on the amount that goes up, but rather that you have a policy that transactions can only be replaced once per block, it should only be after a transaction has been failed to go into a block that you should allow it to be replaced.

What should transaction fees be? It's supply and demand, they meet in the middle to figure out the price. That assumes an extraordinarily simplified model of the world. In real life, the supply of available transactions is extremely noisy, and demand for it is very noisy as well. You have day, night and weekly cycles as well. You have periods in the middle of the night when there's no transactions when the sun is over the pacific ocean or something, and in the middle of the day there's lots of demand.

There should be a time tradeoff. If you are willing to wait overnight, you should be paying much much lower transaction fees than if you needed the transaction to go through immediately. That's an important insight here. Then there's the next question, what should the wallet UX be? This is going to effect the user experience of using a wallet because they need to say somtehing about transactions, specifically they need new inputs. They need to specify the maximum fee to spend on a transaction, and how long the wallet should try to do a send before giving up because it's not willing to pay a required fee. This doesn't mean that the user experience literally needs to ask the user these things, but somehow this needs to be added to the flow. There needs to be a state where if you attempt to send a coin to someone, the wallet has to say I failed to send it within the time allowed for the fee that you said you were willing to spend on it.

Currently in bitcoin there's no way to make it for a transaction to not happen above a particular blockheight; you can make it so that it can't happen below a blockheight, but not above. This creates a real problem because if a transaction fails, it's now in limbo. There's no way to say if it didn't happen by then it's dead. But it's instead in a limbo state where you don't have an assurance that the transaction will never go through; the only way to do that is to spend the inputs, which requires the exact same fee that you weren't willing to pay to get the first spend to go through anyway. So this is a significant problem and I would like to strongly suggest an extension to bitcoin for this functionality be added. It's not a complex extension, but it may be somewhat controversial.

There's a question of what do you actually do- what should wallets do? They can look at what recent transaction fees have been, they can look at recent fees, they can look at mempool data, how long they have been going on current payment attempts. There are some problems with these inputs. What fees were paid in the past is problematic. If you do something where you look at what fees were paid in the past, you can get these crazy spirals where you have peers paying way way more than they need to just off of tradition and what transaction fees were in the previous blocks. This creates miner incentives to exaggerage the transaction price in one mining block because that might force prices up and force them up and keep them there persistently much longer than they would have been to begin with. Using stuff in the mempool requires that SPV clients ask full nodes what's in your mempool, which is trivial pumpable by miners.

You start with either a completely small value like 1 satoshi if you have never sent payments before; you can take the last payment amount times something, as your starting value. I then did some math here. You exponentially increase this up to the maximum that you're willing to spend at the end of the amount of time that you're willing to go, which I assume you're measuring blocks. I assume it's measured in blocks.

M = max fee

S = starting fee

B = max number of blocks from start before giving up

e^(lg(S) + (lg(M) - lg(S)) * H/B)

That's basically my answer to what should be done, it's conservative, it's easily implemented and it can't be gamed in horrible ways. There's an interesting side question of what happens with your utxo combining. You have a wallet with utxos and you have to decide which ones to use for the inputs and which ouptuts, which effects the size of it. This matters surprisingly little because every new input that you get, every new piece of change you will eventually have to be combined, and you will have to pay the price for that, and it will happen at some point and it doesn't matter where that is. So your algorithm for coin selection isn't really effected all that much. You possibly could try and create transactions for doing your combinations at times for when transaction fees are low, and you could do those at your leisure. There are some possible extensions which could help in terms of making your transactions smaller, one is if you are using Schnorr signatures, you could use the combined schnorr signature on those, which would be a nice extension once you have schnorr signatures. You still need to reveal your public keys, which is space. A better one would be if you have two inputs where two need to be signed by the same value, you need to include the signature just once (whereas right now you need to include it twice), and if it's used properly, then it's pushed back the reveal of the same things going to the same output but only by one generation, it's not a big hit to privacy. Finally something you could do that might really provide optimization, every time that you have a private key that you never used in the history of the blockchain, you can give the private key, but I don't believe this saves much space, because you still need a new signature from it.

That's the basics of how I think wallets should handle transaction fees.

https://gnusha.org/url/https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-November/011685.html

https://medium.com/@bramcohen/how-wallets-can-handle-transaction-fees-ff5d020d14fb