Privacy & Anonymity
Bitcoin is often claimed to provides anonymity/privacy
“Privacy can be maintained … by keeping public keys anonymous. The public can see that someone is sending an amount to someone else, but without information linking the transaction to anyone”
Copyright By PowCoder代写 加微信 powcoder
“ Bitcoin is a secure and anonymous digital currency ”
— WikiLeaks donations page, 2016
Other sources say Bitcoin can be tracked
Anonymity and privacy are different concepts
Anonymity vs. pseudonymity
Some examples
Identifiable/named/public
● Easy to link all actions to a unique person
Some examples
Pseudonymous
● Human is obscured ○ No “real name”
● Pseudonym is unique and consistent ○ All actions taken are linkable
Some examples
● No unique identify features
● Indistinguishable within an anonymity set
● Small distinguishing traits can undermine
● Bigger anonymity sets are better!
● Anonymity loves company
Several ways to quantify anonymity
Anonymity set: the crowd that one attempts to blend into
To calculate anonymity set:
• define adversary model
• reason carefully about what the adversary knows or can
Classic measure: anonymity set size
Improvement: use probabilistic anonymy set, calculate
uncertainty
Example: Reddit (pseudonymous)
Example: 4Chan (anonymous)
Bitcoin is pseudonymous due to public keys
Bitcoin addresses are trivially linkable when re-used
Anonymity in computer science
Anonymity = pseudonymity + unlinkability
Different interactions of the same user with the system should not be linkable to each other
Some Bitcoin addresses can be tied to real identities
Many Bitcoin services require real identities ○ Banks/exchanges (know-your-customer
○ Merchants (need shipping addresses)
Addresses can be deanonymized by side
Conclusion: anonymity in Bitcoin requires unlinkability channels
Unlinkability goals 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
Unlinkability goals 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
Linkability heuristics in Bitcoin
Default behavior: new address for each UTXO
Default behavior: new address for each UTXO
Serial control: addresses in 1:1 tx often co-owned
Joint-control: addresses used together often co-owned
K3 K26 1K4
Change addresses can often be identified
Change address tells:
Same address type ○ e.g. MULTISIG
Other address is a retail price ○ e.g. $9.99
Other address is known ○ e.g. Amazon.com
Poor randomization
○ Old clients always put it
Network-level de-anonymization
“The first node to announce a transaction is probably its source” – 2011
Tor offers a solution for network-level anonymity
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
Transitive application leads to clusters of linked addresses
A Fistful of Bitcoins: Characterizing Payments Among Men with No Names
S. Meiklejohn et al. IMC 2013
Many clusters can be tagged by transaction probes
A Fistful of Bitcoins: Characterizing Payments Among Men with No Names
S. Meiklejohn et al.
344 transactions
• Mining pools
• Wallet services
• Exchanges
• Gambling sites
Large service providers know many user identities
Service providers are highly centralized
● Most clusters interact with at least one
Law enforcement has subpoena power over most
Transaction graph analysis is now big business
Customers:
● Law enforcement ● Intelligence
● Business intelligence
● Private Investigators
Transaction graph analysis can be imprecise
Transaction graph analysis can be imprecise
Do we actually want anonymity?
Claim: only bad actors want anonymity
Typical boogey-men:
● Criminals
● Child abuse images
● Drug dealers
● Terrorists
● Ransomware/scammers
● Tax cheats
● Rhino poachers?
Rebuttal: cash has long provided anonymity
Properties of cash
● Highly anonymous at low volume
● Becomes traceable at scale
○ Serial # statistics
○ KYC laws
○ Money-laundering
A useful balance?
Payment cards provide partial anonymity
Properties of payment cards
● Invisible to the public
● Easily traceable by:
○ Visa/Mastercard etc. ○ Governments
Bitcoin potentially much worse!
Can we allow anonymity only for “good”
Common conundrum in computer security and privacy: uses that are different morally are the same technologically
Very difficult to re-create the delicate balance of cash…
Similar dilemma: Tor
• Normal people
• Journalists & activists
• Law enforcement
• Child abusers
Funded by (among others): U.S. State Department
The business case for anonymity: hiding salaries
Might be a problem even if addresses are unlinkable!
The business case for anonymity: supply chain privacy
Ksupplie s
Supply relationships a hint at future business plans ● Price are also likely highly sensitive
Mixing for unlinkability
Idea: to increase anonymity, use an intermediary
Online exchanges are large intermediaries… do they help?
Dedicated mixing services (mixers/tumblers/laundries)
• Promise not to keep records
• Don’t ask for your identity
• Collect a small fee
• May not be trustworthy…
○ Steal funds
○ Record input/output mapping
Centralized mixes are popular, but risky
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
Coinjoin: decentralized mixing
Atomic N-to-N transaction
Each signature is separate
● No risk of theft
● Risk of aborts
1 TX = 1 mixing round
Originally proposed by
Coinjoin logistics are more involved
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 challenges
Hard to find peers
○ Especially reliable peers
Hard to hide output from
○ Use Tor?
Denial of service
○ Can track reputation
○ But that defeats anonymity!
Hard to hide input-output map from participants
Basic solution:
1. exchange inputs
2. disconnect and reconnect over Tor
3. exchange outputs
Better solution:
special-purpose anonymous routing mechanism
Hard to manage griefing/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)
Can improve anonymity with a series of mixes
Mix 1 Mix 2 Mix 3
Mix size puts anonymity, reliability at odds
Best anonymity: one giant mix with everybody
• Tempting target if centralized
• Hard to organize if decentralized
Smaller mixes can also be attacked…
Flooding attack: adversary controls N-1 inputs/outputs
Challenge: all mix inputs/outputs must be same “chunk” size
Difficult to pick a chunk size that works for everybody
Large chunks: small participants can’t afford to join
Small chunks: inefficient to break large amounts into many chunks
Can use a mix of chunk sizes (“denominations”) ● This reduces anonymity
How to pay fees without reducing chunk size gradually?
High-level transaction amounts can be identifying
Alice receives 43.12312 BTC / week as income
Always immediately transfers 5% to retirement account
Countermeasure: merge-avoidance
● Avoid merging anonymized addresses together
Hiding transaction values via
Confidential Transactions
Idea: replace UTXO values with commitments
K3 K26 1K4
Idea: replace UTXO values with commitments
K2c cK4 24
Confidential Transactions, also proposed by
Recap: Cryptographic commitments are a useful tool
● General structure:
○ c = Commit(x, r)
○ VerifyOpening(x, c, r) →yes/no
● Hash-based commitments: Commit(x, r) = H(x || r)
○ Simple hash is sufficient only if x has high min-entropy
● Pedersen commitments: Commit(x, r) = gxhr
○ Addition, proofs of equality, proofs of knowledge, range proofs…
Confidential Transactions uses Pedersen commitments
gx1hr gx3hr K3 13
K2 gx2hr gx4hr K4
● x1, x2, … are the input/output values
● Random blinding factors hr1, hr2 ensure nobody can learn x1, x2, …
● Additive homomorphism ensures we can prove that sum(inputs) = sum(outputs)
Devil is always in the details with crypto…
● Want to prove that sum(inputs) = sum(outputs)
○ Check that c1·c2=c3·c4·hr5, for some value r5=(r1+r2)-(r3+r4)
○ gx1+x2hr1+r2=gx3+x4hr3+r4+r5
○ if x1+x2 ≠x3+x4, can’t compute a valid r5 (as long as loggh is unknown)
● Computing r5 naively requires knowing all other values
○ Can be computed in a more complex way by two untrusting parties
● Need to prove there is no overflow! This only proves x1+x2 =x3+x4 (mod q)
○ Requires cryptographic range proofs that each xi is in range [0, max_val]
Confidential transactions are a powerful building block
gx1hr gx3hr K3 13
K2 gx2hr gx4hr K4
● Completely hides transaction amounts, may be enough in some cases
● Can be combined with mixing, or other anonymity tools for addresses
○ Mixing is easier-no need to match chunk sizes ● Challenge: can we commit to the addresses as well?
A necessary detour: zero-knowledge proofs
Zero-knowledge proofs
● General idea: prove that a statement X is true, but nothing more
○ For example: For a given y, prove that H(x) = y has a solution where x < 2128 ● Proofs-of-knowledge: prove that you know something
○ For example: For a given y, prove you know an x < 2128 such that H(x) = y
● Very powerful idea
○ Winner of the 2012 Turing Award!
Zero-knowledge proof example #1: I know where Waldo is
Zero-knowledge proof example #1: I know where Waldo is
Not fully ZK,
Some info is leaked
Zero-knowledge proof example #2: I have x-ray vision
How can I prove to you that I can see inside the boxes?
Non-solution: say what’s in the boxes
The bottom box has the textbook!
#teamjacob
Zero-knowledge proof example #2: I have x-ray vision
Zero-knowledge proof example #2: I have x-ray vision
I won’t tell you what’s inside, but I can tell that you switched them!
Generic ZK scheme Prover
Sudoku Testing Algorithm
Puzzle , Proof
Accept/Reject
Prover knows solution to Puzzle
Generic ZK
public input
(statement)
private input
• Possible for any NP statement
• Continual efficiency improvement since 1980s
• Practical deployment during 2010s
• Compilers produce prover/verifier from higher-level description
Proving Algorithm
public input
(statement)
Verification Algorithm
Accept/Reject
ZK approaches
Ad-hoc proofs/Sigma protocols
• Very efficient for certain algebraic statements
○ Proofs of knowledge of discrete log
○ Schnorr/ECDSA signatures
• Proofs small, very fast to verify, can be non-interactive Generic ZK proofs/SNARKs
• Work for any NP statement
○ Must be expressed as an algebraic circuit
○ Can be compiled from higher-level code (inefficient)
• Many proving schemes with different tradeoffs • Still far from “push-button” usage
Succinct (constant-sized for any circuit size) Non-interactive
ARgument (computationally sound) Knowledge proof (as opposed to SNARGs)
Cryptonote and derivatives
Idea: hide transaction inputs using ring signatures
Also use standard Confidential Transactions concept to hide values
Idea: hide transaction inputs using ring signatures K1
Also use standard Confidential Transactions concept to hide values
Ring signatures: a special type of ZK proof
σ1 (private input)
Ring signature ZK statement:
“I know a signature on m with one of the keys in the set {K1, ... Kn}”
What about double-spending?
Ring signatures: a special type of ZK proof
σ1 (private input)
Ring signature ZK statement:
● I know a signature on m with one of
the keys in the set {K1, ... Kn} ● That key has form gx and for the
same x as the output hx
(key image)
Many projects use variants of Cryptonote
Challenges with Cryptonote approach
● How many prior outputs should your coin include in the ring signature?
○ Linear transaction size with ring size
○ More=better anonymity, but slower
● How to choose prior outputs?
○ Can lose all anonymity if they are all revealed later! (similar to flooding)
Challenges with Cryptonote approach
● How many prior outputs should your coin include in the ring signature?
○ Linear transaction size with ring size
○ More=better anonymity, but slower
● How to choose prior outputs?
○ Can lose all anonymity if they are all revealed later! (similar to flooding)
The ultimate: Zcash
Idea: entire transaction* is just a zero-knowledge proof
K3 ZK statement: 3
“This transaction is valid” c
Zcash blockchain and coin structure
High-level structure of a Zcash transaction
c1,c2,σ1,σ2 (private inputs)
ZK-SNARK statement:
● The two coins c1, c2 are included in the state root
● I know signatures on this tx with the keys for each
● Those coins have serial numbers sn1, sn2
● The outputs c3, c4 are new well-formed coins
● The total value of c3, c4 is equal to c1,c2 plus fee
stat e root
Prevent double
Zcash blockchain and coin structure
Zcash challenges
● Generic proving system is slow. Proof times in seconds
○ No scripts, multisig etc. Only 2-2 transactions ● Proof system required trusted setup
○ Backdoor was created but (hopefully) deleted
● Zcash also supports “transparent addresses” ○ In practice, over 95% of usage!
Zcash is stronger in theory, but Monero is 2x more popular
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
Cryptonot e
Ring signatures Poor ring selection ZK proof t-address/z-address Altcoin, tricky setup
Privacy for Ethereum and smart contracts
High-level challenges
● Ethereum’s account-based ledge is less privacy friendly
○ Mixing can’t be done with based transactions
○ Smart-contract level mixing is required
● Smart contracts much more challenging for privacy
○ Current solutions are too inefficient, research prototypes only:
○ Zether, Zexe
● Proofs are expensive to verify on-chain
○ Costs dropping with precompiled contracts, new opcodes
Can implement “Zcash”-pools in Ethereum
data merkleTree, serialNumbers[] def deposit(com):
assert msg.value == 1 merkleTree.treeInsert( com )
This is a commitment to:
hash( serialNumber, publicKey )
Partial privacy solution: the Hawk model
Hawk manager collect all input, executes contract logic
Issue ZK proof to smart contract which miners verify
Privacy against miners/blockchain, but not against the manager...
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com