BabySpartan: Lasso-based SNARK for non-uniform computation

Transcript

hi everyone H it's Rafael we are here today uh with s City presenting baby Spartan uh SAS is working at Microsoft research and has worked on a very valuable computation for quite a long time uh I am very excited and I hope you are too about this talk so thank so let's first thanks Sasa for being here and uh let's take notes uh ask questions and yeah thanks again is yours thanks thanks ra thank you all for joining uh it's my great pleasure to present baby sparton in this forum uh so in a nutshell baby sparton is a a new snark and it targets

non-uniform computation uh by non-uniform computation hopefully it becomes more clear through the talk but it it refers to computation that does not have any particular structure so it could be completely unstructured circuits uh so this is Joint work with Justin Taylor and we posted this on ePrint late last year and it's linked from the slide here um so let me start with a quick overview of uh how baby Spartan relates to some of the other papers uh uh so uh so baby Spartan as I said is a non it focuses on non-uniform computation uh so it it depends on this prior system that we also described

in a different ePrint called lasso uh which in turn depends on an earlier work called Spartans Spartan itself is described in a bunch of papers going back all the way to 2019 uh so in a nutshell Spartan is a snark that gave logarithmic proof sizes and one polinomial evaluation argument so what lasso did was it took Spartan and factored out a lookup argument from it and one of the Key properties of lasso is that it only commits to small field Elements by small field elements I mean the bit width of the uh elements is small much smaller than the total

bitwidth of the field elements uh meaning that the set of elements that it commits to are from a small subset of the entire finite field so if you're working with the 256bit fields the bit width of the field elements lied could be 16 or 32 like much smaller than the total field size I'll I'll explain why this matters uh so then there is another paper called jolt which you might be familiar with which is a snark for proving VM executions and this is based on lasso uh so we can think of this VM executions as sort of a uniform competition because there is a uh is the same computation proven for every cycle of the virtual machine

uh so baby sparton sort of um uh is an is is complimentary to jolt in the sense it achieves the same property as jol but for non-uniform computation as I as I'll show later it it's a it's a pretty straightforward combination of lasso and Spartan protocols um so let me go to uh the next slide okay so so and um BB sparton targets p constraint systems uh and in particular it provides what's called a new polinomial IOP and then one can take this polinomial IOP combined with any existing multi-linear

polinomial commitment scheme to get a snark and uh uh one of the key advances like I alluded to earlier is that the PO only commits to small field elements if the witness contains small field elements and this is in contrast with other proof systems for plish like plon and Hyper plon where the provs actually commit to random field elements even if the witness contains only small field elements uh even if the the witness has 16bit field elements the proof system requires as part of the proof system to commit to some vectors where the

elements are random from the entire finite field there is another paper that was posted around the same time as baby Spartan that also shows how lasso can be used to unlock the same advance for the case of hyperplan uh and I think the the two systems are very similar except we focus on using Spartan whereas this other Pap by diamond and pan uses hyper plun which is more suitable for their setting so uh I alluded to this property of committing to small field elements uh

why is this actually important first for if you look at many real world circuits uh and if you look at the witness elements many of them are much smaller than the field the total size of the field for this includes uh circuits like ZK email ZK login where uh uh the circuit actually verifies hash evaluations like sh 256 evaluations and RSA signature verification and many of these deal with small bit as part of the circuit if you look at the bit width of the witness elements they turn out to be much smaller than the size of the field

uh so the other uh reason why this property is important is because in many polinomial commitment schemes the cost to create a commitment depends on the bitwidth of the scalers or the bitwidth of these witness elements uh this includes many popular polinomial commitment schemes like K variant of kzg like kzg plus Gemini Zer marf Dory HX Sona and even the newest polinomial commitment scheme like Bas and uh because of this uh committing to small small scalers or field elements is much cheaper than committing to

