Sangria: a Folding Scheme for PLONK - Nicolas Mohnblatt

Transcript

and F is the sub function of a processor you now have a virtual machine and you can execute and step with a virtual machine if your function f is a transition function of your blockchain and the states are the actual status and the private values are transactions you have a roller so AVC super useful model hacks can be realize it and this is like I think the volume Construction and the idea is that you have along with your space the prover will prove the function f and will produce the proof and this proof gets updated with every step of the computation the question is what happens inside this

black box PF so because we're updating the state we're also updating the functions we're performing the function act so our proofer will have to do s in some kind of circuit we're also updating the proof so we need some extra amputation which right now we're just going to box and call Overhead and the question is how much do we have to pay on top of grid running the function f so how much is the overhand as you notice like we're paying for the overhead with every step of our incremental computation so ideally we'll keep that as new as possible so this kind of a historical approach

like what did we do we're like okay we want the overhead to be super small great we have snarks Snorks are extinct have short verifiers that should definitely be the thing we put there as like our extra work so by doing a snorkel snork that's sort of the approaches that you have in funky 2 or how dark bro do their recursion and what you do is with every step the crew will station the proof read the whole proof run the whole verifier and produce a new proof so everything happens um this is actually super expensive I think fractal does this in a million or one CS constraints if you want to do graph 16 within growth 15 without going into fancy curved Cycles I think the

direct Park people have a circuit with 20 million constraints so this is some pretty crazy circuitry can we do any better yet um so this is the Halo idea where with every step of the computation you've taken a proof you read the whole proof but you don't run the whole verifier you run sort of what we call the easy part of the verifier which is like working with evaluations and the hard part which is checking polynomial commitment you defer till the variance so the idea is with every step you only do part of the verifier you accumulate the hard stuff and the hard stuff you'll do once at the end outside of a circuit um I forgot the numbers here but I think

this takes you significantly down into frames to like about a hundred thousand sort of r1cs equivalent can we do better than this yes again there's this paper called tcd without succinct arguments and PCD is sort of a more General version of incrementally verifiable conversations and what they do is they say all right actually we don't need to read the whole proof so we just need to read part of the proof a small part of it we just need to run part of the verifier and we defer reading the whole proof and doing this hard verification till the very end and this is the first time where you have a small n constant uh recursion

overhead this is great can we do any better than this yes and this is kind of the folding approach from Nova so what we do actually these high eyes that we call proof or ivp proof we'll actually not be fruits they'll be unproven instances and we'll see in a second in Twitter exactly what I mean we take unproven instances you compress the new one into a running instance and what you actually do is you're just for proving until the very end so with every step of your computation you're no longer proving you're just compressing things together and you'll prove that compressing at the very end

okay this takes you down to about 20 000 constraints r1cs and the question now is can we do any better um and yeah Define improving sort of seems like we can't do any better but the question is maybe we can represent our circuit um in something that is more efficient than our ones yeah so the question can we do this sort of Nova construction with a folding scheme but for something other than our one here I'll take a second here just in case you have questions um feel free to type them in the chat otherwise

are you trying so the question is we are trying to get other advertisations in Hope For Better representability or anything else um it's exactly that we're hoping that we can represent our circuit in something that is more efficient also this is where I lack some knowledge but probably some proving systems are more efficient than others and some Brewing systems work with specific arithmetizations but yeah the idea here was all right can this 10 degrees president's recursion overhead in the concludes rather than a Norwin theater circuit hoping that it will be faster to prove similarly for our function at maybe our function that benefits from being

expressed as a plant circuit with oh that's engaged or a very wide circuit and can we still support the Nova style recursion in that so freak definition so that we all agree and I'm sorry for people who are super familiar with Punk he's seen this 50 000 times um but let's do this quickly so if long Trace is kind of like a Sudoku it's a grid has a fixed size the goal is to fill the cells with numbers and numbers who are in quotation marks because we want we're working with

finite field and you have rules that you have to follow so like in the Sudoku some of the values are already filled in for you so you have all this stuff on the left that we call selectors already filled in and stuff on the right some of it is filled in by the verifier so we call those the public inputs the first rule we have to follow is confidence strength so here I've marked squares with colors two squares that have the same color and need to have the same value the second rule is what we call the gate equation and it this applies with each row and you see down here this equation you see that our each of our columns have a

label we want the values along each row to follow to satisfy this equation right a circuit is defined by the selectors the concrete values that are in here on the left and the rules so the increase copy constraints and the concrete gate equation that you choose to use the part on the right which is what the Hoover and verifier get to play with we divide into two parts the top part we call the instant part which is the president of the verifier you get to play with and the bottom part is the witness which only the prover gets to you

um foreign familiar with the Halo 2 ecosystem and they Define their instance slightly differently as a whole column um sorry about that let's stick to this definition but these definitions are actually equivalent so now definition of a folding so this is live from Dan bonnet's lecture in the zero knowledge proof mooc that's going on at the moment um so a folding scheme as I said earlier it compresses two instances into one so the first thing is we have to fix a

