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.

[1715608635]

1715608635

[1715608635]

1715608635

[1715608635]

1715608635

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