ZKStudyClub - Sumcheck Arguments and Their Applications w/ Jonathan Bootle and Katerina Sotiraki

Transcript

uh welcome everyone to uh this edition of zk study club uh i'm alex pruden we have anna rose here as well we're hosting uh today jonathan boodle from ibm research and uh and katarina sotaraki of uc berkeley and this is uh the paper being presented is also co-authored by alessandro chiesa also from uc berkeley and yes we're very excited to hear uh from them today about some check arguments and their applications so uh jonathan over to you oh thanks very much for the introduction um so apparently i was speaking a little quietly earlier and um i also have trains going past my building so if there's something that you didn't hear um or you just want to ask a

question then just feel free to interrupt me at any time um okay so yeah the title of our paper is called some check arguments on their applications and this is a paper about succinct arguments so i don't need to tell anybody in the audience um that 16th arguments have had you know really massive impact in cryptography you know implemented in all kinds of blockchains and um um you know other kinds of products these days so in a succinct argument the setup is that we have um some kind of common statement and there's approver and a verifier and the approver wants to convince the verifier that this uh this common input actually represents a true statement

and the provenance witness so in this case uh the the statements like an arithmetic circuit or something like that with a specified output and the approval wants to convince the verifier that uh they know witness which produces the desired output when you plug it into the circuit um so obviously the prover and the verifier are going to they're going to interact exchange various messages and then at the end of the interaction if the verifier was convinced that the approval is really telling the truth and we've got a true statement here then the verifier is going to accept and otherwise reject um so we've got three different properties here that we want a six single argument to satisfy we've got completeness so if the approver has a valid witness then the verifier should always accept we've

got soundness which means if the proof is lying and they don't have a good witness or there's a bad common input then the verifier should always reject and then uh later on we're going to talk about stronger soundness properties like knowledge assignments and lastly the thing that makes succinct arguments succinct is the fact that the messages exchanged between the approver and the verifier are much smaller than the size of the previous witness otherwise the brewer could just send their witness to the verifier and the verifier could check everything for themselves so there'd be no advantage to the succinct argument otherwise so now all of the succinct arguments that we wrote about in our paper really stem

from the sum check protocol which comes from way back in 1992 so in the sum check protocol what's common to the prover and the verifier is a polynomial p with several different variables defined over a finite field f and then um like a public value public value from the finite field uh which is you oh yeah uh so dara has just pointed out that um yeah zero knowledge is also useful property of succinct arguments but yeah for the most part um we're not gonna consider zero knowledge today um uh you know you can see the you can see the paper for some uh you know some other other connections to uh zero knowledge and how we get some zero knowledge

succinct arguments um but back to the sum check protocol um in the sum check protocol we've got this publicly known polynomial and a value in a finite field and what we have here is that the approval wants to convince the verifier that the polynomial evaluations sum up to give the the value so how this protocol goes is the prover computes various smaller polynomials which they sent to the verifier and the verifier responds with these uniformly random challenges and then at the end of the protocol the verifier performs various checks on the previous polynomials and at the very end uh the verifier oh i think i've got some feedback

at the very end of the protocol um the verifier can perform one last evaluation of the original public polynomial at uh as a random point and then check that this evaluation is equal to some some other value that they already know so the subject protocol is useful for like reducing the task of checking this big sum of polynomial evaluations to checking just just one single polynomial evaluation which is much cheaper so the communication costs of the subject protocol are the number of variables in the polynomial multiplied by the degree of the polynomial in finite field elements and the soundness guarantee of this protocol is

that if the polynomial evaluations don't sum up to the right thing then the verifier should accept with a probability proportional to like number of variables times the degree over the size of the finite field so this is an important slide because it's this sum check protocol that all of the protocols in our paper are based on so hopefully hopefully everybody's at least at least heard of this protocol before so the subject protocol is actually really important it's been used in loads of different works so it started being used you know first of all in complexity theory in in the 90s and i think the first use

of the sum check protocol was for proving that uh the co-mp complexity class is contained in in ip but it's been used in other probabilistic proofs too um more recently we've got loads and loads of succinct arguments which which are usually based on the sum check protocol plus some kind of extra cryptographic ingredient and so there are absolutely loads of these and it's almost as if every new variant of the subject protocol gives you new types of succinct arguments with amazing new properties so there are univariate subject-based arguments which use a univariate subject protocol which works a bit differently and gives you different efficiency trade-offs for the approver and the verifier um there's a sub-check protocol for

error-correcting codes instead of polynomials and this gives you some really cool um zero-knowledge arguments with like great asymptotic properties and in fact the subject protocol is is just so popular and so widely used that we've got you know blog posts with titles like this the unreasonable power of the subject protocol by justin tala which is a really great blog post and i'd encourage you to check it out um but why is the subject protocol like this popular just what's so good about it well it's got various different useful properties we know that the sum check protocol can be implemented so the the prover runs in uh linear time um that's linear time relative to the

number of coefficients in the polynomial or if you link that back to a statement about uh circuits or something like that linear in the number of gates in the circuit um and actually the sum check protocol has another cool property it can be implemented in really small space so you can have a sum check approval which uses a really small amount of memory via some kind of like sliding window algorithm perhaps and then you know lastly the subject protocol is very special because you can make it non-interactive in the standard model without using random oracles but just using some very specially designed like correlation

intractable hash functions or something like that so yeah it's really a very special protocol so after having seen this slide and all of the work that's based on the sunshake protocol you might be forgiven for thinking that it's actually the the only protocol in the space of uh zero knowledge arguments and succinct arguments um well that's that's not necessarily true um so there's a there's another body of work um based on what we'll call uh split and fall techniques so um one of the first papers on split and fall techniques appeared in 2016 and this was giving uh succinct arguments for um arithmetic circuit satisfiability based on the

discrete logarithm assumption and um and based on that there were various different like optimizations and improvements and um more discrete log arguments for for different kinds of things um with with different types of properties um but split and full techniques are not just good in the discrete log setting they've been generalized to work with different assumptions and different cryptographic settings like pairing groups unknown order groups like rsa groups and there are even some post quantum split and full techniques that work based on lattice assumptions and you know all these split and full techniques work in basically the same kind of way you have a cryptographic commitment to a very long message which gets split into a few

