SNARK Design Part III with Justin Thaler | a16z crypto research talks

Transcript

so I'm going to kind of in this talk give a more technical in-depth uh overview of how snarks actually work kind of under the hood um but I do want to talk to be self-contained so uh I'm gonna spend the first maybe five or ten minutes just kind of recapping um kind of my the first two talks I gave at a16z um which were much higher level um they were also like a month ago so I don't expect anyone to actually remember on them so yeah 10 minutes sort of recapping and then kind of diving into um the details uh to give a sense of how this technology actually works okay so um yeah a reminder of what a snark is

so in a snark I'm an untrusted prover claims to know a witness satisfying some property so like a simple and prototypical um setting here would be that um the prover claims to know a pre-image um w for a designated output of a cryptographic hash function H okay so like both The Proven verifier know the hash function H and the designated output y but only the prover knows the pre-image w and the prover wants to prove that indeed it knows w Okay and like the trivial way to prove this is the prover could just send the witness W to the verifier

who could evaluate h on W and check that it equals y so a snark is basically anything that um any protocol that has better cost for the verifier than that trivial proof um so in particular the word succinct means that the proof should be shorter than the witness so succinct proofs are ones where the the proof is is shorter than that of the completely trivial proof system and ideally the verifier will also be faster you know checking the proof will be faster than explicitly checking the witness um and in that case the snark is called work saving it's actually technically you could be a snark have short proofs but not be worth saving

um but work saving snarks kind of everything is good for the verifier okay any questions about that cool okay um so in general you know snarks um tend to work as follows um you imagine that a software developer has written a computer program that takes as input the witness the prover claims to know and the program checks that the witness satisfies um the property um that the prover is claiming it does and then the uh program is fed through uh what's called a front end that spits out um something like a circuit satisfiability instance that is somehow equivalent to the

computer program so like the the circuit is satisfiable um or I should say the prover news is satisfying assignment to the circuit if and only if the prover knew a um a valid witness for the claim that it's making um that is a witness that the computer program would have you know uh checked and accepted as valid um and then the proven verifier apply a snark to the Circuit um you know so the you apply a snark for like circuit satisfiability the prover proves it knows a satisfying assignment to the circuit okay so and that snark is called the back end and back ends are really what this talk is about okay so what are our goals for the back end

um so we basically want the prover to be as fast as possible the verifier to be as fast as possible and the proofs to be assured as possible um and ideally right the prover won't do much more work than just running the program on the witness which it kind of has to do even to make sure that the witness is valid like convince itself that the witness is valid so you can't really hope to do better than that right we want the the verifier to not have to do much more work than just read read any public input to the problem um and really not not much more than that so um in the in the best snark for the verifier the verify does just a few milliseconds of additional work um and the the snarks with the shortest

proofs um those proofs will just be a few hundred bytes or maybe a few kilobytes or something so those are that's sort of um the ideal for all all three of the costs that we really care about um and I'll be very clear today like um we don't actually know snarks that achieve all of all three things simultaneously so I'll be very clear sort of you know um how close we can get to the ideal um for for each of these three costs um okay other things that are really important um in certain settings um some snarks are are what's called transparent so um that means they do not require uh what's known as a trusted setup ceremony

um which tends to be very complicated um these ceremonies oh that wind up producing what's called a a structured reference string um so this is like a long string that anyone who wants to act as the prover needs to know to generate proofs um and if everyone involved in generating that string sort of got together and um colluded um they'd actually be able to um kind of cheat the protocol uh and generate convincing proofs of false statements um so if you don't if you either like don't want to run a complicated setup ceremony you don't want to have to distribute a very large string to anyone who wants to act as a prover you know

don't like um that you have to trust that um not everyone got together included um then you really want your snark to be transparent and another thing another property that would be nice is for the snark to be secure even against improvers with access to a scalable quantum computer because maybe in in 30 years the cheat improvers will actually have access to some computers um and if your snark is in post Quantum secure they could generate convincing proofs of false statements um even if the snark is transparent and you know everything else um okay so these are sort of all of the properties we care about in our snarks

so fast prover fast verifier short proofs ideally transparent ideally post quantum okay um any questions at this point okay so basically uh and I just have a couple minutes left of the recap um essentially all Snorks are designed via the following three-step Paradigm um so first you design something called a polynomial IOP um I'll say in a moment what that means or I'll remind you if you were at one of the first two talks um then you design a cryptographic object called a polynomial commitment scheme um and if you take basically any polynomial IOP and any polynomial commitment scheme you can put them

together to get a succinct interactive argument and then to render the argument not interactive you can apply the fiatrimir transformation okay um so up to some minor caveats this is essentially this is how all snarks are are designed um and you can you can watch at some point um my first talk for discussion of of the minor caveats okay so uh just a reminder um again if you did see the first couple talks what is the polynomial IOP and what is the polynomial commitment and and then we'll we'll dive into the details um so a polynomial IOP um allows the prover to sort of we think

of the proofer as sending um a large polynomial to the verifier okay um however the polynomial is so big um if you were going to write down all of its coefficients um it would be very very expensive for the verifier so um you know if if the prover literally just sent included in the proof like a list of all the coefficients of the polynomial the the snark or the proof will not be succinct and the verifier would not be work saving because the polynomial is so big I mean it's basically as big as the the computation um that the prover is claiming to have run on the witness so we really like in in practice like don't

want the prover to have to send that whole polynomial to the verifier so what we're going to do is we're only going to give the verifier a limited kind of access to the polynomial okay so that is we're only going to permit the verifier to evaluate the polynomial at like a one or two or three points okay so um yeah in the polynomial iops I'm going to tell you about today actually there's only one polynomial sent to the verifier and the very first message it's some big polynomial um after that polynomial sentence the prover and verify are engaged in sort of a standard what's called an interact proof you know where all of the messages from the prover to the verifier are short and there are not that many messages say at most logarithmically many logarithmic and the size of the

computation the proverb is making you know claiming to have run on the witness um and like at the end of the protocol um the verifier is only going to have to evaluate that polynomial that was sent in the first message by the prover at say one or maybe three points in practice it's one but you know you need to do a little extra work to go from three to one um so you know in my slides today I'm going to say three but we know how to make it one um does that make sense this overview okay and then a polynomial commitment scheme is sort of exactly the cryptographic object one would need um to kind of implement

um a polynomial IOP in the real world um to effectively um let the prover like send this giant polynomial to the verifier without explicitly writing down all of its coefficients okay so in a polynomial commitment scheme the prover only sends a very small cryptographic commitment to the polynomial and then later the verifier can say hey I need to evaluate that polynomial at one point tell me its evaluation at that point and the polynomial commitment scheme lets the prover do that and moreover like actually prove that the returned evaluation is consistent with uh the polynomial that was committed to okay so this is like this is just

exactly what you want to implement a polynomial IOP like in the real world um when we can't afford for the prover to actually send all of the coefficients of the polynomial to the verifier what you actually want is for the prover to sort of cryptographically commit to that polynomial in a very succinct way and then just provide the limited kind of access to the polynomial um that the polynomial IOP permits the verifier um so yeah this notion of polynomial commitment scheme grants exactly that and it's typically developed you like you need cryptography to do this so typically it's developed using either what's called Merkel hashing or what's called Peterson commitments which use

cryptographic groups in which the discrete log problem is assumed to be intractable um and today I'll give an example of a polynomial commitment scheme which is in the former category so it'll use just Merkel hashing um it will not use cryptographic groups and as a result it'll actually um be plausibly post Quantum secure obviously if um quantum computers can solve a discrete log problem efficiently so if you use Peterson commitments um you would not get a post Quantum snark okay any questions cool um so I'm just going to run through a really brief taxonomy of known snarks and then we we really are going to get into the details so basically you can

