ZK8: Caulk – Arantxa Zapico - Universitat Pompeu Fabra

Transcript

foreign [Applause] from the one in the CK Study Club because things have happened in four months and that's super exciting so this is work we have done with vitalik Dimitri who is also here Mary markananca and earlier this year well I was an

intern at the term Foundation so let's start with a bit of motivation called has like two Canadian applications lookup tables and membership rules and I'm going to dive a bit deeper in both of them so for membership proofs like we can think of applications such as animal Anonymous credentials or the sequence the sequence protocol and the idea is like I want to prove that I belong to some like authorized set of people and this set of people is public right and we are all represented with our publicist and in order to prove myself into this group without leaking information about my

identity the first thing I I would do is like isolate my public key but with this yellow zero knowledge okay so the idea is that I can prove that whatever is here belongs to the set and then I can prove knowledge of the corresponding secret key and so I can prove that I belong to this set without really leaking uh information so for this to happen it's important that I don't like the value that I'm isolating but I don't lick either of the position both things will lead to my identity foreigners she proves Coke is like especially nice because

um previous approaches like most of the applications use these like murgatory approach so we are going to see later and like numbers in in implementation we have we bet them by like 100 times so we are 100 times faster than what is being used today for lookup tables um what do we have is that instead of a hidden element we have a hidden set and once again we want to prove that all the elements that are in this hidden sets do belong to some public set there maybe they are repeated we don't want to leak positions we don't want to lick values and lookup tables are

think of them as generalization of range roofs so in range proofs we have again one element that we have like in zero knowledge and we want to prove that it belongs to some range a way of doing this is like once again linking it to some public set that for instance in this case it could contain all the values in the range and when we use lookup tables as like range proofs we can really speed up like uh snap Brewers and also when we use them like for instance to replace like hashes to prove that something is the output of hash it makes a big difference in for instance in the secrets that we we need

to to design for the zero knowledge virtual machine and it makes a difference between a circuit that we can prove and one that it's like basically not practical so all these problems range groups local channels membership rules have been tackled before by other works and basically I will say we can like divide them in four groups we have discrete log Solutions and they have a trusted setup and sorry transparency tabs so that's super cool but usually we need both program verifier to build in the size of the big set in the Panic set so we are like

wasting time here right then we have like everything accumulators Solutions which same amount like and can you see properly okay sorry so erisa accumulator Solutions seem like perfect we have a constant program a program that does not depend uh on the size of the big table but we also have on some verifier and a constant proof size but we have trust its parameters and if you are like familiarized with Coke probably you will tell me you also have trusted parameters but they are quite the same kind of traffic parameters we have like ceremonies multi-party computation in

order to perform our just parameters but with everyday accumulators in order to instance the ID Scripts things are way more complicated and unpractical nowadays then we have the American three solutions which are the ones that are all around 6 Edge protocol for instance and it's nice because again we have a transparent setup but then we need to put a zirnary snag on top of a market tree America trees have a lot of hash so this snack has a program that is linear in the size of the secretness oh that's not but in the size of a very big circuit so again this is not the idea and for Pyramid Solutions which we we

have a bunch we have constant proof and concept verifier but usually the Brewer is linear I mean before cook so coke lies in this setting we we work in the parent-based setting we have a logarithm approver in the size of the big table so that's a huge stay and we have also found some proof like most of parent-based constructions and our verifier is still like dominated by a constant number of parents and has to perform a few operations in the field so let's see how how do we construct lookup tables with a fast blower so we

don't want our Brewer to be linear in the size of the big set that's that's what we need right to get rid of the elements with the news and I will give you a recipe for this what what does calc actually do we start with this big public set of size n and first thing we were going to do is create a subtitle so if our healing set it's only taking some elements of this table we don't want to work with all of it so the first like a step two like become non-linear it just gets rid of this size and the big toe and of course this laptop will need to be hidden as well because we don't want to leak like

information about the positions or the values that we are isolating then we have to prove of course the subtitle is well formed it's indeed acceptable of the big set and then we can link it to our hidden set that I would say the hidden set has size m and I hope now is a bit more intuitive that we can actually do this in time that does not only and linearly on the size of the big tail it should be faster right we have something way smaller which is the subtable of size k and we have our hidden set that has also size m less uh smaller than there sorry smaller than the than the big set

and this recipe works it didn't work for us so I have some Benchmark here this is the representation of comparison with previous work in membership proofs our Brewer has eyes login so it's logarithmic on the size of the big table Coke is the orange line that you can see low so in the y axis we have a proper time in a logariance mix okay so this means that we are like order of magnitude is better than the closer solution and in the index axis we have like this the size of the of the big set so we go from sets of size 2 to the six to two to