parts um which are then you know combined together by taking some kind of random linear combination so since they all work in a similar way there are also some abstractions which try and unify all the different split and fall techniques across the different settings now split and fall techniques also give you some pretty efficient succinct arguments um in practice just like some of the subject-based ones and you know in particular some of the discrete log-based arguments are implemented in in lots of different cryptocurrencies okay so we saw why the sum check protocol is good uh what's so good about split and fall techniques well okay just like the sum check

protocol you can implement most of the split and fall techniques using a linear time prover so that's something they have in common um yeah similarly there are some recent works which show how you can implement discrete log arguments based on these split and fall techniques or you know based on rsa groups using like a streaming prover that runs some kind of sliding window algorithm um and uses a very small amount of memory um so that's another really nice property and that's well yeah that's also just the same as the sum check protocol um so you might wonder if there's if there's something more going on here if there's some some kind of uh you know deeper connection between the two types of techniques okay so um yeah spoiler alert as i'm

going to talk about our results like yes there is of course there is um so um in our paper um we we have a look at we have a look at these um these split and fall techniques and we produce like a variant of the subject protocol um which we call some check arguments and this basically tries to uh tries to encompass most of the existing um split and fall techniques and it shows that they're like directly connected to the um the original some check protocol and this is really nice because it shows that um you know these these split and fall techniques they're not really a separate body of work at all in fact they're you know they're really similar in spirit to the um the other types of succinct arguments

which are based on the subject protocol okay so now i'm going to talk a bit more about what some check arguments actually are so the goal of a sum check argument is to kind of give a type of sum check protocol which proves that a cryptographic commitment has um has an opening so the approval wants to prove to the verifier that you know given a cryptographic commitment c and some kind of commitment key ck that the proven knows a message which is committed inside that cryptographic commitment so our requirement here is going to be that um

the communication costs of the argument are much less than the length of the message and you know typically to get an efficient and you know highly succinct arguments for commitment openings you want to focus on commitments with some sort of special structure so the special structure that we're going to use so that we can incorporate these these subject protocols into the arguments is called the notion of like some check friendly commitments okay so we're gonna say a commitment scheme is some check friendly if you can take any commitment to like any message and you can express it as like a like a sum of um of different polynomial

evaluations um so let me break this definition down a bit like first um we'll be summing uh polynomials on the right hand side of a set of evaluation points from a set h where h is a subset of um you know some kind of ring or you know maybe a finite field the commitment space um c where all the commitments come from should be a module over the same ring r so on the right hand side the polynomial evaluation part is split into evaluations of a message polynomial over another r module m and

a key polynomial over another r module k and then obviously these two evaluations come from different spaces so we also incorporate some kind of uh combiner function to map them onto the the space of commitments okay so just in case this definition looks a bit like weird and scary or or too abstract um i'll show you an example which is like how to view a uh a pedestal commitment as a subject friendly commitment so a paradise and commitment is like a sum of products of like message elements from some funnel field multiplied by key elements from some cryptographic group like an elliptic

curve group or something like that so in this case um so one possible choice there are others but one possible way you could express uh pedestrian commitment as subject friendly is to choose h to be like minus one and one and you know the ring could just be like a finite field of prime order the message space is going to be the same finite field and the message polynomial that we're going to pick is like a multi-linear polynomial so every single element of the message appears in like exactly one coefficient of this this multi-linear polynomial um the key polynomial is really similar

except it's um it's actually a polynomial over the group instead of the finite field but again we've got like one element of of the key in each coefficient of the polynomial and then lastly the way you would combine these two is just um it's just like using um exponentiation or like point multiplication between the finite field and the uh and the group there okay so um so this might this might seem a bit heavy so like um yeah any any questions about uh like some check for any commitments or or this definition there was a little bit of a conversation

in the chat around i think this is an earlier question h is h a subgroup of f but then there's some conversation about that not being the case uh yeah um yeah absolutely so it doesn't have to be but um yeah i think it is it's often useful if that's the case um yeah there's some nice nice formulae for like um expressing polynomial evaluations if you're if you're summing over a like a multiplicative subgroup or something like that so it's often useful but not always necessary um where does h equals minus one 1 um come from in the patterson case um so actually um actually a bit later i'm going to i'm going to talk about

um i'm going to talk about the the protocol that you would run on this on this very example in a bit more detail um but to help to help look ahead a bit um um basically um summing over minus one one um it only retains all of the um only retains all of the monomials with like uh even coefficients and we're going to be able to show that that actually um actually kind of um selects all the all the terms in the in the pedestal commitment um in this song but um yeah we're gonna we'll see some explicit formulae later so it'll it'll become clear i'm sure yeah hopefully yeah

um l equals n here okay so if um if if like if n is the the length of the message as a vector then l l would be like um like log n so um if we have like uh if we have log n different variables l equals log n different variables and um we make a multi-linear polynomial then it's going to have like n coefficients uh like one for each element of the message of one feet yeah one for each element of the message or of the key okay great so given this notion of subject-friendly commitments

um i can actually move on to stating the main results in our paper and that is that if you have a commitment scheme which is subject friendly like on the previous slide and also satisfies this like extra invertibility property that we'll talk about about a bit more later then if you just apply the some check protocol with some small modifications to um to the polynomial in the middle of the slide then you get a succinct argument of knowledge for an opening to the commitment and this has communication costs like exactly the same as as the sumjit protocol pretty much um so the first thing that um

like uh you know like a really sharp observer might notice about this slide is that so the original subject protocol was actually the way i wrote it down it was all over uh finite fields and and this polynomial here if you have a look it's actually defined over over the commitment space um which is some kind of weird r module and not not necessarily a finite field at all um but that's actually okay because um it's it's pretty easy to show that you can run the subject protocol over like more general domains than fine it feels like different modules or polynomials of different groups so everything extends um you know quite easily to those cases and you know for the communication costs

of the subject protocol um you can you can keep you can keep the idea in your head that this is going to turn into communication costs something like logarithmic in in the length of the message okay so this is just about succinct arguments for you know proving that the prover knows an opening to a commitment but why don't we try and go a bit further um in lots of these prior works on split and fall techniques or um these other some check and polynomial commitment based works um what people do is they reduce like various mp statements like on cs or circuit sat to different statements about like scalar

products for example and then they can use the sum check to define design like efficient subroutines and to let the proven verify reason about different scalar product relations so in our work we actually build on our subcheck arguments and we can do the same thing so we actually have a very general some check argument lets you reason about scalar products over um bilinear modules and the idea of these bilinear modules is to to capture a lot of different uh cryptographic settings at the same time like all the settings that people have considered so far for these split and fall techniques um so using our scalar product argument