circuit C and by fixing a circuit and remember that we mean fixing the selector the copy constraints and the game equation so we fix the circus and then we have two parties approval and a verifier the approver knows two instance witness Paris so it knows instance one witness one that correspond to it and it's with two witness two instance one and two the prover sends a message to you we'll see what that message is the vertical sends some randomness and at the output the proofer now has a new instance witness pair which I'll

also call a trace it has a new trait and the verifier has a new instance the important properties here are completeness so if X1 W1 and x2w2 were satisfying assignments to the circuit then xw the output must also be a satisfying assignment and now knowledge found it which is kind of the important part if approver nodes a satisfying witness to x and x is the output of the folding it must have known with high probability satisfying witnesses to X1 and X2 I'm going to say that again

um if you as a proverb are able to produce a value W which satisfies X you must have known values W1 and W2 which satisfied X1 and X2 and this is a very important thing even though we've compressed two instances into one we haven't lost the requirements on the truth [Music] so how do we do this for funk um this is our first attempt we have two traces Trace Prime and Trace Double Dash right however you want to call it and we're going to take a random linear combination of them so we take a random value r we multiply all the values inside one of

the Traces by R and then we add things together we're very lucky are going to be preserved really the blue squares here a prime one B Prime 3 are equal to each other and the blue squares here a second one and a second three are equal to each other then when I multiply by R they'll be equal and when I add things together everything is still equal so A1 B3 are equal to each other and we have satisfied the confidence rate was because these constraints are actually of degree one the problem is that our guess equation is not linear and we can't actually do

this naively [Music] um I could show you on the Whiteboard afterwards why it doesn't work it is a bit messy but we have plenty of time so maybe that's something we'll do would we do instead is we learn from what Nova did Nova says all right actually the gate equation you can slightly modify it where you can relax it in a way that will allow folding and the second thing is proven verifier so the reference needs to remain succinct but it still needs to check out the prover B is on it and so to do that the verifier will work with commitment while

the prover will work with the actual trade so this motivates what we call the relaxed phone characterization and so the idea is a relaxed witness will be the clock witness as we knew it so the lower part of the trace and a narrow vector and we'll see how we use it later the instance is still the public input from circuit as we know them so the top part of that space that we saw earlier a scalar use we'll see how we use it and commitment to each of the columns in the witness so you have I'm using this rotation where a box with something in it is a commitment to

whatever's Inside the Box and the important thing here is the relaxed gate equation so you see that this U pops up in places under this e fills application how did we do this again we'll do this more sequentially on the Whiteboard the idea here is actually we're going to look at this equation we're going to assume selectors to be so the sectors are fixed right we said we have a fixed circuits so the sectors are not variables our variables are the A's the B's the C's the U and the E we can ignore for now so ignoring equal now which we did with

you is actually we made everything of the same degree right so this term here is of degree two this term here's a degree zero the QC so we multiplied it by U squared to make it degree two all these terms here are of degree one so we multiply them by U to make them a degree two the reason we do this um and I hope I have it written on the next slide I think I do so we'll see in a second why we do this how do we fold with this relaxed arithmetization kind of in the same way as before um we're still going to take our lineal combination linear combination of our

traces with this random r the new scalar you we're also going to just take a random linear communication and the error Vector is sort of the freedom we have to correct any mistakes so let's keep it free for now and see in a second what you do with it now this is the important part and this is why we made our equation or gate equation to be if I compute my gate and by getting the whole gate equation over the final trait which is this linear combination of the incoming traces because negative equations is of degree two I'll actually something have

something of this form where I have Gates of Trace Prime plus r times something plus r squared times gate of Trace this looks a bit like magic um unless you're familiar with like homogeneous polynomial um we can happily write this out afterwards on the Whiteboard the question is how do we get rid of this teeth what do we do about this tea and this is where our error term comes in you can say all right let's define the new error term to be the incoming one and to remove the term RT that we don't care about

and the nice thing about this is that t is fully defined before we know R we don't need to know R to come up with it so overview of the protocol the prover can compute C because it doesn't depend on art it commits to it and send it to the verifier the verifier will sample a random value send it back to the prover B and now they can both compute the printer will compute over the trace as we saw earlier and I think I forgot to have you here there should be linear combination of the traces linear combination of U

and this special equation for our error term and the verifier will do the same thing but over commitment right so recall that are relaxed instance pad commitment to the witness value so we can use the commitments we have from both instances to compute commitments to the new witness without ever seeing sorry we can use the commitments we had to the incoming Witnesses to compute the commitment to the new Witness without ever having to see the witness or

the new one the old ones anything and same with the error term because we were given this commitment to T we can compute a new commitment to the new error term skip some details this is stuff in the paper we will get back to this and hopefully by the end of this difficult we'll seem intuitive performance what the verifier has to do is this work over commitment so if we count this up we have um by Taylor times a commitment which when we're going to be using elliptic curves this is going to be a scary multiplication

so we have five clear multiplication um and finally five Edition Point Edition what happens in practice is we'll be folding a relaxed instant with a non-relaxed instance where it's not yet relaxed so the error term is going to be zero for one of the two incoming instances so actually one of the additions here we don't really need to do so we can take this down to four point additions and four multiplications that you mean that this e Double Dash is zero and no further they do this with only two point Edition because they have one point Edition for the error term and one point addition for the single witness they only have one witness color whereas