random scalers and one small example to illustrate this is if you look at Computing G power 2 to the 16 where the exponent is a small 16bit number is 10 times cheaper than Computing G power 2 to the 160 one of them just requires 16 operations the other requires like 160 operations there is a more detailed discussion of why uh there's a there's a detailed discussion of this point in the lasso and Joel paper so I'll not focus on uh uh providing more details of this uh Point um so uh first uh I'll start so the rest of this talk is organized in

two parts first I'll describe um some background on Modern stock design which will be useful for describing baby spart and then I'll describe spart and if time permits and people have questions I'm happy to go over the paper and then answer any questions of dig deeper beyond the slide deck are there any questions so far um I think we are all good I don't see any questions in the chat okay sounds good so let me start with this background on Modern snar design so just to recap I'll I'll just do a quick run through of these next few slides it just

introduces some terminology that will be helpful later on uh so snark has a PR and a verifier and the pr sends a proof to the verifier and it's a proof establishing the knowledge of some witness to some statement and the statement could be as simple as I know a witness X such that sh to 56 applied to this witness results in some public value y or it could be more general for example the Prov proves that it know a witness W such that the circuit applied to W and some X where X is the public input makes the circuit output one um a trivial proof system is one in which the pro just sends the witness and the verifier

checks uh compared to this trivial proof system we want a snark that has much better properties for example the size of the proof is much smaller than the size of the witness and the size of the statement proven for example we want uh a proof size to be exponentially smaller uh so this is captured by requiring the proof size to be polylogarithmic and the cost to verify proof should also be similarly smaller than the cost to check the witness so in the modern snarks including uh baby Spartan it's constructed with this uh simple recipe where there is a polinomial IOP and it's combined with a polinomial commitment

scheme and this sort of gives a very modular design for snarks because one can take a a polinomial I combined with any different polinomial commitment schemes to get different properties or you can take a polinomial commitment scheme and then find a different polinomial IP to suit your needs and get a snark uh so this combination gives a suent interactive argument of knowledge and it's then made non-interactive using the fat Shamir transformation there are some uh some exceptions to this General recipe uh most notably this includes things like linear PCP based SARS like growth 16 or folding scheme based Nars like NOA they

follow a slightly different recipe but for the purpose of this talk it's uh enough to focus on this General recipe so just to uh dig a little bit deeper so I'm going to introduce this polinomial IOP uh and I'm going focus on the circuit satisfiability so here the the prer sends a polinomial in each round and the verifier um Can evaluate this polinomial at a point in its domain and then uh the prover uh and then the verifier uh runs some check at the end of the protocol based on this um uh based on this check it outputs a bit whether it accepts this messages that the pr sent or not and

there are standard Notions of for completeness knowledge soundness just like in snars that can be defined for a polinomial IP and then one can also use preprocessing so that the verifier does not have to read the description of the circuit in the uh last step of this protocol so the other primitive that we are going to use is a polinomial commitment scheme so here the prer has some polinomial G and it sends a a commitment to this polinomial by sending this message C then the verifier can ask for an evaluation of this committed polinomial at some point R the pr sends a value V and a proof pi and then the verifier

checks runs a check using the commitment the point at which the polinomial is evaluated the value provided by the pro along with the proof and then it outputs a bit and one uh important property here is that the commitments are short and the proof verification is quick it turns out this polinomial commitment scheme is it can be thought of as a special purpose Nar so it has standard Notions of completeness extractability and so on turns out this is exactly the combination that we need where we have a polinomial IOP where the prer would send pols

instead uh we would have the Prov send a commitment to those polinomial uh so in instead of sending them full polinomial it sends a commitment to those polinomial in each round and then instead of the verifier evaluating those polinomial the Prov provides an evaluation along with some proof and then uh the verifier just checks this final predicate by using those evaluations along with the proofs provided it outputs a a bullan and then we can obviously make this non-interactive using the Fiat Shamir transformation giving us this snar so this is the general recipe that we are going to use and the main thing

