Solving the fast payments problem

[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.