ZK HACK - zkSNARKs from Polynomial Commitments - Pratyush Mishra

Transcript

so let's invite pratush to the stage who's going to be as mentioned talking about snarks for polynomial commitments going into uncharted territory it sounds like i'm very excited to hear this cool awesome uh hi everyone and thanks anna excited to be here so yeah so as uh nick said we'll be uh looking at constructing snacks from polynomial commitments which is sort of a very recent paradigm for constructing uh snacks compared especially to like the hash-based snacks which go back to the 90s all right okay so let's before we dive into our construction let's quickly recall iops um from alice talk right so in this model you have approver and a

verifier the approver has the public input and the witness and the verifier has just the public input and the proven verifier exchange some messages the provers messages are some arbitrary bit strings right they're just some oracles and the verifies messages are just some randomness right so basically the proven verifier interact over some sequence of t rounds and at the end um the verifier can generate a query set to query the so it'll ask for the value of the oracle at a particular location and it'll take the result of um these queries and plug it into a decision procedure and then decide whether or not to accept right so this is a you know it looks like a fine model

something to consider um but you know why i have iops been useful um and lots of that we can let's take a look inside common iops right so what what is the underlying uh technique uh behind common iops okay and the answer uh spoiler alert is polynomials everything in crypto is polynomial so it's no surprise that we have polynomials here as well so in particular um inside iop uh most common iops such as stocks or aurora or you know basically anything that you could really want to implement um the prover messages are supposed to be polynomial encodings right and the verified queries are evaluation points so the verifier is

asking what is the evaluation of say p1 at a point z1 something like that right and it's okay so the messages are supposed to be polynomials and then to actually enforce that they are polynomials uh most iops also include what's called a low degree test which yeah as i said ensures that the messages are actual polynomials of a specified degree okay so this is really nice um but you know it's not quite satisfactory because what happens is that when we do these low degree tests even the best ones that we have today for example um the frylo degree test uh they're quite expensive and they'll require a logarithmic number of rounds in the degree of the polynomials um and they result in a lot of queries

because the verifier also has to query um has to query these polynomials that many add many locations okay all right um so this is a problem right what can we do about it what if we just get rid of the low degree test entirely right what if we just assume that messages are polynomials instead of you know having to test for that so this leads to this recent model called uh polynomial iop which has introduced within the last couple of years um and in here you have as inside of the standard iop model you have the previewer and the verifier and the proven verifier exchange some messages but now we sort of just assume that the prover messages are polynomials right and they can be whatever you know

for a particular kind of i have polymer and iop that can be you know multivariate problem polynomials univariated polynomials over different kinds of bases coefficient binomial whatever it doesn't matter they just are polynomials right and then the query set is still as before some set of evaluation parts evaluation points so the verifier it queries p1 at a point z1 pt at a point zt and so on right and then based on uh the you know the results of these evaluations it makes some decision so this is basically the same as the iop model except we don't have any ldt's right we just assume that the prover messages are polynomials

so i mean this is like a relatively strong assumption but we'll see how to you know why this is useful uh in just a bit okay um so let's see how you know like what this restriction does in terms of uh how it allows us to change the properties of these polymer iops compared to um standard iops so from a completeness perspective um what we or the guarantee that we want is that there's whenever sort of the proverb is honest and it actually knows the correct witness it it can get a strategy that always outputs only polynomials so the messages are are only polynomials right and the verifier will accept these polynomial messages in comparison in the iop the prover can output like an arbitrary bit string

right it doesn't have to be a polynomial and similarly in the soundness case what we want is that whenever the verifier accepts um we will only consider adversarial provers that output polynomials so we don't consider approvers which output arbitrary bit strings we only want soundness against proverbs which output polynomials right and against these sort of algebraic provers which output polynomials we're able to construct extractors which find the secret witness okay so you know there's been a lot of work so this is like a useful model and there's been a lot of work over the past uh you know three four years on constructing uh

pip constructions which have different kinds of uh you know prover efficiency verifier efficiency and you know support different kinds of computations um and they use a variety of very interesting underlying techniques such as univariate and multivariate subjects uh product checks permutation checks lookup tables and is a huge world of interesting techniques um that you know underlie efficient pip constructions all right and so they seem to provide like a strong foundation if you can construct a snack for them right because then your snack will maybe inherit some of these properties or interesting properties okay so how do you actually get a snack from a piop right

