Solving the fast payments problem

[BubbleBoy]

I started this as a reply to the "zero-confirmation is not safe" thread, but i believe it warrants it's own thread.

Therefore, we are adapting ourselves (and letting others adapt) to a false reality by designing systems with an assumption that there is some security in zero-conf transactions.  I'd much rather just write it off completely, and let businesses and users adapt to the idea that zero-conf transactions are basically useless for exchanges between untrusted parties.  Forget it.  If you don't trust the person, don't mess with zero-confirmation transactions.  Period.

This is generally a solid design principle: when something is to break, you should make the failure visible and document it clearly so the user understands this is not the intended use of the software.

However, in this particular case zero confirmation can be fixed so they are almost as secure as 1-confirmation payments with minimal tweaks to the client rules, a much more worthy goal than breaking them completely.

Tweak 1. Don't silently discard double spend transactions. Forward them along to other peers, marked as double spends^(*. This is essentially the same solution as in the Two bitcoins for the price of one paper. They suggest hijacking the Bitcoin "alert" for this purpose, but I think the marking need not be explicit: you just need to always prefix the doublespend with the first spend when forwarding along to other peers, implicitly communicating the correct order. So if they haven't seen any of the transactions yet, they will inherit the same order as you, just as it happens today.

This kills in the bud all race attacks, where the merchant is unaware that a fraction of the miners have received and are actively extending a double spend. After you received the first zero-conf transaction, you listen 10 seconds for another txn attempting a double spend and if none is received you have a very high certainty that all honest miners have received that transaction and are actively mining it. The propagation time is on the order of 3 seconds so if the attacker sends the 2nd spend after 10 seconds the probability it would reach any miner first is zero.

So we are down to a Finney attack. (or an involuntary Finney where the attacker interferes with a miner's network connectivity so as to present it a different spend order)

Tweak 2. Don't obliviously extend blocks containing a double spend. When selecting the longest subchain to extend, blocks containing a known double spend should be assigned a zero or negative difficulty. All other things being equal, a miner would chose to extend a 2 blocks subchain rather than a 3 block subchain the first of which contains what he can recognize as a double spend.

This will not fork the chain: if what we believe to be the double-spend subchain grows faster than our original choice, at some point we will concede that we were wrong and the network has a different view of what was the legitimate spend, so convergence will eventually be reached. The "some point" where this happens is determined by the negative difficulty we assign the double spend block. A small negative value will allow the work from the Finney attack block to simply be ignored by the majority of honest nodes, making the attack very costly in terms of resources and BTC potentially lost. ^(**

It's also stable in the Byzantine-Altruistic-Rational paradigm: if we are confident on our determination regarding what is the legitimate spend, then we are confident most other miners have the same idea because of tweak 1. Thus it's rational for us not to extend the block containing the double spend, due to the negative difficulty impact it would have on our work for the point of view of most other miners. When enough miners are altruistic and implement Tweak 2, it becomes irrational not to implement it and a rational majority will maintain the status quo.

Together, tweaks 1 and 2 rise the bar immensely for zero-confirmation attacks,. When 10 seconds have passed since the initial broadcast, we are fairly certain the vast majority of miners are on our side and will actively fight a Finney attack because it's profitable for them to do so. When the attacker gets the merchandise from the store and broadcasts it's Finney block, all nodes learn about the double spend within it and rationally chose not to extend it (they should also carve out the 2nd spend from the Finney block and broadcast it, so the merchant learns about what just happened).

To surpass the penalty, in the small negative penalty scenario, the attacker needs to mine two blocks, the first of which is the Finney block. The probability for this to happen is  on the order of (his ratio of hash power)^2, forcing him to do many double spends at the same time to have any chance of recovering the costs. So any vending machine could accept the zero confirmation payment with no risk and no need for observers or bribing miners to get on their side.

*) Naive implementation could open a potential denial of service, a rogue node sending over and over double spends of the same transaction. So you need to forward just one 2nd spend, not any of the following. The merchant needs to know that a double spend is in progress, not it's details, so races among 2nd, 3rd... spends are irrelevant. If any of the racing doublespends arrive at him, he fails the sale and holds the merchandise.

**) What about a large negative penalty, worth one or more blocks average difficulty ? It would make double spends attacks even harder requiring private mining of 3 or more chained blocks; but at some point reorgs are slower and deeper with many orphans, negating the benefits.

