Dr. Sarang Noether - Bulletproofs

Dr. Sarang Noether Discusses Bulletproofs and Monero
October 22, 2018

Transcribed by Cake Wallet for Monero on iOS



Speaker 1 (Justin): 00:02
Hello everyone, and thank you for coming to today's Bulletproof conversation with me who's just the random person helping Sarang here. And so Dr. Sarang Noether who is here to really give you all the information that you need to know.

Um, so we can start off with the, maybe a little bit more introductions with Sarang especially, but um, this is really meant to be the communities’ time. We're here to facilitate a conversation and answer questions, as you have them in chat.

So what, we're not here for Sarang, like for Sarang knows more about Bulletproof, right? It's for you all to learn what Sarang has to say. So make sure you ask questions and we'll be able to get to them plenty. There's no real rush with this.

We're just trying to make sure that we have a nice informal but still good resource for people within the Monero community and potentially other communities. Anyone interested in Bulletproofs. So that they can sort of start somewhere and get going. So with that, Sarang would you mind introducing yourself for everyone, please?

Speaker 2 (Sarang Noether): 01:08
Sure! So I am Sarang Noether, which is a pseudonym, and I work as a full time researcher right now for the Monero research lab. And as you may know, the Monero research lab is a work group of the Monero projects.

And it is our responsibility to kind of do coordination and kind of spearhead a lot of kind of the initial kind of theoretical style R and D stuff that goes on with Monero, you know beside what's new in the cryptographic community, you know, what can we come up with that are new contribution to the crypto community, determine what's feasible to go into Monero eventually, what's not and just kind of what lessons we can learn.

So there's, it's a huge field, especially in the privacy and fungibility space. It's a really big growing field and it's our job to be on top of it. So a lot of what we do is, going through papers, we do a lot of kind of, you know spit balling and prototyping and for some stuff like Bulletproofs, it does eventually make into the code base.

Huge portion of what we does not ever make it anywhere. But that's okay, you know, there's the old saying in research that like, if you knew how the research is going to end up with it wouldn’t be called research, you know, just keep doing the work. So we do sometimes talk about the stuff in the coffee chats. This is not a coffee chat, there was a boat and this is a bee's knees, so it’s going to be a bee's knees chat and I know that Justin you're, you're not quite as sophisticated as my bee’s knees that I made now, you know………..

Speaker 1 (Justin): 02:28
I know I'm not. I just have what I pulled from my fridge, which is a Sierra Nevada, October fast.

Speaker 2 (Sarang Noether): 02:34
I want to join you but I don’t have any beer in my fridge, so whatever, its okay, so delicious. It’s Crisp, just like Bulletproofs Crisp & Light. So yeah, our goal today, I guess, is to give just a really informal, you know, we can make it as formal as people want, introduction to, what did we do with Range Proofs, which Bulletproofs are example of, why did we do it? How's it gone? Where we're going to go with it? Any other questions that I know you might have.

So, to kind of give them the history of Bulletproofs, you kind of have to backtrack a little bit. And so a while back in 2017, we came up with the idea of like, ring confidential transactions. So, it used to be the case, if you're not familiar with how Monero used to work but we always had rings signatures which kind of obscured the input of your transaction. We always hid the destination of your transaction, that's the so called stealth or one time addresses, we always have that.

And but previously, the amount of the transaction was not hidden. So the way it works is, it kind of work the way that dollar bills work, if you might have a $1 bill, a $10 Bill, a $100 bill, if you're lucky, and things like that, and so Monero what you would do is, if you wanted to send, you know, I don't know, thirteen (13) Monero sometime, which now is I guess a lot but, you know, suppose you want to send thirteen (13) Monero, you're very unlikely to find a bunch of other people who also at some point had spent thirteen (13) Monero, so you can't just drag those into your ring signature as possible decoys to fake, you know who's actually sending that 13.

So what you would do is, you would basically break up the amount that you were sending into denominations. So you might have a ten (10) Monero note, and you might have a few one (1) Monero notes, and so you would grab a bunch of other, one and ten (10) Monero notes, throw them into your ring signature, and do it that way. So we had what where so called denominations. Which, you know, works to a point, but it gets bulky, and it's, it's not very flexible, and it means you have limitations, right? There may be a bunch of one (1) Monero notes floating around, and maybe not a lot of 10s, or hundreds, so you're limited.

Plus, it's just not a good idea to have the amount flowing around, right? Someone can figure out what your salary is, if they were able to identify who you were. It’s, we'd like to have the transactions look as non-descript, boring and information-less as possible. And that was one thing that we didn't have. So the idea of confidential transactions originally came out as a proposal for things that can be used in Bitcoin and by some of the developers who worked with that.

And the idea was that, if we could find some way to obscure the amount of our transaction entirely, we could do away with this whole denomination thing, hide the information, and presumably make it a lot easier to pick fakes that go into your ring signature. After all, if you don't have to worry about these denominations that you got to hunt around for, I mean, if you can just pull in any old fake outputs from previous transactions at once, and mix those in with your own to form the rings signature.

And the way we do that is a little bit tougher than what would have been done in Bitcoin, because this has to play nicely with our rings signatures and there's technical reasons why that happens, and you know, we can point you guys to some resources later on, if you want to know exactly how that works. But the moral of story is, whatever we do with hiding amounts has to play nicely with the ring signatures, because that's how we operate. So the way that we do it is what's called a cryptographic commitment.

So you have your so called output, which is kind of like a message saying, I destined some Monero to go from this person to this person. But instead of associating that with just kind of a plane amount, like thirteen (13) Monero, you actually hide that in what's called a cryptographic commitment, which means that you basically take your amount and you do a multiplication by some other………… it’s actually a core point, but basically, by some other numbers and the large number to obscure it, and you hide it with this additional kind of blinding factor.

So at the end of the day, instead of having an amount, you just have this random blob of data. Turns out, it's actually an elliptic curve but it's this blob of data, which alone doesn't tell an observer anything, it's just like, there's some blob that came in from this ring signatures and it’s now going out to somebody else. But of course, we'd make sure that you didn't just make up an amount you didn't have access to.

So the way that the signature works is it basically confirms, kind of internally that the amounts balance. And the way you can tell that balances, is that these cryptographic commitments that look like random blobs, actually have algebraic structure to them. And the algebraic structure comes from the fact that you're taking an amount and kind of multiplying it by this other large number, which is actually a curve point. And what it means is that you can actually add it to track these things.

And it doesn't give you numbers out but it adds and subtract them in a way that can be useful when you're doing algebra operations. So if I take not the amounts, but if I take the commitments or blobs to the amounts from the inputs of my transaction, this ring signature business, and if I take the outputs that are leaving the destinations, the amounts for that or rather their commitments or blobs, and if I also include fees in there, because we do have transaction fees, and you can work those in to, you can basically show that those balance to zero without actually revealing what they are. And that's really cool.

So that's what a cryptographic commitment is, it's basically a way to encode in a way that's not reversible what the amount of a transaction is, but it has enough structure that it lets things balanced properly. So balance is important. We also know there's a way to work that in with the rings signatures as well but it’s not terribly important right now, that shows that you control the proper amounts and stuff. And we can give you resources later for how that works. But that's kind of the basics of it. So where do Range Proofs come in?

Well, range proofs come in, because you have to make sure that you're not using funky negative amounts, because obviously we are assuming that everyone is spending nice, reasonable positive amounts of Monero. So the amount going in, we know can match the amount going out because these commitments have fairly nice algebraic structure to them. But we need to make sure that you're not throwing around negative amounts.

If you throw around negative amounts, you could basically put your own money because you could find different equations involving sums and differences of positive and negative amounts and whatever in these commitments that would balance to zero. And if you can convince someone that these things balanced to zero, then you're golden. That means that you basically printed as much free money as you want. We don't want that, that basically breaks the contract of an asset, which says it like, you can't just randomly create value, it's got to come from somewhere, you got a mine it or someone’s got to send it to you.

So what a Range Proof does is, a Range Proof basically is a way to hand someone's blobs, his commitment, and say, you can't actually see what the amount is, you can play around with the amount later, in a kind of a balance equation but you can’t actually see what the amount is. So how do you know that it's not a negative amount? How do I know that it's a reasonable amount that's not going to be used in some funky way like that?

That's what a Range Proof is. A Range Proof is basically any kind of structured data that you can provide when you're doing a transaction, that anyone else who's downloading the blockchain, any verifier can take that commitment and that blob of proof information and look at and be like, I am now convinced that even though I don't know what that amount was, I know that it was not a negative number.

And technically, if you know about this stuff, it's not really a negative number, we use kind of a looping number system, it's modular arithmetic over a really, really large field. So very large numbers and small negative numbers are actually the same thing but for our purposes, you need to make sure it's not negative. We can go into detail later, as deep as you want. It's algebra. Hooray! But maybe you don't want to do that. At any rate, you got to prove that it's not negative. So how do we do it before, because obviously we've been doing ring confidential transactions with these commitments for a while now, this is not anything that’s like, really, really new to Monero.

