A dive into VOLE-based Zero Knowledge - Xiao Wang

Transcript

great yeah so hi welcome everyone to uh learn and share PC we like to put these on here and there just kind of shy a spotlight on things in the space that we think are interesting and uh people can learn from uh I'm suu I'm here uh at PSC uh most my focus goes towards developing the TS notary project uh today we have a great guest presenter sh sha Wong sh's an associate professor at Northwestern University he's the uh chief chief cryptographer at Primus labs and is also an author of The Quicksilver protocol which I believe right now is currently considered the state-of-the-art of the so-called Vector o based zge uh protocols that he'll be presenting about

today uh I've been interested in these protocols for some time now uh they really stand out in terms of like both prover performance uh low me memory uh overhead and they're actually quite simple as well relatively simple and uh and albe it there there are trade-offs when it compares to other improving systems it's not better across the board but it has some really interesting characteristics for client side proving TS noty project we recently Incorporated this uh into our protocol uh to create benefit and I just think that other people should be aware of it and should take it into consideration as an option when they're developing uh like client Eye Apps and uh yeah that's enough for me

I'm going to pass it over to showa he's GNA share screen we can get going on that presentation here yeah thanks for the introduction I'm going to share screen I'm going to share the entire screen right now uhow I think you should be able to see my screen so today uh I'm going to talk about some high level overview of V based Z knowledge proofs I'm not going to cover all the technical details uh but I will I will I hope to at least give people a feeling and some kind of intuition why this is lightweighted and like what kind of applications it might be suitable so well so Zer knowledge proof is like like so if we view it as a so-call ideal functionality so it like

we could could view it as a so-called a IDE functionality you can think about it as a I think so I'm not able to see the chat so if somebody uh ask send something in the chat and I need to I I'll try I'll let you know okay uh so you can view it the chared party who take the uh the witness from the approver and then check the predicate U and like whether I I think your screen share went away okay U I think maybe because I um is it let me show it again and higher screen it should be good now great yeah

and the trust dep party can like is actually verify like the pr and send the result of the verification to the uh verifier and I mean there are different levels of definitions of zero knowledge proofs for example like uh what does mean by the soundness what does it mean by like zero knowledge and things like that but that's not really the focus of this talk so I mean I'm just going to use this to briefly talk about mention the the like the properties uh so there are many many many different kind of approaches um for Zer knowledge proofs including for example the the cas no like the IOP based protocols the gkr which is kind of very closely related to IOP based protocols and some less known protocols like MPC in the head and zero

knowledge gble circuit like protocols so I made a uh so so one way to kind of classify all the types of zero knowledge proofs is that we can like a try to see different kind of Dimensions okay so one dimension is interactive versus non- Interactive uh so like so we have Pro and a verifier the interactive protocols would require more than just one message from the prover to the verifier there could be multiple messages going between them and not interactive where where it means that we just need a pro just need to send one message to the verifier uh and like and like something related to interactive and and non interactive would be designated verifier

or not so designated verifier means that uh like the message can only be verified all the particle can only work with a particular verifier so um so majority of the non-interactive Z knowledge proofs are uh not designated verifier which means that any verifier can verify but there are some non interactive Zer knowledge proofs where like the verifier has to set up a very specific like CRS so it is designated verifier for interactive almost all of them are designated verifier and this is actually one of the important the features or I mean it's you can view it as a bug or feature depends on the application I will talk a little bit more about that

and in terms of the S synus there are protocol that are more or less on the high end of suus which is either where the proze is either independent of the statement or it's like a poly logarithmic to the statement there are some somewhat succinct protocols where it is more of the like for example square root of the like the statement there is like I guess the typical example would be Leo for some word sein there are many many many I mean I would say like majority of the ones that people know are sein and there are also portol that are not succinct at all uh uh like for example the portol I'm going to talk about today and there some other variant for MPC in the head and Zer knowledge G circuit and then in terms of

the computational efficiency uh I mean like there we can view it as three layers okay the first layer is that for every gate of every statement every constraint we need a constant number of public key operations okay so that means that we need a linear number of public key operations so this would cover majority of the for example ZN protocols uh and like here publicy operations could be for example exponentiation in groups or it could be some based operations okay so something plus maybe better would be like something or something some number theoretical transformation on the whole circuit then in this case the uh exact complexity would be for example like n log n for n

number of constraint and then now it's really a matter of comparing like log and ordinary operation versus one public operation which is more which is more efficient Which is less efficient and Al I mean like like of course like like a the best in some sense one could hope for is that we just need a constant number of symmetric key operations for each gate and to to prove circuit so this would be pretty much as close as what you would get like uh because like in modern CPU like uh a symmetric key operation is not too is like not too slower than like ordinary operation so this would just be a constant fractions slower than ordinary operations when

