Privacy in Cryptocurrencies: Mixing-based Approaches

Yi Sun and Yan Zhang

(This article is part of a series whose other parts can be found here and here.)

In this sequel to our previous post, we discuss mixing, the earliest approach to privacy in cryptocurrencies. Mixing obscures the linkage between the inputs and outputs of individual transactions by combining (or mixing) them with inputs and outputs of other transactions. For this to work, different inputs and outputs must be interchangeable, or fungible, meaning that transactions must represent transfers of a coin or token, each unit of which is considered the same. In this post, we only consider protocols and transactions of this nature.

As a simple example, suppose that Alice wants to send 10 units of a hypothetical MixCoin to Bob. In a standard Bitcoin-like protocol, she would simply make a single transaction transferring 10 MixCoin from her address to Bob’s address. Mixing-based techniques alter this transaction flow in different ways, allowing Alice to either:

• (CoinJoin) find a user Cindy who also wants to send 10 MixCoin to a user David and arrange with them to combine transactions into a single transaction where Alice and Cindy send two outputs of 10 coins to Bob and David;
• (Mimblewimble) allow miners to aggregate all transactions mined in a block by including only the grouped inputs and outputs and omitting which inputs and outputs are part of the same transaction;
• (Monero) group Alice’s 10 MixCoins with several randomly selected coins belonging to other users and send them in a way which only reveals that one of these was spent (but not which one).

These methods require different amounts of effort on Alice’s part and offer different benefits on the axes of identity, transaction data, and blockchain state discussed in our previous post. In this post, we trace the concept of mixing from its origins in tumblers and CoinJoin to its more advanced recent incarnations in Mimblewimble and Monero, evaluating these axes along the way. Of particular importance will be the size of the resulting anonymity set, which, we recall, is the smallest collection of addresses the sender of a transaction can be narrowed down to, and which measures the effectiveness of a protocol at obscuring linkages between addresses. We now dive into each of these protocols.

Tumblers

Mixing originated as a method to defeat blockchain analysis in Bitcoin. The simplest way to conceal the origins of a set of coins is to use a third party service called a mixer or tumbler (e.g. bitmixer.io). If Alice wishes to tumble 10 BTC, she (and a large group of other users) can send 10 BTC to Tim’s Tumbling Service. Then, Tim can send 10 BTC (less a small fee) which was received from another user Bob to another address owned by Alice. This way, when Alice later uses the 10 BTC she received, there will be nothing on the blockchain to link it to the 10 BTC she originally sent to Tim. Though this method keeps all output amounts and transactions public, it can sever the links between real world identities and addresses.

A non-cryptographic mixer

There are a number of drawbacks to this type of mixing. First, Alice and the other users of the tumbler must trust Tim to send them back coins. While they can use reputation to do so, they have no cryptographic protection against Tim simply keeping all the coins or being hacked, and this type of incident was frequent in the early days of Bitcoin. Protocols such as TumbleBit which run on top of Bitcoin have been developed to address this, but have not gained wide adoption. In addition, Tim has the ability to track all coins which go through his mixer, meaning that he can link users’ deposits and withdrawals from the tumbler if he wishes to. Second, and less maliciously, the centralized operator of the tumbler may run afoul of various anti-money laundering and money transmission regulations. Third, if Alice wishes to mix 8.29387541 BTC instead of 10 BTC, it may be possible to link the two transactions between Alice and Tim using the fact that both involve the rare amount of 8.29387541 BTC. Finally, the anonymity set provided by the tumbler is dependent on the number of users of that specific tumbler at the time of mixing, which may be difficult for Alice to predict or even measure.

CoinJoin

