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.
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.
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
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.
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)
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 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