Decoy and Chain Reactions

Psaná verze třetí epizody Breaking Monero.

Justin: [00:00:00] Hello and welcome to the third episode of Breaking Monero is a series of episodes where we explain the limitations of Monero security and privacy in a comprehensive and understandable way. Today we are talking about zero decoy transactions or 0 mixin transactions and the chain reaction effect that sort of comes as a result of the so sort of a double episode today. But we’re going to try and keep it shorter than the other two in order to get a little bit more streamlined and specific here. So as always I’m Justin and we also have Sarang on here going to say hi real quick Sarang.

Sarang: [00:00:38] Hello, my name is Sarang Noether and I’m one of the researchers who does work on behalf of Monero research lab and the Monero community

Justin: [00:00:46] Excellent, so I actually want to start off with a nice quick screen share from one of the presentations I gave at Defcon where I talked about these ring signature specific specifically. Let me just pull that up. OK.

Justin: [00:00:58] So you can see here on the left of the screen there is a ring signature.

Justin: [00:01:03] Everything in this green oval here. That’s like all of the potential outputs that can be sent in a Monero transaction. Let’s say that there’s gold one there’s gold one here that I have my cursor on is one that is the true one spent and therefore has the key image that comes from it. And all these black pots of gold that are just Monero outputs are potential spends. For zero decoy transactions these are transactions that are sent without any other output being a possible spend. So if you see this transaction you know that is the actual output that is spent. So you can see an example here. Suppose this is another 0 decoy transaction to ring size of one. You know since only one output is possibly included in this ring that that is truly the output that is spent there. So as a result you can say “Ok since this is spent here I can look at all other transactions that include this output” and say “hey this output cannot be there” as the example here the ring size includes this output. So you can put a nice X through this output to say “hey obviously that output cannot truly have been spent” and then if we continue this along for our several other transactions where they each have their own set of zero decoys. Again these are old Monero transactions that could be sent in Monero early history in 2014 and 2015. And you can see that if every single other output is referenced in a different zero decoy transaction then you can realize that one of the outputs is actually spent If there is only one plausible spend left and therefore that ring signature is compromised. This is really the basics of this whole zero decoy attack or a zero decoy form of analysis. You look at transactions where there is only one possible actual output spend and you compare it to other transactions to learn information to sort of whittle down and narrow down information. And then from there since this output is known to be spent in this one transaction that will be yellow the other one there than any other transactions that could include that output for example that this output created as tx10. Then we can also eliminate it here as shown in the second ring signature and that’s on the right here where you sort of have this propagating effect. This propagating effect is called the “chain reaction”. So on a really high level this diagram I think really helps summarize the idea of zero decoy attacks and analysis on Monero and the sort of resounding chain of reaction that results from these zero decoy transactions. Does that look good to you Sarang?

Sarang: [00:03:52] Yes absolutely. I mean the way that I kind of visualizes iterative process in my head is almost kind of like peeling away an onion.

Sarang: [00:03:58] It’s not an exact analogy because these are things aren’t onions. But generally the idea is that like you said you look at zero decoy transactions you look for their appearance elsewhere and you can just start peeling those off of other rings and eventually you might get some rings that then become zero decoy transactions and you can take those and iteratively work those larger rings. So you’re right basically the whole idea is to iteratively find zero decoy transactions using the property at zero decoy transactions have outputs that are known to be spent. And of course in Monero the whole goal is that we don’t want to know if an output is being spent or not because that makes it an invalid decoy for a future larger ring.

Justin: [00:04:38] So Monero moved to make 0 decoy transactions disallowed beginning I believe in March 2016 is that correct?

Sarang: [00:04:49] Possibly. I feel like I should have looked that up.

Justin: [00:04:52] So but between that period time when Monero raised the minimum ring size and until the onset of ring ct in early 2017 you still saw the 0 decoy analysis still have some..although decreasing…it still had some measurable impact.

Justin: [00:05:12] You can still learn a lot about transactions. Why was that really the case that you could still perform this analysis despite no one being able to send these transactions anymore.