[im3w1l]

I like this proposal.

[TierNolan]

This kills in the bud all race attacks, where the merchant is unaware that a fraction of the miners have received and are actively extending a double spend.

You still need some way to define which one is correct.  Presumably, the merchant asks the customer to take a seat and wait for 6 confirms of the original transaction.

All nodes on the network would have both transactions, but may not agree which is first.

Tweak 2. Don't obliviously extend blocks containing a double spend. When selecting the longest subchain to extend, blocks containing a known double spend should be assigned a zero or negative difficulty. All other things being equal, a miner would chose to extend a 2 blocks subchain rather than a 3 block subchain the first of which contains what he can recognize as a double spend.

I assume you mean don't extend a block which the 2nd transaction from a double spend?

I made a suggestion in another thread for having a sub-chain.  If that rule applied to the sub-chain, then it would allow consensus on which was the first transaction of the double spend faster.

**) What about a large negative penalty, worth one or more blocks average difficulty ? It would make double spends attacks even harder requiring private mining of 3 or more chained blocks; but at some point reorgs are slower and deeper with many orphans, negating the benefits.

That seems unfair to miners who included the transaction in good faith.  On the other hand, it creates an incentive for the miner to have maximum connectivity.

[BubbleBoy]

You still need some way to define which one is correct.  Presumably, the merchant asks the customer to take a seat and wait for 6 confirms of the original transaction.

No. If both transaction arrive while the customer is at the checkout, it's cryptographic and legal proof he (or his software/hardware) attempted a double spend. You simply don't deliver the goods. It's irrelevant if you still get the attacker's money; he needs to explain to the police how he attempted to hack the store, failed, and now they won't give him his money back.

All nodes on the network would have both transactions, but may not agree which is first.

Of course, but what Tweak 1 ensures is that the merchant simply knows there are two competing transactions during the listen period. If a second one does not appear in 10 seconds on the wire, he's fairly certain all honest nodes agree with him on which is the first transaction, even if the double spend should later arrive.

The current rules make it that if the merchant's neighbors hear the first transaction, they will never forward the double spend to him, while in other parts of the network the double spend transaction is really the first and the legitimate transaction does not propagate. A dangerous race is going on about which the merchant has no idea. He needs to pay observers with thousands of peer connections to watch the network and report back anything suspicious.

Tweak 2. Don't obliviously extend blocks containing a double spend. When selecting the longest subchain to extend, blocks containing a known double spend should be assigned a zero or negative difficulty. All other things being equal, a miner would chose to extend a 2 blocks subchain rather than a 3 block subchain the first of which contains what he can recognize as a double spend.

I assume you mean don't extend a block which the 2nd transaction from a double spend?

Not forever, that would fork the chain after a double spend race. Just slightly penalize the chain that you believe contains a double spend. And if everybody does it, it's rational for you to do it too, even if you are not sure how many other miners share your oppinion on which is the double spend. This is what I mean by saying the strategy is stable in the Byzantine-Altruistic-Rational sense.

**) What about a large negative penalty, worth one or more blocks average difficulty ? It would make double spends attacks even harder requiring private mining of 3 or more chained blocks; but at some point reorgs are slower and deeper with many orphans, negating the benefits.

That seems unfair to miners who included the transaction in good faith.  On the other hand, it creates an incentive for the miner to have maximum connectivity.

Exactly. If you have connection problems and extend the doublespend because you haven't heard about the first spend, then you will penalized by the altruistic nodes who are have good connectivity for the sake of the network. So it makes sense for you to have good connectivity, at least to the point that you can receive two transactions broadcasted 10 seconds apart in the correct order they were broadcasted. If the attacker shortens this delay, he's risking detection at the point of sale.

[Zeilap]

