Defence against double spending, even 0-confirmation

[jevon]

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.

[DeathAndTaxes]

Interesting but likely impossible to implement.  Old node (not just miners) would be incompatible.   So it would require a 100% upgrade of every single node on the network to avoid disruptions.

[Revalin]

It is possible for people create non-fraudulent double-spends.  A common case: if they forgot to include a sufficient fee and the transaction goes into limbo, they can resend it with a fee.  Under this proposal there's a small chance they could lose the entire balance if a miner who considers the no-fee transaction to be valid and then mines them both.  Evil miners could even hoard such transactions hoping for the opportunity to confiscate a large fee.

Or another: they send a transaction while their LAN is disconnected from the network (another machine on their LAN sees it); they restore from backups; their restored client doesn't show the transaction so they resend it; when the LAN reconnects to the internet both transactions are transmitted and then confiscated.

[DeathAndTaxes]

It is possible for people create non-fraudulent double-spends.  A common case: if they forgot to include a sufficient fee and the transaction goes into limbo, they can resend it with a fee.  Under this proposal there's a small chance they could lose the entire balance if a miner who considers the no-fee transaction to be valid and then mines them both.  Evil miners could even hoard such transactions hoping for the opportunity to confiscate a large fee.

A potential solution for "limbo" tx in general is a kill or fill value.  If not included by block x, the tx is void.  Client default behavior could be to set kill value for 30 blocks into future for a tx (can be overriden by users).  Still the risk is minimal.  Tx only go into "limbo" if the user violates spam rules.  To do that requires using a custom client and willfully breaking protocol rules.

Or another: they send a transaction while their LAN is disconnected from the network (another machine on their LAN sees it); they restore from backups; their restored client doesn't show the transaction so they resend it; when the LAN reconnects to the internet both transactions are transmitted and then confiscated.

The restored node should see the tx from the other LAN node. 

So neither issues are killers but it does make the protocol more "fragile".  Things need to be done right or there is a risk of invalidating funds.

The larger issue is implementation.  A change like this would require not just miners upgrading but 100% of nodes to avoid a permenent fork.  Likely an impossible goal.  There are less drastic solutions to non 51% attack double spends (like tx contracts).  This change wouldn't affect 51% attacks or Finney attacks which are the more likely double spends.

[jevon]

It is possible for people create non-fraudulent double-spends.  A common case: if they forgot to include a sufficient fee and the transaction goes into limbo, they can resend it with a fee.  Under this proposal there's a small chance they could lose the entire balance if a miner who considers the no-fee transaction to be valid and then mines them both.  Evil miners could even hoard such transactions hoping for the opportunity to confiscate a large fee.

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.

[Revalin]

A potential solution for "limbo" tx in general is a kill or fill value.  If not included by block x tx is void.

I support this.  It's a good idea even outside double-spend-confiscation.

The restored node should see the tx from the other LAN node.

The node is not guaranteed to be on the same LAN after being restored.  for instance, a laptop may be carried over to the IT department for a restore.

Also: are unconfirmed txes actually stored and sent to new nodes after the initial flooding?  I seem to recall that if you're not on the net at the time of the initial broadcast you won't hear about it until you see it in a block.

[jevon]

Interesting but likely impossible to implement.  Old node (not just miners) would be incompatible.   So it would require a 100% upgrade of every single node on the network to avoid disruptions.

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

[DeathAndTaxes]

Interesting but likely impossible to implement.  Old node (not just miners) would be incompatible.   So it would require a 100% upgrade of every single node on the network to avoid disruptions.

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

I think you fail to understand how old some nodes are.  Even if programmed to start some years in the future a good chunk of the network would be incompatible.

[kjj]

It is possible for people create non-fraudulent double-spends.  A common case: if they forgot to include a sufficient fee and the transaction goes into limbo, they can resend it with a fee.  Under this proposal there's a small chance they could lose the entire balance if a miner who considers the no-fee transaction to be valid and then mines them both.  Evil miners could even hoard such transactions hoping for the opportunity to confiscate a large fee.

A potential solution for "limbo" tx in general is a kill or fill value.  If not included by block x, the tx is void.  Client default behavior could be to set kill value for 30 blocks into future for a tx (can be overriden by users).  Still the risk is minimal.  Tx only go into "limbo" if the user violates spam rules.  To do that requires using a custom client and willfully breaking protocol rules.

There is no x, and its absence is neither an accident nor an oversight.

[DeathAndTaxes]

Let me help you ...

"a POTENTIAL solution would be a kill or fill value".

Nobody except you claimed "x" exists.

[jevon]

Interesting but likely impossible to implement.  Old node (not just miners) would be incompatible.   So it would require a 100% upgrade of every single node on the network to avoid disruptions.

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.

[DeathAndTaxes]

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 still requires 100% of nodes to upgrade.  Existing nodes would see those outputs as valid.  Your modifications is less effective.  If either or both of tx have fees it would require miners to intentionally choose less fees as opposed to just including the tx with highers fees.

No miners is going to do that so the complexity and risk is for nothing.  Worse any miners that does (say both tx have no fees or they are a non-profit miner) will still leaving existing nodes vulnerable to deception from the "dead" outputs that the existing nodes don't see as dead.

[Meni Rosenfeld]

You are assuming that the miner and the double-spender are not the same person. I send payment to a merchant; I make a double-spend transaction and keep it to myself; I try to mine a block (using my own or rented hashrate) with both transactions. If I'm not the first to find a block I end up paying normally, but if I am, I get to keep the sent amount.