any questions okay so you can you can take any polynomial commitment scheme and more or less take any uh polynomial IOP and put them together and get a snark up to some some minor caveats that I'm worth discussing right now um and so you can kind of understand the entire literature and snarks by just you know saying here are all the polynomial iops known here are the polynomial commitments known and let's look at the crop you know the cross product of all of them um and something to mention is uh the the properties of transparency and post Quantum security they are inherited completely from the polynomial commitment so like any polynomial IOP

combined with any transparent and or post Quantum snark uh any polynomial IOP you combined with any transparent or plausibly post Quantum um polynomial commitment will the combination will itself be transparent and or plausibly post Quantum um and that's not a formal statement about provable post Quantum security or anything um but in terms of just what's plausible uh we don't know Quantum attacks um and you know as long as the polynomial commitment scheme is uh plausibly post Quantum secure so just just to understand that statements you're saying all of the known polynomial iops don't do anything that looks sketchy from the perspective of being broken by quantum computers is that kind of the statement or yeah

that's that's exactly right um does an empirical statement about the ones that people use right yeah I guess you could say that I mean I I might go so far as to conjecture that um you know like uh yeah if we had the right analysis techniques um it would it would just be a true statement that like you take any at least sort of natural polynomial IOP and any like actually post quantum polynomial commitment and their combination would be like provably post Quantum secure um but I don't think you could hope to prove any of that um today um other than I suppose you know on either in the random or

Quantum random Oracle model you could hope to prove something um or maybe you could you could maybe prove something based on like learning with errors but the cost would be vastly um concrete costs would be much higher than the actual snarks people are using today if um yeah so people are just like uh you know they they want concretely efficient snarks um that's the main thing so if they do care about post Quantum security um they are very happy I think right today to have something performative for which like there are no obvious Quantum attacks um so that's sort of the reality of of today as as people are deploying these things um rapidly um

but yeah I I the the polynomial iops don't don't do very much that would um give anyone pause that you're going to have a break in post Quantum um security coming from um what's happening in the polynomial IRP yeah okay all right can I have a quick follow up on that I think I asked you this um during the previous one of the previous talks but um one like as long as there are no quantum computers now that there's nothing you have to worry about you can use this and then as soon as quantum computers are developed then you would have to switch to a different Stark and it's not like you would lose security over stuff that happened in the previous 30 years

um yes that's exactly right um so this is actually a much much nicer situation than um than with Quantum cryptography today uh where people are encrypting messages that they really don't want decrypted in the next you know 50 100 you know years or more um this is really with these knocks um that people are using today um as long as the prover doesn't have a quantum computer when the proof is generated you're you're fine um and moreover to the extent that I mean by the time there are quantum computers hopefully like you know Roll-Ups and things like that won't be centralized but

um you know one of the reasons like nist is developing um standards for post Quantum security now is because it takes like 20 years to get everyone in the world to actually deploy um new crypto systems um but if you have like one roll-up service or something uh again hopefully it's actually decentralized but imagine it's centralized um I guess they were just one person would have to hit one button and update the proof system um and so it wouldn't take like 20 or 30 years to deploy um the you know a post Quantum version um again hopefully maybe the you know I forget what they call the keys to these smart contracts to actually you know change the smart contract um to change what the snark is but um

you know hopefully the world looks very different um in in 20 30 years but yeah I I think it's um these are important things to keep in mind as as one determines um you know do we really need to be deploying post Quantum snarks today or can we kind of wait until um it's more it's a more pressing issue and the situation um first for snark applications today is is very different than the situations that like nist is thinking about as they're developing um new post Quantum cryptography standards got it thanks and I think I mentioned um when you asked the question before the zero knowledge property that a lot of these snarks have

um that is unconditional so the only thing that quantum computers might break um is is soundness of the snark meaning the ability to find convincing proofs of false statements um and that is why uh you really don't have to worry about somebody with a quantum computer 30 years from now because privacy is going to be guaranteed anyway the only thing that the quantum computer could do is find a convention proof of a false statement and if the proof was generated 30 years ago with no quantum computer then who cares okay great questions okay so in terms of what are the known polynomial iops and known polynomial

commitments so I personally um classify polynomial iops into three categories um the details actually are and aren't so important um I guess what what is important is um that there tends to be attention um both in the polynomial iops and in the polynomial commitments between proving costs and verifying costs so I've sort of listed the three categories um on this slide in terms of um uh sort of the the first ones are our nicest for the prover and and worse for the verifier and working towards the opposite end of the spectrum um and and one thing I want to point out because this will come up later in the

talk is that um the first two categories on the slide um which are based on so-called interactive proofs and multi-prover interactive proofs um they do not require fast Fourier transforms um so this will be real I'll you know you'll see shortly why this is relevant um so if you take a interactive proof or multi-prover interactive proof-based polynomial IOP and you combine it with the polynomial commitment scheme that also does not require ffts the combination does not require ffts um so the resulting snark does not require ffts and I'll say more shortly why this is an important point um in terms of categories of polynomial

commitments I'd say there are roughly three of them um the first two um are not post Quantum um because they rely on um intractability and discrete logarithm problem and the third one is plausibly post Quantum and as I did in Prior you know in my first two talks in each category I sort of highlighted in green um the example with the shortest uh proofs you know evaluation proofs and those are sort of the best known because um in blockchain applications of snarks right like typically verification is happening like on the blockchain or something so people really want fast

verifier than short proofs um and hence the sort of verification verifier friendliest um polynomial commitments tend to be the best known so we have things like um kcg commitments which have very very short proofs and very fast education but are not transparent workplace quantum we have bulletproofs which is transparent um but not post Quantum and we have fry which is both transparent and plausibly post Quantum um so just as a change of pace sort of today I'm going to tell you about some proof systems and commitments on the opposite end of the Spectrum which are kind of nicest for the prover um but not as nice for the verifier

Justin yeah I'm curious what the current thinking is around the different security assumptions setting aside the like post Quantum or not distinction so like you're assuming properties of security properties of things based on pairings versus on discrete logarithm let's suppose they just forget about quantum computers like should I have a reason to prefer one or the other type of security assumption all right yeah I mean people seem very comfortable with pairing friendly groups um I yeah I have not myself interacted with someone who's like well like my problem with kzg is it uses pairings and like I think that might be broken or something um you know people have different feelings about trusted setups which is what kzg

requires um either as like a hassle or also as kind of you know an extra security assumption that you know everyone in the world is not colluding in the setup um as an example I believe ethereum is planning to use kcg commitments at the base layer to do data availability sampling soon and they're planning on running a trusted setup for um actually a um the ability to commit to polynomials that are way too small to use in snarks but are big enough um for an application to the data availability sampling and um I believe they're planning on doing you know over several

months like hundreds of thousands of of people contributing to the ceremony you know so it's like very unbelievable that every one of them would get together um and but the reason they're going through all this effort is like if you're using a trusted setup at the base layer of ethereum like you really don't want people to not trust that trusted setup um so I think that's the main issue I don't think it's that um potentially with with you know like Casey G or it's not that it uses pairings it's it's just that you know uh it has a trusted setup um they're certainly there's branding among certain projects around um you know uh post Quantum security being sort of what we want in the very

long term and so we should focus on that now um and I I guess fortunately thanks to Matt's question we have some discussion about um why obviously post Quantum security is nice but maybe we don't need it now um and uh yeah I think that's most of the rambling thoughts I have about that question thanks okay so now I'll get for the plant to the plan today uh finally and um yeah the recap is is over um so I'm going to give you one example of a polynomial IOP um which actually comes from this multi-prover interactive proof based category I mentioned before and one example of a polynomial commitment scheme which actually comes