Seems like a nice way to artificially reduce the network hashing rate / temporarily split the network.
I use a number of nodes to send 2 transactions spending the same input to the network, but I make sure to send them as close as possible to the same time. Thus, the rest of the network see that there is a double spend, but there isn't a strong consensus as to which order the transactions arrived, so half the network mine a fork with one transaction and the other half mine a fork with the other. At some point in the future, one side decides it must have been wrong and one of the forks wins. Up until that time, each fork has been competing possibly with many reorgs.

That's for a single double spend. Now think about a collection of nodes which continuously pump out double spends. Each split halves the hashing power if perfectly timed, it doesn't take much to bring the network to its knees.

[Anon136]

what incentive does the individual node have to rebroadcast suspected double spends? it seems like your proposal would rely on some amount of altruism. assuming it doesn't require too much altruism it will probably work, after all people seed torrents.

correct me if im wrong though is there a way to create incentives for nodes to rebroadcast this information?

[Anon136]

Seems like a nice way to artificially reduce the network hashing rate / temporarily split the network.
I use a number of nodes to send 2 transactions spending the same input to the network, but I make sure to send them as close as possible to the same time. Thus, the rest of the network see that there is a double spend, but there isn't a strong consensus as to which order the transactions arrived, so half the network mine a fork with one transaction and the other half mine a fork with the other. At some point in the future, one side decides it must have been wrong and one of the forks wins. Up until that time, each fork has been competing possibly with many reorgs.

That's for a single double spend. Now think about a collection of nodes which continuously pump out double spends. Each split halves the hashing power if perfectly timed, it doesn't take much to bring the network to its knees.

mb but thats no good to the attacker since the merchant would be forwarded this information as well and he would know to put the transaction on hold until after 6 confirmations.

[Rodyland]

Seems like a nice way to artificially reduce the network hashing rate / temporarily split the network.
I use a number of nodes to send 2 transactions spending the same input to the network, but I make sure to send them as close as possible to the same time. Thus, the rest of the network see that there is a double spend, but there isn't a strong consensus as to which order the transactions arrived, so half the network mine a fork with one transaction and the other half mine a fork with the other. At some point in the future, one side decides it must have been wrong and one of the forks wins. Up until that time, each fork has been competing possibly with many reorgs.

That's for a single double spend. Now think about a collection of nodes which continuously pump out double spends. Each split halves the hashing power if perfectly timed, it doesn't take much to bring the network to its knees.

mb but thats no good to the attacker since the merchant would be forwarded this information as well and he would know to put the transaction on hold until after 6 confirmations.

Maybe the point Zeilap's trying to make is that a double-spend, which forks the network, effectively halves the hashing power of the network, making it more susceptible to attack?

What I'm unsure about, Zeilap, is how your description differs from the status quo?

[TierNolan]

what incentive does the individual node have to rebroadcast suspected double spends? it seems like your proposal would rely on some amount of altruism. assuming it doesn't require too much altruism it will probably work, after all people seed torrents.

This is actually an issue with the protocol in general.  There is no reason for nodes to forward anything.

Arguably, nodes should be able to direct some of the fee to themselves when they forward.  The miner would take the transaction from the relay which took a smaller fee.

[Anon136]

what incentive does the individual node have to rebroadcast suspected double spends? it seems like your proposal would rely on some amount of altruism. assuming it doesn't require too much altruism it will probably work, after all people seed torrents.

This is actually an issue with the protocol in general.  There is no reason for nodes to forward anything.

Arguably, nodes should be able to direct some of the fee to themselves when they forward.  The miner would take the transaction from the relay which took a smaller fee.

interesting. A problem that is clearly a problem on paper but in the real world is not.

[TierNolan]

interesting. A problem that is clearly a problem on paper but in the real world is not.

Right.  People will be altruistic if it costs them very little.  The cost to update the client to not forward transactions it to much effort.

[Anon136]

interesting. A problem that is clearly a problem on paper but in the real world is not.

Right.  People will be altruistic if it costs them very little.  The cost to update the client to not forward transactions it to much effort.

if the devs made this change people would accept it. I hope Gavin takes notice because i think its a very good idea.

[im3w1l]