To remove the requirement for a trusted third party, the CoinJoin method was developed for Bitcoin by Greg Maxwell, one of the Bitcoin core developers. It can be thought of as a way to implement a tumbler which uses cryptography to avoid trusting a third party. More specifically, if Alice, Bob, and Carol each have a 10 BTC input and wish to use CoinJoin to mix them, they can use Tim’s CoinJoin service to construct an (unsigned) transaction sending these three 10 BTC inputs to three new 10 BTC outputs. Tim can then send the final transaction to each of Alice, Bob, and Carol for their signature; once each of them has signed, Tim will then broadcast the transaction to the Bitcoin network. Due to the properties of cryptographic signatures, this process does not require that Alice, Bob, and Carol trust Tim or each other, instead allowing them to only rely on Tim to bring them together.

This transaction will thereby obscure the origin of the outputs; in particular, an external observer will not be able to associate any particular output with a particular input, giving an anonymity set of size 3. This property hinges on the fact that the three 10 BTC inputs had the same amount. If instead Alice had a 20 BTC input, to participate in the same CoinJoin group, she would need to first split it into two 10 BTC inputs, changing the CoinJoin transaction to have four 10 BTC inputs and four 10 BTC outputs.

As with tumbling, output amounts and addresses are public, but by combining different transactions together, CoinJoin prevents observers from linking input and output addresses. When used with a larger number of users and repeated, the CoinJoin method can provide increasingly large anonymity sets. Unlike a tumbler, CoinJoin provides users cryptographic security over their coins. Namely, it leverages the specific transaction format of Bitcoin, which allows each user to provide an independent signature for their input, with the transaction being aggregated off-chain and only being broadcast once all users have signed. Users therefore do not need to rely on a trusted third party to execute mixing transactions honestly.

However, a number of drawbacks remain. First, because CoinJoin relies on off-chain coordination, users must themselves find other online users who wish to run CoinJoin with them. In cryptocurrencies such as Dash, this problem is achieved by incentivizing special nodes called masternodes with block rewards to stay online and perform CoinJoin transactions. Second, the sizes of the outputs should all be identical, making the coordination problem more difficult. Finally, the users involved in the CoinJoin itself will be able to learn the matching between inputs and outputs, though this can be addressed by more complicated variants such as CoinShuffle.

Mimblewimble

Proposed anonymously by the pseudonymous Tom Elvis Jedusor (Voldemort’s real name in the French translation of Harry Potter) in an IRC channel in August 2016, the Mimblewimble protocol (named after the Tongue-Tying Curse) proposes a new blockchain structure in which all transaction amounts and balances are hidden, while input and output addresses are obscured. As of December 2018, the Mimblewimble protocol is being implemented in two different cryptocurrencies:

• Grin, a proof-of-work blockchain project created by a group of anonymous developers with Harry Potter pseudonyms in March 2017;
• Beam, a proof-of-work blockchain project adding Confidential Assets, opt-in auditing, and a founder’s reward created by an eponymous startup in March 2018.

Both cryptocurrencies are undergoing testing before launch. To understand the technical details of the protocol, we first need to briefly discuss commitment schemes in cryptography.

A commitment scheme is a cryptographic primitive which allows a user to commit to the value of a piece of data (so that it cannot be changed later) while keeping the data secret. For example, if Alice and Bob are playing rock-paper-scissors, but each does not trust the other not to cheat by playing later, they can each write down commitments to a play and then determine the outcome of the game by revealing their plays. Mimblewimble uses a commitment scheme with blinding, which consists of a function which takes in some data X and a blinding factor B (an additional number, usually chosen at random). The function

C = Commit(X, B)

is carefully chosen so that if Alice tells Bob the value of C (called a commitment), Bob cannot recover any information about X. At a later time, Alice can choose to reveal the value of the data X and blinding factor B. Bob should be able to easily check that Alice knew those values earlier when she gave Bob the commitment C by checking that C = Commit(X, B). This relies crucially on the fact that it is essentially computationally impossible for Alice to later fabricate different values X’ and B’ such that C = Commit(X’, B’), which allows Bob to trust that the values of X and B told to him by Alice are truthful.