from this like plausibly post Quantum like Merkel hashing based category I mentioned before and why am I giving you these two examples um so one is because I think they are illustrative of how these things work which is kind of the main point of the talk but um also this particular combination um gives a unique snark with properties that are actually novel amongst implemented snarks in particular uh it's the fastest proof in the literature um that's a both an asymptotic and concrete statement um the resulting snark is also what I call field agnostic it works over any large enough field and it's um it's Unique in in that property as well

um and the one downside of the snark I'm going to tell you about today as I sort of indicated before is the proofs are pretty big um so like blockchain projects would not be directly interested in the snog um there's some from it was just posted in the last couple days there's some nice work that mitigates um the the proof size quite a bit um unfortunately it does give up on um the field agnosticism um but I you know I was excited to see uh more progress so you know I think this is something um obviously I'm biased because it's it's uh the it's my work not not the brand new paper but the um the field agnostic one um I think it's worth knowing about

because while you wouldn't want to use it today in blockchain settings uh if it further uh improvements are made it could become a really nice knock to use because it's uh very nice for the proverb okay um so if there aren't any more questions now I will tell you how a polynomial IOP works cool okay so I'm going to describe the polynomial IOP in the context of um arithmetic circuit satisfiability um this is just kind of the cleanest setting to describe it in um there are versions known that work for sort of other intermediate representations that people like to use these days

um like for example rank one constraint satisfaction problems um okay so in arithmetic circuit satisfiability like the prover and verifiers sort of have agreed on a an arithmetic circuit which means the gates of the circuit um compute addition and multiplication over some funded field and the inputs to the Circuit or elements of that field um and you know the the goal um in arithmetic circuit satisfiability is to determine whether the prover knows an input that causes the circuit to produce a designated output okay so in this little example like really toy example circuit on the slide um the circuit just squares every input

and then sums up the results okay does that make sense so uh essentially all snarks um all polynomial iops uh use the notion of a transcript for a circuit so a transcript is just an assignment of a value to every gate in the circuit um and the transcript is said to be correct if sort of the values it assigns each gate are actually consistent with evaluating the circuit gate by gate on an actual input so for example on this

slide I I have you know an input being you know one zero two zero and I've gone gate by gate through the circuit and written down like the gates value right so like one squared is one so um like the the leftmost gate at the second level of the circuit um is assigned value one by the transcripts you know like 2 squared is four and so forth um and and you know um so that's what a transcript is it just assigns a value to each gate of the circuit and the transcript again it's correct if it like um actually assigns Gates values that respect the addition or multiplication operation that each gate performs and

the output of the circuit is whatever the prover claims the output should be does that make sense are there any questions about this notion I guess so so valid witness here is going to be something that outputs to a pre-specified number is that right that's right yeah I mean if um if if I wanted to make this a little simpler I could have declared the pre-specified output to always be one and then you could think of the circuit as literally like checking a witness for validity and now putting one if the answers yet you know valid and zero if it's invalid um but the snarks all work in in this level of generality where the prover just says oh I know

uh an input that causes the circuit to Output whatever value um and actually the snarks are a little easier to describe in that generality so that's what I've done here does that make sense yeah okay all right so now we get to sort of the main conceptual uh leap of snarks um in my view um which is we're no longer going to view these transcripts as assignments of values to Gates in the circuit okay instead we're going to view these transcripts as functions uh mapping the Boolean hypercube so zero

one to an appropriate Dimension uh to the field okay it's it's actually a very simple view but it's like it's weird it's like when you first see it you'd be like why would you view the transcript in this way so you know I'll try to demystify that shortly okay so uh what we're going to do is we're going to assign each gate in the circuit a binary label right so if there are S Gates in the circuit where s is a power two then we're assigning each gate in the circuit like a unique label that consists of log base two of s bits right because there's like just you can use any mapping from like you know numbers between 1 and S two bit vectors of dimensionality log

base 2 of s so I've drawn an example here yeah it's a it's a circuit with 16 gates here I'm referring to inputs also as Gates um and I I've drawn like an example of a correct transcript for the circuit you know that causes a circuit to Output the number four and then I've written down um what a what the transcript is when viewed um as a function mapping you know four-dimensional bit vectors to field elements right so I've just gone like gate by gate to the Circuit you know I've assigned like the the very first like the leftmost input I've assigned

that label zero zero zero and similarly I've assigned the output gate label 111 and so the the transcript now we're thinking of it as mapping zero zero zero to three because that's what the the value of the transcript assigns that that leftmost input gate and mapping one one one one one to four because that's the value the transcript assigns to the Apple gate does that make sense one question Justin does does the does the sort of labels that you assign to the gates have to reflect like the topology the wiring at all or is it totally arbitrary yeah so at some point in the snark the wiring of the circuit will work its way in like it has to

somehow uh to sort of you know make the prover's claims about this circuit and not some other circuit okay um and we'll see that the way the wiring Works its way in um everything will kind of work no matter what uh labels you assigned what Gates um but you really want the if things are nicer if the wiring has structure is is all I can say right now um so you could get a non-trivial this this comes up for like work saving for the verifier and stuff like if um if you if you just want a succinct non-work saving snark like literally it's not gonna matter

um what the why you know how ridiculous the wiring looks How how Wild you know you know gate zero zero zero is connected to gate one zero one one you know um but if the wiring is nice and regular in a certain technical way then you actually get a work saving snark and even if it's not there's other things you can do to get a work saving snark yeah one reason I asked the question is I'm trying to I'm trying I'm sort of trying to figure out why you described it as a function on the hypercube as opposed to just from some abstract set like by saying hypercube I sort of expect you to recruit its geometry like the fact that you have Hamming distance or something else about it right yeah great so um basically the snarks that

so so all there are some snarks uh they're important ones um that do not view um the domain of the function as the hypercube but rather as a one-dimensional domain like literally um you could think of it for Simplicity as just field elements between zero and circuit size minus one um you know so basically right rather than um assigning each gate a log aspect you know a log s bit label they're assigning each gate just like a label that's a finite field element from some subset of the finite field of size equal to the

size of the circuit um and I'll explain uh but for the the fastest Proverbs marks um they use the bit label thing and we'll see why shortly like basically um we're eventually going to turn these transcripts viewed as functions into low-degree polynomials okay and if the polynomial is univariate the degree of the resulting univariate polynomial will have to be like equal to the Circuit size um whereas if the domain of the transcript viewed as a function is bit Vector zero one to the log s um the degree of the polynomial will

actually just be um one in each variable and and the total degree will be a number of variables so basically you get something much lower degree um if you use uh bit vectors as labels you can get snarks with sort of I guess what is a more intuitive domain namely you know like field elements between zero and S minus one or something um but they have different efficiency properties and it's coming from the fact that the resulting polynomials are very high degree makes sense thanks um yeah so that's a little bit of a preview of like what's to come here um I I have slides on sort of exactly this point

um shortly okay so um yeah uh I guess what let me tell you now how the polynomial IOP works right so remember we're we've assigned each gate in the circuit a log s bit label and we're now viewing a transcript um of for the circuit as a function mapping gate labels to field elements and the approver's first message in the polynomial IOP is a polynomial which is claimed to extend the correct transcript and what that means is it's a um it's a polynomial so that if you evaluate the polynomial at any Boolean input it just spits out

the same thing that the transcript does at that input okay I I'll give you an example right now okay so this uh the transcript from the previous slide is um on the left here You Know It uh there were 16 gates in the circuit so we assigned each a four bit label and the transcript Maps each four-bit label to a field element and I've written a polynomial here um and you can check that you know if you evaluate this polynomial at input like zero zero zero zero it spits out three just like the transcript did at that input you know if you evaluate this polynomial add 1 1 1 it spits out four just like the transcript does at that input okay but note the polynomial is defy it

