Double-spend prevention clarification

[BoardGameCoin]

So, I have a half-technical half-systematic question. As I understand it, bitcoin uses a cryptographic proof of work with a most-work-wins approach to double-spend resolution.

What are the implications of black-holing any double-spent coins? Obviously this would need to be transitive. And probably there would need to be some maximum time delta after which presenting a double-spend to the network would not cause coin destruction.

Thoughts? Clarifications where I just have the wrong idea?

-bgc

[1714967921]

1714967921

[1714967921]

1714967921

[1714967921]

1714967921

[TheBitcoinChemist]

And why do you think that there needs to be a built-in prevention mechanism?  The risks of a successful double spend are very low, and non-existant for anyone willing to wait for 6 confirmations.

[Stephen Gornick]

So, I have a half-technical half-systematic question. As I understand it, bitcoin uses a cryptographic proof of work with a most-work-wins approach to double-spend resolution.

Just to clarify, the blockchain (like a ledger) uses a proof of work in knowing which blocks are added to the chain.  That chain then holds the ledger which is used to ensure the coin has not previously been spent.    The "most-work-wins" refers to resolution when there are competing branches when there is fork in the blockchain.

So presumably you are considering this only for double spending where the spend in one branch of the fork contradicts the spend in another branch.

What are the implications of black-holing any double-spent coins?

The double spend in a competing branch could then be spent with an innocent party.  Your black-holing means bitcoins are no longer fungible. Innocents will be harmed.  That's bad.

Without a blockchain fork, there are a couple other double spend attacks as well:

Not all double spends attempts are intentional even.  Take the scenario where someone who imports their private key from a wallet.dat into Blockchain.info, for example, and then spends the one in blockchain.info.  Then the bitcoin-qt is launched but it hasn't caught up on the blockchain and a payment is sent, which happens to spend the coin that was transferred to blockchain.info.  That would be a double spend.  That can happen seconds apart or months apart.

[GenTarkin]

Without a blockchain fork, there are a couple other double spend attacks as well:

Not all double spends attempts are intentional even.  Take the scenario where someone who imports their private key from a wallet.dat into Blockchain.info, for example, and then spends the one in blockchain.info.  Then the bitcoin-qt is launched but it hasn't caught up on the blockchain and a payment is sent, which happens to spend the coin that was transferred to blockchain.info.  That would be a double spend.  That can happen seconds apart or months apart.

Thats very interesting. What does BTC do when this situation arises? Would the second tx not be allowed? .. even tho the double spend wallet hasnt caught up w/ its blockchain yet? The peers, I hope, having an updated chain when it announced the tx to the network will reject it .. because they have an updated block chain.

[TheBitcoinChemist]

Without a blockchain fork, there are a couple other double spend attacks as well:

Not all double spends attempts are intentional even.  Take the scenario where someone who imports their private key from a wallet.dat into Blockchain.info, for example, and then spends the one in blockchain.info.  Then the bitcoin-qt is launched but it hasn't caught up on the blockchain and a payment is sent, which happens to spend the coin that was transferred to blockchain.info.  That would be a double spend.  That can happen seconds apart or months apart.

Thats very interesting. What does BTC do when this situation arises? Would the second tx not be allowed? .. even tho the double spend wallet hasnt caught up w/ its blockchain yet? The peers, I hope, having an updated chain when it announced the tx to the network will reject it .. because they have an updated block chain.

The second would be considered invalid, and simply ignored by most peers & miners.  It wouldn't even propagate past a full client.

[gabbynot]

Has anyone successfully completed a double spend?

[notme]

Has anyone successfully completed a double spend?

No.  To do so would require having more hashing power than the entire remainder of the network.

[nimda]

However, someone might have completed a double-spend against a merchant accepting 0-conf transactions. Or even 1-conf; we've had longer races than that.

[DeathAndTaxes]

Has anyone successfully completed a double spend?

No.  To do so would require having more hashing power than the entire remainder of the network.

Not true.  That would be a 51% attack which could be used to execute an unlimited number of double spends (or halt all transactions).

There are other mechanisms to execute a double spend.  

0-confirm double spend - requires no hashing power but would require very good timing
Finney attack - a variation of the 0-confirm double spend where the attacker has a double spend in a block ready to submit to the network.
Re-org attack - an attacker with a significant % of the network hashing power (but less than 51%) could produce the longest chain and double spend for a limited period of time.


