zkStudyClub: Sean Bowe on “Halo and Accumulation Schemes”

Transcript

hello so welcome everybody to this week's easy case study club we have Sean Bo who's gonna talk about halo and accumulation schemes hi Sean you want to take it away sure yeah okay so I'm Sean Bo I'm a engineer researcher at the electric coin company I know many of the people that are in here so it's nice to see you all again thanks for coming so yeah I'm a I'm an author of the halo paper along with Dara Hopwood and jet grid which for my coworkers they liked your coin company halo is a new way of doing recursive proof composition

our main objective was to avoid trusted setups but there's a lot of other theoretical consequences of the ideas that we came up with so this week i'm just going to be talking about halo and this related concept called an accumulation scheme that came out on a paper that just next week Dara hawkwood will be talking about all the other things in Halo that are more practical and specific to to the actual implementation stuff so circuit optimizations and some clever math and some elliptic curve cycles and lots of really cool fascinating stuff so very

excited to see that and hope to see some people at that as well so you forward to it yeah ok so just as I I'm not really sure what my audience was going to look like so this these slides are a little high level at times and sometimes but they're probably a little confusing so I really enjoy feedback and then anyone's free to interrupt and ask a question would be really great but to have conversations whenever there's issues or questions and I could even probably just exit and modify the slides like as we're doing this that if I see something pronounced so just as a quick primer on recursive proof composition notationally and conversationally i'm going to talk

about in terms of the standard the standard language the prover knows a witness who claims to know a witness and some instance such that if you run the witness in the instance or some arithmetic circuit the circuit equals one or some system of constraints are satisfied whatever it is that's encoding some computation the prover demonstrates this way by using some protocol that produces a proof some non interactive proof and the verifier takes this proof and the public inputs or the instance and checks that the proof is valid so in

in there's so many different proving systems that have different trade-offs with each other the one that's important for a recursive proof composition is primarily well there's there's both proofs sighs and there's also verification time so I'm sorry sorry-sorry trumped I'm showing your video isn't told right I didn't want it to be on all right that's okay okay cool all right yeah so the sort of snart's that are pairing based they use trusted setups have really good verification time it's constant time in at least in the circuit size and some of these other newer systems that don't

have a trusted setup with bulletproof sand and the stuff of boredom I'm going to talk about later with Halo have linear verification time in the circuit size by bulletproof for example has logarithmic proof size which is really useful really awesome can you clarify what circuit size means sure so circuit size it depends on the proving system it depends on the application but generally it most often refers to how many multiplication gates you need or in an arithmetic circuit that encodes your computation and for the purpose of this talk will it always

be multiplication it's I don't think I dive into what I kind of take for granted the size of the circuit whatever that means that it's I speak asymptotically throughout this entire thing so I don't really dive into like a specific proving system it variously for example there's it's very difficult to compare God 16 with sonic or sonic with plunk because they have different areas Asians from the the earth petition used by Sonic and Punk are covered in my talk so cool yeah that'll be a useful thing to touch man I

kind of go over the abstracts and all the slides that follow no thing it's definitely just the asymptotics or the important part or if you're if you want you can just assume that the size of the circuits that I'm our multiplication gates because that's usually that's kind of that's the most fair comparison I can think of this applicable broadly okay so recursive proof composition is when your circuit within the circuit it encodes the computations necessary to verify a proof using the same circuit so inside of our circuit here I've written verified because the verification routine which takes some old proof some previous proof and some public inputs

which are actually a witness for the outer circuit and it checks to see if the proof is correct and then maybe it does some other computation step whatever it is and what would this kind of instance of recursive proof composition is is something called incrementally verifiable computation ooh look what happened to my screen do you sell DLC black it's plug yeah disappeared out of nowhere yeah you list you selected something else but you're sharing I can't stop shelling and try shelling again try escape see escape doesn't work oh yeah shoes look thank you look yeah yeah try sharing a game

they should look now it's Whelan's fault I can move you off sharing should I do it can you do that yeah that might be boy yeah so I have a question in the mean time for the circuits for the each step of the circuit in the recursion does it imply that it's monotonically decreasing in the circuit size because it's like the next circuit must have been encoded in the previous one so it's like they're kind of like a subset of information is that fair oh you know yeah you're muted Shawn ah sorry yes sorry I was a little

distracted when he asked the question but I think I get the gist your question so the circuit this you see how this routine can you see my cursor by the way yes cool you see how this routine takes C maybe you shouldn't in this in this in this slide because it it raises your question which is isn't this circuit bigger than this circuit because this circuit encodes the description of it and that and the fact is that we don't actually encode a description a full description of the circuit inside of the circuit itself in practice we take it in as a public input somehow and we take a commitment to a polynomial that encodes

the circuit in some way or several polynomials that encode the circuit the verification key for example or whatever you want to call it that kicks brought in as a public input and the verification routine works using that so in fact the the goal is expressly that the circuit can reason about itself without increasing monotonically so it'll it will stay the same size we only have one circuit in this example but in your little arrow you have let's say D minus 2 comes after D minus 1 this is just like conceptually what's happening it's not like an actual thing in code where it's like constructs us some

circuit data structure from the previous one right so what I mean by the arrows is that there's some base proof on them on the right that was created the first proof that was created and we keep building proofs that take that for example the second proof we created would used would verify the base proof inside of the circuit and you get a new proof and we could keep doing this and so the errant what the arrow means is that it can attest to the correctness of a previous proof so PI D can attest to the correctness of PI D minus 1 which attests to the correctness of PI D minus 2 so inductively we demonstrate every proof is correct up to the base case but

with only a single proof at the end which is PI D so you don't have a circuit for each respective D ice D entry it's the same circuit each one's the same yes thank you the only thing that differs is which proof is being checked and what the public inputs are that are brought in for that proof that's being checked inside the circuit and also whatever other stuff you're doing in the computation step I just kind of take that to be whatever is going on it could be anything but it's not like it doesn't it's not like that circuit C somehow implicitly has a corresponding circuit for D minus 1 and D minus 2 right one