we have three how does this extend to the nice features of clunk so white circuit if you have an extra column you'll need one equip witness commitment and if you'd be here if we add like one line of width and commitment we'll have one more addition the cost for wider circuits we get we need one extra point addition for high degree games and this I think let's also write it out later what happens is if we have a home Engineers polynomial of degree higher than two let's save

degree d we will have more questions but we will still have this nice um this nice pattern where we have R to the zero times the left incoming Grace witness whatever it is we're computing we'll have R to the highest power times the other incoming traits and a bunch of cost so we can still work in the same way we did we'll just have more questions and therefore the proofer will have to spend more commitments and again in Computing the error term here there'll be more additions for the verifier

so again we have one extra point addition for extra degree cool the question with all this if we go back to our IBC and our overhead is by adding columns and adding stuff to my gate equation and I make this verifier circuit so the circuit that performs mostly scalar multiplication and point additions and this thing be more performance and is there a trade-off to be hit like oh if I add five columns okay I'm paying for five more five more Point Edition but maybe I've made them all 20 times cheaper

I don't know um this is kind of the game for the circuit Wizards out there so hopefully we'll have implementations how soon and you can try this out and that's kind of it for now um the next thing is we chose to find a folding scheme all the rest How We Do IVC um how do we get uh 16 privacy so like a nice little snark at the end all that we can use the results from Nova we can also do Supernova with it we just plug out all the R1 tier stuff and so again this is look up our work in progress I can chat

about some ideas as well as in the Q a and yeah hopefully implementation will be done soon so you can have fun trying to get this for kids uh that's it for the presentation or at least the flight part of the thought um I'll take some questions now to clarify things and then I'll bring up the paper bring up a white board so this is killing multiplication General is very expensive are done in their native field in the IVC verifier this depends what you do so you can do

them in their native field if you're using curved Cycles and why do we need Cycles we the verifier is working with these commitments right and it's but it's also working with the public inputs which I've hidden away from here I think we can see it uh where's this load where you have the proper there we go you can see if you're the verifiers work never mind the graphics work equation stands here you see the verify is working over um actual scales like it's working over the actual trace

the elements of the trace but it's also working over committees and these commitments commit to values of the trade so they are actually represented in practice by points of an elliptic curve and the points of this curve have a base field which is different from the final Fields we're using for our wires for our phrase values so what we do is if we have Cycles we're good if we don't have Cycles we have to do non-native arithmetic folding lookup does it depend on the lookup system or the newest ones such as CQ can also be folded is it mentioned somewhere how to do lookup folding so there are works right now

um I know there's one thing called origami and there's a post on VK research as well addressing this um I think we're not fully There Yet the intuition Behind these posts is the right one and I think I'll keep this for a bit later first I do want to talk about the the basic scheme and going through the paper properly um but yes it does depend on what team you use and PQ is sort of known to be aggregatable and I think that probably will make it easier to I guess fold CQ but yeah don't call me on this I haven't looked into it I've been looking at uh look up mainly is the M16 ZK snark similar to the one

in the Nova paper and the same one we used so the Nova at the end or similarly with this IVC Construction what you end up with these proofs in our case are actually instant witness pairs there are traces of this relaxed blank arithmetization which we do need to prove at the end the snort that is shown in Nova works for relax r1cs so we can't use that one exactly we'll have to take a variant of 12.

um which work for relaxable and essentially what you need to do is remove the first round and make sure that the verifier the other protocol but using the commitments that they already hold the witness and then we I'll give you a bit of information for this long paper if we scroll down to where the protocol happens there we go this is round one the W values are sort of the the widget values as we've seen multiplying them by the LaGrange

polynomial means we actually create a polynomial from each witness column and this is some mapping to make things your knowledge and then these things commitments to these things get sent to the verifier in our case we have to get rid of this round one and we have to say the verifier already holds commitments to the witness calling you have to be a bit tricky about it if you don't want zero knowledge you can just keep going with the protocol here for starting from round two so now let's look at the sangria paper

and see how everything we've talked about so far maps to things happening in the paper so introduction some notation bold letters are vectors digable vectors are matrices clock transmittization this is sort of how I write out the gate equation I say G for I guess circuit U is the sets of selectors I use the specific row we're looking at and abcr columns and this is the gate equation as you know it um all this text we can ignore this is sort of the same a Trace

is divided into the top part and the bottom part instance of witness and this is folding schemes in a very uh informal way so the sangria itself as we saw earlier we make things homogeneous and maybe this is time to bring out the Whiteboard yeah this is time to bring out the Whiteboard so why do we care about making things common changes let's let's hope that this works so we have we left a and you see what I'm writing

oh it's watering oh there we go you're right we that you are pretty but this multiplication a b c okay and that she looks a bit like it here I'm very sorry all right let's look just at let's say Q L A and what happens if I replace a and I say this is actually equal to A1 Plus R A2 not rocket science we'll have this is