Well, the way we used to do it, was kind of like the best way that people knew how to do it. The way you did it, was you had your commitment, your blob of information, your unknown amount of Monero that you're sending, and what you did to generate the Range Proof is you basically broke up that amounts into bits, you can do a bit decomposition, powers a 2d composition, you know, 0, 1, 1, 0, 1, or whatever that represents the amount. And what you would do is, you would basically generate a separate cryptographic commitment to each of those bits themselves. This is why the stuff gets really big.

The big complaint about Range Proofs was always that they were really big and bulky and whatever. So I break apart my amount, which I know because I'm the sender, I do a commitment to each of those bits and then I actually generate a bunch of ring signatures, separate from the rings signatures that we do for like traditional transactions. I generate ring signatures over each of those bits. And what I proved to an observer is two things. I prove to an observer that one, all those little commitments that I built up, I proved that all of those can be used to reconstruct my big amount blob. So that tells an observer that I generated these commitments fairly, and that they accurately represent the big amount that I'm dealing with.

Speaker 1 (Justin): 11:04
Sorry and just interrupt. Sorry, I won’t say anything else. So when you say bits, are, what you generate, are they like bits of information or are they bits of the transaction?

Speaker 2 (Sarang Noether): 11:16
Bits like zeros and ones, like number systems, binary numbers, take my amount, right? It is a binary number. And I had those little individual zeros and ones that if I write them in binary and associate powers of two to them, can be used to just add them up and reconstruct that number that was the amount. Yeah! So I’ve literally use bits, like number, number theoretic number system bits.

So I generate a bunch of little commitments to those bits, I basically make it………. I construct those commitments in such a way that any observer can add them up again, in a clever way, and prove to themselves that they do represent the bits of that number. So I'm not just making up some other random bits. And then the ring signature for each of those bits, shows that each of them is either zero or one. That's what I got to show. So if I base……….. So then I kind of take all that information, all these commitments and ring signature information that's also detailed, and I package that up, and I'm like, this is my Range Proof.

So when someone receives the Range Proof, they know a few things, they look, remember I still have my big enough commitment that they don't know the blob that represents the value of my transaction output. What they do is the observer, you know, if you're thinking of blockchain, you actually do this, you do the verification of this, you take all those little bitty commitments that you see there, you do some power two stuff and you add them all up, because they have nice algebraic structure and you convince yourself that they actually are commitments that represent the bits of my amount in some way. And then you verify this ring signature to show that each of those bits was a zero or one.

And that is actually enough to convince you that it's within a certain range, because you know how many bits I'm dealing with. And if we know how many bits I'm dealing with, in binary arithmetic that tells you the biggest number you could represent. In our case, we do to the 64, which is larger than anyone would need, but still reasonable for our purposes about not being a negative. And that's basically does it, the observer is convinced that even though they don't know what the number is, and why don't they know what the number is? Because all they know is, each of those bits is either zero or one but they don't know which it is.

And that's the clever part. So an observer gets no information about what the actual number is, but they know kind of a bit range that it is limited to, and they know that I generated that kind of representation accurately and didn’t lie about it. Because we have to assume that everyone's going to be lying about everything. That's how a Range Proof works. Had a ton of downsides. One downside is that verifying the Range Proof, which if you're thinking the blockchain, you have to look at all these Range Proofs and you have to verify them computationally.

And how long does it take? Well, you know, it can be on the order of, you know, 10s to hundreds of milliseconds depending on your hardware, which is actually a lot if you have to do this a ton of times. There's a few million transaction outputs that you have to do and the numbers always growing. So you have to verify that. And that verification process means you have to do all this kind of elliptic curve arithmetic on all these things, commitments. And that takes time. So not great, you know. So it takes time.

It also takes a lot of space, because what am I actually sending to the verifiers? What am I putting on the blockchain in this transaction? I'm putting a commitment to every single bit. So to do the 64 of those, for example, or 64 of those representing the different bits and I'm including rings signature data on those. So that's a lot of space that we're taking. That's why Range Proofs are big. They also scale that way. So transactions, if I'm making a transaction, if I'm just sending some fixed amount to somebody, I'll generally but not always, have one amount that I'm destined to the recipient.

So if I'm sending money to Justin for example, I'm taking some amount of Monero in and I'm sending some portion of that out to Justin. That's an output representing some amount that I have a commitment or blob to, but typically, I also will have change. So the change is a separate output, I'll usually destine that back to myself. That's how it works. So all the Monero have to be spent in my transaction, they are spent to Justin or they are spent this change to me. And if you're doing other kinds of transactions, you might have a bunch of outputs that your destining, if you're doing full pay out, you might have a bunch of additional output’s to people but typically, you got two.

Even if I'm sending the exact correct amount, I'll still typically include like a zero amount to myself just to obscure what I'm doing, because we want stuff not to stand out. So this gets big. By big I mean, on the order of like, the Range Proofs alone do that, for like a two output transaction are on the order of like, 12 kilobytes. Is that a lot? Well, it is a lot if you consider that, for example, a Bitcoin transaction is on the order maybe 600 bytes, so we're talking about something like 12 kilobytes. And if I'm doing full payouts, for example, that just blossoms and gets huge. And if you ever take a look at kind of the blockchain growth charts that show how big the blockchain is over time from Monero, we have like this nice increase before we had ring CT.

Because remember, before we did all this confidential stuff, you know, we just had like these denominator amounts, there were no Range Proofs because nothing was hidden, we knew what the amounts were. We had this nice little growth rate and then we just decided to do this whole commitment, confidential transaction thing with these giant Range Proof, and it just is like a change in slope that it just skyrockets upward. It’s nuts, it’s like……... Yeah! It's a rocket ship going nowhere. Why is going nowhere when everyone's like, why is the blockchain 60 gigabytes? That's why the blockchain is 60 friggin gigabytes. It is all Range Proofs.

Speaker 1 (Justin): 16:24
Yeah, it's all, it's all 2017 and 2018 like 14, 15, 16. That's all essentially the relevant compared to the total blockchain.

Speaker 2 (Sarang Noether): 16:34
Oh yeah! It is just like, bonkers big, bonkers big. So as we're thinking about like, Man, what can we do to make Monero better? Have words like, maybe we can make the Range Proofs better? Because there was nothing inherently special about the way we do Range Proofs. We just need some way to be able to hand someone a representative blob, a committed to an amount and just prove that it isn't a negative number. That's all these things answer. They answer nothing else and they do nothing else. It’s crazy! And they're the biggest thing. And you know, there were some ideas for, you know, ways that it might be done but no one really had a great solution. They all scaled really badly and they were all really big.

And then Bulletproofs come along. This paper gets dropped. It was done with collaborators in Stanford, University College, London, some folks at block stream, probably forgetting someone, you can look this up, just Google the Bulletproofs paper, and you'll probably find it. A few different versions. So this comes out and what this promises is that we can do range-proofs that answer the same question, namely; is this blob of information, does it represent a positive reasonably sized number, it answers that, it scales amazingly, by amazingly, I mean, that we could take this thing that used to be about, you know, 12 kilobytes per transaction and we can drop it down to about 700 bytes.

Huge decrease, something like 80% is like the number we threw out for a while, if you run the numbers on it, which is crazy. Not only that, it scales way better. So if I'm just doing a standard two output transaction, some money to you, some change back to me. You know, that's two outputs, turns out that that's about 700 bytes. But let's suppose that I'm doing some giant payout, right and I need to destine money to Justin and also to someone else, and someone else and someone else and a bunch of different people, normally that will scale terribly. It's like take that amount that we had, that 12 kilobytes and scale that out to however many outputs I'm doing, it gets crazy really fast. But with Bulletproofs, I can just generate instead of a bunch of different Range Proof everything,

I can just generate one single large Range Proof that represents all of those amounts together. And it scales amazingly. Every time that I double the number of outputs that I have, I just add a mini minuscule amount of data to it, absolute minuscule. So instead of scaling linearly, which means with the number of outputs, it actually scales logarithmically, which means with the number of times that I'm doubling the number of outputs. It's crazy, in theory you can get it, these things as big as you want. But it gets better. It turns out that instead of doing all of this crazy curve arithmetic that we had to do with our old Range Proofs, they were called boring Range Proofs, because of the kind of ring signature that they used, boring ring signature. Instead of doing that, you could use some different operations which we can talk about later, that it turns out, you can verify that that proof is correct.

 That is, that that represented number is that small positive number, you can do that verification much, much faster, which is great. So we determine that you can have a bunch of Range Proofs together and you can verify them very quickly. Now, the verification does not happen logarithmically. That is, if I have a bunch of different outputs, it doesn't mean that I only had a miniscule amount of verification time. It turns out that does scale linearly still, which means that a, you know, a pool output, pool pay for example, that has like sixteen (16) destinations, still will take, you know, a lot longer than just like a two destination transaction to do verification on. So that's not great. But we do end up solving the problem of blockchain bloat, and we can still verify stuff faster than we can now. We don't get the, like bonkers scaling of the size with verification time, but it's still better. So that's awesome. There's like, no downside to this. It's great.

