PaperlayerView exact revision on arXiv

Source-linked AI summary

Deanonymisation of clients in Bitcoin P2P network

Alex Biryukov, Dmitry Khovratovich, Ivan Pustogarov

arXiv:1405.7418v3cs.CR

TL;DR

The paper asks whether Bitcoin pseudonyms can be linked to transaction-generating IP addresses when users are behind NATs or firewalls. It identifies clients through their outgoing connections and transaction-propagation behavior, achieving substantial deanonymization with limited resources, including against Tor users. The authors also propose countermeasures and describe scope limitations in topology discovery.

  • Problem

    Existing transaction-graph methods do not generically connect Bitcoin pseudonyms to users’ actual identities, while ordinary attackers’ ability to identify clients behind NAT remains unclear.

  • Method

    The attack learns each client’s entry-node set, then matches those identifiers and transaction-arrival patterns to recover public IP addresses and distinguish users sharing a NAT.

  • Results

    59.9% of transactions were correctly linked to corresponding IP addresses in experiments, while the paper reports rates up to 60% with slight network denial of service.

  • Takeaways & Limitations

    Tor does not necessarily prevent the attack, and rotating or randomizing entry nodes is proposed as a countermeasure.

  • Takeaways & Limitations

    Topology discovery cannot reveal connections to nodes that do not accept incoming connections, such as peers behind NAT.

Abstract

from arXiv · show

Bitcoin is a digital currency which relies on a distributed set of miners to mint coins and on a peer-to-peer network to broadcast transactions. The identities of Bitcoin users are hidden behind pseudonyms (public keys) which are recommended to be changed frequently in order to increase transaction unlinkability. We present an efficient method to deanonymize Bitcoin users, which allows to link user pseudonyms to the IP addresses where the transactions are generated. Our techniques work for the most common and the most challenging scenario when users are behind NATs or firewalls of their ISPs. They allow to link transactions of a user behind a NAT and to distinguish connections and transactions of different users behind the same NAT. We also show that a natural countermeasure of using Tor or other anonymity services can be cut-off by abusing anti-DoS countermeasures of the bitcoin network. Our attacks require only a few machines and have been experimentally verified. We propose several countermeasures to mitigate these new attacks.

1. INTRODUCTION

Bitcoin users transact through pseudonyms, but existing graph-based methods do not generically connect those pseudonyms to users’ IP addresses. This paper introduces a practical network attack targeting clients, including users behind NATs or using Tor.

  • Motivation: Bitcoin pseudonyms identify transaction participants, while publicly visible transaction history can sometimes link multiple pseudonyms through graph analysis.These methods can occasionally map clusters to real identities but do not generically tie Bitcoin addresses to actual identities.
  • Motivation: The paper targets the unresolved problem of identifying transaction origins when clients are behind NATs or firewalls.Most peers are clients behind NAT and do not accept incoming connections, making their IP addresses difficult to obtain directly.
  • Approach: The method identifies clients by their outgoing entry-node sets and uses them to associate transactions with public IP addresses.The same identifier can distinguish clients sharing one public IP address and link pseudonyms used during a single session.
  • Results: 11% of all Bitcoin transactions can be deanonymized with a few machines and no more than 50 connections per Bitcoin server.The estimated cost for attacking the full network is under 1500 EUR per month.
  • Results: 60% deanonymization rates are possible when the attacker permits slight network denial of service, confirmed in Bitcoin test-network experiments.The fraction depends on how stealthy the attacker wants to remain.
  • Additional result: The paper also describes an alternative-blockchain strategy for lowering mining difficulty during severe hash-power declines.This extra result could serve either the Bitcoin community during unprofitable mining or malicious administrators seeking to disrupt the system.

2. BACKGROUND