final general it doesn't so it might be helpful for me to just like remove see there's verifying key or something like that I don't know maybe add commitment to C or something like that it doesn't have to be the same circuit so as long as you can describe the second concisely that's is it at all correct to regard C as a function that takes itself or some other function as input it takes a encoding of itself as input yes

so that the encoding of itself would be this verification key so yeah okay if that's clear with everyone if if there's anything confusing about that let me know I can try to clarify so and you can you can actually have a verification key be variable you could you can have a commitment to it in a different protocol or something yeah so if we added multiple verification steps inside of the circuit for example so we're not just checking one previous proof or checking two then it sort of becomes a tree of proofs and so you can do this sort of distributed computation stuff

this is called proof carrying data or this one that's a formalization of this idea so the important thing to point out is that the recursive proof composition only works if the verification routine and you have to perform in the circuit or you have to express as a circuit is sublinear inside as something inside circuit or sub linear time routine in the actual size of the circuit that it checks which rules out immediately any any verification routine that needs to have a full description of the circuit because then it would it would never converge to a finite value and you would be able to do anything but fixed beta fixed step computation or composition in

order to do recursive proof compositions we need at some point what we need the verification routine to be asymptotically sub linear in the size of the circuit that it checks and as long as that's the case then it's some threshold whatever it is it will be possible to to obtain recursive proof composition and in either IV c or p CD whatever whatever it is you're trying to do so unfortunately that limits us and what snarks we can use because there's only there's only a few there's a pairing based snarks which use trusted set up have constant sized proofs and constant verification time and that's that's really great but of course it

requires pairings and trusted setups depending on what you're doing and what scenario you're in it requires maybe large pairing friendly curved cycles and if you're trying to get as much performance as you can get out of it so it's a little tricky you could of course use any any snark that has sub linear type verifiers for example a stark or a fractal which came out last year as well these are kind of heavy though so it would be nice if there was a way to do recursive proof composition in a discrete log setting without the trusted set up and without having to rely on pairings and things like that so that's what that's what halo is all about so just as a sort of

little detour I want to talk about polynomial interactive Oracle proofs or maybe the marlin paper calls a similar concept algebraic holographic something so the basic idea is that the protocol this is a protocol for proving proving proof of knowledge or an argument of knowledge where the prover sends in practice commitments to polynomials to the verifier and the verify responds with challenges and the prove ascends more commitments to different polynomials whatever it is whatever the protocol really defines these polynomials that is as is the important

bit but in the end the verifier asks the prover to open all the commitments that they sent at various different points depending on how the protocols design and then the verifier uses or uses those openings and any other information it needs to check that some identities hold and if those identities hold they're satisfied that the arguments correct of course we can turn this kind of a protocol into when it's when these challenges are publicly challenges we can transform this using a few mere heuristic into a non-interactive argument of knowledge and if you have a pre computation phase for example to encode what you're the values of your

circuit all the wires and how everything comes together a description of your circuit and anything else you need you can also is the privy to open those pre computed values that were computed by the verifier and proved very independently before the protocols ever were performed and the prover can evaluate those and the verifier doesn't need to evaluate those polynomials even if they know if they are they don't need to evaluate them they can just ask the preview to do it for them that's a a useful trick that allows it's for pre-processing which which it is an important aspect of things like plunk and some other protocols so two important points on this if our

polynomial commitments are additively homomorphic like group group theoretic based polynomial Twitter's usually are then we can perform a single opening proof a single polynomial commitment opening by opening a random linear combination of them in a various way so I'm not going to go into detail about how that how that's done it's not that important there's a different talk I think there's a previous study session I talked about pono and commitment schemes and stuff so I'll kind of punt a lot of this off and kind of assume those that are listening know a thing or two about polynomial commitments so the the point I'm trying to make is that the cost it

is dominated the cost of verifying a proof using a protocol that's the polynomial in a interactive Oracle proof protocol is dominated mostly by that polynomial commitment schemes opening verification routine the opening of the polynomial commitment so for example kzg 10 or cocktail commitments they use pairings and require trusted setup but they have a constant time verifier and constant proof size is just a group element which is really great and commitments are just one group element as well there's also these other polynomial commitments that we can build using a modification of the inner product argument that was presented by

Bootle and gratin all those other people I forget all the other authors of that and if you make a kind of a modification of this and you can turn make it zero knowledge and we actually describe it in detail in the halo paper a polynomial a univariate polynomial commitment scheme based on the inner product argument so that's in the Halo paper it has a linear time verifier in the degree of the polynomials and is like the degree and it has a logarithmic precise so that's that's really great but it's not good enough for recursion because of because of the linear time verifier which I'll get into in a second so let me just do a kind of a quick pass over

what this poem intuitive screen looks like this one that doesn't require trust is set up that's based on the inner product argument so we have a vector G of group elements and we have of length N and if we want to commit to a polynomial it's just a vector commitment scheme you commit to the coefficients that's it so P is a commitment we just do this Multi multi scalar multiplication here this is an inner product notation there are my attempt at one so yeah this is a simple vector commitment scheme and when the prover wants to prove that they're committed polynomial when that's evaluated at some point X that the verifier has asked them

to open it to the prove or claims it opens P of X opens at V opens to V and they they want to demonstrate that the inner product of the coefficients with the different powers of this value X is equal to V and then also the committed polynomial agrees was with the coefficients of that we use for the inner product and so the inner product argument is sort of a general case of this this kind of thing so we can make it a very specific variant of it and that's what we did in the Halo paper it's not very novel thing at all it just like in bullet proof there's there's blog two and of the with respect to the

degree of the polynomial there's a logarithmic number of rounds so the proof size is logarithmic there's these elements here which we'll see if in that cursor L and R which was sent in each round by the by the prover and these challenges you you won through UK which are chosen by the verifier as as the protocol progresses and so the verifier ends up checking this equation which only requires a logarithmic amount of effort once you assume that the verifier has access to this value G this value G of this group element takes a linear amount of work to create it's actually a linear

