|Breaking Monero Episode 02: Ring Signatures Introduction
We discuss the history of Monero's ring signatures and past approaches to improve them.
All Breaking Monero Episodes
Justin: Welcome to the second episode of Breaking Monero. Breaking Monero is a series of episodes where we explain the limitations of Monero’s security and privacy in a comprehensive and understandable way. Today we are covering and introduction to ring signatures and their history. It’s important to understand ring signatures before talking about anything else in these episodes, because they all really build off of ring signatures. But before we get there, we have Sarang on here, can you introduce yourself briefly, I know they saw you in the previous episode, but can you also cover some basic terms for people, the idea of plausible deniability and the idea of heuristics.
Sarang: Sure, like you said, I go by Sarang Noether and I’m one of the PhD researchers who works on Monero research and development on behalf of the Monero Research Lab. My counterpart is Surae Noether, who’s not able to be here today, but was on the previous episode to talk about an introduction to the series and why we’re doing what we’re doing. So, ring signatures are a topic that comes up a lot, and as we’re going to talk about later, I’d say that they are the pain point and the sticking point for issues that people have with Monero and one of the things that we’ve had to iteratively deal with over time in order to strengthen Monero for people. In this episode we’re going to go over just a very brief overview of the structure, of how they work. We won’t go into the mathematics, there are definitely good resources if you’re interested in that. But we’re going to talk a bit about their structure and lead into why that structure can lead to some problems. To start out with, the sky is not falling, ring signatures are not broken. We’ll talk about that they do exactly what they say on the box, but they end up leading to, what I would say, are annoyances and things that we iteratively try to improve on. You had mentioned the phrase plausible deniability, and that’s a phrase we sometimes use when we talk about Monero’s sender ambiguity and I wish it was a phrase that was used more often. As we’ve talked about before, people like to throw around words like ‘private’ or ‘fungible’ when they don’t really have any formal meaning. We have intuitive things, where we assume private or fungible mean in terms of digital assets, but it’s kind of tough to nail them down exactly. I like to branch out Monero’s privacy and anonymity guarantees into three parts. Sender ambiguity, or privacy if you want to call it that, recipient ambiguity or privacy and amount and/or metadata privacy. In general, receiver anonymity and amount anonymity, or amount metadata, are in general, very, very good. What happens is when you choose to send funds to someone with Monero and they’re not directly linked to your wallet address, I have one or more Monero wallets for which there are addresses. I can receive funds addressed to those, and I can use funds addressed to those to later send to other people. So, Justin has a wallet address, he gives it to me and then I send funds using my Monero client. But what happens is, the wallet address itself, if I’m sending funds to Justin, never actually appears on the blockchain. That’s huge. Instead, what happens is that I effectively create a one-time output, sometimes called a note address, and that one time address is what appears on the block chain. So wallet addresses never appear over there, and that’s an important face to keep in mind. There’s a difference between those and it’s kind of a subtle difference that’s easy to miss from time-to-time, but the idea is that when you’re sending funds to someone, the recipient, their wallet address is never known. I basically bake that recipient address into the one-time address in a way that is not reversible. So if someone is looking at an output that I generate, that’s destined to Justin, no one can tell that it’s destined to Justin. Justin’s knowledge of the private key that corresponds to his wallet address allows him to later spend those funds, but he cannot directly determine anything about that address. Similarly, as I think we may have mentioned in the last episode, things like the amount of the transaction, those used to be known in Monero for various reasons, but now those are basically tied up in what’s known as a cryptographic commitment and that’s what led to the whole idea of Range Proofs and Bulletproofs and that was a big point of discussion before. But that’s also a very, very good. The amount of your transaction is private, the recipient of your transaction is private, but we often like to talk about sender ambiguity, and that’s where ring signatures come into play. Effectively, if I’m sending funds to Justin, I would have to take some funds that I had previously received from a so called one-time output that was destined to me and I don’t want to just necessarily send those to him. In another alternate version of Monero perhaps, maybe you could do that, where I take that one-time output address and I basically sign it over to Justin in some sense. Effectively what I’m really doing is generating a new output one-time address and I’m signing for it using the one I had received. When done properly, this can ensure to everyone that the money existed before, that I controlled it and that nothing funny happened. But ideally in Monero, we want to obfuscate that even more using plausible deniability. So what I do is, basically take that one-time output address that was addressed to me, that I would like to send to Justin, but I’m also going to take a bunch of random, and random can mean many things, but I take other one-time addresses that I don’t control. Unlike things like CoinJoin or other mixers, I don’t need to collaborate or cooperate with anyone to do this, they have no knowledge of what I’m doing and that’s an important part of this. I basically take other random one-time addresses and I use those to form a structure called a ring, and what I do is, a ring signature is a way to say that I know the private key that corresponds to one of these output’s public keys in my grid. What this really means is that I use the private wallet address that I hold, because those funds were originally addressed to my wallet address, I use that private key to generate the private key for one of these outputs. Again, that’s the separation between wallet addresses and output address which can be confusing from time-to-time. A ring signature just says that I control one of those and certain things involving the amounts and that it balanced properly. So what happens is, whether or not Justin is the one making this verification of the ring signature or anyone who’s synchronizing the blockchain and ensuring that it was all done correctly, they need to know that all these signature are valid and that I actually control the funds and I’m actually sending them over to Justin. In that case, they basically perform a verification of the ring signature and all that verification tells that person is just a couple of things. First it tells them that one of those output one-time addresses was the one that I controlled, importantly though, without revealing which one it is. It says in this case that one of them was the ‘true sender.’ The true sender in that case does not mean the wallet address, it means an output one-time address that was generated on the fly when the funds were originally sent to me. And it also shows that those funds weren’t double spent. The cleverness of our ring signatures is that they have a property called linkability, that means if I were to try to grab another ring and try to respend those funds, because remember, that particular one-time address, that output public key, it might appear in a bunch of other rings, ideally it will appear in a bunch of other rings when people randomly grab it to put alongside their own. But I also need to make sure that that one wasn’t spent twice. The linkability property which involves things like key images, let’s just make sure that not only did I control one of those outputs, the one that I controlled was also not spent in another ring. It’s a lot of info packed into one structure called a ring signature. As we’re going to talk about, there are some limitations to that, but mathematically it does exactly what it says it’s going to do. Effectively, I have plausible deniability, I could say to someone who says “Well, one of those public keys belonged to you.” You could say, “You don’t know which one it was, and that output key probably appears in a lot of other rings and I had nothing to do with those transactions.” So it gives you some deniability about what was actually spent, this is, what public key I’m actually signing over to you. You had also hinted at the idea of what are called heuristics. Heuristics are a subtle thing to talk about, but it’s an important one. A good example of a heuristic, let’s say for example that I asked you to come up with a number between 1 and 10. Let’s suppose I asked you to write that number down and seal it in an envelope so I can’t see it. Now, I being a smart person know a little about statistics and such, I happen to know that in general, people will typically not choose the number 1 or the number 10. It’s actually true, people don’t like the idea of extreme values. So I think to myself that you probably didn’t write down 1 and you probably didn’t write down 10. In particular I know that it’s 3 and 7 that are the most typically picked if someone asks you to pick a number between 1 and 10. So I might think to myself “Aha, I bet you picked 7.” Statistically, if we did this game over and over and you behaved like a rational human being does, more often than not, you probably will pick the number 7 in there. But here’s the thing, unless you actually show me what that answer is, I have no idea if that’s true or not. So what we do in the ring signature heuristic case, is that you would do this, you’d write down your secret number, put it in the envelope, I would say to you, I think you picked the number 7 and instead of telling me, you just eat the envelope and walk away. That’s a heuristic. Can I do anything with that information about you picking 7? I don’t know, maybe. Maybe that has some significance in our real lives somehow, but it’s not checkable, it’s not provable. It’s just me using information about how I think you’re going to operate in order to gain some information that I might be able to use. So we talk a lot about different heuristic approaches to ring signature analysis, but those things are not the same as any kind of proof. There are a whole lot of different pieces of metadata and patterns of usage that we’ve iterated on to deal with heuristics, but it’s important to remember, when we say heuristics, we do not mean any kind of proof. Can you do something with a heuristic? Absolutely, but it’s not provable. Ring signatures when used correctly in the ways we’ll talk about do provide plausible deniability even though an adversary could try to come up with heuristics, in particular, who they might think the sender of a particular ring signature is. It’s important to remember, mathematically, ring signatures do exactly what they say on the box. They provide plausible deniability absent external information. But as we’ll talk about, different kinds of external information can allow an adversary in Monero’s early history to find our actual provable information, and in Monero’s later history determine heuristic information that’s not necessarily provable.
Justin: I really liked that heuristic example because it helps keep things in perspective. There are some things that probably break down your plausible deniability. Things like 0-decoy which we’ll talk about in future episodes, where you can look at Monero’s on-chain data and say “Based on this information, I know for sure that something occurred.” With the heuristic case, you’re using other information but normally you need other information on the side in order to corroborate this information as ground truth. To say that this is my guess, but I still can’t check your envelope, I still can’t figure out what the ground truth is. Maybe your ground truth is talking to my friend who says I always write down the number 7 and you would get closer with an additional piece of evidence to keep refining that heuristic further and further. I think it’s important for people to understand the difference between the way that we talk about Monero’s privacy in relation to plausible deniability where we say, at the minimum we’re making sure that on the Monero blockchain you have plausible deniability, within the ecosystem, you’re protected. But when you start throwing in a bunch of outside, real information, it gets really complicated. I think it’s hard for people to understand that, and that’s why we’re talking about it during this series.
Sarang: It’s something that you don’t typically have to think about in real life, so it’s something that’s artificially constructed when we deal with system like this, but they are important to the security of those systems. A lot of this will have to do with your risk profile or your so-called threat model. Monero’s ring sizes today, for example, are 11. So if I send funds to you, I take my real one-time address and I take 10 fakes, just off the chain, and I form a ring that’s size 11. So mathematically, absent any external information, if you were to guess which one of those one-time outputs was actually the one being spent in my transaction to you, statistically you have a 1 in 11 chance. What does that mean in terms of real, actual plausible deniability? If your dragged before some court or magistrate and they say that they through some external information, figured out that one of these outputs in this ring belong to you, were you involved in some shady business? You can say mathematically it’s a 1 in 11 chance. Is that good enough for your use case? That depends, it depends on the legal system and all sorts of other things that are outside of the mathematics of Monero. Maybe that is a big deal, maybe it’s not. Before the episode we talked about the example of Voldemort. Voldemort is a super bad guy in the Harry Potter universe, I’m told, I’m not a Harry Potter fan, but I’m told that this is true. So perhaps Voldemort sees that one of your one-time outputs appear in a ring, and sees that it is a 1 in 11 chance that it’s yours. Or maybe the rings are bigger someday and Voldemort sees that it’s a 1 in 100 chance. Maybe in that threat model, Voldemort doesn’t really care about the law and just casts a horrible death spell on you anyway. In that threat model, the fact that you were using Monero at all meant that you’re kind of hosed. So it all depends on your threat model, and that’s not a very comfortable things to tell somebody. When you say, how much plausible deniability is enough? That is entirely dependant on your situation. As we’ll talk about later too, we believe in the Monero community, that the use of ring signatures, when done correctly, is the best current way to safely use digital assets. Whether or not that applies to you, really depends on your personal threat model. We believe that for most threat models, it’s sufficient. But it’s always important to keep in mind the Voldemorts of the world. If the fact that you used Monero at all ends up implicating you, then that’s a problem for you.
Justin: Absolutely, thanks Sarang for that introduction. I’m going to resummarize about ring signatures. They allow users to send transactions, or outputs, or notes as they’re sometimes referred to as, like, individual dollar bills. It comes from more than one plausible location, and without ring signatures, like you have with Bitcoin, it’s really clear what source of funds is actually sent, but with Monero we make that ambiguous by saying it could have come from one of several places.
Sarang: In Bitcoin, they do in fact have a similar type of signature. The mathematics is different, but you do effectively the same thing where you sign a note over to somebody else. Where as with Monero, you are signing on behalf of one of a possible group of notes to someone.
Justin: Would you say that ring signatures are used a technology to hide where Monero is coming from, is that a good way to get the point across, or is that an oversimplification?
Sarang: I think it is, because when people say where it came from they often assume that it has to do with wallet addresses. Remember, that is not the case. To be absolutely clear, your wallet address, that you can lookup with whatever Monero app you use, never appears on the blockchain, ever, ever, ever. It is not mathematically possible for an observe to look at a transaction on the blockchain and determine what address they came from or were destined to. They is no way to do that. Instead, you generate one-time addresses and those are the things that actually appear in rings and are signed for.
Justin: It’s almost like when we say it hides where the funds are coming from, it’s sort of...
Sarang: It’s another level of obfuscation that we don’t often talk enough about. And we’ll talk about later, if you interact with other entities like exchanges that have additional information then they might be able to gain additional information, but it’s not possible to make that linkage back again.
Justin: So I think we’ll take the time now to talk about the history of ring signatures in Monero just so we can see how things were and how we’ve addressed changes in the past to make them better with the past two major concerns with Monero. So ring signatures were made in their current form in 2004 and the original perceived use case for these were voting. Where you would have several people vote, but you want to make sure that one person doesn’t vote twice. They actually called these ‘linkable ring signatures’ not because you could trace who was voting, but you have the key image component, like we have in Monero, to prove that someone isn’t just selecting sources of possible votes and casting them multiple times.
Sarang: Yeah, when we talk about linkability and this cryptographic construction, we’re really saying is it possible to link two signatures as having come from the same source, even if you don’t know what that source is. The idea of actually identifying what the signer was is a property called ‘traceability’ and there are many different constructions on how to do a ring signature. You can generate some that are traceable, you can generate some like we do that are linkable. It’s a general type of cryptographic construction of which there are many examples. We use one that’s very suited for what we want to do. But as you’ve said, there are many different kinds of applications that have been discussed and I’m sure we could come up with many more if we sat down and thought about it longer.
Justin: The interesting thing is the CryptoNote protocol which was published in 2014, although they allege it was published in 2012. It took the idea and said, instead of voting, let’s use this to send transactions, where we can make it appear that they’re coming from different stealth addresses, these outputs, instead of just coming from one specific area. And this was a pretty novel application because it allowed you to do a sort of mixing process, but it did not require interactivity.
Sarang: And that’s actually very, very important because part of the deniability is that the outputs, if I’m sending you an output for example, that is very likely to appear under normal transaction volumes and in many other people’s rings. So ideally, the deniability comes from the fact that you can look at a bunch of different transactions, all of which reference the output that I happen to secretly know about, and I can deny all of them in theory, because even though one of them may be the actual spend, it might not be. It’s very, very important that we have that property.
Justin: Yeah, and it really helps with user experience too that you can do things offline or you don’t need to talk to someone or get someone else to work with you to sign a transaction. I think that’s one of the best, the reason why people were originally interested in ring signatures and the CryptoNote protocol because you have this non-interactive mixing.
Sarang: Right, it is a non-interactive process, you don’t need the cooperation of anyone else of who’s outputs you’re referencing in your own ring.
Justin: Sarang, could you take the time to walk through the early years of Monero’s history, from when it started through about 2017 when Monero added RingCT? Can you talk about how well people understood ring signatures, were they well understood? Where people speaking inaccurately about them? And can you walk us through some of the initial research you were doing to document some of these early limitations?
Sarang: Absolutely, so if you go look at the CryptoNote Whitepaper, you’ll see a linkable ring signature scheme that is not the linkable ring signature scheme that we use today. The scheme that we use is more efficient and has some other nice properties, it’s based on a scheme that Joseph Liu came up with. Academic work, especially in mathematics builds off other work, so questions of who invented this... The form that we use is a slightly modified version of a paper by Joseph Liu. The original one was more closely related to a different scheme which was less efficient and less useful to us. We can debate about the history of it as much as we want to, but Monero did not invent this. They CryptoNote authors did not invent this. There’s a novel implementation of some mathematical and cryptographic work that had been done prior to that. We basically use a scheme like that and have modified it since, in particular because we needed to implement the RingCT scheme, but the basic structure of the ring signature is essentially the same, but the modifications helped us work with these encrypted amounts that aren’t very important to what we’re talking about today. Originally, when this was used, ring signatures were basically optional. In theory, you can have a ring of one possible signer, that is one possible note that I’ve plucked off of the chain that I’m sending. In that case, there is no plausible deniability. If you know that one member of the ring had to sign, and there is one member of the ring, it does not take a very smart bear to figure out who the signer was. Again, it was optional, we called it optional transparency, optional transparency is good right? To some extent, at Monero, we believed that you can always give information to someone about a transaction, that’s always possible. In some sense optional transparency isn’t such a good thing, it made optional transparency very, very optional. So there was no minimum ring size, except 1 of course, and we sometimes call these 0 mixin transactions. The other term we sometimes use for the fake outputs that I’m pulling in are ‘mixins’ because they are fakes that I am mixing in with my real one. I don’t really like that term, but whatever. Mixin-0 is ring size 1, mixin-1 is ring size 2 and so on. With those, you had essentially no sender ambiguity. Remember, that still doesn’t reveal the wallet address of the sender or recipient because you don’t have the information from the chain, but it did mean that there wasn’t any ambiguity of which of those notes or outputs was being spent. It was quickly realized, that this is not necessarily a good thing. We’ll talk briefly about this and go into more of thing about attacks on this later on. Would you like us to talk about the 0-mixin problems as they apply to other larger rings?
Justin: We’ll have an entire episode about 0-mixins so keep it high level.
Sarang: Sure, so even though having a 0-mixin or ring size 1 transaction removes sender ambiguity, you still have that extra layer of obfuscation caused by one-time addresses, so does it immediately identify you as the wallet address? No, it does not. We’ll talk later about how we at Monero Research Lab and other members of the Monero community realized how there were other consequences to this. Remember, a ring signature doesn’t really exist in isolation on the chain, it uses outputs that are likely to appear in other signatures. In some sense, the actions that I take can in some ways affect the actions of other ring signature users, and this is a constant theme throughout everything else we’re going to talk about. There are other reasons why 0-mixin transactions are bad, but at any rate we realized that 0-mixin transaction were bad and after that decided to implement minimum requirements. By minimum requirements, I mean consensus enforced minimums, not just that by default the wallet will show that I should use a ring signature of two or three or five or whatever, but if I sent a transaction that does not have at least that many entries in the ring, it will be rejected by the network. So, that’s called consensus enforcement, it will not be accepted by the network whatsoever, it is no longer optional. So that was instituted and over the years we have iterated on larger and larger ring sizes to mitigate certain kinds of analysis that we’re going to talk about. Eliminating the so-called 0-mixin or ring size 1 case was the first step. There are reasons that we’ll talk about later regarding why we continue to increase it over time. I think you have a graphic, do you not?
Justin: Yeah, I can pull that up real quick. So you can see here the history of Monero’s ring size. You can see initially from 2014 through March of 2016 you could send those zero decoy transactions where you made it incredibly obvious that there’s no other way any other output could have been used in sending that transaction. There is only one that could be used. So there was limited privacy for those transactions, they were still protected by stealth addresses, but ultimately it was obvious where they were coming from, but more importantly, these transactions also impacted the other transactions and we’ll talk about the idea of chain reactions later. In March 2016, Monero moved to a minimum ring size of 3 and this was around for about a year and a half until September 2017 when it was raised to 5. In 2018, we learned about another attack that we’ll speak about, so we raised it to 7 and then later in 2018 we decided to preemptively bump it to 11 to split some of the benefits of Bulletproofs to get better privacy and also better efficiency. This chart does a pretty good job of summarizing what has happened up until this point. We started with 1, then raised to 3, 5 and 7 and it’s important to note that when we updated it to 11 in 2018 it is now a mandatory ring size. You previously could send other ring sizes, but now you can only send it with this exact ring size.
Sarang: As you had mentioned, prior to the most recent upgrade to a mandatory fixed ring size of 11, we only enforced minimum ring sizes. Absent other information, for most kinds of analysis, larger ring sizes are better. You have in theory more plausible deniability and as we’ll talk about later, it can thwart other kinds of analysis. Prior to very recently, you could make a ring as large as you want and we’d occasionally just see absurd numbers. I mean what was the largest ring size we saw? I want to say it was over a thousand or something.
Justin: It was over a thousand.
Sarang: It was just absurd, and you could do this. It’s going to cost more in fees, because the size of your transaction does go up as you increase ring sizes. You might say, why didn’t we just make rings gigantic all of a sudden, well, you have to pay for that unfortunately. The ring signature itself involves some cryptographic constructions that have to be stuck on the chain with your transaction. That takes up space, space is going to cost you in fees and in verification time as other folks download the chain to check it. There are always tradeoffs with this in terms of efficiency. We’d like them to be as big as necessary, but not necessarily larger. And as Justin said, when we decided to enforce the mandatory ring size of 11 that was also to reduce distinguishability. If for whatever reason you always decide to use ring size 69, then if someone see one transaction on the chain with a ring size 69, they’ll say oh, that must be the ring size 69 guy. So that’s not good for distinguishability. Ideally transactions should look as identical as possible, so it was done to reduce distinguishability with the idea that there are certain kinds of analysis for which a larger ring size is not necessarily valuable. So that’s why they’ve increased, they’re all prime numbers, which I had not realized until someone asked if there was a deep mathematical reason why the ring size increases were all prime numbers. I said, no. But surely you meant it as a math joke, right? I said no, I did not, maybe some other people saw it, but I didn’t. I felt foolish, I’ve studied math for a long time but I couldn’t see the prime numbers through the trees. So anyway, that’s where ring sizes are now, and some of the changes were made coinciding with the RingCT deployment and the RingCT deployment was when we made some fairly major changes to also hide amounts of transactions. We can also talk about the fact that that was really good too because prior to that, how you had to do ring signatures was a little bit wonky. I was sending 123 Monero, we’d have to break it up like how you would break up dollar bills. So I’d have a 100 XMR note for an output, I might have a couple 10 XMR notes and some 1 XMR notes. You can denominate them however you want. What we’d effectively do, is for that 100 XMR note, you would go a pull a bunch of other 100 XMR notes together and make a ring with those and so on. It was kind of useful at the time, but fairly wonky approach where you had to pull based on denomination. There were impacts on this too where if you had really small amounts, it’s unlikely that you could find equally denominated amounts from this big pool of denominated notes. It kind of became a mess and it’s not great for analysis because it’s dependant on the denominations that other folks are sending and that’s not great. The RingCT deployment was fantastic for many reasons, but one of them was that there are no more amount in Monero transactions. You can’t see what they are. It doesn’t mean you can make up numbers, the math does all have to check out and that was part of why we had to alter our ring signatures, to make that work. But it did mean that instead of having to worry about how many 100 XMR outputs there are that I can among in my ring, that doesn’t matter anymore. You can just arbitrarily choose these post-RingCT outputs and build a ring out of them. It’s pretty fantastic. It’s better for efficiency, it’s a lot better for distinguishability and it makes the pool of outputs from which you can choose from as wide as possible within the RingCT environment.
Justin: Can you talk a little more about the discovery process before the first Monero Research Lab papers were published? Was it well known that Monero had limitations or did someone ask for PhD or PhD candidates look at this and ask if you can break it? How did that process work in the early days?
Sarang: It was fairly well known that there were limitations to this. In particular the blockchain introduces structure, so on it’s own as this beautiful mathematical ideal a linkable ring signature does exactly what it says on the box. It provides perfect plausible deniability of the sender in any kind of message, we use it for transactions. So in it’s own little environment it’s ideal and has these great provable security properties and we absolutely love it. But the second we start introducing structure into the blockchain, by structure I mean that we have an ordering of transactions, we know that certain outputs be chosen in different ways based on how you’re randomly choosing outputs for your ring signature, some people might interact with exchanges which may have some information about what they’ve been doing, when we had denominated amounts there was a lot of information of amounts you were sending, if you’re sending the same amounts each time. Anytime you’re able to glean any amount of information, any kind of structure, any kind of metadata, that’s not good. That is something that an adversary might be able to use to generate some kind of provable analysis or some kind of heuristic, which as we have said is basically an unprovable guess based on supposed behavior. Some of those things were known, they weren’t necessarily formalized right away. They were documented in some...you know it’s very hip these days to publish a paper on some little part of Monero analysis. At MRL we get sent papers, often not of the highest quality talking about some little part of Monero analysis, often involving ring signatures. But in the early days we didn’t have a lot of that. Some of the Monero Research Lab papers, about one in four, talk about some of those early analyses. One of which involves things about 0-mixin transactions, how that interacted with some of the earlier, pre-RingCT denominated amount stuff. Some of the other ones had to do with so-called chain reaction attacks that we’ll be talking about, I believe in the next episode. It’s very much an ongoing process and part of why I like that Monero is able to iterate so well with it’s regular network upgrade schedule is that we can take into account some of these things that are found and iterate on them. An asset like Bitcoin doesn’t really have to worry about this. Bitcoin is about as transparent as you possibly can get. There’s really no privacy concerns in that sense on which they have to iterate. But for something like Monero, the analyses aren’t going to get worse. The analyses that people do are only going to get better and that’s not a bad thing. When folks do publish work, whether or not it’s high quality, I like to see it because I like that we can use that information to make Monero better. But it also means that it’s helpful that we can iterate so rapidly. As you saw in that chart, ring size goes up because we worry about different forms of analysis that we want to avoid, among other things that we iterate on.
Justin: Cool, given that we’ve improved Monero’s ring size in the past and we’ve covered most of the basic forms of attack that we’re concerned about. Do you still think that ring signatures remain one of Monero’s greatest limitations?
Sarang: In terms of limitations, I would say yes, but primarily in the sense of an annoyance. If you’re going to do any kind of analysis on Monero, and again, there are plenty of papers out there. Some of them are great, some of which I think are pretty low quality. A lot of them will deal with analysis that comes out of the fact that ring signatures provide a limited anonymity set. If I know that 1 of 11 outputs was spent and generated some outputs which itself was used as one of a bunch of rings, that invites structure and that structure invites analysis. It is surprisingly difficult to avoid all possible heuristics. So if someone points out, my goodness, there’s a heuristic there. I’m like yeah, anytime you have structure, you’re going to be able to come up with some kind of metric that you might use to make informed guesses about what output the true sender is. Generally, if you’re using Monero well, that doesn’t have a practical impact on your privacy, but it’s still something we want to avoid because attacks don’t get worse, they only get better over time. So I would say that it’s the biggest source of annoyance. I’ve long been an advocate that someday we’ll get rid of ring signatures and it would be a good thing if we did it correctly. I still think that that is absolutely the case. A lot of what we do ends up being analysis surrounding that, it’s a good thing that we’re using our time that way, but if we can move onto something that’s better for sender ambiguity, we could use our time elsewhere.
Justin: So given that, why hasn’t Monero tried to move on to one of these other systems? It doesn’t seem to be developing one of those systems yet, is it that ring signatures are still the best thing we’re aware of or what are the circumstances?
Sarang: Like I had said before, for some kinds of analysis, not all of them, larger ring sizes are better. I use larger ring sizes as a proxy for sender anonymity sets. And again, sender does not mean wallet addresses, it means these one-time addresses as an additional layer of obfuscation. But again making just arbitrarily larger ring sizes, while it would help some attacks and analyses is hugely cost ineffective. For example, if we went from ring size 11 to ring size 1,000. So your output is one out of a thousand that you just plucked off the chain, that is going to be a very, very large transaction, it’s going to be fairly expensive to generate that ring signature. When you do a transaction, part of the time it takes is actually generating this cryptographic ring signature structure, and it means that everyone else who download the blockchain pays for that space and also the time it take to verify that it was done correctly. There are very small amounts of time, on the order of tens or hundreds of milliseconds per transaction to verify that the ring signature is correct and that’s important to do, but that really adds up when you have a few million transactions. Everyone says, my god, why is it so slow to do blockchain validation, that’s part it. Those little, little times add up over time. Some things could be made better if we could do that, but unfortunately we don’t have a way to make a very, very large ring signature that is also efficient. There have been some schemes that have been proposed to do similar linkable ring signatures in ways that would let us make the rings very large, like over 1,000 without taking up that much space. But unfortunately, mathematically, you have to pay for that with verification time. Like you hinted at, there are other schemes that do not use ring signatures at all for sender ambiguity and anonymity. For example, the ZeroCoin and ZeroCash projects, those have effectively as large of an anonymity set as you could possibly get. Their anonymity set is effectively every single note or output that has been placed onto the chain. Now, how that interacts with other forms of privacy, like amounts and recipient anonymity, that depends on the particular scheme. For example, the original ZeroCoin paper was one of these proposals that would have had a large anonymity set, but you didn’t have any control over amounts. You could only send unit amounts, it was designed like a Bitcoin lottery. Cool, I guess, but they paid for it in other ways by not being able to have particular amounts. Also trust comes into play a lot. The ZeroCash project for example, which ZCash is a modified instantiation, solved the ZeroCoin problem by allowing you to do arbitrary amounts. If you’ve used the ZCash system, you know that you can sent whatever amount you want, like in Monero, and you do get a very large anonymity set if you stay within the so-called shielded pool, fairly private transactions. But in that case they pay for it, originally in terms of generating the proofs involved with that, while being very small, which is good on a blockchain, took a long time to generate. So they pay for it in that sense, and they also paid for it with the now probably famous, or infamous, depending on how you look at it, the ZCash multi party computation, the ceremony. Where the ZCash instantiation of this big proving system that let’s them do all this fancy math involves some computation that you basically have to trust that the folks who did it were not compromised, or that at least one of them was not compromised. So there’s always these limitations, ideally we want something with a very large sender anonymity, we also want something that allow arbitrary amounts, we also want something that doesn’t require me to trust that a group of people did some original ceremony correctly, because maybe I trust them and maybe I don’t. And I also want to make sure that it’s efficient. Originally, I couldn’t use a phone to do a shielded ZCash transaction because it took a long time, even though they had really small proofs. With Monero, we can do stuff pretty quickly, but if I want to increase that ring size, I have to pay for it in terms of space and a little bit of time. So the answer to that, to make a long story a slight bit longer, is that there is nothing right now that gives us everything that I want. It’s a very hot topic of academic research right now, how to get rid of some of those things that we don’t like. I am personally of the opinion, that if you cannot accept trust in a centralized party like the ZCash company, then Monero is probably your best option right now for getting reasonable sender ambiguity. But again, someday, we’ll be able to get all of those things that we want, and I would love to move to that if it works for us.
Justin: Excellent. Are there any other final thoughts you want to add in this initial introduction to ring signatures and their history before we move on in future episodes to the specific attacks?
Sarang: I’m trying to see in my notes if there’s anything else. The gist of it I think is really that they do what they say on the box, but blockchains introduce structure. That’s where a lot of our annoyances come from. The process has been iterative, but that’s because we’ve been learning the ways that you can use external information and the structure that’s introduced by the blockchain and people’s interactions with it. Those things are what gives us the problem. You might kind of flippantly say that ring signatures have all these problems. Well, not really. The structure itself, the ideal mathematical construction, that you can read about in the academic literature, does exactly what it says it’s going to do. The ring signature itself is not broken. What it does do though is introduce this structure, and that structure allows for all different kinds of analysis that give you varying levels of annoyance and that we try to iterate on. It’s very much like a belt and suspenders and a second belt and gluing the pants to yourself kind of thing. We try to iterate on things that we think could potentially be any kind of problem for our users in order to improve privacy to the extent that’s possible. Like we said in the first episode, privacy is not a switch you flip on or off. It’s very dependent on your threat model, on the risks you’re willing to take, and the particular kinds of analysis that we think are going to be relevant to our users. It’s all a compromise, anyone who claims they can figure this out without compromise either doesn’t know what they’re talking about or does and is just full of shit. We do, I think the best that we can do given the limitations that we know our users are willing to accept.
Justin: I believe this is the last comment. Is there one major risk that users should...or one action users can do to avoid the majority of risks? What would that be?
Sarang: I would say, that in general, the most issues that might come up for users end up when you interact with an entity that has more information about you. The big classic example of this is exchanges. It would be fantastic if I could pay my rent in Monero and do all this stuff with Monero in a way that wouldn’t require me going to a regulated exchange and converting to fiat currency and stuff. But also understand, that’s not the world we live in. If I’m going to pay my rent, I’m probably going to that in my local currency and that will likely, depending on where I live, involve me going to a regulated exchange, that may know for example, information about my Monero address, it could involve information about me personally, where I live and all sorts of personal data. Interactions with those entities are things that could cause problems if done repeatedly or flippantly or in ways that you worry might turn evil later on. So if you are very, very worried, if you have a threat model that would not necessarily allow that, then maybe giving your name address, personal identification numbers and things to a regulated entity might not be for you. But I would say for the majority of reasonable use cases that I think we tend to consider on a day-to-day basis, I think Monero does an excellent job and it’s recent iterations have gotten a lot better. So ring signatures I wouldn’t say worry me, they annoy me.
Justin: All right. So with that annoyance, thanks Sarang for your insight today.
Sarang: Oh it’s going to get so much more annoying when we go into details on particular annoyances. This has been very purposely vague I’ll say today. We’re going to talk more about different kinds of analysis, both historic and modern day.
Justin: This has really helped set the stage for anyone who is re-learning about Monero’s history or being reintroduced into it. And also understanding ring signatures on a high level and how Monero researchers approach them because they’ve been a source of annoyance for many years and a lot of focus as far as research and development are concerned.
Sarang: And if any of the viewers want to learn more or are more mathematically inclined and want to know more of the details about how they work. Zero to Monero is a fairly well endorsed technical guide to how Monero works. You can see it on the Monero website and that does have a really good explanation of the math behind the ring signatures if you want to understand that. You won’t really have to understand that to understand the rest of the episodes, but if you want more details, they are available.
Justin: All right, thanks everyone for listening and I hope this episode of Breaking Monero will help you understand more about these ring signatures and it’s really critical that you understand those basics for the rest of the series. So again, thanks Sarang for being here with me today. Thanks to you the viewer for watching today’s episode and we hope you’ll watch future episodes, especially those were we get far more granular on specific attacks that people are worried about. All right, thanks everyone, take care.