zkStudyClub - zkSaaS (Sruthi Sekar, UCB)

Transcript

hey it's Ruthie how's it going uh so I'm sorry I screwed up by not deleting this meeting invite this is actually the link if you can use this one okay that would be great so I'll see you over in the zoom yeah great bye okay hi suie yeah hi how's it going yeah

it's going good let just switch my phone sounds sounds great can you hear me better now yeah it sounds great The Sounds sounds perfect yeah perfect um cool um I'm sorry I was a little bit late I had a meeting run over um but that's all right I just updated the the main invite did you want to just test out your slides make sure you can like that yeah yeah yeah just throw them up and then while you do that I'll just invite everybody remind everyone that is happening uh I think I still can't share my screen oh yeah I forgot you have uh I gotta give you permission second okay try

now nice oh your picture is not there CTI yeah because I'm there on the video so I didn't put mine all right nice yeah okay yeah so yeah I think it looks okay cool so we'll give it a couple minutes here I had a couple there's a couple people that registered um and so we'll give a few people a few minutes to kind of roll in usually it's like 5 to 10 people sort of start rolling in um and then yeah we'll run it I've already recording this by the way so the recording is already started technically but I'll I'll edit all this out just that you know and then when I upload the

video to the YouTube channel um you know it'll it'll just be this presentation uh and if you want to share this presentation just send it to me afterwards to my email and yeah I can share yeah in PDF format or whatever and then I'll upload it as a slides share and I'll put the link in the in the video description yeah sure perfect I'll do that yeah cool awesome um yeah so let's maybe give it I don't know a few minutes five minutes or so and then we'll plan on starting maybe just 10 after so if if you need to get like a water or just get prepped it all yeah feel free and then um yeah and I guess Lucas welcome um so we'll get started in in uh in a few minutes here yeah soy just just so you know oh two things

actually housekeeping items uh so do you prefer questions throughout or at the end uh throughout is good I think it's like uh uh it's great if like uh there is something and people ask me right then I think it just clarifies things so throughout is great okay great and then um the uh the chat I'll read you questions that come in the chat and because I'm not sure if you have two monitors or not so sometimes it's easier for me to just read the question so I'll if someone types questions I'll let you uh yeah I'll just read the question alowed um yeah that would be great yeah thank you so much yeah I don't have another monitor right now yes would be great no worries okay so we'll do that and then

yeah people like like I said the way these things usually work is like you know the peak attendance is around 45 minutes in and then it like like a mountain you know so it's like people like start coming in and they start going out so people will filter in and out um typically we usually have a handful to start and then we'll you know it'll pick up over time but we we'll give it three minutes we'll kick it off I'll introduce you by the way just so I know sure so I have I want to make sure I pronounce your name right is suie is it suie yeah yeah yeah that's perfect yeah okay suy SAR or Seer yeah SE is yeah okayu Seer did I say that right yeah yeah that's perfect thank you all right all right I'm sure it's not perfect but I'm gonna

try um yeah cool all right so I'm going to go get some water and uh sure sure and I'll be yeah we'll be right I'll be right back here I'm going to put another reminder in the channel and then we'll get things kicked off here in about three minutes sure yeah cool sorry to interrupt a colleague of mine

asked if there's a direct link or so that he doesn't have to register oh yeah yeah I put it in the uh here I'll I'll uh you should be able to just get the link I don't know if you guys can get the link here let me put it in the in the messages or in the chat There's the link uh it's in the link is in the telegram too um I think if you're not but I'm not sure if you're in the telegram um but yeah there's the link feel free and share with anybody thanks and uh yeah here let me turn my camera back on here and let's get things kicked off all right uh okay cool so I'm gonna kind of give like a three countdown and then

I'll edit all this out and I'll introduce you quickly suie and then I'll let you get started um okay hello everyone welcome back to another edition of ZK Study Club today we're very proud and excited to welcome suu sakar from UC Berkeley um and she's got a new paper called ZK s z knowledge snarks and service with colleagues shown on the slide here but we're very happy to welcome shuie today who's going to present this work through3 uh thank you for being here yeah thank you so much uh for inviting me uh and uh I hope to tell you more about your work um and uh feel free to interrupt me at any point during the talk uh so yeah let's hope I get to

tell you more about uh zero knowledge snar as a service or Zas as we call it um so this is Joint work with sanjam gar arushi goil abishek Jen and gurami poera um so before we head into you know what is zero knowledge snars as a service uh just as a recap for everyone here uh what are zns so uh there are these Primitives that help a party call approv uh you know prove an NP statement of this form which is you know that there exists some witness uh for which you know this relation circuit um outputs one if it's a valid statement um and this proof is sent to this verifier who then accepts or rejects it and the

verifier has only access to the statement and not to uh this additional string called the witness so it requires some additional properties uh and um it comes that's that's all is represented by each of the objectives in the name so zero knowledge means here that you know the string W that the approver has in addition to give the proof um the proof itself hides that W so that's that's what on a high level zero knowledge means succinctness is something that's desired for applications which is that as a verifier uh I should not be required to uh do too much more computer comption um or rather like the the computation time to verifier should be much less than you know actually just

evaluating the relation relation circuit so that's what sness here means roughly uh non- interactivity is something that's already depicted in the picture which is that it's a single shot proof and anyone can essentially verify and soundness again um I'm not explicitly stating what arguments of knowledge is but soundness roughly means that you know the proof will not be accepted if uh the statement is not valid which means if there is no witness uh such that the SS then uh you know prer will not be able to prove a false statement to the verifier so that's like you know a high level recap um which uh probably people here would already be familiar with and um you know not surprising zero knowledge snacks uh

specifically with the zero knowledge competent have also found numerous applications since they're uh you know used uh which includes anonymous credentials you know verifiable in prints of machine learning uh private smart contracts you proving the existence of bugs in code uh or you know security vulnerabilities uh fighting this information which I'll talk about a little bit in detail uh as a you know running example and private transactions like z zcash uh so you know no wonder that we have several such applications where I have listed out specifically the ones where zero knowledge is also needed um and um no wonder there has been a