Speaker 1 (Justin): 20:06
Okay, just interrupt you really quickly. So there is one question come in that just said, they had never seen a 700 bytes transaction with Monero yet, as they see it's been really 1.5 to two kilobyte ratio.

Speaker 2 (Sarang Noether): 20:21
Yeah! Absolutely! So the Range Proof, the Range Proof itself is not the only thing that goes into the transaction. So that's just the Range Proof. So on top of the Range Proof, you also have other information that involves the output public key, you have that commitment, there's a little bit more data that gets thrown in there, information you transmit to the recipient, and particularly you also have your ring signature itself. So you have the, you have the right Range Proof here, but you also have the ring signature, and the rings signature depends on how many ring elements go into that. So, all that other stuff adds on to that but 700 bytes of that is from the Range Proof. So the old transactions themselves are probably about 13 kilobytes, about 12 kilobytes of that is typically the Range Proof. So you still have a little bit of extra stuff in there.

Speaker 1 (Justin): 21:04
Okay. And so are Range Proofs still like one of the big scary intimidating components of a Monero transaction size and verification time? Or are the other components, a larger proportion now that the arrangements and…………..

Speaker 2 (Sarang Noether): 21:18
The other ports are………… the other parts of the exact same size they always were, but they now constitute a larger percentage of a transaction. So now it's not like we have transaction stuff and then we have the Range Proof, it's now like, we have transactions stuff that includes the Range Proof. It's much less creepy. And in fact, if you go onto a chain explorer, like, I always use like, xandychain.net, you can look at transit like recent transactions, and it'll tell you the number of inputs, which means how many, how many, you know, chunks of Monero that came from somewhere else and they are pulling in, it'll show you the number of outputs, oftentimes it's two and some stuff like Coinbase stuff only has one and other big payouts will often have more. And then it'll also include the ring size.

And in particular, if you're look at most of the transactions, like I'm just looking at a list on the side right now, I'll typically see around like 1.8 to two kilobytes for example, for most of the typical, you know one or two inputs and two output transactions. But if you happen to look down the list, and you might see one that uses a lot of inputs and this can happen if you're doing a sweep for example, or if you just have a bunch of little bits of Monero that you're trying to aggregate together to send. If you look at that, so if you look at something that has a large number of inputs on that list, you'll see that the transaction size is much larger. So I'm seeing one here that's got four inputs and two outputs, and that's about 4.3 kilobytes, for example.

So that becomes a much larger part of it than the Range Proof itself does. The Range Proof unfortunately is a lot less. So you’d probably keep that in mind. Hopefully, that answers that question.

Speaker 1 (Justin): 22:47
Okay. Yeah! Awesome! Cool.

Speaker 2 (Sarang Noether): 22:54
So the Bulletproof paper comes out, you look at it, you’re like holy crap, this math is good, like, it looks like is a very feasible thing, we should start to work out a way to do this. So worked out some prototyping code, just to do some little bit of correctness testing, and just kind of play around with the way that we might do implementations of this, because at this point, there were no implementations, you know, there was, there was a mathematical paper that came out as a pre print and, you know, later got published in journals, and was, it was updated a few different times after that, which is pretty typical.

So we have that come out, it has all the algorithms written out, all the algebra, the security proofs that show why this works, different ideas for applications, benchmarking sizes and stuff but is still in kind of an early stage but people were already really excited about this. And there were questions about how can we optimize this even more? So we know the size, like that optimizations great, logarithmic size scaling is phenomenal, like you almost can't ask for anything better than that, constant size would be great, linear is bad, logarithmic that's just, that's just fine but verification time is still the thing.

And initially, we weren't really sure if we'd be able to do a whole lot of times statement on that. So when the first time original blueprint came out of that paper, it really wasn't clear what the optimal times would be, no one had worked it out yet. The authors were still, the authors themselves, and we're working on doing an implementation of this for the particular of the core that the Bitcoin was using. And one of the authors was doing that. And that's done now by the way, it's very good. So the question was, you know, can we optimize it for our curve? And, you know, can we find ways to do the verification faster?

With the original Range Proofs, the old ones, the math on it was pretty straightforward, and there really isn't, wasn't any way to optimize that time, you had to do these curve operations, and they're fairly slow (Incomprehensible: 24:33) can’t do anything about it. And as far as we know, we can optimize that down before, otherwise we would do that for the old stuff, which we have to lug around for all eternity, unfortunately. But we kind of, alongside some of the authors of this, we are working on our implementation as they were working on theirs. And during that time, there were a lot of optimizations that were discovered. So to do the verification of the Bulletproof for example, you have to verify a few different elliptic curve equations.

And we're like, okay you have to verify a few equations, no big deal. But it turns out, there are ways to hugely optimize that, where you basically can take all those equations and kind of cram them down together and do a verification of all those equations all at once. And that's pretty solid. In particular, what happens is, you look at the product of elements, and you show that that is equal to zero, or some of those, you do a sum of a bunch of curve elements, show it’s equal to zero, do another bunch of curve elements, show that's equal to zero, and so on. Turns out simple algebraic trick you can do is, you can do kind of a weighted sum of all those equations, if you remember your linear algebra and if you show that zero, you've done it.

Which looks like it's not really any advantage, you're still taking a bunch of things, and you're doing a bunch of curve operations to them. But there are other optimizations you can do, and in particular called multiple multi exponential, where you do a bunch of weighted linear combinations of curve points. And you can tell us that you can do that a lot faster than doing each of them independently, which is pretty solid. Unfortunately, we didn't have any code to do this yet. So we're like, cool, more code that we can write now. So we decided to write up some codes to do these multi exponentiation operations, which if we could figure out how to do them, would mean we could combine all these different Bulletproofs equations together in kind of one neat, best little chunk.

There's different ways you can do that. We actually worked out three different ways you could do it that we knew about. One’s called the Boss Koster implementation, one is a Strauss implementation, and one is a modification of one called Picanchers algorithm. And there was some different projects that had done some of this stuff before but now we had a purpose for doing it. If you can do multi exponentiation, you can speed up these operations a lot. And it turns out, we did implement that and we see really, really good cost savings on that. You know, we can get down to a reasonable fraction, maybe, you know, 20, 30% of what it would take to do these things normally in the old way that we used to do it.

So we got code working with that, that allows us to combine a bunch of these equations in the Bulletproof together and it speeds up the verification time a lot, huge win. But then we were at a conference at Stanford, the blockchain protocol, something security, something conference, whatever, BPACE is an acronym. Went there in January………… Now it’s called Stanford Blockchain Conference, which is something I can remember. It's a conference at Stanford about blockchains.

Speaker 1 (Justin): 27:21
Yes.

Speaker 2 (Sarang Noether): 27:21
Part of me is convinced that they named it really badly, and the other one, to discourage like scammers from going to it. It was very a very (Incomprehensible: 27:29), which is great. And there was actually a presentation here about Bulletproofs and several of the authors were there, we hung out with them, talked with them a lot about it, since they knew that we were interested in working on it and we knew that they were working on their own implementations, a test of it.

And an insight happened there, in between a couple of the talks, which is wild. About, okay, we're able to verify a single proof really fast but it turns out, they figured out a way that you can use kind of the same algebraic trick that we used for this kind of big multi exponentiation to take as many separate proofs that you want, from different transactions all over the place, and just jam them all together and do one really solid verification of like, all of them together.

Because it turns out, if you combine these things together in a very particular way, you get just bonkers cost savings, you're not doing as many of these break operations as you had to do otherwise anymore. And we were like, oh! My God, unfortunately, none of this have been worked out to the paper yet, we knew that the math on a solid, but you know, we're kind of trying to work this out in code, along with the authors who are trying to work it out in code. And eventually, they worked that into a new version of their paper.

But to those who say, like, why did this thing takes so long? It was because like this hadn't been written out yet, people were still coming up with it. It was crazy. This is all very much an in progress thing. So we came out with, we came out with an implementation, as the other authors working on their implementation and testing too and we saw crazy cost savings on it, it’s called the Batching Operation.

So what this is helpful for is, if you are taking in a bunch of transactions into a block and verifying them, or someone just hands you a copy of the blockchain and says, you need to sync this and verify it, so you can start using it. You can take all these different school of proofs, shove them all together, and just do one big batch operation on them all at once, instead of having to do them all individually. And you see excellent cost savings on these as well.

Speaker 1 (Justin): 29:18
So can you just, a quick clarification, the difference between this batch verification………..

Speaker 2 (Sarang Noether): 29:24
Yeah!

Speaker 1 (Justin): 29:24
And the multi output Bulletproof savings compared to this………….

Speaker 2 (Sarang Noether): 29:27
Oh, yeah! So I know (Inaudible Multiple Speakers: 29:28-30) what makes this really tricky is, there's like four layers of optimizations to this stuff. It’s nuts, so we had to like, come up with like terminology, that's really not confusing. And it is anyway. So the idea is that if I am sending a transaction, I know all the information for the transaction, if I have multiple destinations, I can generate them, I can aggregate them, I use the term aggregation, I can aggregate those output proofs into one proof. So I am throwing one proof out into the blockchain instead of a bunch of different ones. If I have a pool during the payout, I send one proof that represents all, 116 of my output destination, for example.