Bitcoin’s operation is organized around a proof-of-work blockchain containing transaction data and cryptographic headers. Miners search header parameters for a valid hash, then broadcast completed blocks for peers to adopt.

  • Blockchain: Bitcoin maintains a blockchain whose blocks contain an 80-byte header and transaction data.The header includes the previous-block hash, timestamp, nonce, transaction-data hash, and difficulty parameter.
  • Proof of work: A block is valid only when the double-hash of its header is below a difficulty-dependent threshold.The protocol expresses this condition as Hi = SHA-256(SHA-256(...)) < f(di).
  • Mining: Miners exhaustively vary nonces, timestamps, and other parameters until they obtain a valid block header.Successful miners receive a reward transaction included at the beginning of the block’s transaction list.
  • Transactions: Payers and payees are represented by Bitcoin addresses derived from public keys, while transactions are signed with private keys and verified by participants.Miners later add signed transactions to the blockchain.

Bitcoin P2P network

The Bitcoin P2P network distinguishes reachable servers from clients behind NAT or firewalls, with peers maintaining persistent outgoing connections. Address and transaction propagation use connection-specific histories, deterministic responsibility, and randomized trickling.

  • Network roles: Bitcoin peers communicate over unencrypted TCP without authentication and track IP addresses associated with their connections.The protocol also uses penalties and 24-hour bans to limit denial-of-service behavior.
  • Network roles: About 90% of Bitcoin peers are clients behind NAT and maintain 8 outgoing connections to reachable servers.Servers accept incoming connections and can maintain up to 125 total connections.
  • Address propagation: Peers exchange addresses through GETADDR and ADDR messages, forwarding recent small address batches to selected neighbors.Messages with more than 10 addresses or timestamps older than 10 minutes are not forwarded.
  • Address propagation: Responsible neighbors for an address are selected by hashing the address, secret salt, current day, and neighbor data-structure address.The resulting ordering remains unchanged for 24 hours.
  • Trickling: Every 100 milliseconds, one randomly selected neighbor becomes the trickle node and its queued ADDR messages are transmitted.Random delays therefore accumulate across propagation hops.
  • Transaction propagation: Transactions are forwarded immediately to all 8 entry nodes when a hash test succeeds; otherwise queued transmissions wait for trickling.On average, 1/4 of transactions are forwarded immediately.

3. DISCONNNECTING FROM TOR

The attack can block Bitcoin connections through Tor by exploiting anti-DoS penalties, exposing clients’ actual IP addresses for the main deanonymization phase. The paper proposes proof-of-work-based connection costs as a countermeasure.

  • Operational trade-off: The authors note that the Tor-disconnection phase is noticeable, so a stealthy attacker may omit it and target only non-Tor users.This provides a practical scope boundary for the attack strategy.
  • Attack mechanism: Malformed messages can raise an IP address’s penalty score above 100, causing a 24-hour ban.The mechanism targets Tor exit-node addresses when clients connect through Tor.
  • Attack mechanism: The attacker can isolate a Bitcoin server from the Tor network by connecting through many Tor exit nodes and triggering bans.At the time described, this required 1008 connections and a few megabytes of traffic per server.
  • Proof of concept: The attack can be repeated across Bitcoin servers for 24 hours at the cost of about one million connections and less than 1 GByte of traffic.The paper reports a proof-of-concept isolation of its Bitcoin node from Tor exit relays.
  • Countermeasure: A proof-of-work requirement for connection initiation could preserve blacklisting while making Tor separation substantially more expensive.The proposed design uses a hash involving the IP, timestamp, and nonce with a specified number of trailing zeros.

4. LEARNING TOPOLOGY

The topology-learning phase infers clients’ outgoing Bitcoin connections by repeatedly advertising known addresses and observing which attacker-connected servers forward them. The inferred sets can identify clients, but propagation creates noisy entries and can fail when forwarding responsibilities change.

  • Learning entry nodes: Clients advertise their public address when connecting to entry nodes, allowing an attacker connected to those nodes to observe forwarded addresses.The attacker uses this behavior to learn subsets of each client’s entry nodes.
  • Learning entry nodes: The attacker connects to Bitcoin servers, logs forwarding servers for each advertised address, and repeats the procedure every 10 minutes.Repeated advertisements are intended to improve the chance that attacker nodes replace responsible forwarding nodes.
  • Noise sources: Forwarding through non-entry peers and staggered client connections introduce false entries into the observed entry-node subset.These are the two problems identified for the basic topology-learning procedure.
  • Assumption: Noise filtering assumes the client’s IP was previously used in Bitcoin or appears in a known address list, such as a major ISP range.The restriction method relies on prior knowledge of the address or its likely range.
  • Observed coverage: 35 connections to each potential entry node identify 4 entry nodes out of 8 on average when those nodes previously had 90 connections.The resulting fraction depends on the attacker’s number of connections.
  • Failure condition: The attack can fail if responsible forwarding nodes change, although the paper reports this event is likely to be rare when addresses are resent frequently enough.This is a stated operational limitation of the propagation-based inference method.

