Bulletproof Protocol for Set/Not-Set Membership Proofs: Security and Implementation Considerations

Transcript

Hello can hear me hello everyone senior software engineer from Concordium and what we have like wallets walls hold real identities like think about your passport for example and wallets can generate cs about things and we have verifes for that and I want to show you something that we have implemented to generate these proofs so in particular we use bullet proofs for doing set and nonember set membership and nonmembership proofs And first of all whenever I talk about example I want to that you look at the right thing will be like think about your passport in in your cryptallet that will be our example for the talk and to go back to the topic there were like two

things so I want to like break break it down we have like bullet proofs I will talk a little bit of background about that and set membership and nonmembership proofs what that means. So first of all you have maybe heard about the bulletproof protocol there like a research paper few years old and they have an example given for range proofs and that's what most people use it for range proof means you have a lower limit and upper limit and you prove that your secret value is in this range so usually the most basic example would be like proof that older than 18 years old without revealing that your date of birth I want to show you something new because that would be boring if I just repeat the research paper I want to show you how to use like a nonmembership roof or like a set

membership roof or nonmembership roof and how to transform it so we can put it into a bulletproof protocol and proof it with that. So what is our nonmembership or membership proof? It's like you have a public value v and element s and like negation would be like you that v is not s butity i want to actually show you that what is a knowledge set membership proof and what it means is that like your value v is actually a secret set is still a public kind of value like everybody knows the proof the verify knows so think about it like you want to prove European cizening country. In that case you know the

European Union which countries are in that set but you don't know like you don't want to reveal your actual country where it is from. Also I want to first before start kind of give you an overview that like no no protocol is useful for everything. So there some specific areas where I would recommend to use bulletproof protocols and look usually at the kind of cardinality of your set like how big is it? If it's very small then I recommend to use some some basic protocols like sigma protocols for example and use kind of repeat them on like a few small kind of values that you want to test and use an or adapter to kind of link these different proofs together. If you very large threats on the other hand of

course you don't get around to like implement some kind of trees. So like there something what our cryptographers recommend. It's like the curve trees that is a research paper. I'm not sure if already it's implemented. Something you can use or like if you want to use something more in production already. of incremental trees that kind of tornado cash using like nules if you need to prove something nonmembership then you probably use something like sparle trees some kind of implementation also how to do knowledge but for our kind of case we are kind of in the middle middle spot that means we have kind of a few already countries like maximum 200 countries but is like not huge and that area like bulletof protocols quite efficient

Okay. Next kind of slides will contin number set of numbers every kind of ex country code by some kind of numbers and also like two math notation I want to repeat so don't know how far your math lessons is back. So these two mass notation are related to like vectors. You have two vectors in the midle here like H product kind of circle and what it does means when you do product on two vectors you will still get a vector out of it. You multiply the two elements on each position of these vectors and the element what you get out is like still

vector in the phen field. So if you unfamiliar with fields don't think about it too much you can think about natural number for this talk I think but for the crypto you like usually do always like mod number like the h because we infinite fields then the other notation I want to show you like the inner product it's probably even more important for bulletof protocols so the inner product between two kind of vectors is like you also multiply each vector at each position and you kind of sum it is here productors number in field also example to kind of if you if you want to want to go through that

okay like let's go through like the core idea of the bulletproof protocol to understand what it does so the bulletproof protocol it belongs to like kind of group of protocols which do something like a commit phase and then a real phase. So the first phase which is a commit phase you put in your your secret values it's usually some vectors or numbers and important thing is as well to know that actually don't need to be secret in most cases you want to have them secret but it's not a necessarity in some way so you have these two vectors and you have your C which is your number and you put them into commitments think about it like a sealed envelope you put them in and close them commitment it happens concord is created

we kind commit to the to attributes values of of your passport to kind of the fields every field in your passport is committed to and then you have the second phase the second phase is when you generate the proof and also the very proof proofs like checks the proofs so in the real phase the the proof of course has access to like your secret values and the commitments and it can generate a proof and then it sends the proof to the to the verifier and the verifier also has access to commitments of course not to the secret value. usually doesn't make sense otherwise.