that we are going to do is uh we're going to design a new polinomial IOP are there any questions in the chat uh we have a question but uh for the end and not not just yet we are all good right now sounds good so so far I've given a general recipe which is also followed by baby Spartan so now let me jump into what baby Spartan is and how it's constructed so let's Okay so so as I said it's it follows this General recipe I presented

in the last few slides so there is a polinomial IOP and it requires a particular type of polinomial commitment scheme that's applied to so-called multi-linear polinomial this is because um the pols that are sent in the polinomial I are going to be multi-linear pols and there are many existing uh schemes that apply to multilinear polinomial like zerar irax Dory Sona Bas they all have different properties so they all have different performance characteristics so when you take a a a polinomial commitment scheme combined with baby spot and you can get different properties and on the polinomial IOP itself as I'll show you soon it it turns

out to be a straight combination of Spartan and lasso so let me go little bit deeper into how baby Spartan relates to Spartan itself so uh so Spartan itself was originally described for this arithmetization called rancs but recently we showed that uh the same polinomial IOP also applies to PL and air which are typically used in plon and Stark based proof systems respectively in fact we show Spartan applies to a generalization of all these arithmetization called

CCS which stands for customizable constraint systems so for uh it turns out that for uniform circuits for example if the circuit contains um lot of repeated copies of the same subcircuit uh this shows up if your circuit is data parallel or it also shows up if your circuit is this algebraic intermediate representation or air uh it turns out that the spot and the pro just commits to the witness uh what this means is that if the witness contains only small field elements the prer only commits to small field elements so for uniform circuits um sparton already has this property

that the prer only com commits to small field elements but if you focus on non-uniform circuits where there is no structure in the circuit like it's completely arbitrary it turns out uh the Prov does commit to random field elements just like how plon or hyperplan also had this downside so BB Spartan was designed to exactly address this problem where uh even for non-uniform circuit circuits which have no structure we want the pr to only commit to elements from the witness and if the witness contains small field elements the PR's commitment cost is also proportional to committing

to small field elements and we pretty much follow the same blueprint as Spartan's IOP uh the main difference between Spartan and baby Spartan is that it's going to use this lookup argument called lasso to prove linear constraints I I'll it will become more clear what I mean by linear constraints um and um so the the overall result is that even when we have non-uniform circuit circuits have no structure the pro ends up committing only to small field elements so let's see how this is achieved so in the paper we describe uh baby's pattern for R1 Cs and CCS uh in this talk I've adapted the

description to blanish as it may be more useful in practice uh to uh to be implemented in existing Library so I I wrote this for the stock we plan to put this in the paper but for now if you look at the stock and the paper there is going to be a difference in descriptions so for this talk I'm going to focus on what's called a vanilla plish circuit uh for this is just for Simplicity one can easily extend this description to custom Gates and also lookup Gates but I'm complet completely going to ignore this because it's going to make my description much simpler uh here in the vanilla plish circuit I have a a set of rows and a set

of columns uh and some of those columns as uh as you know are pre-processed columns these are columns that describe the circuit itself like these are so-called selectors and there are then there are some witness columns these are the inputs to the different Gates and let N denote the number of gates in the circuit and in vanilla plones there are two sets of constraints one is uh these gate constraints that must apply that must be satisfied for every Row in this um Matrix and it's depicted by this equation and this equation is essentially

emulating uh an addition gate or a multiplication gate depending on the values of the selector qm uh ql QR qo and QC and the requirement is that this polinomial evaluates to zero for every row of this Matrix and then there is uh another set of constraints which are so-called copy constraints and the M the main functionality of the copy constraints is to enforce equality between some cells of the witness columns for example if you want the second row uh column B to have the same value as the third row column C we are going to Define uh these

copy constraints and for the purpose of this presentation I use this um abstraction of a set uh so what the set contains is uh it contains a a set of indices I and J so it's just a set of indices so it so the it's a set of elements where each element is a pair of indices and what this uh set is enforcing is if we take concatenation of a b and c which I have denoted with the letter z for every entry in the set say for for every I and J in the set we want Z the value of Z at index I to match the