makes sense to evaluate this polynomial add non-bullying inputs two right so you can actually like feed into this polynomial like arbitrary vectors from the field and the polynomial will spit out of value right like so if you if you feed into this particular polynomial like four twos you know two is not zero one it's something else it's another field element it'll spit out negative 19. okay so this polynomial is like has a much bigger domain than the transcripted the transcript was only defined at bit vectors at date labels um so we have a polynomial that sort of behaves identically to the transcript at gate labels but it makes sense to evaluate the polynomial elsewhere

that's the last question please um something I just realized so the pop so the polynomial that you send is not just specific to the Circuit it's already specific to the Circuit evaluated at the witness that you're trying to make a proof about and so that's why like you just wanted to represent this specific transcript when evaluated at the specific witness that you're trying to prove something about that's right right that's right so later there will come in other polynomials into the protocol that capture the wiring of the circuit and so those polynomials don't depend on the specific witness but this one this key first message

in the protocol this one I'm sorry this one does um it's specific to the circuit on that witness at the prover knows foreign strategy for converting the transcript into the multivariate polynomial yeah I don't think I'm going to go into this in this talk but it's um you would actually want to use something called LaGrange interpolation um and in the context of um this Boolean domains there are one of the log s you'd specifically want to use what's called multilinear LaGrange interpolation um and you'd want to study like algorithms that are then able to evaluate these extension polynomials you know which are

you know you can Define via LaGrange interpolation uh quickly so that both approver and the verifier are very fast in the resulting protocols um so this is not I don't want to dive too deeply into this in my talk um I do have a survey book that um you know like at the very start is hitting LaGrange interpolation and fast algorithms to evaluate these you know extension polynomials at a point quickly because absolutely like the the prover in its head is going to have to kind of materialize this polynomial and you want that to happen quickly um yeah it turns out if you if you use LaGrange interpolation it's like sort of specifying um the extension polynomial age in a basis such that the polynomials

coefficients are literally just given by the entries of the transcript so you know on this um left hand side of the slide here this you know length 16 um column that just lists all of the transcript entries is literally like the coefficients of the extension polynomial in the appropriate it's called the LaGrange basis um so that that is the short answer is like the standard way of sort of writing down and manipulating um these extension polynomials uh is to use LaGrange interpolation and represent the polynomial in the LaGrange basis uh does that answer the question yeah thanks

right and this actually gets at one of the subtleties that I glossed over about why you actually can't quite combine every polynomial IOP with every polynomial commitment scheme like one of the reasons you kind of wouldn't be able to is um if you are dealing with univari polynomials the way uh like Marlin Planck row 16 starkware snarks do um their the polynomial commitment schemes for univari polynomials they actually like to use the standard monomial basis whereas like the prover in a snark would really like to use the LaGrange basis um and so to use it to commit to a

polynomial with the most known univari polynomial commitment schemes the prover in its in its own head would have to convert uh from the LaGrange basis to the standard monomial basis and that could actually become the bottleneck in the in the uh for the prover time in the snark so like you could combine them but um yeah uh you'd have to do so in a way that introduces extra overheads if that makes sense all right so back to how the polynomial ROP works so yeah the prover's very first message in the polynomial IOP is just this polynomial that is claimed to extend a correct transcript right now the verifier has to check

does this polynomial actually extend a correct transcript but how can it do that because it's only allowed to evaluate the polynomial at like one or two or three points but extending a correct transcript involves like all s evaluations of the polynomial over the Boolean hypercube right so like somehow we have to do some extra work in the protocol so the verifier can magically check all sort of f claims being made implicitly by the prover um about this polynomial just sent in the first message even though the verifier can only look at the polynomial at a single point okay so let me give you some intuition first about like why the polynomial IOP

works this way uh why the first message is this extension polynomial of a correct transcript and by the way like the the snarks that use univari polynomials like Marlin and Planck and so forth they also work this way it's just H is a univari polynomial then instead of a multivariate one okay so you should think of the polynomial H as a distance Amplified encoding of the transcript um so let me explain what that means um so I sort of already said that while the domain of the transcript is bit vectors the domain of the polynomial is much bigger it's um it's vectors with arbitrary entries from the field so just pictorially like here we have um a a transcript

um with four uh entries you know that is like it's a it's a transcript for a circuit of size four um and here is um like all evaluations of its extension polynomial like even when the field we're working over only has size five right but if the field were working over in practice it would have size like two to 128 right and then so while um the transcript has only four entries um the uh extension polynomial would be defined at like 2 to the 256 points right because you know for every pair of field elements um you can evaluate the extension polynomial okay and the key point is that if two transcripts disagree at even a

single evaluation so they assign different values to even just one gate of the circuit their extension polynomials will disagree almost everywhere okay over the larger domain on which the extension polynomials are defined so there's a basic result about low degree polynomials called the short Zippo Lemma which says that like you take two um polynomials that um have total degree at most log s um as these extension polynomials in this protocol do and if they're not the same polynomial then they have to disagree at all but a a log s over field size uh fraction of at points so think of your field size as I don't know 2 to 128 or something and

your circuit size even if it has a trillion Gates log s is 40. right so the the probability like the fraction of inputs at which the extension polynomials will um agree if the transcripts they're extending disagree at even one point is um at most like 40 over 2 to 128 right it's like ridiculously low probability um or fraction of points at which the extension polynomials agree um and what's happening what's going to happen is like the distance amplifying nature of this encoding will allow the verifier in the resulting polynomial IOP to detect even like a single inconsistency in the entire transcript right so again the the prover is sending one polynomial that's claimed to extend

a correct transcript and we're going to design things so that if the transcript at the polynomial actually extends is not correct right then like due to this distance amplification stuff like the verifier is going to somehow pick up with overwhelming probability that incorrectness um in the transcript even though it might only be like a single point of incorrectness so that's the intuition here it's just like you're dealing with distance amplifying codes that's that's why low degree polynomials are coming in any questions sorry this is basically isn't there a degree term in short simple yeah so it's

just um the degree of uh the in the context of the polynomial IOP I'm describing that degree is log circumcised sorry yeah yeah thanks for the question all right so just a reminder at this point in the protocol the the prover has sent one message it's a polynomial which is claimed to extend the correct transcript the verifier needs to check that indeed this polynomial extends a correct transcript but the verifier can only evaluate the uh the polynomial at like one or two or three points so what are we going to do um so it's a we have actually a two-step plan of attack so the first is like given the prover's first message this polynomial H okay

we're going to identify a related polynomial it's defined over slightly more variables okay such that age does indeed extend the correct transcript if and only if the related polynomial um evaluates to zero at all Boolean inputs okay um so that another way of saying that is um the polynomial the related polynomial G sub h um Vanishing over the Boolean hypercube is equivalent to the prover's original claim that H extends a correct transcript okay and moreover to evaluate the related polynomial at any input it's enough to for the verifier to evaluate H

itself at three inputs well you'll see where three comes from shortly and like this whole create I know this is a lot to parse um in one slide it's going to make a lot more sense um in in two or in two minutes yeah but basically just outside please are there any semantics to a b and c like I'm wondering why you didn't just write you know R for that yeah great so um yeah essentially uh when when a b and c live in the Boolean hypercube um you will interpret each of them as a gate label so they're like it's a triple of gate labels but because G sub H is a polynomial you can evaluate G sub H outside of gate label like outside of the Boolean hypercube

but yeah there is a great question the reason I'm not just writing R but rather a comma B comma C is because like conceptually we're thinking of um each of these as a log s bit gate label but like then in the in the final protocol they'll wind up taking values that aren't actually in zero one does that make sense yeah okay so yeah so we sort of uh step one of the attack is going to transform the Proverbs original Claim about age extending correct transcript to a equivalent Claim about this other polynomial G sub H um taking a specific set of values uh just zero