The first two are prevented by not delivering product until 1 confirmation.  The risk of re-org attack is significantly reduced by waiting for higher number of confirmations.    Satoshi provides analysis and simulations on this type of attack.  The "wait for 6 confirmations" is a rule of thumb based on the low probability that anyone with less than 51% of hashing power could re-org more than 6 blocks.

[notme]

Has anyone successfully completed a double spend?

No.  To do so would require having more hashing power than the entire remainder of the network.

Not true.  That would be a 51% attack which could be used to execute an unlimited number of double spends (or halt all transactions).

There are other mechanisms to execute a double spend.  

0-confirm double spend - requires no hashing power but would require very good timing
Finney attack - a variation of the 0-confirm double spend where the attacker has a double spend in a block ready to submit to the network.
Re-org attack - an attacker with a significant % of the network hashing power (but less than 51%) could produce the longest chain and double spend for a limited period of time.


The first two are prevented by not delivering product until 1 confirmation.  The risk of re-org attack is significantly reduced by waiting for higher number of confirmations.    Satoshi provides analysis and simulations on this type of attack.  The "wait for 6 confirmations" is a rule of thumb based on the low probability that anyone with less than 51% of hashing power could re-org more than 6 blocks.

Yep.

[TheBitcoinChemist]

The first two are prevented by not delivering product until 1 confirmation.  The risk of re-org attack is significantly reduced by waiting for higher number of confirmations.    Satoshi provides analysis and simulations on this type of attack.  The "wait for 6 confirmations" is a rule of thumb based on the low probability that anyone with less than 51% of hashing power could re-org more than 6 blocks.

The way I understood it, an attacker with only a simple majority could only prevent transactions from being included in new blocks by creating the blocks himself without transactions, but even that wouldn't be certain as every once in a while an honest miner is still going to get a lucky block in faster than a 1% advantage can deal with.  Also, that 1% advantage might (theorically) permit the attacker to reverse one previous block, if he's lucky, but blocks beyond that one require orders of magnitude more hashing power than all of the honest nodes combined.  The 6 was chosen specificly because it would take a rediculous multiple of the hashing power of the whole of the honest network.

An attacker with only 51% of the total hashing power could double-spend (or simply reverse) just confirmed transactions that he, himself, just spent; but still wouldn't be able to reverse the transactions of other peoples' bitcoins, only delay them from confirmations for as long as he could maintain the attack.  But even with 51% of the hashing power, 6 confirmations is safe.

[notme]

The first two are prevented by not delivering product until 1 confirmation.  The risk of re-org attack is significantly reduced by waiting for higher number of confirmations.    Satoshi provides analysis and simulations on this type of attack.  The "wait for 6 confirmations" is a rule of thumb based on the low probability that anyone with less than 51% of hashing power could re-org more than 6 blocks.

The way I understood it, an attacker with only a simple majority could only prevent transactions from being included in new blocks by creating the blocks himself without transactions, but even that wouldn't be certain as every once in a while an honest miner is still going to get a lucky block in faster than a 1% advantage can deal with.  Also, that 1% advantage might (theorically) permit the attacker to reverse one previous block, if he's lucky, but blocks beyond that one require orders of magnitude more hashing power than all of the honest nodes combined.  The 6 was chosen specificly because it would take a rediculous multiple of the hashing power of the whole of the honest network.

An attacker with only 51% of the total hashing power could double-spend (or simply reverse) just confirmed transactions that he, himself, just spent; but still wouldn't be able to reverse the transactions of other peoples' bitcoins, only delay them from confirmations for as long as he could maintain the attack.  But even with 51% of the hashing power, 6 confirmations is safe.

No.  He can hold back his blocks until he has 50 and the main chain has 49 from where he started.  Then he publishes his blocks and his chain is now the main chain.

[notme]

http://www.bitcoin.org/bitcoin.pdf

Section 11.

[nimda]

The attacker doing 1-tx blocks would simply not build off of "lucky" blocks which included transactions.

1 Attack-block
2 Attack-block which builds off of 1
3 lucky-guy publishes one here which builds off of 2
4 attack block building off of 2
5 attack-block building off of 4
block 3 is now orphaned

[BoardGameCoin]

So presumably you are considering this only for double spending where the spend in one branch of the fork contradicts the spend in another branch.

