PaperlayerView exact revision on arXiv

Source-linked AI summary

An Analysis of Anonymity in the Bitcoin System

Fergal Reid, Martin Harrigan

arXiv:1107.4524v2physics.soc-phcs.SI

TL;DR

Bitcoin’s public transaction record creates a tension between pseudonymous keys and practical anonymity. The paper analyzes transaction and user networks, combines them with external and flow-based information, and shows that many keys and user activities can be linked through passive analysis.

  • Problem

    The paper addresses the lack of public evidence about whether Bitcoin’s pseudonymous design provides practical anonymity against determined analysis.

  • Method

    The paper constructs transaction and user networks from Bitcoin’s public history and combines them with external information, context discovery, flow analysis, and temporal analysis.

  • Results

    Many public keys can be associated with one another and with external identifying information, enabling detailed observation of known users through passive analysis.

  • Takeaways & Limitations

    Bitcoin users should not assume that generating multiple public keys or using pseudonymous identifiers guarantees anonymity against analysis of the public transaction history.

  • Takeaways & Limitations

    The case-study analysis is circumstantial and cannot establish with certainty whether flows indicate shared agency in both incidents.

Abstract

from arXiv · show

Anonymity in Bitcoin, a peer-to-peer electronic currency system, is a complicated issue. Within the system, users are identified by public-keys only. An attacker wishing to de-anonymize its users will attempt to construct the one-to-many mapping between users and public-keys and associate information external to the system with the users. Bitcoin tries to prevent this attack by storing the mapping of a user to his or her public-keys on that user's node only and by allowing each user to generate as many public-keys as required. In this chapter we consider the topological structure of two networks derived from Bitcoin's public transaction history. We show that the two networks have a non-trivial topological structure, provide complementary views of the Bitcoin system and have implications for anonymity. We combine these structures with external information and techniques such as context discovery and flow analysis to investigate an alleged theft of Bitcoins, which, at the time of the theft, had a market value of approximately half a million U.S. dollars.

1.1 Introduction

Bitcoin’s anonymity is contested because its public transaction history may enable users and transactions to be linked. This chapter investigates those limits using network analysis and external information while avoiding broader economic questions.

  • 1.1 Introduction: Bitcoin users are identified by public keys, while the user-to-key mapping is kept locally and users may generate many keys.These design choices are intended to impede attempts to associate public keys with real users.
  • 1.1 Introduction: Before this work, no public analysis substantiated or refuted claims about Bitcoin’s practical anonymity.User views ranged from treating Bitcoin as insufficiently anonymous to advertising it as suitable for anonymous donations.
  • 1.1 Introduction: The central question is whether determined analysis can associate donations or other transactions with the same user or with external identifying information.The chapter frames this as a test of the anonymity implied by one-time public keys and other usage practices.
  • 1.1 Introduction: The study constructs transaction and user networks from public transaction history and examines their static and dynamic properties.It also combines external information with flow and temporal analysis to study information leakage and de-anonymization.
  • 1.1 Introduction: The analysis aims to describe inherent limits to Bitcoin anonymity rather than de-anonymize individual users generally.Economic aspects of Bitcoin are explicitly outside the chapter’s scope.

1.2 Related Work

Prior work spans electronic-currency mechanisms and anonymity attacks in networked or online data. The chapter positions Bitcoin network-structure analysis as an unstudied area within electronic currencies.

  • 1.2 Related Work: Electronic currencies can be classified by ownership, double-spending protection, anonymity or privacy, and currency-generation mechanisms.Bitcoin is highlighted for using proof of work both to establish transaction consensus and to mint currency.
  • 1.2 Related Work: Existing electronic-currency systems differ in trust, issuance, and transaction-validation arrangements, including Ripple, i-WAT, KARMA, and PPay.The examples range from trusted intermediary chains to distributed central authority and peer-to-peer micropayments.
  • 1.2 Related Work: The authors report no known studies of the network structure of electronic currencies before this chapter.This stated gap motivates analyzing Bitcoin’s publicly available transaction network.
  • 1.2 Related Work: Studies of physical currencies have analyzed transaction-flow networks and currency movement using recorded certificates or bill serial numbers.Reported findings include power-law degree distributions, small-world properties, and the significance of transaction direction and value.
  • 1.2 Related Work: Prior privacy research shows that network structure, co-occurrences, and information from multiple sources can identify pseudonymous users.Examples include attacks on social networks and Netflix data using network or external-content information.

