Breaking Mimblewimble’s Privacy Model
TL;DR: Mimblewimble’s privacy is fundamentally flawed. Using only $60/week of AWS spend, I was able to uncover the exact addresses of senders and recipients for 96% Grin transactions in real time.
The problem is inherent to Mimblewimble, and I don’t believe there’s a way to fix it. This means Mimblewimble should no longer be considered a viable alternative to Zcash or Monero when it comes to privacy.
In the last two years, Mimblewimble has grown in popularity as an up-and-coming, lightweight privacy protocol. Mimblewimble was invented in 2016 by a pseudonymous hacker known as Tom Elvis Jedusor, who dropped a text description of the protocol into an IRC chat and then disappeared. Since then, Mimblewimble was most famously implemented in the “fair launched” privacy coin Grin, the VC-backed projects Tari and BEAM, and is even being considered for integration into Litecoin.
Several researchers have hypothesized a possible privacy weakness in Mimblewimble [1][2][3][4]. My contribution is to demonstrate the precise way to perform an attack, prove its viability on a live network, and measure its efficacy. In live testing on Grin, I was able to unmask the flow of transactions with a 96% success rate. Therefore, it’s now clear that Mimblewimble should not be relied upon for robust privacy.
Here is a more technical deep-dive into this attack, complete with open-source code to reproduce it, data collected, and a technical FAQ. What follows in this article will be a high-level, intuitive explanation of linkability, how the attack works, and what it means for privacy tech.
What is linkability?
It’s important to understand what this attack means and what it doesn’t mean.
This attack does not let us determine the amounts that people are getting paid. Mimblewimble successfully obfuscates payment amounts using vanilla elliptic curve cryptography (Pedersen commitments). What this attack does let us do is determine who paid who. In other words, it lets us link transactions together and determine the flow of payments.
It might not be obvious why that’s a big deal.
Say Coinbase knows that a certain address belongs to a Venezuelan individual named Daniel. You, an American user, try to cash out on Coinbase. But after deobfuscating the transaction graph, Coinbase determines that you received money from Daniel, though they don’t know how much you received. Due to OFAC restrictions on Venezuela, Coinbase shuts down your account. (Naturally, exchanges will know a lot about the transaction graph because they have KYC information on users who cash out into fiat.)
Or say an authoritarian government knows that a certain address belongs to a political dissident. You send that dissident a small donation. Later, when you send your Mimblewimble transfer to the local exchange, that exchange shares your transaction data with the government. Since the government can see the entire transaction graph, they now know that you supported a political dissident.
These attacks would not be possible in Zcash. This is because Zcash is unlinkable — or in other words, every Zcash shielded transaction has a large anonymity set. The anonymity set is essentially the set of transactions that your transaction is indistinguishable from. Think of it like blending into the crowd: the larger the anonymity set, the larger “crowd” your transaction is mixed into.
In Zcash, each shielded transaction’s anonymity set includes all shielded coins. This is the maximum possible anonymity from an information theoretic perspective.
In Monero, each transaction’s anonymity set is the set of all (believable) decoy transactions. While the Monero client lets you specify the size of the decoy set, the current default is 11. (Monero has its own issues around securely sampling decoys, but I believe it mostly works, give or take.)
It was originally believed that Mimblewimble’s anonymity set includes all the transactions in the same block and looks like this:
But in reality, it looks like this:
This whittles down Mimblewimble’s anonymity set to a single address.
To be clear, this is not an indictment of Grin. I have great respect for the Grin community and core developers, who have all been tremendously helpful in answering my questions.
Grin still affords a stronger privacy model than Bitcoin or other non-privacy coins, since amounts are safely encrypted. But Mimblewimble provides a strictly weaker privacy model than Zcash or Monero. This makes it insufficient for many real-world privacy use cases.
A high-level overview of the attack
So how exactly can you trace the transaction graph in Mimblewimble?
I noted that despite encrypting the payment amounts, Mimblewimble still leaves a linkable transaction graph. But the protocol designers were aware of this, so Mimblewimble uses two chief techniques to combat linkability: the first is full-block cut-through aggregation, and the second is Dandelion.
The idea behind block cut-through is that as transactions are accumulated within a block, those transactions get aggregated into one “super-transaction”. That “super-transaction” basically looks like one giant CoinJoin — essentially, all of the inputs and outputs are tossed into one giant bucket, with no easy way to determine who paid who within that bucket. There’s just a bunch of inputs going to a bunch of outputs, with amounts obscured.
Sounds solid, right? Only one problem: this CoinJoin has to be built up one transaction at a time. Because transactions are continually being created and broadcasted from separate places, if you run a sniffer node that picks up all transactions before cut-through aggregation is finished, it’s trivial to unwind the CoinJoin. Any sniffer node can just observe the network and take note of the original transactions before they get aggregated. It’s pretty straightforward if you just archive all messages you observe in the P2P network.
Wait — really? Is that all there is to it?
Well, there’s another line of defense that the Grin team put up: Dandelion protocol. Dandelion is a networking technique developed by researchers at CMU that attempts to obfuscate the originator of a transaction.
Normally, in a cryptocurrency like Bitcoin, the originator of a transaction just shouts their transaction to all of their peers, and it quickly cascades through the P2P network. But in Dandelion protocol, every transaction broadcast starts with a secret game of telephone. The originator will whisper their transaction to just one peer, who whispers it to one other peer, and so on in a chain. After a random number of hops, the final peer will shout out the transaction just as in Bitcoin. But this peer is so far removed from the originator, for any observer it’s impossible to tell who the chain started with.
This works great for obfuscating the IP of the transactor. But Dandelion has a second function within Grin: it just so happens to defeat sniffer archive nodes. Because every transaction starts off in a Dandelion chain, whenever two transactions cross in their Dandelion chains, they’ll get aggregated early. If this happens, then by the time the transaction is broadcast for everyone to observe, a sniffer node cannot disaggregate them. They’ve already been CoinJoined.
Against a sniffer node, this is Grin’s principal defense against linkability. But even this defense can be defeated.
By default, each Grin node connects to 8 other peers. But by jacking up the number of peers, I can connect my sniffer node to every other node in the network. Assuming I stay alive long enough, eventually almost every node will connect to me, making me a supernode.
Once I am a supernode, there’s a high probability that I will be on the Dandelion path for any transaction. Therefore, the only way that I cannot catch a transaction before it is aggregated is if two transactions both intersect in their Dandelion path before I see either of them. If I see either transaction before they’re aggregated, I can use simple set subtraction to disaggregate them.
In my attack, I was able to link 96% of all transactions while only connecting to 200 peers out of the total 3000 peers in Grin’s network. But if I wanted to spend a bit more money, I could easily connect to 3000 nodes to disaggregate almost all transactions. I also don’t have to do this as a single supernode; the same attack works by launching 3000 separate nodes with unique IPs, each only connected to one peer. As long as I’m sniffing all the transaction data and dumping it into a central master database, the attack works just the same.
So is Mimblewimble salvageable?
It depends. I believe that Grin, as currently envisaged, has no clear path to unlinkability. Simply ratcheting up the Dandelion factor can be easily combated by a motivated attacker, as I discuss in the technical writeup.
But linkability aside, Mimblewimble still has unique and valuable properties! It allows cut-through aggregation, which is an effective compaction technique for full nodes, and efficiently hides transaction amounts. If you want strong privacy, you can always combine Mimblewimble with another protocol that obscures the transaction graph, such as in Ethereum 9¾ (which combines Mimblewimble with a Zerocash-style commitment-nullifier scheme).
But it’s clear that Mimblewimble on its own is not strong enough to confer robust privacy.
Bitcoin is now 11 years old, but cryptocurrencies are still in their infancy. It wasn’t that long ago that devastating bugs were uncovered in both Zcash and Monero. This is to be expected — most of the interesting technologies are still in the realm of basic science.
But this is how science always advances: we propose new theories, and then repeatedly knock them down, until what’s left standing has stood the test of time.
Thanks to Haseeb Qureshi for major help in putting together this write-up and for the anonymity set illustrations. Additional thanks to Oleg Ostroumov, Elena Nadolinksi, Mohamed Fouda, Lucas Ryan and Nader Al-Naji for reviewing drafts of this post. And a huge thanks to Jake Stutzman (NEAR Protocol) for the Dandelion and block aggregation illustrations.
For more of my writing, follow me on Twitter at https://twitter.com/IvanBogatyy.
Disclosure: Dragonfly Capital abides by a no-trade policy for the assets listed in this report for 3 days from the date of publication.