equal to you will A1 Plus bar A2 and this is URL A1 that's r u l a t so so far we're happy right because we have let's see if I can highlight things here this is kind of the gate equation as before Oh My nope this is horrible let me undo this this looks like the last lecture times a as before this also looks like the left sector times a is before multiplied by something but that's fine because if we have our whole gate equation multiplied by something because the gate evaluates zero we're happy like it's still going to evaluate to zero even if we've

multiplied it by r the problem is when we reach our multiplication gate um a b and let's say that b is actually equal to C1 plus r z we'll have um A1 r82 B1 r B2 and now if we write this out through yeah I'm gonna have um time let's look at degree one term uh the terms I have no artwork so A1 B1 so far we're happy because that's kind

of that that does look like our gate equation as before we are going to have if we look at the r squared stuff we'll have qm A2 V2 not pH because what do we do with a square right like here we have a square and here we didn't so maybe we're happy maybe we're not and where we're very unhappy is they are actually across them so we have R times um A1 B2

and we also have our um A2 B1 hopefully you can see where these come from to stop me at any point if they are unclear so the question is yeah how do we do how do we get rid of the square how do we get rid of all this stuff and the solution comes from Nova is by making things homogeneous so now let's see the same thing but with a Harmony genius equation so URL a because

you write b c Plus or multiplication times a b so you see cool and we said we want to make this um homogeneous so we'll introduce a new variable U and we'll plug it everywhere we need to make the degrees higher our maximum degree is zero degree two because we're ignoring the selectors so let's make everything of degree two easy and if we do the same thing as before you throughout a and actually try to distribute it out

because U equals U1 plus r U2 and a equals A1 which is r a two hopefully you see where this is going U1 plus two look Spectrum A1 so r a two again we can group things in powers of R so we're going to have R to the zero times stuff Plus or the one thing so this r squared and stuff so the r to the zero stuff is this and I guess this

so U1 UL A1 and this is great because this looks a lot like that very happy um our squirt stuff will be easy as well because there's this two terms don't forget the ql okay U2 UL P2 this is great again because this now looks like our gate equation if we have the square just like we did for a multiplication date if we go back yeah we do have the same thing as here and we have the pet key parts of the one turn

so it could be U1 ra2 and this Dot bro 82 L into A1 okay I'm not going to write out the full like I'm not going to distribute the whole gate equation hopefully you can see how I am going to end up with what I promised on the slide which was Dave prime plus r times stuff plus r squared gate of Trades or Trace one Trace two sorry I've been

using one and two here right there okay and hopefully you can also see that the stuff is not dependent on our it's it's always fully determined by this equation how do we get rid of the stuff we actually say all right we have another term here and this term will contain your thought s okay

so now let's go back see the paper work here all right back to the paper hopefully we have some justification as to why the equation is as it is here the next question is why do we need commissions what am I doing here and this is to satisfy the knowledge on this property if you remember from the slides the Nellie's family says if you know

a valid witness to the outfits of the folding verifier you must have known valid Witnesses for the info how do we do this well with commitment the the commitments sort of force you to come up with a unique witness it's sort of saying the new witness has to be the sum of the previous Witnesses with this random through some high probability right maybe the random term is um I don't know allows for some tricks here we have all these R values which I

didn't discuss in the slides it's because we're working with hiding commitments so the commitments uh you commit to all the values in your vector and you also commit to this extra value to hide your commitment so that even if you're committing twice this and vector the commitments will be different cool a slightly important point is to sort of say like why do we care about clunk specifically because clone can capture any computation so any computation can be expressed as a function circuit is easy to verify if I give you

a valid Trace you have a polynomial time algorithm that can read through the traits and make sure that it's correct and what the algorithm will just check the rule are equal to each other and go row by row and check that the equation holds that is the polynomial time algorithm so those two conditions mean that Planck is what we call NP complete it captures all the problems of NP and it is it's not part of MP we want to make sure that by relaxing plunk we haven't lost that property so what I'm saying is take any sort of long story because set the scalar U to the one the error

Vector to be zero and you actually now have a relaxable circuit so any Punk circus can be expressed in a relaxed long circuit and we already said any computation can be expressed in a plank circuit so if we follow through we actually have any computation K be expressed in a relaxed long circuit is relaxing itself part of NP yes you can still check it in polynomial time you do have to do a bit more work because you have to detect the commitment but it's still probably not enough time cool now the next part we talk about the

actual construction and here we're following the formal definition from Nova so they say that holding scheme has four algorithms a generator algorithm I forgot how they called it I think this is like a Egen algorithm approve and verifier so first you generate your parameters and in our case it's going to be parameters to produce commitments who need to commit to the witness columns so these are in the paper it's size s and we need to commit to the error vector which is actually the whole length of the column which is n plus one and again this is just

formalism some people write it differently um the feature algorithm is sort of there to keep things very generic um but actually we don't really use it the verifying key is nothing and the proving key is the circuit us the verifying key which was nothing and the public parameters cool now what I'm saying here is the verifier is giving two committed relaxed instances and the notation is super ugly but it's the best I could do because there's a lot of variables