flurry of research and you know improving the efficiency of the snars in terms of like all the parameters including you know keeping the balance between succinctness and appr running time but uh unfortunately for you know several applications um and I'll State a running example to show you what I mean the pr time uh in generating The snars Still Remains to be much larger than the relation circuit time and um you know this uh for SE certain applications at least uh you know picking out any of the general snacks from here uh doesn't serve the purpose and it still turns out to be very inefficient and um here is a running

example to kind of elaborate on what I mean so the example is that of fighting disinformation which is something that um has been re recently you know uh shown to have like very deep impact and is one of um you know an important application to look at where zero knowledge snars uh serve they can be applied to so particularly here is an example where aover has some video clip so this could be about images or about video uh but let's say you know video because it's like a larger file so the Prov is trying to prove that you know only an allow set of edits have been made to this video and uh this is important to do so

because um while camera these days come with you know some form of signatures uh with which you can authenticate the image that has been clicked uh however when you know you see like these images or videos circulating uh online uh you do not have control over like what software was used to edit and what kind of edits were made so in some sense like the uh already existing like signature would not work uh for you to authenticated and particularly some of these images or videos might be sensitive which is where the zero knowledge aspect comes out to be important um and you may have like edit operations including blurring sensitive

part of the image or video and um zero knowledge snars help out in such scenarios where you know as a approver or as a person publishing the video or image you append a proof uh that you know only a certain allowed set of edits and nothing fishy was done to this video or image and hence you can trust it so as a verifier or as a viewer you can just check that it's a valid uh you know image or video uh and then like believe it so that's the rough idea behind you know how you would find this information using snars so as I said the pro would send this proof uh proving that only a loud set of edits have been made to this you know video and clearly the proof needs to be zero knowledge because uh

you know there are sensitive parts of the video and improving something about it you don't want to leak those blurred out parts or those sensitive parts and um clearly here when you consider the example of video you know typically all the videos even shorter Clips if it is high definition it's going to be super large and so if you pick out any of the snacks uh as is the generation time is going to be super long so this is going to be a you know a running example for you to understand that there would be scenarios where relation circuit that you're trying to prove can be like really large with you know uh large number of gates and for such scenarios um you know a single prover uh doing the entire proof

computation can be really expensive and so the question that we ask is you know can the Zs now computation itself be delegated instead of a single Pro doing it so of course like you know here's a simple thing that all of you might already see is not a good enough solution what if we just you know send the video to a powerful machine um and then ask it to compute so just delegate it to a single shot single server uh of sorts of course okay that's works you can get the proof and the pro doesn't have to do the work you've completely delegated but this while it's privacy because um you're just giving the entire witness to the server and it's not just that you're protecting the

sensitive video from the verifier but you also want to protect it from the server that you're delegating uh this to so this is not a you know good enough solution for the setup that we are looking at so instead uh what we ask is sure okay we delegate this to a bunch of servers instead and you don't give the entire witness to all these servers but give them in some some form in which each of them do not learn anything about the witness so as we'll see later it's like giving a share of the witness where each of the share doesn't leak anything about the witness and uh the group of servers will using this shared witness uh just run a multi-party computation protocol which is just a protocol that

helps you you know generate the knock proof um without revealing anything about each other secret inputs in some sense okay so this is the um you know rough idea where we visualize the delegation to be useful and it's not just us uh this concept was like formalized you know into a concept of T server Z knowledge uh by this work of collaborative znx um by oir and Bon in 2022 and um that brings me to a comparison of what was known right so we did want to do it but it's not so much that uh this was not done in some form before so the collaborative ZN work um does formalize this notion of how to you

know uh do a efficient MPC to compute the zis KN proof uh while still preserving the client's sweetness but unfortunately uh you know each server in this multiparty computation takes as much compute time as a single Pro um so this is not this is good for like you know wanting to do this delegation in a private way uh where you might not be looking at applications uh essentially where the circuit is like super large maybe a single Pro itself is good enough but it's just that the client who is wanting to do it uh does not have that much computer power for such scenarios collaborative zik no is itself trade but um remember our running application is a

scenario where the circuits are like super large and uh necessarily single Pro computation time uh may not be good and on the other side there was this work of distributed zero knowledge proof system uh or diic where um they did look at how to distribute the work uh the Pro work across like you know several machines uh in a compute cluster for faster proof generation uh however they did not care about the Privacy aspect so essentially all the Clusters that you're using will get the entire witness so there's uh no privacy component in greed in this and our result somewhat um tries to combine you know the best featur from both of these Works which is get the faster proof

Generation by you know delegating it and actually getting a divide of work amongst the servers um and at the same time um preserve the Privacy guarantees that the collaborative KNX work did uh which is you also retain the zero knowledge not just against the verifier but also against the malicious servers okay so um with that like uh we required here is like a very brief summary or you know Road road map of what we end up doing so the first step we do is formalize this framework and that's what we call uh Zas or Zer knowledge snars as a service um and you know the goal really is uh to make this use where you provide or snag generation

as essentially a service where a client can come give you it shared witness and then request you to give a proof uh and be sure that you know nothing about it its witness is going to be leaked in this process um so this is what we formalize and each server here uh I want to stress again each server here is expected to run for a shter duration than a single local prer uh if not this then it's essentially collaborativ Cas now where you take as much time as a single T so this is a key expectation we have from this framework and uh then we go ahead to design the Zas uh for some of the existing you know widely used snugs like uh Groth 16 Marlin and plon

um and these were also the choice you know snars and the collaborative zik snars work and we show that you get faster run times than local prer so specifically uh we have a prototype implementation where we show that you know Zs for uh we show it for R 16 and long and uh we get a 22x speed up when you run with like 128 servers um and I'll talk more about you know what is the compute power memory PA that you need from the servers but this is the you know just a summary of how much speed up we end up getting uh when and we can go up to like two part 25 constraints for growth and two part 21 gates for PL uh so this is like the summary of our results in some sense um

and I'll compare it with a concurrent work which is uh you know EOS um and in the next slide but you know if anybody has any questions about this yeah I was actually gonna ask about that e because EOS is obviously P's work right so I think you know Berkeley Berkeley Alum so I was yeah I was curious to hear the uh the comparison with that that was my only question at this point does anyone else have questions all right yeah keep rolling this is great than you yeah yeah so um yeah this is the point where I bring up this concr work um and of course their goal as well was um you know private delegation of the kiss for fast approv Generation Um but I just wanted to

