Best practice for fast transaction acceptance - how high is the risk?

[jav]

Scenario: You, as a merchant, would like to allow for quick payment with Bitcoins - for example at a supermarket - and therefore can't wait around for one or several confirmation blocks. Instead, you receive the transaction, broadcast it to nodes you know and wait for a couple of seconds to see if you notice any double-spend attempts. If not, you accept the payment right away.

I know that this scenario has been discussed already to some extend in the snack machine thread (http://bitcointalk.org/index.php?topic=423.msg3647#msg3647) but it went a little off-topic there I thought, with people suggesting central or semi-central solutions to accomplish this. Central solutions are what we have today, they are not the answer. Whatever is needed to do fast transaction confirmation will need to be decentral.

In any case, I would like to hear your thoughts and attack scenarios on the procedure outlined above. How high is the risk of accepting transactions in this way? My assumption is, that the attacker does not have more than 50% of the CPU power of the network available to him, but might be able to control a large number of IP addresses.

Once the transaction is broadcasted to all nodes, they will start working on including it in the next block. The attacker can not outpace that (see assumption) so his only chance is to get his double-spend transaction to spread through the network faster and thus have more nodes working on including his second transaction. In that case though, I - as the merchant - will also receive the second transaction in a matter of seconds and notice the double-spend attempt. So I can only think of one attack scenario: The attacker controls a large number of IP addresses and - after waiting for a while - hopes that I am only connected to nodes controlled by the attacker. The attacker is now free to selectively forward transactions from the rest of the network to me and thus be able to prevent me from seeing the double-spend transaction too early.

Is this really the only attack scenario? Am I missing other risks that I would expose myself too?

[theymos]

You need >50% of the computational power to get 6 confirmations. For 1 confirmation, 1% of CPU power will give you about a 1% chance of being able to reverse the transaction, regardless of how well the original transaction propagated.

If the attacker can't do that, then broadcasting and waiting a few seconds does give a good chance that there will be no double-spending. However, nodes will not relay transactions they consider bad, so you might not see bad transactions until they're in a block. This is why a centralized "super node" with many connections is desired. And Bitcoin doesn't currently warn you about double-spends, anyway.

[Hal]

Suppose the attacker is generating blocks occasionally. in each block he generates, he includes a transfer from address A to address B, both of which he controls.

To cheat you, when he generates a block, he doesn't broadcast it. Instead, he runs down to your store and makes a payment to your address C with his address A. You wait a few seconds, don't hear anything, and transfer the goods. He broadcasts his block now, and his transaction will take precedence over yours.

[ByteCoin]

Scenario: You can't wait around for one or several confirmation blocks. Instead, you receive the transaction, broadcast it to nodes you know and wait for a couple of seconds to see if you notice any double-spend attempts. If not, you accept the payment right away.

In the current Bitcoin scheme, one can't accept transactions until it has been incorporated into a block. Suppose two transactions "spending the same coins" enter the network at different points. On average, half the network will have one transaction and half the other. The only way out of this deadlock is which happens to make it into a block first. So you can see that the race across the network is unimportant but the race to get into a block is the deciding factor.

Hal's attack above would yield a reliable income.

ByteCoin

[jgarzik]

In the current Bitcoin scheme, one can't accept transactions until it has been incorporated into a block. Suppose two transactions "spending the same coins" enter the network at different points. On average, half the network will have one transaction and half the other. The only way out of this deadlock is which happens to make it into a block first. So you can see that the race across the network is unimportant but the race to get into a block is the deciding factor.

Presumably, a commercial bitcoin payment processor would spend the bucks to enter the network at a wide array of points, implementing their own double-spending detection and prevention.

[AmnesicWeasel]

Presumably, a commercial bitcoin payment processor would spend the bucks to enter the network at a wide array of points, implementing their own double-spending detection and prevention.

This is my own presumption. One may, in a sense, view modern credit cards as a secondary currency backed by and pegged to e.g. USD. "Bitcoin credit cards" would, I expect, be the same.

The current situation blinds people to the fact that eventually, most BTC users would likely not be concerned with things like "addresses" and "blocks", they would use credit cards, bank accounts, etc. not terribly unlike they do now, trusting (hah) the finanical institutions to get it right in the background, as they have historically.

[Nefario]

The best way to ensure a past, instantanious payment is to have another system ( such as a web based payment processor) backed by bitcoin. It would mean users(and spenders) wouldhave to deposit bitcoin to their account first.

This gets rid of the need to worry about doublespending or any of those other problems, and changes to the question of "do I trust the system provider to have all the bitcoins he says he has?"

[genjix]

just pay the fee

[AmnesicWeasel]

just pay the fee

That does nothing to solve the problem of standing in a grocery store waiting up to 10+ minutes for a new block to be generated. This is not a problem one can solve by blindly throwing money at it.

[joe]

Scenario: You can't wait around for one or several confirmation blocks. Instead, you receive the transaction, broadcast it to nodes you know and wait for a couple of seconds to see if you notice any double-spend attempts. If not, you accept the payment right away.

In the current Bitcoin scheme, one can't accept transactions until it has been incorporated into a block. Suppose two transactions "spending the same coins" enter the network at different points. On average, half the network will have one transaction and half the other. The only way out of this deadlock is which happens to make it into a block first. So you can see that the race across the network is unimportant but the race to get into a block is the deciding factor.

Hal's attack above would yield a reliable income.

ByteCoin

We could update bitcoin client with the following modifications:
- if 2 double-spend transactions received within 20 seconds of each other ==> ordering unknown. Accept blocks with either transaction, and build on top of the longest chain. (Current implementation)
- if 2 double-spend transactions received more than 20 seconds apart ==> ordering known. Reject all blocks that include the later, non-original transaction(s). Do not build on top of the rejected block.
- stop rejecting blocks containing double-spend transactions if the block receives 6 confirmations (to prevent a permanent chain fork)
- clients should relay double spend transactions to alert the recipients that there was a double spend attempt.

If we do this, then fast payments will be possible using the method laid out by the original poster.

[Steve]

My thinking is that the amount of resources you would have to amass to pull off double spending means that it isn't going to be profitable to attempt such a thing for a few transactions of small value.  In fact, I think the transactions would need to be on the order of $10k or more in value for it to be worthwhile...in which case waiting a little while for the transaction to confirm won't be a problem.  And, as others have said, peripheral networks that clear instantly and centrally and are backed btc are likely to arise.  In fact, the various exchanges are already good examples of that (as is youtipit)...you deposit your btc in a trading account and trust they don't run off with the money (and trades settle instantly).

So, I guess in a nutshell, I think this is a non-issue (though it is certainly worthwhile to explore the topic in depth).

[jav]

Thx for your input! A few comments and questions (sorry, long post):

However, nodes will not relay transactions they consider bad, so you might not see bad transactions until they're in a block.

Aw, I see, I wasn't aware of that. Is there a reason why they don't relay those transactions? Would it hurt if they did? (provided that they make sure to first relay valid transactions). It seems this way it's indeed fairly likely to not see a bad transaction until it is in a block.

In the case where nodes don't relay bad transactions, it would actually hurt to sent the transaction out, as it creates a sort of 'wall' just around you and you are fairly likely to not notice anything else. So I guess it would be better then to not send out anything and instead only listen. And even when you receive the transaction, you don't send it out, but wait until _all_ of the nodes you are connected to have relayed the transaction. If - after some time - some of your neighbor nodes haven't done so, you can deduce from that, that they must have heard a conflicting transaction first and are therefore not forwarding the other one. Doesn't help you with Hal's attack though.

So you can see that the race across the network is unimportant but the race to get into a block is the deciding factor.

Ok, yes. But when the attacker doesn't have much CPU power he needs to rely on other nodes to include the bad transaction. The more nodes that will be working on that, the better the chances. So in that sense the race across the network is off some importance as it will make it more likely that the transaction wins, which the attacker would like to win.

The best way to ensure a past, instantanious payment is to have another system ( such as a web based payment processor) backed by bitcoin. It would mean users(and spenders) wouldhave to deposit bitcoin to their account first.

I don't find this the "best way" at all. How is this different from a world where everyone has gold, but to allow for fast, instantaneous payments you allow some payment processor - let's call them a bank - to move numbers in their system around instead? And then at some point the whole "gold-backed" thing is conveniently forgotten.

Isn't the whole point of Bitcoin that you can move the _actual_ Bitcoins around. If you are going to give that up, what have you won?

Suppose the attacker is generating blocks occasionally. in each block he generates, he includes a transfer from address A to address B, both of which he controls.

To cheat you, when he generates a block, he doesn't broadcast it. Instead, he runs down to your store and makes a payment to your address C with his address A. You wait a few seconds, don't hear anything, and transfer the goods. He broadcasts his block now, and his transaction will take precedence over yours.

Ok, that sounds like a pretty realistic attack scenario that isn't too difficult to pull off. So anything that can be done about that without waiting around for 10+ minutes? Maybe something with timestamps? My understanding is that blocks are timestamped and there are some checks regarding the timestamps (https://en.bitcoin.it/wiki/Block_timestamp). However pretty wide time periods seem to be valid. In a world with with high-speed networks, couldn't that be made a little tighter? So that a 'precomputed' block would quickly become invalid?

One way I look at the Bitcoin network is this: A bunch of nodes want to establish a 'shared reality'. This 'shared reality' says who has how many bitcoins. They find that consensus by - in a way - voting and the more CPU power a node has, the more votes it has. If you look at it from this way, shouldn't there be more mechanisms to ensure that every node knows what is being voted about right now? I know this is hard in a best-effort network with nodes constantly joining and leaving, but might have a lot of potential. I think nodes shouldn't so readily accept a shared reality which contains decisions (transactions) that they haven't even seen before and thus weren't able to vote on.

[AmnesicWeasel]

Isn't the whole point of Bitcoin that you can move the _actual_ Bitcoins around. If you are going to give that up, what have you won?

What makes you think you've given anything up? You can still move bitcoins around yourself through the network. All we're saying is that high-speed, on-the-spot transactions will still need a trusted third party to facilitate.

So long as people are capable of evil, various forms of escrow services will continue to exist. That's all an immediate-settlement payment processor is -- an escrow service.

[Nefario]

It is an important point about sites "backed" with bitcoin, that like many bank in history cheat, and issue more currency than they have backing for.

The reason banks can easily do this is (originally) gold was kept in a vault, and it's existence could not be verified by any outsider.

But bitcoins are digital, we can instantly audit for the presence of bitcoins, so that as soon as the "bank" started inflating we would know.

At the moment we dont have any payment system backed by bitcons like this, but one of the requirements for my trust is instant auditing and verification. An outside auditor can be used, where at the end of the trading day to bank sends all their bitcoins to an address the auditor has, auditor confirms the presence of said bitcoins, signs with their privste key a certificate for that day. As long as you trust the auditor this works. You could even have multiple auditors.

It does not eliminate the risk, but reduces it, making it much more difficult and expensive to commit fraud.

[casascius]

Ideally, a supermarket is going to be using a payment device like a credit card machine, which will interact with a payment processor like MYBITCOIN that can capture the funds and hold them immediately.

There is already a pretty strong consensus that having every bitcoin node be a full node is unscalable and unsustainable, so to me, the problem of how fast a grocery store can prevent a double spend in the current client is moot.

Since I have a SDK for a very popular payment platform, I've been tempted to sell a few of the devices for BTC and see if the open source community could come up with a way to compile to them based on anecdotal information I can share without pirating the SDK.  (These devices use ARM processors and the proprietary OS has been made to be as POSIX-like as possible, so this isn't too unimaginable... plus much of the hardware inside is third party and full specs can be obtained freely)

