anonymity-in-bitcoin.blogspot.com
This work is about looking at the Bitcoin transaction history as a network, and investigating privacy and anonymity, in practice, on it - something there's been a good bit of discussion around recently.
You can see a lot of non-obvious things, when you 'collapse' addresses, as we describe in the paper, and look at it as a network.
We're not really talking about the extent to which Bitcoin itself is useful as a currency, or investment - that's a whole other topic, and a big one.
If anyone has any questions on the work we did, if you post them here or on the blog, I'll try and answer.
1. You stop short of actually identifying the thief; is this primarily due to ethical concerns or the paucity of off-network information? Could you speculate on whether non-public information available to law enforcement would be enough to resolve the thief's identity?
2. How easy is it for users to protect themselves to foil your analysis techniques? Could client software automate some of these obfuscation mechanisms?
Incidentally, you cite my Netflix work, but my work on deanonymizing social networks based on topology (http://33bits.org/2011/03/09/link-prediction-by-de-anonymiza..., http://33bits.org/2009/03/19/de-anonymizing-social-networks/) might be more relevant, and some of the techniques potentially applicable to deanonymization of the bitcoin transaction network if and when it grows larger and gains a more substantial resemblance to the network of real-life relationships.
1) We made a decision that the purpose of this specific work was to illustrate anonymity pitfalls, for the benefit of users generally, and not to de-anonymise any individual users.
As such, we haven't dug deep to try and identify the thief. We've just examined the theft as a case study, to show that specific flows can be followed in practice.
We think that law enforcement would have, at the least, some leads to follow, if they used similar analysis techniques - we could also have looked deeper into this incident, but didn't.
We can't speculate on whether there's enough information to identify the thief - a lot would depend on whether the leads panned out, and on what sort of assumptions the thief made about trying to hide their identity - outside the scope of this work.
2) I think that some of our analysis would be possible to foil. Its probably possible for client software to avoid a lot of the account 'linking' that is due to transactions inputs being merged, perhaps by breaking the connected components formed, by putting merged Bitcoins through intermediate accounts, or perhaps by supporting mixing of some form.
There are other leakages, of off-network information, such as the Bitcoin Faucet displaying IPs, that could trivially be turned off.
But as to whether this would render Bitcoin anonymous overall, it is very hard to say. It is extremely difficult to get anonymity into your system, unless it has been an explicit design goal; and it would be possible to take this kind of analysis much further than we did.
Thanks for the tip about the paper - we should probably reference it. That was nice work - it occurred to me it was possible to use such a strategy when the competition was announced, and when we saw the results, we knew someone had!
I already did some work on this:
http://coderrr.wordpress.com/2011/06/30/patching-the-bitcoin...
I think it should be adopted by the official client, and, ideally, the users educated as to its usage; it would mitigate a lot of the entity resolution, which our work shows is a widespread problem.
We'd never get our point across if we exhaustively stated every single assumption we made - but you are right to highlight this - its good to be aware these assumptions are there.
I'm not sure it would make the analysis trivial, but you certainly could engineer a system that would have an easy user interface for conducting this sort of analysis on Bitcoin.
For example, the software tools we wrote would probably only require UI work to get them to a first draft of that - we've basically got a fully functional backend system, although I don't think we've any plans of taking it further.
I don't know if you've looked at the SVG we have on the blog, but its a pretty useful way of looking at this data, even as it stands, with hyperlinks to the relevant blockexplorer blocks.
There's probably some clever way to express the general problem in information theory terms and prove that any set of data with certain characteristics must be de-anonymizable to some given extent. 6 billion people in the world is still just about 33 bits to uniquely identify an individual (and of course generally we're not talking global population), and so even a very small number of bits that can be correlated back to the real world in arbitrarily clever ways will reveal real-world identities in a putatively anonymous data set. It wouldn't take much to clean that up into a mathematically rigorous statement; no matter how you slice it, low tens of bits will tend to identify people and that's a low threshold.
Some academic with too much time on his hands wrote an entire Ph.D thesis on that very idea [hint: me :-)] http://33bits.org/about/
I'm browsing through there and see you've got good coverage on HN already. Is your thesis available publicly anywhere? I'd be interested in reading the full-strength version.
The rest of my thesis is (almost literally) a concatenation of several of my papers, most of which I've covered on my blog; a quick list is here: http://randomwalker.info/publications/
What bitcoin is about, however, is about the feasibility to have pseudonymous entities that can't be traced to real persons, yet trade online commodities and services. Take lulzsec fot instance : they accepted BTC donations and could spend them to buy web hosting, to make donations to various associations, or to simply buy services from anyone accepting bitcoins.
Right now, the anonymity is lost as soon as BTC is converted into a regular currency, but as long as it stays in the BTC network, the account is nothing more than a number (and an IP if you don't use a anonymisation network).
You could have pseudonymous software developers, writing code in exchange of hosting of gfx works, all of that happening in the gray legal area of international services exchanges. Today there are no way of creating a small international dematerialized company, which is a shame and a failure of international cooperation. Bitcoin could be a tool to address just that.
Thanks!
Bitcoins don't exist as independently tracked entities in the system, as such. Lets say an address with 10 unmarked Bitcoins receives 10 marked Bitcoins, such that its balance is now 20 bitcoins.
If it then sends 5 bitcoins to another addresses, it is not possible to make statements about what proportion of those 5 bitcoins were marked - the individual Bitcoins are not individually identified.
So, its more meaningful to think of balances getting transferred around, rather than Bitcoins.
What you can do, is the type of flow analysis we did, where you try and track the majority of flow in and out of addresses, and make inferences about how the Bitcoins flow around. As the network is currently used, this appears to work well - which is one of our main findings - but I'm sure this analysis, as we currently do it, could be frustrated by employing mixing of various types - especially if such mixing were done at a protocol level.
This still has other problems - you are then trusting the mixer to some extent, and I'm sure there are attacks that are possible where someone deploys a malicious mixer, or where someone constantly floods a mixer with coins under their control.
But that's not the point of Bitcoin's anonymous capabilities. The relative ease which you can create multiple wallets and keep your questionable Silk Road and Wikileaks donation purchases separate, as opposed to creating multiple offshore bank accounts in Switzerland, can establish a high degree of anonymity. Almost like how drug dealers use prepaid cell phones and discard them for new ones the moment they suspect something is compromised.
Once this system had a few users, the difficulty of tracing any particular wallet 'owner' would be significant.
I suspect that "random" in this instance would have to be very carefully defined, as a lot of signals only become more apparent (to the human eye) when cloaked with the right type of noise.
"The main problem is that every transaction is publicly logged. Anyone can see the flow of Bitcoins from address to address (see first image). Alone, this information can't identify anyone because the addresses are just random numbers. However, if any of the addresses in a transaction's past or future can be tied to an actual identity, it might be possible to work from that point and figure out who owns all of the other addresses. This identity information might come from network analysis, surveillance, or just Googling the address. The officially-encouraged practice of using a new address for every transaction is designed to make this attack more difficult."
Not that you are saying they claimed otherwise and it is exactly your article that made me look through this page in detail, so thanks for that.
We actually wrote a sentence in our paper addressing this: "While there is an under- standing amongst Bitcoin’s technical users that anonymity is not a prominent design goal of the system, we believe that this awareness is not shared throughout the community."
Also, there is a gap between 'might be possible to work from that point' and actually trying to do it; and it is this gap that a lot of Bitcoin users are counting on. The idea is out there that while it might be possible to tie things together in theory, its really not doable in practice.
The discussion mentioned on this blog, and the post its replying to, is an interesting example of the uncertainty that's out there, even among very tech savvy users: http://blogs.forbes.com/timothylee/2011/07/14/advanced-bitco...
So, we knew that Bitcoin didn't try make hard guarantees of anonymity, but we wondered how well analysis would work in practice; and it turned out to be work much better than we expected.
The problem of linking accounts, too, turned out to give us a lot more information than we think most people would have expected.
We aren't trying to claim any more than that - some people will read this and say 'huh, obvious' but we think a large number of people will also be surprised this practically worked - we were.
Hell its not even the digital equivalent of investing. It's just plain old investing. (Or speculating, you might say)
You should be familiar with the old tradeoff- safety (aka risk) vs reward. Traditional currencies do not fluctuate very much. Bitcoin does, and being a fledgling currency, has the potential to explode in value.
There has been some criticism of bitcoin's technical aspects. I just wanted to post a thought I've been having for the last week or two, given your great answer (perhaps you could respond):
If someone creates a better cryptocurrency than bitcoin, they should lock in a 1:1 exchange with bitcoin - so give 1 bitcoin and get 1 of the new currency back. At any time, one can recall bitcoins with the new currency at the same 1:1 rate. This way current bitcoin holders don't lose out to the new currency. There might be a minuscule commission to the creator.
One issue in uptake is trusting the issuer of this new currency to stick around to make good on their promise.
One weakness I see with bitcoin is speed of transactions across the network.
In addition I can securely store an encrypted file containing my private keys on several cloud services and access it from anywhere in the world. If done correctly, it is possible that no one knows that I have this asset until I try to cash it into a national currency.
That's just bitcoin itself. The bitcoin protocol opens up the possibility of all sorts of distributed and secure interactions, contracts or property titles for example. namecoin is a distributed DNS service based on this idea.
For example, it can be used to transfer wealth halfway across the globe in at least ten minutes.
Also, the network operated 24 hours 7 days a weeks, so you don't have to plan around banking holidays or banking time nonsense.
It is also used a store of wealth because the network put an upper limit on bitcoin money supply.
P.S. The concept of deposit insurances does not hold much meaning with Bitcoin. Deposit insurance applies to banks, which hold on to & handle your money. Bitcoin is money. Now, if a Bank of Bitcoin was founded, because maybe you are afraid your PC will get hacked, and you deposited BTC with them, then deposit insurance would be meaningful.
The bitcoin network doesn't do that, hence no need for FDIC. The apparent risks to the BTC network are that a malicious entity gains control of > 50% of the network's computing power and uses that to illegally modify the blockchain, or the network goes down. The network is so big now that only the largest botnets would have a hope of the former, and it would take a global calamity like a scorched earth world war, asteroid, or EMP from an intense solar flare to accomplish the latter.
It is one of the central ideas behind bitcoin and leaves no doubt about the anonymity of the transactions.
It is a well publicised idea and it is even mentioned on the main page of the bitcoin wiki (http://bitcoin.it).
The reason people think Bitcoin is anonymous is because they think that identities cannot be linked to the addresses involved in the public transactions.
When careful enough, bitcoin can be used anonymously. But the developers do not claim that it's anonymous by default, certainly not in the current mainline client. For example, the wiki page about anonymity:
https://en.bitcoin.it/wiki/Anonymity
Anonymity is not guaranteed. There are various initiatives under way to improve this. But people should stop thinking that anonymity is the single redeeming feature of bitcoin, anyway.
The moral of the story is still what it's always been, and it's a two-parter: 1) anonymity is only as anonymous as how you use it. And, because Bitcoin's transaction history is public, it's very very hard to use it truly anonymously. And 2) very few people go to even reasonable lengths to stay anonymous. For most, I simply doubt they think it's worth the effort - why anonymize legitimate use?