size a linear time multi scalar multiplication that computes it and it's computed as the inner product of this vector that has this kind of binary counting structure that emerges during the protocol so it's defined this vector s is defined by the challenges that are sampled by the verifier during that inner product argument protocol and so it's just a vector commitment to all these these weird as weirdly structured set of set of values so unfortunately computing GE requires linear time and requires a linear time multi scalar multiplication so we can't just play we can't wait we can't just build it we

can't just use this as our polynomial commitment scheme and build a start verifier inside of our circuit because it's linear time and we won't be able to converge to a finite size and we won't be able to get recursive proof composition just like I was explaining earlier so the value G instead of computing it we take advantage of the fact that the prover can supply it without actually computing it inside the circuit the prover can supply what they claim is G and then the circuit can proceed to perform the rest of the checks which like I said are logged this equation is logarithmic time in the circuit size

the circuit can proceed to just assume that that G is correct and then perform all the rest of the checks and then this value this G as well as the challenges that determine what G's should be computed as are taken as public inputs to the circuit and as a result the verifier of the of that circuit or of that proof is responsible for ensuring the G is correctly computed with respect to those challenges that come in as public inputs so if we try to apply this to our recursion or a recursive thing or recursive context we had this sort of verification routine as a complete

verification routine I maybe I should call it verified partial not instead of verified paths or fast but essentially it takes the old proof and as public inputs it takes the old G value that it that the bat circuit wasn't capable of evaluating or checking itself and then we need and then the prover just like before will witness what it claims to be the G value for the polynomial commitment scheme opening for the old proof so now we have two instances of checking if one of these G values if these G values are correct with corresponding with the challenges that are sampled so we can't just take two and then make those public inputs

because then the public inputs don't converge to a finite size and we can't get recursive proof composition that way either so we have to do something else so we take advantage of the fact that the structure this weird binary counting structure that emerges in this vector s that defines G it allows us to actually reinterpret G as a commitment to a polynomial just as if it were as if we had committed to a polynomial and not just any polynomial it's one of high degree is very complicated polynomial but it has a succinct description so we can evaluate it in logarithmic time at an arbitrary point so as a result what you could do is you could have the

prover provide what it claims is to be G and then open it up to a random point and if the opening matches with our expected opening then with high probability the commitment is correct because of the degree bound of the poem and commitments game so that's exactly what we'll do we'll as part of the proof verification we'll open the old G value at a random point and then of course the verifier can compute what they expect that G value to open to so we sort of integrate this opening just like I described earlier much earlier we can throw as many polynomial commitments as we want into our proving system at the end it's just

one polynomial commitment opening proof that needs to be performed because it's the additive homomorphism of the group so going back to where I was yes so the so the prover will be asked to open that G old value at a random point verifier checks the opening and as a result there's this G new value that the prover has to witness and we can take that geniune value as a public input and if the verifier of that proof checks that G new is correct then we know that G old was correct and inductively we know every proof in in this tree of proofs was correct by induction so kind of just

to recap what I just said again I guess the proof being verified inside the circuit takes the old G value and all the challenges that we use to compute that define it as public inputs the circuit checks the G old is correct by asking the proven to open it at a random point and in doing so and as part of the proving system whether it's plunk or Sonic or whatever you're doing as part of that you kind of shove G old into the opening and you pick a point X and you open it and if it agrees with what you'd expect it to open to then you know with high probability it's okay and what this effectively does is it transforms that

old yield check into a new instance G new along with the new challenges for the new poem and commitment opening group and then we take those challenges as public inputs mirroring what happened above here this is the exact same form just transformed into a new instance and outside the circuit the verifier of the recursive proof checks that the final Jean Valley is correct and if it is then corresponding with the challenges and if it is then we know inductively that every G value inside of the recursion was correct so this is essentially what we what we refer to as nested amortization we can rewrite this oh

sorry I should know a lot of her questions if anyone has a question yeah I had a question so if you had multiple G old proofs that you wanted to verify bidding and the PCD scheme how would that work combine them using that's if morphism yeah exactly so however many old G values you need to check the correspond with every proof you just add it to your to the list of things that the provers asked to open and you also evaluate it using this this polynomial here that the arrow points to and inside the circuit which is logarithmic so yep

that's that's more or less what's going on so what I was saying was that this is an instance of a broader concept that we refer to as nested amortization so I can actually rewrite this slide a little bit make it a little simpler but for the general theme of what's going on there's some are the proof that we're verifying inside the circuit take some public inputs X & Y we want to make sure that X really is f of Y for some function f whatever it is in the case of before it was the multi scalar multiplication but let's think abstract so some F of Y and we transform that and do a new instance for some X prime and y

prime we take those X Prime and Y prime as public inputs and then outside the circuit we check that X prime is really F of Y prime and we can we can keep doing this kind of collapsing procedure over and over and over throughout the recursion all the way up until the end the final verifier outside the circuit can just check this value and inductively and we know that everything was correct so this is what we were referred to as nested amortization but it's actually a there's a better way of looking at what what's going on here is something called an accumulation scheme so the observation that was made earlier this year in a paper called proof

carrying data from accumulation schemes is that what we came up with an halo is just an example of much more general concept from an accumulation scheme where we have a few different operations or a few different concepts first we have the accumulator so for example with the the polynomial commitments the discrete log base polynomial commitment scheme the accumulator is this G element along with those challenges so the accumulator is brought in as a public input to the circuit the accumulation step is the thing that happens inside the circuit that allows you to collapse multiple instances of these of the accumulator into one accumulator so we

just open G the current value of the accumulator using a polynomial commitment scheme we get a fresh G and fresh challenges and then we replace the current accumulator with those values that's essentially what we're doing and then at the end of the protocol outside the circuit we check that G is really actually a commitment to the correct polynomial using the challenges and we call that party a the decider so the deciding algorithm is the expensive algorithm but it's in particular it's the one that we don't put inside the circuit and by doing so this allows us to avoid the the blow up in the size of the circuit that would

result if we were to naively compute G inside the circuit does anyone have any questions please feel free to interrupt any time also there's some you might want to check a chat real quick question from a few slides ago hopefully you're able if your face I'm trying to hide my face because just at the very bottom there are some questions oh I can just ask my question um I think you kind of answered it Shawn I guess I was so use this term transform and I guess it's unclear to me whether or not