value of Z at index G so this basically enforces particular requirements on equality of cells in the witness columns are there any questions if not I I will go so the next few slides sort of build on this so if anyone has questions or comments about this please let me know I think we all good uh okay yeah all right so um so the way uh we're going to so we I'm going to uh describe baby spartn in two steps first I'll focus on proving these so so-called gate constraints then I'll focus on proving

copy constraints so proving gate constraints turns out to be exactly same as how Spartan proves gate constraints for R1 CS so what we're going to do is we're going to define a polinomial g uh that is basically the constraint applied to every row of the plish um trace or the plish Matrix uh so and then so the main requirement now is translated to requirement on this polinomial so we want this polinomial G to Value to zero for I ranging from 0 1 to n meaning every row of this Matrix so turns out that uh checking this

polinomial G is zero for at n places is same as checking the sum Su check equation so except for a small soundness error checking that GFI evaluates to zero for all the N locations is same as sampling a t and then taking sum of evaluations of G with the weights given by this special polinomial called EQ so this is a special multilinear polinomial EQ it's defined by this random value Tow and we evaluate this EQ at all the points uh from 0 to uh so one to n and we take the weighted sum between the two and then we check if the weighted sum is

zero so now uh here is the argument for proving uh G constraints turns out this is very similar to how Spartan proves gate constraints for R1 CS so the verifier in an offline setup phase it creates commitments to these um selected polinomial so there is qm ql QR and qo these are the four selector polinomial it's going to create a commitment it retains commitments to those polinomial so in the argument in the first step the pr sends commitments to pols a b c these are going to be multi-linear pols but for this description it does not quite matter so much here uh and then the the

verifier samples random to sends it to the pr in the third step which is where all of the work happens uh the pr and the verifier run the sum check protocol and what the sum check protocol does is it reduces the task of checking this uh zero equality over the entire hyper Cube to the task of checking the valuation of g at a random point R and this R is going to be picked during the course of the sum Che protocol and then what the verifier does is it just uses the polinomial commitment scheme to query all the polinomial incl the pols that it holds in the setup phase and the

polinomial that were sent in the first step and it queries all of them at r R and then it checks checks this simple equation uh at a random point and if the if this check holds the verifier accepts if the check fails the verifier Rejects and this is all that is necessary for checking gate constraints so now that I've described how baby spartn proves gate constraints now oh one more thing that I want to point here is like if if you notice um uh the during the course of the sum check protocol there are no additional commitments that are sent by the prer and the only commitments that the prer sends are the commitments to these

Witness polinomial A B and C so if the witness has small field elements the prover ends up committing only to small field elements so now let's see how we are going to prove baby so baby spartn proves copy constraints so recall we have a set s where the entries are a pair of indices and for for Z which is a concatenation of all the witness columns we want for every pair of indices in the set we want the value at the index I to be the same as value of the index J so suppose we have M Copy constraints um and turns out proving them uh is same as proving this uh Matrix equation so

for this for the sake of this description I'm going to use two matrices L and r out there is a a way in which we can live with only one Matrix which will give 2x savings but for the sake of this description I'm going to use two matrices because it's much easier to describe uh so what this um um let let me talk about what this Matrix contains uh so this Matrix has M rows uh one for each copy constraint and uh if you look at each row of these matrices it's a unit vector meaning uh there's only one entry that is non zero and that value is going to be one uh so what it does is if you look

at a particular copy constraint it just it set one at the let's say the copy constraint says I comma J uh and we going to set the E column of L to one for this copy constraint and the J column of r 2 one so what it does is if you do take the Matrix Vector product the left hand side picks the Z and the right hand side picks the zg and then the equality enforces that Z equals ZJ so we've just translated from this uh uh set um formulation to a linear algebraic