highlight like there were certain differences in their model from ours um which comes from the kind of again like the underlying theme is similar where NPC is used to do the proof computation and you do it in a fast efficient way uh to make it useful but um the Highlight is the difference in the model so in e um what you require is for the client to be always online so in some sense um I think prush already spoke about this that uh to make use of uh or to actually G get gains in the uh you know uh runtime you need to also bring in the delegator or the client um they call it delegator so the client always needs to

be online through this MPC computation um of the zik kishna so you do a MPC where the client is like the honest party and um in this model the goal is to reduce the client's work right so it's not so much that you visualize the client just coming giving its witness to the servers and then now the MPC is done by the servers who then give it back to you so it's not visualized as entirely being able to divide and split the work amongst all servers whereas what uh we visualize it as here is that the client really is not part of the protocol and it's really application dependent scenario if for certain applications you're okay with your client anyways being online um then EOS is great but in our scenario we visualize uh you know

there might be async issues and things like that so the client may not want to remain online uh it can just come do this like one shot computation give you give give the servers the shared witness and um you know after the entire computation is done uh the servers will return the proof to the client so we really view it as a complete delegation of the work to all these servers um besides that um in the paper itself us has malicious security um you know they don't lose out on that uh whereas for us in the paper we only Pro semi honest security for the setup but uh I want to mention that we can add malicious security with just like a factor to

speed up if it's FL and in fact fact for certain settings um that are interesting enough for applications I'll mention you know later in the talk towards the end for for certain scenarios like Groth 16 specifically we can add malicious security without any additional cost so we have zss for Groth 16 with malicious security without any additional cost this is something we can do uh and we don't have this in the paper we only present you know semon security for e but this is something that can be done this is something just I wanted to mention nice and I I guess is it worth uh you may do this in a minute but I guess is it worth the finding what semi honest security is in this setting yes so semi honest security is where um uh

the servers can be corrupt T of them can of course be corrupt but um the sem honest assumption is that they still follow the protocol so whatever the multiparty computation protocol requires them to do they would still follow the protocol um and this is typically the the like assumption in semi-honest adversaries um whereas in malicious security they can arbitr deviate and do whatever and so for several practical scenarios that's like usually the uh the the requirement that you know you don't assume the dersy behaves honestly so it can do whatever it wants got so yeah so that's the I would say difference between us and our work but um again like these model differences

and stuff uh it really depends on the application scenario um and what kind of underlying secret sharing scheme or underlying stuff that you want to build and what you're more comfortable with for the specific application it really depends on that whether you use EOS or zikas um but um yeah so that's really the comparison that I want to leave at and if you have any more questions like yeah no this is great yeah well I I agree I think it's it's right that I think like a lot of these schemes you know like on their face seem similar but I think there are important differences and I think that application the specific application matters I mean obviously for the purposes of ZK Study Club it's it's all about research and

you know obviously this research is typically focused on pretty low-level protocols you know that people will build on but I think it it is important to think about it from the other side where to your you know we were just talking about security right like right in the Practical setting you know like is anyone going to be okay or is it is is is semi-honest security enough I mean probably for some applications maybe not for every application but that's the key so it's it's great to have more a greater diversity of these different models that people can build upon because it theoretically supports a greater class more more yeah no this is thank you yeah let's continue actually we can also add the malicious security but it comes with the cost of a factor to blow up uh in the Pro time cool yeah so but it's like

you know whether you're willing to pay the price yeah yeah exactly yeah yeah depending on the application of course so yeah to it and I think it'll be interesting to see you know obviously the concrete you know seeing seeing concretely like you know how some of these uh these advantages manifest So yeah thank you shy please continue yeah yeah yeah great yeah so uh moving on like uh I'll tell you more about now the framework itself so how do we build this for that let's uh take back a step and look at what what does typical Z computation involve and um today like I'm going to be in the setup of pre-processing zik SNS where you know there is some setup face and you establish some common information uh so the typical ZN computation involves a first step of computing

something called an extended witness so you given this witness string and the relation circuit that you need to compute um or you know you're proving things about and from there you need to do this computation step of something called an extended witness um before you go ahead and you know generate the proof itself and the generating the proof itself has typically you know two sets of operations and this is for a particular class of snars this is true uh where there are cryptographic operations by which I mean you know you have group exponentiations or pairing operations and they are typically more heavy um as compared to the field operations part um and this is typically you know the very very high level

blueprint of what goes into a SN computation so in our model or framework what we want is for the client or you know the person who's delegating the proof to come in and compute step one which is you know Computing this extended witness and then secret share this extended witness amongst all the servers right so note here that uh the client already is doing you know um when you're secret sharing and sending the witness to all these servers the client is already doing linear work uh but then it's only in the field operations so you're uh and also this component can be something if you don't want your client to do you can think of doing this component also by using some NPC protocol um so this this part of the

stuff is not something that I'm going to get into for how to do but it is of course an important step to figure out for end to end implementation and it really depends on what power your client has and you know for the specific setup um whether you're willing for the client to do all this or you want to actually you know get a split of work in that component as well but I want to stress here that this aspect uh is all field operations and that's why it's okay for the client to do in some sense and uh then the servers essentially compute the step two which is generating the proof part and of course can use some additional pre-processing um where each Ser gets some correlated Randomness and um this

is going to be you know the step two is the part that we want the actual work divide and step two generation using these servers is what would be the focus of zasas framework essentially okay so um and within this I want to stress that the more heavy computation which is the cryptographic operations uh they get equally divided amongst all servers both in the sense of like the memory usage as well as the you know compute time uh and this is great this is what leads to the saving that we end up getting uh unfortunately the you know end goal was to get a split of everything for all all operations that you do the entire proof

generation but uh because of a certain component of proof Generation Um which I'll talk talk about and this is specific to the uh you know snars that we focused on which are you know the univariate polinomial regime SNS like plon or Marlin um or Groth the reason uh because of that the field operations unfortunately do not get divided entirely and there is some asymmetry in the server requirements that we need so we need one of the servers amongst all of them to be you know some King server that is able to do linear in the number of field operations um but the remaining servers can all be like uh much smaller machines

