Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Anonymity in the Bitcoin Peer-to-Peer Network b...

Papers_We_Love
September 12, 2019

Anonymity in the Bitcoin Peer-to-Peer Network by Giulia Fanti

Recently, researchers have demonstrated deanonymization attacks that exploit weaknesses in the Bitcoin network's peer-to-peer (P2P) networking protocols. In particular, the P2P network currently forwards content in a structured way that allows observers to link users' Bitcoin addresses to their IP addresses. This is a substantial privacy vulnerability that extends to several other cryptocurrencies as well. In this talk, I will discuss how these attacks work, and how effective they are at deanonymizing users. I will also talk about countermeasures, including proposed modifications to the networking stack.

Papers_We_Love

September 12, 2019
Tweet

More Decks by Papers_We_Love

Other Decks in Technology

Transcript

  1. Anonymity in the Bitcoin Peer-to-Peer Network Joint work with: Shaileshh

    Bojja Venkatakrishnan, Surya Bakshi, Brad Denby, Shruti Bhargava, Andrew Miller, Pramod Viswanath Giulia Fanti
  2. Bitcoin Primer Alice Bob kA kB Transaction kA sends kcoin

    to kB kcoin Blockchain sd93fjj2 pckrn29 … our transaction
  3. Multiple Identities Alice Public Key IP Address Used in the

    P2P Network Used in the Blockchain Used nowhere
  4. How can users be deanonymized? Blockchain Meiklejohn et al., 2013

    Ober et al., 2013 Entire transaction histories can be compromised.
  5. This Talk How to break privacy How to fix it

    1) Anonymity Phase 2) Spreading Phase
  6. Early attacks • A. Biryukov, D. Khovratovich, I. Pustagurov, “Deanonymisation

    of clients in Bitcoin P2P network”, CCS 2014 • P. Koshy, D. Koshy, P. McDaniel, “An analysis of anonymity in Bitcoin using P2P network traffic”, Financial Crypto 2014
  7. Key Results • Make ≈ 50 connections per node •

    Between 11-34% of users deanonymized, even behind NAT!
  8. Does diffusion provide stronger anonymity than trickle spreading? G. F.,

    P. Viswanath, “Anonymity in the Bitcoin P2P Network”, NeurIPS 2017
  9. Anonymity Metric , = 2.0 0 = 0.7 2 =

    1.1 4 = 1.5 5 = 0.3 (detection|, ) graph timestamps = , 2 … C
  10. Estimators First-Spy , = 2.0 0 = 0.7 2 =

    1.1 4 = 1.5 5 = 0.3 Maximum- Likelihood (detection|, ) graph timestamps
  11. Results: d-Regular Trees Trickle Diffusion First-Timestamp log log Maximum-Likelihood Ω(1)

    Ω(1) Probability of Detection Degree, d First-timestamp Maximum-Likelihood Intuition: Symmetry outweighs local randomness!
  12. Proof sketch (diffusion, max likelihood) Source Not yet received Received

    Received and reported - Generalized Polya Urns - Concentration of measure
  13. Results: Bitcoin Graph 0 5 10 15 20 0.3 0.4

    0.5 0.6 0.7 0.8 0.9 1 Trickle, Theoretical lower bound Trickle, Simulated Trickle, Theoretical lower bound (d=2) Diffusion, Theoretical Diffusion, Simulation Probability of Detection Diffusion Trickle Number of Eavesdropper Connections
  14. Botnet adversarial model fraction p of spies spies collude honest-

    but-curious observe all metadata identities unknown
  15. Metric for Anonymity Recall Precision 1 J K 1 Ns

    tx = Mapping User Users Transactions Number honest users Mapping 1 J K 1 Ns tx = # tx mapped to v [Recall] = Probability of Detection
  16. Goal: Design a distributed flooding protocol that minimizes the maximum

    precision and recall achievable by a computationally-unbounded adversary. S. B. Venkatakrishnan, G. F., P. Viswanath, “Dandelion: Redesigning the Bitcoin Network for Anonymity ”, Sigmetrics 2017
  17. Fundamental Limits Precision Recall 0 1 1 p p2 Thm:

    Maximum precision ≥ 2. Thm: Maximum recall ≥ . Fraction of spies
  18. Approximately regular What can we control? Spreading Protocol Topology Dynamicity

    Static Dynamic How often does the graph change? What is the underlying graph topology? Given a graph, how do we spread content? Diffusion
  19. Theorem: Dandelion spreading has an optimally low maximum recall of

    + , C . fraction of spies number of nodes Theorem: Fundamental lower bound = p Why Dandelion spreading?
  20. Line graph DANDELION Network Policy Spreading Protocol Topology Dynamicity Static

    Dynamic How often does the graph change? What is the anonymity graph topology? Given a graph, how do we spread content? Dandelion Spreading
  21. Theorem: DANDELION has a nearly-optimal maximum precision of 2ab ,ca

    log 2 a + , C .* fraction of spies Theorem: Fundamental lower bound = p2 number of nodes *For < , 4
  22. Why is DANDELION good? Strong mixing properties. Precision:() Precision: a

    ,ca (1 − ac,) Tree Complete graph Too many leaves Too many paths
  23. Latency Overhead: Estimate Information Propagation in the Bitcoin Network, Decker

    and Wattenhofer, 2013 Time to first transaction sighting (s) PDF
  24. Take-Home Messages 1) Bitcoin’s P2P network has poor anonymity. 2)

    Moving from trickle to diffusion did not help. 3) DANDELION may be a lightweight solution for certain classes of adversaries. https://github.com/dandelion-org/bitcoin BIP 156