um albeit over more more inputs you know um so age extending Crypt transcript is a statement about H's Behavior at s inputs and this statement about G sub H is a statement about Its Behavior at s cubed inputs right because there are SQ bit vectors of length three log s question to three um however one you know the reason we've made progress sort of here is because um here uh G sub H is taking a single prescribed value just zero at every single one of those S cubed inputs whereas the original claim like the verifier doesn't you know like H could take all sorts of values at each of the um escapes and still be a correct transcript so we've kind of reduced

um the number of values required to specify the proofer's claim from s down to you know one or zero or something um but we've also sort of increased the number of inputs um to the polynomial um that we have to kind of check the resulting claim add um okay and then the second step is just to design an efficient interactive proof for um this claim that came out of the first step and what's really going to be key here is that the verifier and the resulting interactive proof only needs to evaluate G sub H at a single point um and remember uh we were made sure that evaluating G sub H at a single point

um it's enough for the verifier to evaluate H at three points and that's once we have these two steps and you put them together you're sort of done because it means like the verifier checking the prover's original Claim about each extending your correct transcript it becomes equivalent to running this interactive proof from step two uh which only requires the verifier to evaluate H at three inputs which is exactly the sort of thing we wanted okay so let me now tell you about step one okay um so this will be another sort of situation where initially it's a little bit much to parse but um actually let me tell you before I put this on the slide how to simplify the parsing let's imagine that the circuit only has

multiplication Gates okay that'll just simplify things a little bit so here I'm putting it on the side we have something to deal with the disengates I want you to just ignore that because it turns out you don't need it if if the circuit only has multiplication Gates so this second term this malt twiddle of ABC times blah blah that's all that's all you actually need um if they're only multiplication dates okay um so this is um a bit of a of a scat this isn't the um actual polynomial G sub H but it's pretty close to what what it actually is so what okay what this malt thing does is it is it takes as input uh you should think of it as thinking as input three

gate labels okay A B and C and it's going to spit out one if the two in the if gate a actually computes the product of gates B and C and it's going to spit out zero otherwise computers according to H I'm sorry computes according to H is that right computes according to the circuit oh okay okay okay so um yeah I had yeah to tie this back to some earlier questions so Tim had to ask like why am I calling the input use of h a comma B comma C and I said well we're going to wind up thinking of each of

them as a gate label so we are here and then Matt asked um something about you know like you know does H depend on the witness or just the circuit and the answer was yes H depends on both the witness and the circuit but you know there will be other polynomials that depend only on the circuit and those polynomials are exactly this multi-twiddle thing it depends only on the circuit so Mo if if the circuit only has multiplication Gates then what mod twiddle does is if you if you feed it Boolean input so you interpret them as gate labels it's behavior is as follows it spits out one if like the two in Neighbors of gate a are Gates B and C and it spits out zero otherwise so it's just kind of it's capturing the

wiring of the circuit okay and then we have um this extra term h of a minus h of P times HSC and the point there is like that expression spits out zero if and only if h of a is actually equal to the product of a should be in h to C that is the transcript that H extends assigns to gate a the value that is the product of the values it assigns to Gates B and C so instead I get the sense that this is a lot to to parse online so let me just take a step back and tell you the the net effect

okay um so this is a pop this polynomial right if you if you feed it three gate labels okay it will it will spit out um uh zero at at that triple of gate labels um if and only if one of two things hold okay so either um the first gate label is is like not connected to the other two gate labels or the first gate label is connected to the other two gates okay and the transcript H or the extension of the transcript H like

respects the operation of that gate okay right so like what this malt thing just like kills everything if a B and C are like are are not connected to each other right but if a B and C are connected to each other right like this small thing like spits up one so it kind of like doesn't change the value of the resulting polynomial and in that case this second expression h of a minus h of B times HC so it spits out zero if and only if right like gate a is really you know assigned the product of the two gate values that it really needs to be assigned the product of construction is agnostic to the choice of labeling we picked at the beginning

okay yeah so um at the end of the day um the verifier is either going to have to evaluate this malt polynomial on its own or it's going to like have to ask the prover for help doing it um if it like you know if it would take a lot of time and it doesn't want to spend that time okay so the only way the gate labeling and like the wiring comes in is through the small polynomial okay um and in the in the worst case if the wiring pattern or the circuit is totally wild and irregular evaluating this mod polynomial may take time linear in the size of the circuit it never takes more than that okay but for circuits that sort of do the same thing over and over and over

and over again which is actually like mainly what people are applying snarks to these days um these wiring polynomials will have will be evaluatable in like logarithmic time they'll be very quickly evaluated sorry can you expand on how the structure of the circuit plays into the complexity of this polynomial I hear intuitively what that means but like will you give any formalization of like what it means to be structured or yeah I wasn't going to in this talk but maybe I can um try to limit myself to 30 seconds and see if I can convey a little bit I guess let's imagine for a moment that the circuit is what I call data parallel

um because a lot of circus people care about today are so that means um and make it very concrete like imagine you know the the application is like the prover is claiming you know there's a hundred public Keys the prover claims to know a corresponding private key for each of the hundred public keys okay so you might apply a snark to a circuit that sort of takes you know uh does the following 100 times in parallel right so it it uh it takes as input like public input a public key private input a you know a private key and checks like does this private key actually correspond to this public key

okay so if you're just doing that 100 times in parallel like to Independent public key private key pairs I'm going to call that data parallel okay so you now have a circuit that it's like the same little sub-circuit just laid side by side 100 times Okay and like the different um copies of the little sub-circuit like don't don't interact at all okay so in that situation um these wiring polynomials like get the gate labels a b and c if you sort of um label the gates in the natural way like each gate label will actually have two parts they'll be like which copy of the 100 sub-circuits are you dealing with and then they'll be like within that copy like which gate of that of the

little sub-circuit you know that just takes one um public key private key pair are you dealing with Okay and like checking whether Gates a B and C are connected to each other in like the big data parallel thing is equivalent to checking like two things like are we are all three gates like referring to the same copy of the subcomputation and if so are um you know within the little sub-circuit you know our gates a b and c connected to each other right so you can kind of factor out malt twiddle as a product of two terms one that just checks like you know are the three copies the same are the three

copy variables equal and one that checks like within a copy are we dealing with three gates that are connected to each other and more Twitter will literally just be the product of those two independent things um and so like the complexity of evaluating my Twitter will depend only like logarithmically on the number of copies but in like the worst case like linearly on the size of the little sub-circuit that you're repeating many many many times um so hopefully that made some sense I think there's a lot there's a lot of confusion um I think in the community about this about which techniques have this property that for like sort of

structured repetitive circuits they can um sort of be work saving for the verifier without help from the prover B and the answer is a lot of snarks can be um like I think um there there's somehow a belief that um there's not that many snarks you know um that's not the case there's uh uh if these wiring polynomials are structured um that there are a lot of snarks that can that can do this sort of thing [Music] so so the stuff is just jumping ahead one question so so G sub H we should continue to think of this as defined over the whole field

right like r i take it might be from the is likely to be from the whole field not the hypercube right um um right so G sub H because it's a polynomial is defined over the whole field um but we we do care very much about Its Behavior specifically at the Boolean inputs and so this slide um sort of reasons about Its Behavior exactly at those inputs um so do we need to say I mean do we need some analog do we need to say have a distance amplification property of H like translates over to G sub H about Its Behavior off of the hypercube or um I would I would point it will be it

is important that um so H has degree one in each variable and because it has log s many variables it does total degree three log s and because it yeah sorry it has total degree logouts like um H is what's called multi-linear which means it has it's a multivariate polynomial with degree one in each variable and and total degree at most number of variables um G sub H is not multilinear um right because mock Twitter is multilinear and H is multilinear but they get multiplied together and that results in degree two in each variable okay so it's not multi-linear but it's still low degree its degree is almost

