ZK7: Comparing Arithmetizations - Harjasleen Malvai - UIUC / IC3

Transcript

[Music] okay um so hello everyone i'm jocelyne i go by her joseline as well and i'm a phd student at uiuc and i also work with folks at ic3 i'm giving a talk on comparing arithmetizations and if you're not here for that you should stay because it's hopefully going to be interesting yeah thank you for laughing on uh at my first joke because uh that helps me be less nervous um okay so um what do i even mean when i say comparing snarts you say you you probably are gonna say people do this all the time they have uh you know every paper has

this like evaluation section here's one from the plonk paper um and uh they provide a bunch of comparisons with other work um here's another one this is from the stark's paper um but the thing is most of these papers compare with other works both based on their full end to end performances on the same program so for example the plonk paper will compare with other constructions but the other constructions are based on different properties than the planck paper or different cryptographic assumptions and so on so but as a lot of you know this

these types of schemes can be broken down to use the same arithmetization but with different polynomial commitments so this is i mean there's a lot of detail missing here but at a high level you put together an arithmetization and a poly commit and that's a really nice recipe and you if you do it correctly then it gives you a tasty little snark okay so you do this to build a nice non-interactive protocol and i'm going to be talking about how the first piece of this compares across some of the more common things that are being used today i have a few caveats yeah i guess if anybody from any legal team is here

this is for you so notice i said arithmetizations so that just means i'm referring only to a class of snark constructions which reduce some program to a class of problems that end up with polynomial relationships over fields and this is based on work in progress so if you have comments concerns please email me or catch me after the talk and and i mean hopefully not publicly embarrass me after this talk uh uh okay so uh i try to focus on the most important costs so uh for example you may see a few off by one errors and stuff that's just for ease of exposition i think it's very hard to read size with

full detail and some of you may say where's blanc well i'll make some controversial statements here old variants of planck close to r1cs in cost kind of newer variants close to error with permutation checks uh so i'm ignoring planck for now and i'm going to try to compare the costs of the air and r1cs type paradigms which are fairly distinct from each other so i also only consider the compression type properties and not the zero knowledge properties because uh once you under add their knowledge usually the overhead is about the same at the same level soundness and the same level of zero knowledge security so

again ignoring that for ease of exposition and also i try to stick to conventional definitions of algorithms because the thing is you don't want programmers to contort their programs every which way to fit your snark arithmetization structure right uh so you know if if you're in a circus you want you don't want this to be our snark and uh this to be your code uh you want it to be the other way around you want your code to you want to pick an arithmetization or a snark that fits your program's needs so that's i guess the end of my legal section so to speak um and with that for people who are not familiar

here's a very very quick rundown of r1cs if this is too fast you can slow down the recording later thanks um so um so basically r1cs there's three matrices that define the program ahead of time and there's an input vector z that the approver provides um and in a sense the a b and c matrices represent the program description and they're sometimes represented by some collection of polynomials which can eventually be able to use to compute some polynomials f a b and c and there's an input vector z okay thank you

uh input vector z represented by a polynomial fc um and um and then you know overall there's two polynomial problems you end up with one of them is called lin check which is basically checking that you computed the product with the matrix correctly and the other one is row check which is then checking the actual az element wise product bz is equal to cc okay so so that's what these are again not going into detail um you can slow this down later and look if you want and overall there's if you start analyzing the costs uh most of these costs depend on the maximum

number of non-zero entries among the three matrices so and i know this is a very dense slide so i'm going to highlight the important part so there's a pre-processing phase and and you can make this transparent if you want so if you're using some sort of hash base narc for instance and it still depends on the maximum non-zero entries among the three matrices um the intuition for this is sort of you want to capture all the information in the matrix right so you need at least that much work to be done and the prover time ends up being quasi polynomial in this variable um and the verifier time ends up usually being polylog