formulation so what the reason this is very important is because uh this is exactly the setting of lasso uh and uh in lasso what we do is uh uh it provides a lookup argument and every row of this SPS Matrix picks a an entry from this table so in the lasso setting Z is the table and L is basically specifying which entries of Z are picked and uh By Design l so by using offline memory checking it only uh commits to small field elements so by using lasso to prove this uh uh linear algebraic equality uh we end up also

getting the same property of same property where the prer only commits to small field elements so in a bit more detail um uh so for this description I gave the verifier key for the copy constraints this commitments to these pols L and R these are sparse pols but in the case of L so this is just commitments to two vectors of size M where m is the number of copy constraints so I so in a bit more detail let's say the set s consists of M Copy constraints i1 J1 I2 J2 so on up to I IM JM so L is just this Vector

of indices on the left i1 I2 so on up till I am and sorry there's a typo here so it should say r r r is the vector of indices J1 through JM and these are the only two commitments that the verifier needs to keep in the offline pre-processing phase and this is in addition to commitments to the selected polinomial so um now to prove copy constraints here is the argument in practice so this is going to run lasso which internally also runs the sum check protocol in practice what's going what what should be uh done is uh this Su check argument a sum check protocol

should be batched with the sum check of the gate constraint so to reduce the proof sizes uh so what the verifier does is it it samples a random beta which is of size log M where m is the number of copy constraints and then we run lasso to check this equality and what this equality is checking is it it basically checks The Matrix the linear algebraic formulation that I showed in the last slide uh so the the let me go through the notation a little bit uh so the L beta comma y uh basically takes the weighted sum of all the rows of L multiplies so once we take the weighted

sum of all the rows of L we get a vector we multiply that Vector with z and then on the right hand side we again take the weighted sum of the rows of r with some evaluations of beta and multiply that with Z we get another value uh we sum we basically take the inner product of the two vectors and we compare the two values and this is exactly the kind of um uh statement that lasso can prove very efficiently so in summary uh uh what baby Spartan does is it can full clish constraint systems without committing to

random field elements turns out this is a straight forward combination of Spartan and lasso uh so as I mentioned earlier in the talk jolt shows how to use lasso for uniform computation uh baby Spartan does the exact same thing for non- uniform computations like blanish constraint systems so these are all the slides that I had so in the next part of this uh uh session I can answer questions and also go through the paper to dig even deeper into the construction yeah thanks a lot uh so we

have one question uh so I will just uh repeat it in recent months people have used gkr for I guess the same reason only commit to actually use bit I would be interested I would be interested in the trade-off between baby spent and JK based lookups yes yes so I think um so uh by gkr lookup I am assuming uh people are might be referring to um uh log up uh that was based on gkr I think yes yeah yes so uh so that protocol is almost the same as lasso in many

respects uh so uh so the the lasso paper came out I think uh so the main difference between lasso and log up is U lasso commits to only small field elements whereas log up in addition to committing to the elements that were looked up which could be small it also commits to inverses which are not guaranteed to be small uh so what the log of gkr protocol does is instead of committing to those inverses it uh it sort of does the check that the verifier would have done by using the gkr protocol so it avoids committing to those uh inverses which could be arbitary field elements but the

end result is like this log of gkr pretty much has the same performance characteristics as um lasso in some ways they're almost the same uh so baby Spartan you could use lasso or you could use this log up gkr I hope that answered the question uh yes thank you that was very interesting um so we have another question uh on the slide that you showed showing the matrices I think uh uh someone uh noted that this looks uh like a direct application of the St check protocol where you are just

checking that the left side equal to the right side so yeah just checking that the sum of L minus r * Z equal z um and so oh sorry and so the question was if you could explain a bit Mo tells how this relates to lasso uh yeah yes yes yeah yes exactly sorry yes that makes sense so I think um so there are two so on the last step on this slide that I'm showing uh there are two ways of proving this one of them is uh uh so so in in Spartan like this uh goes back

