Source-linked AI summary
Bitcoin Transaction Graph Analysis
Michael Fleder, Michael S. Kester, Sudeep Pillai
TL;DR
The paper addresses whether Bitcoin’s public-key-based ledger provides meaningful anonymity. It annotates transactions with definitive or probabilistic links to real users, then analyzes the resulting graph to identify activity and user relationships; the authors conclude that the network is not entirely anonymous.
Problem
The paper investigates whether Bitcoin’s public ledger and cryptographic public-key identifiers provide user anonymity despite privacy concerns.
Method
The authors scrape public forums, probabilistically match imprecise transaction information, and analyze the annotated transaction graph to trace and cluster users.
Results
The bitcoin transaction network is not entirely anonymous, and forum users were linked to Silk Road nodes through a single intermediary and to known entities such as SatoshiDICE and Wikileaks.
Takeaways & Limitations
Publicly available forums and Bitcoin’s transaction ledger can be combined to associate public-key activity with real users and known entities.
Takeaways & Limitations
The threat model assumes access to public identity–address pairs and rough transaction information overheard from known users.
Abstract
from arXiv · showhide
Bitcoins have recently become an increasingly popular cryptocurrency through which users trade electronically and more anonymously than via traditional electronic transfers. Bitcoin's design keeps all transactions in a public ledger. The sender and receiver for each transaction are identified only by cryptographic public-key ids. This leads to a common misconception that it inherently provides anonymous use. While Bitcoin's presumed anonymity offers new avenues for commerce, several recent studies raise user-privacy concerns. We explore the level of anonymity in the Bitcoin system. Our approach is two-fold: (i) We annotate the public transaction graph by linking bitcoin public keys to "real" people - either definitively or statistically. (ii) We run the annotated graph through our graph-analysis framework to find and summarize activity of both known and unknown users.
2 Contributions
The paper contributes a two-part transaction-graph annotation system and a graph-analysis framework for tracing and clustering user activity.
- The annotation system scrapes bitcoin addresses from public forums and matches users to transactions using incomplete information and matching probabilities.Imprecise timing and exchange-rate-dependent amounts are handled by generating candidate transaction matches.
- The graph-analysis framework traces and clusters user activity in annotated transaction data.
3 Background
Prior studies identify privacy limitations in Bitcoin through external information, transaction-graph analysis, and statistical investigation of user behavior and fund flows.
- Earlier work combined external information with context discovery and flow analysis to investigate an alleged theft.
- Other research analyzed transaction-graph statistics to study user behavior, spending and acquiring habits, and bitcoin flows between accounts.
4 Threat Model
The threat model concerns associating real names or usernames with blockchain transactions using publicly available web data and overheard, imprecise transaction details.
- The attacker’s goal is to associate numerous unrelated cryptographic IDs with a person’s true name, forum username, or other public identity.
- The attacker can scrape intentionally or unintentionally disclosed bitcoin addresses from forums, donation sites, and public social networks.
- The attacker may overhear rough transaction information, such as a named user sending approximately $100 in bitcoins around noon.
5 Implementation
The implementation extracts blockchain transactions, builds transaction graphs, and uses web scraping to connect public bitcoin addresses with forum users.
- The system investigates statistical and definitive approaches to revealing bitcoin user activity from publicly available transaction information.
- The blockchain was parsed with Armory and wrapper classes that extracted information needed to construct the transaction graph.
- 5.1.2 Web Scraping: Forum signatures create an attack vector because users publicly attach bitcoin addresses to posts while seeking tips.
- 5.1.2 Web Scraping: Scrapy crawled bitcointalk.org breadth-first, matched likely addresses with a regular expression, and validated them using Bitcoin’s built-in checksum.
- 5.1.2 Web Scraping: In just under 30 hours, scraping covered 44,086 pages and 89,088 posts, yielding 2,322 users and 2,404 validated addresses.
5.2 Transaction Fingerprinting
Transaction fingerprinting tests how many blockchain transactions remain plausible when only approximate time and USD value are known. The resulting ambiguity increases as Bitcoin trading becomes more frequent.
- The method matches blockchain transactions against windows of approximate time and USD value.The motivating example uses an imprecise report such as sending $100 at noon yesterday.
- For every blockchain transaction, the analysis varies time and USD windows to count matching candidate transactions.The figure reports the average number of matches for given window sizes.
- 1/10 is the example probability assigned to identifying Bob’s public key when the conversation occurred in March 2012.These probabilistic annotations can supplement transaction matching and web-scraped identity data.
5.3 Graph Analysis
The graph-analysis framework converts blockchain records into transaction and user graphs, then combines graph structure with web-scraped annotations to investigate identities and activity.
- 5.3 Graph Analysis: The framework de-anonymizes users using scraped Bitcoin forum information and transaction data.Its components are summarized in the graph-analysis pipeline.
- 5.3.1 The Transaction Graph: The transaction graph is directed: nodes are public addresses and edges represent transactions from source addresses to target addresses.For October 25, 2013, it contains 89,806 transactions and 80,030 unique vertices.
- 5.3.2 The User Graph: The user graph groups public-key addresses into users or entities and links multi-input transactions as originating from the same user.This proxy directed graph supports analysis of user-level activity.
- 5.3.2 The User Graph: Figure 6 presents an entity graph for October 25, 2013 with the top 30 PageRank nodes, including communities, single entities, and large-volume transactions.A significant set of users remains untraceable.
5.4 Page Rank
PageRank guides investigation toward prominent users in the directed user graph by favoring nodes that receive substantial traffic and are easily reached.
- PageRank ranks user-graph nodes by importance, prioritizing nodes that receive enough traffic to be easily reached.The authors use this ranking to select interesting users for linkage with known forum users.
5.5 User De-anonymization
Graph analysis highlights prominent transaction activity and combines those findings with web-scraped identities to trace relationships among known entities and forum users.
- 445 transactions transferred exactly 324 Bitcoins from Silk Road entities to a publicly known FBI address.The FBI address was identified as a high-PageRank user by the graph algorithm.
- The analysis backtracked one hop from Silk Road transactions to uncover Bitcoin forum users connected through an intermediary.The analysis covered transactions from March 25 through October 25, 2013.
- The graph also identified direct transactions from multiple forum users to SatoshiDICE and from a few forum users to Wikileaks.The paper says these links may indicate gambling, dealing, support, or interaction.
- Figure 7 shows top PageRank nodes, their first-order edges, and annotations from web-scraped results.The Silk Road seizure is one of the noticeable activities involving highly ranked nodes.
6 Conclusion
Public forums and Bitcoin’s transaction ledger together reveal that the Bitcoin transaction network is not entirely anonymous, including links to Silk Road nodes and known entities.
- Public forums and the transaction ledger show that Bitcoin is not entirely anonymous.
- Forum users were tied to original Silk Road nodes through only a single intermediary.
- Transactions directly linked scraped forum users with SatoshiDICE and Wikileaks, implying possible dealings, support, or interaction.