zkStudyClub: EOS - Efficient Prover Delegation [Pratyush Mishra - Aleo]

Transcript

hello everyone welcome back to ZK Study Club in this Edition we have pratyush Mishra a repeat guest uh he is going to be talking about EOS his efficient private delegation of the case in our approvers paper that he co-authored with Alessandra chiesa Ryan lemcool and you know Zhang from UC Berkeley uh pratyush welcome back and take it away hi uh yeah thanks Alex fantastic to be back uh hi everyone so sorry I have a little bit of a cold so I might be a bit lower in energy than normal um but yeah so basically uh today I'll be presenting a paper EOS which constructs uh efficient delegation schemes for uh

zika snack Hoovers okay um yeah so this is Joint book as Alex said with Alessandro Ryan and Nino okay awesome so probably for this uh audience you know we don't drink to go over snacks but I'll still do like a quick overview so basically uh but ZK snork is this protocol between approver and a verifier the proofer is making some claim that uh awesome function f and uh partial input X to this uh function it knows some private uh rest of the input W or private input W that satisfies the function so you can think of f as being

the function which checks the data uh W is sort of the pre-image of some hash uh X right okay so there's there's these two parties proven verify the crew are mostly convinced to verify that this statement is true then what is EK snack allows approver to do is to compute uh very efficiently a very short proof um attesting to the truth of this uh fact which the verify can then take uh and check um in time much shorter than the time it actually takes to run the function itself or to run the computation itself right

um and the key property that uh you know we care about in this talk besides the standard completeness soundness succinctness properties is that a zero knowledge which basically means that this proof reveals nothing to the uh verifier um nothing about doubling to the verifier except the fact that this claim is true so the only thing the verifier learns and the hash example would be that okay there is a prover knows the pre-image uh for this public hash string X right okay uh do we have a question in the chat okay no um uh produce just so you don't get distracted I will I'll let you know if

there's a question in the chat I just I'll be welcoming people as they come in and I'll just prompt you if something comes up so that way you don't have to switch back and forth between your screen okay awesome thanks all right uh yeah so the success properties basically just says that the uh verify running time is not shorter when the proof sign is much shorter than the size of the function okay so you know fairly standard things so again this is everybody in this chat probably knows uh and this call knows is that there's you know been tons of applications of um serial knowledge proofs over the past two years I mean also over the last 30 years but specifically also in the last decade or so so things like private transactions private smart contract

systems uh you know sort of these decentralized multiplayer games which have hidden state but are running on public chains um things like Anonymous credentials um you know bunch of other applications um and all of these sort of in some sense rely not just on the succinctives part uh uh um of uh of the stocks but also on particularly on the Zero knowledge part like they really rely on the Privacy aspect of these um these fruit systems okay all right uh there's like only a bunch of these applications but out of there I suspect like they use

they the use of these systems in the real world is when someone hampered by the uh poor relatively for proven performance of these uh of the best proof systems that we have today right um so for example if you take Route 16 which was kind of the state of the art I mean just a couple of years back um if you want to do like a simple task such as hashing uh some string with stratu it takes say 140 seconds this is on my machine like last year uh probably has changed but I sort of you know there's like this massive orders of magnitude gap between the actual computation natively on your computer

and generating a proof of that same computation right um and sort of you can get around this by doing some clever circuit design and stuff but you know what most applications find is that there's still like at least a couple of orders of magnitude difference between running the computation uh natively and actually producing a proof for it uh yeah this is on a very limiting for especially as you sort of move into more expressive applications such as uh these private smart contract systems where users would want to run out they want to prove the execution of some arbitrary program right and it's not for end user trying to do this proof so basically all in all uh it's quite important to you know use every trick

that we can uh or every technique that we can come up with to really improve the performance of including to remove it from the bottleneck phase from the bottleneck in these applications okay so one approach besides you know really optimizing the proof system would be defined uh you know Outsource the proof generation from your potentially weak device to a much more powerful one so say I have a mobile phone right and I want to generate a proof on it at some point I'll run into some uh you know performance like the sort of the limitations of the CPU or of the memory or you know the proof integration is taking uh eating up too much battery on my phone so it's like a bunch of

constraints right and you would like to minimize sort of these costs to allow you to scale to larger applications okay so one idea would be to sort of um say okay I'm going to generate the proof on my phone I'm instead going to Outsource it send over the this proving task to some more powerful machines say somewhere in the cloud maybe it's my desktop at home you know there's a bunch of options okay so I'll send over the public input and private witness to this powerful machine and then that machine will do the computation and send me back the proof which I can use in my application all right um but okay this works but again you know in end up being limited by

you know what your single machine can do so people have come up with uh systems that allow you to sort of you know Leverage The Power of the cloud to its fullest extent and actually you know use uh multiple machines to collaboratively generate your proof right so instead of now a single machine or I have like this cluster of machines and they collectively will generate uh the proof for me okay um okay so we know how to do this uh you know this is um work from uh we at all from a few years back um and it works and like probably you know

this was like the first time in the first uh work in this line probably this today if we took our Tech modern techniques because improve on their results quickly uh but overall the there's still a problem with this approach right especially for these privacy focused applications that I mentioned earlier the problem is that all of these workers they learn what the private witness my private witness was right um right and in the scenario where these workers are located in some public Cloud you know the public Cloud uh is now if it is eavesdropping or whatever you can

learn my uh my witness right and sort of de-anonymize me when I'm trying to use this application all right so ideally we want a solution which allows us to do this Outsourcing but in a privacy preserving manner so the the workers that I use they don't got any information about my witness right so this is uh now our new role right so we want to come up with some sort of Delegation protocol or scheme where there's um yeah the approver uh the sorry the mobile phone uh provides uh the public input and then some sort of obfuscated or encrypted or hidden version of the witness into the protocol

um and then like there's some interaction or some something goes on inside the protocol and at the end um the phone gets back the proof that it wanted right um and there's two goals here so the first one is that efficiency so you know we we want to have privacy but we still want to it to be the case that the mobile phone is not doing a lot of work because again you know there are some uh constraints on the amount of computation it can do so overall its work should be much less than just generating the proof um locally and the second is obviously privacy right that at the end of this protocol uh the delegate has witness should be entirely hidden um from the worker right so it should

not learn this this machine should not learn any information about this private witness w all right okay so this is the setup so far um any questions about the motivation or the protocol setup yeah feel free I guess uh ask questions in the chat or yeah or whatever is the appropriate protocol so no questions so far Perfect all right so okay hopefully I've been very clear and people are totally understanding what I'm saying uh but if not again for you to stop um okay so our this is our setup we want

to construct this delegation protocol so let's see how we can try to go about doing this task okay now unfortunately um when you have just a single worker as far as I know there's no way to really realize this this protocol in this setting without using relatively heavy weight uh cryptographic tools like um fhe so and the problem with these is that or at least like some maybe limited homorphic encryption right um when the problem with these is that probably the the act of just using this this tool is going to make uh even the outsourced prover like the work of this outsourced machine much much

higher than if the uh like the IQR running time of the delegation protocol will be much higher than just running the truth locally on your generating the proof locally on your phone right uh so anybody want to have a system which avoids these heavyweight tools like fhc um but it's very unlikely that we will be able to do this in the setting of just a single worker machine so maybe we can relax our privacy goal a little bit and move to maybe a setting where we have a little bit more flexibility and so instead of saying you know we want to have just one machine and we want to have privacy against that one machine

um we'll relax our goal and say you know we'll want privacy um against a bunch of machines as long as one machine is behaving honestly right so in our delegation protocol now um sort of the phone the delegator provides its witness in the obfuscated form as before and then now these workers are sort of engaged in some protocol with each other with each other and at the end of this protocol they are able to generate the proof and send it back to the delegator right so the efficiency goal is um the same as before it should be the the delegator's work should be much less than doing the