you're transforming it or if you're just taking like can you elaborate a little bit more yeah it's not really transformation right I don't know what the best word is for it but what what I'm doing is I'm trying to take multiple instances of something like this where I want to see is yield really correct with corresponding with this and turn it into one instance of that same problem so it's transform in that sense it could also be amortized or it could be there might be a better word I like I like compress compressing that's great right there

sorry just to clarify I mean so G is a group element and then these unions are coefficients to a polynomial and so the transform is basically what so you get like a group element and new coefficients but they're new coefficients on the same polynomial or so yeah well so G old is a group element that commits to a polynomial right a univariate commitment to a polynomial defined by these coefficients and it sounds to me like like that that tuple of G and use is itself a mono ATAR or

sending group or something like that but it just has that structure that's what that sounds like the you know accumulating a bunch of instant into a new thing at the same time it's definitely something creepy so okay so let me just I like compresses or I heard another one that was good but that's a that's a better instance of this what we're doing is they're essentially saying okay so I have multiple of these G olds I will I will have you prove to me that they're correct I hope by using a polynomial commitment scheme to open them which just takes a random linear combination

of them and opens them at some point I can compute very efficiently what it should open to and if it does then I know all those are correct however in order to check that proof I need to compute another instance of this G old using these new challenges so what I've done is I've taken multiple instances of this and compress them or merge them are combined them into one one check which I can then expose as a public input to the circuit sort of continually collapsing the process that needs to be performed my question is also on this slide oh yeah says that it says is it checks that

J old is correct by asking the prover to open G old at a random point X when it says the prove oh you mean like proving circuit or the actual proving the actual entity okay the proof is interactor does it well I mean when I say ask when it's not it's not interactive in that in its it's not really interactive it's just we're these circuits and usually how this works is that the prover can supply values without actually having to compute them inside the circuit the circuit assumes that the prover is being honest and and continues on with its checks but it needs to know at some

point someone needs to know whether the prover was honest when it's applied that diet because if the circuit didn't compute it then the prover could be lying so in that sense it's it's not that it's interactive it's that it's non-deterministic so the prover the circuit leverages the fact that the prover can compute this on its own outside of the circuit allowing the circuit to be sub in size and uses an argument that is efficient to compute inside the circuit to check to make sure that it's correct and this this process of compressing the checks continually throughout each cycle the recursion is exactly what allows the circuit to maintain the invariant that it is always it converges with finite

size so and then also that the public inputs don't grow in size it just it's always merged together okay so oh I have a question while we're here so suppose you're using this for a block train application say and you want to upgrade the circuit but your new circuit is larger think you can still do that provided that so so the cost of your proof will increase but it'll only increase wants when you increase the

circuit is that right hmm well how would you do it though like you could if you're gonna change the circuit you could just like take the recursive proof that you have at the boundary of the upgrade or the network upgrade or whatever you want to call it and then just like give it to everyone and have them check it and then use that that's a very good state that I'll test to this for another and then then you're only paying an extra cost per upgrade but no I don't know is a good point yeah okay cool so I wanted to show other accumulation schemes because this is one example of an accumulation scheme that allows us to actually get a compare this

is an example of an accumulation scheme that allows us this is what's in halo this allows us to get to use the discrete log based polynomial commitment scheme to build using sonic or plunk or whatever you want to build a to build recursive proof composition or proof carry data or whatever without needing a trusted set up so it's really great well there's there's a little bit more that you could do so for example if you are using kzg 10 commitments so you have some polynomial commitment P you have an opening proof Q you have an opening value V so so at some point Z that you evaluate your commitment it opens to V and you have some structured reference train and then

this is just what keys eg 10 commitments are if you need a refresher on this kind of stuff feel free to there's like I said there's other talks and other study club sessions that went into this sort of thing and I think this equations right I kind of just eyeballed it I'm not really a hundred percent sure but the verifier basically checks that this parent equation is satisfied now if there are two instances of a polynomial commitments game opening kind of like what we have when we're doing this collapsing procedure then what the verifier could do so for example I have this P and I have a P prime Q and Q

prime so there's there's two different openings and two different commitments the verifier could just sample random alpha once they've obtained P and P Prime and Q and Q Prime and then we can take a random linear combination of the values that are on the left-hand side here the g1 elements of the pairing and and the value on the other instance so first instance and then alpha times the second instance and the same thing with the left hand side of this side of the equation the equation check Q and Q Prime so we now we have this a and B the verifier can now check this pairing equation and if it does this it only performs two pairings but it's able to

check both of these polynomial in the scheme opening so this is a standard batch verification technique that's used in kata-kata commitments and this Maps exactly to what we're doing in accumulation schemes so we have an accumulator which is two g1 elements in our accumulation step we have a random out for that sampled and then we replace the accumulator with a random linear combination of the existing accumulator plus the check that we want to do and then the decider outside of the recursion checks to see if this if this pairing equation check is satisfied so you don't actually need to perform a pairing at all inside of the circuit which is really helpful for avoiding needing to

do really expensive circuits for like if you're actually using pairing based snarks with trusts and setups for performance reasons or whatever you're using them for this allows your circuit to be quite a bit smaller and depending on what you're doing it also allows you to maybe avoid having to do curb cycles with where both curves are appearing friendly because you can use this accumulation scheme for one side of a cycle for a curve that isn't pairing friendly and use this one for one that is and it just as an example it's something I think it it's not so much the cost of verifying the pairing in the circuit it's the complexity because if if you want to apply all of the

optimizations then it becomes very complex and hard to make sure you've done it all correctly it's a good point however this this this accumulation step thing it's so much faster than a pairing so like for example I think to Aztec people they're doing simulated or ESMA paper or whatever using hookup I would much rather just do this which is way more efficient than doing a gigantic pairing using simulated or again I take that that's ridiculous yeah so yeah I'll go ahead so so Shawn what you're describing here is really a