Seems like a nice way to artificially reduce the network hashing rate / temporarily split the network.
I use a number of nodes to send 2 transactions spending the same input to the network, but I make sure to send them as close as possible to the same time. Thus, the rest of the network see that there is a double spend, but there isn't a strong consensus as to which order the transactions arrived, so half the network mine a fork with one transaction and the other half mine a fork with the other. At some point in the future, one side decides it must have been wrong and one of the forks wins. Up until that time, each fork has been competing possibly with many reorgs.

That's for a single double spend. Now think about a collection of nodes which continuously pump out double spends. Each split halves the hashing power if perfectly timed, it doesn't take much to bring the network to its knees.

Nice attack, but it can be protected against.
If 2xspend are close together ( <10s), try to mine a block with the earlier transaction. Do not penalize chain choosing the later transaction
If 2xspend are sent far apart ( >10s) try to mine a block with the earlier transaction. Penalize chains incorporating the later transaction.

Now if they are sent close together the network will not split, but the fraud will be detected in time. If they are sent far apart, all nodes will try to favor the earlier tx. If you try to send some nodes <10s and some > 10s, then they will all be able to get the earlier tx before the later, since it will have time to propagate. Hence this will not split the network either.

[TierNolan]

if the devs made this change people would accept it. I hope Gavin takes notice because i think its a very good idea.

You could propose it as a BIP?

[Stephen Gornick]

*) Naive implementation could open a potential denial of service, a rogue node sending over and over double spends of the same transaction. So you need to forward just one 2nd spend, not any of the following. The merchant needs to know that a double spend is in progress, not it's details, so races among 2nd, 3rd... spends are irrelevant. If any of the racing doublespends arrive at him, he fails the sale and holds the merchandise.0

Your node's memory pool has a transaction with inputs A and B.  Then received is another transaction with inputs A and C.  
So your node prefixes this second transaction with the first and relays this pair.

Then to another node the attacker has the transaction with inputs A and D.  
Your node will not relay that but other nodes that haven't learned of the transaction with A and C will.

At the same time the attacker relays a transaction with just an input D.

Your node learns about the transaction with D and relays it.

So, some nodes then have the transactions [A+B], [A+C], and [D]  but will never know about [A+D].    If a merchant relies on this node and accepts [D], that merchant loses if [A-D] gets included in a block.

So this doesn't really eliminate the risk, it just makes the attack a little more complex.  

[Fry]

Seems like a nice way to artificially reduce the network hashing rate / temporarily split the network.
I use a number of nodes to send 2 transactions spending the same input to the network, but I make sure to send them as close as possible to the same time. Thus, the rest of the network see that there is a double spend, but there isn't a strong consensus as to which order the transactions arrived, so half the network mine a fork with one transaction and the other half mine a fork with the other. At some point in the future, one side decides it must have been wrong and one of the forks wins. Up until that time, each fork has been competing possibly with many reorgs.

That's for a single double spend. Now think about a collection of nodes which continuously pump out double spends. Each split halves the hashing power if perfectly timed, it doesn't take much to bring the network to its knees.

Nice attack, but it can be protected against.
If 2xspend are close together ( <10s), try to mine a block with the earlier transaction. Do not penalize chain choosing the later transaction
If 2xspend are sent far apart ( >10s) try to mine a block with the earlier transaction. Penalize chains incorporating the later transaction.

Now if they are sent close together the network will not split, but the fraud will be detected in time. If they are sent far apart, all nodes will try to favor the earlier tx. If you try to send some nodes <10s and some > 10s, then they will all be able to get the earlier tx before the later, since it will have time to propagate. Hence this will not split the network either.

Your Proposal does not protect against that attack.
What if i sent the second Transaction after a specific time, so that it reaches half of the Network <10s appart from the first Transaction and the other half of the Network >10s appart from the first Transaction?

[Anon136]

Seems like a nice way to artificially reduce the network hashing rate / temporarily split the network.
I use a number of nodes to send 2 transactions spending the same input to the network, but I make sure to send them as close as possible to the same time. Thus, the rest of the network see that there is a double spend, but there isn't a strong consensus as to which order the transactions arrived, so half the network mine a fork with one transaction and the other half mine a fork with the other. At some point in the future, one side decides it must have been wrong and one of the forks wins. Up until that time, each fork has been competing possibly with many reorgs.