let's try to see how to do this uh by taking inspiration from the iop to start compiler that nick just covered right so let's see if we can look and look for lessons there to construct our piop does not compiler all right so in this iop to start compiler you have iop plus a vector commitment like a merkle tree um this is just a generalization of multiple trees right and then you can get a snark and the rough strategy uh i won't recap it in detail is you have the snark prover it'll run the iop prover and commit to the um oracles the you know vectors or bit strings that the iop approver

produces and then it'll generate the queries and prove that the sort of queried locations in the committed uh oracles uh is uh or the values are correct using some sort of opening proof so in the merkle tree case you will provide a sort of authentication path uh there's other vector commitments with different sort of opening proofs and then sort of the snark verifier it'll run the iop verifier and also it'll check that the opening proofs are correct that the merkle tree parts are correct for example okay so okay so for this to work what we need from our vector commitment is we need to be able to succinctly commit to the vector right and then we need to be able

to provide a short proof that the you know of the commitment opening the local opening right so in the merkle tree case their succinct commitment is the is the root and the sort of opening proof is a merkle tree path which is logarithmic in the size of the oracle right so okay so for for these i for iop to start compilers we you know understand it well let's try to see what happens when we move to the piop world right so now we have a polynomial iop and we want some kind of commitment scheme which gives us maybe like a similar structure for our final snark so we want to be able to commit to the polynomials that are output by the piop prover prove that they are correctly evaluated

at some challenge points so we want an evaluation proof and then the snark verifier needs to be able to check this evaluation proof right efficiently so similarly here we want we need to be now instead of committing to a vector we need to commit to a polynomial and then we want to open the commitment um at arbitrary evaluation points right okay so this gives us like a list of a couple of properties that we want from our uh sort of question mark question mark question mark commitment so let's see what how we can fill in this blank right and it seems that basically what we want is a polynomial commitment so what are these so polymer commitment

um has a few different algorithms first you do a setup which takes in some degree maximum support and degree of the polynomials that you want to support with your pc scheme and it outputs like a committing key and a verifying key then the sender and receiver these are two parties um they interact using three algorithms the sender is uses uh the commitment scheme the commit algorithm inside the pc scheme to commit to its polynomial right um gets his commitment sends this over to the receiver and the receiver then responds with a challenge point and asks hey sender can you you know prove to me uh can you tell me what the evaluation of the committed polynomial is at this challenge point z

and can you also prove that that's correct right so what the standard does is it evaluates the the polynomial at this point and then it produces an opening proof that the committed polynomial at the point z actually evaluates to the point to the value v right and this gives a sort of an evaluation proof which the sender sends to the receiver and the receiver can then check this evaluation proof against the point and the original commitment okay so basically all we're doing at a high level in a polynomial commitment is we commit to a polynomial and then later on we're able to provide a short evaluation proof that the committed polynomial evaluates to some claimed

value v at the challenge point z so that's the property that we want from a polynomial commitment and uh we want completeness and extractability these are just standard properties um so that whenever uh the sort of sender is acting honestly and it actually you know this evaluation claim is is true that the committed polynomial evaluates to v at the point z then the receiver accepts and we want extractability which basically just says that uh whenever the receiver accepts their the sender actually knows inside the the commitment central ascender actually contains a polynomial that is of the appropriate degree d okay and which sort of agrees with the

evaluation claim that the committed polynomial actually you know has this relation p of z equals v okay so this is like a mouthful but basically we just you know want to commit to a polynomial and then prove that its evaluation is correct later on okay so this is like the most basic definition of a polynomial commitment you can consider more i guess complex definitions where you commit to multiple polynomials at the same time and then you open them at a query set instead of a single point uh and this actually leads to big efficiency improvements sort of this batch commitment and batch opening property which we'll see when we get to our construction of a snark from these pc schemes okay

so i mean i've talked about this definition of a polygon commitment but can we actually you know realize these via efficient constructions and the answer is yes uh basically over the past 10 years there's been a number of constructions which achieve uh you know which based on different underlying assumptions such as pairings uh groups of unknown order discrete log whatever um and which have different kinds of prover and verifier efficiency and proof sizes as well as these homomorphism and batching properties right so this is just like a this table is a you know high level overview of maybe the state of the art or most popular pc schemes right um and they as you see they achieve different kinds of properties in terms