and it's like right how do we keep things relatively clear so big X is the normal plug-in instance U is the the scalar from the relax long distance and all these things with little bars at the top are committed foreign is this being recorded I am not sure that's more quick and for our for the rest of the organization team uh similarly we have a second instance of the same shape get it beautiful the prover had the instances as well and it also has the witness so Big W is

the lower part of the table let's go back here this is the w e is the error vector and all of these r's are the randomnesses that we use for our committee now the reason we need to keep track of them is because if we still won't our commitments to open correctly once we've added them together we need to add the randomnesses together so first round the approval samples are random RT because we're going to do a commitment and confuse a commitment to T where T is

computed as this where does this come from so this 2m times a prime B prime a prime B second a second B Prime is actually what we have drawn uh here this stuff let me write it out again [Music] if you factor out the r's factor out the qm you're left with A1 B2 so A2 B1 foreign

so hopefully this isn't super surprising this stuff up here you second times ql a prime and U Prime Times ql a second is this stuff point to it correctly right and then we do it for all the other all the other I guess degree one Gates and this one I haven't expanded earlier but this is the costumes for heat let's start here I'm using Vector notation here because

actually I'm saying all right C is the vector because we have a t value at every row and we're Computing all of these values in one go so once you've committed to this the verify your sample is a challenge at random this is going to be the challenge that you use to fold your Tracer together using the challenge you can fold the top of the trace the public input you can fold the scalar and you can fold the commitment using notice here this commitment to T that we got in the first run another approver does the equivalent stuff but over the uncommitted values W's and E's and over the randomnesses to make

sure that the commitment is still open correctly I'll stop here for questions sorry about it foreign no questions either I've lost everyone or it's a very good thing well I'll just wait a few seconds to see

QB of piping thank you oh okay um if someone has like any questions and wants to like say them like speaking instead of typing just ask to be on the

stage and we can just give you permission and therefore you can ask with your voice instead of texting which might be annoying for for some things so yeah yeah um we can look at the truth if you're interested um I'll first do custom Gates how do we deal with custom Gates let's say um oops always a tiny bits more and I still see someone typing [Music]

thank you all right I'll get started and so no the question isn't set aside with us afterwards absolutely they're actually already on my GitHub I think I'll share the link at the end okay so custom gate of degree to let's keep things simple for now will read this custom gate as a new selector qg and some function G where G is of degree 2.

and if we were to write the full gate equation like the full new rule this is what it would look like this is classic one gate Plus the new stuff how do we fold first thing we need to do is our function G we actually need to break it down into a thumb because we need to make our whole gate homogeneous right so we break it down into thumb by actually having new selectors we need a selector for so ignore that actually we keep the same selector but we have the degree one part of our gate the degree two part of our gate

and any constant part of it and as before we make informal genius so we multiply by U squared the constant part we leave the degree two part alone and we multiply it by U this is all in one bracket the degree one part and folding still happens as we saw it earlier just now we have a new craft term we'll have cross terms that arise from the degree two part of Eugene wait did I mess this up oh yeah well that's fine the degree 2 product PG we have crossings that come from the constant part of it and they're called across the hero from oops can't

highlight the right thing doesn't want me to highlight but I hope you see what I'm talking about it's a green one that's relatively easy to custom gauge what we need to do is just change our expression for t and everything else the whole protocol happens the same way so that is quite powerful because I mean at no extra cost we get to do two three any number of multiplications we want inside our gate right we're not limited to qm A1 B1 we can also do you know another multiplication selector and say oh I want a times d um with three variables not super interesting so can we do it with more

variables and the answer is yes and it's not written anywhere here okay um if you have a wider circuit hopefully you already have the intuition for this um we need one more witness column this Matrix is just one row bigger so is this Matrix um and the crosstalk key will change obviously to take into account the new gate equation and the new columns um but otherwise pretty simple the only thing is we have this extra commitment that we need to deal with so our instances are bigger by one element

and the work of the folding verifier is bigger what by one point addition oh actually let's see what's here higher funding find out that I think they didn't really buff it higher degree custom gate I think I wrote that to degree three gate so I have this randomly breathing that multiple size three inputs together if we want to relax that equation same as before we now take our constant stuff and multiply it by U Cube you one gets multiplied by anything of degree two and U squared gets multiplied by

anything of degree the crosstrom will now have this form and debating whether or not to show this for a simple equation because it is a lot of work do you trust me that this works or do you want to see them after the now if you really want to see the map return out face on the chat otherwise we will work based off of trust but essentially we'll have these sort of degree three crawfords

like and by that I mean you're expanding a polynomial of degree three now they no longer have just like a plus two a B plus b square a squared do you see what I'm going for um you have a much wider one so now you have these three popping up and these two is coming up eventually we'll get to the point where Computing these Customs is actually quite costly even though it's just uh you know arithmetic and it's happening outside of a circuit we still have to commit to these vectors and that is a whole lot of game modification

okay proofs completeness so the perfect business what we do is we say okay we have two cards u Prime W Prime and use second W second we say that both of these are satisfying so if I if I run sorry if I apply the gate equation to either of these things I should get zero and the question is what happens when I apply the gate equation to this thing which is the output of the folding vertical