uh in this variable and the field size also ends up being log of security parameter times this many bits and also there's usually a public input which you want to make smaller for this type of compression application and this is linear in the size of public input so i guess tldr what matters for cost number of non-zero entries in the matrix what does that depend on like as as a programmer what does that depend on um it depends on the number of quadratic operations required to represent your program and the number of distinct memory accesses of the program so even if you access the same variable multiple times

each time you sort of access it it ends up costing you some and for the verifier again it depends on the non-zero entries of the matrix but this time the relationship is poly logarithmic or some sort of quasi-poly logarithmic type expression and linear in the public input as i said before so what does not matter for this cost which is to say where does r1cs really shine r1cs doesn't take into account the order or the structure of memory accesses and whether a program can be written down succinctly for example can you write this program as some repeated iteration of the same function

uh that doesn't matter because you intuitively this everything ends up looking like an unrolled loop and you have to decide the size of the loop ahead of time okay so moving on next arithmetization that i want to consider this is called air and i guess uh people are probably familiar with this as well again slow down the recording if you need to later um so you have a bunch of registers that's what these r1r2 and so on are representing uh and an honest prover should fill these according to some rules um and each register has h states this this is the variable that you want to pay

attention to now this little h and all registers um so just shorthand for later all the registers which are at a particular state uh are called a row and all the states of a particular register are called a column so if i use these terms afterwards just know that i'm that's what i mean i mean if it looks kind of like a matrix then yeah that's that's kind of how you want to think of this row and column thing anyway um and you basically lay out all of the states of the program ever and uh the rules get applied at each state um so what does the proofer do to turn this into a polynomial problem

once the approver fills in these registers so these are the previous slide was all symbolic right it's just empty registers that you could do something with um once the approver fills these in she can interpolate a polynomial with some fixed predetermined set of inputs in order to get a polynomial representing them and again you have a symbolic set of symbolic polynomials a bunch of boundary constraints which are basically um some little b number of expressions of the form this particular register i mean this f i x j is essentially saying some claim about one particular

register at one particular point in time uh is equal to some particular value and there's some thing called transition constraints which are basically how does this register depend on everything that came before it uh again um this is a lot of detail feel free not to absorb it and when you actually uh the approver actually writes the inputs they actually compute these polynomials and the polynomial of the problem form of this problem is um there's boundary constraint checking which is basically checking something some expression of this form and there's another expression set of expressions which is transition constraint checking which is expression of this form again i'm sure i'm losing a lot of people you

can come back now because i'm telling you what the costs actually are so pre-processing nice thing about air once you agree on what the programs are and what the relationships are there's no actual pre-processing you need to do for the program representation and this is sort of based on the assumption that program representation will probably be pretty small right because because if the program were large that's when you need preprocessing and the proofer time has a bunch of interpolations of polynomial divisions and so on evaluating a bunch of polynomials um in the end basically you what you're doing is quasi-linear in program size uh as well as all of the variables you ever

computed um and so it's a little bit of a complicated expression uh which is why i didn't want to include it in detail here um and basically for the verifier all operations are over the field um which means they're all polylog in the um number of different states um and and you know there's a few other operations and there's some checking of polynomial commitments in the end uh basically all boils down to linear number of constraints both boundary and transition and number of registers and polylog in number of steps so yeah that's i guess all you need to remember from the slide

again tldr what matters for cost for the prover and verifier both number of registers number and degree of transition functions number of brown boundary functions this is what both the proof and verifier depend on linearly and overall if the algorithm can be written succinctly as an iterative algorithm that's the most important thing and uh the order and structure of memory accesses if there's a lot of variability in this you basically you can no longer write your program succinctly right because you because because every different type of memory access adds something to the description of of an iteration of the

program okay so number of accesses matters um and uh different types of accesses also matters so um yeah again just summarizing that a linear number of iterations for the approver uh polylogin number of iterations for the verifier so let's do one example which is checking the validity of a snark friendly hash chain um and i picked this example just because it's simple to explain but i think an interesting actually applicable analog might be uh taking some sort of proof of stake uh blocked in and looking at the various stakes states off the

