ZK13: Lookup tables in CoSNARK - Florin Fabsits

Transcript

[Music] Hi, my name is Fin. I'm a cryptographic engineer at Tatio. And yeah, I will talking a bit uh we'll be talking a bit about lookup tables in So at the beginning I want to give a quick intro into secure multi-arty computation. So for short NPC. So all right. So in okay so in MPC multiple parties can compute functions um over their secret inputs while keeping this inputs private. So there are many different

protocols and security levels to it. So semi-honest versus malicious security, honest versus dishonest majority and there are many protocols. Um NPC is capable of supporting privacy across a range of applications. So such as privacy preserving data analysts, threshold signatures, digital wallets and importantly in the context of this talk collaborative snarks. So um how does MPC work? So at the core of MPC stands the concept of secret sharing data and with secret sharing schemes you have your private input and you want to distribute it to possibly unrusting parties to compute on

it. And yeah, therefore it is important that the shares do not leak anything about the underlying data. And how to achieve this? For example, in editive secret sharing for M parties, you pick n minus one random shares and then you get the last share just by the difference from the previous ones. And the nice thing about secret sharing schemes that is that it is linear. So meaning that you can do linear combinations on the shares and the underlying data gets modified accordingly.

um where you have to do interaction between the parties is when you multiply shared data and this is why in general you have to be careful with nonlinear computations such as multiplications since communication is often the bottleneck in MPC protocols and of course why we are doing MPC is that the inputs remain private and also the intermediate results remain private and unknown to the parties and also if you ex these pictures there you get the original cats. Um yeah. So what are collaborative snarks then? Um these are computing basically a snark in NPC where the private secret witness is secret

shared among the NPC parties and these then do the proof computation on these shares in NPC and then you get a proof out of it which is not different to one from a single prover. Um the big question then is why would you want to combine these two things with um overhead. So we have two primary use cases. The first one is private proof delegation where you want to outsource the proof generation from I don't know a handheld device which is not so powerful and can do the computation in reasonable time. Um but the problem there if you just upload your witness to someone you leak the witness to the person and you

have to trust them. So this is where MPC comes into play. So you secret share your witness and then an MPC network does the computation for you. And recently we launched a tier proof for beta testing. So this is our solution for private proof delegation. At the moment it works with circum and the crop 16 prover and also in the future our konoir implementation will be um possible to do with tio proof. So check out the blog post on the right if you're interested. And the other um use case we see is private shared state. So blockchains like example uh like for

example adst they store the commitments on chain. But the question then is how can you compute on these when you have a sensitive input from multiple parties. Yeah. And to do this with cosnarks you have to do all this stuff the snarks and so on in MPC. So what about the performance of coax? So yeah um our CK proof systems MTC friendly so for snarks we are mainly dealing with linear operations which we said before are nice in MPC so FFTDs MSM evaluating polomials at public point

some check and so on um examples of such protocols cross 16 bronc ka 2 and so other KCG IPA based protocols. Um on the other hand most starks they construct a merly tree and require many hash valuations which is not so nice in MPC because it's not so linear. Yeah but there are tricks to deal with that also in the stark case but that's another story. Okay.

Um, I think it's lagging quite a bit. Sorry. Okay. It stays I hope. Um so one challenge in co-arks is the extended witness generation. So there are quite some few papers on collaborative snarks but what is often missed out is the extended witness generation. So these papers they focus on the components of the proof system

and only pre briefly mentioned this witness extension. So we want to kind of distinguish this into two parts. So the first one is where you have your program your circuit and you basically compute the circuit on the input and then get the witness out of it and maybe some additional outputs. So this um basically requires an MPCVM. We have stuff we have to do there like bit decomposition lookups ROM ROM operations etc. Um the good thing is if you're just doing proof delegation you don't have to care about these things. And then the other part which belongs to this extended witness generation is the trace building. So where you have to do um additional

computations and witnesses on those witnesses and put this into the trace. Okay. Um, so now let's talk about lookup arguments in CK proving systems and what challenges they bring to the MPC setting. Okay. So why are lookup arguments necessary? So they are used to prove um operation statements which are expensive in CK. um for example range check, speed operations, elliptic curve

operations, s boxes and so on. So instead of doing these computations in CK adding many constraints for it and so on um you use lookup arguments and then you prove that these input output pairs belong to a certain table. So there are different techniques for it such as PL lookup lookup and others. So we've heard it before in the intro. Um so what does this mean for our case for the MPC case? So we have to do the lookups during the witness extension because we need the results for these lookups to actually continue the computation and get the witness out of it and then we also have to do deal with the lookup arguments during the trace building um which we'll

have a look up uh at a bit later. Um on the other hand the lookup stuff related to uh during the actual proving so we actually prove the stuff and that is no blocker this is just minimal overhead in MPC. Um yeah, now we okay. Um so we just said uh range checks are a possible application for lookups and there is an alternative for it. Um so this is how it is done in Bettinburg. So that's the proving back end. Um so say we want to uh range