in this general setting as like a subroutine then we can get like quite general succinct arguments for different types of mp statements so what we'll consider is the r1cs problem of a ring r so given three matrices defined over the ring you want to ask whether there's a vector in the ring a vector z which satisfies a z times b z equals c z and now um you know typically to make these succinct arguments um the provo is going to you know make a cryptographic commitment to the witness zed and in order to give us the infrastructure to do that

um i'm going to talk about what um a bilinear module is and what that means so our scalar product arguments are going to work with commitments defined over these bilinear modules and for a billionaire module we're going to have like a left module which you can think of as being like um like messages a write module which you can think of as being like commitment keys and like a target module which you can think of as being like uh commitments and um some kind of bilinear map some kind of way of multiplying these two things together and then if you have this very abstract setup then basically you have enough structure to define some version of pedestrian commitments uh over the

modules and you can do things like run snow protocols over these modules and then like um you know given that we'll be able to um give arguments of knowledge for reasoning about things like pedestrian commitments and like more general scalar products commitments over these modules we'll be able to get um an argument about r1cs over over certain rings so whenever we have a bilinear module which has some kind of extra security properties and whenever this left message space is also a ring then we'll be able to get an argument for r1cs

over not the original ring but like a closely related like quotient of this ring and the proof of time here and the verified time are going to be like um linear in terms of operations in in all of these modules so you know comparing to the discrete log setting you can think of protocols which might use like a linear number of group operations and then the proof size is going to be like a logarithmic number of commitments and that's logarithmic relative to the size of the rcs instances okay so i guess this might be a good time to like um you know pause and see if there are any more any more questions um about uh maybe maybe about this bilinear

module setup or anything else so far all right if there are no questions i'll i'll just head on so one of the nice things about having this this very general setup um with these bilinear modules is that if we just instantiate these bilinear modules somehow then we can recover rncs arguments for all different applications so um there are many in our paper but one of the new ones that we came up with is like a lattice-based succinct

argument for r1cs defined over the rings that people use in lattice cryptography so this this will give you some kind of plausibly post quantum secure succinct argument um so this is really exactly the same theorem as on the previous slide except i've just changed all the domains and things to be um like the rings associated with um lattice cryptography and the um the ring sis problem so so how does this differ from other existing improved systems using lattices um let's see so um so i guess this stocks um try um

i thought it's just codes doesn't it okay yeah yeah that's right so um yeah so fry it frey uses codes and um actually it doesn't use any it doesn't use any hard hard problems um related to error correcting codes it kind of just uses the distance properties of the code whereas um the different series this is more like um let's say like a lattice analog of bulletproofs where you're using um hard losses problems to give you um to give you like a a cryptographic commitment to a long vector okay so this is completely new really um so well i guess um i i guess so what's new here is that um so there was already like a lattice analogue of bulletproofs but just for

um just for proving that you knew a message inside a long commitment but it wasn't really extended to um you know proving different statements like like on cs for example yeah and um you know it wasn't really it wasn't really in a framework either with the with the other split and fall dating so there were some frameworks but not quite connected to the the subject protocol um but having said that we do there are some concurrent works out there so um um like there's another cool concurrent work which um which which proves uh which proves like a very very similar theorem basically um lattice based succinct arguments for np statements and there are some other works which um they prove like strong limits

on um you know just how efficient just how efficient these things can be and um they have some pretty good and cool um instantiations of different lattice rings which you know hopefully are going to lead to some you know some exciting and efficient you know practically efficient lattice based succinct arguments oh there's a question maybe i can say it for kev can you explain why i would use this commitment scheme versus ipa as a commitment scheme um yeah and so i think i think praticia's um patricia's just

posted uh posted a comment about that and um yeah i think um i think i basically agree so um um oh we should we should maybe say it for the people watching the video yeah yeah absolutely sorry i'm about to read it out so um pratici says this is generalization of inner product commitments this particular commitment scheme is post quantum actually um some of the commitment schemes that we that we deal with in the paper and that we use for these succinct arguments are like generalizations of the ipa commitment scheme but just defined over these um these bilinear modules um so that you can instantiate them in like all kinds of settings like you know pairing groups or groups of under an order or um all based on like uh based on lattice

assumptions um so um so really really should fit in to the same kind of framework all right so um that's another one of the the main results from a paper um and you know next for the rest of the talk um i'm going to go into a bit more detail about um how all of these things work oh i see there's another question so no gains in terms of communication complexity um uh so no that's that's right um so we have the basically we

we were able to replicate all the communication complexity of um of other like succinct interactive arguments um based on all kinds of different cryptographic assumptions um but actually based on based on this framework of some check arguments we're able to you know pretty quickly and easily come up with like um lots of new results so for example the generalization of these um these inner product arguments into you know um based on different assumptions like lattice assumptions um so much easier to come up with once you have this subject-based framework so we're able to kind of uh you know fill

in a lot of blanks and like come up with come up with um inner product arguments under lots of different assumptions um you know really quite easily so no efficiency gains but like lots of um lots of extra combinations that people hadn't investigated oh and there are still some open questions um which um which come from our work so um firstly um even though some of the some check arguments still investigate use assumptions based on lattices um which are plausibly post quantum secure

uh we still need to analyze the security of uh some check arguments against uh quantum adversaries so like a quantum prover or quantum verifier that might make use of superposition in strange ways for example so we're using quantum hard assumptions but we don't necessarily have quantum security proofs just yet um another thing we'd like to do is investigate new lattice instantiations from these concurrent works and see how they could lead to different concrete performance improvements from protocols and using these suncheck arguments we were able to capture almost all i would say almost all of the the

split and fall techniques um from different parts of the literature um but still not quite all of them so there are a few um so there are a few like um uh like the the dory protocol for example or a couple of other different works that we didn't quite manage to express as some check arguments and we're pretty confident that it can be done um either in our framework or like a small generalization but we just didn't quite get that far so that's still that's still something that's open the the um analyzing the post-quantum security does it seem like there'll be any obstacle to that or is it um did you expect it to be quite