the uh root of a block and so on and verifying those over time it's a repeated operation includes some hashes usually and includes some signature verifications in addition often signature verification and hashing uh include similar operations as well so the specific hash function that i want you to look at really quickly is mimsy which is uh arithmetic friendly something to pay attention to there's a bunch of rounds and you repeat the same operation over and over again and there's one uh k for one implementation or one invocation of mmc um and uh there's a

a round constant but these round constants for every single call of this mimc round function thing um are exactly the same and there's one exponentiation so essentially um what i'm trying to say is you're at every call of this round you're only introducing one new variable everything else is predetermined or from a previous step um okay so let's look at what r1cs would look like with this now again just see how many um uh how many values you need to write in that matrix remember i said everything depends on how many non-zero entries you have in a matrix just think of unrolling a loop so you need the input

vector for example to contain hash function round constants and all the intermediate states starting at the input um and the matrices need to be at least that large so um and and also if you have a you have to fix an upper bound number of iterations because you have to have pre-processing you define the program ahead of time uh so even if you actually end up proving a smaller hash chain you still end up doing the same amount of work and since each multiplication is in its own row that also may lead to more cost so in the end basically your cost ends up being remember this k was the factor that that determined everything

is going to be linear in the number of maximum iterations of of this function and and basically the maximum length of the hash chain every single time regardless of whether some of that space is wasted or not so again just repeating that um okay so uh how do you do this in air remember i told you if a program can be written succinctly and i think the code that i wrote was fairly succinct um and kudos to me but okay so each row of an error remember rho is all the states at a given particular time the state of a few iterations may be

inside of that round function that i showed you um and each iteration only of the internal function only requires one new variable so you actually end up having very very few actually fresh values at every every step so you can include a bunch of them within one row and still be okay with the linear cost and also you can support a variable number of iterations and prover cost is always linear in the number of actual iterations being proven and not the maximum um and again this is um same as before this this value h was the most important one and also not italicized by me sorry um it does not really depend on the mimsy

exponent and correspondingly the prover's time and required memory is also kind of independent of this exponent and it's it's around some factor of number of rounds that you actually run for um and the uh and this b is basically the number of uh blocks that you actually want to or number of columns you actually want to write so this think of this as b is limiting is is the upper bound of how many registers you're allowed to use um okay so what this means is prover time is linear in all of the variables again unfortunately but the variable the verifier time is linear in the number of this like constant b which is the number

of um uh is the number of registers you're permitting as well as this mems exponent which is usually pretty small it's three seven something like that usually um okay so i've shown you something where air does pretty well uh i guess the takeaway here is uh air is doing pretty well r1cs not so much um so with that let's maybe um give r1cs its day of glory and look at another example um in just one second sorry okay so now we'll look at fft and why did i pick fft so fft is usually

they have a structure similar to a butterfly network and what that means is each step has a unique but predefined access pattern and you need all of the values in each step to compute the values in the next step so let's call each of these steps around and the diagram on the left by the way taken from wikipedia is is basically just showing you uh which values you combine to do what uh it's not actually showing you the operation uh and usually and the input size is usually uh some power of two otherwise you have to pad it up to some power the next power too um okay so in r1cs i said that um the the diagram before

didn't show you the actual operation the actual operation is here uh this is what you need to do in r1cs for example is you need to show you basically need to update the value of two variables at each step and that requires multiplying um these these these two small vectors um with with this vector um and and that basically means that the input matrix must have at least two n uh values in it and again reminder you may say i can do better i can pick a better algorithm but i'm trying to contort not contort the algorithm to fit the arithmetization here so what this means is basically again that

factor k is n 2 log n log n and there's another factor which is the input vector length again and log n so basically you're ending up in the n log n type sphere which is what the original algorithm required anyway right outside of r1cs or anything and the verifier cost is polylog in this end uh which is which is nice um and then what happens if you use air first of all remember you usually want to restrict to a constant number of columns and i know this from experience because i tried to code this in error and so suppose we without without using a constant number of columns

