Sri Aravinda (Aravind) Krishnan Thyagarajan is a PhD student at University of Erlangen-Nuremberg, Germany under the supervision of Prof. Dominique Schroeder. I specialize in analyzing theoretical foundations and various problems pertaining to blockchain and cryptocurrencies namely, privacy, anonymity, scalability and other applications.

Omniring: Scaling Up Private Payments Without Trusted Setup
Sri Aravinda Krishnan Thyagarajan, University of Erlangen-Nuremberg
https://www.youtube.com/watch?v=tmxPHb8QNqE

MoneroTalk w/ Sri Aravinda Krishnan at MoneroKon 2019! youtu.be/afWFTS_UxhI

Abstract

Monero uses Ring Confidential Transactions (RingCT) for providing anonymity and confidentiality. Prior attempts of analyzing RingCT schemes are either informal, miss fundamental functionality, or introduce undesirable trusted setup assumptions. Moreover, the RingCT scheme currently used in Monero limits the anonymity set due to spend proof size growing linearly with the ring size. As a solution to these problems, we present the first complete and rigorous formalization of RingCT. We then propose a generic construction of RingCT and prove it secure in our formal security model. By instantiating our generic construction with efficient zeroknowledge proofs which extends Bulletproofs, we obtain Omniring: the first RingCT scheme which 1) does not require a trusted setup or pairings, 2) has a proof size logarithmic in ring size, and 3) allows to share the same ring between all source accounts in a transaction. Omniring enables significantly improved privacy levels without sacrificing performance.

Transcription

Good morning to everyone, welcome to my talk. First, it is a lot of pressure for me to start the conference with my talk. Let us see if I do a good job.

Thanks for the introduction, I will be talking about our paper Omniring. Our work mainly focuses on formalizing the functionality of ring confidential transactions the security guarantees, while giving an efficient construction that can be instantiated almost inmediately in the currency Monero.

Ring confidential transactions has three components, the first one is sender privacy, amount confidentiality, and receiver privacy. And this is what is currently used to achieve privacy and anonymity in monero today. Sender privacy is achieved by a primitive similar to linkable ring signature that gives you an anonymity and anonymity set and also giving the capability to detect double spending.

So a bit more of introduction, let me start with ring signatures. A verifier can verify a signature on a document that has been signed on behalf of a anonymity set. In this case, the red user knows that one of this three users has sign the document but not necessarily who sign it.

Moving -- Jumping from ring signatures to linkable ring signatures the verifier can link two signatures if the same signer had sign from the anonymity set. This analogously gives the detection for double spending attacks in case of Monero. Alright, so, the next component is amount confidentiality which is achieved through pedersen commitments, confidential transactions. Which hides the amount inside a commitment while giving the capability to verify if the amounts are balanced or not. To look at it in a more fine detail, the green user here puts the amount 23 inside a commitment, right, and sends this commitment to the red user here. Of course the adversary does not know what is inside the commitment, as of yet, he does not know ever. Then the key, the openining information for this commitment is passed on to the red user who can now open the commitment and verify if-- check what amount was inside. The adversary can or any external user can verify if the amounts in this commitments that the green user had which was passed to the red user are indeed balanced. That is the only information that is known to the external user.

The third component is the receiver privacy which is achieved through what is called stealth addresses. Let me directly jump into the detail of what stealth addresses is. So, here, the blue user who wants to receive money sends his long term address, which is the master public key to other users from whom he wants to receive money. The red user signs some money and send it to a user, no one knows who he is, and happens again, and happens again. But the point is all these three recipients addresses have indeed been derived from this master public key that the blue user had given. But the adversary doesn’t know this, the adversary can not - obviously doesn’t know - that all this fresh looking recipients are indeed belonging to the same user. Ok, so in this way the recipients addresses are unlinkable from each other.

So what are the security properties of RingCT? First is balance, where the amount that a person has is what he spends and nothing more. And obviously he should not do a double spend. Then you had privacy, where you have privacy for the sender, privacy for the receiver, and the amount that is being transacted is also hidden.