way of taking que que que si Jin cooks for K different polynomials and K different evaluation points and batch verifying them much more efficiently right right so the best verification technique that I'm describing in this is already very well known this is something that was probably the original paper I don't think so I don't think this was well it's aggregation rather than batch verification so so for batch verification well I'm just I'm just making an analogy to signatures so an aggregate signature scheme you can

basically combine the signatures into one which is what you're doing here as opposed to having lots of signatures and just having a way to to verify them more quickly you usually only really affect has so I guess this was well known in the sense that we knew that you could batch verify pairing equations but I don't think the applications the kcg was well known okay well hopefully as well no no actually I think this has applications to other things too like verifying shares and distributed key generation protocols where you have a bunch of polynomials in you verify a

bunch of shares on this form oh cool okay yeah so yeah it's one of these things where it's obvious after you see it and then you you're unsure whether it is actually every invention okay so like I was saying this this batch verification technique mat maps to the accumulation scheme or the nested amortization stuff directly so we can use it as another tool in our toolbox and finally to kind of wrap up for the day I wanted to talk about another accumulation scheme that exists in I don't know if it's fair to call it an

accumulation scheme with respect to the actual accumulation scheme paper because they're the formalisms might not match up there it might be a little bit orthogonal but it works similarly it's something that we put inside of the halo paper so in the halo paper we put sonic we use sonic on top of this polynomial in that scheme because we've done this but I think plug came out like days before we we published a liver opposed to halo publicly so there was too late for us to like mess around with that stuff but and we would have gladly had there not been like 80 papers that came out in September but so we use sonic we built sonic on top of our commitment scheme

poem and commitment scheme and it's on if you have to do the verifier need to compute this polynomial at some known points x and y this is polynomial s similar to what's done in my bullet proof so this s polynomial is public it describes the circuit but what instead what we do in Sonic is we have the verifier ask the prover to commit to that polynomial where Y is realized but X is still unknown so it's using the univariate commitment scheme commits to that and then the verifier asks the prover to open s and X and that gets them sx y assuming the prover was honest when they committed to s so in if if

this is a necessary step that when you're checking a sonic proof in addition to the polynomial commitment scheme and checking the G thing we also need to check that these s values are correct and it turns out that there's this idea of stems from the sonic paper where if we have two instances s1 and s2 where we the prover claims that they were commitments to this s polynomial with different Y values what we can do is we can collapse them into one one instance collapses another one of those words collapse compress whatever we can collapse these two instances of this problem into one basically the verifier samples a random value Z and then the proof of the prover is asked to commit

to the S polynomial with X realizes Z but with Y's filling with y unknown so we can do that with a univariate polynomial commitment scheme and then the prover opens s1 and s2 at Z which should agree with the openings of C at y 1 and y 2 and if C is correct then we know with high probability to s1 and s2 we're correct so to get things back into the original form that they were the verifier samples another random y3 and then ask the prover to commit to the s polynomial evaluated it what with X unknown but with Y evaluated at Y 3 and then the prover opens s3 at Z the same

point that C opens in Y 3 if s3 is correct then we know C was correct which means we know s 1 and s 2 are correct so now we have one instance s 3 is s 3 indeed a commitment to this polynomial is y 3 rather than two instances that we had before with s 1 and s 2 so we can go back to our accumulation scheme slide and just right here we can just write exactly what's happening I meant to actually add some lines in between where the verifier samples stuff which is just vh Amir or whatever but I forgot to do that but but this is accumulation skip a

step is exactly what I described on this side I think it probably does fit into the accumulation scheme formalism I can't see why it wouldn't the reason why it might not is because the accumulation scheme is really ok I have to live the paper it's certainly an it's certainly very similar but there might be some specific thing with the accumulation schemes that talks about starks and stuff like that and I don't know I have no idea so I think like it's interesting you can think of it say you know instead of just giving you a bunch of univariate s-- I give you write a bunch of univariate but encoded in this way as

different restrictions of the same bivariate is what you get so can you in this case when I give it to you like this accumulate / compress more efficiently than you do for general kzg univariate sand and I think the answer is yes right I think the work of either the prover or the Vera or probably the verifier in this third case is a little smaller than in the second case what's the second case o kz g you a bunch of unit variance compressed and

here you have a bunch of different restrictions of the bivariate yeah yep so i just looked up the definition of an accumulation scheme and they actually distinguish between the the basic definition and an accumulation scheme for a snack i think so the accumulation scheme paper mentions this third one not by describing it as an accumulation scheme but by describing it as a what they call it post-processing which i file i find to be really intuitive and

interesting idea because in halo we don't since we do this this third accumulation scheme we don't actually have to perform any pre-processing so we don't commit to polynomials that encode our circuit description which is an interesting it's interesting from a theoretical perspective it doesn't really pay off in terms or it may not really pay off in terms of performance depending on what you're doing but it certainly does want to use in Sainik the sonics very inefficient but maybe with plunk and other things it's not really that helpful i'm not sure cool well i mean i think it is still i don't know if anybody's really looked into it like say yeah you're in this forget maybe recursion for simplicity just you're doing a bunch of instances of the same circuit i'm not sure we can rule out

that like the sonic bivariate thing can to be used to you know further improve clong slash Marlon yeah something I was considering I don't know a few months ago was posting on the plunk telegram channel was this idea of where this bivariate pono meal s actually encodes all the univariate polynomials that you need in plunk to compute it for pre-processing they like all the select your polynomial commitments and so on and whenever you need to evaluate them or open them up at some points then

you can just use this technique at the same time and then bring it in as public inputs and do the collapsing thing over and over and over when you don't actually have to perform pre-processing and plunk either which is interesting from a theoretical perspective but well I mean maybe it's more efficient I don't know where you're calling it not doing just the pre-processing is this one s instead of a bunch of variants I don't know why you're calling it no it's so so when I say pre-processing I mean to say that this group element is computed before the protocol begins right but that's not the case when it comes to this s polynomial these these are computed as the protocol is ongoing and the verifier checks that they're correct