approvers output in the fully protocol how do we do this well we're going to write out the gate equation and here I'm doing it in Parts because these equations are too big to sit on one line we right side the gate equation for the output so it's stuff that doesn't have dashes or double dashes and as we go along I'll replace with dashes and double dashes and this rotation Lin Q is just to say oh the linear part of the game so if you run through it here we have U times Lin plus r Lin and because this

is linear I can go from here where the r's are inside the linear the Lin parts so here where the r is outside hopefully that's fine um and now it's about multiplying this stuff by these new use and as we saw earlier we'll have power zero times distinguished looks like the input r squared times is the same thing and the Crossing so the cross terms we all package into this tli because it's like term for linear and we'll use this later finally we have the multiplication gate which we actually wrote out together on

the Whiteboard so hopefully this crossturn would be familiar to you um yeah and then we have the constant costume which is the one I didn't right now but you have this is squared so this distributes out to U Prime squared plus two U Prime who sorry U Dash U Double Dash plus u Double Dash squared multiply that by QC everywhere infinitely again we have this costume which hopefully be recognized from the T equation earlier bringing this all together if we say

the new e is actually the old e that's r squared the other old e like the left and right inputs minus all the costumes that we defined above we're back to what we actually um claim for our definition of e and so we can write nicely write applying the gate to the folded output is the same as applying the gate to the left input plus r squared times applying the gate to the right input and because these things were solid satisfying assignments this is equal to zero this is equal to zero times r squared still zero so we have zero at

the end we have to show also the copy constraints or preserved and this sort of what I showed you intuitively with the colors matching if I want again whatever I went to the master the message essentially saying this uh R times the blue squares these things are still equal and if we add things that are equal to each other sorry if we add things that are mutually equal then we'll have something that is equal

so we're saying all right if m Prime so anything Prime is on the left hand if the lesson since I J is equal to the left instance or the left Trace Alpha Beta so we're saying these blue squares here and we're doing the same came in with these but on the other side the same indices on the other side if these ceilings are equal if I take a different way to replace this from our equation of the folding so we know that this is actually this is equal to that because that's how we folded and this right hand side is

equal to this right answer side here because that's how we folded and so we found that our blue squares because the final traces are equal commitments are the commitments still valid and this is sort of where the homomorphic property of the commitment picks in we're saying okay the output commitment was by definition the left inputs plus r times the right input so if we write this out in our commitment notation we're saying we have a commitment to the vector WK Prime so I'm using K to say like any one of ABC

so it's a commitment to the left witness vector with some randomness plus r times a commitment to the right instance Vector plus a randomness and because our commitment is additively homomorphic I can say okay this is a commitment to the sum of the vectors where the sum of the randomnesses and this is why it's very important that we use a commitment scheme that is additively homomorphic because going from line 54 to 55 is only true when our commitment team is obviously homomorphic you can throw the same for e so it's working with three commitments um

and once you've done that you've filled that the gate equation is preserved the copy constraints is preserved and the commitment opening are preserved so you actually have a satisfying assignment to the circuit so to recap what we did here we said it starts with two satisfying assignments come up with a new assignment and show that it is satisfying and we showed it because it does satisfy the gate constraints as we saw here it does satisfy the copy constraints and it does satisfy the commitment okay now which sound is is harder the nounselves we say okay

let's devise an extractor so this is some kind of device or some kind of program that takes the proof of his input and gets to manipulate the prover as if you can imagine this as the extractor being able to debug the proverb so I'm debugging the prover and I get to rerun it multiple times from the same breakpoint so I'm going to set a breakpoint after the prover has committed to T so I want to have always the same initial commitment to T and I'm going to run the approver from that point three times and we get free transcripts from this and through transcripts means I'll get

three different randomnesses from the verifier and I'll get three different outputs of the new folded Trace and from these three new outputs I will essentially do gaussian elimination to recover the witnesses that approvers started with before committing so the extraction strategy we said that we have three different values for r so let's see let me actually show it um we have three different values for r

and in this equation we know w and this W primes and W Double Dash are unknowns so we actually need two values of R to be able to solve this equation and to recover these values is that fine with everyone cool so two unknowns we use two values of R and we recover the two unknowns currently for the error sorry lighting like crazy for the error we have three unknown e Prime d and e Double Dash so we're gonna have to use

three equations so we use three different values of R we have three different equations and we'll be able to recover all three of these terms so that's our extractor strategy that's great that's long enough to prove that we have knowledge Summit we said okay if you're allowing me to debug the prover I can come up with this like candidate values for the incoming Witnesses and the incoming error terms now I need to show that they're actually satisfying assignments and so this is what happens in the rest I say okay now that I've extracted

things I will feel that they actually correspond to the commitments that we had I will show that the gate equation is still satisfied and I will show that the confidence is still satisfied this is slightly involved um just because I guess we are once again working through the logic of I have an instance witness fair I need to prove that it satisfies the equation we're sort of doing it the wrong way around um the overhead teasing foreign

so this will ignore the important part is that we need to show that our commitments are valid and remember that for our witness we have extracted the witness from only two transcripts from only two runs of um the proverb whereas through the errorism we had three runs so we need to make sure that whatever witness came from the Third Run actually is still valid and still has the right commitment and this is sort of where we don't have perfect knowledge on this we actually have something probabilistic because we have some value and we hope that it corresponds to some commitment and here we call upon the binding property of the commitment which says

