How anonymous is Bitcoin?

How private is Bitcoin? On the one hand, it is entirely anonymous. On the other, it is completely transparent and trackable. How can that be – and what does it mean for privacy?

Incumbent Bitcoin exchange Mt Gox recently imposed authentication rules on people trading fiat currencies on its network. The rules – which didn't apply to people trading only in bitcoins – require people to verify their identities. There may not be any such requirements on native bitcoin users yet, but it highlights the issue of privacy. Many people using Bitcoin don’t want others to know who they are. The question is whether they're able to hide that information.

Bitcoin could be interpreted as a 'pseudo-anonymous' network. It is anonymous in the sense that you can hold a Bitcoin address without revealing anything about your identity in that address. One person could hold multiple addresses, and in theory, there would be nothing to link those addresses together, or to indicate that the person owned them.

So far so good, but there is another side to Bitcoin. Everything that happens in the Bitcoin world is trackable. Thanks to the way that the algorithm is structured, every Bitcoin-based transaction is logged in the blockchain.

This leads to a level of transparency that may surprise some Bitcoin users. "If you publish your Bitcoin address on your website, then everyone in the world will be able to know what your bitcoin balance is," points out Sergio Lerner, CEO of Argentinian company Certimix.

Certimix develops products for protecting online card games sites and their players, using mathematically proven algorithms. Lerner has a strong cryptography background, and has discovered several vulnerabilities in the Satoshi algorithm.

“Privacy is not enforced by the Bitcoin protocol design,” he says. “If you re-use the same address over and over to receive money from other users, then every one of them will detect that the others have sent you money.”

But surely this isn't a problem. After all, if your name isn't explicitly linked to a Bitcoin address, then it doesn't matter if people know what transactions that address is participating in, right? Wrong, says Matthew Green. Green is an assistant research professor at Johns Hopkins University, and the co-developer of an anonymity system for crypto currencies called Zerocoin.

Interested parties have become very good at inferring information from large network movements, Green says, pointing out that this is pretty much Google’s business model. Facebook’s, LinkedIn, and pretty much any other social network that laps up big data will be working hard at extracting as much data from that network as possible by looking for patterns.

“With a bit of data mining, my concern is that people will get a lot of information. The things people are doing to protect themselves today are pretty naive compared to the kinds of clever data mining tricks that exist. What I’m worried about is that a lot of people are doing things that are leaving a permanent history and will then inadvertently leave some trace that reveals their actual identity," he says.

Sound far-fetched? Let's not forget Arvind Narayanan and Vitaly Shmatikov, who were both researchers at the University of Texas in 2007. They took a dataset, publicly released by Netflix, which contained 10 million movie rankings by 500,000 customers. The online video company was running a competition to see if people could develop a better movie recommendation system by analysing the data set.

There should have been no problem, because the dataset was rendered anonymous, meaning that all personal information pertaining to the movie rankings had been removed.

But the researchers matched rankings and timestamps with information publicly stored in the Internet Movie Database (IMDb). It enabled them to find out who certain people were, removing the anonymity from certain parts of the data.

Thelma Arnold, a widow living in the US state of Georgia, probably never searched for “deanonymisation”. Nevertheless, the Internet suddenly knew a lot more about her search history in August 2006. She was a frequent AOL search user, and her searches were mixed anonymously into a file with 20 million others and released by AOL for researchers to play with.

By analysing the searches, data scientists were able to figure out who she was (along with the fact that she’s interested in single men over 60, and that she'd like some way to stop her dog urinating on everything).

Recombining personal information by analysing large data sets isn’t just for sport – it has huge ramifications for law enforcement, intelligence services, and other players. Narayanan calls this branch of research "reidentification". Presumably, the techniques used will vary depending on the data sets involved. But with a completely transparent block chain, bitcoin is a ripe target.

How do paranoid bitcoin users stop this happening? John Hopkins’ Green hopes to help with Zerocoin. It effectively builds a money-laundering service into a crypto currency at the protocol level.

“The way we designed it is that you take original bitcoins, you turn them into Zerocoins, and then you turn them back into new bitcoins in another wallet,” he says.

The technology is being refined to be more efficient, particularly in the size of mathematical proofs that it needs per transaction. It will be ready for deployment in a couple of weeks, says Green.

But just because researchers built it doesn’t mean that Bitcoin users will come. Getting someone to adopt it is perhaps more challenging than the mathematics behind it. It would need to be built into the core protocol, and all of the clients would need to be updated, probably needing a hard fork. The core development team has enough work on its plate.

“The core devs (who have very little resources) are focusing in reducing the complexity and creating a robust application, not adding more features that would need great efforts of testing and validation,” protests Lerner.

Green agrees that getting Zerocoin into the Satoshi protocol is a long shot. But hopes that some alternative currencies will take a risk and try to work this into their clients. “Then we would get to test it and see it working. We are hopeful."

Lerner has his own altcurrency, with a built-in anonymity feature, but it isn’t using Zerocoin. Qixcoin, which is designed to support online wagering, is anonymous, untraceable, and tradeable with other cryptocurrencies, Currently in beta, it uses Lerner’s own anonymity protocol, called APPECoin.

“APPECoin uses special cryptographic constructions to make the size of the proofs much, much smaller, and so it is as scalable as Bitcoin,” says Lerner, who hopes to release a technical paper on the project in the next two weeks. “Also, APPECoin completely hides the amounts paid, and coins can be divided and combined privately without disclosing the amounts.”

These developments are all very well, but don't help Bitcoin users paranoid about their transactions today. So, what can be done? Lerner has some advice. Changing Bitcoin payment addresses often (or even creating a destination address for each payment) is a healthy thing to do, as is connecting to the Bitcoin network using the Tor anonymity system.

Connecting to the Bitcoin network using two peers in a chain is another worthwhile step, advises Lerner. "The first node holds the private wallet and connect only to the second node," he explains. "The second is the gateway with the remaining nodes of the Bitcoin network."

Another is to use an external mixing service to render your coins anonymous. There are several of these, which don’t work at the protocol level. Instead, they simply function as third-party services. One of them, called BitLaundry, works simply.

The sender (Alice) gives the address of the recipient (Bob) to the laundry service (BL). BL gives a one-time address to Alice, to which she sends Bob's bitcoins. BL mixes them into a pool of other bitcoins, and then deletes the database link between the one-time address and Bob's address, before sending the bitcoins to Bob. This happens according to a predefined delivery schedule, making it difficult for any third-party to analyse transaction timestamps.

BitLaundry advises users to send themselves bitcoins, thus obscuring their history, and to use multiple recipient addresses, further obfuscating the transactions.

Until bitcoin includes a protocol-level anonymity system, users interested in true privacy will have to follow a number of workarounds to decrease the probability of detection. If they don't follow the rules, then they should be aware of the consequences. In many ways, Bitcoin is like Vegas: what happens in the blockchain stays in the blockchain.