two in each variable and its total degree is at most two times the number of variables so it's very important that G sub H has this low degree property but it is no longer multilinear the way H is if that makes sense it's using the distance the amplification property you need will just follow what kind of immediate from that little degree necessary exactly yeah you'll lose like a factor of two and what comes out of the short simple bounds that's it so you can maybe think of G sub H as like an ultra distance Amplified encoding of H's Behavior over you know all Boolean inputs where you know G sub H is defined

over even more even a bigger domain than H is um so it's like extra extra distance Amplified or something like that and um yeah it's still uh its degree is also very low as long as H's degree is very low something like that okay um so thanks for all the questions I hope that made some sense so at this point in the in our attack um to try to get apply to my IOP um we sort of reduced the prover's original claim that this polynomial agent sent as its first message extends a correct transcript to the equivalent claim that the related polynomial G sub h vanishes over all you know SQ Boolean inputs so the question is now how can

how can verifier check this new claim while only evaluating G sub H at a single point okay so I'm going to tell you um one way to do this but it's not the way that my you know my personal favorite snarks work um it actually is the way that univariate polynomial based monarchs like Marlon Planck um even grow 16 wind up working um yeah so um and this will just give you a sense of of why this this claim about G sub H Vanishing over the Boolean hypercube is like efficiently checkable by a verifier that can only evaluate H at a small number of points okay so imagine for a moment that g sub H were not some three

log s variate polynomial but instead we're just a univariate polynomial okay and rather than needing to check that g sub H vanishes over the Boolean hypercube you know zero one to the three log s we just needed to check that it vanishes over some specific subset of the finite field okay so let me call that subset Capital H okay so here's a fact um which is really not hard it's quite intuitive G sub H Vanishing over the set Capital H is equivalent to G sub H being divisible by like the lowest degree polynomial that vanishes on Capital H so that is it

has as its roots exactly the elements of h capital h okay so you can see like if if G sub H is divisible by this um what's called The Vanishing polynomial of Capital H then clearly G sub H does indeed evaluate to zero for all points in Capital H right just because G sub H would then be a product of something that kills everything in Capital H and something else and it doesn't matter what this something else does on any point in Capital H if the if the other term in the product equals zero and the converse is also true which you can sort of see just by factoring out the roots of of G sub H because we don't it's not really that important um

okay so if you just accept this fact that vanish G sub H Vanishing over a specific set Capital H is equivalent to divisibility by the specific so-called Vanishing polynomial for Capital H then here is an efficient polynomial IOP for the previous claim so the proverb will just send the polynomial um that is the quotient when you divide G sub H by The Vanishing polynomial for Capital H right and here's the key point right like if the prover is honest then the verifier can actually like kind of spot check the the claimed equality um by just evaluating like both

polynomials on on both sides of the equality at a single random point and making sure that the two evaluations are the same okay why does this work why is the verifier able to spot check this claim right so the the approver is claiming it's got that that it it has two different ways of expressing the same polynomial you have G sub H itself and then you have some product of of this polynomial this quotient polynomial Q and The Vanishing polynomials use of Capital H if so here's what's going on if they are the same polynomial then obviously evaluating them at the same point is going to spit out the same result but if they're not the same polynomial well they both have the degree that's not too large

specifically at most like um three times the size of the circuit or something okay so if you take two different polynomials that are both reasonably low degree and you evaluate them at the same point then with overwhelming probability they'll spit out a different value like that's basically the short Zippo Lemma but here just for univarial polynomials [Music] together okay um and so the point then is like the verifier is able to check the prover's claim that g sub H is divisible by The Vanishing polynomial Z sub Capital H

simply by evaluating G sub H at one point and then evaluating the quotient polynomial at the same point and the vanishing polynomial at the same point okay now remember we Define G sub H so that you the verifier could evaluate that at one point by evaluating H at three points this was assuming that this like my Twitter polynomial was efficiently evaluatable by the verifier on her own anyway so the verifier can get the evaluation of G sub H at this one point R very quickly just by evaluating H itself this first message the prover sent in the polynomial IOP at three

points so that's the sort of thing we wanted right um this polynomial q that the prove percent as like it's its second message or whatever um the verifier only needs to evaluate that at one point and like in practice right like Q would be sent via polynomial commitment scheme and then you just would invoke the evaluation procedure of the polynomial commitment scheme and then you have this question of how the verifier can get the evaluation of the vanishing polynomial at the requested point and here's the rub people in practice like Marlon plant grows 16 they will choose Capital H like not to be field elements like zero up to Circuit size minus one but instead to be

um like all roots of unity of a given degree and that the reason they do that is just to ensure that um this these disease this Vanishing polynomial is is highly sparse it's it's like you know um it you know the disease is z sub Capital H the Spanish polynomial at R is just like R to the N minus one right that's like equivalent to if if Capital H is like all entered to Unity in the field that's what the vanishing polynomial is um R to the N minus one and that ensures that the verifier on its own can evaluate Z sub h um in logarithmic time at the request it at the desired point okay so I'm hiding a bunch of details

about how like Marlin and Planck work um for example I you know even if um H itself or univariate G sub H would be trivariate the way I've described this protocol so you know um I've sort of lied to you as I said imagine juice of H is univariate because that's what Mullen plant is so modern implant like they have to do some extra work to sort of reduce the trivariate thing or univeary thing but once they do reduce to a univarity thing which they ultimately do this is exactly how they work is the prover just um you know sends this quotient polynomial and thereby convinces the verifier that g sub H is divisible by The Vanishing polynomial

for the set Capital H that is literally all like nth roots of unity in the finite field okay any questions I know this is um way more technical than certainly the first two talks I gave but hopefully some of the key ideas are coming across so also for evaluating GA like G8 jokes you know like evaluate the like most Twitter and add total right correct correct yeah and and so that's a complicated issue which is actually why there's some confusion about this stuff and I think in the community um and the the high level message is if the circuit has repeated structure like it's data parallel or something right and then the verifier can perform those

evaluations quickly on her own and if the circuit is like some totally wild wiring no structure to it uh the verifier could do things on her own and time linear in the size of the circuit but that's not work saving for the verifier and there are some other things you can do to make it work saving involving somebody committing to those polynomials and pre-processing um and then in the online proof checking phase the verifier has to prover to sort of reveal the needed evaluation of those polynomials and prove that the returned evaluation is consistent with the commitment

and this actually came up in one of my talks uh you asked to uh sort of a question that this was basically the answer um I said well you know you you can wind up having the prover essentially like commit to the Circuit in pre-processing sort of and that's that's what that approach is is effectively doing did that make sense yep that's a good question um is my understanding correct that the soundness error uh increases as you grow the size of the circuit yes um it does but it sort of never gets above like circuit size cubed or something sort of no matter what you do so as long as your field has is a side you know big

enough say two to 128 to 256. it's going to be like okay like I mean if you really want 128 bits of security um your field size actually should be you know that you do have to pay attention to to this loss in in security and the soundness error um yeah uh I guess that that is yeah if you work over a field of size 2 to the 256 like no matter how big your circuit gets you you don't have to really worry right because like you know um you're saying like is it if the circuit is at most 20128 youth uh that you still have 128 bits of security yeah or you

know I guess the way I'm describing good maybe maybe you'd have a line well okay yeah exactly that yeah that's fine that's fine yeah I think with with the univarian polynomial based techniques you get a bigger loss in soundness okay that's linear rather than logarithmic in the size of the circuit so you got to be you have to be a little more careful then um but still it's not uh it's not a huge deal uh you but you're absolutely right like if you really won 128 bits of security and you also don't want to work over a field that's much bigger than 128 bits you you do have to pay attention to the soundness loss yeah okay all right so uh yeah this says um I'm gonna I'm gonna speed up a bit because

