Sarah Meiklejohn discusses "A Fistful of Bitcoins" (cacm.acm.org/magazines/2016/4/200174), a Research Highlights article in the April 2016 Communications of the ACM.
00:00 On a dark night, cash tells no tales. But on the internet your enemies can follow you, bitcoin the only friend who'll keep your secrets. But how good a friend is bitcoin?
00:14 Join us as Sarah Meiklejohn shows us how this cryptocurrency can betray your secrets, in "A Fistful of Bitcoins".
00:23 [Intro graphics/music]
00:31 Bitcoin originated in January of 2009, just as Sarah Meiklejohn was finishing her master's degree. But while she was making a name for herself, others turned to bitcoin to obscure their own names.
00:46 DR. MEIKLEJOHN: Bitcoin, as I mentioned, uses these addresses. And these addresses are basically pseudonyms, and moreover they're pseudonyms that are in no way tied to the real identity of the person controlling them. ... So one user in the system can operate using many different pseudonyms.
01:02 Criminals exploited this pseudo-anonymity. But while she was a Ph.D. student at the University of California, San Diego, Dr. Meiklejohn and her colleagues developed heuristics to uncover these criminals' identities. The first: Input address clustering.
01:17 DR. MEIKLEJOHN: Transactions don't just have one input and one output: They can have many inputs and many outputs, O.K.?. ... So that the sender in a transaction needed to know all the secret keys for all of the input addresses, so it must be the same person.
01:37 This method collapsed over 12 million addresses down to about four million. Then they applied another heuristic that went much further: change address clustering.
01:47 DR. MEIKLEJOHN: So this one was based on the way that you make change in bitcoin. ... You know, it's not physical, there's no way for them to give you a five back. ... So what you do is you actually create a transaction with two outputs, basically: One output is their fifteen, and one output is your five.
02:05 At the time, these "change addresses" were usually temporary, used only once more to spend your change.
02:13 DR. MEIKLEJOHN: So basically, any address that was in the output of a multi-output transaction, that had only ever been used once, we suspected was a change address.
02:24 They tracked how these change addresses were spent over multiple hops, and could then cluster even more addresses together. But whose addresses were they? That they learned from some undercover work.
02:34 DR. MEIKLEJOHN: We did sort of this whole slew of our own transactions. ... And this was our way of generating even some small, minimal amount of ground truth data, right? We could definitively say, "This address, or these, you know, 30 addresses definitely belong to Mt. Gox because we saw it with our own eyes."
02:52 Combining these transactions with their heuristics, the researchers unmasked many bitcoin addresses that were held by this now-defunct currency exchange.
03:02 DR. MEIKLEJOHN: And so now, whereas before we had one or two or 30 addresses that we were sure belonged to Mt. Gox, we now could bootstrap and have 200,000 addresses that we were reasonably sure belonged to Mt. Gox.
03:16 Changes in the bitcoin world have made both heuristics less safe than they were when the team did its research. Still, Dr. Meiklejohn believes their work could be a model for future heuristics.
03:27 DR. MEIKLEJOHN: So it would definitely be a little more complicated today, I think. At the same time, if you used sort of a more-flexible solution like machine learning or something like that, you could probably more easily adapt to these kind of approaches.
03:43 Find out more in the Research Highlights article, "A Fistful of Bitcoins", in the April 2016 issue of Communications of the ACM.
03:52 [Outro and credits]