and because the field operations also get equally divided amongst all the small servers so this is uh unfortunately the asymmetry we still have in this model but in spite of this because um at the end of the day you know the sking server needs to do linear work but only in the field operations and the heavier cryptographic operations get divided uh we see like still a large Improvement in the number like as as I mentioned before we get a 22x Improvement uh than what a local prer does but of course like the dream goal is to you know get to a Zas framework for something that you know this kind of a symmetry also doesn't exist so this is like a direction for future work is to figure out how to reduce exactly the

Symmetry got it yes so I'll particularly talk about like what is the protocol also that needs it uh looking ahead it's essentially fft so when you're trying to do this split of work amongst all servers and figure out some distributed protocol for fft um that necessitates uh you know such a asymmetry in some sense if you were using a different uh Proto or a different uh you know type of ZK snark that didn't require the comp fft like I I think I correctly like Spartan I believe does not require ffts would that would that uh you know how does that change in this model I I don't know if you guys that that would get a that would get a perfect I mean that

required work to do it but we have some followup work uh we working on it essentially so um essentially yeah non f5b SN will not have these issues that we Face specifically for F50 uh and the remaining computations are all nice so MSM which are the more heavy part they get completely divided um as I'll show you yeah right right and I guess maybe on the flip side a a snark that is heavy fft like Starks for example would be this would be would probably the disadvantage this model would be more disadvantageous for those categories of snarks is that would you right okay got it yeah so um I do want to point that

even even if you get you know that Improvement in number because you know you end up that the group operations dominate but not for the example you mentioned where anyways group operations may not be there uh but um the the main thing is that we in some sense um look at it this way that because of this one requirement of asymmetric uh need from a king server you're still uh in some sense in the memory requirement uh somewhat restricted by what the underlying snark is restricted by uh not so much we can still tolerate you know a little bit more in the sense of constraint size or gate numbers uh we can go a little a little bit above what the local prer does but not so much not as much as we would like to because of

this asymmetric need so this one king server really hinders that in some sense so it would be nice to get like a full split and you know who knows we'll be able to go all the way up to like two part 40 constraints or something which is not possible in the local prer for sure yeah so cool yeah thanks by the way if anyone else has questions besides me you feel free and jump in but um I'm just a curious person so uh please continue throughly yes uh yeah feel free to interrupt me anytime just I want to mention again okay so um what are the kind of example applications where such a framework might be useful like I listed a couple of examples of you know where zik snars

itself are applied but I just wanted to bring it back with the model in mind and um you can have like two sorts of things one on the one end you might use this application of snars as a service to users with mobile devices who do not have as much compute power so particularly there may be um you know these two applications of private smart uh private transactions in smart contracts where you're trying to prove General computations on Smart contracts or you might have like statements involving ethereum wallets um and essentially the vision is that you know as a mobile device you can just send this uh to all these servers and U you know not even required to be online while they're Computing things for you

and then they you'll get back the proof essentially so that's the vision for this side of applications the other is something I spoke of as a running example which is when you consider computations or SN where the snar pro anyways does like really huge computation so for extremely large computations like fighting disinformation we'll have or even verifiable private machine learning inference because the learning model is what determines how big the circuit is uh first such scenarios again like this will be useful because you would be able to get a divide of work amongst all these servers so the burden is reduced essentially yeah so heading into how do we design zikas so I hope like

everybody's on on page with how the framework Works um the blueprint of the design is something similar to what was done in the collaborative zikis work which is identify the key building blocks in the underlying snars that we interested in so as I me we'd be interested in Groth 16 Marlin and plon and then we focus on designing you know these MPC protocols uh for these underlying building blocks and now there is an additional goal which was not a part of the collaborative zus we also want the desired efficiency so it cannot be just an MPC that runs on you know the regular shares and thus the same amount of work per server as the local prer we

actually want a pro protocol that uh sorry yeah we actually want a protocol that gets a divide of work uh among I saw I saw the king the king server just pinged you I see right there with its updator with its updator request sorry bad joke but yeah yeah sorry yeah go ahead yeah so um yeah so you basically designed MPC protocol but now with this added efficiency requirement that you know you have to also get a divide of work amongst all the servers or all the parties and once you have these two like essentially you head into essentially stitching all of them together and uh if it is a IOP protocol

like long or Malin you need to figure out how to do the F chir step uh and then you get to essentially the zikis as for SN so I'll not talk about the whole whole picture but all right suie I think we lost you there that may possibly was me hopefully it wasn't me but um we're still recording so you want to just uh present again suie and sorry about that make sure my

awesome all right let me minimize this perfect okay yeah sorry about that I don't know what happened cool yeah so I guess like yeah I was just talking about the basic blueprint um yeah so um I was going to say that essentially I'm not going to talk about the full stitching image but I just want to mention in case you're wondering how the um F step would be done in the case of like plon or Malin um you don't do the computation of the hash so I mean before that just what what does doing f mean like we in the if you're in the IOP

setting where uh you're building an interactive protocol uh public coin interactive protocol and then converting it to a non-interactive by essentially making use of something called a f transform uh you would be requiring to uh do some hash computations or random Oracle computations on the transcript uh to essentially compute the verifier challenges and this step you don't do inside the MPC so I want to mention here that um you build essentially the NPC for each of the blocks separately and whenever you need to do you know this fi step or computation of the hash you end up uh if you're in the semi honest setting nobody deviates from the protocol so you can get one of the

servers um in this setting since there's already a symmetry all the parties can send their shares uh to one of the servers and uh in in a hidden form of course because the zero knowledge also has to be retained and the single server can do this hash computation and then you know uh send it back to everyone so the fu step is something that you don't do over the MPC you do it uh outside the MPC you do the Reconstruction and then uh compute it uh so that's something I want to mention of how you would convert it uh into the fully non-interactive version of marlin and Blan but besides that rest is just like once you have MPC for each of the building block uh you're good to go

essentially you can just plug in that NPC and um you know you can use it with underlying SN okay so that brings me to what are the building blocks in these snacks that we're interested in so essentially you know they're comprised of these four operations once you have these four functionalities you can do the snar proof uh you can generate the snar proof just by making calls to these functionalities so uh of them there's only one of them multiscalar multiplications or msms which is uh which involves group operations um so it's essentially you have M group elements and M field elements and you require to do this kind of a product of the group