proof itself [Music] but the second goal is now change so instead of saying that you know we have one worker and we have privacy against that one worker now we have a bunch of workers and we'll have privacy against of the witness against these workers as long as one worker is honest and sort of following the rules um of this delegation protocol right so sort of um n minus 1 threshold so you know in this case up to two of the workers can be dishonest but as long as one worker is honest and following the protocol rules then things should um be just fine and uh we should be able to get the product get the

uh proof it'll be a correct proof um and nobody was on the witness all right so this is now our new goal and maybe let's see how we can go about actually achieving this relaxed careful privacy goal all right that's out of the the task of this paper so what we do in uh uh this paper is to construct uh these delegation protocols for stocks that are based on polynomial iops but I suspect also the techniques in this capable generalize uh to to other systems as well but we focused on polynomial iops

because these are the most uh snacks based on polynomial iops because these are the most uh I guess state-of-the-art systems where everybody is using in practice nowadays all right so particularly we show how to construct delegation schemes or protocols for uh uh you know popular polynomial commitment schemes such as the kcg and the bulletproof for ita-based PC scheme um the Marlin polynomial IOP but I suspect should be easy to do it for say long also and then sort of any snark which relies on these components so sort of our our delegation protocol for this not is in some sense generic you plug in the appropriate delegation

sub protocols for the underlying polynomial IOP and the underlying PC scheme and you should be able to get out uh delegation protocol for the snark as a result right and sort of um this is our theoretical contribution along the way we have some interesting results on what kind of tools you would actually need to realize this even with malicious security so even when your workers might deviate from the protocol um and we'll cover some of that today but sort of doing the Crux of it is not just a theoretical instruction um we were actually able to implement and evaluate these protocols and sort of the the takeaway is that

delegating from a phone we found was um with our protocols was like up to 26 26 times faster than just running the I'm trying to generate the proof locally on the phone itself right and furthermore it allowed us to scale to proving larger instances and were provable on the phone itself right because a lot of these stocks they have high memory requirements so even if you're okay with eating the whatever time it takes uh you're okay with that cost you might still run out of memory when you actually try to generate the proof so if you do if you are delegate then maybe you can prove larger instances uh when you're not limited by a memory budget okay awesome so this is a checkpoint so

this is a summary of our results uh I'll stop drink some water and also see if there's any questions anybody has anything there's no questions in the chat the only question that I had and I know you're going to get to this later but maybe it's just interesting to State now is what uh obviously there's a lot of different mobile phones out there so I guess uh how should we think about this 26 times faster uh is this like my iPhone 14 or like a Nokia like from last year so this was like a pixel 3A or something uh so I was like definitely not new I think it was newish when we did the evaluation which

is like uh so this paper has been in the works for a long long time almost two years now uh so a Rel but a relatively modern smartphone I mean not you know not not state-of-the-art but you know reasonably modern probably with regards to you know probably the average of What the mobile phone technology level is for most of the world yeah yeah so it's like a I guess it's slightly above the like middle and uh phone but yeah it's also like there's like what uh new like two three years ago so now it's like somewhat old um so um yeah so I think uh it's uh if you took uh maybe a model phone that it

might be the Gap might be a bit less but then also there's like a wide distribution in the power of these of these phones so I think yeah this is the average number you would expect to see I mean probably you're going to be more limited by the bandwidth that you have on the phone um because as we'll see so maybe so maybe this is a good point to ask was this done on a 4G network or a 5G Network 45 50 Mbps connection if I remember correctly cool so slower than 5G definitely um got it if you want to use this on uh on data then you would blow through your data cap if you had one very quickly unfortunately there's like a large

uh communication requirement basically you have to as you'll see you have to send some like a linear in the witness size like the R1 CS weapon size for example a vector to the the local machines so cool and it'll be good to see it as a way to sort of work around that in future work but yeah cool uh thanks uh that's I think unless anyone else has questions uh I don't see any in the chat obviously anyone feel free and just I mean I'm assuming Patrice you're okay and uh yeah uh also yeah just if you need to take a break pratish we need to stop pause for a few minutes to give your voice a rest so they have a cold uh don't hesitate just

yeah we can we can edit that out of the video so don't worry about it thank you yeah no I think for the time being I'm okay but yeah I need to stop then I will great okay awesome so all right let's see how we can actually go about constructing these delegation schemes right and sort of a natural starting point is um this notion of multi-party computation or MPC okay so uh what is MPC so it's basically a way for multiple parties to come together and sort of jointly compute um some function f over their inputs in a privacy preserving manner so in this case you know there's these three parties they have X1 X2 X3 and they want to compute F of

um you know X1 X2 X3 basically an MPC protocol allows them to do this um while completely hiding uh all information about X1 X2 and X3 except for whatever is reduced by the output right so um yeah this party 2 doesn't learn anything about X1 and X3 except for you know this result and same for the other parties so yeah this seems like kind of uh you know magical thing but uh yeah we've known how to construct these NPC schemes for the past yeah 30 years almost now and we have like some relatively efficient constructions but in

reflection marks efficient in this context means still like a 100x slower than the native computation right uh but okay they exist right and they are efficient in cryptographic terms okay so let's see what one such construction would look like and this is sort of based off of the speeds protocol if you've um heard of that but you know I won't assume what that is we'll cover what the construction looks like right so basically this NPC protocol the first thing you have to do is you have to express this function of this computation that you want to do as a circuit just like in Starks right so second alphabetic circuit over some finite field um like some Z mod P or some prime P right

um and so if X1 X2 X3 are sort of the individual parties inputs then sort of you will run some computation um over these X1 X2 X3 uh with some additional multiplication and equality and maybe some other Gates Right but so this is a standard arithmetic circuit model nothing uh fancy right so how do you actually go about executing the circuit once you you know have it and once you have the party's inputs so the first step that each party does is it will share its input using some secret sharing scheme so what is the secret sharing so basically it's a way to take your message and and split it into

um if there's end parties like n um uh sort of related messages such that um as long as I am missing just one of these messages one of these sis for example uh the rest of the SI is revealed no information about the message M right so in say in the two-party case uh if I don't have the other parties share then I learn no information about the message that is supposed to be encoded inside the secret share right it's completely perfectly information theoretically hiding right but the moment I get all of these shares I can sort of add all of them up and

reconstruct um the original message all right so if I have all of the shares and there's no privacy but if I'm missing even one share then there is full privacy and so you can also Define uh SQL sharing schemes which have a more threshold notion of security so you know if I have at most say p minus one shares for T sub threshold there are a lot of information but the moment I have t-shares I can recover the uh uh the encoded message and right but in this in this talk we won't talk about those schemes um let's talk about this very simple additive SQL sharing where just you have

to have all of the shares to recover the message okay anyways that's background on SQL sharings so every uh party secret shares their X1 X2 X3 to all of the other parties using the SQL sharing scheme and then basically the parties evaluate the circuit gate by gate on on these inputs right um and how does this proceed well for relation gate the key idea to notice is that these Shares are additively homomorphic so if I have a share for x and I have a share for y then I can just add my shares for x and y and I can I'll get a share for X Plus y okay so these shares have a very nice additive

homomorphism um so if you're doing additions and linear operations in general then there's no communication things just work out fine but if you want to do a multiplication gate if you want to evaluate a multiplication gate then there's a bunch of um you know different kinds of protocols that you could use so I'll just list a few of them we won't go into in detail on how these actually work but we can talk about it later if there's you know people are curious because like these triple based multiplication protocols you could use linearly homographic encryption uh based protocols oblivious transfer based protocols there's like a bunch of these protocols which allow you to do this