That's for a single double spend. Now think about a collection of nodes which continuously pump out double spends. Each split halves the hashing power if perfectly timed, it doesn't take much to bring the network to its knees.

Nice attack, but it can be protected against.
If 2xspend are close together ( <10s), try to mine a block with the earlier transaction. Do not penalize chain choosing the later transaction
If 2xspend are sent far apart ( >10s) try to mine a block with the earlier transaction. Penalize chains incorporating the later transaction.

Now if they are sent close together the network will not split, but the fraud will be detected in time. If they are sent far apart, all nodes will try to favor the earlier tx. If you try to send some nodes <10s and some > 10s, then they will all be able to get the earlier tx before the later, since it will have time to propagate. Hence this will not split the network either.

Your Proposal does not protect against that attack.
What if i sent the second Transaction after a specific time, so that it reaches half of the Network <10s appart from the first Transaction and the other half of the Network >10s appart from the first Transaction?

as was mentioned earlier in the thread, the merchant would be notified of the conflicting transaction because the conflict would be forwarded through nodes. After being notified of the conflict the merchant could politely ask the customer to wait for a couple of confirmations.

[im3w1l]

Seems like a nice way to artificially reduce the network hashing rate / temporarily split the network.
I use a number of nodes to send 2 transactions spending the same input to the network, but I make sure to send them as close as possible to the same time. Thus, the rest of the network see that there is a double spend, but there isn't a strong consensus as to which order the transactions arrived, so half the network mine a fork with one transaction and the other half mine a fork with the other. At some point in the future, one side decides it must have been wrong and one of the forks wins. Up until that time, each fork has been competing possibly with many reorgs.

That's for a single double spend. Now think about a collection of nodes which continuously pump out double spends. Each split halves the hashing power if perfectly timed, it doesn't take much to bring the network to its knees.

Nice attack, but it can be protected against.
If 2xspend are close together ( <10s), try to mine a block with the earlier transaction. Do not penalize chain choosing the later transaction
If 2xspend are sent far apart ( >10s) try to mine a block with the earlier transaction. Penalize chains incorporating the later transaction.

Now if they are sent close together the network will not split, but the fraud will be detected in time. If they are sent far apart, all nodes will try to favor the earlier tx. If you try to send some nodes <10s and some > 10s, then they will all be able to get the earlier tx before the later, since it will have time to propagate. Hence this will not split the network either.

Your Proposal does not protect against that attack.
What if i sent the second Transaction after a specific time, so that it reaches half of the Network <10s appart from the first Transaction and the other half of the Network >10s appart from the first Transaction?

It does. Maybe I didn't explained it clearly. Lets look at what happens

Attack goes like
T=0   Transaction 1 sent to Miner group A
T=2   Transaction 1 sent to Miner group B
T=11 Transaction 2 sent to everyone

What will also happen
T=6 (ok I am just guessing the this happens. Important thing is that it should be < T=11)  Miner group group A forwards to group B

Since at T= 11 everyone will have heard about Transaction 1, it will be the one included.

[Dabs]

So, if merchants are not willing to wait 1 block or 10 minutes, if they wait for 30 to 60 seconds (1 minute) before doing anything, and if nothing is happening, then they can effectively accept zero confirmations. Isn't that much better? No, it's not instant, but maybe it can be considered "near instant".

10 seconds might be cutting it too close.

Then again, if there is a hard fork, 12 blocks or 2 hours is too short a time to accept a transaction.

I guess it really depends on the amount of coins we're talking about. A cup of coffee (as the usual example) can wait 1 minute before it is served.

[Fry]

Seems like a nice way to artificially reduce the network hashing rate / temporarily split the network.
I use a number of nodes to send 2 transactions spending the same input to the network, but I make sure to send them as close as possible to the same time. Thus, the rest of the network see that there is a double spend, but there isn't a strong consensus as to which order the transactions arrived, so half the network mine a fork with one transaction and the other half mine a fork with the other. At some point in the future, one side decides it must have been wrong and one of the forks wins. Up until that time, each fork has been competing possibly with many reorgs.

That's for a single double spend. Now think about a collection of nodes which continuously pump out double spends. Each split halves the hashing power if perfectly timed, it doesn't take much to bring the network to its knees.