Speaker 1 (Justin): 30:08
So basically, if you're sending a transaction, you just need to create one proof no matter what you kind of include there, in that transaction.

Speaker 2 (Sarang Noether): 30:15
Yeah! Yeah! It turns out also a talk a little bit later but there is actually a cap to this that we put in place. But you know, most people will not run into this cap, it’s 60. So anyway, you can do just a single proof. And turns out that we were able to optimize it so that that proof, even though you know, it was fast………….. it was much smaller in size than doing it the old way but it turns out, one layer of optimization can be used on that single proof to make it faster than it would have been if we didn't use these optimizations.

But if I am looking at the blockchain, and I see that each transaction has a separate Bulletproof in it, each of which itself could represent many different outputs, I can take all of those separate proofs, from separate transaction and I can just chunk them all together and verify them all at once and show okay, all of these are good, all the amounts that are represented are positive, non negative reasonable numbers, and I call that batching. So you gather them all up into a batch. So an aggregated that proof is within a single transaction generated by one person or entity, that knew all of the output information.

Batching is for completely separate proofs by completely separate people that's, they had no connection to each other whatsoever, no transaction connection at all. And that's another different level of that. So that's batching. So it turns out we can also batch very efficiently too, which is great for synchronization. Batching itself does not affect size, it's just an operation that we do to speed up synchronization. Now, why do you put a cap on it?

We applied a cap of 16 output destinations, and again most or two, so not a big deal. If you're doing pool payouts for example, or you might have other reasons, you might want to do a lot more than that, but the reason we put them in place is because the way that synchronization and verification happens is you have to do a very particular kind of, a kind of padding. So if a transaction normally would only have, say, a certain, you know, kind of given number of outputs, you have to do a little bit of padding in order to raise everything up to be a power of two. There are, there’s technical reasons behind why that has to be the case.

So if someone's got a, you know, a transaction with 11 outputs, you actually have to do a little bit more work verifying up to 16. So that means that the way that these work right, worked before, is that they were based on transaction size but transaction size isn't really a big deal anymore. So this one’s disconnecting Bulletproofs, in that the size scales really slowly, logarithmically, the verification time while still much better than it was before, it's still technically linear in the number of outputs that you're verifying.

So because there's that disconnect, it's possible in theory, if we had kept the old fee model for example, that you could just pack a transaction full of stuff, very, very cheaply, and force the network to do all that work to verify it. So it's technically a form of denial of service attack, which isn't good. So it’s why we modified our fee structure, so now it kind of accounts for the fact that Bulletproofs do that.

And in order to make that a little bit simpler and easy to understand, easy to work with, we decide to place the power of two cap on the number of outputs. And right now it's sixteen (16). In theory we like, mathematically nothing's forcing us to do that, you can do it to as many transactions as you want. All the math still holds, if we need to increase it later and we find a way to do it that makes sense with our fee structure and the verification time, then we could definitely consider that in the future.

But right now, if you have more than 16 outputs, what do you do? Well, you generate a couple of different Range Proofs, you do 16 of those outputs and one Range Proof and you do the rest in it that way. So you can still do it, you just have to do a bit more work.

Speaker 1 (Justin): 33:39
Awesome!

Speaker 2 (Sarang Noether): 33:40
In a nutshell, that's what these things are. They do the exact same thing as the old stuff did. Here's a blob. Is it a negative number? Yes or no? That is literally all the information you get out of a proof, whether it's these old bore man proofs, or it's a Bulletproof. It's a yes or no. But is a very important yes or no. It's a yes or no, of like, can I print free money now? You want the answer to the question, can I print free money, to be no. That's what it answers.

Speaker 1 (Justin): 34:07
Awesome!

Speaker 2 (Sarang Noether): 34:08
But we've been able to do it very quickly through optimizations in size, and a lot of optimizations in time. And, you know, (Incomprehensible: 34:15) not all of the time optimizations are in the code base yet, we kept on finding out more and more ways to kind of just, like, suck as much, you know, verification time out of these things as we could, and not all those made it into the release just based on the timeline.

So it's actually a pull request open right now to go make them even faster by adding a few other optimizations. And that's not going to require an network upgrade to do. It doesn't change the proofs themselves, it's just a way that the client verifies that they are correct. So those are going to just the future, you know, wallet upgrade. So as always, if you keep your software upgraded, you know, you can get all the best performance on stuff, which is great.

Speaker 1 (Justin): 34:50
So do you have any estimations for those, the speed and verification time and upgrades?

Speaker 2 (Sarang Noether): 34:57
No they are, you know, now they are fairly minimal, we got kind of biggest stuff into the release already. These are just kind of some small little tweaks just to eat a little bit more out, you know, it's unclear, you know, what, exactly this would, what effect this would have, you know, on like, total synchronization time, we can run those numbers eventually if we were curious, but, you know it's, might as well get as fast as possible, which is…………………

Speaker 1 (Justin): 35:16
What about the difference between the boring and Range Proof and the, the Bulletproof that you have now is, as terms of a relative percent, is it around 80%? Or is it a different number?

Speaker 2 (Sarang Noether): 35:25
Let's see, I think we're probably……………. Yeah, we're around like, 70 to 80% faster, or something. Oh! it's kind of buried over time, we had to add some other checks in there on some of the input elements and such. In fact, I should run my more recent one, now that we've kind of got all this stuff in place. The problem was all these time estimates that we had kept on fluctuating, because we kept on adding more stuff in there.  We got to get to run those numbers just to test now if we actually have it out. We have a test that I can compare the two for example. But, yeah it's much faster than it was before, which is pretty great,

Speaker 1 (Justin): 35:56
So just to clarify, someone had a question in the chat’s asking if this had an impact on the miners have the Monero network and the answer's no. It impacts…………..

Speaker 2 (Sarang Noether): 36:05
No it doesn't.

Speaker 1 (Justin): 36:07
It impacts the nodes that are receiving these transactions and sort of processing them and it impacts your wallet as you're trying to scan to figure out which outlets are yours. It doesn't impact how quick your miner mines.

Speaker 2 (Sarang Noether): 36:19
Yeah! Yeah! I mean, you know, technically, if you get a transaction in before we throw it in the block, you check to make sure it's valid, yes. But these are very, very small amounts. Realistically, what this effect is if you're doing synchronization.

Speaker 1 (Justin): 36:31
Exactly!

Speaker 2 (Sarang Noether): 36:30
Yeah! So if you got a lot of them, each of them is still a very small amount of time to verify but if you're going to be doing this for an entire chain going forward, then that's what matters Here's the neat thing, Bulletproofs aren't done yet. Bulletproofs are really good at doing Range Proofs, that's fantastic. There are entirely different applications to these, involving zero knowledge proofs, which everyone's talking about zero knowledge proofs. No one knows what zero knowledge proofs are.

So yeah, if you're reading the news, everyone's like, we invented zero knowledge proofs, of like I, hold on there, hold on there, technically, we're using zero knowledge proofs before we're using them now, it's a class of proof style that, you know, lets you prove various statements with some technical definitions. We're using them right now to prove a statement of the forum, this committed amount is in this particular range, and so on. But it turns out, you can actually use Bulletproof to prove much more general statements and so called arithmetic circuits, which is really cool.

For example, other projects, like Zcash for example, on their entire transactions verification structure, is based around a big zero knowledge proof that ensures that everything in the transaction was done properly. That involves things that are, kind of like, you know can I, you know, anonymize the sender and show that it came from a given set that's much bigger than our set, and does the transaction balance and a bunch of other statements too. And they use the Zk Snark for that, which has the benefit of being extremely small and compact, and very quick to verify, very quick to verify.

Previously, it was very expensive to generate those so that the proof time, you know was not great, they've since optimized that way down, so it's a ton faster. It's really great work that went into that. And of course, there's a trusted setup thing, where if you're not cool with the trusted setup, then it's kind of a non starter for you but it's still really cool tech. Bulletproofs can do similar things. Bulletproofs can also prove general statements, basically general arithmetic circuit based statements, in zero knowledge. But they are subject to the same space and verification requirements style that the Range Proofs are.

Namely, if you want to prove a very big statement, the size scales pretty well, the proof itself does not get very big. So that's cool. The proven time is going to be pretty slow. How slow? Well, it's going to depend on what statement you're trying to prove but it's still pretty slow. And the verification time is also going to be pretty slow, because it scales with like the size of the statement that you're trying to prove and such. So you're not going to get the kind of scaling that you're going to get, for example out of a Zk Snark, which is something that Zcash uses but for very particular statements, a Bulletproof could be useful.

I know there's other projects that are looking into using Bulletproofs to prove other very specific zero knowledge things that are not just Range Proofs. So there's a lot of work that's been going into zero knowledge proofs and Bulletproofs are a great example of a way to do it.

Speaker 1 (Justin): 39:22
Interesting!