proving something and like there are like for example try setups like whether there's any try set setup whether the TR setup is universal or whether you need a different setup for different program these are not related too related to our talk so I will not not talk too much about this and finally something that has not been studed that much would be the memory requirement so U so like typically there are two types of memory complexity uh uh like for the existing particles so one side would be uh memory that is linear to the size of the statement or the size of the circuit that has to be uh that that needs to be proven and the other one would be linear

to the memory needed to evaluate the circuit which could be much less than the circuit itself so this is a little bit uh like like a tricky so let me try to explain it a little bit more okay so let's say if if we have a circuit and the circuit say just uh like let's say the circuit verifies a iterated application of some hch function in that case let's say if the iteration has let's say if there are 100 iteration then the circuit has the circuit size is 100 times uh the unit step however in order to verify this in order to run this circuit we do not need to keep the whole circuit because after the one interation we don't need to like a as a

plantex the like evaluation of the circuit we can just we can forget part of the uh like previous iterations this is like when like for example when we write a for Loop if some of the variables are uh like local variables when they are actually like when we finish the isation these local variables will automatically be recycled so so verifying the circuit requires could require much less amount of memory than the circuit size itself and like a and that and that Gap can be very very big for like a real protocal so uh so I order them in this case because like the top ones are what actually people has paid a lot of attention why this like where the lower ones are the ones where

people actually have doesn't hasn't like paid that much attention yet I mean I mean like in the past few years this has been more and more people realize that this is more and more important but like overall like like memory requirement is something that people does not really pay that much attention before do you have any thoughts on why uh that attention has been mostly focused on those uh other properties is that well I I guess for my view that might be an artifact of just I guess the block chain space and for example having a smart contract verifier of a proof obviously needs to be non- interactive uh and also there are uh bandwidth considerations as well so it needs to be succinct there's

just a high pressure there um is that kind of like a fair thing to point to or or do you see it differently uh I think maybe this is a little bit orthogonal because yeah are also snars that can have a small memory requirement M or like small as like smaller than the circular size so there exist the snars where the memory requirement is not as big as the typical snars uh but this like uh these protocols the computational complexity is higher but the memory requirement is lower I think uh people didn't take memory complexity that much because I mean uh in the maybe in the past maybe

20 to 10 years ago snars are too inefficient such that memory is not the bottleneck it's really the computation that is becomes the bottleneck and once people for example like uh realize that they can they can actually Pro the Prov can prove say uh 10 one billion gate like uh in reasonable time then they realize that okay they can prove much larger statement that actually captures like real world needs but then we realize that okay so they are out of memory and then but like so so they have to the P has to be sufficiently efficient to hit the memory bottom neck and then they people will start considering like a memory requirement so before that people like

memory is not even a bottom neck they can always open a say 100 128 gigabyte machine to do the proof but now it's like if the if the if the demand on snark is higher and higher and the statement becomes larger and larger like like cannot make it like arbitrary you cannot like just like a like a it's like economical economical to just like add memories and finding a particle that is memory efficient maybe a better way to do that right that makes sense especially with the pressure to kind of move this stuff more towards being on client side running on mobile devices running on personal computers and such thank you right right right yeah yeah yeah yeah I mean like another line another recent line is you know like all

these uh all snacks and some of them also like support uh kind of for paralyzation meaning in the sense that uh like let's say if aover has a uh like a circuit to prove they can distribute they can distribute the the task into n number of workers such that like the memory cost is also distributed among n workers uh to kind of you know like you know there there there are scale up and a scale out two approach this is like a scale out approach for like reducing the memory requirement per worker but I mean in the end like I mean if there is a way to use algorithm and protocols to reduce the memory requirement that would be

even better because like not everybody can afford a cloud yeah uh okay uh so I mean I made this graph I mean figure to like to show the like the high level classification of what I see as like a I mean some kind of high level like like a partitioning of existing works uh so there are like many succinct and non- interactive but there are also linear sized non-interactive particles some like based on NPC in the head some Bas on like v e in the head which is which combines v e based the zero knowledge which is interactive along with some other techniques and also some cut and choose G circuit

actually there exist the portal like this which is also non interactive but the communication is a lot a lot higher okay and on the on the interactive side like uh so before the the line of V the only one that is practical is the G circuit based Z knowledge proofs that requires I mean pretty much like 128 bit per second of communication so that's uh uh that's like fairly High okay so the in the VAR the zero knowledge like it's not just the like myself the work there's like a like there are multiple teams in Academia working on like a V Bus knowledge and in the past five years I mean I mean it's the like it's everybody's effort and we are able to

make this V based knowledge very lightweighted uh so concretely like let's say if you want to prove a circuit of size n then the com the proof size would be n bit and the majority of the communication is from the pro to the verifier however there are some number of like interactions between the part between the two parties so so the proof is like interactive protocols that require a proof and verifier to par for some number of small number of run like I think it's probably less than 10 or maybe less than five and the majority of the communication comes from the approver to the verifier and uh it the side the communication is about one bit per gate uh yep and like we can we Act and the