exponentiation um remaining all the operations are field operations so particularly we would require something called partial products uh which is specific to plon um where you requireed to uh essentially as the name suggests compute partial products of uh all these field elements all the partial products and uh besides that um if you're in the setting in any of these s any of these U snags uh you would be required to do computations on univariate pols and um specifically you know you need fft for converting between what is known as the coefficient representation and the evaluation representation and uh that is what ends up making uh polinomial

multiplication and division faster so this is uh something that you would also need if you're in the setting and uh that's pretty much it so these are the operations for which we need to design be able to design this distributed protocol uh or an NPC that uh essentially gets this divide of work okay so um that brings me to what is the you know key primitive we use to do this what is it that enables us to get this uh divide and that's something called pack secret sharing so before we before I highlight what pack secret sharing means let's start with something uh all of us here might have already seen in some form which is regular secret sharing so what is the goal in

regular secret sharing there's a single message a secret value which you want to split amongst these NN parties S1 through SN and um you know we represented by this uh in future just a Square Braes around M um and the guarantee here is that if you're in the semi honest setting as I have been saying the corruption threshold um by which I mean how many of these parties can actually be adversarial or how many of them can be corrupted by an adversary uh that can be up to n by two so up to half of them can actually be corrupt and you can still hope uh to protect your

secret against them right so what this means T of them cannot learn anything about your message M whereas if you get t plus one of them together you'll be able to reconstruct the message so this is what regular secret sharing gives and the most commonly used regular secret sharing scheme is uh for the threshold setting like this is Shamir secret sharing um and U this is something that we would have seen uh but extending on from here is what is spack secret sharing and um uh this is also this also can be very easily built from you know shami secret sharing and what it helps you do is instead of just secret sharing a single secret Vector in a sing secret value you end up secret sharing a vector

so you now combine M1 through ml L values and together you share them into these secrets S1 through SN so what you're doing is instead of just splitting one value into these end shares you're you can go all the way up to some order of n just like some constant factor of n values can beack together and you can share them together and the tradeoff here is of course with the corruption threshold so this cannot be unconditionally done uh it's that whatever you choose to pack together the L will determine how much you can tolerate in the sense of corruption threshold so this is the relation that will hold now which is you know combine the the number of parties you choose to

corrupt d uh plus the number of values you choose to pack that is now like at most n by2 in the semi honest setting right um so this is something that you would have to tolerate as a trade off it's not an unconditional thing why is this useful on a high level like um when you pack all of these things together what you end up doing when you compute anything on the shares will be a combined effect on a vector of values instead of a single value so as I'll head into a bit later the idea is that now you're combining the computation uh of you know several values by packing them together and reducing it to just

doing computation on these shares so packing will essentially help us get the reduction or or the you know split in the cost the way we visualize got it so the way to think of this is basically pack secret sharing is just a vector as opposed to a single value okay got it great yes yeah perfect so just to you know uh how do we compute on the pack secret sharing so if you have like these two vectors u and v and their pack secret share into let's say five shares then um addition is like simple if you add the shares uh the corresponding vectors get added uh so this is how addition will work uh multiplication will now be a hadm mar product so in in

regular shares uh we already know that multip multiplication to do degree reduction requires some communication which will be the same here but um the only difference is you know because it's Vector of values it's essentially a hadamar product so if you multiply the shares correspondingly you get a hadamar product of the corresponding vectors and this is now a 2T out of n pack sharing so if you want to bring it back to a you know T out of n which means T the threshold of the parties that can be corrupt um then uh you need to do some communication to do it but this is like similar so I just wanted to highlight this so that you're able to visualize how to do the computation on pack secret sharing so

addition is going to be local okay yeah so with this now like you know we're back to the goal and this is all the building block that we need uh we can focus again on looking at these operations and trying to do a distributed protocol for them so I'll start with the you know the most heavy and the most important component that helps us get the speed up which is the MSM part uh the multiscalar multiplications so uh this is the function as we as I mentioned before and the g are the group group elements so the key observation here is how do we secret Share Group values so whatever I spoke of right now as a value uh I meant those are field elements and you know

regular secret sharing or pack secret sharing all of them focus on sharing field elements like Shamir is something that works on only field elements if you take other secret sharings um you can make something work for group but in the setting uh of using you know sh me secret sharing the key observation that was made by you know uh this paper of collaborative ZN is that if you have to share a group element G power x what you can do is just compute shares of x uh which is in the field um and and then you exponentiate each of the share that is received using the same generator G so essentially you visualize sharing group group elements as just sharing

their exponents okay and this will be of great use in the in the MSM case uh as we'll see just in the next slide so we can just extend the same thing for pack secret sharing uh there is no surprise that instead of just Computing shares of you know this Vector of group elements you compute shares of the underlying exponent vector and then you can just uh exponentiate the shares that you get with the same generator G uh and that will be the secret sharing for the group okay so this is what we have have when when I say the group element is shared this is what we would mean okay so with that in mind let's take a example scenario let's say there

are 32 values so m is 32 and um it is our choice as to how much we want to pack together and as I said this is like a trade-off thing and we'll see in implementation what is a parameter that's reasonable to choose but for now let's say I'm packing four values together by which I mean the L uh in the pack Secret sharing is four so let's say this is the order in which I pack and this is something up to us like how we want to put these values together and that depends on the computation you want to do on them so here like uh for MSM you can essentially just pack them in a sequential order you know G1 to G4 G5 to G8 and so on so you pack secret share you know these group elements as well as

the field elements so all the inputs are shared now okay and now the you know key observation because of how this you know secret sharing of the group element has been done is that if You observe here while this is a product of group values uh it essentially ends up being you know a linear operation on the exponent right so this is something the parties can locally compute initially which means if you have these secret shares they can essentially just do a local computation and essentially receive you know pack shares of the single Vector uh where if you really look at it when you're you know multiplying all of

these group elements together uh the corresponding first entries of each of the vector uh you're doing a MSM computation on that the second gives the second value of this Vector the third the third and fourth the fourth does that make sense like you're just doing uh essentially this Lo local computation on the exponent because you have the shares corresponding to it and this is something the parties can locally do on the shares that they have right so uh on the shares that they have they can just combine these values in know you know like it's just a linear combination so addition on shares is like local uh and you're doing it on the exponent but this is so this is where