Nice attack, but it can be protected against.
If 2xspend are close together ( <10s), try to mine a block with the earlier transaction. Do not penalize chain choosing the later transaction
If 2xspend are sent far apart ( >10s) try to mine a block with the earlier transaction. Penalize chains incorporating the later transaction.

Now if they are sent close together the network will not split, but the fraud will be detected in time. If they are sent far apart, all nodes will try to favor the earlier tx. If you try to send some nodes <10s and some > 10s, then they will all be able to get the earlier tx before the later, since it will have time to propagate. Hence this will not split the network either.

Your Proposal does not protect against that attack.
What if i sent the second Transaction after a specific time, so that it reaches half of the Network <10s appart from the first Transaction and the other half of the Network >10s appart from the first Transaction?

as was mentioned earlier in the thread, the merchant would be notified of the conflicting transaction because the conflict would be forwarded through nodes. After being notified of the conflict the merchant could politely ask the customer to wait for a couple of confirmations.

Your proposal would make instant Transactions safe. Thats not the point.
The point is that the network would not be safe against denial off service attacks any more.
The question is what happens if someone creates intentionally double spends, not to cheat someone else, but to fork the chain.

[Fry]

Seems like a nice way to artificially reduce the network hashing rate / temporarily split the network.
I use a number of nodes to send 2 transactions spending the same input to the network, but I make sure to send them as close as possible to the same time. Thus, the rest of the network see that there is a double spend, but there isn't a strong consensus as to which order the transactions arrived, so half the network mine a fork with one transaction and the other half mine a fork with the other. At some point in the future, one side decides it must have been wrong and one of the forks wins. Up until that time, each fork has been competing possibly with many reorgs.

That's for a single double spend. Now think about a collection of nodes which continuously pump out double spends. Each split halves the hashing power if perfectly timed, it doesn't take much to bring the network to its knees.

Nice attack, but it can be protected against.
If 2xspend are close together ( <10s), try to mine a block with the earlier transaction. Do not penalize chain choosing the later transaction
If 2xspend are sent far apart ( >10s) try to mine a block with the earlier transaction. Penalize chains incorporating the later transaction.

Now if they are sent close together the network will not split, but the fraud will be detected in time. If they are sent far apart, all nodes will try to favor the earlier tx. If you try to send some nodes <10s and some > 10s, then they will all be able to get the earlier tx before the later, since it will have time to propagate. Hence this will not split the network either.

Your Proposal does not protect against that attack.
What if i sent the second Transaction after a specific time, so that it reaches half of the Network <10s appart from the first Transaction and the other half of the Network >10s appart from the first Transaction?

It does. Maybe I didn't explained it clearly. Lets look at what happens

Attack goes like
T=0   Transaction 1 sent to Miner group A
T=2   Transaction 1 sent to Miner group B
T=11 Transaction 2 sent to everyone

What will also happen
T=6 (ok I am just guessing the this happens. Important thing is that it should be < T=11)  Miner group group A forwards to group B

Since at T= 11 everyone will have heard about Transaction 1, it will be the one included.

Ok, thats right.
Assuming that after 10 Seconds the Transaction has reached every node on the network, the chain will not split if the attacker has only sent these two Transactions.
But what happens if the Attacker Mines a Block at T=12 that contains Transaction 2?
In this case Miner group A will not accept this Block, but Miner group B will continue on the Block and the chain will Fork.
If both Mining Groups have the same Hashing power the fork can last for a longer Time.

[jgarzik]

You can never be guaranteed a notification of a double spend.

The classic example is where you broadcast transaction A, and then quietly mine transaction B.

Nobody sees B until it appears in a block.

[phelix]

[...]
Tweak 1. Don't silently discard double spend transactions. Forward them along to other peers, marked as double spends^(*. This is essentially the same solution as in the Two bitcoins for the price of one paper. They suggest hijacking the Bitcoin "alert" for this purpose, but I think the marking need not be explicit: you just need to always prefix the doublespend with the first spend when forwarding along to other peers, implicitly communicating the correct order. So if they haven't seen any of the transactions yet, they will inherit the same order as you, just as it happens today.
[...]

Something like this has been suggested a while ago. But how does it help with the problem at hand? A pool can still replace the first tx if the second tx has a higher fee.

[BubbleBoy]

You can never be guaranteed a notification of a double spend.

The classic example is where you broadcast transaction A, and then quietly mine transaction B.

This is the point of the Tweak 1, guaranteed notification. You either get:
 - instant (<10s) notification that a race has happened and the state of the network is undetermined, so you can fail payment
 - delayed (>10s) notification that a double spend was attempted, but the state of the network is in your advantage
 - delayed notification (minutes) that a double spend was attempted when the Finney block is broadcast

So the attacker is forced to go Finney, raising the bar for the attack. It's not about absolute security, it's about opportunity cost and making instant transactions "safe enough" for a Bitcoin vending machine. Now they are not because race attacks are trivial without Finney.

Something like this has been suggested a while ago. But how does it help with the problem at hand? A pool can still replace the first tx if the second tx has a higher fee.

It helps with altruistic pools and miners, who will respect the wire order. For rational, profit maximizing miners we need to create incentives as in Tweak 2.

[BubbleBoy]

Seems like a nice way to artificially reduce the network hashing rate / temporarily split the network.
I use a number of nodes to send 2 transactions spending the same input to the network, but I make sure to send them as close as possible to the same time. Thus, the rest of the network see that there is a double spend, but there isn't a strong consensus as to which order the transactions arrived, so half the network mine a fork with one transaction and the other half mine a fork with the other. At some point in the future, one side decides it must have been wrong and one of the forks wins. Up until that time, each fork has been competing possibly with many reorgs.

That's for a single double spend. Now think about a collection of nodes which continuously pump out double spends. Each split halves the hashing power if perfectly timed, it doesn't take much to bring the network to its knees.

Great attack. One solution, as others have suggested, is to make the penalty time dependent. You apply no penalty when the race took a few seconds, than gradually diminish the Finney block's difficulty for higher delays as you are more and more sure most of the network agrees with your order. So rapid double spends will not halve the hashing rate (but will be detected at the store) while delayed broadcasts will shave <1% of the hashing power (the poorest connected miners, who will tend to be the same regardless on where you inject subsequent double spends).

This makes sense from a rationality perspective: it's irrational to extend a shorter chain if you don't know the ratio of altruistic nodes that share your view. For higher broadcast delays, when are you are sure altruistic nodes have detected the correct order, it's profitable for you to follow their penalty scheme, for fear they will tend not to extend your work otherwise.

But what happens if the Attacker Mines a Block at T=12 that contains Transaction 2?
In this case Miner group A will not accept this Block, but Miner group B will continue on the Block and the chain will Fork.
If both Mining Groups have the same Hashing power the fork can last for a longer Time.

It's not a good solution to put a discrete limit, like 10 seconds, after which penalty jumps, because you invite races against that limit.  I propose a gradual penalty proportional with the delay. So that your scenario reduces to the classic Finney attack with a slight dispersion in penalty across the network, not enough to split the hashing power but enough to incentivize miners you not to attempt it and thus increase the cost of zero-conf double spends.

The correct Penalty[delay] function to achieve this needs to be experimentally or mathematically explored, as well as the resulting zero-confirmation payment you can "safely" accept. It's more than a tweak tho, it's a major modification to the blockchain extension rules...

[BubbleBoy]

So, some nodes then have the transactions [A+B], [A+C], and [D]  but will never know about [A+D].    If a merchant relies on this node and accepts [D], that merchant loses if [A-D] gets included in a block.

So this doesn't really eliminate the risk, it just makes the attack a little more complex.  

Ok, so my implementation was naive too. The object here is to avoid opening a new DDoS avenue other than multiple small transactions each with it's own fee, which is already possible. Without putting to much thought in it it seems possible to make at least one alert reach the merchant without flooding everybody with double spends. How about forwarding whenever, from our perspective, a new input is used ?

[solex]

The OP makes a good suggestion about double-spends. This is a passive variation:

A wait time of ten seconds is more than acceptable for most point-of-sale situations. So, without changing the way transactions are included in blocks, it seems that the principle of simply forwarding double-spends. marked as such, for informational purposes is very helpful to merchants. The time limit for forwarding could decay faster for transactions on a scale, as their values decrease by orders of magnitude of coin_dust.

[TierNolan]

How about forwarding whenever, from our perspective, a new input is used ?

Sounds good, it means that there is notice of TXO double spends.

On the sliding scale, block creation is pretty much integer based.  A block that is worth 0.99 more is the same as one that is worth 0.01 more.

What about adjusting the difficulty target.  The difficulty target for a block containing a double spent transaction to be accepted would be e ^ (time delay / delay constant) in blocks.

If the delay constant was 10 seconds, the value of a block for a given time difference in seconds would be

0: 1.0X
1: 1.12X
5: 1.65X
10: 2.72X

If the block is built on, then the difficulty drops back to the normal amount.

The safest thing for miners is to just exclude both transactions.  Then they suffer no penalty at all, no matter which one was first.

[Impaler]

Looks interesting.  What effect would limiting each address to just 1 transaction per block have?  If the node detects in its transaction pool 2 transactions originating from the same address they are both simply voided and never get put into a block.  Thus it's impossible to double spend and its not necessary to examine the balance of the address and no disagreement between nodes as to what the next block should contain and no forking.  If due to a failure of transaction propagation a node has only one of the two and thus included it in a successful block the other nodes will accept this because their is no double spend, the next block will catch the overdraft as normal.

[phelix]

related threads:
https://bitcointalk.org/index.php?topic=3168
https://bitcointalk.org/index.php?topic=54746
https://bitcointalk.org/index.php?topic=81844

Tweak 1) is mostly a comfort thing as you can achieve pretty much the same by listening to a lot of nodes.

Tweak 2) What you are suggesting is quite far from the main Bitcoin paradigm of the chain with the most hash power put into it being always right. Interesting to think about, though.

It all boils down to motivating miners to process incoming tx in the correct order - either using a technical solution or if it can not be done a political one.

[Anon136]

Seems like a nice way to artificially reduce the network hashing rate / temporarily split the network.
I use a number of nodes to send 2 transactions spending the same input to the network, but I make sure to send them as close as possible to the same time. Thus, the rest of the network see that there is a double spend, but there isn't a strong consensus as to which order the transactions arrived, so half the network mine a fork with one transaction and the other half mine a fork with the other. At some point in the future, one side decides it must have been wrong and one of the forks wins. Up until that time, each fork has been competing possibly with many reorgs.

That's for a single double spend. Now think about a collection of nodes which continuously pump out double spends. Each split halves the hashing power if perfectly timed, it doesn't take much to bring the network to its knees.

Nice attack, but it can be protected against.
If 2xspend are close together ( <10s), try to mine a block with the earlier transaction. Do not penalize chain choosing the later transaction
If 2xspend are sent far apart ( >10s) try to mine a block with the earlier transaction. Penalize chains incorporating the later transaction.

Now if they are sent close together the network will not split, but the fraud will be detected in time. If they are sent far apart, all nodes will try to favor the earlier tx. If you try to send some nodes <10s and some > 10s, then they will all be able to get the earlier tx before the later, since it will have time to propagate. Hence this will not split the network either.

Your Proposal does not protect against that attack.
What if i sent the second Transaction after a specific time, so that it reaches half of the Network <10s appart from the first Transaction and the other half of the Network >10s appart from the first Transaction?

as was mentioned earlier in the thread, the merchant would be notified of the conflicting transaction because the conflict would be forwarded through nodes. After being notified of the conflict the merchant could politely ask the customer to wait for a couple of confirmations.

Your proposal would make instant Transactions safe. Thats not the point.
The point is that the network would not be safe against denial off service attacks any more.
The question is what happens if someone creates intentionally double spends, not to cheat someone else, but to fork the chain.

individual nodes can ip block at will. A very skilled ddoser with a botnet could cause some trouble before the nodes could block all his gateways but he couldnt do any REAL damage to a system as adaptable and decentralized as bitcoin.

i definitely could be wrong on this one though. I'm not an internet securities expert by any stretch of the imagination.