of setup you know commitment size proof size verify time and so on all right okay um and the interesting thing is by sort of you know these different pc schemes when we sort of plug them into our construction of snacks from these pc schemes this will sort of the snark will inherit the properties of this pc scheme so for example if your pc scheme has a private setup then your stock will have a private setup if it has a public setup it'll have a public one um yeah and so on okay so this is like a summary of pc schemes right um let's see how we can actually now combine these pc schemes with the pio ps that we saw earlier to get a snark

right so okay so as we saw so as a if you recall the snark has three algorithms you have a setup algorithm which outputs the proving and verification key and you have approver and a verifier so let's see how all of these algorithms work in our construction okay so in setup what we do is we'll take in sort of the maximum size of the computation that we want to support so let's say we want to you know prove a snark for a circuit of size 100 gates right so i'll plug in 100 into the setup and this will tell me sort of the max degree that is required by the that sort of the polynomial articles have so what's the maximum degree of the oracle's output by the approver

and then we'll do our setup to invoke this and we'll get out like some commitment key and verification key and we'll set these to be the prover and verifier keys for our snark okay i mean you don't know too much basically we just output commit true and verifier keys which support the maximum circuit size for example that we want to uh use with us proof with arsenal okay um so how does our so we're going to construct our approver and verify and what these will do is at a high level they will invoke inside them the piop prover and the piop verifier so this the snark approver will run the the piop approver it will obtain the

first polynomial oracle and then it will commit to this using the pc commit algorithm it will send this commitment to the snark verifier so okay yeah so i guess before you know we get too deep uh we'll first just uh discuss the sort of interactive protocol and then basically you can just apply fiat from here to make it non-attractive so it's similar to the situation in nick's talk okay so just for simplicity i'll just talk about the interactive case here first right so as you were saying um the prover commits to the first polynomial oracle output by the piop approver and then the snap verifier invokes the prp verify to get the randomness and

this continues for you know the key rounds in the piop and sort of the news we are done and then what the uh what the snark prover does is that it generates the query set that corresponds to the randomness sent by the verifier right and then it opens the committed polynomials at this query set using the pc open algorithm right and this results in some evaluation proof and some corresponding evaluations which are plugged into the uh the piop decision and the pc check algorithms um and if both of these accept then the

snark verifier as a whole accepts okay so we commit to the articles and then the prover also provides an opening proof at the query set and the verifier checks the evaluations as well as the opening proof right so the high level structure as we saw before is very similar to the killian setting right and then plus you can apply fiat for me to get non-interactivity and i won't really go into like the soundness and completeness errors of properties but basically in the interactive case um the soundness error is basically the soundness error of the of the uh piop and plus the soundness error of the pc scheme right and similarly for the prover and

verifier efficiencies and okay all right okay so this is a construction right i mean it looks like a useful construction but does it actually solve the problem that we set out to solve all the way in the beginning of my talk and their problem was uh of large proof sizes right so if you remember as well as from nick's talk that um these iop based marks they have large proof sizes so let's compare um the proof size of our construction this piop based construction with that of the iop based snare okay so we'll start off with an asymptotic asymptotic comparison right so first the proof consists of the commitments to the oracles right and this is the same in both usually um

you have t commitments for t oracles right and then you have uh sort of the values of the oracles at the query set right so you have these this also looks looks at the first at a first glance the same right and then the part that is mostly different is the sort of opening proofs right uh in this for example in the merkle tree based iop based snark right the opening proof consists of authentication parts so there are q queries and you have key authentication parts right so this is sort of where that size comes in and the piop base case you have uh opening proof which i won't expand it depends on the pc scheme right

okay so this is the sort of asymptotic expression but what does it look like for concrete snacks right so as we saw in next talk for fry based iops like aurora or stark um as well as you know recent iterations on those the argument size is 100 kilobytes right in comparison if you take a state-of-the-art univariate piop such as planck or marlin or recent improvements on those then what you'll find is that if you plug in for example the bullet proofs based pc scheme then you get a much smaller proof size of five kilobytes and if you're okay with using pairing assumptions then if you use the kcg pc scheme then you get down to just 600 bytes right that's less than a kilobyte

that's absolutely tiny so it's like an order of couple of orders of magnitude difference from the fry based uh iop snark right okay why is this why is this the case right because just from this table it doesn't seem that it's not apparent why that should be the case well there's two reasons first recall that in the iop case you have to do a low degree test right and this results in a lot of queries to the various articles right and this means that the query set for the iop case is much larger there's a lot more sort of queries in there compared to the pio pk so concretely for example in planck and

marlin there's only two evaluation points the query set consists of just two field elements right whereas it can be much higher in the iop base case so this means that sort of this contribution the oracle values that's already much larger okay then in the the second reason is that for many polynomial commitments the evaluation proof can be much smaller than sort of the even the number of commitments and the query set size right so for example in the kzg case um the evaluation proof if you even if you're sort of you know proving the evaluation of a say 100 committed polynomials

the final evaluation proof uh if you're evaluating at the same point all these polynomials you only require one group element right whereas sort of in the iop based case you would need to have a hundred different authentication parts right for each query and there's also this amplification arising from the sort of the query set size right so both of these factors put together one and two results in this massive difference in the proof size right so it seems that you know after all this work our final construction actually has achieved what we set out to do which is get a snark with a smaller proof size right um yeah so basically that sort of wraps up this construction right so we've seen

how to construct snacks from polynomial iops and pc schemes uh and these are efficient and have much smaller argument size and iop based marks which is a positive on the downside they usually rely on some more structured cryptography such as pairings industry logs and groups of unknown order and as nick pointed out these tend to not um be quantum resistant right we know they're not quantum resistant for many of these pc schemes so if you want to use these you know 100 years down the line maybe you know think about what kind of assumptions you're okay with all right so this sort of concludes the first part of the talk right we saw about the how to get a smaller argument size

but what we haven't seen so far is how to achieve subliminal verification for iop and piop based snarks right by subliminal verification i mean that the verifier runs in time that is smaller than the size of the computation so if you have a circuit the verifier should not run you know linearly in the circuit size but maybe something a square root or logarithmic something like that right and allah alluded alluded to this in his talk but we'll quickly go over um you know why what's the you know why this is a separate topic on its own okay so let's take a look at the complex the verifier complexity in these prp based marks so in the rest of this talk i'll sort of abstract um

you know both piops and iops into just some iop okay because the material is common to both all right um right so this is the sort of expression the for the running time of the verifier right the time for the snark verify is roughly equal to the time for the check algorithm for checking the mercury path or checking the evaluation proof you know whatever plus the time for the iop verifier right we know how to make this portion small right in the merkle tree verifying the path is logarithmic in kcg you just require to do one pairing for example um so we know how to make this succinct what about this right what about the iop

verification cost so let's take a look at what happens in you know your iop you have some articles and the verifier makes some queries so nothing changed but what actually happens is that this public input x can actually be divided into two parts one is a description of the computation f so for example the circuit um the description of the circuit right or the description of your algorithm right and oh there you go and the actual input x right so the actual public input to the public input to the circuit for example right um

so the problem so what this means is that the iop verifier has to at least read you know even if it doesn't do anything else with f that's it it at least has to read f right um and you know when the size of f is much less than the size of the computation example in machine computations then this is this is fine because this time can be sublinear right so if you for example think of doing the same hash function 100 times right the description of the computation is just the description of the hash function but the size of the computation is you know 100 times the hash function computation so you know this condition holds right and then in that case you know we know how to achieve some sort of sublinear

verification the verify will run in time only in the sort of description of the hash function not in the you know hundred times the hash function okay but you know if you have an arbitrary circuit which consists of you know many different components all you know matched together then the size of the function description is actually equal to the size of the computation in this case the circuit size right and so far in this model uh the verify will run linear in the you know in the size of f or in the size of the circuit which kind of sucks right because a lot of applications of stocks you know rely on having some sort of sub-linear verification

okay so to resolve this um recently a new model was proposed which extends iops and piops with what's called holography so i won't you know explain the why it's called holography but basically the idea is that we introduce a new algorithm that first preprocesses the circuit right and then the so we call this okay so you have your sort of standard prover and verifier so this is unchanged but there's also a new algorithm called an indexer or a preprocessor which takes in the circuit c and outputs a set of oracles which is different from the prover oracles right that somehow encode the circuit right

and then and the verify as before it can access it can query the approver oracles but it can also query the index or articles right this article which corresponds to the circuit and notice that now it is not reading the circuit it's not taking the circuit as input at all right and so this means that it can be sublinear if it's only making let's say you know a logarithmic number of queries total in the circuit size then the verifier can potentially be sublinear right so just in this model what we've done is probably we've sort of removed c from the input to the verifier and instead we've sort

of pre-processed it and given the verifier oracle access to an encoding of c right okay so that's the sort of this uh generalization of piops let's see how we can go from these um i guess not pc schemes but uh yeah from some commitment scheme to a pre-processing snark right so if you recall in pre-processing stock we want to sort of pre-process the um the circuit in some way right and that's exactly what pips enable these holographic pips enable okay so we have our setup algorithm right um and it's similar to before except now um we uh yeah output public parameters um

for you know any supported size n right and just as a note i guess oc here denotes oracle commitment right so it can be a vector commitment it can be a polynomial commitment it can be some other kind of commitment if you have a different kind of iop i'm just abstracting that away for the moment okay then the new algorithm the indexer what happens here is that you run the iop indexer okay and you get out some oracles which correspond to the circuit and then you commit to these using your oracle commitment right and now you have a commitment to some encoding of the circuit and you plug this into the verifier key so the verifier key consists of you know the public parameters uh whatever's in the universal parameters

as well as this commitment to the uh circuit or the encoding of the circuit and then the prover and verifier look almost the same except that this query set can contain queries to the circuit oracles right the index or oracles and so the approver has to answer queries to those oracles too inside oc dot open right so it produces an evaluation proof for those um for queries to the circuit oracles as well and then you can apply for extramura in a standard way to get non-interactivity okay so yeah basically it's the high level idea is that instead of having to verify take the circuit as input we sort of encode it and commit to

it in a succinct way and then prove that accesses to the committed encoding are correct okay let's see how this leaves an improvement in the verifier complexity so what we've done now is you know we already knew how to make this portion succinct the oracle commitment check right that part is already succinct and what we've done is we've now made the iop verifier also succinct by leveraging holography so as a whole this means that now the snark verifier can also be sub-linear right and yeah so now we have this new technique of photography which enables sub-linear verification for arbitrary circuit computations okay awesome so that sort of wraps up my

presentation so in this talk we looked at piops and pc scheme there's lots of exciting future directions we want to reduce the prover memory that's you know currently unfortunately a big bottleneck in deploying these by reducing the polynomial degree we can get better um prover time and holography is also super not super cheap yet um uh and the pc scheme front you know we want to maybe construct construction achieve constructions that are efficient but from new assumptions such as lattices um we're going to improve uh the constructions that we do know from existing assumptions uh like discrete law maybe you know let's try to achieve succinct verification um

as well as you know uh new applications so for example recently there's been uh constructions of efficient recursive snacks that rely on this new notion of accumulation for both pc schemes as well as iops and polynomial iops right so maybe there's more applications that um can pop up right so yeah awesome uh yeah thanks everyone for listening that wraps up my talk very cool thank you so much for touch i'm wondering i mean there's been incredible conversation happening in the comments about 46 comments yeah there's been a lot but i don't know if it'll be easy to find a question okay

here's a question i don't know if this is if this needs some uh context just disappeared hold on a second yeah i know susanna's looking for some good ones in the chats all right there we go yeah so yeah basically that's the idea so instead of instead of testing that the oracle is low degree as a polynomial via low degree test we just require the polynomial commitment to enforce that um so for example in the kcd case your commitment uh you know you basically you're evaluating your polynomial at the srs in some sense right um and the extractability property of your polynomial commitment scheme means

that no matter what the prover sends if it makes a verifier accept then there is sort of some polynomial that is underlying the provers commitment um so you can always sort of you know no matter what the approver is actually doing like you can always take its messages and get a polynomial out whereas in the sort of standard iop case you would have to do a low degree test to enforce that very cool um yes okay so you can chunk and split polynomials so this is a good question um this does increase the proof size because you know if you are you want to support really large degree polynomials then you would have to commensurately commit to each chunk right

um and also it doesn't really maybe apply as much to things like the two transparent pc schemes it's mostly a restriction for um like kcg based schemes where you have a trusted setup which only supports polynomials up to a specific degree but yeah you can do this chunking it just results in an increase of proof size that corresponds to the number of chunks yeah the theoretical difference is just that in iops the messages can be some arbitrary strings in piops the messages have to be polynomials they can't be anything else um yeah we just assume that okay well

i think we are actually at time so thank you so much for touch for answering those questions um and yeah i guess if there's more questions you know where the comments section is so um maybe we'll hear a bit more from you over there too