5. DEANONYMIZATION

The deanonymization attack builds a database linking client addresses to entry-node sets, then matches transaction propagation patterns against those sets. Three entry nodes are expected to uniquely identify a client, enabling session-level linkage of transactions even across unrelated pseudonyms.

  • Attack workflow: The attack collects servers, composes a target client list, learns clients’ entry nodes, and maps transactions to those nodes.The final output records an IP address or ISP, a client identifier for shared IPs, and the transaction pseudonym.
  • Client identification: Three entry nodes uniquely identify a client because collisions among entry-node tuples are unlikely in the estimated network topology.Two entry nodes also identify a large percentage of users.
  • Transaction mapping: The attacker matches each transaction’s first 10 forwarding servers against previously learned client entry-node subsets.The proposed procedure tests 3-tuples first, then 2-tuples and 1-tuples when necessary.
  • Estimated performance: 60% of testnet transactions were linked using 50 connections per server, while the pessimistic real-network estimate was 11%.The experiments obtained 6 of 8 entry nodes on average; the real-network estimate assumes fewer attacker connections.
  • Propagation basis: Transaction matching depends on entry nodes being among the first forwarders, because propagation through additional peers requires more messages, checks, and delays.The paper contrasts a four-message path through an entry node with a seven-message path through an intermediary peer.
  • Session linkage: The method uniquely identifies clients for a session and links transactions made with unrelated public keys that transaction-graph analysis could not connect.The session identifier is the client’s outgoing connection octet.
  • Countermeasure: Changing the client’s connection set after every transaction and adding random delay could prevent transaction linkage and distinguishability among clients sharing an ISP.The proposed countermeasure would not prevent learning the client’s ISP.

6. EXPERIMENTAL RESULTS

Testnet experiments evaluated both transaction propagation and the complete deanonymization procedure. The attack identified entry nodes reliably enough to link many transactions and connect transactions made by the same client during one session.

  • Experimental setup: The testnet contained 230–250 servers with an average node degree of approximately 30, and the experiments used 50 additional connections per server.The experiments imitated users sharing an ISP IP address and users connecting from different ISPs.
  • Experimental setup: The experiments generated 424 transactions, including 104 immediately forwarded transactions and 320 transactions using trickling.These two groups were compared in the first experiment.
  • Propagation results: 99% of immediately forwarded transactions and 70% of trickled transactions had at least 3 entry nodes among the first 10 forwarders.The first two forwarders were entry nodes for the majority of transactions.
  • Deanonymization results: 59.9% of all transactions were correctly linked to the corresponding IP address in the complete attack experiment.Each client was uniquely identified, with 6 entry nodes identified on average, and all same-session transactions were linked.
  • Deanonymization results: 41% of transactions were deanonymized when the attacker added only 20 additional nodes in a more conservative setting.This result shows reduced coverage with fewer attacker resources.

7. ANALYSIS