to how Spartan Works uh so we could run one more Su check um to bind these variables that I've called Y in this picture uh so what happens at the end of the sum check is um we the verifier needs to evaluate the polom Z random point Y which is fine because Z is a dense polinomial though we can just call the polinomial commitment scheme to uh get an evaluation of Z the polinomial Z but the problem is with the pols L and R they are so-called sparse polinomial so for example we would end up needing to query this polinomial at beta comma

let's say the randomness in the sum check is r y so we have to end up querying this polinomial L and R at beta comma r y uh so this turns out there are different ways of doing this one of them is the n way where the verifier evaluates this on its own this is efficient only if the polinomial is structured that's why for structured computations even Spartan was able to get U uh uh very good cost for commitments uh whereas for non unstructured comp ation EV proving the evaluation of the spars polinomial turns out to require random committing to random field elements because it has to

commit to some EQ polinomial oh sorry commit commit to uh lookups into some EQ polinomial uh so this is at the heart of the what is called the spark spark commitment scheme whereas what by what lasso does is uh it sort of avoids making lookups into that EQ polinomial so so it it's uh turned into lookups into the table Z itself uh and if Z has small field elements the pr commits to the looked up values they'll also be small whereas making lookups into the EQ table EQ table will have random field elements so if the pr commits even the looked up

values which is what Spartan was doing uh it ends up committing to random field elements do does that answer your question yes thanks a lot we have another question uh and it is about whether you could go a bit more in detail on the small field optimization uh so it is a general question yeah so I think um so uh maybe uh there is a let me go back to the earlier slide yeah so uh so uh maybe we can focus focus on the MSM based commitment schemes so here we are going to

repeatedly compute these exponentiations so we have a set of bases G1 through uh GN where n is the size of the polinomial that we're committing and each of them is uh raised to some power and then we are going to multiply all these values together uh so if the exponent is so there is a standard optimization that's used in this context called the pingers algorithm that's going to compared to nely Computing this exponentiations and then multiplying all of these together Pinger saves all like an order of magnitude or more uh but if the uh so the small scaler optimization is in

addition to pener where if the scalers that are involved in the multiscalar multiplication or the multi- exponentiation are small smaller then the amount of work that the pr has to do for each scaler is much smaller the main reason is it's just uh uh like for example in the simple example if you take G Let's ignore the piper because it's a single scalar uh it's a single exponentiation so we just need to multiply G uh with six we just need to square G 16 times so take G compute G square and then square that value so we just need to keep squaring 16 times to

get the value of g^ 2 the 16 whereas for G to the 2^ 160 we have to do 160 such squarings uh so it's it's in order of magnitude cheaper to come it to the compute the the smaller qu the one on the left hand the small the G power 2 to the 16 than G power 2 to the 160 yeah thanks a lot uh we I think that was very helpful yeah it answer the question um I

have a question since you are since you are committing to small scalas does it mean that you working on field extensions to reach uh the higher security if you wants to have 128 bits of security for instance yeah actually uh so when using um so I think um it depends on the commitment scheme for example let's say we are using kzg or zero marf uh something that's based on the elliptic Cur scheme even though we we committing to small field elements but the the for security uh of those polinomial commitment scheme we still need to work with this bigger fields uh uh so so the

field operations are going to be still with the big fields but the multiscalar multiplication or the multi- exponentiation will be done with smaller field elements and this does not affect security at all as long as you use the the elliptic curves that are normally used for these commitment schemes uh but there are obviously like other schemes like pineas which does not require elliptic curves and uh one could commit to small field elements much faster than committing to Big Field elements and uh baby Spartan can be used with Bas as well and there I think for the security you would have to use extension fields to make sure the

challenges are sampled from the right field to get the small soundness error yeah thanks lot uh I think we don't have any more questions uh so you were talking about going through the the paper uh if I remember well so we can do that if you want sure let me pull up the paper