at the end hence why I think the accumulation scheme paper calls it post-processing so what my suggestion which I don't know how much of a theoretical or practical benefit it would be probably none but we allow all of the univariate polynomials that would otherwise have to come in as public inputs I mean maybe it can decrease the verification key sizer no but it is I don't understand why not to call it pre-processing right you're just encoding the pre-processed polynomials in one bivariate instead of like five you know I don't know what why not to

call it I don't understand why it's not pre-processing I guess it's not pre-processing because we're not committing to a bivariate we're committing to univariate using a specific way that we ended up using Oh mmm but that's needed for that specific proof so that this s commitment s2 is not helpful for any other proof in the recursion versus oh right oh right because the Y's have to be chosen by Fitch all right yeah well okay yeah but I don't know if it's enough of a distinction to matter but yeah there's one yeah but right okay but for that you need okay yeah maybe this is yeah there's a lot to there's a lot of

sides here yeah but but you can do that when you have a protocol where the verifier he actually knows s and actually computes at least once right right yeah it'll have to evaluate us at the end or something or maybe fold it into some other actually I don't know I I think the prover could you could combine this with pre-processing actually on the outside you don't actually bring in the pre-processed elements on the inside just the recursion but then you use the pre-processing on the outside to see if they is the commitments agree with each other or something like that maybe that's a way to do it I'm not sure yeah I'm just trying to to suggest I'm not

really sure if this is helpful but I'm just trying to suggest ways that maybe this style of an accumulation scheme could come in handy with clunk or with recursion may be reducing verification key size or whatever it might be able to do and I would really invite people to think about more accumulation schemes so I have a question about that can we think of post quantum accumulation schemes because the the the proof carrying days of the accumulation scheme paper has a section on post quantum security and the same idea works but obviously the schemes here and not as quantum secure because they're well in

sweet log in some sense like this third one doesn't have any it just as just information theoretic yeah right it just depends on whatever the polynomial scheme underlying it actually depends on so so so that depends on the commitment commitment scheme being at stiffly how a morphic does it no it doesn't it doesn't okay log we're um refinements in these two so when you say that we should those quantum like we're like the discrete one so this top accumulation scheme is the

discrete log based no trusted setup based on the inner product argument polynomial commitment scheme it's an accumulation scheme for that polynomial kaminsky and the second one here is for the cocktail commitments which is pairing plus trusted setup this third one is agnostic to the underlying commitments game and its properties so this third one might be helpful like for example in fractal I can imagine me like if you're doing something with fractal or whatever I don't know it starts and you and you want to do you don't really need it to be additively homomorphic

probably you can probably do probabilistic stuff to achieve so SoCal simulation can we use this to make fractal more efficient because I am sure things I think currently for the recursive proofs mentioned in the fractal paper they just rely on the basic the basic idea from BC tv-14 so if you combine that with an accumulation scheme how much does that help oh yeah okay so that's all I had in terms of

slides I'm not a good teacher so I was probably confusing I always skimmed over things nom at but I tried I tried so here's some reading material the the halo paper the accumulation of schemes paper I tossed in supersonic and Marlin because they have formalizations for things that are like polynomial IOPS I don't really know that much about those formalize it well I know and I know enough to be able to talk about them but I don't really care about formalizations like that but if you if you're interested check it out and then there's the fractal paper that we were referring to in case you I'm aware of that but besides that I would love to answer any

questions anyone has and go through the slides or whatever but I don't have any more material outside of that but thanks thank you for everyone for bearing with me and attending thank you cool I'll add those links I'm gonna be putting this on youtube so I can actually put the links to those papers as well anyone wants okay cool I could send you these slides I could actually I'll post these slides I can check it out that would be great yeah that's good can I ask just next week Dara is going to be giving on yes different it's so it's kind of half and half so I'm part

of it is how to optimize hallo so I'm part of it is constructing the elliptic curves so so for the elliptic curve part I actually talk about a more general case where you're constructing graphs of elliptic curves so we see one case as that it's a two cycle and I explained why you need to use because I have complex multiplication to get cycles but I also go into how we use and

endomorphism on the case optimize the operations in hello things like that awesome Thanks thanks Sean for their Leslie presentation thank you for your time hey so I'd like to make Sean talk some more but I guess how much time do you want to take beyond here yeah okay excellent okay yeah I think I'd like to build a better intuition on how you get kind of the new G from the old G I mean I think you had an example we at the beginning of the talk that you kind of skimmed through there but I feel like if

I had a more concrete example that would kind of solidify the abstract concept for me for me a little bit so it might help to explain where this structure comes from I guess I get away with not doing right I guess that's already in the bulletproof paper so yeah I recognize that you know all possible combinations of the use with their inverses I recognize that from the bulletproof paper I just okay I guess I kind of missed how you go from one step to the next really that's all okay so so in so in this adaptation of the bulletproof polynomial commitment scheme like I was

saying before commitments to polynomials are just commitments to the coefficients vector commitments to the coefficients so if our coefficient if our polynomial is defined like this then this is our commitment to that polynomial easy easy peasy now it turns out that and I can explain why but hopefully I don't need to but it turns out that in order to actually check this equation the verifier needs to compute this group element that's computed as this with this with s defined as this and you've seen this in the bulletproof spay / well that s this s vector can just be interpreted as coefficients of a

polynomial right this this G value is the same thing as a commitment to a polynomial just like what we did before here it's the same thing just with s as the coefficients and it turns out and again I can go into detail why that this committed this G value can be interpreted as a commitment to a polynomial that is has this succinct representation takes only a logarithmic a number of steps in order for me to evaluate it at a random point so let's say I have two of these G's and they're defined by by different s vectors because they were created with different challenges or whatever and I wanted to use the I wanted the prover to assist me

in determining whether those two are correct so what I can do is I can take a random linear combination of the two G's and then open it at a random point and I can I can compute what I expect the evaluation of it is now if either of those G's weren't correct they weren't commitments to their respective s vectors then with very high probability given a large enough field the opening argument of the new linear combination of the commitments would be would not open to the correct what either the argument would fail or would open to a different point or to a different value with very high probability so we know with high

