Bitcoin and Anonymity Notes

Bitcoins and Cryptocurrencies

Lecture 6: Bitcoin and Anonymity

Anonymity Basics

• Bitcoin's anonymity is debated, with some claiming it's secure and anonymous, while others argue it's not.
• Anonymity literally means "without a name."
  • Interpretation 1: Not using your real name.
  • Interpretation 2: Not using any name at all.
• Bitcoin addresses are public key hashes instead of real identities.
  • By the first interpretation, Bitcoin is anonymous.
  • By the second interpretation, it is not anonymous.
• Bitcoin addresses are pseudo-identities, leading to pseudonymity.
• Bitcoin is pseudonymous.

Pseudonymity vs. Anonymity

• Forums:
  • Reddit: Uses long-term pseudonyms.
  • 4Chan: Posts are made anonymously without any attribution.

Anonymity in Computer Science

• Different interactions of the same user with the system should not be linkable to each other or to the user's real identity.
• Anonymity = pseudonymity + unlinkability.

Why Unlinkability is Needed

• Pseudonymity is not enough for privacy in Bitcoin.
• The Bitcoin blockchain is public, allowing anyone to look up transactions involving a given address.
• If a Bitcoin address is linked to a real-world identity, all transactions associated with that address (past, present, and future) can be traced back to the identity.
• Linking Bitcoin addresses to real identities is easy because many Bitcoin services require real identity verification.
• Linked profiles can be deanonymized through various side channels.

Linking Bitcoin Addresses to Real Identities

• Interacting with Bitcoin businesses (online wallets, exchanges, merchants) often requires providing real-life identity information.
• Exchanges might require credit card details, while merchants need shipping addresses.
• Paying for coffee with bitcoins can link your physical identity to a Bitcoin transaction, making all other transactions involving that address linkable to you.

Side Channels

• Even without direct linkage, pseudonymous profiles can be deanonymized due to side channels or indirect leakages of information.
• Example: Correlating the times a user is active with other publicly available information, such as Twitter activity.
• Pseudonymity does not guarantee privacy or anonymity; unlinkability is required.

Defining Unlinkability in Bitcoin

• It should be hard to:
  • Link together different addresses of the same user.
  • Link together different transactions made by the same user.
  • Link the sender of a payment to its recipient.

Quantifying Bitcoin Anonymity

• Complete unlinkability is hard to achieve.
• Anonymity set: The crowd that one attempts to blend into.
• Anonymity set (for a Bitcoin transaction): Set of transactions that an adversary cannot distinguish from the transaction in question.
• To calculate anonymity set:
  • Define adversary model.
  • Reason carefully about what the adversary knows, does not know, and cannot know.

Alternate Measures of Bitcoin Anonymity

• Taint Analysis: Assigning a high "taint" score if bitcoins sent by address S always end up at address R.
• Not a good measure because it makes implicit assumptions about the adversary’s calculations and the adversary may use alternate techniques.

Why Anonymous Cryptocurrencies?

• Blockchain-based currencies are totally, publicly, and permanently traceable.
• Without anonymity, privacy is much worse than traditional banking.
• Motivations:
  • Achieve privacy level at least equivalent to traditional banking.
  • Go beyond the privacy level offered by traditional banking based solutions.

Ethical Concerns About Anonymity

• Legitimate uses: Preventing the disclosure of salary information or private business dealings.
• Legitimate worries: Money laundering.
• Bottleneck: Moving large flows into and out of Bitcoin ("cashing out").

Can We Keep Only the Good Uses?

• Common conundrum: Uses that are morally very different are technologically pretty much the same.

Similar Dilemma: Tor

• Tor: Anonymous communication network where sender and receiver of message are unlinkable.
• Used by:
  • Normal people, journalists, activists, law enforcement, malware distributors, and child pornographers.
• Funded by (among others): U.S. State Department.

Anonymous E-cash: History

• David Chaum, 1982.
• Blind signature: Two-party protocol to create digital signature without signer knowing the input, a form of crypto magic.

Anonymous E-cash via Blind Signatures