computation very cheap we only need Conant number of symmetry key operations so it is way faster than any other like the pro protocol and I'm and like I hope that in the next 40 or five 15 minutes I will convince everybody why this is the case Okay um so essentially like U so snar is really good for this kind of a synchronous setting where we have one Prov and the and the prover wants to convince uh like the prove the knowledge of some witness to a bunch of verifiers and that when Prov generat the proof the pro doesn't know the identity of all these verifiers that's where like snugs actually shine because like a the pro is kind of a synchronous in the sense that

when Pro generate the proof the pro doesn't need to know the identity of the verifier so there are also other like a synchronous settings so for I mean the most synchronous setting would be when Pro wants to prove something Pro already like can talk to the verifier so the two parties are online at the same time so in that case the prover can just prove it to the verifier directly and in this case a interactive Zer knowledge prove would make more sense uh so like obviously well like like any application uh all the applications on the synchronous setting can also use a asynchronous uh solution for example the narks they also work on the left hand side because the left hand side is you can view it as a more restrictive setting uh but it also means

that there are opportunities to optimize and improve the efficiency on the left hand side so if we don't need a synchronous like a like a notion then maybe we can do a lot more better like by actually uing the fact that two part is online okay so that's that's really what we want to do so the portal I'm going to talk about is interactive and it's often linear I mean if it could be sublinear to the statement size if somebody actually uh try to optimize the circuit carefully so there are actually ways to optimize uh the communication is at most one field per gate and for buing gate one field will be just one bit so the efficiency is the constant number of

AES so like constant number of Hardware accelerated AES operations and constant number of Hardware accelerated finite field operations per gate and I mean so both of them are hard accelerated because like uh uh this gowa cter mode GCM which is part of the hgdp Le standard like which also like Inc I think 99.9% of internet traffic actually requires using AES and the like like extension field operations so pretty much every computer right nowadays has a like module to accelerate operations for eses and finite field operations of this

particular like a field and uh so so actually so so the protocol actually only requires Conant number of both of these operations when the conent is actually small okay and the mem we have a raised hand was Alex go ahead yeah I um I wanted to add is um is being field agnostic like a difficult thing to achieve in volley because I know it's a big thing to achieve in the traditional snark world or is it like pretty simple to achieve in the NPC in the head setting yeah I mean uh like uh so for our ptical it's pretty much support uh any field um like uh there are also extensions to support uh like integer Rings like operations like uh modular 2

to the for example modular 2 to the 32 natively uh so it's actually a lot more flexible than like snugs and other stuff cool yeah and so what I talked about I mean I think like like from this like after this point I think majority of the slides are actually like uh already field diagnostic you can actually interpret it in any field that you want and mean like and like the portal also works even for small field like bulling or like Z3 that five they it also works on this kind of even smaller field it really depends on the application what you want so that's also in combination with the fact that you don't have to hold uh

a field element for I guess every gate in the circuit right you can drop essentially as values are no longer needed so yep that really provides a very low memory overhead it's quite quite cool yeah uh yeah uh so Tech to be Tech Ally correct uh if the field is small uh they need to hold a Mac of the value and the Mac would still be uh 128 bit around like a computational security parameter bit so even if the field is small the Mac is still slightly larger than that ah I see yeah but I mean but I mean like I mean so for majority of the

natureal programs like we WR like mean like like many majority of the wires are really local variables and they can be forgot like like pretty quickly because so so that's essentially the the biggest advantage of the protocal so the me the size of the Mec is not turns out to be not the bottom neck in memory yeah and like we don't need any trust in setup that any two parties can just like directly like as long as they have pki they know each other then they can just directly run the protocol and it is US secure so it's as as secure as one could hope for okay uh yeah and this is kind of the best one could think of

because even if we want to actually evaluate the circuit in the in the plantex we still need the one instruction for that gate Okay and like the throughput of a is about like one like one or two in like cycles per a so like a like so these are pretty much like a constant Factor slower than how like what you need to evaluate the circuit okay uh so uh so like so like there are two like a main component the first component is to quickly authenticate the protocol and the other component is to quickly check uh the authentication without revealing the

information and then they are actually different all different kind of op like like operations that we can support uh so in order to support like this kind of like a quick authentication so we have one work published in 2020 which is called farro uh that that is that follows a l line of work on S random correlation generators I think I have few slides to give a high level overview of what it does and maybe I can like talk more like maybe like maybe like next time when we have a chance exactly how it works and I will talk about I will focus this talk I will focus more on how to actually check this gate efficiently and why checking this gate only requires like field operations and EES rather than any heavy comp heavy

operations and so our first protocol for the checking was published in maybe also 2020 or 2021 I can't remember but it so we call it the Wolverine and then and and we have like and then like we have followup works and the other groups also have more and more Works building on top of this Paradigm to get it more and more efficient and more and more cap capable okay uh so uh so this is the first important slides so if you can't remember if you can can't remember anything that I talked about so far then this is actually one slide that is very important okay so we have aover and a verifier so so we want the prover and verifier to establish some kind of information theoretic Max so the

