pc Monero Research LabRESEARCH BULLETIN MRL-0001A Note on Chain Reactions in Traceability inCryptoNote 2.012 September 2014Surae Noether*, Sarang Noether and Adam Mackenzie*Correspondence labmonero.ccMonero 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 inationto 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 nbsp;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 pairsso-called \stealth addressesquot; 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 8cute 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 itAn urn contains N marbles of two possible colors. We have NB black marblesand NW white marbles, where NB NW N is nbsp;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 whiteIf 0 nbsp;m nbsp;M, what is the probability that we have m black marbles andM nbsp;m white marblesWhen 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 blackset B M, and we can use convenient ulae 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 unitthe 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 ula is exactly what weneed. Lisa composed her ring signature with M nbsp;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 arei 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 uni, unordered way without replacement,iii all new transactions use exactly the mandatory minimum mixin level handfulsize M, andiv 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 nbsp;oodof ostensibly honest transactions are composed quite suddenly, so what happensProtecting 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 Dayquot; 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 becuted 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 \controlledquot; 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 anattackc 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 nbsp;p nbsp;1. Denote by Prp the probability that any one ring signatureusing 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 Prp for this example.p pN Prp10 3 1 010 2 10 722 10 710 1 100 973 10 405 500 0125Table 1 If Burns controls pN transaction outputs from an anonymity set of N 103 outputs,we display the probability Prp 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 \seequot; about 125 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 000000722that Lisa’s ring signature is really controlled by Burns. This is so small that on av-erage, it would take about 138 million signatures from this anonymity set to startseeing collisions. If Burns controls 100 outputs, there is a probability of 0000973that 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 125 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 Prp10 3 1 010 2 10 901 10 510 1 100 991 10 305 500 025Table 2 If Burns controls pN transaction outputs from an anonymity set of N 103 outputs,we display the probability Prp 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 \grabquot;about 25 of new transactions.c Monero Research Lab Page 5 of 83 Monte Carlo s 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 NB0NB0 NW0 before beginning. On the ith iteration, weare adding the Ni NB0 NW0 ith marble to the bag. We draw a unirandom number u from 0;1 and compare it to the hypergeometric mass functionas described before. If u nbsp; NBiM nbsp; NiM , then the next marble will be black, so weiterate NBi NBi 1 1. Regardless of the choice of u, we iterate Ni1 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 NBINI. 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 nbsp;NB0I; 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 parametersNB0;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 nbsp;5000PI15000, 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 00 to 10, thevertical axis displays the nbsp;nal proportion of the new transactions in the UTXO setcontrolled by Burns, varying from 00 to 10. 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 NBNB 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/p