Speaker 2 (Sarang Noether): 39:22
And we already have kind of some of the basic code in there. And there's a lot more that goes into it. But it's definitely an open area of research, you have to find a particular statement you want to prove that's useful to your asset. For example, determine if it’s reasonable to put it into a Bulletproof of a circuit, determine what the verification requirements and proving requirements are? Things like that. There's a lot that goes into it. But it's definitely something that we kind of keep in the back of our head, is now we have a proven system that's pretty darn good, and doesn't have a trust itself.

Speaker 1 (Justin): 39:50
Okay, that's pretty……………. So since we already got to this topic, um, how do you continue to load more on the potential applications of Bulletproofs and how they relate to things like, Zk Snarks and Zk Starks. So, in addition to Monero implementing Bulletproofs, I know maybe one of the, least one of the other projects that it is, working on integrating Bulletproof, is working with Bootle, which is one of the Bulletproof authors is PIVX, they are, like are you familiar with how they're trying to use Bulletproofs, how it's similar or different to Monero and why they're considering using a Bulletproof instead of a Zk Snark, because they sort of have a trusted setup already with the RSA set up there…………..

Speaker 2 (Sarang Noether): 40:34
Yeah, so PIVX, So the way that PIVX works, PIVX was originally based on one of the zerocoin protocols, and zero coin was kind of one of the spiritual predecessors to zero cash, which is what Zcash was originally based on, so it's this whole big timeline. And zero coin is kind of the first, I would call like, zero knowledge asset for example. I'm going to use cryptographic commitments to show that, you know, it’s the center of a transaction came from somebody previous transaction without giving you any information.

So in theory, its anonymity settles better than what we use, which is a ring signature. And there’s other limitations involving like, a fixed denomination and so on. And it also had a trusted setup, so that this cryptographic accumulator that it used to show that a commitment to a particular, you know previous asset was contained in some bigger set, it's called an accumulator that use the trusted setup. The trusted setup they used was not one that came up with themselves, they didn't do any kind of ceremony like Zcash did, they use a fixed RSA number or just part of an RSA……………. there's, I don’t what the company's called the RSA Incorporated or something.

They had this big competition involving factoring, they released these big composite numbers and challenged you to factor them into their prime, in their prime factors. They pick one of the big ones that no one's been able to break yet publicly and said, this is our, kind of big secret that we're going to use. They don't even know how to break it. As far as we know, no one does, we think. And their accumulator technology is based on the fact that, you know what RSA number. They could have come up with one on their own but they didn't want to do that, you know, I think it's a, it's a reasonable approach, it's pretty good.

And so they use that right now. Their prover is still pretty slow, as far as I know, based on the original technology, and they wanted to kind of move away from the trusted setup and, you know, make this thing a bit snappier. So they're not, I would say, not quite as flexible as with Zcash doing, there's a reason Zcah doesn't use the zero point protocol, there is a bunch of limitations to it. But PIVX to my knowledge, and I have not been updated in awhile on this, but I spoke to at least one person who works in their team, who said that their goal is to remove the trusted set up by using a type of accumulator to accomplish the same thing that they were doing before, which involves, you know, proven that your input came from a previous transaction in a valid way without specifying what that transaction was for example.

They want to do that accumulator setup in a way that doesn't involve a trusted setup. And so to do that can be kind of tough. So they're trying to find one that is both efficient and can be done in zero knowledge with Bulletproofs. Like I said, Bulletproofs can be used to prove particular kinds of statements with moderate efficiency, but you might have to be careful with it. I don't know what system they're using for that. They said that they've been working with some, you know, you know, pretty high caliber cryptographers on this, I would really like to know what they're doing. They've said that they plan to publish once they get this thing working but they're kind of holding it close to the chest right now.

So apparently, they want to do a zero knowledge proof system involving in particular kind of cryptographic accumulator that, I don't know what kind it is, as far as I know, it's a new kind of accumulator if they can integrate with Bulletproofs to do in zero knowledge.

Speaker 1 (Justin): 43:38
Okay. So they're not replacing the entirety of their system with Bulletproofs, Bulletproofs are just a component that would allow for them to switch…………..

Speaker 2 (Sarang Noether): 43:47
This would involve a pretty significant overhaul of the way they do things. And who knows, I mean, there are other limitations that are in place with the original zero coin protocol, that involved things like fixed denominations. I don't know if they have move passed or intend to pass that to a more general system that involves arbitrary amounts. To be honest, I haven't really been following it very carefully. I read the cryptographic literature and I'm really eager to find out what this accumulator system is that they're working on, because it sounds really fascinating.

But I think it's an example of the fact that people are doing research into ways to use these kind of proven systems, but you have to use them for a specific purpose. People sometimes think like, oh! Man, you can turn your asset into a zero knowledge asset. But really, what you have to think about is, what statements am I trying to prove in zero knowledge that say what I want to say about my transactions? That might involve, for example statements about accumulators that show where outputs used to exist and if they're valid or not, or in our case, we use them to show things about Range Proofs, you know, we have other kinds of proving systems that are used for things like ring signatures but in a more limited way. If anyone knows what PIVX is doing, I am super interested to know because like that kind of math sounds fascinating to me. They say they're going to release it; I look forward to reading it. Until then, like I have no thoughts on it because I don't know what they are doing.

Speaker 1 (Justin): 45:05
Okay, I wasn't sure if you were…………

Speaker 2 (Sarang Noether): 45:06
No, like what do I think about it? It's like, I don't think about it because I don’t know what they are doing. I have no reason to believe that they are not being genuine about it because they're working with some really high caliber people who do know what they're doing. Yeah! Including Boodle who was very well respected in this field and did work on Bulletproofs, among other things as well.

Speaker 1 (Justin): 45:30
Okay, so what other sort of applications do you think, like are Bulletproofs generally good for more, like public sort of blockchain implementations where you don't need the present setup and for business applications, you'll just generally see that people use Starks more often or Snarks more…………… I’m sorry, Snarks more often, or do you think that's not a fair general comparison?

Speaker 2 (Sarang Noether): 45:54
That I think is a much deeper question. You know, I, if I were cynical about it, I would say like if you're working within a single business and you have one trusted entity, you almost certainly don't need a blockchain to begin with.

Speaker 1 (Justin): 46:06
Well, yeah, yeah. Yeah!

Speaker 2 (Sarang Noether): 46:08
So I’m always kind of a pessimist about that, when everything's like, oh! Man, we're going to take this business thing that we have and put it on a blockchain. And the first question you ask is, you know, is there any single entity that everyone can trust to manage the data correctly? And if the answer is yes, then we don't need the blockchain. But there are certainly private blockchains, there are other applications where you might have parties who don't necessarily trust each other mutually, like supply chain and stuff. And I'm sure a ton of other things that I'm not even thinking of.

But that's a good point though, because a lot of this comes down to your trust profile. So in the case of like, a public distributed asset like Monero, where I think kind of the ethos tends to be, you shouldn't have to trust anyone to have done something correctly, besides, you know, the underlying crypto and the code that anyone can verify if they really, really wanted to know what they were doing. So in our case, something like Snarks or other kinds of proving systems that require a trusted setup, it's just a non starter. If there were a better way to do it without a trusted setup and we got the same kinds of efficiency, that would be fantastic.

I have no doubt that we would, you know, work our asses off to try to get that into play. Other business models, like, you know, what Zcash is doing for example, is you know, they kind of started out with the assumption and they’re very open about this, that, you know, you have to trust that we did this right. And if we didn't do it right, then, you know, if we were all compromised in the case of the original ceremony, and if everyone including the, you know, big open group of people were compromised in the second ceremony……….. they're very open about the fact that if those things were compromised, then very bad things can happen to  Zcash, where you could have kind of arbitrary inflation.

And some people have suggested that there might be a denomilization but I haven't had that verified yet. But they're very open about that. And like, that's the level of trust that their users are putting into them and it's up to you. If you decide that that's okay, then you are free to do that. And if you decide you're not okay with that, you are free not to do that. In the case of business where you may have the desire to do independent verification of statements in zero knowledge, but you maybe have enough trust in whatever entity did the trusted setup. Then yeah! Something that's much more efficient like Zk Snarks or whatever is going to be coming later, or whatever is being worked on now. That may make a lot of sense for that application and I could totally see that, and frankly that's reasonable. It all depends on your trust on this profile.

If you have something where you are not willing to accept a single trusted entity to do some kind of setup like that, then you need something that is trust us. And right now we do not have anything that is as efficient as those involving trusted setups. Zk Snarks the way the implementations that are being used right now, elsewhere as far as I know, all rely on a trusted setup, generating a bunch of stuff with a bunch of algebraic structure and that's what gives it its efficiency but it's complicated. But in a trusted setup, you have consequences. Right now those consequences are efficiency limits, size is pretty good, proving times not great, verifying time doesn't scale very well at all.

Speaker 1 (Justin): 49:04
Do you think that these are two things that are at odds with each other, where you'll have a level of trust versus efficiency? Or do you think that's……….