Sarang: [00:05:21] Sure. So again the whole idea of this is that it is iterative. Right. So when you’re able to take early transactions and you kind of whittle away what be known decoys are to get to the truth spends. You can kind of push those forward into smaller rings and then a little bit into larger. So as ring size get bigger. Effectively the number of outputs that you’re able to, kind of, whittle away from those larger rings ends up being less effective. So again part of the reason we have larger ring size in ring size increases over time is so such analysis is less effective. Kind of a belt and suspenders approach. You’re kind of adding in some more decoys to ensure that the propagating effect has less of an effect. So they still were effective to a degree, but the degree to which they were effective definitely went down over time. Part of reason that that is because the way that you choose your decoys and we haven’t really talked about exactly how we do that — we just kind of use the word random..kind of don’t talk about it..has changed over time and I know that we’re gonna be having a future episode about how exactly we choose outputs from the chain and why that does matter when it comes to decoys. But suffice it to say that the way that we started choosing our outputs has gotten better over time and that has also made this particular analysis less effective than it was before.

Justin: [00:06:35] Excellent. Thanks. So can you speak a little bit about the history where Monero is learning about these sort of zero decoys. I know that there is the research papers MRL1 MRL4 that talked about the idea especially in regards to chain reactions that there was there specifically addressed in those research papers.

Sarang: [00:06:53] Yeah exactly.

Justin: [00:06:55] OK. Then you said that there was a new research paper or relatively new recent paper at least that helps quantify these a little bit better?

Sarang: [00:07:01] Yeah. Yeah. So the idea of this was known for quite some time. There were some internal discussion that eventually culminated in a couple of internal papers MRL1 and 4 the talk about this to varying degrees some of which was in the form of kind of an accidental passive analysis and some of which was from kind of an active analysis..perspective..Where You might have someone who’s purposely injecting outputs into the chain that they then have some knowledge over so you can look at it a few ways. But the extent to which has actually happened on the later chain wasn’t really quantified until a couple of papers came out and one of which was two different names could its name is an early preprint was a bit different but the later preprints from April 2017 was called “An Empirical Analysis traceability in the Monero blockchain” and then there was another later paper which has a confusingly similar name of “traceability analysis of Monero blockchain” that did a really good job of talking about a few different forms of analysis and did a good job starting to kind of quantify those forms of analysis and what they showed and kind of the number that got floated around for a while. Was this something that something like 65% of monero outputs were known to be traceable by some combination of zero mixin chain reaction..maybe a couple of other forms of analysis..which I say sounds very very scary like “my goodness if 65% of the outputs are known to be spent and should not be chosen as decoys for modern transactions surely I and everyone else are totally screwed” but again the way that we choose our outputs is very very unlikely and is less likely over time to choose any of these and then later on a lot of other papers seem to kind of rediscover this analysis. So you know we saw kind of a swath of prints over time that maybe introduced one or two other newer small forms of analysis but also for some reason tended to bring up this this idea of chain reaction over and over again as part of that analysis which I think led to kind of some misunderstanding about what was already known about chain reaction unfortunately. So we actually did kind of a fairly independent look to see if we can reproduce those values in MRO 0007 where we introduced another more general form of analysis and we found approximately the same numbers that if you just kind of look at the chain as a whole from whatever point they looked at it kind of back toward the beginning of Monero history you still saw around you know 65% about outputs being known to be spent based on this analysis. But if you look at modern transactions in particular kind of after the big ringct switch They’re vanishing. I mean at the time that we did it we found that precisely zero outputs were vulnerable to this kind of analysis. And again if you were to choose old outputs that were known to be compromised that would be bad but modern transactions do not do this.

Justin: [00:09:44] Exactly. I think that’s important to sort of cover in the last episode we talked about the idea of plausible deniability. Zero decoy transactions were a really important sort of area to look at because it broke down the plausible deniability of people’s transactions on Monero because you could explicitly look just at the information on Monero blockchain and determine that since this sort of transaction occurred this output could not possibly have been spent anywhere else. So it was a really important consideration to look at. And it was really great to see where I know we have several responses out there. We have several research papers at this point that looks into this but it’s important to distinguish Monero pre ringct and Monero with ringct because it’s night and day difference..