And the third property is non-slanderability, which says, “an adversary cannot sign a valid document on behalf of an honest user”. Which, also you can think of as unforgeability of a digital signature. Why do we need to formalize the functionalities and the security guarantees? Because it gives you a concret platform to design your protocols, to understand what the security guarantees of a protocol are. And once you have formalized the security notions then you have multiple protocols you can compare them on the basis of their efficiency, and so one and so forth. And not necessarily worry about, “oh one protocol gives me this guarantee, the other protocol gives me the other guarantee”, this is a tradeoff. You won’t have to worry about that anymore. It gives a guideline to comparison of different protocols.

Naturally if you end up not formalizing, there can be problems at times, in one of our papers we found a deniable of spending attack (on the zerocoin model). Where the adversary could essentially create a transaction and use the tag of an honest user, and spend the transaction which is valid, right. Now, if the adversary ends up doing this, the honest user, whenever it comes online, or whenever he tries to spend his transaction with the same tag, it always ends up being a double spend because users can link this tags and they know that this tags has already spent the money. So essentially, the adversary has forced the honest user to not spend this money. And we found that this bug actually existed in a lot of coins out there, and it also was a bug in the formal model that was initially proposed in 2016, but not the scheme itself but the model of the security guarantee.

There have been two attempts at formalizing ringct. The first one was 2017, an effort to add RingCT 2.0. They failed to formalize stealth addresses, thereby not capturing the guarantee of receiver anonymity. And their definitions of security are a bit weak in the sense that they failed to capture many real world scenarios, and they end up using trusted setup in order gain better efficiency for the construction. The most recent attempt was the ringct 3.0. You can see the iterations and numbers. So the anonymity definition in this case is split between receiver anonymity and spender anonymity and it’s not clear if this two definitions together play in achieving privacy for the whole system. Their definition for balance is weak compared of what we give, in the sense that they either restrict the power of the adversary or they a little bit of a stronger assumption.

To summarize our contribution, we first of all give a strong model, in a sense we capture stealth addresses that are receiver anonymity. We also capture the viewability or trackability feature that is prevelant in monero today. We end up giving strong security guarantees for balance and privacy as a comprehensive privacy guarantee. And we have what is called, “the one ring to rule them all”, a lot of the ring reference, to achieve better efficiency and better anonymity. I’ll come back to this a little bit later. And we have less assumptions in the sense that we do not rely on any external security channels between users, we do everything on the ledger.

Let me jump right into the formalization of the functionality. Users obviously want to setup and want to join the network, so the user first runs a setup algorithm that generates the public parameters that are necessary for the RingCT scheme. Then they setup this stealth address, they need to setup this one time address, around the stealth address key generation algorithm that outputs this master public key and master secret key, which is done one time. A transaction basically in our formalization is a ring of accounts, the tags of the accounts that are spending money, and the target accounts, and some arbitrary message or meta data, new.

How do you spend? in order to spend, the user first needs to know what the target accounts are, where he wants to send the money to. He runs this one time account generation algorithm. He takes the master public key of the recipient and the amount that he wants to send to the recipient, that the algorithm outputs the coin key of the coin and the account of the target user. You can think of this coin key as the blinding factor or the randomness that goes into the commitment, of the coin. Then he,--Once the destination or the target account is setup, he knows where to send the money to. Then he runs the spend algorithm that takes example the ring of accounts and source account from where he spends the money, the target account where he sends the money to, and some message. And it outputs the signature or the spend proof that he publishes to the ledger.

Once the spend proof on the transaction are in the ledger, you need to verify if everything is fine so the verification algorithm checks if the amounts are balanced between the source accounts and the target accounts, and it checks if the tags do not reaccure in order to prevent double spending. It also makes a crucial check where the accounts that are used in the rings have at some point in time appeared as a target account. The user can not generate a fresh account out of thin air and include it in the ring. Moving on to receiving, the money has been sent to the receiver, now he needs to do something to make the funds that he received spendable again. So he runs the receiver algorithm that takes the master secret key of himself and the target account that specified in the transaction and the algorithm outputs the coin key that he needs to learn, the amount, the one time secret key, and the tag, right. With this information the funds become spendable for him when he wants to later spend whenever he wants. One aditional check that needs to be performed is that when a receiver receives funds from many different times he needs to ensure that the tag of everytime he receives are different, otherwise he receives money maybe twice to the same tag but he can only spend the tag once. That means he can only spend one of those and not both, he needs to ensure this.