information theoretic Max can be view I mean is a like a like a a top of two values on each side so on the prover side the prover wants to supply a value X and get a value like M subx so this this is this value m is related to X that's that's why we call it m subx and now the verifier side verifier has a Delta which the verifier will use across the whole the whole protocol so this Delta is fixed and and the verifier will like this like protocal will give the verifier a value K so these are just some values and they satisfy this kind of relationship okay so so so the this is this a essentially a Mac so this Mac

equals to the key that is that is sent to the verifier plus the bit that Pro get times Delta so ex I mean so what's what's happening so what is this so essentially I mean we can think about it so Delta is something that verify p uniformly and it doesn't has anything to do with X this KX is also uniform from The verifiers View and because KX is very is uniform so it means that KX doesn't like a does not reveal anything about X so so this this information ma is a so-called zero knowledge or hiding re like to the verifier and then from the pro side Prov has a value MX equals

to essentially like uh this value ped with x times Delta so what what this means so now like uh so this is a authentication of the value in the sense that now if the prover wants to convince like let's say later if the prover wants to convince the verifier that at this point the value is X then the prover can send X and MX to the verifier and then the verifier can verify whether this equation is true or not however if the if the pro wants to cheat and the send a different uh X Prime then that then the Prov has to actually figure out a value MX Prime that also satisfy this equation because

this is what the verifier is going to satisfy okay if if if this is doable then like uh we know that this is true and this is also true if the Val Pro can figure out both of these two equations then the prover can essentially solve these two linear equation and figure out what is Delta but Delta is very Delta is never sent to the prover so the pro like the like Pro would require like there it's not computational feasible to compute data that means that it's not computational feasible for Prov to figure out to open the value X to a different value X Prime and and the letter verify like a like accept the value so this can be viewed so so this is essentially some way to authenticate

a value to the verifier without revealing the value uh another way to think about is that this is pretty much a commitment of the value X so this can be viewed as a interactive commitment from the approver to the verifier such that verify hold the commitment which is this value and the pro has the opening of this value which is this value if the pro wants to open the pro can send this value this is hiding and also binding because of what I just said is this for the o o comes from in Vector o yeah so this is a so because this data I mean so this is a uh so this relationship is o e and uh o e e okay so if this Delta is fixed across many many many many

correlations then this is a vector o in the sense that there there will be many many vectors of M many many vectors of K and many many vectors of X but the Delta is the same Delta so this is really the vector O So Vector O is just defined as this itm computation where Delta is fixed yep and uh so so this thing is actually very very nice because this has many many nice properties okay so the first property is that so I'm going to use this bracket X notation to denote the configuration that the prover has MX and x and verifier has KX and uh if the two parties hold a

authentication of X and authentication of different X Prime then they can locally compute the authentication of the summation of them by just like locally Computing all the values as the summation of just just sum up their own values respectively then that becomes the the SoCal the authentication of the summation of the values and it is also like you can also add a constant to the authentication by the verifier like updating the value and like two parties can also like it's like it can also like a multiply a constant to it like two parties can just like multiply the constant to their own values and the relationship still hold this is I mean like so all of them hold because the

constraint itself is a linear relationship so all the linear like operations on top of of this linear relationship is still good okay so okay so this is nice and this is actually very very efficient to generate so for pooling where we need where we need like V on top of like extension field this pretty much takes like 14 nond per entry uh and for like a larger field let's say if like for like this like a mer and Prime field then it's it's going to take 85 nanc per entry because some of the operation are are slightly more like like inefficient but I mean these are on the

nanc like level in terms of the efficiency we actually spent a lot of engineering effort when we had the paper in order to minimize the cost and you know because this is really on a nano second level even one more memory memory copy is going to kind of increase the cost by a lot so actually we took like it was quite a pain to actually optimize as much as possible like in this project but I mean but like like I mean the prot I mean our implementation is open source so so so so if anybody who wants to use it doesn't need to actually like optimize it anymore so um so this is the cost for like for the Semion is the case and the malicious case and in like for

the rest of this talk we need actually the malicious case so so this is uh something that we are more like interested in so the so in order to generate one such correlation the communication is 0.0044 bit per correlation and the cost is 17 and when the the the banner wi is small and is about 14 when the BWI is larger y so this is U so so I mean like I hope everybody is convinced that this like we can generate this kind of stuff very very efficiently Okay and like they are like like I think I may I may talk about I I think I talk about the construction of this kind of particle

like I put the slide like at the end so like if you have time I can really talk about how the high level idea what are the operations needed to generate them linger here for another moment so addition and multiplication and uh with constants are free operations as well as just addition isomorphic itself Y and it takes about back to your slide there uh 17 nond to prove a multiplication oh so this 17 is to generate a uh generate a uh a correlation like this set up this kind of correlation requires 17 nanc oh

I see so this this figure doesn't include I guess like total proving time for a multiplication yeah not yet uh I think I have a slide after talking about the ptical to to give a numbers and then that number is like include this cost and some other cost needed for the Z knowledge groups great thank you yeah uh yeah so like so as I said like so we want like a me we wanted like small memory so we want the memory to be as small as possible so this means that uh uh we want to follow so-called the gate by gate Paradigm so so what does it mean by gate by gate Paradigm so essentially like a like uh so essentially let's say if we have a circuit we want to like

once we prove a portion of the circuit if the internal wires of the circuit are no longer used anymore then we want them to be like we want to kind of deallocate uh the materials that we stored for them so so let's say like let's say like a so the first step in this kind of protocol is to actually authenticate the input let's say Prov has a witness which contains say an element and we want to First authenticate this element to the verifier so that they hold the authentication of the witness okay so the two part is using the pr like using the previous method can generate a authentication on a random value and then the Prov can just send

the difference of the witness and the random value to the verifier and then this value is the public value between proen verifier so they can just add this value to the authentication and by the homomorphism the summation of these two values will give us the authentication of the uh witness so in order to authenticate the witness we just need to send exactly the amount of information prop linear I mean exactly the same as the size of the winess so now two par is hold the authentication of the winess so now let's say if we have a circuit let's say if I have a maybe I can draw a circuit I can just draw a circuit quickly here okay so let's say if I have a circuit here I'm going to and draw one

more Kate here okay uh okay so what we wanted to do is that we want we want to First authenticate all the values so two party is whole authentication of these values okay and then we wanted to draw a protocal to convert these authentications to the authentication of the output wires and once we have the authentication of the output wires we don't we do not need to hold the authentication of the input wires of these two k anymore because these two gate are these two wires are no longer needed at at any part of the circuit so we can kind of deallocate the authentication for the input wires so after we prove the first gate we only have like three authentication let me see how can I can like change the color okay maybe I can change so after I prove

this this gate I only need to hold this wire this wire and this wire I only need to hold this three wire the authentication of this three wire and then I can uh after I'm done with this I can like a prove this gate and after I prove this gate I I can hold the authentication of this wire and this two the authentication of this two wire are no longer needed and then uh after I prove the first two gate I just need to hold the authentication of the of these two wires so so although the circuit is large I like I I do not need to hold the authentication of all the Wes any at any point I'm going to kind of thrw away the authentication after I I finish the proving of the gate I mean as long as this why it's not used elsewhere and

then I can I can for example I can prove this gate and then like just need to hold the authentication of this one so I can just progress like a like a I can just like for example use a topological ordering and like dynamically like forget about some of the authentications to reduce the memory and they can be done if the front end is smart enough like uh I mean pretty much any uh program language will will know which variable is local variable and which variable is not so it's a it's fairly it aligns well with like existing like understanding from the program language side okay so with this kind of Paradigm the important thing is this unit box okay so given the authentication of the

input how to obtain the authentication of the output so that's the most important okay and for addition gate it's easy because it's additively homomorphic so if we have the authentication of the input wires Computing the authentication of the output wir is free it's just local comput just like just addition so if this is a addition gate or if this is a actual gate then like this kind of propagation of authentication is easy so it's really just the question when it is a multiplication so when it is a multiplication then it will become more difficult so here this is the case of addition is just like people can just do the like a homop addition like locally so when this is a multiplication so the

prover and the verifier hold the authentication of the input values which we are we denote them as Alpha and beta Omega Alpha and Omega beta so these two values are authenticated okay authenticated by the Max and keys okay oh I have here so so these two values are authenticated and the parties have me and keys so now can first assume that the prover is going to do the operation I mean is going to be honest in that case the prover can actually send the multiplication of the so essentially this is what the output is supposed to be and then the difference of a uniform like a like authentication and then the parties can kind

of like obtain the authentication of the of the out desired output by actually doing a homomorphic addition of this public D value so why this is this is value because so D equals to this value and we we add this to SI so SI and Si will cancel out so this will give us Omega Alpha times Omega beta which is the desired output okay so if Pro is so so this means that for every multiplication Kate or end Kate we are going to send one value that is exactly the size of the field so if there is a bulling Kate we send one beat if this is a arithmetic G we then we send one field okay but this is assuming that the pr is honest so if Pro is honest then

everything is good but I mean of course the pr may not be honest and that's the whole point of sness in Zer knowledge proofs okay so uh in some sense like the now like the job is that we have so for a gate we have authentications of two values and also authentication of the output and we want to check that the authenticated value is actually a correct modifcation so that's the whole job okay so essentially majority almost all of the V based zero knowledge proof are the same up to this point okay so every Z know knowledge proof I need to kind of first do something so that parties get the authentication of the

input and output assuming that the pro that the pro is honest okay so now we have because we have many many gauges so we have many many topos of this kind of authentication people so now the rest of the job is really to check whether all these authentications are correct whether this actually form a correct multiplication like relationship that's really the whole point and uh how that's how like different works and try to do it more efficiently okay um so in our original work which is w w ring we actually adopted a very CL classical idea by uh n n o uh this is the paper I think uh uh maybe around 20 year 20

years ago and the context was so this paper is was I think it was published in crypto so it's crypto n OB I can't remember the year but it's definitely more than 20 20 years ago so this Pap was about making a classical NPC protocol maliciously secure and uh and in that and in that in that paper they talk about a particular way of checking this kind of triples which is so called the cut and buting so essentially like in the Wolverine paper we essentially uh observed that actually that kind of idea can be used here with a slightly better efficiency okay and but I'm not going to talk about the details of this because this is no longer the C of the art and this is fairly like complicated to explain so I just want to give people

some kind of context or kind of history of how the ideas like evolves over the years so this is kind of more or less like a borrowing from the previous like existing work and try to do it in the blackbox way okay and uh uh there is a another work that also try to use like the blackbox feature of the commitment so it will work for any additive commitment uh so that's the mac and cheese paper which is which also follows a similar line but they have a different way to do this kind of checking but but both this W and mean chees try to do this checking using so-called blackbox way so this is more less efficient but more General uh however like so in the quick saver version we are going to do

it in the we're going to do it this is this is uh let me try to put in somewhere else uh can you still see my screen yeah looks good oh okay okay I moved the Google meet like a floating bar a little bit so I want to make sure it still works yeah so I want so so this quick server actually doesn't use this kind of authentication as a blackbox way it actually utilize the fact that this authentications are linear so this is where the Improvement comes from okay so essentially like remember that uh so we have all these three toles uh all of them are authentications and we want to check whether the multiplication of this two

values equals to this value so that's what we want to check okay so we want to check this value and we know that this is true okay so we know that this is true already okay and we want to check whether this is true okay so in order to check that this whether this is true we're are going to plug in the fact that the things that we know back to this back to essentially back to this kind of relationship okay so we have omega gamma so Omega gamma can be replaced by uh by some of the like values here because Omega gamma we can we can we can we can rewrite this relationship as like as as Omega gamma so that's essentially what we are doing over here okay so Omega Alpha equals to uh let me try to see so like so this

value is like so all the Maxs are known to the prover and all the uh keys are known to the verifier so so like so essentially we can compute all we can compute all of them locally okay so this is some value that Pro can compute and this is something that that that also the prover can compute because prover knows the the original value and the Mac okay and this is uh uh and this is something that the verifier can compute because verifier has Delta and verifier has all the keys okay and and Dela I mean mean I mean and so essentially like so so like we want to have this term and this term sorry this is should be gamma okay this should be gamma so uh and this should be Alpha why I have all of them as a beta so this will be Alpha and this

will be beta okay so this term is supposed to be zero okay so so checking whether this relationship this equation hold I mean sorry checking whether this is this hold essentially means that whether we want to check whether this is zero or not okay so let me let me let me Let Me Maybe repeat a little bit and try to like like a uh to to like explain again exactly what's happening okay so this is the kind of the key of the whole particle I mean so we need to do all the like a sending but this is really like the I mean this is the most complicated part part of the map which is just a bunch of linear relationships okay so Pro sorry the verifier has all these values okay remember that verifier has the key so verifier has the key so

verifier has all the keys for for both of the input and output so verify has key Alpha key beta and the key output okay so uh so when we have all these values so we can write key Alpha as m alpha plus Omega Alpha times Delta okay this is by definition okay so KY Alpha equals to m alpha plus Omega Alpha time Delta and key beta can also be written in the same way so that's going to be m m beta plus Omega beta times Delta okay and then minus uh M gamma plus Omega gamma times Delta and then times Delta again okay so

this equation equals to this equation so this equation is something that Pro verify can compute locally and that equals to this equation why because we know this is how like the set the relationships are set up okay so now like we have so there are four terms over here and a two and two terms over here because like we have two terms here two terms here and multiplication can expand to four terms and we have two terms here okay so if we rearrange all these terms this will give us this this value okay so like the left hand side equals to the right hand side and the right hand side is the rearrangement of this term for example m alpha and M beta is just multiplication of this value and this

value and others are similar okay so this just a rearrangement we have one two three four five six six ter exactly this six ter okay so we know that we know that left left hand side equals to the right hand side and if we the fact I mean our job was to check whether this relationship is correct or not if this relationship is correct then this equals to zero okay because I mean mean right so so this ter will Zero and if this is zero then this equation is really a linear relationship with respect to Delta okay so this is the key okay so the two part is hold some value and they

can do some kind of local computation okay after they do some local computation they like they have four values so verifier I'm going to use a different color just to distinguish from what I have before this value and the verifier has this value the pro has this value and the pr has this value okay if the relationship is is correct and then this term is going to be zero then the two parties hold some value that that becomes a linear relationship because I me like because this is Delta Ian so this is like it this again looks like ITX so this is a linear relationship okay if this the the multiplication is incorrect then there is a quadratic term