Mimblewimble represents the data, blinding factors, and commitments as elliptic curve points, which can be thought of as algebraic objects which can be added (like numbers in modular arithmetic). It is therefore able to use homomorphic commitments, meaning that the commitment scheme satisfies

Commit(X1, B1) + Commit(X2, B2) = Commit(X1 + X2, B1 + B2).

The specific homomorphic commitment scheme used is called a Pedersen commitment and relies on elliptic curve cryptography. Though the specifics will not be necessary for the rest of this post, we mention the key property that a user with knowledge of the blinding factor B for Commit(0, B) can prove this knowledge without revealing B using a cryptographic signature.

Mimblewimble is based on an idea from Greg Maxwell’s proposal for Confidential Transactions (CT) in Bitcoin. Instead of using unspent transaction outputs (UTXO’s) as in Bitcoin, coins in Mimblewimble are stored on the blockchain as homomorphic commitments to output amounts. Private keys are then implemented as the blinding factors. For example, if Alice owns 10 coins with a private key of 1337, they will be represented on the blockchain only by the number Commit(10, 1337), which looks like a random number to everyone except for Alice.

If Alice then wants to send 6 coins to Bob, she generates a new private key, say 201, for her change and create the output Commit(3.9, 201). She then tells Bob the amount (6 coins) and the difference between her old and new private keys (1337–201 = 1136). Bob generates his own new private key, say 1000, his output Commit(6, 1000), and a small transaction fee, and creates the transaction

• Inputs: [Commit(10, 1337)]
• Outputs: [Commit(3.9, 201), Commit(6, 1000)]
• Transaction Fee: 0.1

To make sure that the transaction is valid, Alice and Bob must also include:

• A signature using the excess blinding factor (1136–1000 = 136, where we recall 1136 is the difference between Alice’s old and new private keys) as a private key and Commit(0, 136) as public key proving that Bob has knowledge of this private key. Bob’s ability to create this signature is the special property of Pedersen commitments used in this protocol.
• Proofs that the number of coins in Commit(3.9, 201) and Commit(6, 1000) is positive (as allowing negative coins could allow Alice to create coins out of thin air). These are called range proofs (Grin uses Bulletproofs) and may be created without revealing the number of coins in the commitment.

To check the transaction, validators check that the range proofs are valid and that the signature is valid for the difference

Commit(3.9, 201) + Commit(6, 1000) + Commit(0.1, 0) - Commit(10, 1337) = Commit(0, 136).

This ensures that the total number of coins in circulation does not change (it is given by the data portion of the sum of all commitments), and that Alice indeed knows the private key for the input she is spending. After this transaction, only Alice and Bob know the private keys and amounts for their respective outputs; however it is public information that the input Commit(10, 1337) was spent into the two inputs Commit(6, 1000) and Commit(3.9, 201).

Transaction aggregation in Mimblewimble

To further hide transaction information, Mimblewimble merges all transactions in a block. Suppose Carol sends coins to David in a separate transaction from Alice and Bob. If those transactions are included in the same block, for the purposes of transaction verification, the only relevant data are:

• the list of inputs and outputs
• the sum of all the excess blinding factors
• range proofs for each output

In particular, these do not rely on the grouping of inputs and outputs into transactions, so Mimblewimble simply forgets these after placing transactions into blocks, effectively performing a CoinJoin-like procedure on all transactions appearing in a block and obscuring links between input and output addresses. This aggregation can be done by groups of users using a CoinJoin-like procedure or during transaction propagation at the network level using the Dandelion++ protocol, which makes it more difficult for an observer to deduce that which inputs and outputs belong to the same transaction.