multiplication but the common thing in all of these uh the common property of all of these multiplication uh sub protocols is that they require interaction between the parties and so this really ends up being usually the bottleneck in uh using MPC the moment you have the multiplication you need to do a network round trip right even if the computation is cheap and it ends up being relatively cheap for many of these multiplication protocols the moment you uh encounter a multiplication gate you have to start interacting with other parties and sending information over the network and basically incurring the network ground trip um time at least

right and uh yeah it's it's so really what you want to do when these NPC protocols is a minimize the number of multiplication gates in your circuit but also sort of minimize the number of consecutive multiplications so when the output of one multiplication feeds into another multiplication right this is called the multiplicative depth I really want to minimize uh the the this multiplicative depth because it determines the I guess the sequential like number of network round trips that you need to make at least okay so yeah that's really um

roughly how these um well this simple NPC works you know most of the secret sauce is actually inside how you implement this multiplication but we don't really care about it too much and we'll see later on how we can realize in our delegation setting very simple protocols for doing this multiplication okay so any questions on the model upon secret sharing and anything um if anyone has questions feel free and jump in but yeah I don't see any so I think we can just keep on rolling thanks okay awesome

all right so this is the background in NPC um so startup at first glance this seems like the perfect tool to use to construct a delegation protocol right so what we do is we'll have these workers so what we'll do is personally have the the uh the delegator sort of secret share it's witness with all of the workers right so um run the SQL sharing protocol uh to generate these so in this case three three secret shares um of w and send W the the first Secretary worker one the second one to worker two and the third one to work at three right and then these um workers will run some FPC protocol for

the circuit which corresponds to the the zika snack approver right so you somehow encode your your approver as an arithmetic circuit and then you run an NPC protocol for it okay so this seems like conceptually simple right and you might be asking okay why aren't we done well the issue is that as I mentioned before um NPC is you know has some of the same limitations that starts that the overhead is quite High so one overhead comes from the fact that um your circuit or the smart grouper might be quite large um in particular right you need to support field operations uh uh but also group operations and random Oracle and hash calls right and it's not like

you're doing like a small number of these uh you have to do large uh like a large number of these for example to compute msms to compute ffts um you know General polynomial arithmetic if you're using things like plookup lookup protocols here we have to do some sorting in there as well so basically it gets um you know the circuit itself can be quite large right um so we will first have to figure out a way to you know how to optimize this circuit and secondly you know even if you do that circuit optimization you're still going to end up with some overhead just from the

MPC protocol itself right so as I mentioned these multiplication is required interactions so if you have a large number of multiplication gates in your circuit or even a large multiplicative depth um they're going to end up with a yeah bring a lot of round trips in the protocol which will slow you down and maybe this doesn't matter for like a small uh circuit but uh you know as you scale to larger circuits you're sending a lot of information over the network and these NPC protocols and you'll be sending at least like a linear in the witness size you know information to the other workers so you will be running into some bandwidth constraints there okay so you really want to uh figure out a way to

reduce or make your multiplications as efficient as possible um furthermore like your IPC protocol might require some pre-processing so for example the speech protocol does and the most of these pre-processing protocols uh require use of heavy cryptography such as you know photomorphic encryption or some notion of oblivious transfer or other such schemes right um uh compared to the online phase of these schemes is computationally uh very light it just requires some field operations like field additions and multiplications um so yeah we want to figure out a way to reduce this pre-processing overhead and finally if we want to achieve

malicious security and you know it seems like a good goal to go for we don't want a privacy to be compromised or the correctness to be compromised uh when the workers sort of deviates from the protocol in summary so we would want like security against malicious workers but for all of the schemes that I know of uh right in the sort of n minus one out of n uh threshold scenario right malicious security requires at least a 2X overhead compared to uh the semi honest protocol right um and so basically you know if you use these games you are immediately just leaving uh like 2x uh

performance Improvement for your delegation protocol just on the table right there right and in practice this actually grows larger because okay you actually have to communicate 2x over the network and your network might be slow things like that right so as we see like some prior work which in this in this model the best lowest overhead they can get is is 2x compared to sort of local grouping um and we'll see in the evaluation uh I don't get about this okay then how our protocol gets about um performance okay so the takeaway from this slide is basically yes you can try to use NPC but there's these two obstructions that we need to overcome first we need to figure

out a way to get like very efficient circuits for Starks and second we need to really sort of optimize our NPCs for our application um setting Maybe by taking advantage of particular particular uh properties of our of our application uh yeah and generally sort of try to like really optimize the heck out of this uh well the underlying MPC scheme okay um so maybe let's see how we can do each of these um tasks uh one by one and we start by looking at the circuit authorization all right so our goal is to construct these efficient circuits for Z case not proofers

and as I said before in this talk uh and in this paper we focused on a particular kind of snark namely that those which are constructed by combining polynomial irps and PC schemes so this covers um you know Sonic clunk Marlin all the variants of Planck all the subsequent follow-ups to Marlin all of your plookup uh you know you know lookup table protocols everything sort of Falls essentially in this in this paradigm right um and just to be clear on what just for the viewers of this video to be clear on what doesn't fall on this Paradigm this would be like the Fry based protocols would not fall in here is that correct so you can technically also cast the fry uh base protocols like something like

um so Stark or say plug it too as sort of using the the fry protocol in some sense as a polynomial commitment um but using um yeah but it's like a it does require a little bit of a perspective change in doing some work to put it into that into that Paradigm um but yeah for other reasons actually we won't be able to support these uh IOP style protocols uh impact because you sort of heavily Leverage the homomorphic nature of a polynomial commitments and PC scheme and like say the fry PC scheme or the pieces scheme that you could construct from fry is not uh additively homomorphic yeah yeah got

it that's awful uh thank you um sorry to interrupt yeah fantastic question um awesome right so coming back so basically in this talk we'll um uh yeah we focus on these piop based starts and let's do a quick recap of how these work so basically this uh there's this polynomial IOP component right um so think like the polynomials in Planck or Marlin or whatever is your favorite polynomial IOP it's your snack approver runs this polynomial IOP approver to get out some polynomials and it invokes this polynomial commitment scheme to commit to these and this happens over a bunch of rounds uh where and at least

around the verifier in turn runs the polynomial IOP verifiers we generate some challenge or some Randomness or whatever sends this over to the the other side and you know this happens a bunch of times until sort of we're done with generating polynomials that we have all of our commitments and at this point uh we want to show that okay these these polynomials inside these commitments have some relation they satisfy some identities or whatever right and we'll do this by querying these identities at some random points essentially right so we ask for the evaluations of the committed polynomials at some evaluation points um and we show that these evaluations are actually the correct evaluations by

using an evaluation proof or an opening proof that is provided by these PC schemes okay um and sort of regenerate this evaluation proof along with the corresponding evaluations and you send this over to the verifier who can invoke sort of some decision procedure on these evaluations and also will check the evaluation proof to make sure it's actually valid that the evaluations are correct okay this is an interactive version for all of the Paranormal iops that we care about um there they're what are called public coin polynomial i o keys so you can sort of replace the verifier with a hash function and this is the fee action rate transform okay um

now this is a high level overview of these piop and PC Plus PC snarks right and this is a paradigm underlying uh Sonic block Marlin Etc as I said okay so this is the construction let's take a slightly deeper look at what operations are performed by the snack approver in this uh in this type of construction right um so focusing first on the polynomial IOP approver right well it's a polynomial IOP and the output of the previous polynomials so you can imagine you know you're doing some kind of polynomial arithmetic but the polynomials are defined over some

Fields say FR right um in particular like you're doing a bunch of uh operations such as ffts uh things like sub checks um you're doing polynomial evaluation polynomial interpolation basically a lot of arithmetic with polynomials and these polynomials have degree that's linear in your in your witness size at least right so uh you know for efficiency what we want is that our circuit that we designed for our snack prover it really should natively support operations over this field FR that's used by the polynomial IOP program right