Speaker 2 (Sarang Noether): 49:12
I thought about that a lot. I don't think anyone has done any formalization of whether or not that's required or not. I suspect that no one has done any verifi……… any anything on that. I don't know, I kind of waffled back and forth between, this is probably some theoretical limit of the universe back to know it probably isn't, we just not quite clever enough to figure out how to do it yet. There's a way to be proven wrong, which is if someone does it and it's correct, then we're wrong and it turns out, you can do it and that isn't a limitation of the universe in mathematics. But no one's done it yet but it does not mean that people aren't trying, there's a lot of interesting work going into it.

Speaker 1 (Justin): 49:50
So do you have any other comments on other applications of Bulletproofs and how it relates to other proving systems?

Speaker 2 (Sarang Noether): 49:57
Yeah, so we, we've been thinking a lot since proofs came out about, you know, different ways that we might be able to do implementations that involve them, and different ways you could kind of integrate those with accumulator setups. Obviously, people are working on things like accumulator based setups that involve those. I think that's fantastic. There are a couple of different………… we've been looking at, kind of so, but there's the idea that eventually someday, maybe we can move past ring signatures altogether, which we know have a bunch of limitations.

I know you don't like ring signatures, I don't like ring signatures either, they’re the best we have right now. But we know that we have to do a lot of work to make sure that, you know, that we use them correctly. And, you know, we're confident that we do the best job that we can and that we update when we're not doing the best job we can. But there's the idea that someday we'll move past those and it’ll be some beautiful zero knowledge land where everything is efficient, and small and trustless. But you know, we're not there yet and so we're going to keep working to get there. But we also are working on other things that involve ring signatures; in particular there are benefits to using larger ring sizes.

There's ways that that interacts with things like churn behavior, or just using the larger ring sizes to kind of diffuse your outputs and things like that, where, you know, in general, for the most part, bigger is better. Of course, ring signatures don't scale well because as the brain gets bigger, the amount of time it takes to verify a ring signature increases as the size increases, and it's a whole other size scaling thing. And there's some proposals out there for how to make ring signature smaller, and hopefully maybe at least a little bit faster, or at least no slower than we have right now.

And in particular, some of those schemes also involve Range Proofs. So we already have an idea where there's, there's one scheme we've been looking at, it's not public yet, that another group presented to us. That has a proposal to do a sub-linear or smaller sized, large ring signature, that kind of has an integrated Range Proof already built in, but you can also kind of rip that integrated Range Proof out and just throw a Bulletproof in. So Bulletproofs might be able to work with other schemes like that as well.

Basically if you come up with a statement that you want to prove in zero knowledge that has particular properties that you like, and if you can express it in arithmetic circuit that's not to giant, then yeah! Bulletproofs might make sense. You have to have a purpose for it, you know, we don't have a definite, you know, purpose in mind for it, for which we know that it could scale really well, besides Range Proofs which we are already doing, which worked great.

And by the way, they're looking great. Oh! Man I cannot wait to see like the blockchain growth rates because we have the original slow growth rate, pre-ring CT, then we did the confidential stuff and they just blossomed and skyrocketed, and now we switched over again and I look forward to them shrinking back to that again. I haven't seen any charts like that but if you just look at like the chain explorers, the kind of type that I watch from time to time if I want to feel good about myself, they’re pretty small.

Speaker 1 (Justin): 52:45
Just wait for our research papers to come out in the future though and say, well Monero started at zero and now is here, so the growth rate must be this linear line. So Monero’s going to keep growing at a significant rate…………..

Speaker 2 (Sarang Noether): 53:00
(Incomprehensible: 53:00) like the growth rate still going to be linear because transactions take up space but it's the rate. It's also we're saying because sometimes we get asked this, like can you take Bulletproofs and like retroactively do stuff with it? It turns out the answer is no. you can't. The only person that can generate a Range Proof for a transaction is the entity that created the transaction originally, so the old Range Proofs are here to stay. Once you’ve synchronized the blockchain, you can technically prune those off, you can get rid of those Range Proofs on your own because you know everything's good.

But if everyone does that then, you know there's arguments about whether or not it's a good idea to keep those around for like trusted archival purposes, to make sure that you know that nothing bad was done. There's already ways you can technically prune it off but you can't just replace the old stuff with Bulletproofs, so. Do we wish that we could have deployed them earlier? Sure that would have been great but you know, they were still on active development, we wanted to get them audited which we did, all the audit reports are out now by the way, the Quarkslab audit we withheld because it had another denial of service bug in it, that's been out now, so you can take a look at that.

Speaker 1 (Justin): 54:05
So how about we can switch, since you brought up audits, I wanted to discuss……..

Speaker 2 (Sarang Noether): 54:09
I did bring up audits……………

Speaker 1 (Justin): 34:10
But now's a great time because you brought it up. So can you walk us through the audit process because you were the one who helped really organized a lot of the audits for the Bulletproof process. So how did you speak with organizations and entities in terms of getting these audits in place? How did you select the proper ones? What did you do when you received these audits in order to improve Monero’s code? Maybe the whole process with the audits for the Bulletproofs, like even why did we want to do audits for the Bulletproofs?

Speaker 2 (Sarang Noether): 54:41
So the reason why to audit it is because this is new maths, like the algebra itself is not new but this particular construction and the way that it was done is new. So I hadn't really been, hadn't had kind of the test of time that often we want to see in cryptography but at the same time you know, mathematicians read this net is good. So really it comes down to, is your implementation done correctly? The implementation of the existing Range Proofs is actually really, really straightforward because they're not clever, they're just, the old Range Proofs are straightforward but they're big. Bulletproofs are clever, and clever is sometimes, you know subject to being bad, clever is not always like a compliment, sometimes clever is not a compliment.

So we decided want to get them audited and for that reason wait until one of the next fork. So Spring fork 2018, it kind of been like an initial like, wouldn't it be cool if we could do it by this time. Um, but it turns out they weren't ready yet, so we decided to push until this one. We did mean that we suffered like the addition of a bunch of extra transaction space on the blockchain but you know, it's kind of the price you pay for doing it as right as possible. So we decided to get audited, we talked to the open source technology improvement fund (OSTIF) and that is a now nonprofit organization, they are, it’s actually a registered charity (Inaudible: 55:59) United States and they do a lot of things trying to make open source code better and safer.

And they agreed to help us out by kind of soliciting proposals from some auditors that they knew were trustworthy. And we also reached out individually to some individuals that we wanted to do particular audits as well. So one of the people that we reached out to directly was Benedikt Bunz who is one of the, he was actually the lead author on the Bulletproofs paper. So he’s probably single entity who knows the most about Bulletproofs in the world, because they were his baby among all the other co-authors they worked with. So we got Benedikt Bunz on board to do a review, to make sure that our, the way that we had prototype Bulletproofs was done correctly. And then also to put us into contact with a few different organizations, one of whom was not comfortable being mentioned publicly. So we decided not to go with them because want to do this publicly.

So they recommended a few additional groups, we kind of put up the notice and a summary of what they intended to do, and we let the community kind of give their input, and we eventually decided to go with two additional auditors, Kudelski security and Quarkslab, both of which had a lot of experience in doing reviews and audits, things like that. And you can read their, their statements of work are up on our research repos, so they're public, and anyone can read them. And their goal is to determine if the implementation that we have, matched what we expected to have and whether or not there were any bugs involved. And whether or not those bugs could lead to exploits. I would like to say a bug is not an exploit, so it’s important to differentiate. Bugs can lead to exploits and just because you can't find an exploit based on a bug doesn't mean there isn't one there.

But they're not the same thing, just because you call it a bug does not mean it's exploitable. In our case exploit would mean, you know, can I generate a proof that leads a verifier to think that the proof is correct but really, it's a false proof. That would not be good, things like that. And we don't want the verifiers to be able to generate any information from the proof about what the original commitment amount was. So we don't want people to be able to deconstruct the Range Proof to determine what went into it. That would violate, like the zero knowledge properties and such. So we went and had the audits done and they took a while but they did a good job. And Kudelski and Quarkslab both came back with some fixes they recommended. Some of the fixes were recommended to the initial prototyping code.

That code was never intended for direct production, so like the underlying libraries weren’t assumed to be secure or anything, so we consider those not to be a big deal. Those are basically for algorithmic purposes, not for implementation purposes. And they also found some things that we could shore up in the Bulletproofs code itself. Couple of kind of little edge case bugs and it's worth noting, as far as we know, they didn't, wouldn't have yielded any direct exploits that we know of. But again, that code wasn't live yet. So the reason we have the audits done was to determine if there's anything we want to shore up before it was deployed. So none of the Bulletproofs stuff was deployed, we did integrate the fixes, and Quarkslab in particular, they went really above and beyond the initial scope, which is great. So they looked at some other things in the code base that they came across, that they recommended that we shore up and fix involving some other, some routines and other algorithms and things we were doing.