so you'll see my screen yes yeah I think so as I mentioned earlier in the paper we end up describing this for um uh R1 CS because it's much simpler we are going to update this at some point to also describe for blanish like I did in the talk uh so let's see yeah I think I covered many of these things yeah I think one other point which might be related to something that was asked earlier is uh uh the gkr lookups we could definitely use uh uh any lookup argument as long as it only

commits to the small field elements I think the gkr lookup also achieves the same property as lasso uh uh so we need something called an index lookup ARG so here uh so there is a so in a in a lookup argument in in general uh so the there is a commitment to the table and there's a a commitment to uh some values and then we uh just need to prove uh that all these values in one commitment is contained in the table whereas here by index look up arguments what we mean is we are the prer is also committing to the indices at which these values sh up like like

for example let's say there's a value V and there's a table and this value V appears at particular index I and the pr also ends up committing to those indices where this Val shows up and this is part of the statement and this is uh what we call an index lookup argument and uh as long as the lookup argument like gkr based lookup also supports this index lookup argument they can be used inside baby Spartan uh so let's see yeah I think um most of the description that I gave in the talk uh applies to both rancs and CCS uh so let's

see I'm trying to see if there are any particular points that I want to elaborate related to The Talk yeah I think the main as I alluded to earlier the main reason we uh the main reason a Spartan ends up committing to random field elements is it has to go through this abstraction of a sparse polinomial commitment scheme so in the lasso paper what we did was uh uh uh if if we do not really like for the purpose of proving uh copy constraints we don't really need this uh the abstraction of a

SP polinomial commitment all we need is the abstraction of a a lookup argument so that's that's exactly how we uh end up not having to go to the uh not having to go to this spots polinomial commitment scheme and then completely avoid this random field elements so let's see yeah so uh so there is another question which is can we generalize this um baby part to handle arbitary CCS so there is a distinction between plones and CCS so in plones if you look at uh it only has two types of constraints the gate constraints which are satisfied by

every row and there is copy constraint uh so these copy constraints are just enforcing equality between two different cells whereas if we look at R1 CS or CCS uh the linear the linear constraints are much more General they're much more General than the copy constraints the reason is it can pretty much enforce any linear combination of values in the witness for example I could uh take weighted sum of a bunch of witness elements and then check if it equals a particular value this could be useful for uh checking bit recomposition let's say somebody has split a scaler into some bits and they want to check if the bit decomposition

is correct uh it could be just one constraint whereas with plon is depending on the customization done or if there is no customization done it could have a lot of addition Gates uh so one question that naturally arises we describe baby spartn for blanish can it also handle arbitrary CCS turns out uh there may not be lot of um U benefit from generalization the main reason is whenever we are proving these non-uniform circuits uh we end end up paying costs proportional to the number of non-zero entries in these matrices so if you're taking linear combinations there's going to be many non nonzero entries for every

row of the Matrix uh and the pr cost end up being proportional to the number of non-zero entries so it's it's uh the more General the general artiz might not actually help the pr so in some ways I think by describing a snark for plish uh in this setting of non-uniform computation we might get uh we might have gotten the best possible uh solution already uh so that's one additional point that I didn't mention earlier so to dig a bit more into this recent work of diamond and pan they also pretty much achieve the same property they start with Hyper plon and use

techniques from lasso to get their results whereas our uh description I think is conceptually simpler and it has pretty much the same benefits uh because it also uses lasso and Spartan instead of hyperplan uh to get a snark with the exact same property and the reason their solution seems to use hyperplan whereas uh we ended up starting with Spartan is because I think in their setting they they wanted to naturally work with multiple Columns of the witness vector but as as I showed in our in the talk today uh even baby Spartan can be described for such a an albitization

directly so in some ways I think uh this this work was a a pretty uh straightforward combination of existing techniques uh and we believe this is the the best way to implement a snark for plon F constraint system so if your circuit is going to be uh non-uniform and it might have small field elements I think this is the best way to get the fastest Pro time is there a benefit to folding for this yeah so I think um so here um I think uh we focus on the non recursive proof systems for example you just have