probability or I shouldn't I should say the other way around but what if if it opens to the correct point then with high probability we know the original two G values were correct and of course opening a linear combination of the original G values using the polynomial commitment scheme necessarily requires us to go back to this equation but this time with a new vector s we have to compute this G and that's sort of what's happening in the accumulation scheme we're just we're collapsing the G in each step the the the G value in each step with a new fresh instance of G does that help her is there something missing in that description on slide 19 yeah can

you just explain why that and the second bullet point is true why oh um the reason why it's true is so it's just the structure of the s the a specter that makes this happen so basically it they're here actually I'm kind of prepared for this a little bit I have a little pad here we'll see if this works yeah we get to use it yeah so I don't know I don't really know what I'm doing here let's let's take an example of like

K is equal to 2 so we have you 1 inverse and you 2 inverse times G I guess I'll just do 1 a 1 index plus I think this is U 1 u 2 inverse to thanks for bearing with me so this is the structure of this G ailment yep depending on the

challenges you want to need to now we can rewrite this as opponent so so if we rewrote this as a polynomial we do like you you want inverse I can actually do that without having to rewrite it if we rewrite this as a polynomial commitment or sorry if we rewrite this as the polynomial that it represents is this commitment represents let's see if I can get rid of these what we're gonna end up seeing is this

sort of like self-reflection or I don't know what do you want to call it so what descends what this ended up being is [Music] like you inverse plus or sorry you 1 inverse plus u 1 X which is sort of if you pretended like there was no second challenge my semi explaining this right

babe I haven't explained this before so I don't know if it's it's helpful but yeah ok so if we look at like the equation ok it's the other way around so you that might be actually wrong I don't know it could be yeah that might be backwards or something in the paper but yeah so it just ends up being that that that pump that this describes it I could like sit here in bumble around until I figure out how the best way to describe it but I'd probably just waste everyone's time but yeah if you if you actually like if you wrote if you looked

at it and you tried to figure out like how do I describe this how do i efficiently like for example compute this multi scalar multiplication if all you can do is multiply by challenges you'd realize that you could do it like you realize that you could like break it apart into smaller and smaller pieces until all right you just break it into half multiple times gosh did that answer your question or did you have more to that question I don't think I have much more I guess maybe I would just close with like this little bit of feedback like it'd be really nice to have a concrete example that can kind of really drive home the wow factor of like wow you've compressed

all of these linear time checks that the verifier has to do into a single one at the end and I feel like right right now I'm kind of like missing that punch I mean I think there was a lot on the upstroke yeah yeah but that's like I'm not I'm not asking you to do anything more that's not a question that's more just like a comment first if you feel like following up then I'm happy to listen so thank you you know like I was saying when I first started to talk I really suck at visualizations so what I would really like to do if I could is to take like this diagram here and start putting G's and stuff in it so that you go oh I see what's going on but of course I'm seriously I'm gonna have to

need to hire someone to make graphics for me because I just can't sorry sorry I can't get you the wow factor but yeah oh good thanks thanks a lot I appreciate it yeah in the front any other questions in the group they're still like quite a few people here there's also a little bit of chatter in the to look at the check well anybody else is thinking cool oh I don't really have a strong

opinion like if you say we should actually say for the people watching on YouTube what you're talking about okay sure yeah so the question is like I'd be interested in to see a mini debate with Arielle and Zach if you guys are up to it so the question is is the halo orestes style recursion which one's better I think it depends on what you're doing like clearly aetherium the way aetherium is today it cannot handle a gigantic multi scalar multiplication to check a recursive proof I can handle a pairing and so that's kind of why you would probably want to do as textile recursion which is basically just this second accumulation scheme as far as I know plus like plucked up or something

yeah yeah the interesting question is can we just hear from Zach real quick I wouldn't mind my inference from Boniface oh so to me the interesting question is whether it's better to to do the pairing basically in every other steps so say you have a half pairing cycle is it better to do the pairing every other step or is it better to just use the discrete log scheme and then do the pairing at the end it's the the advantage of doing pairing at the end is that you end up with a shark so you're only relying on the pairing to get a one

verification and if you don't need that you can still do the decision on the accumulation scheme um yeah I think I think I might I might not have fully understood the question I'm like it I mean it depends on whether you care about you can - plus a set up because if you don't then yeah um yeah I mean I'm I'm not sure it's gonna be much better being because I think they've basically made they just don't get by very different cases in the trade-offs face fool you have the lowest recursion bound possible there it's it's pretty clear the hell is going to give you the best the best relation that my quite a wide margin the reason why we're using

is what's the reason why we're using like kind of dislike brute force profession and clip ups is twofold one of them is the the absolute need for a fully assisting verifier the other one is it's quite as if they're in specific because we're very restricted in the types of elliptic curves that we can that we can support specifically there are - there's the EMT but one of the spheres phosphate one and say if he wants just for repression on both curves then it's difficult you can't directly use a half-time from the cycle um BLS for a one because the field the prime field silently for the semi not and there's also the additional complication

that the the Trifield order of the BLS curve it has is it's not like it doesn't have a high density so if that was the the native modulus you'll feel realistic then constructing forming the polynomial everything to take required to make a proof would be challenging so sorry say that again I think I missed something you said that so it's just that so imagine if you I guess I guess it's actually more academic because there's no way to eat I mean there's no there's not it's not possible to great kind of a cycle where you have a curve where the group order is equal to the Trifield characteristic of the BLS for fair one care but even though I could creating crystal that code would be very very

challenging because you will be able to use base to your fifties because at the UM eventual value about prime number would take right I mean the the half pairing cycles you can get both curves of iiterest but obviously yeah and that's that's kind of the crux I mean if you you know if we if we didn't mind a time verifier even because the recursion is quite low like the B be calling linear into Paris linear time isn't particularly fair because it can take a convex second is break it down as multiple recursive parts that have a smaller size but even even in that context you can't really

you can't do you can't do very many exponentiation in a small contract I mean what is the prospect of getting Assyrian to support more curves I can't speak the ethereal and addition I can speak like I can just like give my personal thoughts another which is um is that it's going to mean it's not it's not impossible but it is challenging because I mean we have to remember that the actual individuals that will be required to actually make it maintain like support in curves the implementers of the etherium nodes get parity and