Yes, that's correct. It's a thought experiment about penalizing double-spends visible to the network in too-short a time frame by removing the coins from circulation. Roughly how it would work is right now, miners have to choose one of the double spend transactions to hash into their chain. I am proposing adding the ability to hash BOTH double spend transactions into the same chain with the net effect of making the coins disappear and for miners to prefer building off of blocks that black-hole double-spends. Innocents could be harmed, but attackers would have less incentive to Finney attack this way. I'm not sold on it, but I haven't been convinced its definitely a bad idea yet.

Not all double spends attempts are intentional even.  Take the scenario where someone who imports their private key from a wallet.dat into Blockchain.info, for example, and then spends the one in blockchain.info.  Then the bitcoin-qt is launched but it hasn't caught up on the blockchain and a payment is sent, which happens to spend the coin that was transferred to blockchain.info.  That would be a double spend.  That can happen seconds apart or months apart.

This is true, and is one of the potential drawbacks of the approach I'm considering. However, it already is possible to lose coins, and it seems to me that appropriate windowing (e.g. only possible for a miner to black-hole a transaction while there's less than 'x' blocks chained on top of it, where x is probably < 18) would address at least the 'months apart' instances of the unintentional case.

Your black-holing means bitcoins are no longer fungible. Innocents will be harmed.  That's bad.

It's true that this reduces fungibility, but it applies only to a situation where fungibility is already bent a bit (an attempted double spend). We already expect users to exercise due diligence with respect to private key management, and it seems to me that a similar notion of responsibility could hold in this hypothetical case.

Thanks for the serious response Stephen, I'm most grateful.

-bgc

[DeathAndTaxes]

An attacker with only 51% of the total hashing power could double-spend (or simply reverse) just confirmed transactions that he, himself, just spent; but still wouldn't be able to reverse the transactions of other peoples' bitcoins, only delay them from confirmations for as long as he could maintain the attack.  But even with 51% of the hashing power, 6 confirmations is safe.

As notme pointed out the attacker will always build off his attack chain.  With 51% of hashing power and enough time it is a mathematical certainty the attack chain will end up the longest.

Saotshi recommendations for x confirmations to be safe only apply for attackers with less than 51% of hashing power.  If an attacker has 51%+ then 6 confirmations isn't enough 106 isn't enough and given a patient enough attacker 10,006 confirmations isn't enough.

Confirmations provide security because they represent a given amount of hashing power if the attacker has the majority then no number can provide security.  You need some "non confirmation" method like checkpoints where the client will never re-org to earlier than the checkpoint no matter how much longer the attack chain is.

[TheBitcoinChemist]

The attacker doing 1-tx blocks would simply not build off of "lucky" blocks which included transactions.

1 Attack-block
2 Attack-block which builds off of 1
3 lucky-guy publishes one here which builds off of 2
4 attack block building off of 2
5 attack-block building off of 4
block 3 is now orphaned

What would happen if two lucky blocks in a row were found by honest nodes in less than the 10 minute average?  At that point, wouldn't the honest network be working on a new block 5 while the attacker is still trying to build a block 4 to attach to his alternate block 3?  Wouldn't then the chain split favor the honest network and put mr 51% on his ass for a round, forcing him to reset and restart his attack with honest block 5?

[DeathAndTaxes]

What would happen if two lucky blocks in a row were found by honest nodes in less than the 10 minute average?  At that point, wouldn't the honest network be working on a new block 5 while the attacker is still trying to build a block 4 to attach to his alternate block 3?  Wouldn't then the chain split favor the honest network and put mr 51% on his ass for a round, forcing him to reset and restart his attack with honest block 5?

No.

It would go like this:
1 Attack-block
2 Attack-block which builds off of 1
3 lucky-guy publishes one here which builds off of 2
4 lucky-guy #2 builds off #3
5 attack-block ignores 3 & 4 and builds off #2
6 attack-block ignores 3 & 4 and builds off #5
7 attack-block ignores 3 & 4 and builds off #6

attack chain is the longest & attacker broadcasts all blocks to the network.   
compliant nodes re-org to longest chain (attack #7)
double spend occurs.

The side with 51% of hashing power has a mathematical certainty to end up with the longest chain ... eventually.  Given enough time if an attacker has more than 50% of hashing power the probability he will have the longest chain approaches 100%.