Mimblewimble applies one further trick. When validating transactions, notice that the state of the chain is given only by the set of unspent outputs, so spent outputs can be eliminated in a procedure called cut-through. In addition, due to the constraint that the sum of all commitments commit to the total number of coins, this set cannot be easily tampered with without making the chain state invalid. The result of all this is that we may treat the combination of this set of unspent outputs and a set of recent blocks as the shared consensus state, which is a model which notably differs from a traditional Bitcoin-like blockchain. In particular, new users can check that this state is valid without knowing the full transaction history, and its size is proportional to the number of unspent outputs. This means that those users can trustlessly sync Mimblewimble using significantly less bandwidth and storage.

It also has hidden transaction amounts and partially hidden input and output addresses. A few potential issues remain in this protocol. First, while transactions are joined together within each mined block, a listener Eve can still attempt blockchain analysis by pretending to be a miner and recording the individual transactions she receives from users before they are included in blocks. As we mentioned earlier, using transaction aggregation through the Dandelion++ protocol can mitigate this attack to some extent, but it remains to be seen empirically whether it can enable Eve to reduce the anonymity set of the sender. Second, due to the nature of the transaction structure in Mimblewimble, the sender and recipient must communicate before making a transaction. This means that the recipient must be online in order to receive coins, which may be an obstacle to practical adoption.

Monero

Monero (XMR) was originally based on the Cryptonote protocol proposed in a whitepaper by the pseudonymous Nicolas van Saberhagen in October 2013, but has since evolved significantly to incorporate ideas from Greg Maxwell and Adam Back. It was launched as Bitmonero by an anonymous team of developers in 2014 and later forked to Monero after some disagreements on the direction of the project. The protocol combines two core cryptographic ideas:

• Ring signatures allow users to obfuscate the set of inputs appearing in a transaction. In Monero, an extension called RingCT is used which additionally hides transaction amounts in a manner similar to that of Mimblewimble.
• One-time addresses allow users to receive each payment at a unique address used only for that payment without interacting with the payment sender.

We now explain each of these as it relates to Monero.

As in Mimblewimble, coins in Monero are represented as homomorphic (Pedersen) commitments Commit(X, B) to the number of coins X and blinding factor B. Suppose that Alice has a 10 XMR output and wishes to send 7 XMR to Bob. In Mimblewimble, she would use only her output, feeding it into a transaction as an input. However, in Monero, Alice must specify decoy inputs called mixins to prevent observers from guessing which inputs are actually used in the transaction. To do so, she creates what is called a ring signature for them.

A ring signature is a cryptographic procedure which produces a single signature from a single private/public key pair and set of unrelated public keys. The ring is the set of public keys in the signature, and ring signatures have the property that someone verifying the signature cannot identify which member of the ring created the ring signature. Monero uses a linkable ring signature, meaning that it is possible to detect if the same private key is used to sign two different messages; this is crucial to detect doublespend attempts. The signature scheme used in Monero stems from one invented by Adam Back and is adapted to Pedersen commitments; we will not describe it in detail here.

Example of a transaction with 2 real inputs and 6 mixins in Monero

For Alice to send 7 of her 10 XMR to Bob, she first chooses at least 6 other outputs (possibly not belonging to herself), known as mixins. She must then generate a random number and combine it with Bob’s public address and her public address to generate two unique one-time addresses to send to, one for the 7 XMR payment to Bob and one for her 3 XMR change. This procedure yields

• two one time addresses, one for Alice and one for Bob, and
• a transaction public key derived from the random number.

For any transaction, Bob can combine his private key and the transaction public key to test whether he is the recipient of any outputs from that transaction. If he is a recipient, he can also view the amount of XMR he has received.

After generating one-time addresses, Alice creates output commitments Output_Bob and Output_Change intended for each one-time address. She then creates a ring signature with the output she wishes to spend and the mixins she has chosen. A special feature of RingCT is that this signature can also include a proof that

Amount(Input_Alice) = Amount(Output_Bob) + Amount(Output_Change)

without revealing to an outside observer which input in the ring is the true Input_Alice or any of the quantities Amount(Input_Alice), Amount(Output_Bob), or Amount(Output_Change).