that um the the commitment can only like there won't be a collision there is only one vector for which we can open the commitment and this is where the negligible probability comes in and this is where we end up with our extractor working with almost like one minus something negligible for those here the success of the extractor this is a very high level run of the now Islamic proof what's important is the strategy here the strategy of first I show how to extract Witnesses from as many transcripts as they want and then I saw that these are valid Witnesses very

important to that second part finally zero knowledge is kind of the easier one of the bunch the only messages being exchanged are hiding commitment and a random value and so even without knowing a valid witness I can produce such a commitment and such a random value there is no decision making on the very far side so there's nothing I need to satisfy so it's very easy to produce a valid transcript without ever knowing the witnesses cool I think I was up there for the prison page inside I'll just take this question

on knowledge on this is RW Prime understand we are stricter more relaxed and now we found it of WWE Prime individually on their own so we're talking about knowledge soundness of the protocol so the knowledgeable property of the protocol says if you know a valid witness sorry I'm I'm sharing as you know a valid Witness to this instance X which is the output that's holding verifier then with high probability ju new valid witnesses to X1 and X2

there's no like the witness W1 and W2 it's not like very probabilistically Witnesses that they they do satisfy X1 and X2 for sure I know that really is answering your question but my point being here because it's sort of a not a relation relation to the wrong word if they're saying okay I should be able to from a valid witness to X and enough transcript I should be able to produce valid witnesses to W1 W2

so you can't really compare them there's a probability of knowings everyone there's a quality of doing W-2 undercoming right yes okay okay if that's the question then yes it is yeah so it's slightly lower right there might be some values w um for which you can't actually extract valid and Witnesses w1w2 but these are extremely negligible like this this happens almost never

and so we assume that this is fine cool oh sorry missed me for now and I'll take the question from QB what's the overhead to using flunk over r1cs Nova versus Andrea can you talk a bit about relaxing which is this is for comparison metrics on verification okay so long and or Wednesdays or two different authorizations as you know in flunk we say with every row we have one addition and one multiplication but then we came up with these

extensions of oh we can have wider circuits we can have custom Gates especially with custom Gates and where your circuits you can say at each row I have some number of addition some number of multiplication with r1cs you say at each row I have as many additions as I want but I have only one multiplication so the question is okay the way I see this essentially is by saying we allow multiple multiplications real real a high number of multiplications per Row in clunk we're saying actually I can do parallel

computation I can compute things at the same time whereas allows me only one um one multiplication per step this isn't the whole picture because you also have the proof system and how fast the proof system is and this is where I don't have good comparisons or benchmarks I think the general understanding is that plonk is faster than something like Marlin for example for most practical circuits cool also feel free to shoot questions I

think we're into the Q a section fully what about lookup okay I like that question uh so lookups there are two articles by Ariel gapson who whose name you'll hopefully recognize about how to do lookups in Block not necessarily in some kind of copy so this first one from Arista wraps so it says okay an error is the right hand side of the

pancreat so just a witness and The Entity air or pair is a trace and the selectors and this article sort of says okay if you're allowed for one round of interaction if you're allowed to verify to give a random value then you can create this wrap which is our air or PR as we saw it before with this extra column that is generated using a gamma value which is given by the verifier and if you're familiar with blank this is actually the ground product argument and checking this ground product actually comes into this equation which is a constraint of degree two

right so this article says you can do what we call a multi-set check by adding one round one round of interaction adding one column and applying a degree two constraint constraints of degree two and columns are things that we can deal with very nicely the round of interactions and this is where I'm still working on it because essentially you need to make sure that this gamut value comes from the verifier that it is truly random so either using shechemere random Oracle or actually having an interaction

and that means you have sort of a little on you have a bit of an unstable state you place wrap you know this thing with this extra column is slightly unstable because I only know the positioning is valid if I know that the gamma is valid so imposes questions for an album found this and I think this blog post called origami but I think it's also PSP people you might I don't know they're here um origami Builds on this idea applies it specifically to the Halo 2 lookup argument but I'm still yeah I'm still not sure that we fully solved the knowledge on this question

so yeah work in progress but the intuition I think is is out there and I do think it works so there's also another article which is linked here how you can do copy constraints and look at tables for multi-side checks so I'll link that as well foreign okay so

um the first one is uh towards the cycle of curves that you need to use so if you plan to use for example like bien and gram king or something like this where one of the girls has painting but the other doesn't uh like how how can you like merge both things together at the end so that you end up with a single proof that you can for example verify in ethereum or something like that and kind of related to that is do you think something like hyperplunk on one side an IPA on the other one or like some kind of skin like this would work better yeah um so multiple things in here the first

thing is the career cycle effect like indeed we don't have curves efficient Cycles where you have parents on both sides um when you work with Cycles you do have to verify the proof at the end on both sides of your cycle and the question is can you how can you actually bring everything back to one side um answers I don't know they're sort of naive way of doing this is by having um sorry I was clicking on the link uh the naive way of doing this is by having approver on your BN side that reason the proof from the Grump inside and actually performs the verification

