How to Double-Spend a Bitcoin
by 0x80
First, sorry for the sensational title. No, I haven't discovered some amazing way to subvert the blockchain's integrity properties and perform an on-chain double-spend. Rather, this is a social engineering attack which takes transactions off-chain, enabling a double-spend.
But please bear with me. I think this will be interesting to many readers.
What Does It Mean to "Own" Bitcoins?
"Ownership" is a messy concept to define for bitcoin and similar cryptocurrencies. The easiest definition of ownership is "the ability to spend." If you can spend the bitcoins, they're yours, right? But what if someone else also has the ability to spend those same bitcoins? Let's look briefly at how bitcoin transactions actually work.
Bitcoin transactions have inputs and outputs. Transaction outputs are the closest thing to instances of bitcoins existing (and inputs spend the outputs from previous transactions). These transaction outputs are locked away with little programs which one must cause to return true (or, more precisely, a non-false value) in order to claim the output's value and transfer it to a new output. Usually this locking script returns true if, and only if, one can demonstrate (with a cryptographic signature) that they have the private key corresponding to an address contained in the script.
Bitcoin's scripting language isn't limited to just asking for signatures; it's possible to make lots of different programs. It's possible, for example, to make a transaction output which can only be spent by someone who can find a SHA-256 collision1 or someone who can provide a specific file, such as a bitcoin-themed parody of a Western Union ad.2
And it's entirely possible that more than one person has the requisite file, or that a hash collision is known by multiple people. (Maybe none of them knows or cares that they can get a reward in bitcoin for it.) Even if the challenge is to prove ownership of a private key, it's always possible that multiple people know the same private key. The key could have been generated with insufficient randomness. One person could have compromised another's device. Even if two people do everything right, it's within the realm of possibility (however astronomically unlikely) that they just happen to randomly generate the same private key or that a hashing collision causes their private keys to yield the same address.
Until a transaction output is actually spent (and another is made to replace it), it's impossible to say with absolute certainty who "owns" it. Arguably, ownership can only be defined retroactively: if you spent it, you must have owned it when you spent it.
With this in mind, I thought of an interesting scheme. Of course, I would never do this, and neither should you. But what hacker doesn't look at a system like this and start to think of ways it could be exploited? So please, dear reader, play make-believe and enact this scheme with me.
Double-Spending Physical Bitcoins
For this scheme, we'll be minting physical bitcoins. These are a real thing, by the way. A bitcoin user called Casascius made a bunch from 2011 to 2013 before stopping due to legal issues.3 They're fundamentally just "paper wallets" (private keys written down), but in the form of metal tokens. The private key (or a seed used to derive it) is protected by a tamper-evident sticker, and the bitcoin address (or its seed) is readable on the outside of the sticker. A transaction is created which locks away 1 BTC (or some other amount represented by the coin) such that it should only be spendable by someone who has the private key.
This enables the physical coin, representing a virtual coin, to be traded. Since the address is visible, anyone who observes the physical coin can check the blockchain to verify that a still-unspent virtual bitcoin is represented by it. However, they can't actually spend that bitcoin until they remove the sticker, exposing the private key and permanently marking the physical coin as used.
You might be thinking that when we mint these physical coins, we're going to simply write down the private keys and spend the virtual coins later. But that would be too easily detected. If we sell a physical coin to Alice and then spend the corresponding virtual coin, Alice can check the blockchain and see that her coin is gone!
No, instead, we're going to do something more subtle, which relies on the fact that these coins are collector items. Collectors like to keep things in mint condition. They're more valuable that way. Thus, it seems likely that many of our customers will not want to spend the virtual coins. Anecdotally, I know someone who has a small collection of Casascius coins who has told me that they would probably never remove the stickers. Empirically, at the time of writing, only about 27.5 percent of the Casascius physical bitcoins (counting by number of discrete physical units, not total BTC value represented) have ever had their virtual counterpart spent.4
We'll specifically target our sales to collectors we believe will not spend the virtual coins. Suppose we have two different customers, Alice and Bob, and we believe that neither will spend the virtual bitcoin, instead treating the physical coins only as collectibles backed by virtual coins. Suppose that we also believe Alice and Bob will not compare their physical bitcoin collections. (We might choose pairs of customers in different countries with no apparent connection to each other.) In this case, we can create two coins representing the same private key and sell one to Alice and one to Bob.
Interestingly, since ownership is so messy, as long as neither party actually spends the virtual bitcoin, both Alice and Bob might be considered rightful "owners" of the same bitcoin, and to each, it will appear that they are the owner. And just like that, we have double-spent a bitcoin!
References
1.) bitcointalk.org/index.php?topic=293382.0
2.) See transaction: 200f3f6f8a91ae438d1924e5cedca98cea7f0197b9eba11343948b5621ca19ed which provides a gzip-compressed JPEG to spend one such output.