over here okay so the the job of checking whether like a kit is correctly computed becomes a job of checking whether these four values satisfy this kind of linear relationship ship this is a line essentially so this is a linear relationship okay and in order to check whether this is a linear relationship the easiest way is to first we generate a linear relationship and then I use the linear relationship to mask this relationship that is supposed to be linear and then we check whether like the difference is still a linear relationship so that's essentially a way that we can do so this is how how how I wrote it wrote it here so if I have a linear relationship and if I have a two

linear relationship then the difference is still a linear relationship but if I have a linear relationship and a quadratic relationship then the difference will no longer be a linear relationship so essentially that is kind of the intuition of how we can check a gate by using the fact that is is a linear relationship okay but this is not good yet because we still for every gate we need to send two values that's not good we don't want to send anything more like because like this is going to be too much to send this is going to improve like increase the like performance like going to increase the communication a lot okay but I mean the the nice thing is that if we like recall that we have many many gate in a circuit meaning that means that we have many

many relationships that we want to check so for every gate we are going to be we we are going to check this kind of linear relationship for like a different linear relationship for each gate okay so now let's say if we if our circuit has a they million million anate then that would be become a million linear relationships okay so instead of checking each linear relationships individually so essentially what we can do is to linearly combine all of the linear relationships and just check the linear combination of all of the linear relationship okay so this use the fact that like if we have many linear relationship then the random linear combination of them is still a linear relationship and if this a linear

relationship that the parties cannot arit change okay so so instead of checking say a million relationships individually we going we are going to uh randomly combine like this linear relationships I mean I guess using snar word it's kind of a fold of all the linear relationships into one linear relationship and just check that one single linear relationship and this turns out to be fine so this means that in order to check any number of G the verifier just need to send a seed to the prover and then the prover just need to send two field element so this is going to be 256 bit in total to the verifier and and that will like that and that's it for checking all of the gate in the

circuit so so once the like a authentication are set up the communication is really constant there's not not really anything that the parties need to send and of course this you can f is out so it's really just one one message from Pro to verifier to check the relationship okay so so overall like the the protocol works by first authenticating every wire assuming that the pro is honest and then like the part is run a linear linear random linear combination of all the like constraint on the wires and get one linear relationship that they want to check and then like they can check it like easily using like a like using like this kind of existing like establish the linear

relationship okay so that's pretty much the high level idea of the protocol okay so like given that like uh we have the the protocol so now like we can look at the performance okay so like uh uh I think this is actually not up to this is probably not the St state of the art already maybe let me try to find the the latest number on on GitHub I always keep my GitHub performance more or less up to date but uh not my slides let me try to uh yeah maybe I can like I'm going to share screen again so this is this is more or less like the

like the like what we can do right now so for 50 megabit per second if when thre we can prove about 8.6 million gate per second and if we have for thre then we can prove about 19 uh million gate per second so this is about I mean pretty much like a so at this point like uh engineering is more important than the particle there are a lot of engineering effort to to make the to make the particle as small as possible so how much how many nanc is it so it's 10 to the 9 over uh 19 over 10 to the six so it's about 50 uh 50 NC per gate uh this is end to end every every cost is included

this is about 15 nanc per gate and uh I mean this and and it's really like just use a 50 megabit per second because even if we go to Local Host it doesn't improve the the Improvement the cost is like it's not getting more efficient like if if we further improve the bway so it's a so if as long as the communicate the bway is higher it's like it's about 50 you can get pretty much the the best like the performance that we can get which is about 19 million second per million Gates per second do you recall how many gates are in the shaw 256 circuit just to kind of put put it into a metric that snark people might be more familiar with so I think it has 200k about 200k for like one

compression it's uh yeah so you can yeah you can do the math yeah uh I think it's 200k I I mean need to I can't remember the I it sounds about right to me yeah okay yeah I mean I think it's between 100 and 200 I'll probably slightly more I mean it's on the order of hundreds of like 100 K yeah so yeah so it's a like a fairly efficient and like I mean it's not only efficient but but I mean the portal is really really lightweighted we don't need any I mean pretty much like any CPU in the past 20 years has all the instructions that we need to like push the performance so we actually run a protocol on some kind of very small like

a like a node on Amazon so these are the smallest node that I can find on Amazon that are not this uh kind of for bursting node for for the burst node like they the performance like changes over the time so I don't these are the ones that are not bur and smallest one noty so the cost of this are like five cents per second per per hour so like so we also run the particle on this kind of instance so for I mean so I think I I made this slid maybe three years ago I mean like I don't know the I think maybe the price of latte increased a little bit but anyway so for the price of one like a gr size cafe latte from starbar

we will be able to com like prove this number of endgate so this is this is what this is 3,000 billion andate so you pretty much like I don't know I would say that whatever statement that they want to prove uh you can prove with a cost with with the cost of less than one L if you need a circuit if you actually want to prove a circuit that is larger than 3,000 billi and gate I would really be interested to know what's the statement and the try to see whether there are ways to actually optimize it even for the I mean otherwise it's actually it's like really really efficient and like in terms of the gate per gate gate percent it's like a I mean I don't 10 billion