[Gavin Andresen]

To cheat you, when he generates a block, he doesn't broadcast it. Instead, he runs down to your store...

I think the real danger is that a large mining operator would create a side business selling space in their blocks for these types of intentional double-spends.  When they generate a block they could send a text message to a bunch of people saying "try to spend NOW".

I wonder if there's some way to discourage that kind of anti-social behavior; could the network detect that was being done and "shun" that miner's blocks?

[FatherMcGruder]

What about just having an account with the supermarket or bar? Just load it up before you go shopping or drinking.

[jav]

Isn't the whole point of Bitcoin that you can move the _actual_ Bitcoins around. If you are going to give that up, what have you won?

What makes you think you've given anything up? You can still move bitcoins around yourself through the network. All we're saying is that high-speed, on-the-spot transactions will still need a trusted third party to facilitate.

I can also move my gold around today. But my salary is paid in a currency that isn't backed and so is everyone's salary around me, so the gold doesn't really help in preventing a crash.

I guess Nefario has a good point about audits being easier with Bitcoins and that is definitely and advantage compared to gold. But it also requires a bunch of people to be vigilant and to understand all the pitfalls of money systems. I'd much rather see these protections against money creation baked into the system that will actually be in use by everyone.

[Hal]

I wonder if there's some way to discourage that kind of anti-social behavior; could the network detect that was being done and "shun" that miner's blocks?