non-native arithmetic which is quite expensive um I mean it's expensive and Snorks is going to be much more expensive in NPC where it's more difficult to use tools like um you know look up uh uh lookup protocols as well as custom gates to reduce the overhead okay so ideally we want to support native operations over FR all right okay so that's the constraint from the piop side well what about the constraint from the polynomial commitment side well you know looking at popular column and IOP such as the kcg scheme are the sort of bulletproofs or inner product argument based piops underlying say Halo 2 right what we see is that

these polynomial iops they require so they do a lot of elliptic curve operations over an elliptic curve uh who whose order is R right so which has a scalar field equal to fr and now for security unfortunately um these elliptic curve operations themselves require you know some field arithmetic some underlying field arithmetic but this underlying field arithmetic is over a field SQ which is different from FR right so each elliptic curve Edition elliptic curve doubling or whatever you're doing right it requires operations over a small number of operations but still some

operations over fq which is not equal to fr all right um so okay but again still we're doing a lot of these uh elliptic curve operations uh during linear sized msms for example so you would really want to sort of be very efficient uh and have your circuit also be native over F Cube somehow right so you want to be native over both FR and fq right and uh unfortunately we don't actually know how to do this this is a problem we'll see how to resolve the next step okay um this is the this is the issue from both the Pio p and the and the polynomial equilibrium side but we also have to

compute uh this random Oracle in some sense inside our circuit right um and doing this would require us to somehow instantiate the random Oracle with some sort of NPC or snark friendly hash but unfortunately even the most efficient hashes that we know of still have relatively High multiplicative depth and a large number of multiplication multiplications um so yeah sort of we're limited by we you know we will have some okay we're not doing like the hash is another like a large amount of data but still we'll like we'll be the sort of our sequential right so we can't proceed to the next

round it will we've computed the the action hash for that round so we're waiting that we have to wait at least for the multiplicative depth of the a hash circuit to to before we can proceed with the rest of the protocol um we have a question in the chat from Dara uh do you want me to read I'll pause for a second unless if you want to just say it yourself otherwise I'll read it okay the question is uh oh uh okay so the question is does using a cycle of Curves help that's a good question so I haven't really thought about it um so

maybe it could help but the so like unlike snarks where sort of your the snack construction itself restricts you to using a particular elliptic curve right here the MPC protocol isn't necessarily it's not like um it the implementation of the NPC phone call internally uses an elliptic curve right so I suspect um I mean maybe there's like some some interesting protocol that you can develop that uses a cycle of Curves to uh avoid you know not to sort of get around this this requirement of fq not equal to fr but I suspect um you know we have more flexibility

here compared to the stock settings so we don't have to resort to tools like disciple of Curves great thanks yeah but yeah that's a good question maybe there's some interesting uh protocol ideas for future work that we can Leverage okay so you know we have these three constraints we have to compute FR arithmetic we have to compute these group operations and we have to compute these random oracles uh all of these efficiently right so let's see how we can get sort of resolve all of these constraints simultaneously um and there's all this problem of

supporting multiple kinds of these operations right um and then then after that we move on to okay how do you actually if you want to figure out how to support these operations how do you support uh lots of these operations uh efficiently right so this is the two problems that we had to tackle what we're doing on time okay so 950 um yeah probably I think I'll take another 20-ish minutes which fits within our time profile great yep [Music] mysteriously on this line uh but okay so the key idea that we'll do is to sort of uh that will use is and so take inspiration from some prior

work and sort of generalize our circuit model so instead of just saying we have a circuit where we only do field operations what we'll do is we'll extend our circuit model and add in um uh new gates which do for example group addition and group scalar multiplication and random Oracle calls right and these will sort of be like native um uh operations that you can do inside our circuit right so now in our circuit you might say okay I'm going to add X1 which is a field element to itself right but then I'll multiply that result of like this 2x1 um with uh like I'll do a scalar

multiplication of X1 with some group element right and then I'll take that result and I'll feed it along with X3 into some random Oracle right so this will be okay this is like basically like a generalized generalization of a previous circuit model we've extended it with some more uh gates in in the basis right um okay so you might be saying okay you know we've sort of just shifted the problem to another layer of abstraction we sort of just said okay now our circuit natively supports these things but let's see how we can actually um once we have this shift in perspective how we can design efficient NPC protocols for this generalized circuit

right and so that's the key idea that we are able to Leverage is that additive sharing is linear right as I said before um and I guess the the key way to leverage this Insight is that what I'm additively sharing doesn't necessarily need to be field elements it can also be now group elements right so I can take a group element say m and I can see could share it into a bunch of group elements like S1 through SN right each of these is themselves a group element right and the idea is that if I have up to n minus one of these group elements

I get no information about M right but the moment I get all of the sort of secret shared group elements I can add them up using group Edition right and then I will be able to recover the underlying group element message and okay um and roughly the sort of okay maybe I can explain what the secret sharing scheme looks like so for a finite field message M right say for two parties however do the secret sharing is I would sample a random r and I was sent to party one M plus r and to the other party I would send R right and the idea is that the party was received R okay it's just a random field

element it reveals no information about M and the party which got M plus r that part like the M plus r itself will look like a random field element because so if you're taking something and you're adding in completely something random and so basically you're ending up like a random spot in the field so that's how you get privacy this is for field elements right but the same idea extends to group elements also right so I take my message my group element right I'll sample um say like a random group element uh call it capital r and I'll send to uh party one capital M plus capital r and this will again look

like a random group element I'm just adding in something random and to the other party I'll send R now so far like yeah the sort of the the argument for privacy goes through as before um and again you know you can add up M plus r okay I would actually send M minus r and r but if you add these two things together the R's will cancel out and you will get out your message and right so basically the the key Insight is that um the secret sharing doesn't actually require uh you to be over um a finite field but like for the more I guess you know algebraically uh uh knowledgeable I guess uh which I am not but basically like these additive

sharing schemes they also work over modules so FR modules and an elliptical group is an example of a FR model and a module is basically just something where you can add things together um and you can also do scalar multiplication essentially [Music] so that's a high level takeaway but yeah basically all you need is like something which has this additive uh structure of uh like additive group structure of order R right and your elliptic curve uh group has order are the additive subgroup of the field has order R so basically you can move between these and

extend your SQL sharing scheme to both of these settings okay that was uh quite a mouthful any questions um on this basically the idea is that yeah you can take your attitude sharing scheme over field elements and you can sort of shift it to work over group elements also you have the same guarantees and everything bro uh no questions okay awesome awesome um I know hopefully everybody is following around along all right um oh so this is like uh I lied we have one question

yeah awesome so does needing to use scalar multiplication cost a lot more that's a good question right and what you see is that just like in the finite field case right where if I'm doing uh a multiplication of a secret shared element by a public element right then it doesn't require actually any interactions um uh so if I have some element public element C and the private element uh secret element X then I can compute the secret share of uh c times x just by locally multiplying my share by C all right uh

uh similarly in this setting if I have either a private group element G that I'm trying to do a scalar multiplication with a private element a private field element or vice versa like I have a private uh yeah private field element and a public group element then sort of you can just use your standard double and add algorithm natively to compute the scalar multiplication so you're not you're not actually your your cost for executing the scalar model gate is going to be the same as the cost um of doing it locally I mean not you know there's no interaction involved nothing yeah so we're just going to cover this

uh literally in the next portion um Okay so so to evaluate the circuit this new generalized circuit we proceed as before for field elements um okay I'll get to your question there in a second um but okay so for complete elements things have changed as before um for group elements yeah sort of again we are able to just locally add our shares of the group elements right but for multiplication the scalar multiplication operation um right uh you can sort of again do this native scale of multiplication of this say public element y by the share of X