Sarang: [00:10:28] And it is definitely worth noting that you know that modern transactions that only use ringCT outputs and for the most part that’s you know with vanishingly small exception that is the transaction. Those are the transactions that happen early pre ringct outputs presumably those are the ones we had denomination’s kind of..and stuff. Those aren’t chosen are used. So a lot of the papers did not make it a clear enough distinction and I think that that kind of muddied the waters for a while on this whole 65% number.

Justin: [00:10:59] So is there anything else you want to mention on zero decoys or do you want to focus now a little bit more on the idea of chain reactions which are continued to be something we sort of test other attack vectors with and Monero with these sort of chain reaction methods because we don’t really look at zero decoys or zero-mixin really anymore because now sort of moved on from us.

Sarang: [00:11:24] No that’s true. And I mean to be fair you know the idea of zero-mixin is what underlies the idea of a chain reaction because you got kind of this “onion methodology” for trying to piece transactions apart but as we’re gonna talk about in later episodes we have other methods of analysis to try to determine whether or not outputs are spent. And you can apply the idea of a chain reaction after you run those other analysis. So if I’m able to determine by some other means whether or not another set of outputs that are spent through my new clever analysis (whatever it might be). And there’s been no improvements to this over time. You know you can also take those outputs which you now know are spent. Those are effectively a zero-mixin transaction and you can then apply a chain reaction off of those. So in general, while we do find that being able to identify some modern outputs are spent does let you kind of remove them from consideration from other modern transactions. Again the entire point of a chain reaction is that you have to be able to do that enough so that you get another large ring all the way down to one remaining output. And in general we’re not able to do that which is good. Maybe in some transaction you can remove one two maybe even a higher number than that for consideration.. But provided you don’t get down to one. You still have that plausible deniability.

Justin: [00:12:36] Excellent yeah. I think it’s I think it’s really important to cover the idea of 0-decoy and 0-mixin because if you if you can sort of reuse the same sort of thinking that you do for these zero decoys 0-mixing which are pretty basic and really easy to understand. For far more complicated attacks that sort of try and recreate to 0 decoy and 0 mixin situation. So I think that it’s important to show people I have. A spreadsheet that I’m going to show with you I’ll share with you all regarding how we evaluate this chain reaction and see under what network circumstances with a variety of compromised outputs that other transactions are also compromised.

Justin: [00:13:18] So I’m just going to start sharing that here.

Justin: [00:13:23] So I use this pretty frequently. I created this in early 2018 to help better understand to make a spreadsheet that’s easier for people to understand. This is really just though an extension of MRL1 and 4. There aren’t any real new ideas introduced here. It’s really easy to play around with. So I have just for like a really easy sake here I have the ring size set to three right here. So it’s it’s a really low ring size but this is Moneros first mandatory minimum ring size here is with three..and You can see here that four on the left here you have a different proportion of outputs that are compromise. So these vary between zero and I mean technically not 100 percent but essentially 100 percent there and you can see the proportion of the time that the true input is revealed based off of you’ve been able to break down these ring signature.

Justin: [00:14:18] So you can sort of look and see directly at the chain reaction effect here. So you sort of say “OK half of the outputs are compromised” let’s say half the outputs are zero decoy. You can go through and say “OK well then for twenty five percent of the transactions out of the box by just doing this one level of analysis you can say “OK well these are now compromised” and then you can say “OK well now we found these twenty five percent new compromised outputs” let’s run the test again including these twenty five percent is compromised and you can do this across several layers here until you ultimately take the sum of all these amounts.