straightforward um let's see um it does seem it does seem quite hard so i think generally the difficulty with these multi-round protocols is that um all the all the split and fall techniques in there their knowledge extraction proofs use a lot of rewinding and it's really difficult to do rewinding against quantum adversaries um there are all kinds of problems with um with with making quantum measurements and and stuff like that um so i think it does seem quite hard um but what gives me some hope is that um actually people have investigated these things for um for the sum check protocol and you know maybe maybe that will provide some some inspiration and um and help with

the analysis so so the best analysis i'm aware of of bulletproofs like um protocols is um the one that uses states restoration soundness is it maybe possible to have a quantum analog of that because that produces tighter proofs than the techniques yeah i mean i guess i guess that kind of thing would be the hope um yeah i think it's really interesting and you know i haven't really looked into it too much so far but yeah i think it's interesting and important all right so now let's talk about some

of the techniques that we used in our paper so we're going to start off by talking about how succinct arguments for proving you can open pedestal commitments can be expressed as some check arguments and you can see this you can see i've got a car icon um on the slide here and a little diagram and we've actually got a petrol pump and that's because um understanding the understanding how some check arguments are connected to pedestrian commitments is is really the main part of the talk and i think if you can understand this part then you can probably understand um your most of the following um like applications like modifications generalizations so

um i'll start off by talking about pedestrian commitments and their connection to some check arguments then we'll talk about like scalar product or like inner product commitments um so then we'll generalize a bit further up to some check friendly commitments like up to that point in the talk we'll just be talking about um groups and finite fields so um we'll be talking about the same cryptographic setting that like normal pedestal commitments are defined in and then finally at the very end of the talk we'll generalize just one step further and we'll talk about how um well give some hints anyway about how the protocols can be made to work in like very general uh rings and modules and um in particular this lets you this lets

you see how to come up with like uh you know lattice instantiations and how to give succinct arguments based on lattice assumptions and of course like i'm just going to scratch the surface here but there are many more results in the paper so i'd really encourage you to have a look at it okay so with pedestrian commandments um the common input for the proven the verifier is um a pedestal commandment over a group and a commitment key which is a vector um vector of group elements from the same group and the claim is that the approver knows a message such that when you take

the scalar product of the message and the commitment key you get the original pedestal commitment so how do we give a succinct argument of knowledge to show that the approver knows an opening to the pedestal commitment well what we're going to do using the using the polynomials that we're given in like the pedestal commitment example a few slides earlier the provo and verifier are just going to run a some check protocol so the polynomial that we're dealing with here the polynomial the prover and the verifier running the some check protocol for is like a product of the message polynomial and the commitment key polynomial and you

can you can actually take the product of these two because um yeah again this is just like exponentiation or scalar multiplication between field elements and group elements um and so the approver and the verifier are going to run a sum check protocol and they're going to prove that when you sum up evaluations of this polynomial you get n times the original pattern commitment so not quite the original one but the end times but that's okay because if the prover knows how to open n times the person commitment then we can divide by n and the privilege should know how to open the original pedestal commitment too so the proven verifier just going to run a subject protocol

with these polynomials and then the one difference from um like the classic some chick protocol is that at the end when the verifier wants to you know compute an evaluation of the polynomial um at a random point actually they can only open they can only open half of it so the polynomial that we're dealing with is like a product of like a message part um related to the message a and a key part related to the key g and you know since the message is private and only the prover knows it the verifier can't compute the um the pa part of um of the polynomial by themselves

so the approver has to send this part to the verifier so the verifier can make can make a final consistency check so the communication costs of this protocol are going to be three log n group elements and these correspond to all of the sum check polynomials that the approver sends to the verifier which are polynomials defined over the group g and they're all quadratic polynomials so they all have three coefficients so that's like um in log n rounds log n variables in the polynomials we've got three log n group elements and the log n plus one field elements comes from the verifies random challenges and this

final evaluation that the approver sends to the verifier now the verifier's computation in this protocol is a linear number of group elements and this comes from the cost of evaluating the the commitment key part of the polynomial at a random point so the polynomial's got n coefficients one for each element in the commitment key and then when the verifier commit computes this evaluation um well that's where all the costs are coming from so although it's a although it's a little bit different um this is actually strikingly similar to the um the original split and fall techniques and um there's a good explanation of this um given in

appendix a of a paper um so you know the the only real difference at a high level is that um you know some of the coefficients of the message and the key are like shuffled into a slightly different order and the split and fall techniques in this 2016 paper um actually use a small optimization of the protocol here so that the communication cost is like two log n group elements instead of instead of three log n but still these protocols are really like um really strikingly close and there's like a good explanation of how this works in the paper okay so um next i'll be going into like why this protocol is actually

you know complete and sound um but before i do um are there any questions about this like high level overview of the protocol uh yeah you can can you just uh explain again why it's uh where the three comes from right so um so the polynomial that the prover and the verifier are running the sum check on is is a product of two multi-linear polynomials um so in particular the um like the the degree in any variable of this polynomial is three and so when you run a sum check protocol um on this product of two multi-linear polynomials

all of the all of the messages that the prover sends to the verifier are going to be quadratic polynomials defined over the group g and since they're quadratic polynomials all of them have three coefficients so the communication costs are going to be three group elements per round now actually um the split and fall techniques in the 2016 paper are an optimization of this kind of idea down to two group elements and that's because um some of the group elements in these quadratic polynomials um they actually depend on group elements that you've seen already so um instead of like sending extra group elements and checking

consistency um between them using like different equations as part of the sum check you can actually avoid sending like one extra group element per round and instead of performing like different consistency checks you can use the same equations to um to like define the next group element that would have been sent so it's um it's really a similar kind of thing but it's like an optimization where you just um avoid sending some redundant information so you're saying the other direction is is also true that if i want to do a sum check on a product of multi-linear polynomials i can i can actually do it uh i can save uh like a field element in each round if i do a

splitted fold um yeah that's right so yeah in the original so in the original suncheck protocol um you could if you wanted to um you could always avoid sending one of the coefficients of each of the each of the previous polynomials and instead of doing um instead of doing the consistency checks between different polynomial evaluations and and things like that you could use the same checks to actually um come up with like a definition of what the last coefficient should be so um yeah you can apply the same optimization to the like the field based subject if you want to thanks quick questions on things i

should think of um as p sub a and p sub g respectively as being basically multilinear interpolations of the of the a and g vectors right um so interpolations is another option um you can also do that but here i'm thinking of each element of the message as being one coefficient of the multilinear polynomial i think okay i'll take some time to think about that yeah you i think um you can also you can also come up with um a protocol that uses interpolations if um if you prefer