1.3 The Bitcoin System

Bitcoin is a decentralized electronic currency whose public transaction history supports consensus and prevents double-spending. Its transaction structure and key reuse or co-use provide the basis for two network representations.

  • 1.3 The Bitcoin System: Bitcoin has no central authority, issuer, central bank, or fractional-reserve system, and its eventual supply is designed to reach 21 million coins.Coins are generated at a predictable rate rather than issued by a central institution.
  • 1.3 The Bitcoin System: Users transfer Bitcoins by publicly declaring that previously assigned funds controlled through public-key cryptography should be reassigned to other identities.At least one receiving identity is controlled by the intended recipient.
  • 1.3 The Bitcoin System: Participants validate transactions by appending them to a collectively agreed public blockchain through repeated cryptographic hash computations.The computation requires a transaction digest, other pending transactions, and a nonce to satisfy a specific form.
  • 1.3 The Bitcoin System: The complete transaction history is publicly available because validating transactions and preventing double-spending requires awareness of previous transactions.This public record is the first of three system features central to the chapter’s analysis.
  • 1.3 The Bitcoin System: Multiple inputs and outputs, together with public-key reuse and co-use, support transaction and user network structures.Edges represent input-output relationships between users and carry Bitcoin values and timestamps.
  • 1.3 The Bitcoin System: The dataset covers 1,019,486 transactions involving 1,253,054 unique public keys from 3 January 2009 through 12 July 2011.The history was gathered using the Bitcoin client and a modified bitcointools project.

1.4 The Transaction and User Networks

The chapter constructs transaction and user networks from Bitcoin’s public transaction history, then characterizes their structure and dynamics. Contracting public-keys into users provides a complementary, incomplete proxy for relationships among Bitcoin users.

  • The Transaction Network: The transaction network T models Bitcoin flows between transactions, with vertices as transactions and directed, valued, timestamped edges linking outputs to later inputs.T is a directed acyclic graph because a transaction’s output cannot ultimately become an input to itself.
  • The Transaction Network: 974 520 vertices and 1 558 854 directed edges comprise T after excluding transactions not connected to another transaction.The omitted transactions correspond to newly generated Bitcoins and unredeemed transaction fees.
  • The Transaction Network: 948 287 vertices (97.31%) lie in T’s giant weakly connected component, which contains a giant biconnected component of 716 354 vertices (75.54%).T has 1 949 maximal weakly connected components overall.
  • The Transaction Network: T’s monthly analysis shows network growth and sparsification, with anomalies in average path length during July and November 2010.The measurements track edge number, density, and average path length and are not cumulative.
  • The User Network: The user network U contracts public-keys inferred to belong to the same user, representing Bitcoin flows between users while remaining incomplete.Multi-input transactions link input public-keys, and the resulting network can serve as a proxy for Bitcoin users’ social network.
  • The User Network: 881 678 vertices and 1 961 636 directed edges comprise U after preprocessing; unlike T, U contains multi-edges, loops, and directed cycles.The preprocessing identifies 86 641 non-trivial ancillary-network components and 795 037 isolated vertices.
  • The User Network: 879 859 vertices (99.79%) lie in U’s giant weakly connected component, which contains a giant weakly biconnected component of 652 892 vertices (74.20%).U has 604 maximal weakly connected components and 579 355 maximal strongly connected components.

1.5 Anonymity Analysis

