Bitcoin vending machine timing attack - testing scenarios?

[BombaUcigasa]

Once upon a time some hackers broke into a bank subsidiary, and stole the credit card details of over 100.000 workers. They then proceeded to quickly sell off those credit cards but with a twist. All clients agreed to use their stolen card at a certain point in time (15 minutes after the bank transferred the worker's salaries into their account). So all over the world, 25.000 people got to an ATM and in the exat 15 minutes interval, withdrew someone's salary out of a random ATM.

Supposedly a vending machine could be able to dispense products once it receives a payment to the unique wallet address it created for the order. The fact that the private new wallet address is created on the spot and only known to the client allows for confirmation of payment. The fact that the client sent a transaction to be included in the next block, to the whole network, shows this has happened. The vending machine has no reason not to deliver the goods, since within about 4 minutes, a block will include that transaction and lock profits. Or does it?

What if 1000 people all over the clock synchronize their clocks, download the same wallet to their mobiles, generate a new sender address and pay their close-by vending machine for some snacks within a 10 seconds span, definitely less than the time required for a new block that shows the transaction is invalid. What would happen? Would it be able to double-spend if the vending machines do not await confirmation?

How can we test this scenario on the testnet?

[1714846995]

1714846995

[1714846995]

1714846995

[1714846995]

1714846995

[1714846995]

1714846995

[1714846995]

1714846995

[tymothy]

Dunno how you test it, but the solution is to have a third party merchant who allows a small line of credit to the customer and runs their own (fast) verification network not based on bitcoins. Each transaction will be approved in serial until the wallet hits its limit.

[Stephen Gornick]

Supposedly a vending machine could be able to dispense products once it receives a payment to the unique wallet address it created for the order.

If you use a hammer where what was actually needed was a screwdriver, do you have a legitimate complaint when the results go badly?

i.e., there is a reason why multiple confirmations are required before a transaction is trusted.

Right now, there is a solution.  As long as both the merchant and customer use the same ewallet provider, transactions can be instantaneous.  MyBitcoin works this way already today.    Similarly, another solution might be simply to advance some amount to an account with the merchant or with some other intermediary.  Consider if the mobile point of sale vendor Tabbed Out were to add bitcoins as a payment method, for example.  They would hold your coins in their wallet so those coins would be spendable instantly regardless of which restaurant you dined at.  With those solutions, however, you have the drawbacks where you must extend trust to an intermediary and lose some privacy.

One other idea includes a pure bitcoin method where low value transactions might be allowed on receipt by the merchant with no confirmations.  This method assumes however that there are listening posts on the network that would monitor for double spends and alert the merchants after any double spend attempts were discovered.  Without such monitoring, this approach would be completely vulnerable to your attack scenario.

Additionally, there have been reports that work is underway to integrate bitcoin with the Open Transactions platform to allow transactions that are both anonymous (as far as the merchant knowing the buyer) and also are instant, requiring no confirmations. This too requires pre-paying bitcoins to the OT account that will be used for spending.

[DamienBlack]

Yes, this would be a valid attack. That is why transaction are not considered confirmed until it has been included in six blocks. In fact, you don't need vending machines, you can do it right now from two different computers that have the same wallet. In the end, the two transactions will slowly battle their way through the network and only one will get confirmed. In a very, very rare case that would likely have to be a coordinated attack, both transaction may end up being included in different blocks. But, assuming the miners aren't working to muddle the system, it will sorted out and only one will end up with 6 confirmation. The odds that both transaction accidentally end up with six is completely astronomically unlikely, which is why we consider six transaction confirmed. Honestly, barring an intentional attack on the network, you can be fairly confidant of a transaction at one confirmation, and very sure at two.

[Maged]

Dunno how you test it, but the solution is to have a third party merchant who allows a small line of credit to the customer and runs their own (fast) verification network not based on bitcoins. Each transaction will be approved in serial until the wallet hits its limit.

This. As for what that network would do, they would listen for a few seconds for a conflicting transaction. If no conflict is heard, approve the transaction. If a conflict is detected, decline the transaction, at which point the user of the snack machine would have to call the payment processor to get their money back if the original transaction went through.

After a few seconds, it is all but impossible to get a conflicting transaction into a block. The only real threat to accepting unconfirmed transactions, at that point, is the Finney Attack - and that can only have one victim per coin. Of course, a Finney Attack can be staged with hundreds of double-spends. Imagine this: you generate a transaction to yourself and submit it to a company that does Finney Attacks. Then, when the block is ready, they text you: "spend NOW!", giving you about 30 seconds or so to do a double-spend before they publish the block. However, it's impossible to do a Finney Attack on your time-table. (good luck using a Finney Attack at the grocery checkout, for example)

[MoonShadow]

There are a number of ways to reduce the risks in accepting a transaction as proof of payment within bitcoin.  Waiting for confirmations is, obviously, the most secure and trustworthy method, and the only one presently established.  However, there are a couple of ways that a vendor rapidly selling low value items in meatspace can significantly reduce their exposure to just such a coordinated fraud.  First off, ten seconds is pretty tight timing, so it's not going to be an easy attack anyway. 

But think of it like this...

Vending machine doesn't do the verifications itself, this would likely be done at the owning company's server, but for simplicity let us imagine that it's done at the vending machine.

One participating attacker walks up to vending machine, no one waiting.  His watch is set for just the right time to send the final transaction.  So he chooses his loot and sets up the transaction, hears his watch alarm and presses 'send'.

The transaction hits the p2p network, doesn't matter if the attacker sent it to the vending machine first or directly to the Internet.  Vending machine is waiting a few seconds for the transaction to move across the p2p network.  What it is waiting for is to see all of it's peers, and most importantly it's most 'netgraphicly' distant peers, to tell it about the new transaction.  If all of it's peers tell it that this transaction exists, then that means that transaction is the first one that spends those coins that said peer has seen.  It also means that those peers will ignore any other transactions that spend those same coins, refusing to include them in mining blocks or forward them to their own peers.  So if the vending machine sees that all of it's peers have received and accepted that transaction as valid, then that means that vending machine was the first to get it's transaction out onto the p2p network, and thus it doesn't much care about any other transactions because it's astronomically unlikely that a double spend attempt will work out counter to it's own favor.

However, if even one peer does not tell the vending machine about the new transaction within a set period of time, then that likely means that said peer has already seen a conflicting transaction, and the vending machine simply refuses to dispense.

[Stephen Gornick]

However, if even one peer does not tell the vending machine about the new transaction within a set period of time, then that likely means that said peer has already seen a conflicting transaction,

or a network issue, or a grieffer realizing how to disrupt vending machines, or [...]

But I might be misunderstanding this.  Are you saying that if my node relays a transaction to your node, your node will then in turn bounce that transaction back to me?

[BombaUcigasa]

First off, ten seconds is pretty tight timing, so it's not going to be an easy attack anyway. 

Actually ten seconds was chosen as a consideration of peer propagation. You can do it faster than 10 seconds. Clocks are pretty exact these days. A vending machine taking more than 10 seconds to confirm payment would be almost useless. And ten seconds was also chosen so even the slowest humans can still perform the attack in a reasonable time. A first confirmation is expected in 4-6 minutes, so we won't go there.

However, what does the bitcoin client see when 2 people send the full address funds to it, from within the same wallet? Does it see two consecutive unconfirmed transactions? Does it pick one of them that happens to arrive faster? Does it propagate one or both across the network? How can any network peer check that both transactions are valid, do they perform it against the blockchain or does only the receiver have to do that?

[MoonShadow]

However, if even one peer does not tell the vending machine about the new transaction within a set period of time, then that likely means that said peer has already seen a conflicting transaction,

or a network issue, or a grieffer realizing how to disrupt vending machines, or [...]

But I might be misunderstanding this.  Are you saying that if my node relays a transaction to your node, your node will then in turn bounce that transaction back to me?

Well, no.  It wouldn't.  What the nodes actually do is announce the hash value of transactions that it is aware of to nodes, and nodes that do not have that transaction will request it.  If that node considers it valid, it also then annouces to it's other peers.  So what would have to happen is that the vending machine would have to pick a couple of it's peers out to not announce that transaction to, so that it could just wait to get that transaction to announce it back to itself, thus confirming that said transaction has moved across the p2p (that said vending machine could see) without another conflicting transaction hitting the chosen peers first.  I oversimplified the scenario, I guess.  Most people seem to get very confused.

[MoonShadow]

However, what does the bitcoin client see when 2 people send the full address funds to it, from within the same wallet? Does it see two consecutive unconfirmed transactions? Does it pick one of them that happens to arrive faster? Does it propagate one or both across the network? How can any network peer check that both transactions are valid, do they perform it against the blockchain or does only the receiver have to do that?

As I mentioned above, when a node sees a new transaction, it checks that transaction for validity, including making sure that it has not already seen a transaction that spends those same coins.  The second transaction thus fails the validity check and is not propogated furthur.  So, in the end, the first transaction to hit the p2p network will get propogate to the majority of the peer nodes, and stop when it hits the propogation wave of the second transaction.  The differences between the first and second transaction would be milliseconds, and it would likely take less than three seconds for any other conflicting transactions to fail right at the vending machine server itself.  A vending machine server would also have an economic encentive to maintain a connection with a major miner, such as a pool, due to the lopsided propogation that such a peer connection provides.  So, even with a 10 second window, only those who hit send right at the beginning of the window will succeed, and players also have an encentive to cheat by sending early.  Maybe a few people could get the machine to give up some loot, but one of them is actually going to still get paid.  The vast majority of players are going to get nothing.

[Stephen Gornick]

Maybe a few people could get the machine to give up some loot, but one of them is actually going to still get paid.

Ha, I forgot that defense mechanism.  At the profit levels for vending machine snacks, even if you succesfully pull off a [single] double-spending attempt, you still lose because the markup on the one snack you did just buy is so high.