um I do want to say a little bit about polynomial commitments um so I'll tell you in a in just like one slide how um snarks that use multilinear polynomials actually work right so um yeah the the the previous slide only made sense for univari polynomials um also the resulting protocol is like more expensive for the prover in practice because the prover has to commit to extra polynomials right like the protocol had the prover send this quotient polynomial and that requires applying the polynomial commitment scheme to a new polynomial and that's expensive for the prover and like in Marlin and Planck actually this winds up

happening for many polynomials not just one extra one um so if you really care about minimizing prover time you really want to try to avoid that and so the solution is rather than sending this quotient polynomial thing you use something called the subject protocol which is an interactive proof for more than 30 years ago now and I'm not going to tell you in detail how it works but basically it lets you sum up all the valuations of a multivariate low-degree polynomial okay and essentially the verifiers costs just grow with the degree of the polynomial in each variable um so remember like this G sub H

um that I was describing to you has degree two in each variable okay and the number of variables it had was like three log circuit size so the verification costs if you apply the subject protocol to like this G sub H um would be certainly logarithmic in the circuit size concretely it's actually pretty close to um something like two or three log circuit size many field operations um and then the only thing the verifier has to do in addition to uh those like two or three or four log circuit-sized many field operations is evaluate the polynomial being summed at a single randomly chosen point so it has the same

kind of effect as this quotient polynomial based univariating thing from the previous slide uh where the verifier winds up only having to evaluate the polynomial being referred to at a single point um same kind of effect but without the prover actually sending some kind of very large quotient polynomial um that the previous slide required okay um so it's kind of like for a purpose of this talk just treated as a magical black box that sort of replaces this need to send quotient polynomials with um it just gets rid of it and the extra cost is that um the proof length and verifier cost grows with the number of variables of the polynomial and the

degree of the polynomial in each variable which in the context of like the reason I had um you know Boolean gate labels instead of you know gate labels being numbers between you know one and S or something was exactly to keep the degree of the polynomial in each variable as small as possible but then it means there's logarithmic in many variables so you basically you wind up paying a logarithmic verifier cost um but getting rid of the need of the prover to send these large quotient polynomials as as you uh require with the the univariate techniques okay so um with that out of the way like as as just like a final sentence um about how the polynomial IOP Works

um like the the verifier it needs to check that g sub H evaluates to zero at all Boolean inputs okay let's imagine for a moment um that we're not working over a finite field but rather over the integers the reason I want to do that is to avoid this sort of nasty sort of wraparounds issue wherever a finite field you can add up a bunch of like positive numbers and wind up with the result being zero um but over the integers that can't happen so just to explain the main idea like I want to work over the integer so I don't have to worry about that okay so in that case checking that g sub H vanishes at all Boolean inputs is equivalent to summing up its evaluations overall Boolean inputs and then squaring

the results um the reason you would want to square the results is to basically take negative numbers and turn them positive so that they don't cancel you know summing them up doesn't cancel anything out okay so then if you do this right um then if G sub H evaluates to zero at every Boolean input you just wind up summing up zero over and over and over again and the result is zero but if G sub H evaluates to something non-zero at even one Boolean input then once you square that you get something strictly positive and so you sum up a whole bunch of things at least one of which is strictly positive and none of which are negative you get out something strictly positive right so checking that g sub H evaluates to zero everywhere in the Boolean

hypercube turns out to be equivalent to checking that the sum of its squared evaluations over the same domain is zero and this is exactly what the sun check protocol does so we can apply the subject protocol to G sub H squared okay and that's it the verifier checks that the resulting sum is zero and this is literally what the um certain state-of-the-art practical snarks do um except some of them don't like to work with circuits they like to work with generalizations and I'm hiding this issue that in finite Fields like you have to do something a little different because you can uh kind of sum up a bunch of things and they wrap around the

zero even though they were each independently like positive okay did that make sense I know I wound up going fast and this was all very technical I want to hear why fft matters okay great great um let me Jump Ahead then it matters for two reasons um if you want the fastest possible proverb um you can't have the prover do an fft okay an fft is n log n time which is super Linear by a login Factor okay so if you want like you can hope

for a linear time prover um order n not order I'm sorry n log n where n is the size of your circuit so if you really want a linear time proverb you can't do an fft so that's one thing so to get the fastest possible approver asymptotically and concretely you can't do an fft um another reason to avoid fft is only some Fields support ffts okay um in particular you need a multiplicative subgroup with certain structure blah blah blah blah um now there are very natural statements people would like to prove with snarks especially about you know um involving certain elliptic

curve-based crypto systems and deal you know until people five ten years ago started developing snarks these elliptic curve groups um people were not worried about doing ffts over like the field underlying the group right so um if you want to prove statements about the elliptic curve groups that people have been using for a long time um you often can't use a snark that the prover has to do ffts and there's been some recent work mentioned at the bottom of the slide that seeks to kind of do ffts over any field um it's as far as I know the work um hasn't been fully implemented and um it's not clear that it's practical

um and even if it is practical asymptotically at 10 log in time right and like you're probably it can't possibly be faster than the fft over fft friendly Fields right it's like it's trying to generalize ffts to other kinds of fields um so it's probably you're going to have to pay some price for that so that's going to make things even worse for the proverb um so yeah and then the final reason is ffts um you know they tend to be hard to parallelize and distribute and like get Hardware speed ups for because they're often memory bound rather than compute bound so yeah they're like three different reasons why you'd like to try to avoid ffts you know work over any field

um fast prover amenability to Hardware acceleration and parallelization Etc et cetera okay um so I have I have recent work that gives a polyamal commitment scheme that does not require ffts and if you combine it with a some check protocol based um polynomial IOP like the one I just spent an hour and a half presenting to you like nothing in the snark requires ffts and in the process we get the first implemented snark um where the prover is strictly linear time so like n log n is not strictly linear time um and it's field agnostic you really can work over any field as long as the field is like big enough that soundness

holds in the snark um and maybe I you know I obviously won't tell you how it works now because I have two minutes left but I can show you some performance results because why not you know what so you know I Was preparing this talk I I didn't feel good enough yesterday so I Was preparing it in the last like two hours and I said there's a brand new paper very nice paper from what I could tell just looking at it like two days ago know caught Orion okay um they do they actually they take the the snark that I designed with co-authors um and to get the proof size down a bit they compose it with a different snark that has smaller proofs but a slower prover and we've discussed

in like my first two talks how you can kind of try to get the Best of Both Worlds by through composition where you take a a snark with a really nice proofer but bigger proofs and you compose it with a smaller proof snark and uh you know up to concrete details like you should you know only sort of pay for the expense approver on a small statement and so it's really a low order cost and you wind up with like the small proofs of one snark and the fast prove or the other so they they were sort of pursuing that approach um unfortunately the the small proof snark they use does require ffts so they're sort of at least right now giving up on the field agnosticism um but they do and sort of inherit the

the fast prover of arsenarch okay unlike my paper they had pretty grass so I just I posted like you know an hour before this talk the graphs from that preprint into um the slides here so that I you know it's something you can to parse in like a minute or two um so okay so breakdown is is my my snark you know from field agnostic um linear time prover and Orion is the new one again it does work only over fft friendly Fields right now but um inherits like the the nice fast prover um and so you can see like the the new approver is

um about the same um so certainly no slower um and the the nice Improvement is in the proof size which for my snark was in like the dozens of megabytes so like sublinear proofs but like not very sublinear sub-linear so by sublinear I mean like the proofs are smaller than like the size of the transcript for the circuit but they're not they're like square root in that size with a gross constant so um you know they're only a little bit sublinear if you will um so now the proofs um in this new snark called Orion um are on the order of like one two a few megabytes so still too big for blockchain projects probably but

um certainly small enough for non-blockchain snark applications you can put them in you know attach them to an email or something like that and the verifiers fast like the proofs are big but like the verifier is not doing all that much work to check them and then just some comparison to some previous snarks um actually you wind up seeing that um the prover for you know the um breakdown in Orion um so that would be what would that be that would be on this top left chart on the blue and the red like way lower than the Alternatives um now the alternatives are somewhat old so um I will say like if you're comparing to the latest greatest uh

