Introduction
Welcome to the first post from The Stack Report! As part of the Cypher Stack Research Team, our goal here is to present the complex ideas of Monero in a concise and understandable way. The topics we plan to cover can range from current legislation regarding privacy, to research projects in privacy-focused cryptocurrencies like Monero, Firo, etc. While our research team has some very qualified people, we take pride in the fact that we aren’t dry, so we’ll do our best to make this material as approachable as possible! If you have any questions or comments, please email us!
For our first report, we’re going to focus on our favorite cryptocurrency, near and dear to our hearts, Monero! More specifically, we are going to summarize a recent report from our research team about a common practice called “churning.” Now, we assume that if you’re reading this, you’re already familiar with the basics of the Monero protocol, but regardless, we want to give a bit of background because the bulk of the paper can get quite technical.
First off, as the primary privacy cryptocurrency, Monero has a number of high-level protocols in place to enforce an exceptional degree of confidentiality. One of these protocols is called a ring signature, an efficient way for Monero users to sign and verify the authenticity of transactions. Ring signatures are where any user in the permitted group can perform operations with the signatures, but that specific user can never be linked to a single identity.
Think of this like a company: any one of the high-level officials can represent the institution and sign a document, but their name is never attached, it just says “signed by an official.” In fact, one of the requirements is that this anonymity can never be revoked, meaning that even if an official is fired, it can never be retroactively revealed exactly which documents they signed. Practically, this guarantees that your identity is safe - nobody can go back and uncover which Monero transactions you took part in.
Check out the graphic below to get a great visual for how it works!
With this in mind, let’s move onto churning, an interesting action (not part of the basic protocol!) that one can take to increase privacy in Monero, which involves sending funds to your own wallet. This may initially seem pointless - after all, aren’t you effectively taking money out of your wallet then putting it right back in? Not exactly, because there’s a subtlety here. Think of churning as going to the gas station and asking them to split a bill for you. You’ve taken money out of your wallet and put the same amount right back in, but now any serial numbers on the bills that could be used to identify you are no longer in your possession.
Each churn acts to separate your transaction from you, forcing an adversary to do more work to uncover your personal information! Many zero-knowledge schemes utilize the same concept, where an adversary can never determine if a transaction is legitimate or if a user is just creating chaff by sending themselves transactions.
Check out the graphic below to get a great visual for that works too!
To give a numerical example, suppose that we’re working with transactions in a standard ringsize of 16. If I send you XMR, then I know where that transaction sits on the blockchain, as I was a part of it. When you spend those funds, I can see that a transaction took place as it’s linked in the ring, but won’t know for sure who was doing the spending. If you churn, I’ll similarly be unable to determine who was sending funds, but I can guess there’s a 1 in 16 chance that you spent the XMR I sent, linking you to those funds. If you churn again, then it’s a 1 out of 16^2 chance. Again, and now it’s 1 in 16^3. See what’s happening here? After just 3 churns, there’s only about a 0.025% chance that I can link that final transaction to the original funds I sent you - I’m as likely to be dealt four of a kind in my first hand of 5-card poker than I am to naively identify those funds.
We illustrate this in the graphic below, where an adversary (with the unibrow) is trying to track your (purple) spending.
In the paper mentioned above (https://github.com/cypherstack/churn), we identify a Uniformly Most Powerful (UMP) test that aims to classify which transactions on the blockchain are churns. UMP means that for any set of parameters, there is no other test that can outperform it, so long as it satisfies the same assumptions. The existence of this test has long been an open question. This test helps to track the statistical dynamics of churning, and has already been recognized as “an important contribution to the analysis of churning”.
Obviously, any algorithm capable of efficiently and correctly identifying churning transactions from ad hoc, or “normal” transactions, would be detrimental to Monero’s privacy. After all, since ring signatures use prior transactions to protect the privacy of an ad hoc transaction, knowledge of which users are churning means that the ring signature’s privacy pool would shrink! Even if the original 1/16 chance of identifying an ad hoc transaction decreases to 1/15, such an algorithm could have far-reaching repercussions!
We illustrate this with the graphic below wherein the purple transactions are correctly labeled as churned transactions. The end of the graphic shows the shrinkage of the ring sizes as a result.
One positive finding of our paper is that this UMP test is actually unreliable! This test has too high a probability of misclassification to be considered dependable in a practical setting. When using the standard significance level of 0.05, we get that 95% of ad hoc transactions will be wrongly miscategorized as churns - but this is actually a good thing! Due to the definition of a UMP test, across all parameter sets, there is no other test that can be more powerful than the one derived. Therefore, if the best uniform test is still quite ineffective, then this serves to strengthen trust in Monero’s formalism.
With that said, one could raise a cromulent point: “if the UMP test is for a specific set of parameters, what if there is a better set of parameters that corresponds to a more accurate test?” This might give pause, however our paper already goes so far as to assume the best possible parameters for a naive adversary! Returning to our gas station example, suppose an individual is churning to hide their real transactions. Is said person more likely to go to the gas station and split bills every single day even if they have no transactions, or would they just go split bills immediately following a legitimate transaction? Our belief here at the Cypher Stack Research Team is that simple human psychology suggests that the second option is much more common than the first.
It’s this sort of mindset that permits naive statistical analysis of churning, where an adversary might gain an advantage by assuming that the first in a small, close-knit collection of transactions is the real one, with the rest being chaff. The current provisional patch is to hold off on churning after a legitimate transaction for some random amount of time, according to a delay distribution, in an attempt to appear more equidistributed. Our assessment is that even using the strongest test available with the best possible parameters, this type of advantage is not conclusive: the rate of misclassification will still be extremely high.
All that being said, there is still much more (always more!) to be done in this line of research. It’s possible there exists a parameterization of this UMP test using derived empirical data, or it may be feasible to extend the model to formally implement taking Bayesisan updating into account, to improve outcomes in the case that the UMP test indicates a churn correctly. As with most churn research, all of the above leaves plenty of unanwered questions. The fact that a UMP exists at all is enough to make some of us nervous. The awesome news is that Monero’s upcoming Full Chain Membership Proofs (FCMP) upgrade will be going live relatively soon, and all of the above will no longer apply.
Either way, we at the Cypher Stack Research Team head back to our research hovels to crunch more numbers. We’ll see you again real soon and hope you stay tuned for the next installment of The Stack Report!