c Monero Research LabRESEARCH BULLETIN MRL-0001A Note on Chain Reactions in Traceability inCryptoNote 2.012 September 2014Surae Noether*, Sarang Noether and Adam Mackenzie*Correspondence:

[email protected] Research Lab AbstractThis research bulletin describes a plausible attack on a ring-signature basedanonymity system. We use as motivation the cryptocurrency protocol CryptoNote2.0 ostensibly published by Nicolas van Saberhagen in 2012. It has beenpreviously demonstrated that the untraceability obscuring a one-time key pair canbe dependent upon the untraceability of all of the keys used in composing thatring signature. This allows for the possibility of chain reactions in traceabilitybetween ring signatures, causing a critical loss in untraceability across the wholenetwork if parameters are poorly chosen and if an attacker owns a su cientpercentage of the network. The signatures are still one-time, however, and anysuch attack will still not necessarily violate the anonymity of users. However, suchan attack could plausibly weaken the resistance CryptoNote demonstrates againstblockchain analysis. This research bulletin has not undergone peer review, andre ects only the results of internal investigation.1 IntroductionThe CryptoNote protocol has a problem: my anonymity depends on your anonymity.If I use 5;6, or 18 of your outputs when I compose my ring signature then you cansee the true signer. If you spend all 5;6, or 18 outputs with no foreign outputsused as mixins in your ring signatures, you reveal yourself as the spender, andnow any observer can also see the true signer of my transaction. This may notbe malicious if you spent your outputs non-anonymously for legitimate business orlegal reasons. Hence, any party with a large proportion of the UTXO set may gainknowledge of the traceability of others’ transactions and reveal that informationto the network at will. One may fancifully interpret this problem as an abstract,cryptocurrency implementation of Gresham’s Law: bad money drives out good. Ifthe unspent transaction output (UTXO) set is lled with a lot of transactions thataren’t really anonymous, there are fewer ways to make untraceable ring signatures.At this point it must be noted that, even in this scenario, the one-time key pairs(so-called \stealth addresses) used in CryptoNote protocols are not violated inthis scenario, and so the anonymity of users is still not directly violated. Rather,this attack violates the untraceability between one-time ring signatures, but thisdevelopment is still somewhat worrying. Hence, even non-malicious entities canc Monero Research Lab Page 2 of 8execute this attack on accident, malicious entities can spam the network to ownlots of the UTXO set, and malicious entities can break untraceability for others.An attacker’s intent may be perhaps in the interest of a pump-n-dump schemeby undermining the credibility of a currency, perhaps in the interest of spying onother users, or perhaps in a disinterest in paying the extra cost of adding moreforeign unspent transaction outputs to their ring signatures. In all cases, despitethe a priori hope that any particular user should always be interested in using alarge number of mixins for a ring signatures as a matter of principle, both in theinterest of personal security and the common good, we should have no expectationof this in practice. A version of the tragedy of the commons may take place andcause traceability throughout the network for everyone due to a subset of users.However, we should also keep in mind the forest, not the trees: since any usercan always compose a trivial ring signature with no additional outputs, immedi-ately exposing outputs down the line, there is a second-order problem here. A newtransaction has been exposed, creating exposure risk for any ring signatures thatused the newly exposed transaction as an obfuscating mixin. Is it possible that achain reaction could occur, even if a malicious entity stops actively attacking earlyin the history of the coin? This research bulletin was written to analyze this prob-lem, determine the plausibility of a conservative route of such an attack, and assessnetwork parameters to ensure graceful degradation of untraceability.2 Setup for a Passive AttackEveryone who has had a college probability class has come across the following,even if you don’t know how to solve it:An urn contains N marbles of two possible colors. We have NB black marblesand NW white marbles, where NB + NW = N is xed. We draw M marblesfrom the urn. What is the probability that all of the marbles we drew fromthe urn are black? What is the probability that all of the marbles are white?If 0 m M, what is the probability that we have m black marbles andM m white marbles?When phrased this way, we immediately jump to the hypergeometric distribution.The probability mass functionNBBN NBM BNMcan be used to compute the probability that all the marbles in my hand are black(set B = M), and we can use convenient formulae available in any number of freeonline textbooks, or wikipedia, or whatever, in order to compute the probability ofany particular occurrence. It’s one of the nicer distributions.We play the following game: if all the marbles I draw are black, I’ll toss a newblack marble into the urn while I replace my handful. Otherwise, I’ll toss a newwhite marble into the urn while I replace my handful. As it is with marbles, so itis with CryptoNote coins: It may help to envision each marble as an atomic unit(the CryptoNote analogue to a Satoshi) tracked in the UTXO set of a CryptoNotec Monero Research Lab Page 3 of 8network. The color denotes who is in control of the marble; black if controlled by amalicious entity, white if otherwise.Let’s say Lisa wishes to send some money to Milhouse (which would add a marbleto the bag). The UTXO set that Lisa draws from in order to make her ring signatureswill contain N transaction outputs, of which NB are controlled by Burns (the blackmarbles; assume the rest are white). Then the above formula is exactly what weneed. Lisa composed her ring signature with M N mixins[1] (she drew a handful ofmarbles to decide the color of marble to add to the urn), and if all are controlled byBurns? Well, then, if Burns spends his outputs with no mixins[2], Lisa’s transactionwill also be exposed. Furthermore, forget Lisa, any ring signature that used onlyBurns’ signatures can actually now be considered part of Burns’ controlled set, interms of untraceability, even if Burns does not control the private keys. Notice thatin this scenario, we are having a chain reaction occur: Burns reveals only his owntransaction outputs, but he, in turn, reveals Lisa’s output. The four assumptionswe have made are(i) Burns controls an initial proportion of an otherwise unknown UTXO set,(ii) all new transactions generate their ring signatures drawn from the currentUTXO set in a uniform, unordered way without replacement,(iii) all new transactions use exactly the mandatory minimum mixin level (handfulsize M), and(iv) Burns gains control of new transactions if and only if their ring signatures aresolely composed with Burns-controlled transactions (i.e. Burns stops puttingnew transactions in the system at time t = 0).We can change our assumptions to strengthen or weaken the attack in our scenario.For example, the attack is weaker if some transactions use more than the mandatoryminimum. The attack is stronger if Burns can also gain control of transactionsby generating them himself, i.e. he is not some passive actor in the background.However, this seems to be a reasonable, middle-ground scenario, if we interpret it inthe following way: Burns initially controls a portion of the UTXO set before a oodof ostensibly honest transactions are composed quite suddenly, so what happens?Protecting the network against a large-scale degradation in untraceability underthis scenario is simply a matter of smart engineering. If we can protect the networkagainst large-scale degradation under worse scenarios, all the better, but we shallstart here. This could be considered a \Christmas Day attack, both because oursimulations are set up to mimic a sudden in ux of economic activity before a trulymalicious attacker can respond (for ease of coding) and because the attack can beexecuted by an ostensibly innocent individual simply spending their money non-anonymously for perfectly legitimate reasons.Since the hypergeometric distribution is so nice, what can we expect out of thisgame? Well, let us analyze the results for a single new transaction. Assuming M isthe minimum number of mixins across the whole network, what is the probabilitythat all M mixin signatures are controlled by Burns? If this probability is large,then new transactions are very likely to be \controlled by Burns, even if he has yet[1]We de ne a mixin as a foreign output included in the transaction.[2]Which, it again must be emphasized, may be an ostensibly innocent act, not anattack!c Monero Research Lab Page 4 of 8to reveal the transaction outputs he controls. That is to say, the more CryptoNotetransactions controlled by a single malicious party, the weaker the untraceabilitytrait of new transactions becomes. Consider the following numerical example.Suppose we have N = 103 transaction outputs in our anonymity set (not countingthe real output belonging to Lisa), and that Burns controls pN of these transactionsfor some 0 p 1. Denote by Pr(p) the probability that any one ring signature(using three mixins) is signed solely with outputs belonging to Burns. This proba-bility describes, roughly, whether or not Lisa’s new marble will be black or white.Table 1 contains sample values of Pr(p) for this example.p pN Pr(p)10 3 1 010 2 10 7:22 10 710 1 100 9:73 10 40:5 500 0:125Table 1 If Burns controls pN transaction outputs from an anonymity set of N = 103 outputs,we display the probability Pr(p) that Lisa’s output is traceable from Burns’ point of view,assuming that Lisa uses three mixins in the construction of her ring signature. That is to say, atthe beginning of a large scale simulation, if Burns controls half of all transactions, we can expecthim to \see about 12:5% of new transactions.How do we interpret this table? If Burns controls only a single output in theanonymity set, there is no way three distinct outputs in a ring signature can all be-long to him. If Burns controls ten outputs, there is only a probability of 0:00000722that Lisa’s ring signature is really controlled by Burns. This is so small that on av-erage, it would take about 13:8 million signatures from this anonymity set to startseeing collisions. If Burns controls 100 outputs, there is a probability of 0:000973that a signature made by Lisa is controlled by Burns, so we should start seeing col-lisions after around 100;000 signatures. Finally, if Burns controls half of all outputs,then 12:5% of all new transactions will have a ring signature composed entirely ofhis outputs, so Burns will only be gaining 1 in every 8 new transactions, and soBurns’ share of the UTXO set will shrink over time unless he takes action.In Table 2, we produce the same values as for Table 1 but with only two mixins.In this case, if Burns controls half of the outputs, the consequence is that every onein four new outputs will really be controlled by Burns. If Burns controls 10% ofthe outputs, only 1 out of every 1000 new transactions will be controlled by Burns.Clearly, not as great as 3 mixins, but still not terrible; even if Burns controls halfof all transactions, there is only a 25% chance that a new ring signature will belongto Burns. Hence, his share of the UTXO set will shrink over time unless he takesaction.p pN Pr(p)10 3 1 010 2 10 9:01 10 510 1 100 9:91 10 30:5 500 0:25Table 2 If Burns controls pN transaction outputs from an anonymity set of N = 103 outputs,we display the probability Pr(p) that the new output is revealed during an attack, assuming thatLisa uses two mixins in the construction of her ring signature. That is to say, at the beginning of alarge scale simulation, if Burns controls half of all transactions, we can expect him to \grababout 25% of new transactions.c Monero Research Lab Page 5 of 83 Monte Carlo Methods and ResultsHold tight for some notation. We choose parameters NB0;NW0 and M, where NB0denotes the initial number of black marbles owned by Burns, NW0 denotes theinitial number of white marbles, and M is the minimum mixin level. We play thegame iteratively. We record the initial proportion of unspent transactions ownedby burns as P0 = NB0=(NB0 + NW0) before beginning. On the ith iteration, weare adding the Ni = (NB0 + NW0 + i)th marble to the bag. We draw a uniformrandom number u from (0;1) and compare it to the hypergeometric mass functionas described before. If u NBiM = NiM , then the next marble will be black, so weiterate NBi = NBi 1 + 1. Regardless of the choice of u, we iterate Ni+1 = Ni + 1and if we need to compute NW we can simply subtract. After some iterations, say Iiterations, usually enough iterations to double or quadruple the UTXO set, we stopthe game and consider the proportion of black marbles, PF = NBI=NI. However,since we are only concerned with how many of the new marbles were black (not howmany in total are black), we will watch as our metric of success for Burns’ attackthe value bPF = (NBI NB0)=I; number of black marbles Burns gained during thegame divided by number of marbles added to the bag.The above process constitutes one simulation. For each choice of parameters(NB0;NW0;M), we get a result bPF, which was determined as a result of a sequenceof random experiments, and is such a random variable. So we run 37 trials andtake the sample mean and sample variance from these experiments. We initiallylooked at the 95% con dence intervals, but they are so narrow that we may as wellignore them, in the end. We simulate a UTXO set growing from 5000 transactionsto 20000. Hence, we plot (20000PF 5000PI)=15000, that is, the proportion of os-tensibly honest transactions that Burns grabs. Figure 1 illustrates our simulationresults for NB +NW = 5000 and M = 1;2;3, and 4 mandatory minimum mixins inthe event that the UTXO set quadruples with honest transactions (that is, 15;000new transactions need new ring signatures). The horizontal axis displays the ini-tial proportion of the UTXO set controlled by Burns, varying from 0:0 to 1:0, thevertical axis displays the nal proportion of the new transactions in the UTXO setcontrolled by Burns, varying from 0:0 to 1:0. Note that any number above zero onthe y-axis represents a loss of security.It’s clear that bPF is monotonically increasing as a function of P0 = NB=(NB +NW), but that the situation improves for greater numbers of ring signatures. Noticethat there are some dynamical systems problems built into our data. If you graphPF vs. PI, (rather than our bPF vs. PI) then you can interpret this as a discrete-time dynamical system’s evoluti