right and then now you will have a share of x times y um or you could do it reverse also like you know you could uh scale or multiply public X by the share of Y and then we'll have a share of x times y um so the follow-up question that there are asked in the chat was um if both X and Y are public um in the small scalar multiplication case uh do you have any additional cost and the answer is no right because um there's nothing to hide in that case so you can just execute it locally yourself right and you don't need you don't need NPC for that so public scalar Times Public point is completely uh there's no NPC involved at all right and in some sense you can actually

pre-compute it before you start the MPC because both X and Y are publicly known and sort of then you can hard code this this value inside your your circuit that's like sort of you know the case of um say these constants in in Z case in Arc circuits the same idea would apply here um okay yeah so this is how you would evaluate these Edition gates for group operations and simply the multiplication gate for group operations double also is similar to like the Edition gate uh you just do like a native like a local doubling uh using a standard doubling algorithm for elliptic curve okay so that's the group operations uh taken

care of um look I guess you know the question is if we have this restriction that Y is public right or the group element that we're doing that we're using in the scalar multiplication gate is public and you might wonder okay is this actually a restriction in practice and thankfully as you can see it's not really a restriction because for all of the stocks that we consider the scalar multiplication essentially happens between the uh some secret Point like your witness right and the SRS and but the SRS is sort of publicly known to everybody in the world right so it's a public point so in practice for our applications

there's no restriction on this restriction of the why being public is not actually a restriction uh maybe maybe there were some other applications where you your group element might itself need to be private um but that's something that we don't consider for for this use case okay uh all right so the landscape is you know random oracles and okay I won't exactly cover this right now um we'll we'll see how to efficiently realize uh or evaluate random Oracle kits um a bit later okay all right so assuming this model

basically what we've done is now we've sort of cut the knot and now we don't need to have fq operations over over in our circuit right we can only get we can get diverges doing FR operations only inside the entire circuit and uh uh so we'll get like really high uh it seems like we can get like a really efficient circuit for um the secrets not proofer right in some sense also uh this extends like I uh okay maybe I'll go on to the next step right so now we have to figure out um how we will realize is efficient

circuits for this polynomial IOP approvers I mean are yes so that's problem one solved and like how do you actually support these different kinds of operations the second problem is um okay now we have lots of these operations so how we support them how do we actually get a circuit which has all of these um many operations supported efficiently right so to to do that let's take a look at the kinds of operations that are performed in say the piop approver circuit okay uh oh I got the animation order slightly Ox on this yeah I'll just fast forward through all of the animations um okay so if you look inside a you know

Common polynomial IOP approver you know you're doing a bunch of operations such as evaluating p over some multiplicative subgroup um you know multiplying P by the scalar you know interpolating polynomials you're adding two polynomials you're multiplying polynomials you're dividing problems all kinds of polynomial arithmetic is going on right but the key Insight that you can really take advantage of is that for everything except multiplication of two secret polynomials basically all all of the other operations that are performed by polynomial iot approvers they are in some sense linear operations and can be realized only with addition Gates Right and what this means for our scheme uh

for our sort of uh cost model is that uh actually doing these computations only requires local computation doesn't require any interaction between the workers or between the parties of the MPC protocol right um and because you're only doing it locally and you're just giving your standard field operations uh you can get efficiency that is roughly on par with the efficiency of the plain text grouper right so for these operations you're literally as efficient as the plain text proverb would be outside of NPC but what about uh this polynomial multiplication right so if you look inside the this how what a polar multiplication looks like essentially

you have to do fft to sort of put the let's say you're starting off in coefficient forms you do an fft to go through evaluation form for both of your polynomials and then sort of you do a point-wise multiplication on all of the evaluations and then you would do an inverse fft to go back to coefficient form if you need to right now the cool thing is that the fft is a linear operation right so we don't actually have to execute it again inside NPC in any way it's going to be an entirely local computation just like these other operations so for the fft and the inverse fft we're completely fine there's no additional cost however we do have from this point twice along the application but uh and you

have to do like a large number of these like up to the degree of the product right um but the nice thing is that all of these can be sort of done in parallel so the multiplicative depth is is still just very low it's just one because you do sort of a bunch of independent Point wise multiplications right like the multiplication for the 100th evaluation I think the point was multiplication the point wise multiplication for the 100th evaluation is completely independent of the point wise multiplication for the first evaluation right so you can do all of them at the same time in parallel so you're able to sort of saturate your network bandwidth as much as possible um and you end up having low

multiplicative depth right so you're not paying a lot for a network round trip cost here okay so basically the takeaway is that for polynomial IOP approvers most of the uh cost is going to be equal to the cost of doing a plain text prove very locally and then for Poland multiplications okay maybe we'll have a little bit more cost but the cool the good thing is that for a lot of um stocks that we care about in practice such as say Marlin or like the three gate uh the three RT but I got a three column version of plonk um we only have to do one polynomial multiplication right um so we were able to avoid a high

multiplicative depth um or even if you have more more polynomial complications you're going to get the sort of independent multiplication so you can do them in parallel essentially okay um any questions about this I don't see anything in the chat uh maybe we'll stop for a second nope I think we're good okay all right so that's the polynomial IOP approver and the summary is that it's basically as efficient uh as the local piop approver okay all right so now let's try to design efficient circuits for PCs right

um and I will focus on this slide on kcd just because it's very efficient uh it's very simple to to describe and it's also efficient and use a lot of snacks okay so our goal with in the in this uh slide is to basically say okay I have a secret share of a polynomial and I want to go from the secret share of the polynomial to a secret share of the commitment to the polynomial right so however how would I go about doing this so what I will do is look at I have my SRS which is a public group elements right and I have my polynomial which consists is basically a list of coefficients um

in secret shared form so this is private uh private information now to compute the secret share of the commitment uh I would basically just compute the MSM like standard right so I would uh take these coefficients Ai and multiply them with respective elements in bi and some those all of those results up right and if you recall um this is a multiplication of a private scalar by a public group element so this is a linear operation right it doesn't require any interactions between the between the workers and so each of these individual uh scalar multiplications is interaction

free and now we're just adding up a bunch of shares of group elements which is again a linear operation so uh it ends up being overall completely linear right so we can compute this entire commitment uh in a local manner without um having to interact with anybody else on the network and I'll be able to achieve to get my commitment my share of the commitment very efficiently okay um and you so if you don't have to actually I was just you don't actually have to do the individual multiplications and then sum up the results uh you can use a protocol like or an algorithm like click address even in the

secret shared setting and that'll it just works out fine okay so that's the commitment what about the process of computing the opening proof right so now we have the secret shared polynomial then we have a public point so let's say we know what the point is that we're going to be Computing the evaluation proof at so the first step would be to compute this witness polynomial um and this involves um doing the division of a private polynomial by a public one right this x minus Z is a public polynomial and fortunately for us this is again a linear operation um

you can think of it one way to see why this is linear is for example if you try to do the polynomial division using the fft method right so you compute the fft uh you get you get the you use the fft to get the evaluations of the numerator and the denominator both right um and you sort of invert the evaluations of the denominator and then you do the point wise application as before and then you do the inverse F of T to get back the the division result but the thing to notice here is that now in the pointwise multiplication right um you're multiplying the private evaluation of the numerator by the

public evaluation of the denominator right so you're doing a private public multiplication and this doesn't require any interactions right so it's a linear computation and so we can compute this with this polynomial without any interaction again so we have multiplicative depth zero no multiplication Gates so you know this is this is uh fantastic for our efficiency and then we compute uh the commitment to this witness polynomial as before and this is again an entirely linear operation okay and this gives us the secret share of the evaluation proof okay so yeah we we're heavily sort of leveraging the fact that uh in some sense kcg is additively homomorphic

so if you want to compute uh and the idea now is that I can just add up these commitments uh these shares of commitments to get out like the commitment to the actual uh polynomial p all right so the takeaway from this slide is basically for for kcg you can get complexity which is on the same order as the actually exactly the same as same text kcg outside of NPC and there's no interaction I have a question is this the same for the IPA schemes or is this as unique to kcg yeah so for IPA um the commitment is the same because again it's like sort of essentially a Patterson commitment right

so there's um you have the same property there for the opening it's a bit more involved because [Music] um yeah you have like these interactions like random Oracle calls in the middle right it's like a logarithmic round protocol so there's a little bit more involved and you need to um communicate essentially like a in the protocol that we have maybe it's like more efficient protocols but you have to communicate between the workers like uh linear in the degree size Vector between the workers um but the cryptographic cost beyond that is the same as a standard IPA so it's once you do some essentially you

find a blind the commitment that you're opening I need to do the blinding in like a secret shareable way um and uh uh once you've done that though like you're basically doing the IPA over like a publicly known polynomial which is blinded so the blind even though it's publicly known the blinding ensures that no information is leaked but then sort of you can proceed with sort of the standard public coin like the the standard IPA so even in that case there's like one round of interaction but like the majority of the work which is the msms and all of that stuff is uh very uh much the same as the plain text IPA based PC scheme yeah so yeah that's a great question

Alex thanks um okay I think there's one more question from Dara in the chat I saw that great yeah go ahead if you see you feel free and uh yeah can you just read the question so the video people can yeah so the question is um is it important to reduce the number of piop rounds as far as possible um and sort of generally kind of yes um but in practice it doesn't matter too much um because the cost of the approver okay so the the aim of reducing the PRP rounds would be to reduce the number of random Oracle calls eventually right like uh that is the main benefit of having a lower number of rounds

the downside though is uh I guess not the downside but rather like the performance characteristic of our NPC scheme is that we'll be able to realize these random Oracle Gates um essentially by involving the delegator by doing the interaction with the delegator and okay so you'll have to pay like a network round trip time interaction with the delegator but it's like okay for all of the protocols that we know of is like a logarithmic number of of rounds right so okay you'll have to talk to the delegator like a log number of times but that's like okay like your MSM is going to cost much more than it takes to sort of send a small message to the delegate and get the response back

so uh yeah anyway like in general it's beneficial to reduce the number of runs so piops and the same cost condenser supplies here also but it's not like a larger uh uh it's not more critical here in some sense okay so essentially now we have these efficient circuits for the piop um scheme and um PCC scheme okay I guess there's one more question from there so the question is does the number of rounds uh is it basically the same as the sort of uh standards in that there is

um uh it's like the same number plus maybe like some small additive constant so I think it's a good um uh to keep in mind here that a goal here is that sort of the end proof of this of this protocol should look in some sense identical to as if I had computed the proof locally I didn't I should have mentioned this earlier but our goal here is that the end proof is looks identical to like the actual uh proof as if I had computed the proof on my own machine so it should be indistinguishable to somebody else looking at the proof they should not be able to figure out oh you know this this proof was actually computed using a delegation protocol we want to avoid that so the end snark has

the same number of rounds the same complexity the verification from the city everything is entirely the same as the piop scheme that's the sort of underlying same text scenario so there's no change in number of rounds there in the uh MPC protocol though um yeah so this analysis actually applies so the number of interaction like interactions between the workers and the delegator and all of this stuff is uh ends up being yes uh like the number of rounds in the Pio P plus like some small constant um usually so that that is the that is the analysis for these uh for our at least our delegation protocols so that's that's a

good question that's very good to clarify this awesome okay just quick time check so we have about 15 minutes left of the of the session here so just wanted to give you a heads up there yeah yeah so I will uh I think uh yeah we should be able to cover things very quickly yeah we always we always save the heavy hitting questions for the last 30 minutes so you know to in an attempt to foil your ability to end on time well that's where all the meat is so okay it makes sense right everybody knows about a snarcus nobody's asking oh wait what is a you know the proof size in the stock everybody's asking me how does the scheme actually work so it

makes sense um okay um so okay so a lot of these techniques are not sort of you know super novel um so again because the paper has been in progress for almost three years we've seen you know these results come passes by in some sense um but yeah these techniques have also appeared like in Prior works such as um the ones that have listed uh below um and again I guess it's not very useful and I can provide slides afterwards which has the links embedded inside okay so so maybe let's summarize our progress so far okay I guess I'll be taking a step back so we had efficient circuits for power level iops and PC schemes and essentially like uh and like I didn't talk about the random Oracle

stuff but the idea is that once you have these efficient sub circuits it's very easy to stitch them all together and get a circuit for the overall CK snack uh group so get this season Arc uh circuit all right um so we've designed now the sufficient stock but if you apply this to like uh you know our MPC protocol which now supports these scalar multiplication Gates and so on uh we're only sort of achieving efficiency that is um you know on par with this prior work that I mentioned um on the previous slide right and the question is can we do can we do better can we sort of tailor our MPC to avoid these these slowdowns right

um and let's take a look at how you can actually go about so the answer you know spoiler alert is yes um but it's somewhat non-trivial right and the two sort of opportunities that arise in improving or specializing our NPC for our application use case is the first one is to sort of take advantage of this asymmetric uh threat model right so in most MPC protocols sort of each of the parties they're sort of equally distrusted right like no particular party has like a privileged position in the uh uh uh in the protocol execution right so you can't like trust that like any

particular party to do to do special parts of the protocol however in our application setting um we have one party who is always honest right they will always follow the rules of the protocol that is the delegator right it doesn't make sense for the delegator to cheat uh because okay what will it gain out of it right okay at the end maybe if it cheats it'll get out an incorrect proof but then it's sort of wasted its own time wasted probably money to run the cloud proofers and all of this stuff so you know good question can we trust ourselves let's assume that we can uh if you can't then there's lots of problems then we'll have to solve uh well it's I guess it's I guess it's important here that you're

producing a proof that is the same essentially as the underlying scheme um so then you know it's as sound as the underlying scheme yes yes so that yeah that we will actually leverage that that property also right um but the idea is that so we have this party this delegator who is always honest okay it's a bit computationally limited you know it can't do heavy computations but you know we can trust it to always follow the rules and um uh um sort of want to preserve its own it will be incentivized to preserve its own privacy right um and so we can maybe try to leverage this delegator to to do more efficient uh protocol design so that's uh the first opportunity

the second opportunity would be to sort of somehow try to take advantage of the kind of computation that we're doing right and what I mean by this is that if you look inside see like the circuit that we're Computing it's Computing a snork right and uh the point of a snark as Dara mentioned right is that it's supposed to be sound right so if the question that we want to ask is you know if one of these worker machines sort of deviate from the protocol in some sort of non-trivial fashion um like will they be detected by the fact that okay maybe the snock will just fail to verify right so maybe if we add a check

for SNAP verification at the end of the the delegated checks are the snack it obtains is actually valid um then we will be able to detect some malicious behavior on part of the workers right and so then can we use this to get cheaper security guarantees against malicious workers right and sort of reduce that that at least 2x overhead that arises from existing malicious security techniques all right so these are sort of the two questions that you want to ask and see whether we can you know make some Headway back taking advantage of these two opportunities and let's go over them one by one right so first we'll start by looking into how we can take advantage of this asymmetric

threat model nope oops sorry supposed to animate that but anyway so um let's see how we can do this by sort of how to design more efficient protocols for multiplication Gates right so remember the point of a product of a multiplication gate is that if worker a and worker B have shares of X and Y then they should be able to obtain you know via this multiplication protocol shares of the product Z which is equal to x times y right that's the goal of this any multiplication protocol um and so there's like a you know in the literature there's like a bunch of these of these protocols for doing multiplication in sort of the standard NPC setting one example which is sort of

used for example in this please protocol is sort of a multiplication protocol which has some pre-processing step that happens in the offline phase and is independent of the X and Y that you actually want to do the multi multimodo multiply okay so in this offline phase what the workers do is that they will do run some pre-processing protocol and get out some pre-processing material A and B which they'll be able to use in the offline phase um yeah sorry in the online phase but the downside is that this pre-processing protocol is usually quite um heavy right it'll require says something like a bunch of OT operations or obligations transfer operations or a bunch of homographic encryption operations with uh like some

tailored zero knowledge proofs of correctness about the the ciphertext and things like that right so overall it's like you know not very clean very very heavy all right so so the speed processing protocol is heavy the cool thing is that the online phase is very cheap right it's pre-processing material is basically looks like a bunch of secret shares and so when you want to do the online protocol it's basically doing like a some very cheap uh field multiplications and additions right so really the bottleneck in these protocols is this pre-processing step so ideally we want to be able to remove that and sort of I guess the cute Insight that we had was look you can just actually just replace it with the

delegator itself or the delegator will just generate the pre-processing material in the offline phase give it to the workers and then they can use that during the actual group generation phase to to compute the menu multiplications that they need right and um yeah so you like a need like a linear amount of this pre-processing material like linear in the number of multiplication Gates but again you can just do this in an offline phase so it's like you know when the say your phone is plugged in um overnight right that's when you do this pre-processing step um to generate the material for for your workers right and the cool thing is that um or I guess even cooler thing is that um if you if you have the delegator

doing this pre-processing you'd actually don't need any of this heavy cryptography you can just get by with some finite field mod applications and additions um so concretely for people who want to look later on um this pre-processing material is called multiplication triples uh it's a very common technique in the NBC literature for doing multiplications but you can generate them very efficiently if by yourself you know if you trust yourself right uh but if you didn't trust there was no sort of trusted party to generate these triples you would have to use this heavy cryptography to do to do that instead yeah so I know we're five minutes in the wrap up very quickly okay so there's also another protocol that you could do

basically instead of using any of this pre-processing you could just have the delegator perform the multiplication the workers send their shares to the delegate at the delegate that combines them reconstructs the values and performs the multiplication and shares the multiplication results back to the to the uh where to the workers the disadvantage of this is compared to the previous one is that now you have higher delegated worker communication in the online phase which you might want to avoid or maybe you don't care like and this is simply that you don't need a new pre-processing stamp yeah okay so this is another example of how you can leverage the delegated to really cut out any heavy cryptography um

okay again my animations were off I have to go back and fix all of these things um Okay so so I talked about multiplication Gates uh I had mentioned earlier that you know we would see later on how you would realize a random Oracle gate but again the idea here is very simple before right so when I want to evaluate the random article on some private input X inside my circuit what I'll just do is I'll have the workers send the shares to the workers uh oh sorry I'll have the workers send the shares to the delegator the delegator will reconstruct the input compute the random Oracle over it and send back the random Oracle output either shared or not shared it depends on the on the use case in this case in Instax we will need to hide that

the random Oracle output generally so the cool thing is now by doing this we're able to completely avoid hashes inside the MPC protocol um and so we're like at Native efficiency right I guess because the um the random Oracle output so public coins yeah exactly yeah so there's look like random things then they don't have much information about anything okay so this is how you would do random Oracle Gates um so overall by doing this um we're able to get up the end-to-end NPC protocol which has uh which avoids any heavy cryptography so it's like uses basically prgs to do the to do

delegation right and that PRT is only there for reducing the the cost of the secret sharing step you can avoid them whereas like we don't know in like the standard NPC setting how to get uh n minus 1 out of n security with um with just say prts you need to rely on some public key type operations as far as I know okay so that's we have three minutes left I will rush through this next part but sort of the the next step is to use the other um yeah I'll get to the there's a question maybe after this uh portion

um okay so the overhead um in a lot of these NPC protocols for malicious security is quite high right so one approach to doing to achieve military Securities for example to use specialized zero knowledge proofs to prove that you computed the the message at that NPC round correctly but you know zero screws are quite expensive and even some of the most efficient protocol speeds uses these algebraic Max which at the very least double the amount of communication and computation right and so this is reflected in this prior work uh by um osdemeer and Pune which in their

protocol sort of they incur at least a 2X overhead compared to proving locally right so the best overhead they get is 2x um rates and all the number of provers increases uh this sort of Gap actually goes up right so they have larger overhead compared to local grouping all right so questions can we do better um and the idea is that actually yes um and to do this let's go back to this sort of idea of using zkps to prove that I've computed the steps of the protocol correctly right so what this is called the gmw compiler it's 1986 seven something like that like super old classic work in the NPC space

but the idea is that if you take some NPC which is semi honest secure um but and has the additional property that you get privacy but not correctness if the you know adversary is malicious then you can um basically apply a zero knowledge proof um which shows that okay each step each message was computed correctly by each party and you know all the parties verified these zero knowledge proofs and you can get on a maliciously secure protocol right um and you have privacy and correctness against malicious adversity is up to aborts basically the adversary can force the protocol to abort early and nobody will get their their result but modulo that you know you can get privacy and correctness

now the downside is that as I said these groups are very very expensive um so what will I do is we'll have to leverage this idea that the computation itself ever doing is a zkp right so if the verifier if the delegator checks that the NPC the proof is valid right right maybe we can uh get some correctness guarantees so privacy in some sense is guaranteed by the base underlying semi on this protocol which we're using speeds it has this property that you have privacy against malicious adversaries and the correctness hopefully you know um is guaranteed by the fact that if the adversary deviates is non-trivially from the protocol then the end resulting

proof will sort of fail to verify that's at least Our Hope right um like if this guy say Associated to a completely different secret share and just discards the the secret share sent by the delegator then at the end it'll compute like a proof for like a garbage awareness and so with very high probability that that'll fail to verify right um so this is the Hope right but unfortunately this doesn't actually work out um uh okay so let's uh Dara has a good point in the in the chat this is actually what we use but okay so this this approach as is doesn't quite work

out and this is because um the malicious worker can sort of malleate its messages in a way that the final proof will fail only sometimes so for example think of um an r1cs instance where you have like a Boolean constraint right like x times 1 minus x equals zero so if the original value of x was 0 right then this constraint works out fine and the proof will go will work out completely fine everything checks out now I'm a malicious adversary right um what I do is I am alliate my share of x to like by adding one to it all right um so now if the initial the actual value of x

was Zero then the malleated value of x will be 1 right but this will still pass the booleanity check so you will be it'll still pass the x times 1 minus x equals zero right and so the proof at the end will still be valid however if the initial value of x was 1 right then now the valiated value will become 2 because I've added 1 to it and the booleanity check will fail and so the end proof will also fail right and so now by observing whether or not the delegator rejects uh on the basis of the amaliation I can figure out okay this bit was actually zero or one and so now I've gained some information about the witness and this

is you can sort of extend this to sort of arbitrary ranges in some sense um and you can if there's repeated usage like if the verifier uses the same workers again and again and the same witness again and again maybe you can over time reconstruct large parts of the of the witness or the secret key or whatever that's inside they are uh Witness so yeah this is kind of you know catastrophic for this for this idea in some sense uh but actually it turns out it's not actually catastrophic what we actually need to do is we need to enforce that okay the adversary is using exactly the witness that I uh sent it right um uh and it's not using sort of any

malleated um witness and so what we do is we introduce this I want to go to details we introduced this new notion of a polynomial IOP consistency checker which basically says that um I will query the polynomials um sent by this potentially malicious prover and I'll check them for consistency in some sense with what the honest Brewer would have produced um right so I'll check that say the witness uh polynomial in uh Marlin or Blanc actually equals like the the actual witness witness polynomial that I would have generated as a uh honest prover right and the idea is that this is a very cheap check to make

