HAVE A SNACK, PAY WITH BITCOINS
Tobias Bamert, Christian Decker, Lennart Elsen, Roger Wattenhofer, Samuel Welten – ETH Zurich, Switzerland – Microsoft Research
Discussion of Bitcoin in the context of ‘fast transactions’ requires careful consideration of the possibility for double-spending attacks; in this paper Bamert et al. address such concerns and possible countermeasures, presenting the methods with a real-world use case.
For those who don’t know, double spending attacks occur as follows:
“To perform a double-spending attack, the attacker would create two transactions Ta and Tv. Both transactions spend the same output and can therefore not both be valid. Tv denotes the transaction that transfers the required amount to the merchant, whereas Ta is a transaction that transfers the same amount back to the attacker. The attacker then attempts to convince the merchant about the validity of Tv, while broadcasting Ta to the network at the same time. For the double-spending attempt to succeed two conditions have to be met: (a) the merchant should only see Tv until the good or service is released, and (b) Ta must be confirmed by the Bitcoin network, hence Tv would not be valid.”
As outlined by Decker and Wattenhofer, information eclipsing in the Bitcoin network compounds the effectiveness of this attack:
“If the merchant forwards Tv to its neighboring nodes, they will verify and tentatively commit it to the local ledger. Should they later receive Ta, it will not be considered valid as it conflicts with Tv, and it will not be forwarded to the merchant. The merchant inadvertently shields itself against conflicting transactions like Ta, and will be unaware of the double-spending attempt.”
Let’s go over the countermeasures. First, if the merchant is always connected to a significantly large random sample of nodes, the attacker will not be able to deduce with which nodes the merchant is communicating. Second, merchants shall block incoming connections to avoid being sent the transaction directly by the attacker. The merchant should also refrain from broadcasting the transaction when they receive it, forcing the attacker to shield all of the merchants connected nodes from Ta to keep the merchant isolated. This method eliminates the possibility of timing attacks as well.
One must also consider the attack in the context of money being returned to the customer (as change, perhaps tx was cancelled, or the funds were insufficient to complete purchase). In this scenario the merchant would create transaction Tr as a ‘return chain’ of transaction Tv, such that the output of Tv becomes the input of Tr, allowing for a return of funds without the need of a confirmation. This also protects the merchant from returning funds not owned by the attacker.
The performance of these countermeasures were measured. The probability of an attacker succeeding in the case of a double-spending attempt is calculated as “the product of the probabilities of the merchant first seeing Tv, only seeing Tv and of Tv not being confirmed later.” Data was compiled during 1922 double spending attacks, repeated 1000 times each.
With >=40 sample nodes, the first transaction seen is accepted 73.64% of the time. The probability of each one being seen first is 1/2 that, as they are not differentiated while sending. However, when connected to a random sample of 100 nodes in the network, the attacker is left with a .088% chance of performing a successful attack; thus the probability of a double spending attack completing successfully under these conditions becomes 1 in 1000. Quite a significant improvement.
Gavin has mentioned this is in his post-0.9 todo list.