• Bank cannot link the two users.
  ```
  User Balance: …10… -> Withdraw anonymous coin -> {317038628684424} -> OK: 9
  …5… -> Spent coins -> {317038628684424} -> OK: 6

Anonymity & Decentralization: In Conflict

• Interactive protocols with bank are hard to decentralize.
• Decentralization often achieved via public traceability to enforce security.

How to De-anonymize Bitcoin?

• It is trivial to create a new address.
• Best practice: Always receive at a fresh address. So, unlinkable?

Linking Addresses

• Shared spending is evidence of joint control.
• Addresses can be linked transitively.
• Alice buys a teapot at Big Box Store.

Clustering of Addresses

• Refer to "An Analysis of Anonymity in the Bitcoin System" by F. Reid and M. Harrigan, PASSAT 2011.

Change Addresses

• Identify which address is the change address.

"Idioms of Use"

• Implementation details or idiosyncratic features of wallet software that can be used to design heuristics for identifying (linking) change addresses.
• Most wallets generate a fresh address when a change address is required.
• Bitcoin-Qt library bug: Change output always first output in a transaction.

Shared Spending + Idioms of Use

• Refer to "A Fistful of Bitcoins: Characterizing Payments Among Men with No Names" by S. Meiklejohn et al., IMC 2013.

Tagging Service Providers

• Transact to tag service providers.
• Mining pools, wallet services, exchanges, vendors, gambling sites.
• Using 344 transactions as per "A Fistful of Bitcoins: Characterizing Payments Among Men with No Names" by S. Meiklejohn et al.

From Services to Users

1. High centralization in service providers, where most flows pass through in a traceable way.
2. Address-identity links in forums.

Network-Layer De-anonymization

• "The first node to inform you of a transaction is probably the source of it" - Dan Kaminsky, Black Hat 2011 talk.

Solution: Use Tor

• Caveat: Tor is intended for low-latency activities such as web browsing.
• Mix nets might provide better anonymity, BUT Tor is what’s deployed and works.

Mixing

• To protect anonymity, use an intermediary.
• Online wallets do this. Do they provide anonymity?!

Bits

• Study Suggests Link Between Dread Pirate Roberts and Satoshi Nakamoto
• Researchers Retract Report That Linked Bitcoin Creator and Silk Road

Online Wallets for Anonymity

• Reputable, often regulated, businesses.
• Typically require identity, keep records, no anonymity w.r.t. wallet service.
• Users trust them with their bitcoins, keep them for longer, bigger anonymity set w.r.t. everyone else.

Dedicated Mixing Services

• Promise not to keep records.
• Don’t ask for your identity.
• Essentially swaps a user’s coin (address) with other users’ coins (addresses).
• Relatively small anonymity set (only comprise of those users who use the mixing service at that instant)!

Mixing: Terminology

• Mix vs. Mixer; Another term: Laundry; Avoid using "laundry" in this lecture.

Principles for Mixing Services

1. Use a series of mixes, implementing a standard API to make this easy, as per "Mixcoin: Anonymity for Bitcoin with accountable mixes" by J. Bonneau et al., Financial Cryptography 2014.
2. Uniform transactions. In particular, all mix transactions must have the same value as per "Mixcoin: Anonymity for Bitcoin with accountable mixes" by J. Bonneau et al., Financial Cryptography 2014.
3. Client side must be automated using desktop wallet software as per "Mixcoin: Anonymity for Bitcoin with accountable mixes" by J. Bonneau et al., Financial Cryptography 2014.
4. Fees must be all-or-nothing. Probabilistic fees: $0.1\%$ mixing fee = mix will swallow chunk with 0.1% chance as per "Mixcoin: Anonymity for Bitcoin with accountable mixes" by J. Bonneau et al., Financial Cryptography 2014. Current mixes follow none of these principles.

Remaining Problem: Trusting Mixes

• Stay in business, build up reputation.
• Users can test for themselves.
• Cryptographic “warranties”.

Decentralized Mixing

• Currently no reputable dedicated mix.
• Caution: Mixing services may themselves be operating with anonymity.
• As such, if the mixing output fails to be delivered or access to funds is denied there is no recourse. Use at your own discretion (per Bitcoin Wiki).

Why Decentralized Mixing?

• No bootstrapping problem.
• Theft impossible.
• Possibly better anonymity.
• More philosophically aligned with Bitcoin.

CoinJoin

• Each signature is entirely separate. This is 1 mixing round. Mixing principles from before apply on top of basic protocol.
• Single transaction, proposed by Greg Maxwell, Bitcoin core developer.

CoinJoin Algorithm

1. Find peers who want to mix.
2. Exchange input/output addresses.
3. Construct transaction.
4. Send it around, collect signatures (Before signing, each peer checks if her output is present).
5. Broadcast the transaction.

CoinJoin: Remaining Problems

• How to find peers.
• Peers know your input-output mapping (This is a worse problem than for centralized mixes).
• Denial of service.

Finding Peers

• Use an untrusted server to facilitate this process.
• Unlike centralized mixes, these servers cannot steal users' funds.

Peer Anonymity

• Strawman solution:
  • Exchange inputs
  • Disconnect and reconnect over Tor
  • Exchange outputs
• Better solution: Special-purpose anonymous routing mechanism.

Denial of Service

• Proposed solutions:
  • Proof of work.
  • Proof of burn.
  • Server kicks out malicious participant.
  • Cryptographic “blame” protocol (CoinShuffle: Practical Decentralized Coin Mixing for Bitcoin, T. Ruffing et al., PETS 2014).

Heuristic: Merge Avoidance

• Instead of a single payment transaction, the receiver provides multiple output addresses, and the sender avoids combining different inputs (Proposed by Mike Hearn).

Zerocoin and Zerocash

Zerocoin

• Mixing capability baked into the protocol.
• Advantage: cryptographic guarantee of mixing.
• Disadvantage: not currently compatible with Bitcoin.
• Refer to Zerocoin: Anonymous Distributed E-Cash from Bitcoin I. Miers et al. IEEE S&P 2013.

Basecoin and Zerocoin

• Basecoin: Bitcoin-like Altcoin
• Zerocoin: Extension of Basecoin
  • Basecoins can be converted into zerocoins and back
  • Breaks link between original and new basecoin

Zerocoins

• A Zerocoin is a cryptographic proof that you owned a Basecoin and made it unspendable.
• Miners can verify these proofs.
• Gives you the right to redeem a new Basecoin (somewhat like poker chips).

Challenges

• How to construct these proofs?
• How to make sure each proof can only be “spent” or “redeemed” once with a basecoin?
• Otherwise, a basecoin could be turned to a zerocoin which could be redeemed into multiple basecoins.

Zero-Knowledge Proofs

• A way to prove a statement without revealing any other information.
• Example:
  • “I know an input that hashes to da39a3ee5e”
  • “I know an input that hashes to some hash in the following set: … ”

Minting Zerocoins

• Zerocoins come in standard denominations (Let’s assume 1 basecoin).
• Anyone can make (or mint) one!
• They have value once put on the block chain. That costs 1 basecoin.

Minting a Zerocoin: "Commitment"

• Generate serial number S (eventually made public) and random secret r (never public, ensures unlinkability).
• Compute $Commit(S, r)$.

Minting a Zerocoin

• To put Commit(S, r) on block chain: Create “Mint” Tx with 1 basecoin as input
  Mint signed by A Commit(S, r) $H($ )

To Spend a Zerocoin S:

• Create a special “Spend” Tx that contains:
• Serial number S
• Zero-knowledge proof that:
• “I know a number r such that Commit(S, r) is one of the zerocoins or commitments {c1, c2, …., cN} in the block chain”
• Miners will verify S hasn’t been spent before. Miners will also verify the above zero-knowledge proof (which establishes the claimant’s ability to open one of the zerocoin commitments without actually opening it)
• Output of the spend Tx now acts as a new basecoin
  Mint Proof:

Zerocoin is Anonymous

• Since r is secret, no one can figure out which zerocoin corresponds to serial number S
• Commit(S, r)
  c1 c2 cn

Zerocoin is “efficient”

• The proof is a giant disjunction over all zerocoins
• Yet the proof is relatively small (logarithmic in N)!
• I know r such that Commit(S, r) = c1 OR Commit(S, r) = c2 OR Commit(S, r) = cN

Need for a Trusted Setup

• One of the crypto tools (RSA accumulators) requires a one-time trusted setup
• Security relies on difficulty in factorizing a composite N of large primes $p$ and $q$!
• A trusted party needs to select random $p$ and $q$, compute $N=pq$, release $N$ and permanently delete $p$ & $q$
• Sociological issue: Can we trust someone to do this?
  Solution: “Threshold cryptography” – a set of delegates jointly compute $N$ (even if one is honest, difficult to determine p & q)

Zerocash: Zerocoin without Basecoin

Two differences

• Different crypto for proofs (More efficient)

• Proposal to run system without Basecoin

• Zerocash: Decentralized Anonymous Payments from Bitcoin E. Ben-Sasson et al. Usenix Security 2014

Zerocash: Untraceable E-cash

• All transactions are zerocoins
• Splitting and merging supported
• Put transaction value inside the envelope
• Ledger merely records existence of transactions

Zerocash: the Catch

• Random, secret inputs are required to generate public parameters
• These secret inputs must then be securely destroyed
• No one can know them (anyone who does can break the system)

5 Levels of Anonymity

Tor and the Silk Road

Anonymous Communication

• Diagram of senders, recipients, communication network, and messages.

Threat Model

• Diagram of senders, recipients, communication network, messages, and attacker.

How Tor Works

• Alice's Tor client picks a random path to destination server.
• Green links are encrypted, red links are in the clear.
  Safe(ish) if at least one router honest
• Key challenge: hiding routing information

Solution: Layered Encryption

• Side effect: contents encrypted from Alice to exit node.
• BUT: Unencrypted from exit node to Bob.

Hidden Services

• What if the server wants to hide its address?
• Simplified:
  • Connect to “rendezvous point” through Tor
  • Publish name → rendezvous point mapping
  • Client connects to rendezvous point Onion address looks like http://3g2upl4pq6kufc4m.onion/

Silk Road

• Communication: Tor hidden service
• Payment: Bitcoin
• Security?
• Anonymous shipping?