First Annual Review of Technical Approaches to Anonymity in Cryptocurrency (Part I)

Leo Zhang

By Leo Zhang

Tags:

This series introduces the concept of anonymous transactions, methods of deanonymizing Bitcoin transactions, and techniques to enhance Bitcoin privacy. Part I is an introduction. Parts II and III discuss specific implementations of anonymous cryptocurrencies. Part II will cover the CryptoNote protocol and Monero, and Part III will focus on zero-knowledge proofs and Zcash.

The "Warlocks" and anonymous identities

In sci-fi author Vernor Vinge's classic cyberpunk masterpiece True Names, a group of prominent hackers called "warlocks" regularly operates on the largest open virtual reality world to penetrate computers around the world. To protect themselves from each other, and the authorities ("The Great Adversary"), the warlocks must keep their real identities anonymous at all cost. Failure to hide their identity could result in slavery, or even death.

Protecting the identities of participants in financial networks in the real-world is taken just as seriously. Failures in privacy protection can expose network participants to social engineering, theft, or blackmail.

In the traditional financial system, privacy is achieved through limiting access to information. In a bank, only authorized individuals are permitted to view identity or transaction data, and security systems are built around preventing unauthorized access to the sensitive databases.

Picture13-1

(Image source: Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System)

Over the years there were numerous attempts at creating financial systems native to the digital world (see Bitcoin's Academic Pedigree). Bitcoin is the first successful implementation. Unlike most of his predecessors, Satoshi Nakamoto designed the transaction database as a fully transparent public ledger. In Bitcoin, privacy is achieved through breaking the connection between real-world identities and transaction addresses.

Picture14

(Image source: Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System)

On a blockchain explorer, transactions look like this:

Picture2

(Image from Bitcoin Explorer)

For most people, it is extremely challenging to figure out the identities of the sender/recipients just by looking at these alphnumerical strings. However, Bitcoin transactions are not fully anonymous. With the right tools, it's possible to track down exactly who is moving Bitcoins around; and the tools are constantly improving especically when there is financial incentive for malicious actors. Before going into the specifics of the techniques, let's go over some fundamental cryptographic concepts.

Cryptographic primitives of Bitcoin

A hash is a function that maps data of any size (file, video, audio etc.) to data of fixed size (a string). A cryptographic hash function is a special class of hash functions that is designed to preserve the integrity of the data source. After the original file is hashed, it is impossible to derive the input from the fixed-sized output.

Picture3

As illustrated above, the output changes completely when only a single digit of the input is altered. Even though the hash results look uncorrelated, the same message will always return the same hash. However, to produce a specific hash result, you will have to try almost all possible inputs. The ideal cryptographic hash functions are also collision-free, meaning that it is infeasible to produce the same hash value with two different inputs.

Cryptographic hash functions are a critical component in digital signatures. Digital signatures are the public-key primitives of message authentication that guarantees the validity of a Bitcoin transaction. They are used to bind a signatory to the message. Public key cryptography, or asymmetrical cryptography, uses a pair of keys: the public key and private key. Asymmetrical cryptography was revolutionary in eliminating shared secrets between the sender and receiver. Its security relies on mathematical problems that are currently considered too inefficient to solve, such as integer factorization, or discrete log. Profound and difficult theorems in mathematics tend to be more secure when turned into algorithms. The private key and the public key have a mathematical relation that allows one to easily derive the public from the private key, but almost impossible to find the private key from the public key.

The first private-public key scheme was proposed by the legendary Whitfield Diffie and Martin Hellman in 1976, and further inspired industry-grade algorithm such as RSA, developed in 1978 by Rivest, Shamir, and Adleman. Today, Digital signatures are a standard weapon in most cryptographic protocol arsenals.

Picture30

A simplified illustration of RSA

To sign a document, the sender needs to combine a private key with the hash of the document.

Picture4

To verify the signature, the receiver first decrypts the signed document with a public key and compares the results with the hash of the original document. If the results are equivalent, the signature is authentic.

Picture5

The public key in a digital signature is usually the representative of identity. The hash of the public key, combined with a network identifier byte, and a checksum, is the alphanumeric address we see on the blockchain explorer. Digital signatures have a wide range of applications in computer science.

Fermat's last theorem, Elliptic curve, and the NSA

It's important to note that no asymmetric cryptographic schemes is perfectly secure. The underlying algorithms work due to the intractability of the mathematical problem. As computation power improves, cryptography also needs to constantly improve. Bitcoin uses a particular digital signature scheme known as Elliptic Curve Digital Signature Algorithm. The security of ECDSA relies on the algebraic structure of elliptic curve over a finite field.

Elliptic curve gained popularity from the proof of Fermatโ€™s Last Theorem. The theorem, conjectured in 1637, states that no three positive integers a,b, and c satisfy the equation ๐‘Ž^๐‘›+๐‘^๐‘›=๐‘^๐‘› for any integer value of n greater than 2.

Among the many challenges that Fermat left for the world, this was to prove the most difficult. A tantalizingly simple problem about positive integers, it stood unsolved for 358 years until Andrew Wiles proved that semistable elliptic curves over the field of rational numbers are related to modular forms, which implies Fermat's Last Theorem holds.

The elliptic curve has several interesting properties that can be useful in cryptography. Neal Koblitz and Victor Miller introduced elliptic curves to cryptography in 1985. Today, elliptic curves cryptography has been extensively studied. For more detailed tutorial, please see a post by Andrea Corbelini. Based on currently understood mathematics, elliptic curve cryptography proves to be a much more secure scheme than first generation systems like RSA.

An elliptic curve is a set of points that satisfy the equation ๐’š^๐Ÿ=๐’™^๐Ÿ‘+๐’‚๐’™+๐’ƒ, also called Weierstrass Normal Form. As a and b change, the shape of the curve varies too:

Picture6

(Image from Wolfram MathWorld)

Choosing the right curve is essential for security. Many cryptographic standards widely used in commercial applications were developed by the National Institute of Standards and Technology, a government entity that works closely with NSA. In 2007, security researchers found NSA backdoors in some of the cryptographic tools. In an article written by Vitalik Buterin, he describes how Satoshi Nakamoto avoided such threat by choosing secp256k1, a curve that was almost never used before Bitcoin, hence making sure the digital signature scheme in Bitcoin almost impossible to be compromised by backdoors.

Vulnerabilities in Bitcoin transactions

Despite Satoshi Nakamoto's careful and deliberate selection of the cryptographic tools, Bitcoin still is not fully anonymous. Which parts of the network are vulnerable to privacy attacks? Let's review the transaction process step-by-step:

Picture8

Recall that the Bitcoin network is a public ledger. During the transaction process there are several steps the data feed interacts with the public network. Before sophisticated tools such as Chainanalysis were developed, people often try to find basic patterns in transactions that happen frequently between the same addresses. Over the years, many methods have been tested to reveal the real identities of the senders and recipients. Due to the linkability of the transactions, we say Bitcoin is pseudo-anonymous. To compromise the pseudo-anonymity is to associate identity information with a series of transactions. Such information can be acquired during the highlighted steps below:

Picture9-1

De-anonymizing bitcoin transactions

The common techniques to denonymize a transaction can be summarized into two categories: network analysis and blockchain analysis.

Network analysis entails tracking down the IP of the node initiated the transaction. At the 2011 Black Hat conference, Dan Kaminsky suggested that due to the P2P nature of the network, "when you are connected to every node, the first node inform you of a transaction is the source of it." This recognition inspired some new experiments with network layer IP analysis. It is especially effective when multiple nodes coordinate and listen to the network. An example of this method is CoinSeer. This kind of exposure can be partially mitigated by using Tor or some other i2p services. However, not only is Bitcoin-over-Tor hard to use, extensive studies have shown that the IPs are not fully protected. Plus, i2P and Tor themselves are not fully anonymous under certain attacks.

A more common type of attack is blockchain analysis. Through collecting a magnitude of transaction data, the adversary is able to cluster and tag the identities of participants. Open Bitcoin Privacy Project lists linking network identity to Bitcoin address as one of the top threats.

Such type of clustering attack is possible because of the "cash" characteristic of UTXO, the data structure responsible for tracking the balances on Bitcoin public ledger.

Picture12

The design rationale of UTXO is to help tracking the flow of transactions such that it is easier to check double-spending. A UTXO is like a bank note and each one is unique. A userโ€™s wallet contains a set of UTXOs. Supposing the Sender needs to send 5BTC, the Bitcoin client will extract UTXOs with sum of value larger or equal to the transaction amount (3BTC and 4BTC), and the difference will be a new UTXO deposited back to the Sender.

Picture11

As the illustration shows, sometimes a transaction can have multiple inputs. These different inputs are evidence of account ownership. With the right tool, the adversary can link multiple inputs to find out the controller of these addresses. This process can be repeated many times to plot out an entire cluster of transactions belonging to a single entity or individual. We call these transactions linkable. Some of the heuristics employed in the linkability analysis are:

Shadow Change: Change public key has never been seen before in the blockchain.

Optimal Change: Wallets do not spend unnecessary outputs if there is a unique output with a value smaller than any inputs.

Consumer Change Transactions from consumer's wallet have less than 2 outputs.

After linking and clustering the transactions, the adversary can tag the central servers in the network after interacting with them to associate real-world identities with the transactions. Common service providers are exchanges, wallets, mining pools, and vendors. Below is a transaction graph plotted by researchers Meiklejohn et al in 2013 in the article A fistful of Bitcoins: characterizing payments among men with no names. Each grey line contains at least 200 transactions between two nodes. The size of the circles represents the comparative volume of capital transacted.

Picture10

(Image source: Meiklejohn, Sarah, Marjori Pomarole, Grant Jordan, Kirill Levchenko, Damon McCoy, Geoffrey M. Voelker and Stefan Savage. โ€œA fistful of bitcoins: characterizing payments among men with no names.โ€ Internet Measurement Conference (2013))

Why privacy matters

For service providers or e-commerce platforms accepting Bitcoin, such exposure can invite many unwanted trouble. Your competitors will know exactly how much volume you are handling, and hackers/social engineers can create more specific strategies to attack. Especially if your address shows up on the list of Top 100 Richest.

Privacy is also an essential basis for fungibility, and fungibility is a fundamental property of a currency. It means very coin is worth the same value and is thus mutually interchangeable. Bitcoin is not fungible, because of the public ledger used to track all historical transactions. Some tokens may be blacklisted or overpriced as a result of previous transactions.

In order for a token network to be fully fungible, it must maintain privacy on the public ledger. How anonymous is anonymous enough? To be fully anonymous, we require the transaction network to be untraceable and unlinkable, which means it is impossible to link together different addresses of the same user, impossible to link sender of a payment to its recipient, and impossible to link together different transactions made by the same user. But how do we know if a network is truly anonymous? How do we quantify the system's anonymity?

Measuring (and effecting) anonymity

Anonymity on networks is not binary measurement but a spectrum. In 1988 Chaum introduced the concept of anonymity set. It is defined as the set of participants who could have sent a particular message, as seen by a global observer who has also compromised a set of nodes. It is common to use the cardinality of the set as a measurement of anonymity. Increasing the privacy of a network is maximizing the anonymity set to any adversary.

Over the years, researchers proposed and tested new methods to enhance Bitcoin privacy against blockchain analysis. Various techniques that achieved relative success are more-or-less based on the concept of mixing (sometimes referred to as tumbling). As the name suggests, mixing combine several transactions together to obfuscate the addresses of a particular transaction.

Picture15

Mixings are usually done through a dedicated service provider. Some notable implementations include CoinJoin and ValueShuffle.

Lightning Network could also potentially increase the privacy of the network. While it is not specifically designed for privacy purposes, using multiple hops in the Lightning Network could potentially obfuscate a transaction's origin. However, if the Lightning channel is opened only for direct transactions, those transactions will be aggregated and recorded into the blockchain after close, and anyone listening on the Lightning during this process could still have observed all these transactions.

Next: Comparing approaches to privacy in Monero and Zcash

None of these forms of anonymization are perfect; for example, in the case of mixers, the centralized mixer itself could be malicious and steal customers' assets. More advanced anonymization techniques are explored over years in some alternative protocols. We will discuss anonymization techniques in further detail in Part II.