So our RingCT construction has two steps, the first step we give a general construction where the spender whoever is spending takes a complicated language and throws it into a Signature of Knowledge (SoK) box that outputs the spend proof. I’ll come to Signature of Knowledge in the next step. The next step is to instantiate the signature of knowledge. We rely on the Bulletproof framework that was done by, Buns et al at 2018. Note that is already used in Monero to proof rangeproofs of the amounts, where the spender needs to prove that the amount that is hidden in the commitment is written in some range. He needs to do this, and Bulletproofs are already being used for this. Bulletproofs enable you to proof algebraic relations between integers but unfortunately they do not natively imply a ring signature or a RingCT. This is where we had to work a bit to extend this to RingCT. So we extend the Bulletproof framework to a Zero Knowledge proof system where you can proof relations on Discrete Logarithm (DLOG) representation and note that our proof can handle not only algebraic relations on integers but also on group elements. If it’s a bit to technical I will go fast.

Step 1, just a very high level key point of Generic Construction. We use a public key encryption system for giving the veiwability and trackability feature, thereby removing any assumption of security channels between users. And, “one ring to rule them all”, comes here now. We can have multiple spends meaning that spending from multiple accounts to be done from the same ring, and not necessarily have different rings for different spends. This gives us “k” out of “kn” anonymity where “k” is the number of accounts from where you want to spend, and “kn” is the size of the ring. And if one of the keys, if one of the spends of the accounts is de-anonymized you still have (k-1) out of (kn-1) anonymity. Let me show this pictorially. Since this is the first talk of the morning. Lets say that there are three accounts that are being spent from three rings, the arrows point down to who is actually spending. Let us say the first guy the blue guy gets de-anonymized, that means now that the whole ring is useless for the anonymity of the other two spenders. But now, let us say that you have one ring and you have multiple spenders, the three spenders here, and if one of them gets de-anonymized its just his key that’s not contributing to the anonymity to the rest to spend anymore, you still have a large ring for anonymity of the other two accounts. This is a feature of our Generic Construction.

Let me now move on to the Instantiating of our Omniring. The first time I think mentioning the Omniring . So we instantiate the public key encryptions scheme, the elliptic curve intergrated in from encryptions, scheme Shoup’01. We have Pedersen Commitments for Confidential Transactions. We have Pseudo Random Function (PRF) for the tag account and we instantiate the Signature of Knowledge we our extended variant of Bulletproofs, which I will briefly show now.

Bulletproof, how does it work? As I said they want to proof the rangeproof of an amount, they want to show this value lies between a certain range. What they do is they represent this value “a” in terms of a vector “a” and vector “b”, and commit to this vector in the form of this capital “A” over there in step number two. And they proof this complicated sofisticated relation to show that actually the amount lies in a particular range.

The key caveat for proving soundness of this proof is that the prover does not know any non-trivial Discrete LOG representation of the identity with respect to the base in which the commitment “A” is generated. In our case we want to have ring membership where there is ring of keys, and you want to prove the knowledge that at Portecle Index you know the Portecle Secret Key, for achieving ring signature of the RingCT. The challenge here is how encord this relation into this commitment “A” that I showed before. The more important challenge is actually that the prover, meaning that the spender however is spending, may know the Discrete Logarithm relations between different keys in the ring. This does not let us use the Bulletproof soundness proof as it is. So we need to do something slightly different, we do it. We do it, by commiting to this “a” with different base where the “g” vector before is now replaced by “gw” which ensures that the Discrete LOG relations between the members-- the keys of the ring are not known by the prover anymore. Then you have this commitment with respect to this new base, you run the Bulletproof system as before twice and you can extract the witness and the soundness proof goes through. Running Bulletproof twice could potencially incur some cost and we could get a little better optimization that are really straight forward. This means that you actually end up running the Bulletproof just once.