twenty two um we can say I mean we can claim that coke performs better than other solutions for basically any like practical set and the red line the second one the pointer is not really working but the red line it corresponds to where I say accumulators we say they have like concept Brewer so it doesn't really matter how big is the set we we are working with and then with a green line on top we have a murder trees with positan hashes so even with potato hashes we are 100 times faster and the pink line or the very top is like murder trees that are

constructed with such houses so for membership groups we we did pretty well and then for lookup tables the same chance of it so at the very top we have like Miracle trees with Poseidon hashes and a snark on top they are like obsolete hopefully compared to the other ones and in this case we have again proper work in a logarithmic scan in the y-axis and in the X we have like the size of our hidden set so for lookup tables we are not isolating what element but a bunch of them so we try numbers from 10 to 50 small sets and the line the color of the

line is what is represented the size of the big set so the blue line is to open sets of size 2 to the eight so if my public set has a size 228 we go from 10 11 to 50 color performs quite well endurance line is when we start with public sets of size to of 2 to 20. called still performs nightly nicely and the direct one is RSA accumulators only one line because again in another circumulators we don't really care about the size of this box um the things that we only computed up to 220 because that's everything my

laptop could handle but if I would say that for sets of size to 223 to 225 already performs worse than error second and also like you see our Brewer has size M square plus M times again so it depends logarithmically on the size of the big table but quadratically on the size of the Hidden set and this will probably have well this that's this okay okay

no worries [Music] okay foreign okay perfect so uh also this m Square um like elements will play a role for bigger sets hidden sets so in the x axis we may get also worse if you see in the orange and the blue lines like the slope is growing slowly but this will screw so

this is this is what we care about here we like all the improvements we are going to talk about are like on getting rid of this and square and logarithmic log of anything so how do we actually follow this recipe in Cork let's talk about like concrete stuff to create a subtable first we use like kcg commitments to polynomials that encode the vectors with um LaGrange interpolation so for the big table we need a set of LaGrange polynomials of size of degree and minus one that will correspond to a set of root of unity of size n but

for the subtitle we I mean we are creating a subtitle because we want to work with smaller things so committing to the subtable with the same set of LaGrange polynomials would be like nonsense so what do we do sorry it's like commit to it with another set of larynx polynomials that correspond not to the entire set of root of unity of size n but only to those that represent the values we care about that represent the positions we care about so this other polynomial that has um that is also interpolated using roots of unity will have only degree K minus 1.

and this is an idea we took from this very nice work from thomasco at all um but we also took from there is the proof of information so we can create this up too we can commit to it and communicate it with a small polynomial and then we can prove that it is well formed with like the proverb only will take like time K not M sorry that's a typo given that we have a pre-processing that is linear in the size of the big tail so we can get rid of the big table somewhat but we pay a price which is in the pre-processing

and this is I would say fair enough then our prover is K just like cheap small the thing is that in our setting we also want zero knowledge this is not something that was um considering the work of Thomas Scotto and to achieve zero knowledge we need to prove World formation of some like banishing polynomial I'm not going into the details we have a very nice protocol for this it's like seven pages two columns and it takes time M Times login that is the m Times login that we have in the benchmark

and then like I think it was like two months after we we release Coke we got this email from Jim Poston and Katie's and they were like hey why there is this other way of doing things have you considered it uh no we didn't and it was way wet they reduce these two end which implies that now the lookup table as the title says is independent of the big table modulus the processing but once we have the processing that's it we don't care anymore about this began so this this was great we only have now M square plus m and

as I said before once we have the whole formation of the sub table we can get rid of the big one we don't care about it anymore and now what we have to do is just link this subtable with our hidden set our hearing set will also be committed with the KCT commitment as an encoding of of the vector and if you see we are working with a different set of polynomials here a different set of LaGrange polynomials why because the first one we are using that is public has eyes n we don't want anything to have size n here then the second one the tiles those are secret those are like LaGrange polynomials that will leak information about the positions that we are opening

so we need another one we need a public set of large polynomials we can work on later um this will give a bound yeah it's what we call them so assuming that that means like way smaller than it and now our problem is to link these two guys the subtable with the hidden set and in Coke this is what takes time M Square and this is what we want to improve this is all I'm going to talk about now so we have two polynomials we have two polynomials and called vectors that we want to link we want to prove is that

everything that is in the in your right side so all these A's are actually the same as one of this of the beasts in the left so everything that is there has been taken from here and this is nothing but the lookup table itself right this is exactly what lookup tables do with the difference that we have this the hidden set keeps being hidden as in previously but now we have the table itself is hidden it's not only hidden but it's also in an unknown basis amazing that approver makes itself and has to keep Secret

