UCSD - University of California - San Diego
12/12/2024 | Press release | Distributed by Public on 12/12/2024 17:07
UC San Diego Computer Scientists Earn IMC Test of time Award for Pivotal Bitcoin Crime Fighting Research
Published Date
December 12, 2024Story by:
Media contact:
Share This:
Article Content
When Bitcoin launched in 2009, the virtual currency was heralded as virtually untraceable - an alarming prospect for crimefighters - until a team of computer scientists at the University of California San Diego devised a clever tracing technique that could in fact follow the money.
Nearly a decade later, the team led by Sarah Meiklejohn, then a PhD student in the Jacobs School of Engineering's Department of Computer Science and Engineering, is still credited with shedding light on the structure of the Bitcoin economy and how it is used. Their 2013 paper, "A Fistful of Bitcoins: Characterizing Payments Among Men with No Names," was recognized with a Test-of-time Award at the Association for Computing Machinery's Internet Measurement Conference (IMC) 2024 held recently in Madrid, Spain.
The story behind the paper and its impact on cybercrime was chronicled in a 2024 book, Tracers in the Dark: The Global Hunt for the Crime Lords of Cryptocurrency,by award-winning author and veteran cybersecurity reporter Andy Greenberg. Several chapters recounting Meiklejohn's pivotal role in tracing these illicit transactions were featured in a WIRED magazine article, "How a 27-Year-Old Codebreaker Busted the Myth of Bitcoin's Anonymity," also by Greenberg.
Sarah Meiklejohn was a computer science PhD student when the revolutionary paper "A Fistful of Bitcoins: Characterizing Payments Among Men with No Names"was published. Meiklejohn and the research are featured in a book and an article in WIRED by veteran cybersecurity reporter Andy Greenberg.
Greenberg links Meiklejohn's study to some of the largest dark-web takedowns in history, helping to uncover drug rings, cryptocurrency heists, and money launderers.
Meiklejohn (PhD '14) and Stefan Savage, a computer science professor and the paper's senior author, accepted the IMC award on behalf of their co-authors, which include CSE Professor Geoffrey M. Voelker, CSE alumni Marjori Pomarole (B.S. '13) and Kirill Levchenko (PhD '08), Grant Jordan who took CSE graduate courses, and Damon McCoy, a former CSE post-doctoral scholar.
Revealing Bitcoin's True Nature
At one time, it was assumed that Bitcoin would be untraceable, enabling the sale of contraband with complete impunity. The research by Meiklejohn and her co-authors decisively quelled that misapprehension and illuminated the currency's unexpected transparency - for those who know where and how to look.
In their groundbreaking paper, the researchers analyzed Bitcoin's unique characteristics, the longitudinal changes in the Bitcoin market, the stresses these changes would place on the system, and whether Bitcoin would prove highly attractive for criminal or fraudulent activities. Within that broad scope, the team empirically tested whether Bitcoin payments were truly anonymous. They weren't.
"Bitcoin has the unintuitive property that while the ownership of money is implicitly anonymous, its flow is globally visible," the authors wrote in their paper.
From the vantage point of 2024, an era where cryptocurrency is a widely-traded commodity, this statement might sound unremarkable. But in 2013, Meiklejohn's findings shattered preconceptions surrounding the burgeoning cryptocurrency and enabled law enforcement to trace Bitcoins through a seemingly impenetrable web of global transactions into the dark underworld of cybercrime.
Tracing Bitcoin Through Time
Bitcoin was initially introduced in response to a growing demand for low friction e-commerce. The proliferation of online payment systems in the early 2000s included eWallets, like Paypal, direct debit systems, and money transfer systems. Apart from Bitcoin, these payment options utilized existing fiat currencies, like dollars and cents, and were administered by a central controlling agency, which could explicitly identify the parties tied to each transaction.
Figure, from the 2013 paper, shows the main players in the Bitcoin landscape. In (1), a user wishing to deposit Bitcoins into a bank receives a public key, or address, belonging to the bank. In (2), the user incorporates both his own public key and the one sent to him by the bank into a transaction, which he then broadcasts to his peers. In (3), the transaction floods the network. In (4), the transaction is eventually received by a miner, who works to incorporate the transaction into a block. In (5), this block is then flooded through the network, and in this way is incorporated into the global block chain. The Bitcoins now belong to the public key of the bank, and have been successfully deposited.
Bitcoin reshaped the e-commerce model. As a purely online virtual currency, it was unbacked by either physical commodities or sovereign obligation and operated without central administration. Instead, it relied on a combination of cryptographic protection and a global peer-to-peer network of participants to validate and certify all transactions.
The physical items the researchers purchased with bitcoins (from the 2013 paper "A Fistful of Bitcoins: Characterizing Payments Among Men with No Names").
This decentralized accounting requires each network participant to maintain the entire transaction history of the system. Back then, this amounted to over 3GB of compressed data, which is precisely what Meiklejohn downloaded to a desktop in a computer science lab to begin her analysis.
"Our approach is based on the availability of the Bitcoin blockchain: a replicated graph data structure that encodes all Bitcoin activity, past and present, in terms of the public digital signing keys party to each transaction," she and her co-authors wrote.
The blockchain refers to a series of transactions, each one referencing the previous transaction, to form a chain. Think of it as a series of interconnected crochet stitches forming the first row of a blanket. Much like adding rows to this imaginary blanket, transactions are then grouped into blocks, with each block referencing the previous one and serving as a timestamp that validates the transactions it contains. Blocks are then formed into chains and made publicly available to every user within the system.
Meiklejohn and her fellow researchers developed a new clustering heuristic, or systematic method of associating data, to comb through the massive database of blockchain transactions and link transactions. Their algorithms put Bitcoin's anonymity claims to the test.
"Our work seeks to better understand the traceability of Bitcoin flows and, through this understanding, explore the evolution of how Bitcoin has been used over time," they said.
The team built on past efforts to cluster public keys, or Bitcoin user addresses, based on evidence of shared spending authority. Once they could positively identify one public key, they could link an entire cluster of transactions containing that same public key.
They also employed a re-identification attack. Essentially, they opened accounts and made purchases from a broad range of Bitcoin merchants and service providers. Since they were at one end of the transaction, they could positively identify the other end as the service provider.
Employing this meticulous methodology, Meiklejohn was able to follow the money, or Bitcoins, through a seemingly impenetrable web of 16 million transactions and 12 million public keys to their online sources. Her novel tracing technique eventually led law enforcement to user addresses of criminals. With a subpoena in hand, officials could put a name to the crime. Today, variants of these algorithms are in daily use in both government enforcement and private sector compliance roles, supported by a range of crypto tracing companies including Chainalysis, Elliptic, TRM Labs, and CipherTrace (now part of Mastercard).
Today, Meiklejohn is a professor in cryptography and security at University College London (UCL) and a staff research scientist at Google.
Levchenko is an associate professor in electrical and computer engineering at the University of Illinois; McCoy is a professor at New York University Tandon School of Engineering; Jordan is the founder and CEO of anti-drone startup, SkySafe; and Pomarole is an investor and consultant for Brazilian tech startups .
IMC 2024 is the 24thin a series of flagship conferences sponsored by ACM SIGCOMM, a professional forum for the discussion of topics in the field of communications and computer networks. This three-day event focuses on Internet measurement and analysis in areas such as technical design and engineering, regulation and operations, and the social implications of computer networking.