This exploit can be used in conjunction with the Finney attack (waiting until I have a block before sending payment).

Even if the idea has merit, it is a fundamental change to the design principles of Bitcoin.

A potential solution for "limbo" tx in general is a kill or fill value.  If not included by block x, the tx is void.

Theymos said (and I'm sure he didn't make that up) that it is impossible to make transactions that are only valid if included up to block x, because this is not invariant to reorgs. A transaction can be included and the receiver thinks his payment is secure, then there is a reorg where this transaction doesn't appear, and it can't be added to a new block because it's too late.

[DeathAndTaxes]

Theymos said (and I'm sure he didn't make that up) that it is impossible to make transactions that are only valid if included up to block x, because this is not invariant to reorgs. A transaction can be included and the receiver thinks his payment is secure, then there is a reorg where this transaction doesn't appear, and it can't be added to a new block because it's too late.

Wouldn't the risk be the same as any other tx.

i.e. if hypothetically the default option in client was to create tx w/ a void "x" 30 blocks in the future.  Under most scenarios that tx would be included in the next block (b: 1).  If the merchant then waits 6 confirms (b: 7) by the time the kill or fill passes (b:30) it would require a 30 block re-org to void that tx.  If someone is doing a 30 block re-org we likely are facing a massive and well planned 51% attack anyways.

Right?

This is mostly academic because I am under no illusions that such drastic changes to protocol will ever happen.  However Bitcoin may not be the crypto-currency that goes mainstream so it may be useful to some "real" alt-chain (all alts so far w/ exception of namecoin as worthless as they haven't attempted any improvements on Bitcoin).

[DeathAndTaxes]

You are assuming that the miner and the double-spender are not the same person. I send payment to a merchant; I make a double-spend transaction and keep it to myself; I try to mine a block (using my own or rented hashrate) with both transactions. If I'm not the first to find a block I end up paying normally, but if I am, I get to keep the sent amount.

That risk always exists. Thankfully the cost to have even 1% of the network is generally prohibitive as most 0-confirm tx would be low value or easily reversed.    Double spend fraud doesn't have to be 0% just lower than other payment systems.

[Pieter Wuille]

Interesting but likely impossible to implement.  Old node (not just miners) would be incompatible.   So it would require a 100% upgrade of every single node on the network to avoid disruptions.

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.

This is not correct. Old nodes will not accept a block whose coinbase has more than one, or non-empty inputs.

[jevon]

If either or both of tx have fees it would require miners to intentionally choose less fees as opposed to just including the tx with highers fees.

I updated it again so the miners get the entire amount eventually, and in the future get it immediately.

If you believe miners will take a double spend for a higher fee, then it's already completely unsafe to take 0-conf payments. Double spenders can bribe the miners at any time.

In fact, if miners can be bribed with fees, then the network falls apart without this change.

Send a 1000BTC payment. Wait 2 blocks. Double spend it with a 500BTC fee. All the miners switch to 2 blocks ago to get the 500BTC fee.

It doesn't have to be one payment. Pay 10BTC to 100 people. Wait two blocks, double spend them all with 5BTC fee.

leaving existing nodes vulnerable to deception from the "dead" outputs that the existing nodes don't see as dead.

That is true, but those will still stay permanently 0-conf, and it's already not safe at all to accept 0-conf. After the change, anyone who wants to safely accept 0-conf can upgrade. It's mostly merchants that want to accept 0-conf, and they generally keep up with the latest updates.

This is not correct. Old nodes will not accept a block whose coinbase has more than one, or non-empty inputs.

The scriptSig of a coinbase is a scratch area that is ignored that can be used for extension data.

[Pieter Wuille]

This is not correct. Old nodes will not accept a block whose coinbase has more than one, or non-empty inputs.

The scriptSig of a coinbase is a scratch area that is ignored that can be used for extension data.

I misread - I thought you wanted to include it as secondary inputs to the coinbase transaction. Still, the coinbase is limited to 100 bytes. It will be very hard to put two full transactions plus an extra output in there...

[jevon]

I misread - I thought you wanted to include it as secondary inputs to the coinbase transaction. Still, the coinbase is limited to 100 bytes. It will be very hard to put two full transactions plus an extra output in there...

Ooooh, you're right.

The extension data would have to be shoehorned in somewhere else, like an extra 0BTC output on the coinbase to a deadend scriptPubKey that contains the extension data in a push-drop. I think that would be about 15 bytes overhead, and only when there's a double spend to kill.

It is possible for people create non-fraudulent double-spends.  A common case: if they forgot to include a sufficient fee and the transaction goes into limbo, they can resend it with a fee.  Under this proposal there's a small chance they could lose the entire balance if a miner who considers the no-fee transaction to be valid and then mines them both.  Evil miners could even hoard such transactions hoping for the opportunity to confiscate a large fee.

To preserve this option, don't consider it a double spend if it goes to the same outputs.

Double spend = same input, different outputs.

[sebastian]

"Double spend = same input, different outputs."

You would still need to reconsider the changed tx fee. That would require you to change the amount of the "change" adress, and/or add new inputs and/or outputs to the transaction (if the too-low-fee transaction also included inputs with too low value to be able to increase the fee) so the new fee add up correctly in equation.

Its hard to check in a safe way. I think a tx expiration feature would be better then.