The challenge of online anonymity

The Bitcoin system has been the center of much interest of late, for a variety of reasons. One interesting aspect of the Bitcoin system is that it attempts to provide secure, private, anonymous online transactions. From the Bitcoin paper:

The traditional banking model achieves a level of privacy by limiting access to information to the parties involved and the trusted third party. The necessity to announce all transactions publicly precludes this method, but privacy can still be maintained by breaking the flow of information in another place: by keeping public keys anonymous. The public can see that someone is sending an amount to someone else, but without information linking the transaction to anyone. This is similar to the level of information released by stock exchanges, where the time and size of individual trades, the "tape", is made public, but without telling who the parties were.

As an additional firewall, a new key pair should be used for each transaction to keep them from being linked to a common owner. Some linking is still unavoidable with multi-input transactions, which necessarily reveal that their inputs were owned by the same owner. The risk is that if the owner of a key is revealed, linking could reveal other transactions that belonged to the same owner.

This idea of online anonymity has been around for a while; one primary source is Wei Dai's famous "b-money" proposal, which begins as follows:

I am fascinated by Tim May's crypto-anarchy. Unlike the communities traditionally associated with the word "anarchy", in a crypto-anarchy the government is not temporarily destroyed but permanently forbidden and permanently unnecessary. It's a community where the threat of violence is impotent because violence is impossible, and violence is impossible because its participants cannot be linked to their true names or physical locations.

You can learn more about Tim May's crypto-anarchy here. May traces these ideas back to the mid-1980's, and describes them as follows:

Computer technology is on the verge of providing the ability for individuals and groups to communicate and interact with each other in a totally anonymous manner. Two persons may exchange messages, conduct business, and negotiate electronic contracts without ever knowing the True Name, or legal identity, of the other. Interactions over networks will be untraceable, via extensive re- routing of encrypted packets and tamper-proof boxes which implement cryptographic protocols with nearly perfect assurance against any tampering. Reputations will be of central importance, far more important in dealings than even the credit ratings of today. These developments will alter completely the nature of government regulation, the ability to tax and control economic interactions, the ability to keep information secret, and will even alter the nature of trust and reputation.

Now that the Bitcoin implementation is online and operational, the question naturally arises: is it successful? Does it provide privacy, with assurance against any tampering, because its participants cannot be linked to their true names?

Two computer scientists at University College Dublin have been studying this question, and this summer they published An Analysis of Anonymity in the Bitcoin System. The paper discusses the general notions of online anonymity, and then looks specifically into the question of whether Bitcoin is achieving its goals. The core of their analysis explores several particular attacks on Bitcoin anonymity:

1. Integrating Off-Network Information, that is, correlating Bitcoin transactions with other information that may be available from other sources outside of Bitcoin, such as from those organizations and services that accept Bitcoins as payment.
2. Egocentric Analysis and Visualization of the User Network
3. Context Discovery
4. Flow and Temporal Analyses, which involves developing circumstantial evidence about possible correlations and identities of Bitcoin actors

and points to a number of other possible attacks.

The authors argue that the techniques they've developed so far have been significantly effective:

Using an appropriate network representation, it is possible to map many users to public-keys. This is performed using a passive analysis only. Active analyses, where an interested party can potentially deploy marked Bitcoins and collaborating users can discover even more information.

Lastly, as the authors point out, security attacks on a system which intentionally preserves all known transaction data publically, forever, will only get better over time, so the approaches they've developed so far may well be improved upon.

The goals that Bitcoin have set for themselves are challenging. I believe that they welcome this sort of analysis and study; it's the sign of a serious system that they take their work seriously. From my own perspective, I enjoyed following the techniques that the authors used to explore the possible weaknesses in Bitcoin. I'll look forward to following the discussion as it develops.