This is very nice work, thank you. I've only had time to skim the paper; pardon me if these questions are answered therein:
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?
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!
"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,"
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.
One assumption that the post (and I assume the paper as well) makes is that there _was_ a thief. It is entirely possible that one user played both the victim and the thief in this story.
We are aware that this is an assumption.
We refer to the 'alleged thief' at several points in our paper, and I mention this in the blog comments.
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.
How much time (in hours) would law enforcement spend to perform this similar analysis technique? Or would this become trivial if a system that performed analysis continuously were built?
I honestly don't know how long it would take them. It would very much depend on their technical sophistication, their experience with writing network analysis code, etc.
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.
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.