The reference implementation of Bitcoin (bitcoind/Bitcoin-Qt) has ad-hoc code for dealing with transaction priorities and fees. In particular, there are several 'magic' constants that are chosen by the core developers, setting policies for minimum transaction fees, minimum transaction priorities and minimum output sizes.
This document describes the algorithms used by my 'smartfee' branch to replace most of those arbitrary constants with values that will rise and fall based on transaction volume and miners' willingness to include transactions in their blocks.
The reference implementation needs to know two things to provide a good user experience:
- If a transaction has priority X, is it likely to be included in the next N blocks?
- If a transaction has a fee of Y, is it likely to be included in the next N blocks?
... where N is a preference set by the user (who might sometimes want very fast confirmations, and might sometimes be willing to wait 24 hours if they can avoid paying a fee).
smartfee estimates miner's fee/priority policies by recording the fees and priorities of the last 10,000 transactions it has seen as they exit the memory pool and are included in blocks. The data (approximately 320K) is saved to disk at clean shutdown, and read back in on next startup. Until a sufficient (100) number of transactions have been observed, hard-coded fee rules are used.
A new RPC method returns estimates:
estimatefees [prioritymedian=0.1] [feemedian=0.5]
Returns estimate of priority or fee needed to get transactions accepted into blocks.
Values returned are:
freepriority : priority required for 0-fee transactions
feeperbyte : median transaction fee (satoshis/byte)
Values of -1.0 are returned if not enough transactions have been seen to make a good estimate.
For example, estimates right now (13 Sept 2013):
> bitcoind estimatefees 0 0
{
"freepriority" : 55803571.42857143,
"feeperbyte" : 10.22756328
}
How to interpret those numbers: the lowest priority zero-fee transaction accepted into a block in the last 10,000 transactions had a priority of about 56 million. The lowest fee zero-priority transaction accepted into a block in the last 10,000 transactions had a fee of 10 satoshis per byte (or .000026 BTC if it was a typical 257-byte transaction).
> bitcoind estimatefees 0.1 0.5
{
"freepriority" : 77085866.30232558,
"feeperbyte" : 194.55252918
}
So 10% of zero-fee transactions had a priority of 77 million or less, and 50% of zero-priority transactions had a fee of 194 satoshis/byte (or 0.0005 BTC for a typical 257-byte transaction-- the current hard-coded minimum fee).
Instead of using hard-coded rules, the bitcoind send methods (sendtoaddress, sendfrom, sendmany) will do the following:
get the 10%-median priority estimate needed to get into a block
if the transaction's priority at the next block height is greater than that estimate:
send the transaction without a fee
else:
if the user has set the paytxfee option: send it with that fee-per-kilobyte
else:
estimate the median fee needed to get into a block and send it with that fee-per-kilobyte
Another place the hard-coded constants are used is the transaction relay policy. The problem is: given that we receive a transaction from a peer, should we bother adding it to our memory pool and relaying it to other peers or not?
I propose that the relay policy for non-miners be changed to be entirely based on the estimates of fees/priorities that miners will include in blocks. Because those estimates inexact, I think the relay policy should also be "fuzzy" -- zero fee / zero priority transactions should have zero chance of being relayed, but higher priority or fee transactions that might or might not be interesting to miners should have a higher chance of being relayed. Transactions that will almost certainly eventually be accepted into blocks should always be relayed.
At the risk of introducing Yet Another Set of Magic Constants, and after testing several policies, an exponential (N^2) fall-off in chance-of-being relayed from a 1%-median-estimate level works well to suppress transaction spam but still get all reasonable transactions to miners.
Miners that explicitly set -mintxfee and -minfreepriority will use those directly instead of trying to infer a policy from the behavior of other miners.
Pseudo-code for relay policy algorithm:
If -mintxfee and -minfreepriority are set: use them for the relay/don't relay decision.
Else:
Compute 1%-median priorityEstimate/feeEstimate (hard-coded default if not enough data to estimate)
Compute transaction priority/fee
If transaction priority or fee is greater than estimates: relay.
Else:
Get a random float between 0.0 and 1.0
if (priority/priorityEstimate)^2 > random float: relay
or if (fee/feeEstimate)^2 > random float: relay
Note: if the networking code can detect that relaying transactions is using too much bandwidth, the 1%-median number could be dynamically increased/decreased until the right number of transactions were relayed. Or perhaps the user should specify a bandwidth budget...
The definition of "dust" outputs is based on the currently-hard-coded transaction fee. Changing it to be based on the median estimated transaction fee will be straightforward.
The CreateNewBlock function in the reference implementation already implements a market-driven mechanism for the supply side of transactions. Miners can decide the maximum size of their blocks, the smallest fee-per-kilobyte transaction they are willing to consider "paid", and how much space in their blocks they are willing to set aside for high-priority "free" transactions.
At least initially, I have no plans on changing the criteria miners use to fill their blocks. Using the same fee estimation methods for both miners who don't bother changing defaults and users is probably a bad idea, because doing so might cause unintended feedback loops that drive fees up or down.
Question: give the user more knobs to influence policy? E.g. there could be a "calculate priority transaction will have in N blocks" and "use 1%-median priority" if you are willing to wait longer to avoid fees. Or "use 75% median priority and fees" if you want transactions to confirm quickly.
I think the GUI should use a similar algorithm to bitcoind, but should give the user the ability to adjust the fee paid (if needed) on a per-transaction basis, within a reasonable range (Bitcoin-Qt should still refuse to create a 0-priority 0-fee transaction that has little chance of confirming in less than a year):
get the 10%-median priority estimate needed to get into a block
if the transaction's priority at the next block height is greater than that estimate:
just send the transaction immediately without a fee
else:
recommend that the user select a fee between:
slow confirmation: if tx priority in 24 hours will be 10%-median estimate: 0-fee
otherwise suggest 5%-median fee
fastest confirmation: 95%-median fee
... with the default at the 50%-median-fee level.
With the state of the network today, that would result in Bitcoin-Qt suggesting that the user give a typical 257-byte transaction a fee of between 0.0001 and 0.001 BTC:
> bitcoind estimatefees 0.05 0.05
{
"freepriority" : 56912062.25680933,
"feeperbyte" : 38.75968992
}
> bitcoind estimatefees 0.95 0.95
{
"freepriority" : 25296000000.00000000,
"feeperbyte" : 387.59689922
}
A new protocol message so SPV clients can query full nodes to get their estimate of transaction fees is probably a good idea, as long as the SPV clients are well-connected and ask several of their peers (miners have an incentive to lie about transaction fees to try to get SPV clients to pay higher fees, and attackers might lie just to cause trouble).
IRC discussion with Mike RE: SPV clients: http://bitcoinstats.com/irc/bitcoin-dev/logs/2013/09/13#l8733495