The analysis estimates how Bitcoin’s connection topology affects deanonymization, models false positives from changing connections, and reports attack success under practical connection limits.

  • 7. ANALYSIS: The attack’s success depends chiefly on the fraction of attacker connections among a client’s entry-node connections.Fewer entry-node connections give the attacker greater influence and a higher chance of deanonymizing the client.
  • 7. ANALYSIS: For n = 50 and m = 50, paddr = 0.75 and ptx = 0.50; for n = 90 and m = 35, paddr = 0.49 and ptx = 0.28.The adversary’s connections are limited by the default maximum of 125 connections per Bitcoin peer.
  • 7.1 Number of connections to servers: 60% of peers allow 50 connections or more, while 80% allow up to 40 connections.Additional connections may become available later as clients disconnect, allowing an attacker to retain established connections.
  • 7.2 Estimating false positives: The model uses connection-arrival and disconnection distributions to estimate whether client addresses reach non-attacker links after time Δt.The experiment collected 61,395 connections over 60 days and simulated 10,000 runs for each connection setting and Δt.
  • 7.2 Estimating false positives: Resending client addresses every 10 minutes appears reasonable because forwarding probability depends on total connections rather than the attacker’s connection fraction.The analysis also notes that subsequent propagation after a non-attacker forwarding event may still affect the result.
  • 7.3 Overall success rate: A careful attacker using the 3-tuple rule and at most 50 connections per server can catch about 11% of client-generated transactions.With 70,000 transactions per day, this corresponds to 7,700 transactions daily; on average, 9 transactions reveal a user’s public IP address.

8. ALTERNATIVE REALITY

The paper describes an alternative-chain construction that preserves Bitcoin’s protocol, wallets, and transactions while exploiting delayed difficulty adjustment. It reports that a lower-difficulty history can be created within a small timeframe, but switching clients requires a new checkpoint or additional high-difficulty blocks.

  • 8. ALTERNATIVE REALITY: The proposed alternative-chain procedure leaves the Bitcoin protocol, existing wallets, and transactions untouched.The authors identify both community use when mining difficulty becomes unsustainable and a possible malicious-administrator attack vector.
  • 8. ALTERNATIVE REALITY: Bitcoin’s difficulty adjustment is reactive to rising hashrate but has large latency when computational power falls.Recovery can require 2016 blocks within at least 8 weeks, and the network may become too slow to produce them.
  • Block construction rules: The protocol caps difficulty changes at a factor of 4 and constrains timestamps using the median of 11 previous timestamps.It also prevents difficulty from falling below the checkpoint-based minimum determined by a factor-of-4 reduction every 8 weeks.
  • Alternative-chain construction: The alternative chain selects a difficulty-recalculation block, changes its date to the current date, and constructs subsequent blocks with adjusted timestamps.The procedure repeats this pattern until the resulting difficulty would contradict the checkpoint’s difficulty constraint.
  • 8. ALTERNATIVE REALITY: The difficulty may drop by a factor of 2^10 compared with the previous checkpoint.The stated checkpoint period is about 140 days, or 25,000 blocks, at the current difficulty-increase rate.
  • Switching to the alternative chain: The resulting chain is initially rejected because its total difficulty is lower than the original chain’s.Completing the switch requires distributing a new checkpoint or adding high-difficulty blocks to make the alternative chain more difficult.
  • Computational cost: A mining pool with 10% of network computational power would need only 3 days to create the illustrated lower-difficulty history.The estimate reduces the work to about 1,400 blocks at difficulty D, or fewer than 50 blocks at current difficulty.

9. FURTHER LEARNING THE TOPOLOGY

The paper develops marker-address methods to estimate Bitcoin nodes’ connection counts and identify server-to-server connections. Experiments show the approach can confirm connections efficiently, while NAT-bound nodes remain outside its reach.

  • Estimating node degree: The attacker estimates a node’s degree by sending fake marker addresses and monitoring which markers are forwarded to neighboring peers.Markers are sent in groups of 10 addresses per ADDR message.
  • Estimating node degree: The method was tested on nodes with 10, 30, 70, and 100 connections using corresponding marker and listening-connection configurations.Table 1 reports five random runs for each series.
  • Determining server connections: The connection-discovery method sends markers to one peer and uses GETADDR responses from another to test whether the peers share a connection.The number of markers known to the second peer is compared with the estimated forwarding count.
  • Limitations: The topology method cannot reveal connections to nodes behind NAT or firewalls because those nodes do not accept incoming GETADDR requests.The limitation applies to nodes that do not accept incoming connections.
  • Determining server connections: Experiments on nodes with 59, 53, 73, and 81 connections produced zero false positives across candidate server connections.The candidate set contained 400 randomly selected running nodes plus the nodes’ current connections.
  • Determining server connections: Five ADDR messages were sufficient to confirm that a connection existed, reducing the number of GETADDR requests relative to the model’s upper bound.The model considers up to 20480 addresses and 2500 random addresses returned per GETADDR request.