and it's it's not fine so suppose we restrict to b columns we're writing fft registers alone there's you know a bunch of detail if you want to follow them feel free to take a look at the slide but i think the most important thing here is that the verifier ends up being linear in n and remember n is a power of two may be very large so i've basically shown you that uh error is going down great okay so air by itself you when you have a variable type of access pattern across across and across multiple iterations of

a function doesn't perform very well what happens if i actually add something called multi-set checks or permutation checks to this so um and permutation checks by the way in general are based on multi-set checks so i'm and their costs are kind of close so i'm just going to use those terms interchangeably for this talk so remember i told you prover fills in this table of all the states of a register over time so what you do in order to show for example that r1 and r2 are some permutation or multiset equal to each other um and and a lot of people might be familiar with this you commit to the

first set of values you get a random number gamma this is in random oracle model obviously using that commitment and then there's a few constraints that you end up with again not going into detail right now but but in the end what you end up with is another essentially another second error and so we call the first error the original error and then there's another one which is a second air um yeah i guess the secondary didn't get the house um uh so um how do you describe this program uh the same first you start with an error instance like normal uh and then you tell which columns you want to show permutations or multiset equal of each

other um and you say where to look for the proofs for those in the second error and basically that now you have an air instance that contains all the values from both the ears so you also prove that again you know very similar to the previous version except you know you do that commitment and gamma thing and and these are the extra constraints you end up with again brushing through this because i want to get to the cost of this so again no special pre-processing um uh same as uh air with one additional polynomial commitment uh if any multi sets are done you need one additional poly commit and uh you

need a couple two boundary constraints and one extra transition constraint of degree two uh pretty uh cheap really is three additional poly checks uh for the verifier on top of plein air one uh extra poly commit so why did i introduce this uh i wanted to improve on fft so remember this protocol takes place in rounds just computing an fft the algorithm takes place in rounds and each round can be broken into calculation and permutation steps so what if we wrote down each calculation step in its own column and each permutation step in its own column so for example see the highlighted terms these are these are each

the calculation step starting from the initial state and you write them all down in a column um and uh and then the other alternate columns are basically permuted values of this and and you end up with an extra set of constraints which is basically saying each value is computed by the two values before it kind of thing and uh and then you have an additional set of permutation constraints showing that the permutation columns are correct depending on the the iteration of the fft that you're at okay so i've shown you this um

i know i'm running out of time but so there's a bunch of calculation for how i got here but in the end uh the most interesting thing is this this last highlighted statement which is you've taken the verifier gone from a linear factor of n to a logarithmic factor of n which uh really brings you close to what r1cs could do so what i'm trying to say is i threw something pathological at air air itself wasn't very happy with it but once you introduce permutation checks here uh you end up at pretty much the same spot as r1cs um okay so i guess the summary in in summary

almost always you'll need to at least write the um all the states of your algorithm down so so the prover cost usually doesn't go down in the case of error thankfully and and i guess error with permutation checks which is just a superset um uh if you have a repeated computation you can only write you can write down just the parts that you actually need but the thing that's interesting is um so hash chain verification for example um it can be can be much more efficient in air error but for fft once you add permutation checks you end up close to close to r1cs so this is just a couple of examples and the reason that i picked these two were

basically trying to get at the strengths and weaknesses of of error and r1cs and yeah i guess this is a work in progress so what i didn't include is a systems level comparison that i've been working on so that's building these proof systems on the same crypto assumptions and the same code base and we're using winterfell which is a stark based fry based prover and um also working on other examples of useful programs to distinguish between uh these various constructions um and and there's you know various things that are sort of a lot less

mature than the those systems level code that i mentioned um yeah feel free to talk to me about this if if you're interested um yeah and then i guess with that i'll thank my awesome collaborators and also everybody for listening and also for laughing uh yeah that helped okay and if you have ideas for other applications you think i should throw at these that i haven't covered yet or um may not have come up with you think or if you want to see the paper when it gets done feel free to contact me or take a look at my website okay thank you [Applause]

you