Bitcoin Forum
January 22, 2018, 10:51:58 PM *
News: Electrum users must upgrade to 3.0.5 if they haven't already. More info.
   Home   Help Search Donate Login Register  
Pages: [1]
Author Topic: Fair Fees: a proposal for avoiding the Tragedy of the Commons  (Read 925 times)
Offline Offline

Activity: 2

View Profile WWW
July 14, 2013, 03:29:20 AM

The Problems

The Long Term Security Problem
[Skip this part if you are familiar with the Tragedy of the Commons/Race to the Bottom concerns that have been raised in the past.]
Bitcoin security is based on it being expensive to mine blocks. The cost of mining a block is essentially determined by the revenue a miner gets for mining a block. That revenue currently consists of the block reward and transaction fees. The block reward falls over time and transaction fees are currently extremely small. Moreover, since a miner's marginal cost of including a transaction in a block is effectively 0, he has an incentive to include any transaction with a non-zero  transaction fee. Since users would generally prefer to pay as little as possible in transaction fees, transaction fee revenue can be expected to remain minimal and there is no reason to believe that it will be sufficient to maintain bitcoin security in the long run.

The Fee Fairness Problem
Currently, paying more than the minimal amount required in transaction fees has little effect on how quickly your transaction is processed. You might pay 1% of your output volume in transaction fees and find that your transaction is included in a block immediately, but so are other transactions which have payed absolutely nothing. This seems fundamentally unfair and discourages users from funding bitcoin security by paying higher fees.

The Proposed Solution

The solution I propose has the following properties:

1. It is voluntary for both miners and users.
2. It does not require a hard-fork and only those who wish to participate would need to update their software.
3. It is decentralized and low trust, like bitcoin itself.
4. The fees are fair. Specifically, a user can reasonably expect that all the other transactions in the same block as his transaction either paid at least as high of a rate, or waited at least as long, as he did.
5. The fees are clear. When submitting a transaction a user knows how his fees affect the number of blocks his transaction will likely wait.
6. The fees are market base and total miner fee revenue is near the maximum that the market will bear, ensuring that bitcoin security is based on the actual value of that security to bitcoin users.
7. Transactions with minimal or zero fees will still be processed, albeit with more delay.

In a nutshell, here is my proposed solution. The sender, recipient, and/or a third party attaches “security fees” to a transaction. These security fees are separate from current transaction fees and are paid to any one of many intermediaries. If the transaction is included in a block where the security fees are not fair, then the intermediary refunds the security fees, otherwise the intermediary pays the fair amount to the miner and refunds the balance. The fair security fees for a transaction of a particular size that has been waiting for a particular number of blocks is determined by the consensus security fee schedule that was in effect around the time that the transaction was submitted. The consensus security fee schedule is the median of the security fee schedules requested by the miners of the most recent 2016 blocks (~2 weeks).

Miners should like this because it provides a way for them to set different prices for different levels of service and thus get more revenue. Users who currently pay more than the minimum transaction fees should like this because 1) if they put that excess toward “security fees” instead, they can be sure to get better service in return, and 2) it encourages others to pay their fair share.

Of course, the devil is in the details. Everything that follows is an initial proposal for how the details could be addressed. Specifically, who can be trusted to be an intermediary? How do nodes keep track of how long a transaction has been waiting? How do miners publish their desired security fee schedules? How do users attach security fees with transactions? How do miners determine whether a transaction's security fee is sufficient to get it into the current block? How do nodes determine whether the security fees paid in a block are fair from each user's perspective?  What happens to transactions which don't have attached security fees?

Becoming an intermediary

Each intermediary could steal all of the security fees with which he is entrusted.  Fidelity bonds can be used to make that unprofitable. Any address that wants to be an intermediary must have a "fair fees" fidelity bond. A "fair fees" fidelity bond is just a fidelity bond that was paid to a particular fixed unspendable address (e.g. "1FairFeesBlahBlahChecksum"). The size of the bond that is required to remain an intermediary varies with time.  The required size of the bond is the total of all unconfirmed payments required of the address (i.e. paying security fees to miners or refunding them to users) plus twice the highest total amount paid in combined security fees and transaction fees for any of the last 2016 blocks. If an address actually breaks the rules (e.g. by paying a miner for an “unfair” block), then that address is no longer considered an intermediary unless/until they acquire a new fidelity bond.