10. CONCLUSION

The paper presents a low-cost attack that fingerprints clients by their outgoing connections, links transactions to public IP addresses, and remains applicable to users behind NAT. It also identifies topology, anti-DoS, and checkpoint weaknesses and suggests countermeasures.

  • Deanonymisation attack: A client’s eight outgoing connections serve as a session-level fingerprint that can distinguish users sharing the same NAT IP address.The attacker can update the fingerprint as entry nodes change during a session.
  • Deanonymisation attack: Receiving a transaction from just 2–3 entry nodes lets the attacker link it to a specific client with very high probability.The full-network attack costs under 1500 EUR.
  • Countermeasures: Tor does not necessarily prevent the attack because Bitcoin’s anti-DoS behavior can prohibit Tor connections across the network.The paper proposes randomizing and regularly rotating entry nodes as a countermeasure.
  • Topology and denial of service: The paper’s topology techniques can reveal peer relationships, locate minimal network cuts, and support denial-of-service attacks against those connections.The authors also describe a memory-exhaustion attack discovered while examining Bitcoin’s source code.
  • Checkpoint weakness: Adding a checkpoint to client code can be exploited to construct an alternate blockchain reality or reduce difficulty under unsustainable mining conditions.The paper characterizes the attack scenario as noticeable but the strategy as potentially useful after an unforeseen rise in difficulty.

A. ESTIMATING SUCCESS RATE: DETAILS

This section models the success probability of deanonymization by combining entry-node detection with the number of entry nodes appearing among early transaction reports. It reports estimated tuple-capture rates and operational costs for continuous attacks.

  • Success-rate model: The success-rate model combines the probability of detecting entry nodes with the distribution of entry nodes among the first 10 transaction reports.The model assumes these two events are independent.
  • Success-rate model: The model uses an average entry-node detection probability of paddr = 0.34 to estimate how many of 8 entry nodes are detected.The detection spectrum is obtained from Eq. (1).
  • Results: 11% of transactions are expected to expose 3-tuples, while 35% are expected to expose 2-tuples.These are the calculated deanonymization success rates for the two tuple sizes.
  • Validation: The model fits the authors’ actual deanonymization results on the Bitcoin testnet well.The mainnet extrapolation assumes similar network performance and a stable entry-node spectrum.
  • Attack cost: Continuous deanonymization for one month requires 104,544 GB of data and costs less than 1500 EUR per month.The estimate assumes advertising potential client addresses every 10 minutes from 50 servers.

D. ON STABILITY OF THE FINGERPRINT

The paper evaluates how stable a client’s eight-entry-node fingerprint remains and examines VPN effects. The fingerprint is generally stable during typical sessions, although free VPNs periodically drop connections.

  • Fingerprint stability: Entry nodes can disconnect when the client closes Bitcoin, when no data crosses a connection for 1.5 hours, or when an entry node goes offline.These are the three disconnection causes identified from the bitcoind source code.
  • Fingerprint stability: After 2.5 hours, only one node disconnects on average, and after 10 hours only two nodes disconnect on average, indicating a stable typical-session fingerprint.In one 10-hour experiment, 3 of 8 nodes disconnected.
  • VPN effects: Because the fingerprint remains stable while a VPN protects the user’s IP, an attacker can still link different Bitcoin addresses to the same user.The paper explicitly examines VPN as a popular anonymity recommendation.
  • VPN effects: VPN use can preserve fingerprint stability, but free VPNs dropped entry-node connections about every 20 minutes on the mainnet and every few minutes on the testnet.Non-free and self-operated VPNs showed stability comparable to using no VPN.
  • Denial-of-service implications: Flooding a node with 30,000 fake addresses per second caused significant interaction delays after about 45 minutes and blocked new Bitcoin connections.A reduced real-network experiment was stopped after memory consumption increased by 100 MB.
Loading 1405.7418v3…