alternative snarks um and this this uh we're we're looking specifically at rank one constraint satisfaction um and so some of the latest Greatest Show marks like to use other generalizations of circuits so they get a little hard to compare and and they're just not appearing in this comparison here that I pulled right out of the Orion paper but anyway so comparing to several prior works you have like uh more than an order of magnitude fast approver um in the in the new snarks um and while actually um the this new work Orion gives it brings the proof size down to um on the order of um

Megabus you know what just like a few megabytes or something and it turns out to be competitive uh so so Aurora is is the green line that was actually a snark with poly logarithmic proof size but I guess the poly and the constants were sort of uh high enough that um uh you actually wind up with you know like a megabyte turns out to be competitive with with poly logarithmic um proof size uh for some of these these snarks that are using um fry is a polynomial commitment scheme that has probably logarithmic size proofs and it's just it's uh poly logarithmic is asymptotically great but concretely uh the poly is at least two and the constants might not be the best

um and actually the the verification cost of breakdown in Orion is is better than the uh than the older snarks anyway so just to summarize um these these new polynomial commitment schemes um that you know have some nice properties that are really nice for the prover um avoiding ffts and and asymptotically linear time and concretely um like a significant speed up over over prior work and the remaining hurdle to sort of make this uh something that you know like uh blockchain projects would really want to pay attention to is that megabyte size proofs are still like like way too big when you have snarks like Marlin and plank where the proof is like

half a kilobyte or something like I'm you know I'm not fooling myself into thinking um that that's a reasonable Gap half a kilo by two to a megabyte um okay so uh thank you for bearing with me both with uh the voice stuff and the in the rough talk um which I just you know prepared in the last couple hours but uh you know let me know if there are any questions and um yeah you've been a great audience I appreciate all the questions you've had so far today thanks it's just so I had a question on the field days you mentioned a couple times like the points between field agnostic versus not so can you kind of comment on like when do these fields matter or like for different applications

try to be like like how is that integration like come into play yeah so you know let here's an example that um one of the related works I mentioned that was looking to do ffts over any field like use this as a motivator is like let's let's say you wanted to prove to someone that you knew um a private key that I guess could open up a specific Bitcoin wallet um the elliptic curve digital signatures like used by Bitcoin um work over a an elliptic curve such that like so elliptic curves are

defined via something called a base field I guess like um you know curve elements are pairs of elements of the base field so if you want to prove things about you know [Music] um elliptic curve group elements you wind up having to prove things about operations over that base field and that base field is not fft friendly okay so if you wanted to prove to someone that like you you own the funds in a Bitcoin wallet okay uh without like revealing to them like you know the the private key to that wallet um like you could not use a snark but I'll clarify that in a second but

essentially you couldn't use a snark where um they needed an fft friendly field um there are two caveats to that so one is um you actually can um in principle like theoretically um kind of um change field so use a snark that natively works over one field and proves statements about a different field um theoretically you only need to pay a logarithmic Factor overhead and circuit size for that but sort of concretely that logarithmic Factor will turn lead to circuits that are like really big um so people do really try to avoid that

um the other caveat going way into the weeds is that um taking the sort of polynomial iip I told you about today which doesn't require ffts and taking known discrete log base polynomial commitment schemes which don't require ffts you actually could have proved this sort of statement in the past you don't need our new polynomial commitment scheme to do that um so I'm not the biggest fan of this example it's a nice illustrative example but I I don't actually think it was something that could not have been handled previously you would need to maybe cook up a different elliptic curve um than people are currently like using you know widely today but we actually have procedures to do that so there are

you know lots of caveats to what I'm saying but um yeah anyway the however um the new polynomial commitment scheme I just told you about would let you um uh proof statements of this forum about like be you know owning the funds in a Bitcoin wallet and it would have the fastest known prover to do that um even if even acknowledging you know um that some discrete log based snarks in the past could have with enough extra sort of snark designer effort um done something for that particular application so and of course you could you could use your imagination a little bit to just move a little bit beyond like you know proving you own the funds

in a specific Bitcoin wallet to identify other applications um where you really want to work over one field and not another Nation it's just like one particular very concrete easy to describe thing does that make sense yeah so I guess it's in some reason like the field kind of boils down to what typography the Stark is trying to prove and then like that's when you have to care about the feeling Gnostic or not yeah yeah so I think that's the easiest um way to see like you know caring very much about like wanting to work over a very specific field and that field not necessarily you know being snark friendly um you know so there's been a lot of work in the snark design Community now on developing new elliptic curve groups that um work over fields that are fft

friendly so if you ever hear about the group like bls-12381 um people are sort of I guess hoping to um so this is a pairing friendly elliptic curve um the current elliptic curve that's like sort of built into ethereum that's pairing friendly um there are some like new attacks on it from like the last six years or something so people it's it's like you know accepted security level has fallen a bit so people would like to replace that curve with the new one um that you know isn't susceptible to the same attack so they've uh the main candidate is BLS 12381 and it's BLS 12381 has been very carefully designed

so that it you know it is fft friendly like you can you can use these snarks where the prover has to um do ffts and if you just if you had a snark where the approver didn't have to do ffts you could sort of have skipped a lot of that effort um you know you yeah so there's um there's a lot to be said about you know just not needing to worry about um the prover having to do these ffts um let me think if there's anything else I want to add about this um maybe I'm too covered right to to keep going yeah um about can you comment on parallelized

book Proverbs um like what kind of systems allow the Brewer to be run viral sure yeah so I think like all all snarks the prover is paralyzable to a decent extent um and sort of to elaborate further you kind of have to dig into the weeds um of of each snark um let me just pick one at random um let's not it's not it's it's one of the most popular ones perhaps the most popular one where the proverb does have to do ffts so in in starkware's snark for heirs there that's air is their particular circuit-like intermediate

representations Gentry algebraic intermediate representation okay so the prover in in their back end s up committing like independently to a bunch of different polynomials um like if apparently what uh from uh what's coming out of Cairo would involve on the order of 50 to 60 ish maybe a little more different polynomials the proverb has to commit to okay and they use they use fry um to as the polynomial commitment scheme so there's already at least like a factor 60 parallel speed up available just because you know so the bottleneck

for the prover is Computing the commitments and there's 60 independent polynomials to commit to so there's like a factor 60 speed up right there okay but if you wanted to go further than that um you'd want to start thinking about paralyzing each invocation of fried and that means paralyzing an fft which you can do but is kind of nasty in practice and especially if you want the parallel competition to be distributed so like I believe for example there is an old work called dizzy which was not looking at Star Square Stars actually looking at row 16 and like paralyzing The Proven air anyway in a distributed

setting so um that that um growth 16 has to do an fft not from the polynomial commitment but because it has to do polynomial division so that's another place that ffts can come in and in the so people have like a parallel distributed fft algorithm that I believe does it used but there is a step of that algorithm which involves an all to all communication so like all the machines have to communicate with all the other machines Okay and like that's not nice that can be a major bottleneck in practice is my understanding right so if you don't if you have a prover that just doesn't have to do any ffts you can you can really avoid that nastiness so like

even even though ffts are paralyzable um you want it you run into issues like all do all communication or you know if you're trying to use Hardware acceleration that you know they tend to be Memory bound not compute bound so it gets harder to get Hardware speed ups and all these things so if you'd just be really nice if we didn't have to worry about it and like this new snark breakdown you don't but the the proofs are too big for people at least on the blockchain setting right now so we need we need some more progress um hopefully it'll come but you know it's open resource Direction uh did that answer your question yeah thank you I think we should wrap up here then so thanks so much Justin yeah thanks everyone