Definition: An address is an intermediary if it 1) has paid a fair fees fidelity bond in an amount at least as high as the sum of all unconfirmed required payments for the address plus twice the highest total amount paid in combined security fees and transaction fees for any of the last 2016 blocks, and 2) has never broken the rules since it last paid for a fidelity bond.

To encourage at least miners to become intermediaries, intermediaries must obey the following rule:

Rule #1: An intermediary must only pay miners who are intermediaries.

Tracking Transaction Wait Time

When a miner receives a transaction he can use it's security fee to determine whether to include it in the block that he is currently mining. In addition, he should make a list of the transaction IDs of all of the excluded transactions, and include that list in the block being mined. If he successfully mines the block, inclusion of the list will prove that those excluded transactions were first seen no later than that block. When future blocks are being mined, miners will use the exclusion lists to determine how long each transaction has been waiting. A miner has an incentive to include an excluded transaction’s ID on the exclusion list. The incentive is the possibility that he will mine a later block that can include the transaction and will then receive the transaction’s security fees.

The exclusion list is stored in the block by converting each transaction ID to a fake address in a deterministic way and spending 0 BTC to each of those fake addresses in the generation transaction of the block. The fake address is computed by substituting the first 20 bytes of the transaction ID for the key hash when computing a normal address.

Publishing security fee schedules

A security fee schedule is a piecewise linear nonincreasing function which maps a delay to a fee rate. A miner publishes his desired security fee schedule in the coinbase of a mined block. The format of the schedule is "/ Fair Fees Schedule: DELAY[0] RATE[0] DELAY[1] RATE[1] ... DELAY[N] RATE[N] /". RATE[K] is the rate that the miner desires for transactions that have been waiting for DELAY[K] blocks. If a particular delay is not explicitly listed, then the rate is linearly interpolated between the two closest rates. For the schedule to be valid, the following must be true:

1. DELAY[0] == 0
2. 0 <= RATE[0] <= 100%
3. DELAY[K] >= DELAY[K-1]
4. RATE[K] <= RATE[K-1]
5. RATE[N] == 0

Attaching security fees with transactions

Any amounts sent to the address of an intermediary are considered security fees.

Security fees that spend an output in a zero-confirmation transaction are attached to (i.e. pay for) that unconfirmed transaction. This allows senders to pay security fees from the change address of an unconfirmed transaction and allows recipients to pay security fees from the output of an unconfirmed transaction.

Security fees that spend a non-zero confirmation output are attached to the transaction that includes that spend. This allows senders to pay security fees directly as part of a transaction.

If a transaction with attached security fees includes a spend of 0 BTC to an address that is an output in a separate zero-confirmation transaction, then the security fee will apply to the other transaction as though it were part of that transaction. This allows third parties to pay security fees for transactions where they are neither the sender nor recipient.

Example: Alice wants to send Bob 10 BTC. Alice creates a transaction spending a 15 BTC output A1. 10 BTC goes to Bob’s B1, 4.99 BTC goes to Alice’s change address A2, and 0.01 BTC goes to an intermediary as security fees.  Bob can attach security fees to the transaction by creating another transaction that spends some of B1 to an intermediary. Alice can attach additional attach security fees to the transaction by creating another transaction that spends some of A2 to an intermediary. Carol can attach security fees to the transaction by creating a separate transaction that spends 0 BTC to either A2 or B1 and spends the desired security fees to an intermediary.

Determining whether a transaction has the required security fees

To determine whether a transaction’s security fee is sufficient, a node needs to 1) determine the required security fee rate for the transaction, and 2) determine how much that rate corresponds to in actual security fees required for the transaction.