And what the can can do it can say yes or no and it says yes the proof is valid when this kind of inner product relationship holds in in in the envelope and the important thing is it doesn't open the envelope. So it doesn't know the A B or C it just can say like okay I'm convinced that you actually these values you have committed to are following this mathematical kind of relationship. So to understand what the plan is for this talk is we have set membership and nonmembership and we want to kind of translate them into a mathematical equation so they look like an inner product relation because once in product relationship we can put them into the bullet protocol so

that's the first step we do we go quite in detail I think to understand how the kind of constraints are for for this problem how to to write them the second part would be then if you actually have secret protocol engineer kind of protocol nonactive you have to implement it in a way to yeah usually it's called like charm transformation we can look at it later ok let's go for the first kind of step what you want to do like the first goal is we have this kind converter start with our left problem is

an element of so how do we write into like two vectors that the product to see okay we start with the beginning like the start is like how we had the problem so far like our set s is like just some some elements in there and we know there like one we read it's equal to one of these elements in the set so we can write these sets that we have in a vector like left is like the set the set kind of vector with all the I think shi vector secret vector zer and one element other zer position one is exactly that

point where initially said our v is equal to si and when we have two vectors we can actually like do the inner product out of it and if inner product out of it gives then we have kind of written down mathematically that we know now V is actually one of one of these elements like SI and yeah so like we could think we have finished now but there still a lot more we have to do because whenever you have a special vector like this like a vector consist only out of zer on you actually need to constrain them further to make sure it's in this format and not like people to put in other numbers next slide is really how do we constrain al vector

AR vector you can look at the right left down how the vector looks like just has a lot of minus ones and oneer and we have a few more equations to ensure that yeah these kind of the al vectors actually from that form. So the first equation is like our definition from above to write it down holds then the second kind of constrain is that we make a product which is like each of these values al one of the elements at each position has to be zero and it constrains the al vector to just have zer just have ones and the last equation there to make sure that we actually have

one one in the al vector not more and this kind of equation constraint system couldproof protocol few more steps because in reality you would make a really big in product out of it in the moment kind of equations yeah but I kind of skip through that so if you're more interested in it you can read your blue paper how how to do several constraints into like one big constraints to make it one inner product now we get to the second problem which was this nonmembership may need to

make v so problem ai v si to other side equation differ two vales can never zer elemento find identity element multiplicative group about kind of natural numbers if you have a natural number you will always find like another number that you can

multiply with to give one except you of cost zero kind of element begin Ai vales constra sy we have fulfilled our nonmembership problem as well because we want to usually get in product forms then on the left side we have like our public set again that the verify knows they have previously agreed on the order of the element so you cannot shift the orders around of the elements And then we have the A vector and the AR AR vector. And especially the AR vector is the secret one. The AL value vector is like yeah

it's usually also secret. Yeah. The L vector we don't need to constrain further. So like the proof is allowed to kind of choose any element as long the multiplicative inverse to the other side to the difference I would say. And the two constraints we need is like the AR constraint to make actually like a vector consisting just out of V secret values and we have like one constraint which connects vector AR vector and in that way we can like describe a nonmembership problem into like a constraint system and then convert it in a long way into like a bulletproof protocol.

some tips because a lot of you are like auditors how to like review these kind of things like what often goes wrong when you implement these things because we also have to learn some stuff hardware I feel like when we implemented the first way like of course over the years you get better I think one one one thing you always can look at is like you if you have any kind of special vectors like in our cases of course these A vectors consist of zer and ones make constrain usually need a lot of extra constraints to make this form especially in the bullet protocol if you go to the second point as I said like the vectors don't have to be secrets so if you have to read the kind of conditions of your