Fine, so step one and step two are done. Omniring, we do implement and we do have some optimization so we can leverage the batch verification technic that is also used in Bulletproofs. Unfortunately, the Monero Reasearch Lab have pointed out some errors in the numbers we presented and the reason for those errors are actually that our security proof does not allow us to leverage so much of improvement that we thought we could. But we are now working to fix this and hopefully we are actually the same as what we had before, hopefully. We could actually have the transaction size to be logarithmic in the size of the ring. I mean, of course the proof size happens to be logarithmic because we end up using Bulletproofs. And, the setup target account and the setup source accounts are usually small so that is also fine. Usually the entire ring needs to be send as part of the transaction, this could mean that the size of the transaction could be linear in the size of the ring that you are sending. But, we could actually use a logarithmic size description of the ring by using the technic of Chator and Green from 2018 called, “Recovery Sampling” technique. That means we can now have not just logarithmic size proofs but you can actually logarithmic size transactions.

Asymptoticaly, I mean I know is not so interesting but I will come to the concrete numbers just in a bit. So, asymptoticaly just to compare the various constructions so far we have had. the first one the Monero Bulletproof rangeproofs, that is used currently. The signature or the spendproof size is in the linear of the ring size, so, and then in 2.0 it is actually is not dependant on the ring size, anymore, but note that they do use pairing and a trusted setup to achieve such efficiency and they do have really high hidden constant factors in their construction. Ringct 3.0 achieves the proof size to be longer in the size of the ring, but they do not intergrate the rangeproof and the RingCT proof into a single system in which we do and thereby the multiplicated factor of the size of the source concept is actually inside the logarithmic expression for us, here.

What about concrete numbers? Proof size in term of the group elements in the current day use of the ring size of eleven our Omniring has something between twenty to thirty group elements, where the current day use in Monero is somewhere between thirty to forty. As you can see, as you increase the size of the ring the difference is really clear. If you want to have a ring size of one hundred and twenty eight our Omniring gives still around thirty where as the Monero-- currently Monero the size really blows up to seven hundred. That is proof size.

What about the amount of time spent on computing this proof size? In the current day use, Omniring takes a slightly bit more time than what Monero does, but not in a huge order. As you increase the ring size the difference slightly increases but not to a prohibited limit. Most importantly the verification time, note that this numbers are without the batch verification which we are still working on. The Omniring as you blow up the ring size (the amount of time taken to verify) is less than few tenths for us in terms of milliseconds. In Omniring where as it gradually blows up in Monero, you can see the difference here. And, hopefully, with batch numbers we will have better verifications.

Can you use Omniring in Monero today? I hope someone is thinking about this. If you are, yes you can. We need to modify the language that we are prooving to be compatible with the tag that is currently used in Monero, so once you start using Omniring is also backward compatible with what was running in Monero till today. So you can prevent double spendings all together. If you modify this language note that we still maintain this efficiency that I presented in terms of asymptotic and also concrete efficiency that I just showed you. We can still read in this.

And, to kind of conclude my talk. It is very important to formulate the functionality`and the security guarantees when you develop a system. Specially as crucial and monetary significance that Monero holds in the current world. And the ring selection of the RingCT where you select which keys go into your ring, that is very crucial, very important, and we are actually actively working on it. You can soon expect paper to be out. Our generally construction that I showed, which I briefly touched upon, is compatible with any future cryptographic improvements that may come forward. In terms of proof systems are anything, so, it is future proof. On Omniring where you have one ring for many spents, actually ensures that you can actually use large rings. That means better anonymity and better privacy for the spending keys that you have in Monero. Which means better privacy in Monero. Alright...

That is it, thank you for listening. Please checkout our paper it is a new print, 580, that is our code. And, questions please...