The user network exposes anonymity risks through its topology, external identifiers, and dynamic transaction analysis. Publicly available services and user disclosures can connect public-keys to off-network information and reveal related users.

  • Network structure: The user network has considerable cyclic structure rather than primarily representing tree-like flows between unlinkable one-time public-keys.This structure is considered alongside other Bitcoin features to assess anonymity.
  • Network analysis: Global degree distributions, local interaction context, and dynamic flow or temporal properties provide several ways to infer information about users.These analyses examine outliers, direct or indirect relationships, and significant Bitcoin flows.
  • External information: A partial user directory combining known public-keys with off-network information can create a serious threat to anonymity when combined with network structures.Bitcoin has no user directory, so the proposed directory is necessarily partial.
  • External information: Organizations holding email, shipping, financial, or IP data may expose identities connected to related Bitcoin transactions when that information is public or accessible to law enforcement.The relevant organizations include stores, exchanges, laundry services, and mixers.
  • Bitcoin Faucet: A Bitcoin Faucet publishes recent giveaways and recipients’ IP addresses, enabling recipient public-keys to be associated with IP addresses when distributions are not batched.Scraping the page over time produces a time-stamped mapping of IP addresses to users.
  • Bitcoin Faucet: Many Faucet-recipient public-keys were connected to other public-keys in the ancillary network, while a one-week visualization mapped related users to geolocated IP addresses.Edges between mapped IP addresses represented user-network paths of length at most three that excluded the Faucet vertex.
  • Scope boundary: Large centralized Bitcoin service providers can produce much more detailed maps than this small publicly available proof-of-concept dataset.The passage explicitly limits the figures to a proof-of-concept from a small public data source.
  • Voluntary disclosure: Publicly disclosed public-keys are searchable, and many high-degree vertices were identified using search engines, forums, Twitter, and user-generated directories.The ancillary network can link disclosed public-keys to other public-keys belonging to the same user.

1.5.2 TCP/IP Layer Information

Bitcoin’s TCP/IP layer can leak associations between network addresses and public-keys. A passive peer-connection strategy was used to investigate this identity leakage.

  • TCP/IP-layer leakage: Opening connections to all public peers can map IP addresses to Bitcoin public-keys by observing which node first informs the observer of a transaction.The approach assumes the first informing node is more or less the transaction source, and becomes absolutely so over time, according to the cited analysis.
  • TCP/IP-layer leakage: The method investigates identity leakage at the TCP/IP layer rather than relying only on transaction-network structure.It works from peer-to-peer transaction propagation behavior.
  • Source inference: Transaction-source inference is based on the timing of peer notifications, with the first informing node treated as the likely source.The cited assumption is explicitly qualified as becoming stronger over time.

1.5.3 Egocentric Analysis and Visualization

Network-derived balances and transaction histories support egocentric visualizations of Bitcoin users and entities. These views connect identified vertices to donation flows and expose temporal transaction patterns.

  • User-level quantities: Balances can be computed for individual public-keys and aggregated across public-keys linked through the ancillary network.This permits user-level financial summaries even when activity spans multiple public-keys.
  • Transaction histories: WikiLeaks’ public-key received relatively small donations that were periodically forwarded to other public-keys, with a noticeable initial spike.The analysis reports both Bitcoin amounts and transaction counts for receipts and payments.
  • Egocentric visualization: The network surrounding WikiLeaks’ public-key resolves several vertices using identifying information, linking those users directly or indirectly to donations.The visualization focuses on the incomplete user network.

1.5.4 Context Discovery

Context discovery combines network structure, shortest paths, flow capacities, and external information to connect users and investigate the alleged theft. The case analysis identifies transaction relationships around the thief, victim, Slush, and LulzSec-related vertices.

  • Context discovery: Shortest paths and maximum-flow calculations can characterize Bitcoin movement between users of interest within selected time windows.Maximum flow uses transactions and their capacities to constrain possible movement.
  • Case Study – Part I: The case study analyzes an alleged theft of 25 000 BTC after the victim’s Slush pool account payout address was changed.The reported market value at the time was approximately half a million U.S. dollars.
  • Egocentric analysis: The egocentric network includes vertices reachable from the thief within two undirected steps, while removing loops, multiple edges, and edges outside biconnected components.The resulting visualization centers on the thief and includes induced edges among retained vertices.
  • Network structure: The victim and thief were connected by paths other than the theft edge, including a cycle involving the thief, victim, and three other vertices.Vertices representing public-keys belonging to the same user were contracted before attaching Bitcoin values and timestamps to directed edges.
  • External identification: Off-network data identified the purple vertex as the main Slush pool account and the orange vertex as the LulzSec computer, while the thief sent 0.31337 BTC to LulzSec shortly after the theft.The passage states that the LulzSec identification was established before the theft, whereas a separate attempted association with the thief was fake.
  • Transaction context: The main Slush pool account sent 441.83 BTC to the victim over 70 days and 0.2 BTC to the yellow vertex over two days; the yellow vertex sent 0.120607 BTC to LulzSec one day before the theft.The yellow vertex represented a user owning at least five public-keys and connected to both the Slush pool and LulzSec through reported activity.