Justin: [00:14:53] In this last column here this is the total proportion of all the outputs that are compromised that are compromised after this sort of chain reaction impact. So if you have a circumstance where 50 percent of the outputs are revealed to be true under a certain circumstance you can keep running tests and sort of break down the integrity of another twenty nine percent of the output so the total amount would be about 80 percent of the total outputs would be known to an outside attacker. So I these numbers don’t really mean anything but a larger number means a larger chain reaction. In this sense I sort of just add them together so you can see if I put in a smaller ring size. Let’s put Monero current ring size in here of eleven. That these chain reactions get very very small. Right. You’re down to a much smaller number than you were before. It’s a relative term. This is .01 before it was one point to 4. And again that number doesn’t really mean anything it’s just sort of a number you can compare it to other ring sizes. So. But ultimately you can see for any specific amount the first order effect is is vanishingly small. Even for enormous amounts of compromised outputs for a large ring sizes. And if we went to incredible ring size like one hundred, or whatever, you can see like the chain reaction would have to be quite immense for it to really have any substantial impact on other..transactions. So I’m just going to quickly just show the sort of difference between Monero with ring size 3 and Monero with ring size 11 what it has now on the chart here on the right and you can see on the bottom right here this is the proportion of sort of known compromised outputs to begin with. And on the y axis here you can see the proportion of transactions that were compromised or the proportion of rings that are compromised. And so you can see here with ring size 3 there’s far less protection than ring size 11. And as the ring size gets larger and larger these curves shift further and further to the right and get increasingly steep curves because it takes more in order to perform a chain reaction effect. So this is what Sarang and I mean when we say that transactions need to with large ring sizes it really starts to take a lot in order to have chain reactions on the Monero network. So I find this resource to be really easy to help quantify what we mean with chain reactions. Again this doesn’t have to be for zero decoys that are affected but it could be any sort of proportion of outputs that are affected and we can run tests regarding the information that we plug into this Excel spreadsheet that I generally find very valuable.

Sarang: [00:17:50] Yeah and it’s also worth noting too that you know again while modern transactions are vastly unaffected by any of this particular kind of analysis. We do in fact have a tool that is available as part of the Monero of general built in tool just tool set. We used to call the “blackball tool”. We realized it was kind of a confusing name. I consider it just a spent output tool. What it lets you do is it lets you take your copy of the blockchain it lets you run all sorts of analysis including this one zero decoy and chain reaction and internally kind of flag those outputs that again are known to be spent and should not be chosen as decoys. It will make absolutely certain that you do not choose those as decoys. Again the likelihood in a modern transaction of choosing an output that has been affected by this analysis is vanishingly small..vanishingly vanishingly small. And we haven’t come up with any modern outputs that haven’t happened yet but for transactions that are spent you know older like I like a lot of older pre ringct outputs it will still help you avoid those. The tool is kind of inefficient to run because it does a lot of analysis. But if you take a belt and suspenders and glue the pants on yourself approach. A tool is available to help you do that.

Justin: [00:19:03] It’s just my opinion that with large ring sizes this tool really helps us only evaluate whether or not the network is under a sort of severe attack where if you have a chain split you can be like “OK let me go evaluate” at this point we’ll talk about change splits later. It’s not necessarily a tool that people need to run for the sake of sending funds for a low risk transaction or even..

Sarang: [00:19:27] No absolutely not for a 0 decoy transactions and for a chain reaction based transactions. Again modern transactions are unaffected.

Justin: [00:19:38] Excellent. So I think we really covered most of the basics on zero decoy and chain reaction. Hopefully this is a nice summary for people.

Justin: [00:19:45] Is there anything else you want to add to this conversation Sarang?

Sarang: [00:19:49] Just That you know there was a lot of really good research that originally went into this both internally and by external researchers and I mean there’s still continues to be research topic even though we understand it pretty well by researchers, who may not have read the previous papers or we’re adding things on to them.

Sarang: [00:20:05] So there are plenty of different papers and preprints available if you have kind of a more scientific or mathematical bend and want to learn more about kind of the analysis that led to our protections against these kind of analysis.

Justin: [00:20:18] Excellent. So again thank you. Thank you Sarang for joining me. Thank you to the listeners for watching this latest episode of Breaking Monero. I’m glad this one is shorter so hopefully it was nice and just all the information you need and not much else so we’ll keep trying to make other episodes short for you all. With that we would like to say goodbye make sure you watch for later episodes and take care.

Napsat komentář

Vaše emailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *