I edited the first post. Now it only needs 51% of miner support, and old clients don't need to upgrade. Blocks are fully backward compatible.

It would have to be programmed to start at some block number several months in the future.

Instead, the recipient should spend the stuck transaction to himself with a higher fee to push it through. Miners have to include the first transaction to get the higher fee in the second one.

The sender can also do it by spending the change.

Here's an idea to take away the incentive to double spend. If a miner finds a double spend, it can put BOTH into the same block and the entire double spent amount goes to fee. Instead of up to ~50% chance of getting the money back, double spending would almost always fail and lose the money.

This would allow instant acceptance of 0-confirmation transactions for most uses that need it, like point-of-sale.

It's pretty easy to scan for conflicting inputs in a block. I'm not sure it would be necessary to flag or list them in a separate list.

Both transactions must go in the same block. If a double spend comes along after the first transaction is already in a block, it's too late.

This would only apply with a lockTime=0 spend. If you need to create multiple spends on purpose for some reason, use lockTime=1 or higher.

EDIT
New backward compatible version 2:

If a miner finds a double spend, it puts both spends into an extension data area in the block. The double spent inputs are marked as paying to this miner's scriptPubKey, but can't be spent until some future time when we decide enough old clients have upgraded. There's bound to eventually be a security issue that makes all old clients insecure and forced to upgrade.

So the entire double spent amount goes to the miner, eventually. In the future, it'll go to the miner immediately.

For transition, we only need to get above 51% of mining power following the new rule.

This is fully compatible with old clients. They continue to see double spends stay stuck at 0-confirmation.

Both old and new clients will benefit from the fact that double spending is as futile as sending your money to 1BitcoinEaterAddressDontSendf59kuE.

The extension data could be shoehorned in anywhere, like an extra 0BTC output on the coinbase to a deadend scriptPubKey that contains the extension data in a push-drop.

Gavin and blueadept are speculating that could happen in the future. This is all in reply to that concern that there will be dishonest miners that will take the transaction with the largest fee, even if it's wasn't first.

The concern was that a double spender could make his double spend (tx2) with a larger fee to bribe the miners.

In that case, merchants would respond by increasing the fee on tx1 (tx1->all fee) so the double spender won't be rewarded. Double spending would always fail to get any money back, so it would be deterred.

The point is, if there are dishonest miners that can be bribed with fee to take a double spend, then merchants would not sit by while they get ripped off by double spenders.

No, in this scenario the double spender is bribing miners with fee so he would always win. The merchant can play that game too and raise his fee too. Then the first spend has the highest fee and is again in the miner's best interest.

The first transaction is the one paying to the recipient (merchant). This is the recipient doing this action.

Recipient receives tx 1, paying to him.
Recipient receives tx 2, which is a double spend of tx 1 paying back to double spender.
Recipient spends tx 1 to all fee.

Including tx 1 to get to the all fee transaction after it is now worth more fee than tx 2.

Then instead make it in the miner's interest to stay with the first transaction:

When the client software receives a double-spend, display the first transaction as bad and immediately spend its entire amount to fee. It's in the miner's interest to include the first transaction in order to include the all-fee transaction after it.

Double spending is then pointless. You lose your money and still owe the merchant, and it's your fault for spoiling the payment with a double spend.

If the receiver is not online at the time, then he's not a double spending target because he's not even online to act on 0-confirmation transactions.

In the future, this is what any game theory understanding 0-confirmation accepting merchant will do to deter double spend fraud if there are any dishonest miners.

It's fine and good to require ascending fees for lockTime transactions, which are explicitly replaceable...

It would be terrible for final transactions! Final transactions are explicitly not supposed to be replaced. Replacement is fraudulent double-spending! Sure, some miners might cheat, but I think most would be honest for smaller POS sized payments. As long as at least some are honest, the double-spender has a substantial chance that the double-spend won't work and he'll end up paying, which breaks most theft cases because of the discount at fencing goods. Only if you throw in the towel and say miners should intentionally side with double-spenders will they have 100% chance of getting away without paying.

The whole point of the Bitcoin network is supposed to be to witness which transactions came first. Don't give up on that!

Either way will work. Just make sure they can't do this, like with 4 inputs:
0xfffffffe-0xfffffffe-0xfffffffe-0xfffffffe
0xfffffffe-0xfffffffe-0xfffffffe-0xffffffff
0xfffffffe-0xfffffffe-0xffffffff-0xffffffff
0xfffffffe-0xffffffff-0xffffffff-0xffffffff
0xffffffff-0xffffffff-0xffffffff-0xffffffff

Final replaces non-final is simple to implement, just add to the replacement conditions:
  if (!IsFinal())
      return false;

In other words, replacement is only allowed if you're replacing with this:
0xffffffff-0xffffffff-0xffffffff-0xffffffff

The only difference between this and blueadept's way is whether the lockTime transaction can get into the pool ahead of time, or they have to wait until lockTime to broadcast it (if they're still around by then).

Increasing the fee on each version is a perfect solution, except not doubling. It should increment by a constant predefined amount that is more than the maximum estimated cost of bandwidth and resources consumed by broadcasts. Then it's a user fee.

The inputs wouldn't have to change as long as there's a change return to reduce.

That would be a good temporary fix that would work in simple cases with only one nLockTime transaction, like an escrow expiration payment.

They shouldn't create multiple versions though, because if replacement is still disabled, then it's just a race at nLockTime to broadcast first and the version doesn't matter.

Another possible temporary fix would be to enable only a single replacement: final replaces non-final. That would allow a single lockTime transaction for expiration default, and is only one line of code without getting into all the issues. It's stupid that a lockTime transaction can sit in the pool and block a final transaction that trumps it.

I think there's a simpler way that only needs standard transactions and works with the network as-is. I wrote it up in a wiki article:
https://en.bitcoin.it/wiki/Nanopayments

In a nutshell... Bob makes a secret transaction. He tells Alice the hash is in a certain range and Alice tries to guess its hash. Her transaction depends on Bob's, so if she guesses wrong, her transaction is invalid for spending a nonexistent transaction.

Alice doesn't know it's successful until Bob broadcasts it, so Bob can use the element of surprise to grab the pool miners before she knows he's broadcasting.

Nanopayment receivers only need to communicate with other nanopayment receivers at the time to call dibs on coins for a minute or so. This could be accomplished with some simple hub servers. No need to involve the Bitcoin network. More details in the wiki article.

For some applications it may not matter because it would be too much trouble for users to exploit this loophole.

He has a last post detector, of course!

Hello

A standard transaction with two inputs and two outputs could do a secure swap.

  input 1: Alice   output 1: Bob (new address)
  input 2: Bob     output 2: Alice (new address)

Alice signs her input and Bob signs his. The transaction isn't valid until they both sign.

It would be more interesting with a larger group:

  input 1: user1     output 1: user3
  input 2: user2     output 2: user2
  input 3: user3     output 3: user6
  input 4: user4     output 4: user5
  input 5: user5     output 5: user1
  input 6: user6     output 6: user4

This is actually simple compared to the mind bending stuff in the wiki Contracts article:
https://en.bitcoin.it/wiki/Contracts

I've been reading that article, and it seems like there might be a way to swap using two separate transactions, without revealing they're related. If I figure that out I'll post.

Decades from now, if Bitcoin hasn't caught on enough by then to have significant transaction fee volume to replace the dwindling block rewards, it's never going to catch on.

Might be a sign of some miners trying to shun the blank blocks.