the tradeoff comes in I guess where if you this is where the trade-off comes in exactly yeah so instead of doing this uh you know product of M group elements you have like managed to pack them together and reduce it to just doing M by L so you're getting a split by l l is four here but whatever L you choose you're essentially reducing the work by that uh this is not the end of it by the way like so here we ended up with a single pack share of this Vector but to in a sense complete the computation of MSM we need a product of all of them as well right uh and this is something now you can't do you've arrived at a scenario where the single pack share has everything uh and you need to do a computation within the share so that's

something you won't be able to do and so there's a easy way out here which is to convert them into regular shares and this conversion is something that can be efficiently done if you have a Pack share of a certain Vector you can convert them into these regular shares of each of the components separately uh so each of them you split and then now you can do the same local operation but now on regular shares so you can essentially get the final output which is a product of all of these together yeah so this is like you know a high level of how you would do an MSM operation if you have the power of back secr sharing

essentially and um so the factor of as as Alex you mentioned the factor by which you get the divide and work is essentially the packing factor and so whatever L you choose you're going to to get a divide and work by that for the scenario and it would also be you know it'll be the Divide also that you get of the memory use cool okay so this is the good part like MSM is something you get full divide on and this is that's great this is what gets us to speed up um partial products is something that um I won't be talking about uh today something similar to um you know this where we managed to get the Divide and uh it's something

very specifically needed for plon uh so for that you can look at the paper but what I wanted to stress and spend some time on is the fft part because this is the component that if I can just and ask a quick question if you go back one slide sure sure yeah so this is like in the uh picture you showed this is like oh this is the normal servers not the king servers right so the normal servers yeah normal servers can do and another fft is what the king server quote unquote King doing basically got okay yes F50 is what need uh necessitates the king Ser or like this asymmetry is because of F50 and so that's what I wanted to spend some time on and uh you know make it a point like this is a problem with this particular algorithm

so if Z KS where to be built for something that doesn't use you may not have this issue essentially uh so you know just to recap FF is something again like all of us might be familiar with but just to put it in context of what is the form in which we look at the Ed protocol so what is the goal of fft you have this polinomial in you know coefficient representation where this AIS are the coefficient of the polinomial let's take a degree 31 polinomial uh for use case and we want to evaluate it on a bunch of points so the typically a polinomial of degree n uh can be represented in the form of evaluations uh by taking you know 32 points so if it is a 31 degree

polinomial you evaluate on on 32 points and for fft um the specific set of Interest are these roots of unity because of the nice properties they have and essentially that's what helps you get the speed up in fft um and if you were to naively do this evaluation you will take you know cost if it's n degree polinomial you take n Square time and what fft helps you do is get it down to n login okay so on a high Lev the it's a divide and conquer process where you just split the polinomial at each level into odd coefficients and even coefficients and then the way you look at combining them is by this equation where you just evaluate the odd and even polinomial on on the value X squ instead of X and this equation helps you get

back an evaluation on P okay so why am I like recapping all this you know one1 algorithms stuff uh it's to point out that um you know whenever you need to evaluate this polinomial p on the set W of roots of unity instead you've now reduced by the single step into evaluating the even and odd polinomial but now on W square and because of how roots of unity are the W Square essentially uh leads to just 16 unique values instead of 32 okay so what ends up going on in fft you recurse this and go on all the way up to where you know you split it and strip down into linear polinomial and then go back up

evaluating each layer essentially using the same recursive formula so in this example you'll go for up to five steps and then end up Computing you know from this level five up down so it's important to just visualize this to you know understand how the packing is done and that's why like I'm going into the painful details of how fft Works um so I don't want you to look at it as a whole but just this is just an image I had you know to uh highlight what is the computation or how how it's done across layer so as I said level five is where you strip down and essentially bring it down to this coefficients uh so A1 through a32 are the coefficients of this

polinomial and from there you have to do this you know evaluation down each layer um um until you get essentially the evaluation representation on W okay and the way it's done was the formula that I depicted before but in a sense what is it that's happening so if you just focus on level four you know we won't get into the details of the remaining but just to highlight the pattern here which is what we'll use to pack things together right is that all the left or the green highlighted values here get combined with the red values which is the right right of the the right child um on the right side of the root uh these values get combined using this sort of a linear

equation and the two sets of you know scalers that you use for it are the essentially two points of evaluation that you're required to to do so for level four right so level five has only one root of Unity on which you need to do things level four will have two roots of Unity on which you need to do evaluation and in a sense the operation that's happening is just this left Leaf if you consider them as a vector uh you know you're just doing a linear combination of them with the right side uh using these two scalers okay why am I talking them talking about them in this combined sense because this is essentially what gives us the picture for how we going to pack things together how we going to combine these values and

do a you know combined computation on them and so how do we pack them together the key observation is you know all the things that you're Computing on with the other things of course you can pack them in different vectors that is a prime necessary but to be able to do this uh computation on top of shares and that to locally because ultimately these are all linear operations right uh the key observation is that you need to pack these values as far away as possible okay so by that I mean you know you pack like A1 with something which is a left component but then it is like as far down this uh you know sequence as

possible so that you're able to do local computation on them for as long as you can so it turns out like the best or the farthest that you can pack them is by taking M by L uh + one as the next Vector essentially so that for this example would be that you know you pack A1 A9 and then shift it again with the same value so a17 a25 this is how you would end up packing okay so uh this is like something you may not be able to see right now but uh if you just like I I'll send send across the slides and if you stare at it for a while you'll realize that any other push you can't do to this packing this is the optimal way

in which which you can push things down and then you know as I pointed out before the level four computation is just doing computation on these Vector of values together using these scalers right so it'll be like a local computation on the shares corresponding to these pack vectors but unfortunately in spite of the farthest that we pack you can only do this local computation up to a certain point in this recursion so specifically you can only go up log M minus log l levels uh which is in this example three just to you know give you how it's done but after the step of computation all the things that you would need to compute on end up being in

the same vector or end up being within the share of the same Vector so you would need to open up these shares and um you know uh essentially do the computation on opened up shares or rearrange things so this is the m part if we were able to go all the way down this recursion without needing to do this by some way of packing uh this problem would not have arised so this remaining logal levels right even though you've reduced the input size in some sense already by doing these computation you still need to figure out how to do these remaining log levels of computation and that is what uh necessitates the king server so the really choice we had here is either you