To form a valid transaction, Alice now needs to generate range proofs (Monero recently hard forked to use Bulletproofs) for each output to show that the number of coins in each output is positive, i.e. Amount(Output_Bob) > 0 and Amount(Output_Change) > 0. These proofs prevent Alice from counterfeiting coins by creating an output commitment Output_Bob with -5 coins and an output commitment Output_Change with 15 coins.

Combining all of these, Alice can finally broadcast a transaction consisting of:

• a list of input commitments consisting of Alice’s input and mixins
• a list of output commitments
• the ring signature for the Alice’s input and mixins (which contains a proof that the amounts of the inputs and outputs have equal sum)
• a list of output addresses consisting of Bob’s one-time address and Alice’s one-time address for change
• a list of range proofs, one for each output, proving that the output amount is positive
• a transaction fee in cleartext

The Monero blockchain is a standard proof-of-work blockchain consisting of such transactions. Monero mandates that each transaction have ring size at least 7, meaning that each transaction has anonymity set at least 7. If transactions are iterated a few times, this can lead to anonymity sets which are substantially larger. In addition, unlike in CoinJoin, this anonymity set can be achieved in a non-interactive way, meaning that a transacting user does not need to coordinate with anyone else. For this reason, the ring signatures of Monero are often called a form of decentralized mixing, though the underlying cryptographic mechanism is completely different.

The features of Monero combine to create a blockchain with hidden transaction amounts and partially hidden input and output addresses. Although it makes transaction linkage more difficult compared to Bitcoin, there are still attempts to perform blockchain analysis on Monero. An attacker David might be able to learn which of the several possible sender addresses is the real one in a ring signature by:

• owning them himself
• guessing which inputs are mixins using heuristics such as their creation time or their involvement in other transactions
• examining usage of those inputs on hard forks of Monero (as analysed here).

Using these techniques to deduce whether specific outputs are spent or not, David can try to iteratively grow his knowledge of the true inputs to different transactions and thus the common ownership of different outputs by a single entity. These type of techniques were applied to the initial versions of the Monero protocol in this paper, where their success was crucially linked to the minimum ring size for each transaction. As noted in this response, the minimum was set to 1 in the version of the protocol being analyzed, while it has since been raised to 7 in the version of Monero used today, making similar analysis significantly more challenging.

Conclusion

Mixing-based techniques fundamentally leverage the fungibility of cryptocurrencies to improve different aspects of their privacy. On the other hand, fungibility itself relies on the ability to treat all coins in a cryptocurrency equally. In particular, this requires the ability to separate a coin from its transaction history, as users could otherwise discriminate based on its past owners or transaction types. This separation is an aim of privacy itself, creating a symbiotic relationship between fungibility and mixing-based privacy.

In the initial version of mixing, tumblers and CoinJoin used fungibility to hide the linkage between senders and recipients of transactions. These techniques allow users to obscure the link between their real-world identity and the on-chain address of their coins, though the anonymity set is constrained by the need to trust a third party for tumblers and to find willing participants in CoinJoin. The more advanced incarnations of Mimblewimble and Monero allow mixing to happen asynchronously by miners batching transactions in blocks in the case of Mimblewimble and the use of ring signatures to achieve non-interactive mixing in the case of Monero. In these two protocols, fungibility also allows the use of homomorphic (Pedersen) commitments to hide transaction amounts completely. We summarize the impacts on different aspects of privacy in the following table.

The ultimate impact of these protocols on privacy will rest upon the ability of their cryptographic techniques to provide sufficiently large anonymity sets in practice. With their launch and evolution in the wild just beginning, we are excited to see how they develop. In our next post, we will discuss several other families of protocols based on a line of cryptographic techniques known as zero-knowledge proofs which offer different types of guarantees.

Thanks to Mihaly Barasz and Sizhao Yang for reviewing drafts of this post.