constraint some values x0 and so on that these are in the range uh smaller to 16. Then we create a list with these elements put the upper and lower bound in it and also add our multiples of three. And then we sort this list and then we know that the neighbors in this list they have difference at most three and we also have the low and upper bound there. And yeah then we should know if the the values are in this range. Um so what this requires in MPC is oblivious sorting. Um and we need it to be oblivious because otherwise we would leak something about the underlying values. Um the main operations for oblivious sorting are you need to do

comparisons in MPC and then you have to swap them. So doing a cmax depending on the output of the comparison. Um so in our implementation in Kono R we use this oblivious radic sword from 219. Um another option is the batch even merge sword which is a bit slower but yeah also works. Yeah. Okay. Um now let's have a look at more general lookup tables. So you have an input and you want to look up the output value in the table. Again we have this example

speedwise operations sboxes so on and so we have some input X and we want to um get the output f ofx. The question again is how to do this in MPC. Um so you could hope that there are more NPC friendly cases so where you really can efficiently compute this function f in MPC. Um but in reality unfortunately often CK and unfriendly also implies MPC unfriendly. Um yeah uh there are still some cases which are more convenient. For example, for bitwise logical operations on field elements. You convert convert them to binary shares. Do your binary uh bitwise operations on these shares and then you

still have to convert these back. and but for other cases you will need a general purpose uh MPC lookup protocol which also have a look at later. Um additionally what is not helping this function approach where you compute this function in MPC is that you often have to decompose your field elements into smaller chunks and then you do the lookups on these slices. So this means even if you have some dedicated protocols to compute this function f uh this is probably only helpful in the witness um generation phase because in the trace building you will usually need these slices as well for the uh for the trace. Um yeah,

therefore you not only need MPC protocols for the lookup itself but also for this decomposition of the values before the lookup. Okay. Um now let's have a look at what um this lockup protocol introduces to a problem. So in lockup you have to um remember or count how many times a certain value has been looked up. So like in this table for example entry one has been looked up seven times and you have to do this in MPC and this counter then is later used in the constraints of the proving part

and yeah compared to the non-MPC or plain CK case this is substantially more difficult since in plain CK you can just um increment your counter but in MPC you not only have to do this lookup in a secure way but also do the counter increase without leaking anything. Um yeah, now we have a um yeah another related topic in snark systems that is from and drum operations. So we see some no code here on the side where you have um some input array and you want to write and read to this array um in an oblivious way.

Uh yeah, so we have to find some MPC protocol to do this because we have potentially secret shared arrays and indices where we have to read from and write to and this is something that already happens during the witness extension phase and then later again some form during the trace building. Yeah. Now we come to the part um what MPC lookups are and how they can be done and also about this writing RAM operations. So yeah these are the uh two main operations we need or we are

concerned about. So the first one is lookups on shared indices. So we have some array and indices scheme which are uh secret shell secret shared values possibly and yeah we want to for i look up the i value in this array and get the secret share of the x i out of it. Um and the other cases the other cases where where we want to write to this array. So we have some secret index i and some secret value y i. And we want to write this to the if entry of the array. Okay. Um let's look at how we

implemented this in uh konar. uh we based it on myestro which is a MPC protocol for u evaluating um in an MPC way the AES encryptions. Um so it is focusing on the sboxes part of AES. Um so the main point of this protocol is uh how you can efficiently turn your secret shared index into a one hot encoded vector so that you get a vector of secret chairs where only the if value is a one other ones are zero and we used this protocol and implemented it for reads and also extended it to um lookup rights. So

[Music] the the high level approach how you do it for um lookup tables of size two to the k is you recreate this one not vector um for example if you have k equals 2 you have the secret share of the index two and then you get this vector out where um so the tooth entry of the array is one other ones are zero and this requires to communicate K to the k - one - one bits in k minus one rounds and we will see now how we can use this for reading. Um so we have this one hot

vector from our secret index I and then we get our secret share by doing this dot product between this one hot vector and our array. So in the honest majority MPC case this thought product can be done quite efficiently with communication of one field element and in the case the uh lookup table is public we don't have to do any communication because it's just additions and multiplication with public values. Okay. Okay. And how can we use this for writing to tables? So say we want to write an element x to this um to

our lookup table. We can create this one hot vector and then basically cmox the whole table with the one hot vector. So you can see that um we write to the if entry exactly when j equals i. And we can all we can do all these cmaxes in parallel. So we only have only one communication round for this. And yeah, how we can we use this for this lockup program we talked about. So how do we count the values um for the looked up values? Um we create a one hot vector for this secretary indices which

we know when we are layouting this table and then we just have to sum up these 100 vectors and get our counts from it. Okay. So now that we have all these pieces we needed, how can we use them in our kono implementation? So I've said it here and there. Um we implemented all this stuff in our cosmax repo. So noir is at um CK language and we also implemented the ultra honk prover. Um yeah we have this oblivious radic sword which we are using for the