requirements if they are secrets make sure they actually blinded and people have done this kind of last step to make them secrets then the next point is actually what from engineering point of view we actually struggling the most by now is that like at the moment we are U add new stuff new systems stuff it is very hard to kind of reasoning about that old kind of proof cannot be used in a new flow. So really recommend to you like if you out this stuff even not initially security vulnerability if you ref it for the first time really tell the people like

version commitments version context whatever you have probably it's a good idea to kind of version it especially if it could change over time and it really avoids that people use older that have been generated on kind of new flows in your product is like of course whenever you kind of have some sort random blinding make done correctly like you need to have fresh random they need to be uniformly kind of distributed usually there something we call the merlin script so I really recommend you to read about it because they were quite good in writing down how to do this val never reuse any kind of blinding factors or any randomness you generate like generate once use it once in your commitments and

never again and then there next step next transformation which would be like the step I would you transation detail transformation about in general things make implemented all and put everything public into transcript generators keys that everything has been transmitted between the proof and fire make sure it's in the transcript and also like stuff variable data prended lengar as much as can

understanding what transformation why actually complicated to impl the thing is like most of academic papers that we have as kind of blueprint to get started written in interactive way so different way to impl engineer and I think what blue paper in academic paper much easier understand what on the left side we have the interactive version that means the

pro and theifier are I think shi I don't know why and the proofer will send the proof and then later the fire will send back if the proof is valid or not valid this the interactive version what you actually implement is an engineer is the noninctive version that means you started runcript you give it some domain separation for the proof that you have and the middle part it's the hard part you should put as much as possible into this kind of transcripts and it means like for example everything all the messages between the proof and the

verify need to be put into into the transcript or all public values it means like your curve points for example radias or if you have any kind of public key has to be put in there and then when you actually need a challenge from the fire you would like hash your kind of transcript which is just appended and use challenge on the side and in that way you can kind of avoid forth and back communication between a broofer and a fairfire and you would only have like one communication channel which means the will send one message to the to the verify that's the proof and nothing more and that's why we implement this nonactive version because we don't want to have that much measuring betweeners anders

so what could get wrong when we impas input transcript of bulletof implementation vulnerable fixed after paper and it was fixed but it was like the biggest I think problems in the beginning with bulletproof protocols and channel protocols you forget something in the I go add

kind of length of items add example adding strings add a bb they will be generating the same hash if like add a and another string ab so make you add like length beforeh can hashision challenges make you add enough domain separation enough labels to it that kind of allows you to change things later in in the protocol make sure that like a previous label thing you have doesn't like overlap another kind of value later so I also recommend look at the domains and labels a lot and in whenever you have to

impl please transcs have some up me hope you got out of how to review zero knowledge protocols and bulletp any questions any questions for ja >> yeah so I see some similarities with merkle trees where you can prove existence of some element into the into the set I was wondering in what cases it's better to trees. Yeah, I don't know if you were here the beginning was one slide where I tried to give an

overview when to use which kind of protocol. Yeah. So it will depends on the size of the set. If you have very very large set you you have to use trees and if you have kind of a medium size set then I think you can use bulletproof protocols. So in our case we use it for for the countries and for the nationalities of the the passport information. So it's like max 200 countries I would say our size. >> Okay. Any other questions? Ja. Like like your your slide says it's best for the cases where you have max 100.

Could you a bit elaborate on the difficulty? Is it prover site? Is it a verifier site? The complexity of it why 200? >> I mean not a hard limit. use case I don't actually know exactly like we hav done any kind of simulation like how far we should go kind of bullet proofs and when we should stop the size but it would be actually quite interesting to get some benchmarking see like at one point you really say the bulletof protocol shouldn't be used anymore yeah the thing is like verification we do off chain so our faends but it's really because we work with kind could

indation that from from European Union and another at some point people kind of know where I'm from you Yeah, I think it's super fast like I mean the are like rust back ends and for generating the proof like the wallet pops up and you just click so the same flow sending a transaction on chain not any delay in there will say generate and then you approve as a user in the wallet

and generated may generation ok think we're on time thank you so much I love the the security overview at the very end I think it applies to a lot of domains not just knowledges a