so I mean it's it's not the same but I think we already have like a starting point here we just need to construct lookup tables where the Brewer can be linear on the size of the table because now our table is not n is just K it's way smaller so a poorer can be linear on that and we have lookup tables for a linear program in the very base setting so the idea is that what we have to do now just adapt these ideas so the table can be the table can be hidden so the first the first approach we are working on uh with Mary Dimitri and Ariel is to use blue

cup so Ariel says okay this basis is unknown and it's bothering me so let's avoid it we don't commit with LaGrange polynomials anymore but the commitment to the polynomial to the vector to the big table is going to be a Vanishing polynomial at the values of the vector so no more roots of unity or anything like that here this this is a work in progress but let's say good progress um this approach gets very good concerns and apparently pretty sure we can get rid of the parents so this convenient

with other kind of like um polynomial commitments the bad thing is that we need quadratic computation so itself n it will be N squared and the commitment is not homomorphic anymore but for some settings where we don't want to really update it should be okay their approach is to use Smart techniques and when I say snarks I say Matrix and vectors so if you are familiar with Marlin or if you are familiar with r1cs all we do in snarks is try to prove like linear relations like this that some Matrix multiply some Vector equals some other vector and this is a relation that we that holds for cim and

fee it snarks like usually what we have here is cni an a sorry I like the witness a part of the winner so we keep them secret but now the challenge is to keep secret as well the Matrix because the Matrix is what we'll select which elements of c are going to be in a this approach has homomorphic and updateable commitments so that's nice but of course it's a snap technique so it has like the bad snarts Concepts so what to expect for very many solutions we already have like blue cap and Halo those are linear in the size of the big table

so they come out like to be very good for um small tables where we look up at many things so when a hidden set is big but the by the table is small and for Coke right now it's called the opposite right we are quadratic in the size of the small table so if the public set is big and we are looking at like small pieces of it this works well the question is like if we can get the best of both worlds which I mean just linear in the size of the handset I say yes sure but I say like small because you know we have to do the pros yet but that's where we are right now thank you

[Applause] sure uh we're gonna do about five minutes of questions here I'm gonna come around with a mic so please raise your hands if you have a question for a run hey uh you mentioned that the um the the setup is is better or different than the types of like NPCs have been proposed for RSA stuff can you impact a little bit like why that is yes so I don't know how familiar you are with kcg uh

commitments but the idea is that the setup is trusted but it's something that you can compute using multi-party computation this famous like ceremonies and also it's Universal that means that you can construct a very big like uh setup and reuse it for many different for many different like um kind of products and then the thing with RSA accumulators which is not exactly what I do so I I hope I'm not going to make any mistakes here but theoretically we could do the setup with multi-party computation but in practice no like nobody has time so you really need one Jurassic party

for areasa accumulators while for repairing base uh like vector commitments or even snacks this updatable and Universal snacks you have like a better approach which is multi-party computation Plus do it very well once and then you can reuse thank you for the talk just one question about the preprocessing can you say a bit more about the specificity what is the size of the processing that the Brewer has to keep around so um do I have the slides no I missed them okay no it's okay it's

we will have to go back quite a bit but the thing is that in order here no here so in this work the thing is that when you like prove World formation of the subtable you have to relate it with a big one and that would should take size n so this is an equation where you have to compute polynomials of size n in this work what they say is okay you can pre-compute I would say this proof of like all formation of subtitles for subtitles of one element but for all of them so basically you open the big table at every one of its elements

and that's x times n log n sorry but the size is n the computation of this setup is n Times login and then once you have there okay once you have done from this set of end proofs you can compute the Plus for every subtable on time that depends only on the size of the subtitle so in this case I will have all the individual proofs for all the A's that belong to the to the subtable and then I just aggregate them basically with some consonants and I got the proof of all information was it clear perfect foreign

yeah sure um what I'm wondering is is there a way to to Bridge uh these techniques with something that would let you do um like efficient updates to what the sets are right like so because the like the point is sort of the previous talk is that like it's not actually just the proving time but also like how do you actually know what the set is that's evolving over time um and I'm wondering if is there something some way that you can do like incremental updates yes so uh as Coke is right now updating the set is possible but the

problem is that you have this pre-processing so you have already like computed the opening proof for every element and with KCT commitments if you change one value of the plus chain so this is not ideal still there is a way of computing this kcg proofs like in a tree fashion let's say like not America tree but as a tree and once you have that you can like update chance of the of the of the set I like get rid of this like recomputing everything so yeah code for

now will I will say you only use it if you have like a table that will stay like as it is and then you can do some some other tricks and actually we have a work after this on like maintainable back to commitments that you can trivially apply too um and then one last one under the wire is can you also do um proofs of non-membership no actually there was there was a discussion on Twitter about this and Jim the same guy from plus he kind of have an idea but to be honest I didn't check it but apparently like I mean I would trust him after the Improvement he found uh but yeah I will

I will say there is something there but I I cannot assure it works all right please give uh [Applause]