so you you you're back to doing a snorkel snark but you're doing this in non-native arithmetic so that's going to be super expensive the other approach is um I think what aspect have been working on with what's Zach called Goblin plunk let me find the link and I mean I'm not exactly exactly sure what they do but it's it's addressing the same problem uh just with respect to the origami link I think that's the wrong one so that is there there's a little naming Collision people got very figure happy with the name origami because folding uh

origami lookups is here so there's this one sort of gdf ish construction that was called origami which I've been in touch with the author I don't think works unfortunately um for this origami lookups is essentially based on what I was showing earlier this idea that you get multiple checks from a round of interaction a column and a new degree to uh constraint sorry um Pros did a fully answer your question or did I skip the second part you skip the part of uh whether a high

performance oh yes what kind of fix this yes so ITA fixes it because we no longer need pairings um hyperplunk you still need some kind of commitment scheme right so again you can use hyperplunk but not with a pairing based commitment one funny thing about high performance which I'll show you now if I bring up the paper is there might be a nice Synergy between uh the relaxed long arithmetic and hyperplunk so here is hydrophone and here is sort

of how they arithmetize their things they say okay we take the Boolean hybrid Cube so all the prop all the possible Boolean value and we hard code that everything that starts with zero zero is left is like our left column in our contrast anything that starts with zero one is our right column anything that starts with one zero is our output but notice that the one one doesn't exist like there's nothing hard coded into one one but we still do our some check over the whole hypercube so the nice thing is we could actually plug in M11 to be the error vector and we're still doing a subject over the same size hypercube

but we've thrown in our other Vector kind of for free yeah that was kind of a funny little thing about hyperplunk I'm not sure exactly if it works but it's something I wanted to explore um yes yeah but yeah it doesn't solve the the question you're asking about Carlos of like how do we bring back the proof that is on both bn254 and grumpkin and have it in a single bn254 proof there's also one more thing which uh has been discussed uh this morning at uh

which is related to like how how do you see uh lattices being kind of like the next thing to be used so we have post Quantum properties we have additively homomorphic commitments with them also in week like of course I'm not saying that's easy to find but we could even like half things that use like 64-bit fields or even less so what this thing kind of look like uh the future yeah like that is exactly what I'm working on at the moment okay that's really cool okay okay so I want to build too much of the beans

until we're we're fully there but yeah that's kind of put the work going on um I'll just take the question from kill each in the chat uh what exactly is knowledge on this problem you just mentioned when you when we just interpret Halo 2 subset argument as just custom gate so the problem is in the Halo 2 lookup arguments or assembling the lookup argument you have this verifier randomly and the knowledge promise of the lookup argument only holds if the random value that you use to build your ground product if I bring back Orioles vertical here

so you build this extra column and this extra column essentially if this column passes this constraint check you have a so-called a value multi subject but to go from multi-set to look up you actually need this gamut to do random inspectors if we were to fold these we actually need to also fold the gamut and so the output that we have no longer has this uniform distribution of the gamma so I'm not sure that the knowledge soundness proof of lookup or Halo 2 as it is out of the box applies to this

folded lookup column I do think it will work we just need to be careful about how we prove it you envision any way on which cross turns don't blow up with wire documentizations in concave It's A Hard Sell so someone has been

talking about like specific families of functions where the cross terms kind of uh uh goes to zero kind of very nicely or cancel out um I don't know much about those but essentially yes we could try to Define our gate equation specifically so that the crossings are very light don't know what that would look like um the other thing is there was this recent talk at the DK Summit about the Red Wedding where they managed to get rid of a bunch of columns because they are fully determined by the other columns and maybe some similar thinking can be applied here

also this is just one strategy for folding this is just applying the Nova strategy of let's make our equation homogeneous let's add a narrative to absorb the crossburns and we're good maybe there are other strategies in which um yeah which are more amenable to high degree days or wider circuits what about folding for a lattice based system work in progress oh I didn't wait maybe I'm misunderstanding what you're saying oh ZK are verified fully homework

so this we can already do right we can already write uh that performs operation and you prove it it's gonna be a pretty big circuit foreign but I can't hear you might not can you hear me now yeah yep

okay okay uh so it has been one hour and a half plus of session so uh I don't know how more questions like do you want to take also if there's anything left that you want to mention or explain uh in terms of things I wanted to bring up I think that's it for my site but it has to take a few more questions if there are any sure are there any more questions for the from the audience I see no one typing so I I will assume everything is clear

um so yeah thank you very much uh for for this session and for like explaining and guiding us through the paper in the protocol and allowing us to understand much better how it works uh I try to record this but I'm not in the best setup at all to do so so uh I hope that some of my teammates have recorded too and we can like put this somewhere so that anyone can like review it again then yeah just uh express our gratitude with you Nico and and like say thank you very much from the third time and from everyone and yeah I think we will wrap up here so thank you everyone

also for attending and hopefully we will continue with this learning sessions so yeah Nico uh Round of Applause and thank you very thank you very much for for everything uh we'll wrap up here guys so take care and talk to you soon