They found for example, a denial of service bug, which is why we withheld their report from release until just today in fact because wanted everyone to get updated prior to that, but all those fixes are in place now, they did a great job. I think that the audits were hugely valuable to the community, and then I think that that is something that we should consider going forward when we do deployments of kind of big new structures and things (Incomprehensible: 59:59:23). We have really talented people, but you know, anyone can generate something that they don't see a mistake in. But having outside folks come and look at it with fresh eyes is always a good idea. So those audits were great, they helped to shore up the code base and shore up Bulletproofs as well. And if anything, that's good, I think that will hopefully give other projects and groups confidence in Bulletproofs as a good technology. I know some projects as we were developing Bulletproofs kind of just worked up the code and implemented them themselves. I've seen some implementations of Bulletproofs that are old and both inefficient and probably need to get, you know, shored up a bit too.

So if you deployed before our audit was done, maybe you should have done that. Hopefully, those projects will take the changes we have because we're an open source project and, you know, implement them themselves. But I kind of, I think it's kind of cool that, to my knowledge, we were the first kind of major projects to deploy them live. And again, there are other implementations on the elliptic curve library that Bitcoin uses. One of the  Bulletproofs authors works on that as well. You know, they have an implementation technically, but you know, it's not being deployed in Bitcoin. And I know there's been some other efforts to do bitcoins implementing………….. it’s not Bitcoin, Bulletproofs implementations for other curves and in different libraries too. You, my friend are muted.

Speaker 1 (Justin): 1:00:50
You are right, my bad. Okay! So are there any other areas where you would really like to see audits of Monero’s code?

Speaker 2 (Sarang Noether): 1:00:59
In a perfect world, the whole code base would get audited.

Speaker 1 (Justin): 1:01:02
Exactly!

Speaker 2 (Sarang Noether): 1:01:02
The whole code base is giant, so that audit would take years and a bazillion dollars and by the time it was done, we would have upgraded so much stuff because, you know, we move deliberately, but we move………… we move carefully but we move have delivered. So we definitely move things forward. So I think that a great place to start would be to kind of limit the scope to what we think is going to be the most beneficial. So I'm kind of the Ring CT code is, for the most part kind of neatly segmented away in the code base. You know, there's a lot of other stuff that it integrates with, but kind of the base stuff and that involves ring signatures, and the way that integrates to confidential transactions, that's kind of its own large but kind of fairly segmented area of the code base.

I think that's kind of the natural place to do an audit, you know, we were, we were the ones who kind of started doing Ring CT, that is integrating this whole hidden amount thing, the confidential transaction side with the ring signature stuff to make sure that it plays nicely. So the math behind that is also good but, you know, it's always a good idea to see if there's any kind of small little edge cases or just bugs that, again even if they don't meet exploits, we don't want to see bugs, we want to make sure that the code is as clean, fast, well written, well executed as possible. Beyond that, you know some of our underlying crypto libraries, they come from trusted sources, and we try to use a well established cryptographic primitives, whenever possible.

Getting that stuff audited, that would probably be a good idea too. The Ring CT stuff perhaps we should see an audit first but you know, I could have my mind changed about that. It's worth noting though, you know audits, they're not cheap. You know, with the audits that we did, you know, they were, you know, on the order of several 10s of thousands of dollars, U.S. So, you know, in a in a bullish market, when everyone is flush with Monero it's often easy to get donations for stuff like that. And everyone wanted to see Bulletproofs which again, I still think the fact that it was expensive, it was still a great investment. Audits cost money, like no one's going to do it for free and if they do I want to know who they are.

So it's a good investment but it's still a lot of money. And you know, the markets fluctuate a lot and in the bearish markets, maybe people are not quite as willing to open up their wallets electronically speaking but, you know, who knows, you know we can always, we can always try to see if there's interest in doing that and get it done.

Speaker 1 (Justin): 1:03:20
Awesome! So I just want to give people one more reminder, make sure you ask questions in the chat. This conversation is meant to be more focused on Bulletproof specifically, I'm sure that, I could sense that Sarang and I we’re getting towards the edge of ring signatures, at least at some point during a lot of these conversations and I'm sure…………

Speaker 2 (Sarang Noether): 1:03:37
The stuff all integrates, it's all one big cryptographic family.

Speaker 1 (Justin): 1:03:41
Yeah! I'm sure that we should need to schedule a ring signature specific one in the future to really just express grievance really more than anything else.

Speaker 2 (Sarang Noether): 1:03:51
To make it clear ring signatures are not broken. They're just kind of a pain in the ass.

Speaker 1 (Justin): 1:03:55
Yeah! So…………..

Speaker 1 (Justin): 1:03:56
They are doing a good job with (Inaudible: 1:03:57) they are a pain in the ass.

Speaker 1 (Justin): 1:03:59
So just a last few sets of questions related to Bulletproofs. I'm going to go through one last time and see if we missed any major topics, there were some questions about Bulletproofs but I think we…………. sorry the audits but I believe we generally answer those. Is there anything else………….

Speaker 2 (Sarang Noether): 1:04:16
Yeah! And I should say too, you know pretty much all of the entire audit process we tried to ensure that it was open and transparent as possible. You know, on the research repos, you can look at the initial kind of statements of work that we got in, you know, you can look at the final reports that have all the details in there. Anyone is welcome to look at those, review them, we think the fascinating and you can see where in the code base the fixes correspond to. Whatever your level of interest is with that, you know, we tried to be as open as possible with all of it, so. Oh! The community, the community paid for it, you know those, that knowledge belongs to the community.

Speaker 1 (Justin): 1:04:51
So, I guess one question. We know that, like if Monero was ever exploited, perhaps there's a flaw in either the Bulletproof code or a similar Ring CT code that allow people to generate more money than expected in the formation of their transaction. Um, and I know you don't know for every specific case, would depend on the exploit but what's the general process for testing like, once you find an exploit to see if it actually was exploited like you did the last year, earlier this year with one of the Monero Ring CT flaws?

Speaker 2 (Sarang Noether): 1:05:31
Yeah! So the problem is, it really, really depends on the nature of the exploit, right? You know, for example, like for some stuff, even with our Range Proofs right now, if someone were to find a way to do Range Proofs incorrectly, that might be very, very difficult to detect. You could still show transactions balancing, you know, the developers don't know how to disassemble a Range Proof to figure out what went into it, that's the whole point.

So really, for some of that stuff, you know, the best that you do is ensure that the math is done correctly, and that the code is executed correctly. And that's the purpose of doing audits and of having as many eyes as possible on the initial algorithms, which is what we do, so. But other things that are possible in tests that for example was, the key image bug that was exploited a while back in other assets, that was not exploited in Monero. And in that case, we, we knew what the exploit looked like and we did a full sweep of the chain to determine that it wasn't exploited, that had to do with the way the key images were constructed relative to the way that we do elliptic curves. So it really is dependent on what the problem might be.

Speaker 1 (Justin): 1:06:35
Okay.

Speaker 2 (Sarang Noether): 1:06:35
To our knowledge, like a major exploit like that has never been exploited, we get bug reports from time to time. You know, some of them are exploits like that, other ones are things we could be doing better. Like the way we choose decoys and ring signatures for example, that's changed over time, nothing's exploitable but we try to home things when we get reports of ways we do things better.

Speaker 1 (Justin): 1:07:00
Okay! There is a mostly unrelated question that came in, but it said, why did Monero previously use a lower ring sizes in its early days?

Speaker 1 (Justin): 1:07:10
So, I mean a few reasons, right? So initially, I guess, the full impact of, so the full impact I think of what could be, trying to think of a good way to say this, I think, like the full impact of what you could do with ring analysis wasn't as well appreciated. So, you know, we have several layers the way we obfuscate things, right? Recipients are fully obfuscated using the stealth addresses, amounts now are fully obfuscated, they didn't used to be, so there wasn't really a part of the truck model. But also initially, you know, inputs to a transaction where obscured by ring signatures. And it's important to note, even if somehow you figure out who the true sender is in a ring signature, which to our knowledge, there is no way to do that.

If you even figure out how to do that, that does not reveal the address of the center, your address never goes on the blockchain. The only thing that goes on the blockchain are these one-time stealthy addresses that you come up with, these one-time addresses, that's it. I think initially, no one really appreciated the nature of ring analysis. I think it was kind of do or………… I think more or less, it was generally assumed that the fact that you had stealth addresses meant that, you know, the nature of determining the DLP station of that wasn't as important. You know, I mean, now we just kind of assume that because of interaction with KYZ’s, AML exchanges and just our desire to do things right, you know, by our users, which is, if there's any way to do any kind of transaction at the denomization whatsoever. Any level we should avoid it.

I think based on that and based on some new math that we did, which we didn't really have people working on before, we didn't really appreciate that with small ring sizes. It's worth noting that, you know doing the ring size increases that we have done has removed a lot of the issues. The probably the biggest problem before was that, not that you had small ring sizes but that you could do a zero ring or a one ring, a ring was zero mix-ins where it wasn't really a ring signature, it was, here's the inputs, which one was spent, well, it was the one that went into the ring.

Speaker 1 (Justin): 1:09:07
Exactly!