range checks. the mystro core for Roman drum reads and rights and all these um blackbox functions that exist in R like MSM char hashes bitwise operations they use this um techniques for lock up. So we have to to count the lookups fill the input output lookups into the trace and so on. So how this looks in in in practice for example if we have an bitwise end we have to decompose these uh field elements we do this via gard circuits then we can do there the bitwise operations and then we have to convert it back to the um arithmetic shares. Okay. So what are possible

improvements there for the future? So we could investigate more dedicated or specialized or protocols where we um don't need to hide the access type though um because yeah duplicate it is known as the circuit is usually public knowledge. Um one thing you also have to think about combining or with generic MPC protocols is not always trivial and we have to do extra considerations there. And what we also really like to have is some um way of keeping results from this W uh VM part where you compute the witness to the trace building part because we do a lot of duplicate work and we have all these intermediate

results already in the witness um generation and then we have to do it again in some way in the trace building. So it would be nice if we could kind of keep this there. Um yeah, let's have a quick look at some numbers. So here we have a comparison of this master approach we implemented um versus a more trivial approach where you just go through each index from one to the 2k with the secret index and uh do a comparison which gives you a share of zero one and then you put all this stuff into a vector.

Um yeah I think we can all see how much more efficient this master approach is to the dil approach. Um one thing that's left out here is uh that you have to do this um conversion from arithmetic to binary shares beforehand because the maestro demands it. So yeah that is left out here. Okay. Um yeah to sum it all up I think we all know that uh lookup arguments are beneficial to improve the prover performance. Um but on the other hand they introduce some

challenging uh challenges when you're trying to do this in MPC. Uh yeah this course for more research on coarks. So on the one hand for craft 16 which doesn't have this fancy features we are at essentially no overhead but when you introduce all these lookup tables decompositions um and stuff that actually make things more CK friendly they make stuff um less MPC friendly. Um yeah, maybe it is even necessary to take a step step back. So reduce CK friendly friendliness in some way to gain more MPC performance. Um yeah or why not both? That would be

better of course. Yeah. So what for the CK lookups they um require us to do this oblivious sorting this table reads and writes in a secure way. We have our implementation on maestro and this is all implemented in our core noir library where we are at the moment focusing on feature completeness. So implementing all these blackbox functions and stuff like that and yeah then have a lot of performance improvements and optimizations planned for the future.

Um, yeah, here are some links. There's a link to Franco's workshop at the last TK summit, to our docs, our blog, and our repository where all the implementations live. Maybe I'll just leave that here. And yeah, thanks for your attention. Hi, I had quick couple of questions. Uh, is your MPC semi-honest or malicious? It's semi-honest. Yes. Uh, and these benchmarks, how many parties, what network latency are they in the same zone in some cloud or like across? Uh, they were some AWS service. So, they were colloccated I guess. Um, and it was

three parties. Yes. And um are these MPC protocols? I forget mero but uh they're usually offline online the timings that you gave are they end to end timings or just the online phase the so this is for the creating the one hot vector so with all the communication and stuff like that yes so it includes like thanks is there any assumption about the uh number of parties as well do you yeah in you I mean yeah like some some of the MPC um protocols they assume two party at most or but you mean you mentioned three

parties in in in what protocol or what all parts of all parts that you presented are there any constraints on the number of parties in any underlying I mean our our cosarks uh repo at least for the witness generation um relies on rep three so free parties And for the proving we also have a shamir implementation where you can have more parties. Yeah. Uh thanks. I have a question on the uh the log up when you're doing the count values for the hash. You mentioned that there would be one round for each and every index or for all index on that. I Oh, for um when you're doing the

counting the indices, I think specifically for some of the So the counting for the for the looked up values, you mean? Right. Yes. Yeah. I mean it's um it's one communication round for each of these vectors. Yeah. Okay. Thank you. Yeah. There is still some improvements to be made. Yeah, sure. Uh, I wanted to ask about the tooling and how much like when you're writing a new circuit, do you have to always start from scratch or or there are like does the con noir allow you to do things without having to do all the basic things again? Do you know what I mean?

Like am I if I was to write new circuits, do I have to go back to scratch and figure out the the lookup stuff or are there good enough tooling that I can just do it at a high level and it would You mean like save it for later? Like you know how noir what noir did for circuits basically is give a high high level it had already some standard library you know things like JSON parsers and stuff you don't have to do that again every time you're writing a circuit I mean you can just do let's not say or but most of the noir circuits just run with our tooling. Yeah. Okay cool.

Uh I have a similar question regarding circum circuits. Will most of the like if the existing circum circuits can just use the cosnark github and compile and you and work with cosnarks or is there a lot of kind of are there some edge cases that you have to be wary of? Um no you can I mean there are maybe some cases which don't work but basically you can just use the circumcircuit and run it without tooling. Yes. Lovely. That's uh the talk concluded.

So, thank you very much, Floren. And uh it's break time. Lovely. Thank you. Thank you.