know Ensure all of them get the split of work uh but then a lot of communication goes in like which means that log l rounds of communication need to happen and that's really bad if you look at the you know practical scenario so the tradeoff or the Practical solution that we adop adopted here is to use a king server so let me tell you how you would end up doing this so let's say you went all the way here and you are at this you know this particular level where you have the uh specific values from you know this level and continue want to continue doing this operation right so the key observation is fft is like a linear operation and um this is good which means that you know you can use

some form of a pre-processing of this form uh where you have some you know shared random values and uh you do like these last two layers of computation on these random values uh to get this why all this because we want to retain the zero knowledge component right when you're making use of things for the server you have to mask and give it to them uh otherwise like uh you'll essentially be giving secret value and the server the single King server can get essentially the witness uh so this is something we don't want and all this pre-processing is to ensure that you're able to mask the value before giving it to the king server who can then compute the remaining layers and then give you back the value that's the high level so

once you have this you know related M value you can as each party whatever shares they have they will just marks the shares at the end of this level three and send it to the king party who then reconstructs this but mind it now the value is hidden by this random padding uh and the King party can do the local computation of level two and one which is the final two layers and send it back okay so the final step would be just obtained by or the final value would just be values would be just obtained by unmasking using these SI and the the reason you can do this is because of this linearity here okay so you can mask things and then unmask them

later just uh because of this linearity essentially so uh this is like really a high level picture of uh where you would need the king server so as you're seeing here the king server uh needs to acquire all these shares again from all the parties and then do these you know computation um it is at this point reduced inide but not really because in FF you have the tradeoff between the number of polinomial for which you're doing versus so at the end of the day you're doing M evaluations right at each level you have M values so F50 is still doing essentially the king party is still doing linear in the number of field

operations yeah does that uh make sense yeah yeah makes sense yeah so this is the reason why uh because of F50 and like you know the specific feature of it um with pack secret sharing we at least didn't see how to get go beyond this barrier and that's why we need the king server essentially yeah so um hopefully I depicted like you know both the aspects of the work the one that helps us get like a great divide using pic sharing and then one that uh necessitates this asymmetry in some sense in the model um and partial products is something we have in the

paper which you can look at um and if you understood this then pack secret sharing uh essentially does help in a similar way for the partial products as well okay so with that I just wanted to uh come to the implementation part and tell you more on uh the numbers that we get so the this is specific setup that we used where the local prer We compare with um is like a 4GB Ram uh system and for the zss servers the king server is the only one that need needs you know high power so it's a uh yeah 128 GB Ram um but all the remaining ones can be like commodity laptops and in fact have lower power than what we gave to the

local prer which is they're all 2 GB Ram each and I want to highlight here that uh because of P secret sharing uh in our model which is again unique to our model in comparison to EOS is uh the more the number of servers we use the better is the benefit because you'll be able to pack more things things together and so as n is larger in fact for smaller instances of n we won't see any benefit this is just like because of how pack secret sharing works so we really go at it uh with respect to larger ends and the more servers you engage the better it is so I I had a question on this that I was actually waiting to ask because I'm assuming some point but I guess one one dimension that seems like it could

be a trade-off is bandwidth right I think how how does bandwidth I guess to what extent does bandwidth become a constraint I I have a I have a gra graph on it um so yeah yeah yeah I have a graph on it yeah yeah so I'll show you just shortly and then we can talk more when I get that okay so the first set of like graphs is just to show you you know how far we can go in terms of constraint size and really how the time gets divided uh so uh the setup we take is that you take 12h servers to the computer ation um and the packing constant is um 32 and the number of corupted servers proportionately will become 31 which

means the adversary can take over 31 servers for this particular setup uh firstly for memory exhaustion we already see that the weak servers uh or essentially the smaller ones can already handle 16 times more constraints uh than what like a single single local prer can do before running out of memory so this is good so as you see in the line the orange lines correspond to the local prer and the time they take and if you see here this orange line stops set somewhere to part2 for GR 16 whereas the blue line which correspond to the Zas can go all the way up to two part25 so we can handle more uh constraint size before you run out of memory um and um in terms of running time if you see uh

this is what I briefly mentioned when when I highlighted our results we get a 22x speed up over the consumer machine um so I kept saying that you know the divide that we wanted to get was by the packing factor which is 32 here so why not 32x speed up and this is something probably already guessed uh one is of course the fft because you don't get complete equal division of work for fft but there's also one more reason which uh is uh something to do with partly both implementation and something we haven't figured out theoretically as well which is we don't push for um or we don't have the implementation with the PIP iner so when you're doing this MSM computation on shares uh we did not

figure out how to do the distributed Pender algorithm for that step uh so that's why like um while as when the MSM is done locally there of course the PIP inure is being done so it's not like a complete split in that sense because of uh this optimization it's uh something that we believe can be done but we didn't do in in this implementation number so that's why like the speed up is lower than um you know what we expected and to what extent I guess like what's the breakdown between one and two in terms of possible Improvement I guess even if you did a perfect PPP Ander optimal pure you'd still not get to 32 right so I guess but how yeah you would still not right right but uh it would really help because it's still like on

the group operations that you get some improvement so like you might still do uh much better than uh working on with the F50 stuff like like essentially the F50 stuff is something that it will play a role more in the sense of how much more you can tolerate before the memory gets exhausted but uh really in terms of the number of calls and how specifically for these protocols right MSM is really dominant so that's what I was going to get at here if you see the graph the red component in these bars are essentially indicative of the group operations uh so like the major part of the computation time is the MSM computer uh and the yellow component is the field operation which includes not just fft but but all

the other things so that is also why in spite of not getting a full divide we are getting in spite of it like a 22x speed up because MSM is like getting split so if you do the Pinger I'm guessing like the Improvement will be um like nicely a little bit more it's not going to be like a just a very small Improvement is what I was getting it yeah so this is something we don't incorporate here in the implementation yeah and U this is the you know in terms of bandwidth if you have like different uh different bandwidths this is just this graph just depicts how to uh how how the you know speed up varies uh so if you fix the constraint size to 2

