Lecture 6
Bitcoin and anonymity
Lecture 6.1:
Anonymity basics
Some say Bitcoin provides anonymity
“ Bitcoin is a secure and anonymous digital
currency ”
— WikiLeaks donations page
Others say it doesn’t
“ Bitcoin won't hide you from the NSA's prying
eyes”
— Wired UK
What do we mean by anonymity?
Literally: anonymous = without a name
Bitcoin addresses are public key hashes rather than real identities
Computer scientists call this pseudonymity
Anonymity in computer science
Different interactions of the same user with the system should not be linkable to each other
Anonymity = pseudonymity + unlinkability
Pseudonymity vs anonymity in forums
Reddit: pick a long-term pseudonym
vs.
4Chan: make posts with no attribution at all
Why is unlinkability needed?
Defining unlinkability in Bitcoin
Hard to link different addresses of the same user
Hard to link different transactions of the same user
Hard to link sender of a payment to its recipient
Quantifying anonymity
Complete unlinkability (among all addresses/transactions) is hard
Anonymity set: the crowd that one attempts to blend into
To calculate anonymity set:
Why anonymous cryptocurrencies?
Block chain based currencies are totally, publicly, and permanently traceable
Without anonymity, privacy is much worse than traditional banking!
What about money laundering?
Legitimate worry
Bottleneck: moving large flows into and out of Bitcoin (“cashing out”)
Can we keep only the good uses?
Common conundrum in computer security and privacy:
uses that are very different morally are pretty much the same technologically
Similar dilemma: Tor
Anonymous communication network
Sender and receiver of message unlinkable
Used by:
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
Crypto
magic
Anonymous e-cash via blind signatures
Deposit coin # 317038628684424
User | Balance |
… | … |
| 10 |
… | … |
| 5 |
Spent coins |
… |
|
|
|
Withdraw anonymous coin
{317038628684424}
{317038628684424}
OK
9
6
31703862…
Bank cannot link the two users
Anonymity & decentralization: in conflict
Lecture 6.2:
How to de-anonymize Bitcoin
Trivial to create new address
Best practice: always receive at fresh address
So, unlinkable?
Alice buys a teapot at Big box store
5
3
6
8
Single
transaction
Linking addresses
Shared spending is evidence of joint control
Addresses can be linked transitively
Clustering of addresses
An Analysis of Anonymity in the Bitcoin System
F. Reid and M. Harrigan
PASSAT 2011
Change addresses
5
3
6
8.5
.5
Which address
is change?
“Idioms of use”
Idiosyncratic features of wallet software
e.g., each address used only once as change
Shared spending + idioms of use
A Fistful of Bitcoins: Characterizing Payments Among Men with No Names
S. Meiklejohn et al.
IMC 2013
To tag service providers: transact!
A Fistful of Bitcoins: Characterizing Payments Among Men with No Names
S. Meiklejohn et al.
344 transactions
Shared spending + idioms of use
A Fistful of Bitcoins: Characterizing Payments Among Men with No Names
S. Meiklejohn et al.
From services to users
1. High centralization in service providers
Most flows pass through one of these — 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
Lecture 6.3:
Mixing
To protect anonymity, use an intermediary
To protect anonymity, use an intermediary
Online wallets do this
Do they provide anonymity?!
Dedicated mixing services
Back to online wallets
Reputable, often regulated, businesses
Rest of this lecture:
assume a user for whom the trust requirements and anonymity properties of online wallets are unacceptable
Mixing: terminology
Mix vs. mixer
Another term: laundry
Won’t use in this lecture
Principles for mixing services
1. Use a series of mixes
Mixes should implement a
standard API to make this
easy
Mixcoin: Anonymity for Bitcoin with accountable mixes
J. Bonneau et al.
Financial Cryptography 2014
Series of mixes
Mix 1
Mix 2
Mix 3
Principles for mixing services
2. Uniform transactions
In particular: all mix
transactions must have the
same value!
“Chunk size”
Mixcoin: Anonymity for Bitcoin with accountable mixes
J. Bonneau et al.
Financial Cryptography 2014
Principles for mixing services
3. Client side must be
automated
Desktop wallet software
Mixcoin: Anonymity for Bitcoin with accountable mixes
J. Bonneau et al.
Financial Cryptography 2014
Principles for mixing services
4. Fees must be all-or-nothing
Probabilistic fees:
0.1% mixing fee =
mix will swallow chunk
with 0.1% chance
Mixcoin: Anonymity for Bitcoin with accountable mixes
J. Bonneau et al.
Financial Cryptography 2014
Current mixes follow none of these principles
Remaining problem: trusting mixes
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.
— Bitcoin Wiki
�
Lecture 6.4:
Decentralized mixing
Why decentralized mixing?
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
Coinjoin: remaining problems
Finding peers
Use an untrusted server
Peer anonymity
Strawman solution:
Better solution: �special-purpose anonymous routing mechanism
Denial of service
Proposed solutions:
High-level flows could be identifying
Example:
Alice receives 43.12312 BTC / week as income �Always immediately transfers 5% to retirement account
Heuristic: merge avoidance
Instead of a single payment transaction
receiver provides multiple output addresses
sender avoids combining different inputs
(Proposed by Mike Hearn)
Lecture 6.5:
Zerocoin and Zerocash
Zerocoin: protocol-level mixing
Mixing capability baked into protocol
Advantage: cryptographic guarantee of mixing
Disadvantage: not currently compatible with Bitcoin
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)
Two challenges
How to construct these proofs?
How to make sure each proof can only be “spent” once?
Zero-knowledge proofs
A way to prove a statement
without revealing any other
information
Example:
Crypto
magic
Minting zerocoins
Zerocoins come in standard denominations
(Let’s assume 1 basecoin)
Anyone can make 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 H(S, r)
Serial number:
317038628684424
Simplification
Minting a zerocoin
To put H(S, r) on block chain
Create Mint Tx with 1 basecoin as input
Mint
signed by A
H(S, r) H( )
To spend a zerocoin S:
Zerocoin is anonymous
Since r is secret, no one can figure out which zerocoin corresponds to serial number S
H(S, r)
h1
h2
hN
…
Zerocoin is “efficient”
The proof is a giant disjunction over all zerocoins
Yet the proof is relatively small!
I know r such that
H(S, r) = h1
OR
H(S, r) = h2
OR
…
OR
H(S, r) = hN
Zerocash: Zerocoin without Basecoin
Two differences
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
System | Type | Anonymity attacks | Deployability |
Bitcoin | Pseudonymous | Tx graph analysis | Default |
Single mix | Mix | Tx graph analysis, bad mix | Usable today |
Mix chain | Mix | Side channels, bad mixes/peers | Bitcoin-compatible |
Zerocoin | Cryptographic mix | Side channels (possibly) | Altcoin |
Zerocash | Untraceable | None | Altcoin, tricky setup |
Lecture 6.6:
Tor and the Silk Road
�Anonymous communication
Threat model
How Tor works
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:
Onion address looks like http://3g2upl4pq6kufc4m.onion/
Silk Road