a circuit you just want to producer proof uh and if you have repeated copies of the same thing that you want to prove over and over I think hypernova can be sort of thought of as uh a a version of baby Spartan where it runs one Su check and then it uh uh just accumulates or folds all the linear constraints together uh so in some way uh the if you look at the folding scheme literature there are already teams that only pay for uh small field if if your witness contains small field elements the Pro cost is already small in schemes like hypernova so if if if if you have some

non-uniform computation but you have many copies of it uh I think the best solution might be to fold all of those into one and then prove that one uh uh instance with baby Spartan thank you Lee has hand raised uh yeah thanks for your explanation and I'm just wondering what's the tra off between the bab SP and loo and related schemes because it looks like I mean uh according to my Shon you understand it looks like bis SP

has no uh it's just optimization without any TR off here so I just want to know if I misunderstand something sorry what's the question I I I missed the middle part of the question uh yeah yeah I just want to know if there any trade off when you design the baby Buton or it's just it's optimization for the lasso yeah yeah yeah I think I think lasso was a lookup argument so maybe let me go back to the first slide I had here sorry I'm switching to the other

slide yeah so so the lineage of these works is uh uh so we had Spartan which has a snark for uniform computation it's already good enough like it only commits to small field elements we then realize there's a lookup argument inside spattern and it ends up committing only to small field element so that's what we described as lasso and then we described jolt which is a snark for VM executions then while designing jol we realized we could go back and use lasso insights PN to get this baby sparten so you can think of it as an optimization to sparten using lasso uh where it can also get the same

property of committing to small field elements in the case of non-uniform computations non uniform circuits uh so yes you're right that it's an optimization uh in the context of an existing [Music] IOP uh yes thank you very much I feel more safe to use uh baby spr now because I mean we I considering the uh cost and everything comparation stuff yeah yeah I think in terms of tradeoff I think there is some knobs to play with like for example uh by uh proving let's say we focus just on blanish constraint systems proving both the gate checks and the copy checks together and then making

some choices inside lasso to reduce proof sizes I think there are a bunch of knobs around proof sizes uh and amount of communication uh amount of communication and the verifier cost like there's some trade off there uh thank you very much n Nicholas yes hi uh Faceook for the for the talk uh just a quick question back on the folding I I think I understood what you saying but just want to confirm can you uh we can use baby Spartan as the final uh decider at the end of the folding step right so it will improve directly from Spartan because for the well I'm just talking about a1s because it's simpler in this one but for

the1 CS Matrix we can use lasso instead of the one that was natively in spot yeah yeah yeah actually there is a uh so in in the Nova code base there are two implementations of the snark one of them is called snark RS which is based on Spartan uh and does not use this pre-processing it it sort of targets more uniform circuits uh whereas the there is another implementation called PP snark we haven't described that formally in any paper yet but it's it can be thought of as baby Spartan where it's using lookup arguments inside uh but right now because of our circuits are highly they're not plish they're R1

Cs and there are multiple non like in in this copy constraints right like in the slide 17 that I showed these matrices L and R they can have only one non-zero entry per row whereas in a general R1 CS there can be more than one non-zero entry so it ends up achieving something similar to Baby Spartan except there is one uh one place where it it does end up committing to random field elements but I think if we rewrite those constraint systems so that there's only one one uh entry one nonzero entry per row of the Matrix uh we can we basically get the benefit of baby spartn with what is called PP snark inside no code base I

see and for so for General CCS we can use baby pner as a final deci yes yes exactly excellent um I don't see any other question so I think we are good um so thanks a lot for coming today that was a really interesting talk uh I will have to have a look at the at the repository later on uh it seem interesting uh so yeah thanks a lot again for coming I hope to see you here

uh in the future thank you so much thank you all for joining uh if anyone has any questions please reach out yeah uh if anyone has any question you can also reach me out and I can send to to you afterwards that's no problem at all thank you so much have a good evening thanks bye bye