1.5.5 Flow and Temporal Analyses

Flow and temporal analysis traces Bitcoin movements across accounts and public-keys, revealing complex splitting, merging, rapid transfers, and patterns that can support de-anonymization hypotheses.

  • Flow tracing: The tool traces significant Bitcoin flows over time from a chosen vertex or set of vertices when transfers are large relative to estimated balances.It identifies transfers shortly after receipt as interesting flow events.
  • Case study: More than 34 100 public-keys had received portions of the stolen Bitcoins, motivating an exhaustive-list alternative to the visualization tool.The victim had developed a tool to generate this list, which grew very quickly.
  • Case study: The theft-related flows begin with shuffling among a small number of accounts, followed by four significant outflows that split, recombine, and continue across subsequent accounts.Flows 1 and 2 began at 20:55 and 20:13, while flows 3 and 4 describe later recombination and continuation.
  • Case study: Small transfers from Flow 3 reached unseen public-keys pk1 and pk2 about seven minutes apart, followed by simultaneous transfers from Flow 4 to pk3 and pk4.The four public-keys received Bitcoins from two flows that had split two days earlier.
  • Additional flow patterns: Flow Y moved Bitcoins through thirty unique public-keys, typically siphoning off 30 BTC at each step before transfers to a MyBitcoin-operated public-key.That public-key had previously been involved in another separate Bitcoin theft.
  • Temporal analysis: Many flows transferred Bitcoins between public-keys very quickly, with intermediate parties waiting for very few confirmations before retransmitting them.Figure 1.14 highlights two such flows.
  • Interpretation: The analysis is circumstantial and cannot establish with certainty that the flows in both incidents were controlled by a shared agency.The tool generates hypotheses and suggests centralized services may hold further identifying details.

1.5.6 Other Forms of Analysis

The paper identifies additional transaction-pattern and external-data analyses that may link public-keys to users and reveal information about Bitcoin activity.

  • Transaction analysis: Two-output transactions may reveal which output is payment and which is change, allowing a change public-key to be mapped back to the transaction’s creator.This inference can use assumptions about the client implementation and access to its source code.
  • External information: The paper also points to order books for Bitcoin exchanges as another source of information for de-anonymization analysis.

1.5.7 Mitigation Strategies

The paper describes client-level mitigations intended to reduce unintended links among Bitcoin public-keys, while noting that these protections involve costs.

  • Client changes: A patched Bitcoin client can alert users to potential public-key links through its user interface.
  • Client changes: The client may also automatically proxy Bitcoins through dummy public-keys, but this approach incurs a cost.

1.6 Conclusions

Bitcoin’s publicly available transaction history enables network analysis that can associate public-keys with one another and with external identifying information. The conclusions emphasize that passive analysis can expose substantial activity, so casual users should recognize the system’s limited anonymity.

  • System trade-off: Bitcoin’s decentralized, trusted-third-party-free transfers come with the price that the entire transaction history is publicly available.
  • De-anonymization: Appropriate network representations can associate many public-keys with one another and with external identifying information using passive analysis alone.Active analyses and centralized exchanges or wallet services may reveal even more user activity.
  • User implications: Casual users should recognize that strong anonymity is not a prominent Bitcoin design goal, especially when sending Bitcoins to parties they would not want publicly associated with them.
Loading 1107.4524v2…