Speaker 2 (Sarang Noether): 1:09:07
And there's a cascading effect that we've known about for a long time. One of the initial MRL papers is about this cascade attack on cold chain reaction. That dies off pretty fast. So you stop allowing, which means you have to have a ring size of two. That's pretty good. Chain reactions die away pretty fast, as the rings get bigger. If you look at papers that come out, they seem to claim that chain reaction is this brand new thing no one knew about, but we've known about it other for a long time. It's not a big deal anymore, not in transactions…………..

Speaker 1 (Justin): 1:09:35
Okay! I think we're back. Okay, we’re back.

Speaker 2 (Sarang Noether): 1:09:39
Okay, cool. Yes, so chain reaction was something. There's other ways that people try to do chain analysis, one of the way they do is to look at groups of rings together at the same time. Looking at groups of rings together and you can do this kind of subset analysis and people have published different special cases of this, under different names but it turns out, there's a very clean definition of it, you can do involving set during graphs, which says that you can eventually sometimes, determine which outputs of rings must be spent.

And if an output must be spent, you know that it is a fake it if it’s used somewhere else. So that is used as kind of like to contribute to a reduction in ring size, but it doesn't necessarily identify what was spent in what transaction. You can do attacks like that, those do yield a lot of older outputs, which involves smaller rings, but that dies off really fast as rings get larger. So that is also like, we've done analysis on it, as far as we know, it's basically nonexistent. There's forms of it that may work in really limited cases but for the most part, it's completely irrelevant right now.

So we appreciate and understand a lot better the way someone might try to analyze the blockchain and just people have come up with more clever ways to do it. And so to counter that, the solution is to increase ring size. And, but a lot of that came from that original choice to allow, you know zero mix-ins which, like in hindsight is a bad idea.

Speaker 1 (Justin):1:11:01
Yeah! So……….

Speaker 2 (Sarang Noether): 1:11:02
We had we had the idea to do a real form of optional transparency but that was, that affected other people's privacy and it’s  not good.

Speaker 1 (Justin): 1:11:10
Yeah, the key is a much superior way to do that.

Speaker 2 (Sarang Noether): 1:11:13
Yeah? And I should say like, we have done a lot of work into ring analysis. And, you know, to our knowledge the way we're doing it now is very good, and very robust against those kinds of attacks.

Speaker 1 (Justin): 1:11:23
So one last question that came in related to the transaction amount, with Monero the transaction fee is visible because miners need to know what………… First of all, you don't know who to give it to you, right? Which miners get us off the block and also miners need to select transactions with the highest fee per amount ratio or per verification time ratio or whatever similar ratio it would be.

Speaker 2 (Sarang Noether): 1:11:44
Yeah!

Speaker 1 (Justin): 1:11:45
So, one of the users sent in a question regarding what are the possible tax related to this amount still being visible? Is it a major concern or is it um…………….

Speaker 2 (Sarang Noether): 1:11:56
Well, so it could, in theory it could. So if you can set these to whatever amount you want, if you as an individual for some reason pick some bizarre amount, then that identifies your transactions, right? I don't know why you do that. But if you chose to do it, kind of like the ring size argument where it's like, oh! Man, I always use the ring size of 69. I think it's funny, you know, is the privacy good, I suppose for some attacks, but then if someone sees like a 69 and they're like, Oh! It’s the 69 ring guy. And maybe you don't do that.

So one of the reason that we go to fixed mandatory ring size is because transactions should not stand out. And a ring size of 11 for a lot of ring analysis attacks is fantastically good, there's no real risks associated with that. Fees got the same way. And we have talked a lot about that internally, about whether or not allowing arbitrary fees is a good idea for that reason. And part of it is so it could identify individuals, it can also be used to do fingerprinting of different wallet software, which fingerprinting is bad thing.

If your software happens to pick certain values and other person people software types do not do that or do it in a way and that can fingerprint your software, not good. You know it's, that's a form of denominization I guess, but we really don't support. There have been ideas floating around to do kind of fixed fee and fixed fee multipliers, so we're working on ideas on how to do that in a way that is both safe and robust and, you know, it's going to work well for the ecosystem. But it's a very good point, you know, we try to, like, look at every possible avenue into denomalization, even if it's partially denominization of fingerprinting and, you know, that's, that's one method as well.

I would say that's probably on par with the idea of being able to choose our mature ring sizes and in the grand scheme of things it’s probably not the thing you have to worry about but, you know, in general, like choosing reasonable fees, you know based on defaults is a good idea.

Speaker 1 (Justin): 13:44
Yeah!

Speaker 2 (Sarang Noether): 13:44
But it's, it's, it's a good point, and it's one that we're definitely considering too.

Speaker 1 (Justin): 1:13:49
Alright, so thank you, again, Sarang. Are there any other closing remarks related to Bulletproofs that you want to let the community know about, either if it’s a related development or something that people, some frustrating way that people are refer to Bulletproofs that's incorrect but…………. where you want to close them?

Speaker 2 (Sarang Noether): 1:14:08
The crypto meaning I would say, it's very clear (Incomprehensible: 1:14:12) as a technology focused person, though it’s not. I don’t know, I go around forever, I'm reporting of science and math and cryptography in general and there’s folks who do it really well and folks to do it really badly. You know, it's……………... It could be another entire hour of discussion. Like, oh! Man, zero knowledge proofs are brand new, Range Proofs are brand new

Speaker 1 (Justin): 1:14:37
They replace Ring C.T. Yeah!

Speaker 2 (Sarang Noether): 1:14:40
Oh! My god, there's like an article about, like some big bank I guess that, you know, had a way of doing zero knowledge Range Proofs. And all the articles are like, Oh! Man, it's the first zero knowledge Range Proof, like, what the hell are you talking about, (Incomprehensible: 1:14:52) do this for a long time. Not efficiently maybe but, I just, I didn’t even reading, so. I don’t know, I guess the motto of this is, you know, like this, this is why, this is why the Monero research lab exists, I guess, right? Is to, I think it's like, the big shiny example is, something new comes out in, you know, in applied cryptography, in kind of an academic setting.

We take it in, we look at it, we determine if it's correct, which it was. We determine if it makes sense for Monero, which it did. We determine if we can implement it properly, which we did. You know, we go through a whole process of doing it correctly and safely, which means getting it audited and doing review and being very careful about, deliberate about it. And then finally, it goes into the code base. And, you know, it's kind of a big triumph of what it means to work together as a community, right? So, like Monero……….I should point out that Monero research lab is funded through the forum funding system, which is used to fund a lot of different Monero projects, not just us.

I know that there's still open projects looking to be funded. So if you're looking for a way to give back to Monero and if, there's a lot of ways to do it, if money is one of them, like the forum funding system is a great way to support stuff. Like things like Bulletproof happened, because of community funding. If there weren't funding available, you know, the research lab could not do the work that it does in the way it does. So, I mean, please support Monero in any way you can, if you can do translations, that's great. If you do code review, that's great. If you can talk about it knowledgeably to other people, that's great. If you can support it financially. That's great, too.

Speaker 1 (Justin): 1:16:27
Awesome! Yeah, thank you Sarang. I think that…………………..

Speaker 2 (Sarang Noether): 1:16:29
I’m also, I'm also afraid that we may have set the bar really, really high with this one. Well, I feel like Oh! Man, what’d you guys do last year, we shrunk transactions by 80% and made them twice as fast. Like, what are you going to do this year? Like, God, I don't know.

Speaker 1 (Justin): 1:16:44
Like, next part, next protocol upgrade you're going to save 10% and everyone's just going to yawn. You're like, it was so hard to get that extra 10%.

Speaker 2 (Sarang Noether): 1:16:54
Yeah, this was a very long process but it was, it was a very long process that led to a very good result. And again, a lot of research does not result in new big, flashy, fancy things, you know, it's, researches in some, to some extent kind of a crapshoot. You get a lot of dead ends, but that's the way it works. Sometimes you get a gem and this was a gem, so. It was a great value for the community, you know keep supporting the project in any way you can and that's how it gets better. It works because of the community. So thanks to everyone who made Bulletproofs happen.

Speaker 1 (Justin): 1:17:24
Alright, thanks against Sarang, I'm sure that we'll be able to schedule one of these in the future if they were well received. I hope to continue talking about these things if there's a group of people to talk to and I hope you feel the same way

Speaker 2 (Sarang Noether): 1:17:37
Yeah!

Speaker 1 (Justin): 1:17:39
Alright, so thanks again everyone for tuning in. We hopefully answered your question, if not you can join us on Matter Most, there's a link on it to get to Monero.org websites, that will link to several resources where you can communicate with us and other people on the Monero ecosystem. And yeah! Take care; I'm going to enjoy the rest of this nice day in Minneapolis that's really warm. I hope it's nice where you are?

Speaker 2 (Sarang Noether): 1:18:07
It is very nice where I am.

Speaker 1 (Justin): 1:18:09
Sweet! So thanks again for tuning in and we'll see you next time.

Speaker 2 (Sarang Noether): 1:18:12
Alright, see you everybody. Thanks.

********************************THE END************************************