I'm just making one query and then I can use these PC schemes to just provide an evaluation proof um uh for each of these queries that I make right and or it can be like a batch evaluation proof um and by doing this essentially we're sort of able to enforce that where the these malicious workers potentially malicious workers are always using the correct uh witness and sort of then what we show is that you can sort of come if the verifier of the final proof accepts and this this consistency Checker also accepts then we know that okay all of the uh polynomials that were used in this are

generated in this protocol were actually the um that would have been generated by some uh honest ish prover like we allow like some trivial deviations like I don't actually care if the adversary used say like a different Randomness in the one I then that that it was supposed to right um so I don't actually care about uh leaking like some some maliation in the randomness I do care about annalization in the witness then that sort of what we focus are um enforcement and consistency checks on um yeah so this is actually it's a bit more involved

um but what we uh for we designed this consistently checker for modern and what we were able to get was that um we only make one additional query to the with this polynomial and then there's a little bit of additional like layer number of multiplications for the verifier uh for the delegator um to check that okay this witness problem is actually consistent with the honestly generated polynomial uh but yeah it's very cheap and I can evaluations you know adding or removing this consistency Checker made no difference to the to the overall costs at any point like communication I mean communication yeah even communication delegated work etc etc okay so this is the end of the technical section I will very quickly

um go over like our evaluation and implementation stuff and then we can wrap up sorry I know I'm already five minutes over I'll get uh okay thanks so the question is okay we've done a bunch of work I've talked for hour and a half so far I'm tired you're tired does any of this actually lead anywhere do we actually get concrete performance improvements from doing this work um when the answer is tax at least yes so we actually did a bunch more optimizations in the in the actual protocol like the the systems level optimizations more cryptographic optimizations bunch of things uh and and in our implementation so basically this implementation is using artworks and um

it's sort of a generic and you give it like this circuit for the piop scheme so again for the PC scheme and you will get a like a delegation protocol for the full full snark and we show how they uh we provide some instantiations of these circuits namely from the KGG PC scheme and the IPA scheme um so that one right now is not uh giving correct results but it should they should be able to fix it um and the Marlin polynomial iot um and overall this gives us a very efficient delegation protocol for the Marlin CK snack you should be able to extend it also to Planck um we haven't done it but you know it should it should be doable maybe a little bit more overhead compared to Marlin uh but again doable

all right um so in terms of evaluation it is actually 20 speed up so what we found was that um we evaluate in a bunch of settings like a laptop the very fast connection the same laptop is like a slower connection and then a mobile phone and what we found was that in every case we got uh quite a large speed up uh like up to 26x for the phone 9x if you have like a nice internet connection and like once you start sort of throttling your bandwidth then you get like some uh uh sort of the network between the workers and the delegator becomes kind of like a bottleneck so you the Improvement is less

um So you you're able to prove things much faster like nine nine like six to twenty six x um but also more importantly sort of you're able to increase the size of um the urban CS instance that you're that you're able to prove by a very large amount like you can prove 256 times larger circuits or rmlcs instances um for Marlin right um and actually in some sense this is more of like an artifact of our implementation if your r1cs has this somewhat like a streaming structure so that um you uh like you know at the end of the hour like a circuit I'm not like referencing variables from

the beginning of the circuit or like a lot of variables in the beginning of a circuit then South African like get like infinite scalability at this point um so you can scale up to like you sort of stream the witness um secret sharing in the first phase of the delegation protocol and so this can become like 1024 to 2048 like whatever number you want you can scale up your r1cs um probable around CS to that size and finally you know what are our techniques for improving the MPC protocol actually helpful compared to Prior work and the answer is again we evaluated this compared with ob22 and we found that um yeah we're at least 6X um better

um uh yeah so that's sort of the takeaway um and yeah thank you everyone for listening paper is online at this right now at this ugly lick but yeah the security proof has been uh very tricky to nail down because we have all this optimization some malicious security but now I finally have a handle on it and it's almost done and I'll try to push it by the end of the week and so it'll be only pretty soon the code um is a little bit more work than that um uh yeah basically because the paper took so long to to finalize uh everybody has moved on to better things so it's kind of hard to get people to sit down and

clean up the code but do you need people to review it uh the code uh yeah I mean I think I think in the end you know if you've been able to find time on this open source it and people can let the internet uh go to town the internet do its thing yeah yeah um yeah thank you everyone for listening and um yeah I guess I'll take some questions that Dara had in the in the chat um okay so I guess going back to the discussion about the random Oracle stuff that's not actually aware that uh like there's anything with the Halo 2 column in IOP was not uh public coin oh

um so it's in the permutation and look of arguments um you you sample some Randomness and then oh isn't it do you need to do that using the no I don't actually I'm wrong you don't need to do that using the random Oracle it's fine yeah yeah so yeah I think uh otherwise like you would only be designated verifier right because yeah that's right yeah um so I think about all the stuff it's it's the preview just coming with the randomness on its own yeah for the permutation check I guess yeah it makes sense um that question okay and so the next question is the delegator can maybe also check correctness up to a certain round

depending on the Pio P yeah yeah this is a consistency chapter you are sort of checking round by round and thankfully like um it ends up being the case that at least for Marlon we you only need to check for the first round and the witness polynomial uh I think I mean Planck does not like a lot of multiple I think it is still two rounds right uh and Blanc right um uh yes yeah I'd have to check yeah okay yeah yeah um so yeah even in that case I do think though that um you would not have to check across multiple rounds we will sort of Leverage the fact okay the proof passed and some consistency check on the

witness past so then um everything else also sort of fits within like the acceptable parameters for that for the protocol uh that that's that's not at all obvious I can see why the security proof might have been difficult yeah I mean like the the fourth wave of a plan I can explain right so we have this the ca ZB and zc polynomials which correspond to like the interpolations of a times z and b times e and c times e right um and okay you might think okay I actually have to check that these also are actually uh interpolations of acbcz but what you can essentially Leverage is the fact is that okay if I changed za uh right then my I have this in Marlin

this is this so-called Lin check which checks The Matrix Vector product um if I change Z8 to to not be consistent with W which I did check in my consistency Checker then this polynomial IOP this line check polymer would fail right um and we know it's not failing because the snark passes right so uh this means that okay this Za was like consistent up to Randomness with uh with the witness in some sense and and the Matrix a so that's how that's how we're able to like really minimize the number of polynomials we query on top of um the sort of Standards polynomials and so do you end up with only a single batch check

uh from Holland yeah we end up with just one evaluation proof okay okay uh uh all right so yeah and then okay so that's a high level overview of that so okay leaking one bit is already fatal yes yes so like say you could or something like zcash you would if you leaked a bit of the of the key then of the secret key then that could be catastrophic um especially over multiple repetitions um or like you say you're revealed okay the the note is in like the left half of the local tree then that's one bit leakage but it's completely planted it can like halves your anonymity set for

example exactly yes um uh okay so the final question is it's not specific to r1cs I mentioned yeah so we didn't Implement uh a delegation like the circuit for clock um it's it's doable um um you could I mean because like reduce r1cs to like the Plug Circuit format and that'll also be another way to do it and go vice versa with some overheads uh but um yeah you would I doing the work for clock would require a little bit more analysis which I really didn't do uh but I really excited you know happy to talk about it offline and see uh I don't know what that would look like for for blog

thank you awesome well thank you very much uh pratish for being very generous with your time and I I yeah and I know you stayed up late to work on this but this is great work uh really impressive work that I think will really be helpful in terms of making uh use cases real world use cases for snarks more practical which ultimately I think is is really going to help Drive uh you know this Market that we're all kind of striving to serve so uh thank you very much for coming on the show our show on the show coming on uh coming on uh this DK Study Club and um yep um yep I'll post this up on YouTube so everyone else can enjoy it thanks everybody yeah thank you so much Alex thank you for having me