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.

and:

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.

Conclusion

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.

This is my contribution to the November 2012 discussion of the potential for a Double Double Spend attack on bitcoin. Since it is an old thread, I'll start by trying to recap the existing discussion.

<recap>
As described in cunicula's original post, the attacker secretly mines a side chain block containing a double spend and then, after the victim has received enough confirmations to accept the original spend, the attacker bribes miners to mine on his side chain. Every time a side-chain block is mined the attacker pays the miner, on the main chain, an amount equal to the block reward, and also pays some small amount to the miner on the side chain in addition to the block reward that the miner automatically receives for mining a block. By paying the rewards on the main chain and the bribes on the side chain from a separate double spend, the attacker only pays the rewards if the attack fails. However, if miners are purely profit-driven the attack should succeed because mining the side chain is just as profitable as mining the main chain if the attack fails and it is more profitable if the attack succeeds.

mskwik pointed out that the satoshi client doesn't propagate blocks that aren't on the longest chain so the attacking miners would need to be running a client that allowed them to share the side chain while they were attacking. cunicula agreed but didn't think it was safe to assume that miners would refuse to run a more profitable client.

Mike Hearn said that miners wouldn't take part in such an attack because the attack would destroy confidence in bitcoin, which is something they have a lot invested in either financially or ideologically. He also said that if double spends become too common, merchants would require identification and a reputation system would emerge to prevent them.

cunicula's preferred fix is requiring blocks to be signed by a sequence of randomly selected private keys. If signers refused to sign blocks containing double spends, then double spends could not occur.

The rest of the thread is a discussion of the separate issue of what will happen to bitcoin as the block reward drops to zero and what, if anything, should be done about it. While I think that is an important issue, I want to focus on the attack that cunicula proposed in his original post.
</recap>

Since I didn't find Mike Hearn's response particularly reassuring, I went looking for other reasons that the attack might not be as easy as cunicula's explanation makes it seem. I think I've found two things missing from cunicula's analysis.

First, the victim is a player as well, and has at least one potential counter-strategy. Once he sees the side-chain, he can bribe the miners to mine blocks on the main chain instead of the side-chain. He can even play the same type of strategy as the attacker, paying the block reward on the side-chain for blocks mined on the main chain, and paying a bribe on the main chain.

Second, any pool operator or solo miner in possession of a locked post-fork main chain block reward will lose that reward if the attack succeeds. These entities are collateral damage from the perspective of the attacker, but they have a financial interest in stopping the attack, perhaps even stronger than the victim of the double spend. They are players as well and can use the same counter strategy as the victim. Let's call these players plus the victim collectively defenders.

With these two additions, the dominant strategy for rational miners then becomes mining for whichever side (the attacker or the defenders) offers the largest bribe.

This leaves the attacker in a war of attrition game with the defenders. The first thing to note is that depending on how the defenders play this game, the attacker might lose or might need to pay more than the value of the double spend in order to win. This means that attacking is *not* a dominant strategy as cunicula suggested. Moreover, my understandating is that the symmetric Nash equilibrium for such a war of attrition game involves both sides paying the miners at least the amount that the losing side has at stake. As a result, even if the attacker managed to win the war of attrition using a Nash equilibrium strategy, the expected cost would make the attack unprofitable, so the attacker would still not attack to begin with.

Comments?