power 19 um which is itself like large and as I said before the packing constant and the number of corrup continues to have this relation so this is the optimal setup of L that we take which is n by4 and uh for for this if you see you know so the um I want to stress here that the communication that happens uh we don't do communication of every server with every other so the topology of communication that happens is going to be just a star topology by which I mean all these small servers uh only end up communicating with the King server so you don't need every every server to talk with every server so that really saves up on a lot of it and in fact the

choice to keep a king server uh for the 50 instead of having something where every party needs to talk to every other party uh was like a conscious choice to avoid this you know slow down see so the king server role in this place in this in this protocol is not just the fft computation it's also effectively the primary node where everybody communicates with it's it's almost like coordinator effectively yes yes exactly and this is something that uh naturally appears in the MPC protocol for the other other operations uh just for for F50 you know it's something that you can't even do without like you need this one party to do the evaluation but for the remaining like uh you can make a choice uh but you know having the star

topology really improves upon your uh time because the communication um like the topology of communication really affects right so if each person needs to talk to each other person there's a lot of weight time so the overall clock time really blows up in that case yeah so that is something just wanted to s almost make me wonder if you increase the number of parties even more I mean it seems like basically what the graph implies here is that you're continuing to get Improvement as you scale up you can sort of see it's starting to I would assume at some point it levels off because of the bandwidth but like clearly I mean 128 is you know you're still getting improvements so it' be curious to see what you like if you had

256 or even 512 yeah yeah definitely like it would be it would be good to uh so like I said that's the I think uh the good part about the this model in addition to of course the you know intricacies of whether the client is online or not uh that's the other difference that I wanted to point out with the EOS I think like um because of the way that MPC works it works better for like smaller number of parties so when you have like two or three parties or two or three servers doing the delegation uh us already gives you that speed up whereas in our case like something like even eight eight servers won't be helpful yeah yeah because yeah constant reduces the the you know if you think about how mining pools work

in like Bitcoin for example right typically there's a large large number of smaller servers right and you can imagine the coordinator of like the mining pool operator could be the king server effectively and then you'd be able to turn a Bitcoin mining pool into a proving pool in this model based on the fact that you can have a lot of parties which is kind of right inter right yeah yeah so that's really uh the takeaway as I would put it um yeah so I just wanted to conclude with you know some interesting directions which already were I think brought up uh during the course of the talk but just to summarize uh so of course like the one natural question here is to get rid of the sking server uh and you know as you pointed out like way ahead in the

talk Alex you can use like essentially non F50 based snacks and try to build Z ass for it so this is something we're working on as followup uh and it's an interesting thing to do and this will not only help us divide perfect divide of work but also split of memory so it would help us you know get to much larger constraint sizes before we run out of memory so that's really the goal with the the followup and of course like uh militia security as I said can be handled it's just that we don't have an implementation explicitly for that but um it's something that's uh at least not a roadblock for us directly in the head in sense of the theory sense so we don't have an implementation for it so um getting to work it work it out

for the militia security is also like interesting to have as an implementation and of course like uh you know I as I said I didn't focus on the aspect where the extended witness was itself shared by the client and how do you patch everything together and make it work for endtoend applications uh this is interesting and in fact um this is something work in progress where uh uh this company is helping us uh or rather like they were interested in actually building out something targeted to Applications of their need and uh they this is like uh really work in progress now but uh their goal is to build zasas for Groth 16 and in the end to end sense so I have

everything set up including the extended witness and make it work like a service what would the what's the circuit because CR you're hard coding it I guess so do you know which circuit they're implementing yeah so right now I think the uh the test versions are working for like hash functions they're just working with like a bunch of Sha but but I don't know what they're like all the all the use cases for which they would need it I don't know that's the for yeah yeah I was goingon to say on that front like one I to me I think the one interesting especially given like the like this this work reminds me a little bit of diic and I think you obviously talked about a little bit how it it it builds on it and you kind of have more privacy in this model as the

client but a DI you know diic part of that that dire the interest in that research was around you know being able to compute gigantic circuits in fact I shared in the chat here this may be interesting to you and your co-authors um this is a z prize we did a uh competition for a plonc uh you know so using plon to compute diic or rather a diic style model for plonc for a huge circuit I believe it was two to 28th in this one two to 28 in this one right and that I think for applications I mean one one obvious application area that I could see for this is zkl type stuff right so even relatively simple models uh in the EML world like even

classifiers you know are huge in when implemented in circuits and so I think two to the you know two to the 21 is probably several orders of magnitude too small for that but if you could get and this might this might actually be a case in which you would want to get many more machines right if you weren't suff like if you were still getting speed UPS up to like you know two to the you know 9 10 11 machines then yeah you could you could Implement some very complex machine learn excuse me machine learning stuff and you know and have it be practical while while not having to you know obviously in the client they the advantage of that over diic is the client doesn't have to reveal the the you know all the all their private

information right so right right that would be if you guys are interested to you know ex if you want to think about a motivating application for future work I would recommend that one because I think there's a lot of really obviously there's a lot of interest in AI ml right now I think there's also a lot of interest in applying ZK specifically to that area so could be a cool Direction yeah definitely yeah so I mean that is a uh motivation for us to like you know keep looking at this and uh improve in terms of like how much more constraint size we can actually tolerate using you know making use of the power all these servers completely essentially yeah that's the it's an interesting work follow and this is maybe a good point for those just watching or following along as and then who are going to watch

the video I I pasted some links here which the people on the you know watching the video after the fact are not going to see but Z prize Z prize is all about Hardware acceleration for ZK there's a repo maybe I'll put a a link in the video description but there's like a lot of off-the-shelf things in there like a very very optimized MSM pippinger algorithm forus and FBG and so for folks looking you know to potentially improve what you've the work of you know or implement this work you know you can take some of that off the shelf itely yeah yeah some get some immediate you know extra speed up yeah definitely all right cool this is great uh does anyone else have questions well I guess I hog the mic I

successfully hogged the mic and and scared everyone else from asking questions but um Su I thank you so much yeah I really appreciate this is this is a great presentation and I think really interesting work sounds like some exciting directions to take this in the future um thank you very much for being here and for presenting this for all of us yeah thank you so much for having me yeah this was a pleasure to talk about this yeah thank you and I guess it's also worth thanking your co-authors for working on it with you be here but um it's great great to see uh you know hopefully you guys will will be working on more stuff like this in the future yeah definitely definitely looking forward to it yeah thank you