i think oh i see so so you can use any basis and that's the difference between say monomial or lagrange or some other basis right yeah so um so actually like a reason for going a reason for going with the multilingual polynomials is um just actually to to make the connection between um split and full techniques in um in this 2016 work to get a protocol which was like quite close and like almost equivalent to that um but uh yeah like other bases should also be possible yeah that that might actually relate to something that we've been thinking about for um

halo because um the polynomial commitment scheme in halo is um is very similar to bullet proofs so um but part of the expense comes from um doing ffts to convert between the grunge and um minerva basis so if it was possible to avoid that and stay in lagrange basis that would be nice oh yeah yeah sounds interesting okay so next um i'll talk a bit about the completeness and soundness of this this protocol before going on to talk about more complicated commitment schemes okay so completeness we want to know

that if the original pedestal commitment was properly formed then the verifier is going to accept at the end of this protocol so what this subject protocol in the previous slide is checking that is that a sum of polynomial evaluations is equal to n times the original pedestal commitment and if the prover is telling the truth and the scalar product relation between the message and the key and the commitment holds then you know kind of by hypothesis we also know that that this equality holds here so in order to know that the the question mark double arrow is actually inequality we need to investigate the the third side of the triangle here

um so in order to show completeness what we want to prove is that um this sum of polynomial evaluations um gives us the scalar product on the right hand side so completeness is basically linked to this claim about like summing evaluations of multilinear polynomials okay so i think this is um this is an explanation of a question we had earlier i think so um if we sum um the products of multi-linear polynomials over minus one and one then whenever any variable appears with with an odd degree

in a monomial then that monomial is just not going to survive inside the sum it will just be completely cancelled out as part of the sun so the only monomials that actually make contributions to this sum are the ones which have like all even um or even exponents and so actually since we have like a product of um two multi-linear polynomials we know that the like the exponents in the message part and the exponents in the the commitment key part um just come from zero and one so the only way to get a monomial with like all even exponents

is when you multiply the i term of the message polynomial like the the ith message by like the i term of the the commitment key polynomial so like the i th element of the key and then um if you follow the logic like this you can see that um like every term used to produce the better commitment comes up exactly once as part of this sum okay and so um considering the triangle on the previous slide this is enough to prove that the protocol is is complete okay so now let's talk about soundness so the kind of soundness guarantee that

we want to prove for our protocol is knowledge sinus so for knowledge samus we're going to have some kind of efficient extract algorithm that takes as input a tree of accepting transcripts for the protocol and a commitment key and a commitment and finds a good opening message m which opens the the commandment c so if our original subject protocol looks like this then this is what the knowledge sounds extractor algorithm has to deal with like a a tree of transcripts where the top of the tree corresponds to the provers first message in the protocol um the the first three branches of the tree

um going from like level one to level two um different values for the verifiers challenge so and then um uh at each of the the leaves we have like a second proven message um for each of those we've got like three possible continuations with three different verified challenges and and so on and so forth and so given this this information as input the knowledge extractor is going to compute a um an opening message m right so um what we can prove for the pedestrian commitment is that given a three retreat of accepting transcripts for a certain key and commitment we're

going to be able to find an opening so um why three um so in this case it's going to be it's going to be threery because essentially what we'll need to do is um lots of interpolation on the the quadratic polynomials that the prover centers part of the the the sum check critical and so yeah to interpolate a quadratic polynomial um we're going to need like three points at each stage i see okay thanks um so you can think of like the proverb's

final message so the final evaluation that the prover sends to verify the evaluation of the message polynomial is kind of like an opening of a commitment which has length one and in the three tree we'll have three to the power log n of these openings of size one um for this uh final value that the verify has um the the last subject polynomial evaluated as a random point which you can think of as you know a commitment so we'll have three to the log n commitments and openings of messages of length one and the the general strategy is going to be to operate layer by layer in the tree

and every time we'll reduce the number of openings we have by a factor of three but we'll be computing openings which have double the length and they're an opening for a commitment which is like which is a commitment related to the the next polynomial up um as part of the subject protocol so we'll go from openings of length one to openings of length two and uh you know so on and so forth and doubling as we move up the levels in the tree and then finally we'll get to one single opening of um n times c which is like a multiple of the the commitment approval and verifier where we're reasoning about so that's when the extractor will have succeeded

in finding like a valid opening message um because you know it's an opening to nc and we can just divide by by end to get into the original commitment so this is the this is the high level strategy um and if we start zooming in on round eye we're going to see how how interpolation comes into play so what we'll want to show um in like the the ice step of this argument is that if we have openings for like um if we have openings of a particular length um for three different commitments um which are you know subject polynomials evaluated

at three different random points then we can find an opening which has double the length to a commitment which is like an evaluation of the next sum check polynomial up in the subject protocol okay so since all of the proof of subject polynomials are defined in terms of these multilinear ones we can show that all of them are quadratic polynomials and it's a it's a three-year tree that we're dealing with so uh each step in the three-year retreat we're going to have openings for three evaluations of the ith subject polynomial q i okay and

our first goal is going to be to find to you know to use these openings of evaluations of the polynomial um to actually find openings of uh coefficients of the of the subject polynomial and then if we have openings of all the coefficients of the subject polynomial then using some equations that we know as part of the subject protocol we can move towards an opening of like the the next polynomial up in the tree and this is going to be like um this is going to be guaranteed by some of the checks that the verifier does and like every time we do this we're going to be dealing with going to be dealing with like a slightly different commitment key which has

double the length okay so the commitment key every step is going to be like um a partial evaluation of the um the the commitment key polynomial that we used as part of the subject protocol and so every time you kind of evaluate this polynomial in one extra variable kind of compresses the compresses the number of coefficients in the polynomial by a factor of two so this kind of explains why the the commitment keys get um smaller and smaller as you go down the tree

or like you know bigger and bigger as you go up um if the three tree contains like three value three openings of like different evaluations of of the id subject polynomial then we can rearrange those using some linear algebra and we can express like the i commitment key in terms of like the the i minus one commitment key and then we can rearrange those into openings which have double the length with respect to the the i minus one the commitment key and then since we've got these openings for like three different evaluations of the subject polynomial um we can interpolate and we can use linear algebra to find

openings of all the coefficients and then you know finally we'd um would use the equations in the sum check protocol to get openings for the the next polynomial up in the tree okay so that's um that's how the soundness of the um the suncheck argument for pedestal commitment works are there any any questions about any of the details here or or how different parts of this would work okay great um oh actually maybe there is

one question oh i guess okay i guess there's no questions so i'll move on to the next part um actually it's worth saying that um so the the procedure here that we had from moving to you know openings commitment openings of like a particular length to commitment openings of of double the length is is actually um that's actually a general property that we define for like general subject-friendly commitments that we call the the invertibility property which we're going to get to we're going to get to that form of like more general commitments a bit later on all right so next we're going to talk

about scalar product commitments via some check arguments okay so here for scale product commitments the the setup is a bit more complicated um the common input between the proof and the verify this time is going to be a commitment to um a left message vector a and another pedestal commitment to a right message vector b and then finally a um a commitment to the the scalar product of the two of them and then actually what it means to prove you know an opening of this commitment is to prove that you know uh two committed messages which satisfy some kind of scalar

product relation um so this is going to turn out to be like the main building block of six single arguments for rncs but anyway each of the components of the scalar product commitment here basically has the same structure as a pedestal commitment so what protocol are the proven verifier going to run well they're just going to run a subject protocol which has three different components but like every each of the each of the components of the polynomial is very similar to um something that we've seen for the the pattern commitment so the first component is a product of two multi-linear polynomials and gives you a commitment to the the

left part of the message the second component is for the right parts of the message and then the last component is for the the scalar product of the two um so this is really really similar to the some chick argument for pedestrian commitments just with um three different components uh and is you chosen the setup or oh that's the key okay yeah so yeah you can be you can be part of the key here um so this time at the end of the protocol the um you know the the message parts of the polynomials involve um multilingual polynomials in a and b that the verify can't evaluate for themselves so this time the prover sends those um

two evaluations polynomials related to a and b and then the verifier does um does a similar kind of consistency check to what we've seen before and then again the communication is is going to be succinct it's going to be logarithmic in the length of the message vectors and the verifier computation is going to be linear because just like before they have to evaluate different polynomials in in all of these group elements okay so completeness and soundness of this protocol is is fairly easy to describe completeness to show that the verifier always accepts basically we just need to observe that

every component of this commitment behaves exactly like one of the pedestal commitments we've already seen and then use like similar kind of reasoning to what we've already seen and for soundness um this is interesting because qualitatively we get a slightly different result to what we had for better commitments so um for pedestrian commitments to get knowledge soundness we didn't need to use any any additional properties we just needed a tree of accepting transcripts and no computational assumptions but actually for the scalar product commitments we need to use the binding property of the commitment scheme and we actually need to use a foreign tree of accepting transcripts instead of a

three retreat so how this argument works is basically to apply the extractor for pedestal commitments to each of the individual components and then this is good because it gives you openings for the the first and second components of the of the scalar product commitment um but you don't necessarily know that they're consistent with the the last components of the commitment so um this is where the computational assumption and the um and the extra transcripts in the tree come in to allow us to to show consistency between the different components of the commitment okay um so you know um it was pretty easy to go

from pedestrian commitments to scalar product commitments so let's not stop here um oh but before we do move on um i should say that um the you know like again the the fact that we can um that we can go from this foray tree of accepting transcripts um to an opening for the scalar product commitment um comes from comes from this kind of general invertibility property of the scalar product commitment scheme which is something we can define and something we're going to see in the in the next next little section of the talk all right so next we're going to move all the way up to some chick arguments for general sum

check friendly commitments okay so so just here on the slide we've got a reminder of the um the structure that makes uh a commitment scheme some check friendly and so how are we going to give succinct arguments for for openings of such a commitment um what will the sum check argument look like okay so this time the common input is just going to be given in terms of the um well just like before it's going to be given in terms of the the commitment and the commitment key ck and the claim this time is that the proven is a message which satisfies this um like some check

friendly sum of polynomial evaluations from the previous slide so again we just have some check protocol on like um the appropriate polynomial um given by this equation and just like in the pedestal commitment and scalar product commitment cases um at the end of the protocol the prover sends an evaluation of the message part of the polynomial to the verifier so the communication costs of the protocol here are the communication costs for the subject protocol and sending the final evaluation and the verifier's computation this time is you know computing an evaluation of the key polynomial

and one application of this this function f which is going to combine the the message part of a final check with the the key part of the final check together so yeah this this f is just uh just coming from the the definition of some check for any commitments that we had okay so completeness of this protocol just kind of follows directly from the definition of subject-friendly commitments and the fact that every subject-friendly commitment can be written as a sum of polynomial evaluations and so this is the point for some chip

friendly commitments where we define like an abstract property invertibility for the commitment scheme and so whenever some chick friend the commitment scheme is invertible then we're going to be able to take a tree of accepting transcripts for the the some check arguments on the previous slide and find an opening message which opens the the commitment c so the high level strategy is to work inductively just like with the pedestal commitments and instead of using this this linear equation solving which we knew we could do for pedestal commitments we're going to invoke this abstract invertibility property at each layer of the tree okay um so what is this invertibility

property anyway it's the property that allows us to you know gradually climb up the tree and if we zoom in on um on a particular part of a tree of transcripts let's say like a korey tree of accepting transcripts um then we've got different things in this part of the tree we've got the i subject polynomial q y of x and we've got some sort of openings of like evaluations of this subject this subject polynomial and what we mean by openings in this case is that um we've got some smaller polynomials p1 up to pk which satisfy a kind of a kind of sum

check relation which is related to the one used to compute the individual commitments just um you know with randomness in a few of the positions instead of summing over every single variable so those are the ingredients for the invertibility property and what invertibility enables us to do is find a polynomial p which similarly is like an opening for like a sum of evaluations for the the same subject polynomial in in a kind of similar way and um if you like paying attention to the the definition of invertibility uh what we had in the case of pedestrian

commitments was that whenever we kind of inverted or moved up a layer in the tree we were dealing with openings with messages which had double the length every time so what that means here in part of our as part of our abstract definition of invertibility is that the new polynomial p that we find is going to have an extra variable compared with the original uh the the polynomials that we started with in like a lower level of the tree so a polynomial with more variables has like more coefficients and this is kind of analogous to the the length doubling of messages in the in the pedestal commitment case so in the paper we actually show that um

lots of different commitment schemes are invertible so we've got pedestrian commitments these scalar products commitments and commitments to linear functions and um as a special case of these we've got we can show that like polynomial commitment schemes for example also have this invertibility property and we can also run some check arguments on those all right so any any questions about um this this notion of uh invertibility for subject friendly commitments [Music] this was definitely the part i had most trouble understanding questions

okay does k have to be constant um let's see um i haven't really thought about whether it whether it has to be constant or not um i guess if the if the depth of the tree is logarithmic then um you know it would be a problem if if k was too big right it might take too long to um to to gather all the the transcripts in the tree um and you know certainly for all the commitment schemes in our in our paper we're we're considering like constant values of k okay but then i guess you know you could be dealing with like um a sum check protocol that had uh fewer variables and then um you know

probably would be okay like reduce um kind of have like um you know maybe um maybe a non-constant number of transcripts in in every round but just like a constant number of levels in the tree or something like that so so it's just the size of the tree has to be small enough basically that's it yeah the number of leaves in the at the bottom of the tree should be oh i see poland thanks for the question all right so um the last part of the talk is how to generalize from the these subject-friendly commitments um which you could have defined over um you know groups like pedestrian

commitments where originally um two commitment schemes defined over rings and modules and this lets you do things with um with lattice assumptions and get plausibly post quantum secure succinct arguments okay so how to move from groups to rings everything we've seen so far extends pretty easily to general vector spaces over different finite fields um so we've been talking about pedestal commitments in um you know cryptographic groups with finite fields but if you wanted to you could use bilinear groups and we can still come up with scalar products commitments to those where um some of the messages and commitment keys are under the first source group

and some of them are in the second source group and then the commitments live in the in the target group but you know how can we how can we go further and get to lattices and groups of unknown order like rsa groups what we need to do is come up with an abstraction for mathematical structures where split and fall techniques or different zero knowledge different zero knowledge and succinct arguments um work and have you know good security proofs so the abstraction that we use is this um this bilinear module abstraction um that was used to prove like our a second theorem about um rncs in very general settings

so the motivation for this is um to try and be able to come up with like very general pedestal commitments so an all module m is like a generalization of effective space but just with um with a ring r instead of a finite field and you know as i mentioned earlier um a bilinear module is going to be this collection of our modules with a left one a right one and a and a target one and then a bilinear map which lets you multiply left and right elements together to get target elements so you can think of messages for a pedestal commitment scheme being like you know somehow like small left

left module elements and like the keys of a pedestal commitment scheme as being like random right module elements with pedestrian commitments living in like the the target module t and like as an analog of the the discrete logarithm assumption um we've got this kind of bilinear relation assumption so more explicitly if we have a you know a pedestal commitment which is computed like this we'd say all the messages a come from the left module the keys gi come from the the right module and then commitments live in the the target module um and we've computed the better commitment by multiplying messages and keys using e adding them together because we can add

elements in the target module um the binding relation assumption is kind of an analog of the discrete logarithm assumption with many bases and this says it's hard to find like um a small message a from the left module so that when you take the scalar product with the commitment key this is equal to zero and this is like a generalization of um the discrete logarithm assumption or maybe of lattice is the um the cis assumption and there's a pairing analog of this too um and you know even if we define this this crazy general abstract pedestal commitment the subject protocol is still going to work because you know we're dealing with modules and you can still

define uh polynomials over over the ml mr and mt modules the only real difference from from what we've talked about already is that your messages have to be messages have to be small somehow um in this bilinear module set up like for example in a lattice setting um you can only usually use lattice commitments to commit to like very small message elements um so in order to incorporate these recurrent requirements we've got on like the smallness of particular messages we'll need to put some extra checks into um like a some check argument for like um general pedestal commitments over

by linear modules right so the last protocol of the day is some check arguments over rings and bilinear modules and what we've got here is the same um commitment and commitment key as common input and a some check friendly a subject-friendly commitment over uh by linear module would satisfy the the same subject relation so the commitment would be like a sum of polynomial evaluations just like before um and the only extra requirement we have is that a message should be short so that the norm of the message committed to inside the commitment

should be less than a certain size bound so the protocol here is almost exactly the same as the protocol for some check for any commitments we've already seen the proven verified has run another subject critical the prover sends an evaluation of the message polynomial at the end of the protocol and as well as performing the same consistency checks as before the verifier has to do a last check that the provers evaluation that they've sent has no less than a particular size band another difference when you want to work

over these special bilinear modules and you know capture settings like lattice-based settings is that you want to use the special challenge space for the sumcheck protocol um even if we weren't dealing with commitments and we were just dealing with like normal subject protocols over these rings then it would be necessary to use these um these special challenge spaces um so please take a look at our paper for for more details on these and in particular like the um the band that the approver checks on the the band that the verified checks on the provers evaluations is um it's just a simple bound that you get from working out like um um uh the the size of the points um where the prover evaluates the

polynomial and like the the size of each element of the message right so when talking about soundness of these front this final protocol um the difficulty is that when you work over these rings and modules things are not as nice as they were um when we're working with finite fields in different vector spaces it's hard to do linear algebra over over very very general rings and the reason is because not all ring elements have multiplicative inverses and further we want to make sure that whatever we extract using our knowledge extractor is a message which has a small norm um and we didn't have that kind of requirement with normal pedestrian commitments

so um to to capture the soundness of this like this final version of the protocol um we have a generalized definition of invertibility which deals with relaxed openings um and what a relaxed opening is for example for a pedestal commitment is it's a mult it's an opening of like um not the original pedestal commitment but like um a multiple of the original pedestal commitment and if the provers message was supposed to have norm less than b then it could be that the knowledge extractor can only find an opening message which is which is still quite small but just has a bigger norm than what the honest prover started off with so there's this gap

between what the honest prover uses and what the knowledge extractor can get um now when working with lattices um we we kind of instantiate the the bilinear modules um with you know different rings from the lattice settings and then um you know using some of the results in our paper we'll spit out different values which tell you like how big the gap is between what the knowledge extractor can do and what the honest proof uses so in particular if the honest prover started with a particular pedestal commitment then the knowledge extractor is going to um produce an opening to the same pedestal commitment just like

multiplied by like a big power of 8 or something like that and unlike in the finite field setting in the latter setting you can't necessarily divide by eight divide your openings by eight and still have like a good opening of um of a pedestal commitment but you know we gave a very general analysis in our paper and um these two concurrent works are much more focused on the specific case of lattices and um you have like much more um efficient analyses in their papers okay so a last the last thing you might be wondering about is um well if we can only deal with um

relaxed opening competitors commitments how can we actually reason about like r1cs and like general statements like um wouldn't we only get um you know a solution to like a relaxed r1cs instance so we can get a we can get an exact r1cs instance um we don't have to worry about getting like a you know an approximate 1cs solution or something like that and the reason for this is um if we get a relaxed opening for a certain pedestal commitment then you can see this as like um i don't know like a strange fractional opening of the of the pedestal commitment the issues are that um you know a

fractional opening is not necessarily the same as a real one um you know this this factor that we want to divide by to get the fractional opening might not even be invertible in the ring it might not be like a small message so it might not be a valid opening for that reason um so the way we fix this issue is by working with r1cs over like different quotient rings in which in which this fraction actually makes sense and by interpreting interpreting all the commitments and their openings over this quotient ring we can we can deal with the fact that we can't we can only have like relaxed openings to better some commitments um and you know we wind up with like exact witnesses for

our once yes statements over these um special quotient rings okay so you know here's a quick list of um what we can actually do with all of these bilinear modules we can handle the discrete log setting settings based on pairing assumptions groups of an order like rsa and the the ring sys setting uses lattice assumptions okay so this brings me to the the very end of the talk um let me summarize our results our first result was to show that um actually to get succinct arguments of

knowledge for some check friendly commitments you can run a subject protocol our second result was that in this very general bilinear module setting you can get succinct arguments of knowledge for r1cs over quotient rings with logarithmic proof size and as a corollary um we've got a succinct argument for rncs based on lattice assumptions which is plausibly post quantum secure so the takeaway series though we've got many some check friendly commitment schemes out there in the literature and split and fall techniques for these can be used it can be viewed as some chick protocols um and lots of the different cryptographic settings that

we're used to um are actually like special cases of this like bilinear module formalism so that's the end of the talk um yeah thanks very much for listening and um if we've got time i'd be happy to answer like any more questions that people have so for the lattice um instantiations how does the concrete efficiency of your protocol compare with um la21 and ick21 let's see so um so i would say that um okay so i'll compare to ack 21 first so ack 21 uses the the same kind of lattice

instantiation with like um you know similar a similar choice of a ring so like you could say it has like the the same choice of bilinear module um actually we ought to get comparable efficiency to the results in that paper um i'd say the difference the difference between you know the statements in our papers is really you know we have we have kind of um less efficient looking statements but the reason for that is because we were doing like a very general analysis which tried to capture like these um right four different settings at the same time and then um we because of that we weren't necessarily able to make use of like um um you know special facts about challenge spaces and different things in the latter setting which give you

uh better bands um so with a tight analysis we ought to get the same kind of efficiency as a ack 21 um la21 is a bit different because they actually have a um like a different instantiation of bilinear modules um with like different rings um and different lattices that they can use and those have some like really advantageous properties so um we were talking about like relaxed commitment openings where you can only open um a multiple of um of the commitment that you started with um but in the setting that's used in la21 they can actually get like more exact openings which don't have this multiple

and that's the kind of thing that would really improve practical parameters once you did the analysis okay so i suppose one question to us given that you were on the original split and fold paper how much was that of this written this vision fold techniques actually inspired by the sunchat protocol um i don't think i don't think it was at all actually i mean um at least at least it you know it wasn't

it wasn't in our mind at all when we were when we were thinking about the political and so um there's this other paper called something like uh linear algebra with sublinear zero knowledge arguments by yensgrove and um i think mostly when we were when we were thinking about this original splits and fall paper um we were looking at um techniques from that paper now um you know those techniques you know perhaps they were in some way inspired by the by the sunshine protocol but um um i would have to ask uh have to ask kenz about that um because uh you know he wrote that paper all by himself but um i think um for the 2016 one we were just thinking about this this

2009 paper right i mean so looking at the the people that started applying split and fold to multi-linear polynomials the connection became a lot clearer uh uh you know a lot more obvious um sorry could you could you repeat that so basically sort of uh when you be when i read papers like dory uh it then then became very clear that they were doing something somewhere in between some trek and and uh splitting the world yeah yeah right um yeah i think um i think another thing

that that possibly makes it more difficult to to see the connection is that um the split and fall techniques are all written you know they're often written in this like recursive way using um uh round reduction so you just see two rounds of the polynomial at a time um um whereas like i think it's i think it's a lot easier to see the connection if you um if you you know if you write down like um the the full split and fold protocol as a loop then yeah i think it becomes much more obvious um jonathan asking a question for alan

in the chat here which i think you may have touched on earlier in response to a question from dara um is fry a special case it's from alan let's see um maybe for anyone watching this at frye is ffri like not not the word fry like turkey frying um okay so um yeah i think i think that's a great question um that's that's not actually something we've um we've investigated so far but um you know i think i think it's quite it's quite plausible that um you know fry does have some some connections to the the subject protocol um possibly might be might be a little bit

different from some of the other some check arguments here because um um you know fry's fries really presented as um as an iop and then um the cryptographic commitment scheme there is um is based on like merkle trees and hash functions and doesn't have like quite the same homomorphic properties so um i think i think there's probably a connection to you know the original subject protocols like you know almost almost certainly but um like whether it's directly connected to some check arguments i'm unless sure because of the the cryptographic commitment scheme that's used great thank you um

and thank you very much for your time today i know i i want to be respectful of it i don't know where we're about out of time for our session does anyone have any closing questions before we conclude i i would say that like um if if anybody if anybody does have any more questions but they're worried about time or they need to go then um you know you feel feel free to you know send me any questions by by email so my email address is um jbt at zurich.ibm.com um what what's the next step what's the next generalization um good question um

it's a very open question yeah um let's see i think i think for now i'd just like to i'd just like to try and capture like the remaining few split and fall techniques that um that we didn't fit into the framework in our paper so um so you know like like dory for example um and we do have something that works over rsa groups which is similar to um similar to the polynomial commitment scheme in the in the dark paper but not exactly the same as it so um i think for now i'd just like to just like to improve things slightly and just capture those last few splits and fall protocols thank you

awesome uh well thank you very much jonathan for presenting and uh you know thank you katarina if you're still in here for for your work on this paper and i'm gonna go ahead and stop recording thank you to everyone in the audience uh who attended and uh we'll look forward to seeing you all next time