To determined the security fee rate required for a transaction, the node uses the transaction’s wait time to gather the rate schedules published in the 2016 blocks preceding the block which first contained the transaction in its exclusion list. If the transaction has not been in an exclusion list, the node uses the rate schedules published in the most recent 2016 blocks. Any rate schedules published by miners who are not intermediaries are ignored. The transaction’s wait time is then used to look up the rate in each rate schedule and the median of those rates is used as the required rate.

To convert the required rate into the security fees required for the transaction the node would, ideally, multiply the rate by the amount transferred by the transaction (and any dependent pending transactions). Unfortunately, since addresses are pseudonymous and users routinely use new addresses for accepting change, determining the exact amount transferred is not always possible. Instead, the node uses an estimate designed to almost always err on the high side while allowing the user to reduce the error as much as desired.

Specifically, the node uses the “estimated transferred amount” for a transaction which it computes as the sum of all of the transaction’s outputs except for any outputs sent to an intermediary’s address (i.e. the security fees) and any “change” outputs. A change output is an output that has the same address as an input but has less bitcoins after the transaction than before. If there are no change outputs that meet that criteria, then the smallest remaining output is considered a change output.

Once the node has computed the total estimated transferred amount for a transaction and any dependent pending transactions, it multiplies that amount by the transaction’s required security fee rate to get the transaction’s required security fees.  The actual security fees attached to a transaction might be higher or lower than the required security fees. If they are lower than required, then the transaction might be delayed. If they are higher than required, then the intermediary will pay, at most, the required amount to a miner and any excess will be returned.

Determining when security fees are fair

Users don’t want to pay more than necessary in security fees. That means that a user doesn’t want the security fee rate he pays for his transaction to be higher than the security fee rate paid for any other transaction that has been waiting for the same or fewer blocks. To avoid that, intermediaries must obey the following rules:

Rule #2: When a block is mined containing transaction T which has been waiting for B blocks, if the miner is not an intermediary or the block includes any transaction which 1) has been waiting for at most B blocks, and 2) has less than its required security fees, then any intermediary that received security fees attached to T must return those fees via the change addresses in the transactions from which they were paid, on a pro rata basis.


Rule #3: When a block is mined containing transaction T which has been waiting for B blocks, if the miner is an intermediary and every transaction in the block which has been waiting for at most B blocks has at least its required security fees, then each intermediary that received security fees attached to T must pay its portion of the required fees to the miner and return any excess via the change addresses in the transactions from which they were paid, on a pro rata basis.

The destiny of transactions which have little or no security fees

Note that the rules say nothing about transactions which have been waiting for more than B blocks. This is because, when determining whether the security fees he pays are fair, a user does not care about transactions that will need to wait longer than his. This means that miners can choose to use security fees to determine which newer transactions to include but ignore security fees when determining which older transactions to include. Exactly how many blocks a transaction needs to be waiting to be considered “older” will depend on the cost and benefit of doing exclusion based on security fees. The benefit is the security fee revenue. The cost is the lost transaction fee revenue from the excluded transactions. The meager security fees attached to transactions that have been waiting for many blocks will not be enough to make up for the transaction fees of all the transactions that would need to be excluded to capture those security fees.

This means that even a transaction with no security fees will be included in a block once it has waited long enough that miners no longer find it profitable to forgo its transaction fees to capture the security fees attached to other transactions.


To summarize, bitcoin security can be improved in the face of falling block rewards by a system which encourages users to pay their fair share of security costs to fidelity-bonded intermediaries in the form of “security fees”. When a block is mined by an intermediary, all intermediaries pay the miner only the amount that was required to get each transaction in the mined block, refunding any excess to the users. The security fee required for a transaction is determined by using a transaction’s delay to look up a rate in the median security fee schedule, and applying that rate to an estimate of the amount transferred by the transaction. The delay of a transaction is tracked by adding an exclusion list to each mined block, each such list containing the ID’s of transactions that are being excluded for the first time.

If you’ve read this far, many thanks for your patience. I’d appreciate any feedback on this proposal.
Pages: [1]
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!