Transaction Fee rework proposal

TransactionFeeProposal.md

Reworking Bitcoin Transaction Fees

Transaction fees as they are currently implemented in the original Bitcoin code suffer from a few problems:

• The rules are complicated and ad-hoc
• Fees are hard-coded and do not reflect real costs
• Adding fees to a transaction doesn't necessarily make it more likely the transaction will be confirmed more quickly.

I'm proposing changing the rules miners use to decide what transactions to include in their blocks, and changing the way clients tell users whether or not any particular transaction "needs" a fee to be confirmed in a reasonable amount of time.

Economic reasoning

For Bitcoin to thrive, there should be a market between the miners who include transactions in blocks and the users or merchants who want their transactions confirmed. There is natural competition between miners; they have an incentive to include as many fee-bearing transactions in their blocks as possible, given constraints on either the block size or the time it takes them to validate the transactions and construct a block.

Users and merchants want to pay as little as possible for transactions. If users and miners are free to decide what fees they will send and accept, fees should quickly drop to the "correct" level, reflecting the total cost to miners of accepting transactions and the preference of users for fast versus slow transaction confirmation.

Any miners holding on to some bitcoin also have a meta-incentive-- to help make Bitcoin usage and value grow. Therefore, I believe most miners are willing to include some free (zero-fee) transactions in the blocks they create. Free transactions are wonderful, but they also make "transaction spam" possible-- it has to be difficult for a troublemaker to succeed in sending thousands of free transactions to themselves just because they can.

Review: current rules

Transaction fee handling code accreted over time, with ad-hoc rules added to combat transaction spam. The rules currently are:

Memory pool rules (if rejected by memory pool, transaction isn't relayed or mined):

Transactions more than 10k big, or that have an output less than 0.01 BTC, or that are low priority must pay a fee of at least 0.0001 BTC per kilobyte to get into the memory pool.

Block creation rules (bitcoind/bitcoin-qt)

Transactions in the memory pool are sorted by priority, then inserted into blocks in priority order, with the following rules:

• If less 4kb of transactions have been added to the block, allow any transaction to get into the block. I believe this is dead code, since very-low-priority transactions never enter the memory pool (it's possible I'm missing some way that very-low-priority/very-low-fee transactions might actually get mined)
• Else if less than 27kb of transactions have been added, allow any transaction.
• Else only include transactions that include a sufficient fee (0.0005 BTC per kb or greater).
• If more than 250kb of transactions have been added, the fee required for inclusion is raised exponentially up to the maximum generated block size.
• The maximum generated block size is 500kb. (the maximum network-accepted block size is 1mb).

Priority is calculated as sum(btc_value*age)/tx_size -- small-in-bytes, high-value transactions that use old inputs are given priority. A value of 1BTC * 144blocks / 250bytes is hard-coded as the cutoff between "low" and "high" priority transactions (1BTC is 100000000 units, so priority=57,600,000 is the cutoff).

Client rules (bitcoind/bitcoin-qt)

If a transaction has sufficiently high priority, is less than 10Kbytes big and has no outputs less than 0.01BTC then it is sent without a transaction fee.

Otherwise, the user is told that a fee of 0.0005 BTC/kb (by default, users may increase this but not on a per-transaction basis) is required.

Goals

In rough order of priority:

• Create a self-regulating market for transaction fees between miners and merchants/users
• Smoothly transition from the rules we currently have in place to the new rules; transactions from users running old versions of Bitcoin should get confirmed reasonably quickly under the new rules.
• Make sure transaction spam is expensive for would-be spammers
• Replace compiled-in constants with dynamic, market-determined values

Spam prevention

If transactions are free, is cheap and easy to create tens of thousands of transactions- just send bitcoins to yourself over and over. Transaction spam like this is prevented using the priority metric-- because input age is a limited resource, the would-be spammer quickly uses it up and runs out of "aged" inputs to spend.

Legitimate users who might want to receive and then quickly spend bitcoin can still do so, they just have to pay a transaction fee.

The current rules for including transactions in the memory pool are working reasonably well, but to plan for the future the currently-hard-coded "free" and "low-priority" constants in the reference software will be replaced with variables that miners or users can change.

Creating blocks

Mining pools and solo miners have already started implementing their own fee policies, and will, of course, be free include or exclude transactions based on whatever policy they like. However, if they do implement their own policy they are strongly encouraged to use transaction fee-per-kilobyte and/or transaction priority to determine which transactions to include in their blocks, because client software will assume those are the criteria used to determine how quickly transactions are confirmed.

Pools or solo miners using the reference implementation (bitcoind/bitcoin-qt) will be given more control over the block creation process, using the following parameters:

target block size : This is how large blocks "aught" to be. If not set, it will default to the median size of the last 100 blocks in the chain (approximately 50Kbytes at the time of this writing).

maximum block size : The maximum size block that can be created. If not set, it will default to the same as the target block size. Miners can increase this to make room for more fee-paying transactions.

priority fraction : A value between 0.0 and 1.0, this determines how much of the block is reserved for high-priority transactions versus how much is reserved for low-priority-but-fee-paying transactions.

The algorithm for deciding what transactions to put into a block will be:

If priority fraction is greater than zero, sort all memory pool transactions by priority and then include as many of the highest-priority transactions as will fit into target block size x priority fraction bytes.

Next, sort all remaining memory pool transactions by fee-paid-per-kilobyte, and include as many as will fit until the block is maximum block size bytes big, not including "free" transactions (transactions with fee-per-kb of less than the default spam threshold of 0.0001 BTC/kilobyte).

This algorithm should maximize miner profit, make it easier for users to predict how long their transactions will take to get confirmed, keep transaction spam under control, and be compatible with the rules clients are using now to determine whether or not to include a transaction fee.

Is a "dust spam" minimum transaction output value needed?

There is a special case in the current code that requires a minimum transaction fee if a transaction has any very-small outputs.

Artificially limiting the block size and sorting low/no-fee transactions by priority eliminates the need for that special case; a transaction spammer has to pay either in bitcoins or in 'aged inputs' if they want to add useless transactions to a block.

To be compatible with the existing transaction confirmation rules, clients should continue to avoid creating sub-0.01 BTC outputs, and if a transaction is created with a sub-0.01BTC output they should continue to suggest that a fee be paid until a significant number of miners upgrade to use the new fee rules.

The reference software also has a bug that causes performance problems when sending transactions from wallets that contain a very large number of small transactions, but that bug will be fixed.

Should the priority calculation be changed?

As the total number of transactions grows, transaction pruning schemes that "forget" old, completed transaction become more and more important. Pruning is possible when all of a transaction's outputs are spent, so a transaction that takes 10 inputs and combines them into 1 output is good for the network.

The transaction priority calculation could be modified to prefer transactions with a high ratio of inputs to outputs. However, we need to be careful and make sure that there is still an incentive to use 'sendmany' instead of creating dozens of single-in/single-out transactions; a 1-input-10-output transaction should not have one-tenth the priority of a 1-input-1-output transaction.

To give a mild preference to transactions with fewer/smaller outputs than inputs the priority formula could be modified to be:

priority = (sum(value*age)/size) * (1000 + size of previous txouts) / (1000 + size of this txn's txouts)

Receiver-pays-fees model

When deciding what is a fee-paying transaction and what is not, it is a good idea to consider groups of related transactions together. For example, if a user sends a fee-less transaction to a merchant, the merchant might combine it with a few dozen other fee-less transactions and pay a fee to "sweep" them all into a savings address and get them confirmed. It would be fairly straightforward to consider the total size and fees of a set of related transactions together when deciding what to include in a block.

Clients: UI changes

When a significant number of miners are using fee-per-kilobyte as (one of) the criteria for what transactions to include in their blocks, end-user bitcoin software should be changed to let the user select how much of a fee to include with each transaction sent.

Client software with access to the full block chain should be able to estimate the average miner's fee policy by observing transactions as they enter and exit the memory pool. If they have not connected long enough to generate a good estimate, they could derive an estimate from the transactions that were included in the last 100 or so blocks.

Client software should also be able to estimate the average miner's priority policy by observing high or low priority, free transactions as they enter and exit (or never exit) the memory pool. As now, if a user is sending a high-priority transaction and high-priority transactions are typically accepted quickly (in the next block or two) then the transaction should be sent without a fee.

Fetch "current fee policy" ?

It would be easier if we maintained a "suggested fee policy" on bitcoin.org, and Bitcoin-Qt HTTP fetch'ed that data during client startup. The core developers would run a bitcoind that watched the memory pool and generated its own estimate of average fees.

However, that opens up privacy concerns and centralized infrastructure.

Client software that does not have access to the full block chain cannot currently tell how much fee a transaction is carrying, because fee is computed as (inputs-outputs) and the software cannot look up the inputs.

**maybe extend the 'tx' network message so it includes the fee as an extra uint64 ... could be verified before relaying, but could somebody try to trick SPV clients into recommending extra-high fees by spamming them with bogus 'tx' messages? **

Have miners publish their fee policies in blocks they create ?

The idea of miners publishing their fee policies has been floated, and while I think that is a fine idea I think we should avoid relying on miners telling the truth if we can avoid it. They have an incentive to say one thing ("you must pay 0.01 BTC/kilobyte") but do something different (include transactions that pay just 0.0001 BTC/kilobyte).

Changes to the RPC interface

New method(s) to get/set the fee policy parameters; when set, they affect the next block created. These can also be set by command-line/bitcoin.conf parameters.

The fee policy parameters will also be used by the RPC send* commands. If generating a transaction with a priority less than the minimum, fees will automatically be added; otherwise, the transaction will be sent fee-free.

RPC users that want complete control over transaction fees can use the new "raw transaction" API.

Metrics

Metrics we should keep track of to make sure the fee policy is working as expected on the production network:

• Median block size
• Average transaction fee-per-kb
• Average number of blocks for a transaction to get its first confirmation
• Percentage of "free" transactions over the last 100 blocks

As discussed on IRC, I think the layout of "Maximum number of kilobytes worth of paid transactions to include in a block" will cause people to be less generous than they would be otherwise because reasoning about the fees they'll lose is hard.

Instead I suggest "Maximum amount of BTC to give up in order to process transactions in order of priority: M". The algorithm would be:

Set (for the purpose of selection) all fees below the amount/kb to be considered a fee to zero.
Order transactions by fee per kb. Stop when you hit maximum size.
Go backwards and remove M BTC in fees worth of transactions.
Add transactions in order of priority, stopping when the block is full or when the maximum amount of 0 fee transaction data is hit.

I think this is better, easier to reason about, and will encourage more reasonable generosity.

The remaining problem I see is that 'Minimum transaction fee-per-kilobyte to be considered "paid"' will very likely be set to 0 often and it's very bad if people do this, and the reasons to not do this are subtle. I'd rather find a way of expressing— perhaps in terms of the recent average transaction sizes— which is dynamic enough that we can have a floor for the option. E.g. Percentage of the mean transaction size in the last 2016 blocks... and not let anyone set it below one. (Or perhaps something else where 0 happens to not map to 0 btc).

@gmaxwell: gist updated.

IRC discussion link: http://bitcoinstats.com/irc/bitcoin-dev/logs/2012/06/20/4#l3794671

This seems to ignore the refactoring already done in txn_prio. This enables miners to configure the prioritization algorithm, and considers the fees paid on dependent transactions such that they can pay for their precedors.

As mentioned many times, it is impossible to reasonably infer miners' transaction inclusion policy. I also don't see how miners potentially lying about their policies can be harmful (in your example, the miner could just as well honour the higher fee requirement, and nothing would change about user experience).

Edit: gmaxwell explained a reasonable way to infer fee policies, so nevermind that part

Just a thought before I forget it: In the future client behavior, when a TXN would be below the threshold where it wouldn't get relayed while being free bitcoin should say "will not be sent for X blocks" and then not attempt relaying it until it's above threshold. during that time it should show as unsent and by trivially abortable (right click->abort or something like that). Its important that we don't actually try to relay it in this state, because thats what makes the fast aborts safe. This should be helpful because I suspect a majority of txn which hit the relay rule would actually be free with a few more confirmations.

More IRC discussion: http://bitcoinstats.com/irc/bitcoin-dev/logs/2012/07/03/2#l3914072

Gavin,
I applaud your efforts. Thanks! Tx fees are an important part of the long term success of Bitcoin. Currently, it has little effect on the economy as long as transactions are cheap, they work, and spam is mitigated. As Bitcoin moves away from block rewards towards being sustained by tx fees, this will over time become a hotly discussed issue. It's a definitely worth the effort to get this aspect of Bitcoin correct now. It will only get harder in the future.

I've pondered extensively over this aspect of Bitcoin and it was a very pleasant surprise to see you were on the same page. The highlight of the proposal for me was that of giving "knobs" or more control over tx fee policy to the miners. Tx fees is very complex with respect to the very simple block reward system that it is meant to replace. I don't see any golden bullet to solve this unless someone can see the future. The only solution is empowering the bitcoin miners and creating a system where they can communicate how the tx fees work for them.

So, I want to share my viewpoint which I hope you find useful as you continue to craft the proposal above and others. I'm a little late to the game of cyrpto-currency, but it has captivated me ever since I discovered it. One thing that has excited me about Bitcoin from the very beginning was that it is democracy driven and somewhat immune from negative central influence. However, over time I realized that my mining vote was limited. I could vote to mine or not to mine at all. That was it! Well, I also felt responsible to make sure I agreed and understood the updates to the Bitcoin protocol. I noticed those that had real influence over the destiny of Bitcoin was the core development team. This realization is part of what has attracted me here. The tools to exercise my portion of influence or "vote" were not present to my satisfaction as miner. This is also the reason why your proposal excites me a lot as part of your goal is to empower the miners more.

I want to try and explain the idea that has plagued my mind for some time now. Should be complementary to the proposal above. It's also about empowering the miner. First, what do I call this idea? "Democracy on the fly" maybe. (don't really like the word democracy).

So, here's an example. Let's say I'm mining and another miner or pool passes me a newly minted block that just doesn't agree with me. (i.e. full of spam, no transaction, etc.). The current system (as I understand it) gives me two options: live with it or fork. However, I'm proposing a third option. I ignore the block and continue to mine on top of the previous block for a small amount of time. Let's call it protest mining. The amount of time I protest mine would match the amount I disagreed with the block (for example, it could be just one minute before I switch to mine on top of the "stinky" block). All this "protest mining" would be to my individual loss. In essence I would be taking a gamble to influence the network the way I would like it work at my expense.
The fact that a miner is burning hashes this way, he/she would be eager to communicate to the community his standards and protocols. At the same time, the community would be very eager to understand why there was an orphaned block if enough protest mining is successful. They would then have to consider the risk of not considering the changes that are being influenced on them.

This is a solution I see to a very complex problem that cries for central control, but we all know that that route is not an option.

Just give me a few tools. I would be happy to sacrifice some of my hashes. The best part about it, I would feel empowered even if no one agreed with me. I could still participate in Bitcoin yet lean on its direction towards the way I like it. You don't even need to get a general consensus to implement this. Just give the miners the tools. Though, the most critical foundation for it to work is an effective communication tool so all the "protest mining" and increased number of orphaned blocks can be understood and analyzed.

Some assorted comments:

• Why "priority fraction"? I was a big fan of the "fees to forgo to give high-priority, low/no-fee transaction into block" As a miner, I would be more inclined to forgo .01BTC in fees, but a "give up fees in this % of the block" setting, I believe would be more often set to 0. Also, the target vs maximum block size distinction I find unclear and slightly redundant (if nothing else, just setting priority fraction * target block size as one setting would make it more clear)
• dust spam min output? I dont like the idea of this. I highly prefer to put this logic in a proper priority algorithm, if possible.
• Priority changes? Absolutely. However, I do not like the suggested one. In my gist fork I noted "A good priority algorithm will take into account the cost to the network as well as the "spammyness" of a given transaction. It should also be easy to calculate an intermediate value for a given txout may be, to make coin selection efficient." The given priority algorithm's 10+'s makes an ideal coin selection algorithm difficult.
• Client UI Changes: " If they have not connected long enough to generate a good estimate, they could derive an estimate from the transactions that were included in the last 100 or so blocks." Really dont like this. many users open their clients, let the chain sync, send some coins, and immediately close their client. Instead, the current fee policy calculated by watching the transactions that are sitting, not getting confirmed in mempool should be published on bitcoin.org automatically (as it is also needed for SPV nodes to get current fee policy) and that can be used while the fee policy has not been calculated locally.
• Fetch "current fee policy": I really like this idea (mostly because it makes SPV clients with remotely correct fee policy calculations possible). In terms of addressing the centralization issue, since every bitcoind will be able to calculate fee policy (and will be calculating that anyway), I believe making the information published on bitcoin.org retrievable using an RPC call (would simplify the bitcoin.org maintenance too) would be prudent. Though the information is not deterministic, I would think most nodes would get fairly similar values, so it would be trivial for people to set up checking sites that keep historical data that compares bitcoin.org's published values to values generated locally.
• Miners publish fee policy in blocks: absolutely not. As gmaxwell noted, you really want to watch transactions that are sitting in mempool unconfirmed and not rely on data that miners can trivially create/heavily impact without too much loss of profit (as they have strong incentive to do so).

How is this going to stop the inevitable race-to-the-bottom?

The word "market" appears many times in this proposal, and there's a lot of talk about demand for blockspace, but very little attention paid to supply of blockspace -- the other half of the supply/demand balance that determines a market. Unless blocks start approaching the protocol's hardcoded maximum block size, the Nash equillibrium is 1-satoshi transaction fees. There is no incentive for a greedy solo miner to exclude a transaction with a nonzero fee, no matter how small. I don't see anything in this proposal that changes the incentive structure for a greedy solo miner.

If you think the hardwired block size limit (6MB of transactions per hour) will come riding to the rescue, what makes you think that the magic number "6MB/hr" is both high enough to not cripple the network a decade from now and also low enough to force transaction fees to a level that can replace the block subsidy? I can't say I have any reason to believe one way or the other; the number was chosen pretty much arbitrarily. Just hoping that an arbitrarily-chosen number was the right guess seems like a bad strategy to me.

Right now the block subsidy ensures that the amount of mining scales with the value of the overall money supply. As BTC becomes more valuable (in whatever terms you care about) the block reward becomes more valuable, and marginally-profitable mining operations come back online resulting in a higher network hashrate. This ensures that the mining rate won't drop to zero unless bitcoins themselves become worthless. This is important. In the post-block-subsidy world where transaction fees somehow magically take over this role, there is no adaptation mechanism -- nothing ensures that the amount of mining scales with the value of the money supply that it protects.

RE: race to the bottom: This has been discussed to death on the Bitcoin Forums. I think it is pretty clear that the big mining pools and individual miners DO have a (small) per-transaction processing cost, and that cost will put a floor on transaction fees; they will NOT drop to 1-satoshi, unless it actually only costs miners 1 satoshi to validate a new transaction. The actual cost is much larger than that right now, and we are already seeing miners limiting the size of their blocks because of the costs (at the very least, large blocks take longer to propagate across the network, which is an indirect cost to miners because it makes their blocks a little more likely to be orphaned).

I think the right answer to eldentyrell's comments would be "It doesn't". This improves some things about the current behavior and doesn't do anything for the long term economics; and thats fine.

I think the "I think it is pretty clear that the big mining pools and individual miners DO have a (small) per-transaction processing cost, and that cost will put a floor on transaction fees;" — cost of validation sets a floor— argument sounds questionable to me. This is a cost born by all the full validating nodes, including all the nodes that were trying to mine this block but failed. And mining a transaction alone isn't enough— security requires that it be burred even after the fee is assigned. I only see this incentive structure working out if there are very few full validators and all of them miners, since only about 4k blocks will be solved a month... and the more-processing-causes-delays argument is only strong when there are already a lot of fees or subsidy.

The rate regulation eldentyrell points to for coin supply works because evidence of work is can't be faked— it's far from clear how to get something comparable for the permitted transaction volume, things like coins-days-destroyed seem to require too much magic guesswork in order to set the 'right' levels. Perhaps a simpler thing to do as the subsidy becomes inconsequential is to start adopting minimum difficulties.

But in any case, none of this is going to be solved today.

I think Vermin Supremes method of using blueberries as payment for transactions is very efficient.

The problem of hard coding algorithm fees into the protocol is that the market is always changing. There is no one size fit all.

I believe the best option would be to just provide information that Miners and Clients can use and they will decide what fee they want to set. Based on the information they collect from the network (eg. mining power, unconfirmed transactions, BTC transaction volume etc), they can develop some software themselves (outside the BTC protocol), and have their transaction fees set for them. Over time, they will see if certain transactions are being processed or not and how much fees it was, and they will adjust their fee settings accordingly.

Remember:

• Clients - have many different types: Personal use, Business use, Retail use, big trades and little trades - they are all going to be different and some will want to pay more fees as they are transacting in large amounts and wants confirmation as soon as possible, and others cannot afford to pay too much fees as the profits are too small (eg retail).
• Miners: Some are in it to make money from mining, so they want good fees to keep them in business. Others are just there to give support to the network as they make money from other sources indirectly (so they dont care about fees as much).

The idea of miners publishing their fee policies has been floated, and while I think that is a fine idea I think we should avoid relying on miners telling the truth if we can avoid it. They have an incentive to say one thing ("you must pay 0.01 BTC/kilobyte") but do something different (include transactions that pay just 0.0001 BTC/kilobyte).

Wouldn't this be avoided by rejecting blocks that don't match their own fee policy? If the block says "You must pay 0.01 BTC/kilobyte", and contains a 4 kB transaction with a 0.02 BTC fee, it should be an invalid block.

There would need to be some mechanism to avoid a blockchain fork. Perhaps the validation could be implemented immediately, and the publishing later, once a majority of nodes are able to validate fee policies.

I've managed to think of a way to solve how we can build network of independent Bitcoin services: All service providers run a Bitcoin node that subscribes to the same pool. Not mining pool. Transaction pool. This pool has services, all are tracked. Tracking allows pooling funds and accounting. Transactions are processed faster, and the network grows stronger. Simply connecting a miner into the transaction pool would turn the pool into a mining pool. Connecting a merchant service to the pool would run merchant services in the pool. The requirement to participate in the pool would be running a Bitcoin node, and pointing it into the pool.