I think that was Joe's suggestion: if a block shows up that turns one or more previously-broadcast transactions into double-spends, you don't count it. Maybe we could give it a negative difficulty penalty, so that the block chain with this block would have lower cumulative difficulty than without it; that way it would stay an orphan and not be added to the chain. Then if it was all a big mix-up and other nodes kept building on this one, eventually they would overcome the negative difficulty and it would be accepted, as Joe proposed with his 6-block rule.

Obviously changing the voting rules like this would need careful analysis.

[jav]

I think the real danger is that a large mining operator would create a side business selling space in their blocks for these types of intentional double-spends.  When they generate a block they could send a text message to a bunch of people saying "try to spend NOW".

I wonder if there's some way to discourage that kind of anti-social behavior; could the network detect that was being done and "shun" that miner's blocks?

Maybe another example of why a node should be suspicious of blocks that contain transactions it hasn't seen before. I thought joe had a good suggestion in this regard:

We could update bitcoin client with the following modifications:
- if 2 double-spend transactions received within 20 seconds of each other ==> ordering unknown. Accept blocks with either transaction, and build on top of the longest chain. (Current implementation)
- if 2 double-spend transactions received more than 20 seconds apart ==> ordering known. Reject all blocks that include the later, non-original transaction(s). Do not build on top of the rejected block.
- stop rejecting blocks containing double-spend transactions if the block receives 6 confirmations (to prevent a permanent chain fork)
- clients should relay double spend transactions to alert the recipients that there was a double spend attempt.

If we do this, then fast payments will be possible using the method laid out by the original poster.

This sounds like an interesting idea to me. It would change the rule 'nodes work on the longest chain' to 'nodes work on the longest chain which doesn't include transactions they consider invalid' (with the important exception mentioned by joe that a chain that is 6 blocks longer can convince the node that the transactions are in fact valid).

What are possible problems with this? I guess it would make the network vulnerable to an attack which slows down block creation: Different parts of the network could be fed conflicting transactions and the block chain would then start to split up as nodes only work on what they consider the valid transactions. This would continue for a while as now 6 blocks are needed to break the tie and a single part of the network needs to produce all of them. Pretty big vulnerability I guess - any way around this?

[Edit: Didn't mean to ignore Hal's response, only saw it after posting]