gate percent us sent so I mean uh by the way sent is no longer like issued officially so maybe next time I actually change it to something else but maybe quarters and next time so this is this is like this I mean I don't know like the affordability is really like as much as you could hope for from a cryptographic protocol this is like a very very affordable uh yeah and like we also did some uh not a quick five minute warning uh five minutes to top play hour uh there's not a tight cut off there but just thought I'd let you know yeah thanks y so we we always did some uh Apple to Orange comparison because like uh we like a like a i me like the the the one of the

r we really want to see comparison so we added it for them so so I mean like so for example here we did some we did a matrix modifcation of two like 1,000 Dimension matri matrices I mean there are many many different ways to do like to prove like matrix multiplication is all prove efficiently but here we just like like we try all of the protocol assuming that the we just like we don't know the structure of the Matrix so we just like use this as a way to increase the number of end gate without number of modification gate without getting too much trouble okay uh so for like uh so for like uh state of the art uh like zero knowledge proofs at that time it actually requires quite a

lot of like execution time well because it is like a big circuit but the proof size is very small this proof size is like 100 kilobyte however it actually need about 100 gigabyte of memory in order to prove this like a one million gate like circuit or maybe I think this is 100 thousand million G circuit because M multiplication is n Cube okay however for like for the V Bas protocols they really just need one gigabyte of memory okay the communication for like the first CH V is are still pretty high but like once like we using like the like the St of other protocal in V they actually get much much better so uh like

for example the communication is the communication is like is like much lower and if and and if you use like the special way to represent the circuit then they get it get really really like small like for this example okay so there are like a so there are like so like for some circuit they can actually like get very very small and it really so here I think the the circular size is 10 to the power nine number of multiplication okay and uh and like so like so we really just need a very small memory size for computing the even like this kind of circuit okay uh yeah so I hope now it actually uh like so everybody is like understand what I'm what I'm trying to say here so like

where is the cost of AES so there are two parts where we need AES one is generating the seed and expand the seed for random linear combination and this is for like getting the values that are supposed to be uh in finite field so if we have a different field then like like the multiplication beyond the Target that field and the mod and the communication is one and which it's interactive okay so there are like non interactive variant and that would be V in the head um like a work that is published more recently okay and I mean there are more optimizations that I but I don't think I have time to cover like like like more like inside like modific like optimizations specific stuff so I

probably great though you've covered a lot of ground uh we have a ra question uh here Al sure yeah could you please elaborate on circuit versus polinomial on the previous slide oh yeah yeah yeah so uh can you still see my slide yes so yes so there is actually uh maybe let me just go to the to C here so there is actually a Improvement I mean I would say Improvement there's a varant in quick saer that can prove arbitary number of pols with the sublinear to the uh number of gate so let's say so here I'm illustrating I'm I'm proving three polinomial all these three polinomial uh

are computed on top of five input wires and obtains three output wires one for each polinomial and the highest degree of the polinomial is five okay so in this case although there are many many gates to compute this pooms the cost of of like the communication cost of uh our protocal would be the sum of the input wires output wires and the highest degree of all the polinomial so in this case so this is so if the computation can be represented as a a bunch of polinomial where the degree is bondy then there is actually a way to actually further reduce the communication and

further increase the performance so this this is what I mean by polinomial so this is this extra optimization that that is actually very useful so this has fun like many many applications especially in the v in the head so they actually use this optimization to optimize the computation of ases because like in AES it's really just a bunch of s boox substitution box and the substitution box is really just a degate polinomial so they actually use this optimization a lot so so this is just a way to actually further reduce the comp computation yeah this is what I mean by polinomial over here so circuit is is the Baseline protocol polinomial is the

more optimized protocol great I hope that got your question there ali um all right yeah so we're at the top the hour we've covered a lot of ground I feel like there's still so many things that I personally would like to ask and so many things to cover but we've only got so much time here uh so yeah we'll definitely want to consider maybe splitting this out into uh multiple different things in the future here uh pending interest but yeah thanks so much uh shell for for your time today and for giving us a rundown on kind of a different class of Zer knowledge protocols that people at least in my circles don't really look at um all that

much and uh yeah it's been it's been it's been awesome to have you thank you yeah like if anyone has some any questions or want to try it out like feel free to email me or actually also email Shan like because tell me know more about how to like how to use them in like application but I if you have any technical questions also can feel free to email me great uh where uh so email is a good way to contact you uh any other venues you want to put out there uh yeah maybe I let me put my email hopefully that will capture the video recording but if not we'll uh put it on the YouTube description as well is

also on my homepage so uh it's not a private secret so it should beine Perfect all right well thanks so much for joining everyone and uh yeah we'll catch you next time thank you ch