others and they don't have in-house critic of expertise so the the barriers in adopting eCos is extremely high because not only do you have to supply the libraries that implement the curve on a variety of languages but they have to be kind of industry proven isn't widely used elsewhere in industry like so that so that they can be confident that there aren't any bugs yeah they will be called on to face I mean I guess ECC we kind of think nothing of generating new curbs which is a bit unusual yeah I can see why that doesn't work for you I actually did get into is

the if Tyrion 2.0 uses villas one you want to verify deposits that are related to his to own if one so that helped a lot to push 381 into each one and there was a previous efforts by the metal apps people where they tried to get any AP that would support any carries up to a certain side of many different kinds I'd be less variables and amenity curves and so on and that one eventually did not

get enough buy-in from the core Adams I mean from for good reasons because like like Zack said they don't have this desire and expertise to maintain such a huge to graphic memory but they did they did agree to answer this ad for a specific curve after some more yeah I think that the general IP I am I can't remember its number but I have looked at it there was a limit on the calf size which would exclude half buying cycles because you want a half firing cycle to

be about 384 bits I think it was limited to 256 or something I'm actually quite keen on the half pairing cycles because he you don't have to rely on the pairing for the accumulation step but it's useful to have it at the end so yeah I have a

question on actually because um this might just be buying macro knowledge but if even if you have a half break for any cycle because of the the non kind can you sort of a linear sum computation that like somebody needs to do either either in the in the in the pen for any circuit or the Peregrine yeah but it seems like I mean if you if you can afford if you can afford the linear time verifier then the form of the Onyx things and your cycle is is it will be should truly be quite a bit less efficient because because it's very friendly but obviously you have to take into account that the number field sieve attacks and use a bigger a bigger curve and then that curve that curves order has to also be flipped in the non going

from D curve so that you can have a cycle so instead of being able to use a geography 650 use detective 384-bit go yep like do you think that's it it depends very much on how fast the the plonk based halos verify it and and we don't know yet so so obviously it's a little different with the theory with us because we can do batch verification between transactions so whenever we have like a transaction that we need to do

this linear time verifier we can combine it obviously with all the other checks so so there we if if you're even supported those kinds of batch verification things across transactions maybe maybe we wouldn't even need to be consensus critical change and I just need to be in the code extra changes or that kind of thing but I think that that would make the multi scalar multiplications of the kind you have to do for these discrete log based accumulation schemes a little more attractive in the etherion context of course the circuit that's on the side that's the screen log base it doesn't have to grow it just has to be able to well it doesn't have to grow very

quickly anyway it just has to be able to get you around the cycle so that that seems like it seems like in some kind of test it should be reasonable to expect the performance to be good enough yeah I think assuming a game were to support those kinds of batching and this is an underappreciated point and and I hadn't actually appreciated until Sean pointed out the with Halo you you effectively have to proving systems interleaved but they don't have to be the same size circuit so you could for example if you need a large circuit you just put that

on one of the the curves and the the other curve is own the circuit is only logarithmic and the size of the large circuit so you can end up with sort of nice asymptotics yeah I have a question about the aggregation would it be fair to say that this could be implemented at the smart contract layer where you have some sort of aggregator helper a small contract and then you kind of split the gas fees somehow I I don't know specifically how theorem works it was

that kind of thing but it seems in principle like there's some way to do that because obviously this there's there's batch verification which which the node can do but then there's also this coordinated aggregation that can be performed the accumulation scheme can be used across transactions so as long as someone's willing to pay the computational cost they can get transactions to share the same multi scalar multiplication it's a matter but I mean it it's easy to do batch verification across all transactions in a block it's slightly more difficult in the man pool because I mean you have to deal with denial of service attacks if

an attacker could submit a bunch of transactions and you don't you can't necessarily distinguish which ones were submitted by the attacker on which bionis parties see you end up having to verify all of them individually in the West case hey here's a weird idea what if what if you had the month the what if you have a protocol that uses like Halo or whatever on top of it Syrian you the smart contract assumes that the G that's provided is correct and there's like a bounty on whenever you like update the contract state or whatever there there's some not a bounty like a bond or

whatever you want to call it where you lose your bond if you supply a G that was wrong so then this nonsense right could be used to check it so similar to optimistic roll-up that kind of thing yeah yeah pretty much optimistic rule applies I mean it doesn't even have to be optimistic like you could off chain like aggregate a bunch of proofs and then or collect a bunch of proofs do the aggregation and then submit them on chain all at the same time as one batch right I think even without aggregation that I mean it's gonna it will be challenging without some simple article support because you're slamming to the log S

limit by doing I think like a thousand scalar multiplications right now so so even even if they're like Asian balanced a to you she's our the like to to the thousand I mean that's that's much a few templates yes yes I guess there's always gonna be like this yeah it's gonna be a some summer some bound but I wish that we're that's gonna be event we can hammer their loss practical well you like divide this computation into yeah yes is crazy expensive so you have to have entire blocks yeah I mean as I understand the current multi X dozen do like hip and

your fancy explanation yeah but it does the gas price take into account the fact that you can heavily optimized with a clever algorithm no not at all I mean I mean II coming you could give you if you don't think I mean that you can get and I got a straight-up a libero fire ma will be in flight probably fast enough to be practical is fine with the effort the colors just um okay I guess it gets back to the question of actually getting those kinds of equations into into a thirty influence you know so if so if it's no one turns up with that crazy optimized Intel assembly of implementation of dividends it to get back to take one look at and go I can't maintain this so there is a team the

supranational team that's building kind of like assembly optimized implementations of these things and they're doing formal verification I guess when you have the two combined no so you're right so like right now they're focusing on x86 but arm is in the yeah what's really interesting but yeah we take that crunch

fsync formal vacations it can't get more line so we're at the half hour mark I think at least for the recording I'm gonna wrap it up here but we can actually keep speaking afterwards but I want to say a big thank you to Shawn for doing the presentation and thanks to everybody who kind of joined in and helped to refine and work with this presentation thanks Shawn I don't know if you're still here absolutely do