zkStudyClub: Halo Infinite with Ben Fisch (Stanford)

Transcript

so i think this is the first zk study club of 2021 welcome everybody uh today we're going to be learning about halo infinite with ben fish and i know justin who's also a co-author is and ariel i don't know if ariel's here but justin's also on the call to answer some questions so take it away ben thank you anna um yes so as anna said i'll be presenting our recent paper um halo infiniti uh it's called titled recursive snarks from any additive polynomial commitment scheme um i am a graduate student at stanford university and my co-authors on this paper are

dan bonnett justin drake and ariel gabizon so let's get started so um probably i think based on the attendance of this meeting most of you already know what a polynomial commitment scheme is but i will still go through the basics so um and and i might move quickly through some things that i assume most people here know so if you aren't familiar with it then please stop to slow me down so a polynomial commitment scheme at a very high level is a interactive protocol that enables one party

to send a small value called a commitment to a polynomial of degree at most d and later send proofs or potentially interactive proofs that prove a claim that the committed polynomial evaluates at a certain point z to a certain value y and this claim is also uh simultaneously showing that the that the polynomial is bounded by this degree d and a polynomial commitment scheme is called succinct if the proof that is sent later or the community side of the communication during the proof is small and by small

we mean uh sublinear in d um but there's various uh ways of characterizing that it could be poly logarithmic obviously poly logarithmic is better than say square root or due to the epsilon but cesignus in general just means sublinear and efficient means that the proof is fast to check again we mean fast in terms of sublinear complexity in d so a bit more formally the syntax that we'll be using to describe a polynomial commitment scheme is in first in terms of

three algorithms that you always see as part of any commitment scheme there's a setup that establishes public parameters of the scheme there's an algorithm called commit which takes in this polynomial and outputs the commitment c it also outputs a second value called open sometimes referred to as the commitment hint some schemes don't have a hint so the second output will not be anything but other schemes will have a hint particularly when the scheme is hiding and the hint is something that is required to verify that a commitment

is correct when presented with the committed polynomial f so there's a verify algorithm that takes in the polynomial that was committed and this hint and the commitment and either rejects or accepts when we write b equals one that indicates acceptance when we write b equals zero that indicates rejection what makes this scheme different from a standard commitment scheme is the interactive protocol eval the the protocol eval may also be non-interactive in which case we call it a non-interactive polynomial commitment scheme the interactive protocol is informally a protocol

that enables the prover to attest to the fact that it knows the polynomial f that was committed and f evaluates at some point z to the value y the formal security properties are one that the commitment scheme should be binding as a normal commitment scheme meaning that it should be computationally and feasible for an adversary to produce given a to produce a commitment and two distinct values f1 and f2 and openings open one and open 2 that verify accepts so given a commitment there's a unique

way to open it as long as you're a computationally bounded adversary the interactive protocol is an argument of knowledge which is a formalization of the uh the intuitive security uh definition i gave you before in essence the only way to succeed in this protocol is if the approver does know the polynomial f um such that uh and an opening such that uh verify um of f open and c is equal to one and f of z is equal to y great so we can also talk about hiding

or zero-knowledge polynomial commitment schemes hiding refers to the fact that the commitment itself is hiding um which roughly says that from the commitment c you have no information about what the polynomial is and zero knowledge refers to the fact that the interactive protocol is a zero knowledge argument of knowledge meaning it conveys the fact that the prover knows this polynomial but it doesn't leak any information about that polynomial other than the fact that f of z is equal to y another property of a polynomial commitment scheme

that is important for this work um and it hasn't been defined precisely in the literature before so i'm only going to define it now so that it's clear what i mean for the rest of this talk is that of an additive polynomial commitment scheme so it's always possible to define an addition operation where we define an addition over commitments such that if we take the this linear combination of two commitments a times c1 plus b times c2 then it satisfies the property that if

c1 opens to f1 and c2 opens to f2 then c opens to af1 plus bf2 now the reason why i say it's always possible to define this there's nothing special about the ability to define this addition operation is that by default you could simply define this to be formal addition so the representation of the of the commitment could literally be the concatenation of c1 and c2 with the coefficients a and b and in order to open it you would just open c1 and c2 separately and to f1 and f2 and that would be a valid opening of the

commitment to af1 plus bf2 now that wouldn't necessarily satisfy zero knowledge but uh but but but let's not get to that so um i will say that an additivity um is non-trivial uh there is some way of defining [Music] sorry did someone have a question i think someone just joined with a bit of background noise oh got it great okay so this additive uh property of the polynomial commitment scheme is

non-trivial when the addition operation is compressing um otherwise the formal addition is always possible right so uh another way of saying this is that if we look at the additive group of commitments um of of of the commitments under this addition operation then it has a polynomial bounded size so intuitively when we add uh c1 and c2 together or take linear combinations of them the the commitment c that we get uh is smaller than just the concatenation of c1 and c2

so it's losing information now next i wanted to find something that is a slight generalization of what additivity enables us to do so in an additive pcs the commitment c which is defined as a times c1 plus b times c2 is a succinct commitment to af1 plus bf2 um and as i said uh when it's a non-trivial additivity property and when i refer to the succinctness of adding two commitments i'm referring to the fact that it's that is compressing that the sum of two commitments is

smaller in size than the individual input commitments then the sorry then the combined size of the input commitments so more generally we can define a protocol which may be possible even when the polynomial improvement scheme is not non-trivially additive that operates like this it's an interactive protocol where the prover knows the openings and the polynomials that were committed and both the prover and the verifier have the the public input c1 c2 a and b and the output um to the public output is some commitment c

star and the private output to the prover is some opening open star such that this c star is a commitment to the linear combination af1 plus pdf2 so when the pcs is added then linear combination scheme is simply to take addition using the addition operation over the commitment group but more generally we could have a different protocol that does just this clarification um a and b are arbitrary they don't have to be random is that right correct yeah okay thanks so how do we define this security

property properties what do we want from this linear combination scheme well what we want is that any evaluation on c star is effectively the same as doing an evaluation on c so any evaluation on c star is an argument of knowledge for openings of c star and for c equals a c one plus b c two to the same f so when the scheme is additive we it it uh the linear combination scheme can simply just be outputting c which is ac1 plus bc2 then of course it this security property is trivially satisfied but more generally maybe we could output a different c

star and the property that we want is that when we run the eval on c star instead of c for the purpose of the fact that c star is succinct and c is not succinct then the property we want is that that we still this is still an argument of knowledge for uh for for c itself so we extract openings of both c star and c to the same polynomial f any questions on that great so we call linear combination scheme efficient if the verifier is sublinear in the degree in the maximum degree of the two

polynomials and i define this just for simplicity in the slides as having two polynomials as inputs but of course we could have l polynomials as inputs and l coefficients so there are non-additive pcs constructions where there is not a way of defining a sustained edition operation but there exists efficient and secure linear combination protocols uh with the succinct output um and one example of that is the fri based pcs now um let me clarify a little bit more that

it's actually and i don't i don't have this in the slide but uh there is a generic linear combination scheme that always worked it's just also not a very interesting one which is to output a fresh commitment to the linearly combined polynomials and and and uh modify the definition of the eval protocol so that or or actually within the linear combination scheme itself just open all the all the input polynomial all the input polynomials to this game and the upper polynomial to show that um that they are equivalent in fact you know that would uh that would trivially satisfy the definition of a

linear combination scheme um but it wouldn't be very it's not very interesting it's generic and so a linear combination scheme is interesting when the efficiency of the verifier in in in this step here um basically in verifying uh the output c star should be much more efficient than uh than that generic protocol which would just run an eval on the inputs and the outputs um len combine is an interactive protocol in general is that right correct okay yeah so for the purpose of uh this paper we

restrict it to be a public coin interactive protocol but the most general way to define it would be as an arbitrary interactive protocol and we strike it to public coins simply so that we can do fiat chamier okay so the last concept i want to introduce before stating a summary of what the results are are recursive proofs so proof carrying data is actually more general than one described here but this is proof carrying data for something called a path distributed computation um where there are a distributed set of of nodes and each

is going to perform this local computation of this function f and f is taking two inputs one is the output of the previous node in the path uh that's going to be x1 or x2 and then the other one is going to be what i'm going to call a local input so in this case in this case the second node in the path receives the output of the first node in the path x1 and also receives a local input y1 and then outputs x2 so every node is passing along x2 to the next node the next node doesn't receive doesn't receive or see the local input

so in a proof comparing data scheme every node also has the ability to pass a proof to the next node and the ith proof is attesting to at a high level description of what it's doing is that it's attesting to the correctness of the local computation and recursively to the correctness of all local computations along the path preceding it so a bit more precisely it is proving a claim that there exists this sequence of values x 1 through x i minus 1 and y 0 through y i minus 2

such that the local computation is always consistent f of x j y j is equal to x j plus 1 for all j less than i now this is interesting when the cost to prove or verify the proof is independent of the depth i okay so the work that the third node has to do is um and the fourth one has to do et cetera they're they're roughly the same they're independent of of the of the depth even if this depth grows very very large the work is uh is independent of the depth and ideally proportional to the complexity of the local computation

that's being performed and one more important thing to note is that uh every node should be able to compute this proof without having seen any of the preceding inputs xi's or the local inputs it only receives this proof so this is also called incrementally verifiable computation in the setting when all proofs are computed by a single stateful prover and the distinction is really just that the

um the the prover can retain some private state that is not considered part of the proofs that are being passed along and at every step of the computation it outputs an incremental proof um that can uh it's a proof of the same exact claim that we stated on the previous slide um the only difference is that it is uh that the the that the prover that is computing it can can maintain state across across this process the the definitions of pcd that i've seen allow arbitrary graphs yes yes so

as i said sorry but i'll say it again at the beginning here this is a simplified presentation of pcd for path distributed computation but you're absolutely right that pcd more generally refers to uh you know any it could refer to any dag structure any directed acyclic graph structure thank you sorry i just missed that yeah no worries at all yeah so i just want to point out that ivc um implies pcd also ivc is usually talked about uh i'm i may be wrong on this but i've only seen ibc talked about in terms of

like a path distributed computation rather than a rather than a dag but um to me that doesn't seem like the fundamental difference the fundamental difference is really just uh that it's not a distributed computation and there's like a single prover that's that's outputting incremental proofs um but in any case uh obviously implies pcd um with an efficiency loss by just considering the the local state of the prover as part of the proof right so um the first node can always take its state and pass it to the next uh to the next node the reason why there might be an

efficiency loss is that this state might be much larger than the proof and especially when we when we're using succinct proofs that are sublinear in the size of the local computation being done and the proof might might be much smaller than the state so ivc does imply the possibility of doing pcd but there could be an efficiency loss in the size of the proof as well as the complexity of producing a proof but it would still if you have ivc would still be possible to produce pcd where you have this property that the cost to prove and verify is independent of the depth it occurs to me that that we might be

able to disentangle the the single prover versus graph things by talking about um single proof uh sorry um linear ivc and graph ivc and then linear pcd and graph pcd and that would disentangle the two axes along which yes yes that's a good point yes okay so the results uh i'll state now and formally so we can achieve ivc from any polynomial commitment scheme that has

an efficient linear combination scheme and the proofs will inherit the uh and what i mean by a so remember efficiency i don't remember if i define this on the linear combination slide but efficiency similar to the efficiency of a pcs means that the verifier in the interactive linear combination protocol is sublinear in the maximum degree i i think i did define that it's the sublinear and the maximum degree of the of the polynomials that are committed so um proofs the proofs um in the resulting ibc

protocol inherit the the same security and efficiency as the pcs on polynomials of degree uh roughly proportional to the size of the the local predicate that's being computed plus the size of the linear combination verifier and this is a generalization of kind of the theorem behind the halo protocol which was shown specifically for or the first version of it was shown specifically for um bulletproofs as the polynomial clement scheme and a particular interactive oracle proof so if the pcs is additive

then we can achieve pcd with the same efficiency and remember we can always achieve pcd from ibc but there's an efficiency loss so the uh the interesting thing is that when the scheme is additive then we can achieve pcd with with these efficiency characteristics so one thing that we could one thing that we could say in particular is that we get an fri based halo because fri while it's not additive it it has an efficient linear combination scheme really so i could just one you'd only get ivc from it so this is a really

important distinction in this paper you haven't mentioned so uh so you cannot so as i said you can always as i explained on uh on the previous slide uh which we can kind of go back to is that whenever you have ivc that is you that that that trivially gives you pcd because the prover can always pass its uh local state as part of the proof it's just that the size of the proof um may not be sublinear in the size of the local computation or the linear combined verifier it may be it may be linear in the size of the local computation plus the linear

combined verifier but as long as we can get ivc then as i was explaining here um each node you can turn that into a pcd by having each node simply pass its uh its local state along to the next node uh does that make sense sure so there is a distinction between so yes the efficiency of pcd that we get from additive schemes like bulletproofs or kcg or dark or dory or uh you know so many um schemes out there and um perhaps so many more to come

is uh is more efficient than what we get from non-additives uh ones like fry um but but this is kind of a neat observation that that you do at least get ibc and then you also can use that for for pcd even from fri to so in practice say for fry um stop me if you're going to cover this later in the presentation but in in practice what are the relative sizes of the um uh the state and the proof at each step yeah so um that i i mean so when you use it when you do this with

with fry then um it will be at least as good as so i haven't so one of the things that i have to mention is that like the paper kind of states this idea but uh um getting concrete uh numbers for fry uh is kind of ongoing work so i don't really have concrete numbers for that okay but but i would say that uh so i want to point out that because fry is already uh an efficient already an efficient pcs like we already knew that we could we can do ivc from frye um it's just that that this uh gives you a halo like protocol which improves on on what's currently uh possible with fry so

um it will be at least as good as fractal right it's like a strict improvement on fractal because it it it shrinks the recursive circuit um it uses the same idea that was introduced in halo where in the in the recursive step you you don't need to run the the polynomial commitment scheme verifier you only need to run the verifier for this linear combination or what actually you're going to run a verifier for an aggregation scheme that i'll define next and we're showing that you can build aggregation schemes from from from linear combination schemes so the point is that you shrink the size of the recursive circuit and delay the verification of a more

expensive step until the last um step in the ivc and uh and so it would be a strict improvement on fractal but i haven't really gotten the concretes down yet like i'll i'll kind of broad stroke well hang on but so wouldn't it be the case that fractal is in terms of a pcd is more it will be more efficient asymptotically uh because you have to pass something smaller oh sorry i didn't quite understand as you're saying so for pcd fractal will be asymptotically more efficient for pcd fractal would be asymptotically more efficient i don't think that's correct because uh essentially what we're doing is we're

taking we're building on the way that fractal works yep so this is this is this so there's a really important distinction that this this public private accumulation scheme which i hope we'll get to that determines this difference but fractal is the other way around from what you're doing with fry here it's like halos and uh uh and kcg accumulation is isn't the public private accumulation isn't that the more recent paper that oh own it no confusing the the two papers but yeah um yes you're right so so what does the um linear combination verifier

have to do at a high level for fri yeah for fri forever i the linear combination uh verifier is verifying a proof of proximity of two vector commitments and so it's cheaper to prove that two vector commitments are have have a close distance and to prove that a vector commitment is close to an rs codeword okay yeah i got it so it's it's asymptotically like a log d factor savings yeah okay answer my question right

cool okay um so just to go back to the other question so um yeah so i would have thought that the fractal has a a polyglot sized pcd a polylog in the size of the circuit but but but you're right yeah the flight doesn't well your pcb for fry doesn't but your ovc does no that's actually uh so that's it's actually not correct because so i'm stating this result very generally here so it's not always possible to achieve pcd when the when the verifier of the

polynomial commitment scheme is for example linear and not efficient um and the what the way to interpret the result here is to say that if the scheme is additive then you do get pcd with this efficiency even for schemes like bulletproofs where the verifier is linear we already know that we already know that for schemes like fri when the verifier is sublinear then we can anyways do pcd already we know that and so in such cases like fri we get an improvement to strict improvement on the way that we currently do pct remember so pcd is possible with fry because the verifier of the polynomial scheme is poly lag and so what i'm describing here is that

by by using the halo paradigm we actually improve that so that the recursive uh the uh the recursive circuit will be smaller the recursive circuits smaller as long as the state you pass is bigger right so if for ibc it would be great the recursive thing will be much smaller but for pcd we still have to pass this big state where you for fractal uh okay so um i see um right right i think that's

let me think about that for a second yes okay i see i see what you're saying yes right so uh right i guess you're right so your point is that in in in right so in order to in order to do pcd with um a small proof being passed along that you actually have to um right so you can't do private aggregation so that yeah sorry that is correct thank you that's a good point so it gives an improvement on fractal for ibc um and perhaps i mean depending on depending on what you care about then it can it may also give an improvement for pcd um but the the the gains for pcd are not exactly clear

because you're right that in order to um apply this strategy for the pcd version um with fri then uh then then you'd have to pass this larger state that's correct thank you i mean i mean i guess it depends concretely how large the state and and how about your second so well it's going to be proportional to the size of f it's going to be the size of the witness yeah and the witness is typically a linear in the size of the second it's almost yeah for almost all arithmetizations yes yeah

good yeah so it it it probably gives more um yeah it gives it gives a clear advantage over i guess fractal uh if you're using fractal for ivc but but it's not clear um what the gain is for pcd um it's i guess somewhat incomparable good points thank you okay so uh the uh some other results are that there's a generic compiler from um and m spanning additive pcs to hiding or zero knowledge pcs the way that we define m spanning is that the linear span of commitments to uh the first m

nomials uh includes the entire commitment group i'm not going to go into that one in this talk um just pointing it out and um then two other results that that are stated along the way to to to kind of showing this result about ivc or pcd is that one generic public aggregation is possible for any additive pcs and i'll define public aggregation and then generic private aggregation is possible for any pcs with an efficient linear combination scheme uh before you go on so my impression was

that m spanning was um basically just a technical requirement that in practice you have for almost any yeah every useful pcs yeah i couldn't come up with an example of a additive pcs that wasn't m spanning but well i guess i didn't really try to construct a counter example so more accurately yeah all the ones that we use today that um are also m spanning um but this was like a technical requirement in order in order to prove a general result yeah i would have thought that maybe dark would be something which doesn't quite fit this mold

but there's other reasons why it's not generic but yeah it's dark additive i don't think it is so dark is kind of bounded additive uh oh right yeah yeah and i mean it turns out this does work it it it does work for dark and um but um and and dark is m spanning um in fact it's um i mean if you look at the just the the group generated i mean the group has a generator so um so uh i mean it's all contained within um a cyclic group so uh it is actually

unspending um but it is also a bounded additive that's another technicality that we kind of discussed in the paper that some of the general results are don't fully carry over to bounded additive the for zero knowledge we do but not for uh for like public aggregation for additive pcs uh it does translate to to to bounded it for dark but there's uh some technicalities that uh don't fully uh kind of go over in the paper actually that's kind of the next step is to is to update the paper so i can say something a little bit more more general to incorporate bounded added for for public aggregation yeah so um

additivity properties of various pcs schemes um bulletproof dory kcg they're all additive dark is bounded additive fry is not additive they all have a linear combination schemes that consist of one commitment i call them sizeoptimal because they're the size of the commitment is just like the size of a fresh commitment to a polynomial of that degree and um the savings for uh so okay so this lcs amortization is like the um how efficient it is to

uh run the linear combination scheme and open linear commitment as compared to the generic protocol of like opening each common individually and so for bulletproof story dark and kcg you get one overall amortization if you have l commitments in the in the linear combination um for fry uh it's like one over l plus one over over mega log t and one of the reasons for that is that the complexity you save a log factor in the complexity for the linear combination scheme with fri but the uh the linear combination scheme

verify itself still has has log complexity whereas in the other linear combination schemes it's constant independent of d and so the savings is greater so defining private aggregation given a commitment to a polynomial f1 and a commandment to a polynomial f2 this generalizes to to a longer list of commitments but it's easier to present for two in the slides then there is a uh and points x1 y1 and x2 y2 there is a public coin interactive protocol

that um that takes in these two tuples as public inputs and the provers private inputs are the polynomials and their openings and it outputs an aggregate tuple uh c star x star and y star and the private output to the to the approver is a is an opening open start for for c-star and to a polynomial f-star and the security property formally is that an email running an eval on x star and y star satisfies the security property of running eval for both

c1 x1 y1 and c2 x2 y2 so by running an eval on c-star externa and star that gives us an argument of knowledge for openings to c1 and c2 to panels f1 and f2 such that f1 of x1 is equal to y1 and f2 of x2 is equal to y2 uh so we call this aggregation because we're we're we're taking these um these input tuples and we're aggregating them into this aggregate tuple such that the task of um verifying or proving the input tuples is reduced both of them together is reduced to the task of proving and verifying just

this one aggregate tuple any questions on that okay stop me anytime so we only tweak this slightly to define public aggregation where the uh the the inputs are also proofs for the input tuples and then uh it's only really interesting to define this as a non-interactive protocol but then there's um then there is a then there is a a non-interactive protocol um aggregate that takes in the uh the input tuples and the proofs

and it outputs the aggregate tuple just as before but an important difference is that the aggregate protocol does not take it's not a uh it doesn't um it it there's no private uh witness so it's not really an interactive protocol between approver and verifier where the approver has a private witness um there is a uh yeah there is all the inputs are common to uh to both parties so if you were to define this interactive protocol it would only be uh for the purpose of uh of one party being

more efficient than the other and then the security property is the same running an eval on this output aggregate tuple c star x or y star satisfies the security property of eval for both c1 x1 y1 and c2 x2 y2 so the main difference between public aggregation and private aggregation is that uh in private aggregation uh there's one the party that's able to participate there needs to be a party that knows the uh the witnesses of the inputs in order to

in order to make this protocol succeed whereas in public aggregation that's not the case public aggregation is taking tuples with their proofs and aggregating them into a new tuple that needs to be proved so um along the way to describing how to do an aggregation scheme um so we'll start with private aggregation um we describe a generic batch evaluation protocol that um we use just defining this additivity property which uh which which

as i said earlier any any scheme can have so whether the scheme is additive or non-additive we can always uh define some default addition operation so writing linear combinations of commitments is well defined so this works for any polynomial commitment scheme [Music] it is just that the the protocol as written here um will not you know maybe not may or may not be be be useful or interesting its efficiency characteristics will depend on the efficiency of uh succinctness of this edition what i'm describing here is actually a

a batch evaluation of the claim that a list of polynomials evaluate to 0 on some set so there's the inputs are a list of sets of points and the claim is that f i of omega is equal to 0 for all i meaning f i evaluates to zero and every point in omega i and that that's a bit more general and that um and that also suffices to uh extend this to proving that f i of that of some x i is equal to y i so this is the protocol that we described in the paper and then there's an analysis to show that this is this is generically secure just assuming the properties of the

polynomial commitment scheme so this is going to be a proof of knowledge no matter what the commitment scheme is and that's this really just synthesizes ideas that have been described for other particular schemes [Music] with some with maybe one minor tweak but uh but the main contribution here is proving the result generically so that we just assume that eval has an extractor and then this protocol we show is a secure batch evaluation protocol so how do we take this general formula and turn it into a aggregation scheme a private

aggregation scheme so um we can use the linear combined protocol to replace cg with c-star so when the scheme is additive then cg is itself succinct um so we would run the protocol as is but when the scheme is not additive then we could use a linear or even when the scheme is additive but maybe there's a more efficient linear combination protocol we can replace cg with a linear combination protocol which outputs uh c star because cg here is defined as just a linear combination of commitments that have already appeared in the protocol

that's why we're able to do this so the prover obtains the open star which is a pride which is private to the prover and the both parties obtain c-star and that's the output of the aggregation and then in a later step you would run eval on cg sorry eval on c-star and because the security property of the linear combination protocol is that running eval on c-star is effectively equivalent to running eval on cg which is the formal linear combination then composing the aggregation step with the evaluation step gives us back

the same batch evaluation protocol which we proved generically secure uh oh this is this was supposed to appear on the on the next slide so this is kind of cluttering let me see if i can here i just need to delete this and then go back into it um play from current slide so uh towards showing our results on public aggregation

we describe a generic homomorphism pre-image proof which is really just a generalized bulletproofs um and very similar to the generalized inner product pairing proofs um so i this is uh for for the for the special case of uh looking at the the the bulletproof polynomial commitment scheme um this is uh the just i like this this is the the the simplest way to explain and generalize a bulletproof for that particular use case which is just proving

a homomorphism pre-image which is a very very classical protocol in um in cryptography but succinctly and this is actually a proof of knowledge not not just an argument of knowledge it works for homomorphisms which are not necessarily collision resistant and effectively in in every round it well it's just like the bulletproof oh it's very similar to the to the bulletproof protocol um you send the homomorphism evaluated at you split the polynomial into the left part

and the right part um sorry not the polynomial this is more general there's a vector in z to the n and there's a homomorphism that maps this vector to the group g and so you split the vector into a left part and the right part and you send the homomorphism of the left part and the homomorphism evaluated on the right part that's yl and yr and then you get a challenge from the verifier and then there's this recursive combination step where um um y prime is uh is defined as um so uh basically x prime encoded under gr

plus alpha gl uh the way that we define the encoding of x is uh just that basically you can look at the you can define you can take any homomorphism of this form and define it in terms of um a linear combination of group elements where the ith group elements the i base group element is the homomorphism evaluated on the uh some canonical basis so here ei refers to the i standard basis so so this is statistically secure for any large enough group is that right yes okay um sorry um it doesn't

it does not well it depends on the field size um sorry uh the challenges need to be in zero to the altitude to the lambda uh the group oh you said the homicide the group doesn't matter he didn't need to be collision resistant okay so it's just the field that's correct that's the issue okay oh it's not it's not even completely correct to talk about it as a field the challenges are actually integers oh right okay i see right but but there would be no point in having them be larger than the group order

yes okay so um let's see um so as was observed with the bulletproof protocol um in the in the first halo paper um this protocol too effectively reduces um proving that this uh h of x is equal to y to

a statement that the uh that h of u is equal to some y prime where u is a coefficient vector of this polynomial that's defined in terms of the challenges so it was also interestingly pointed out in one of the reasons why this was used in the halo paper was that u is efficient for the verifier to evaluate but that actually we don't actually need to use that it turns out so sorry can you repeat that i i think i missed something that might be important yeah i'll come back to it um again later but

so one of the key points or steps in the original halo halo paper well in your halo paper is uh that this polynomial u is efficient for the verifier to evaluate and so you end up uh basically evaluating it on a random point to check that indeed uh basically you're trying to prove that um y prime is equal to the that you're actually trying to prove that h of u is equal to y prime exactly and uh and you and you and so you're because you're trying to prove that y prime is a commitment to a specific polynomial

defined by you then you evaluate you on a random point it turns out that that um and i'll come back to this uh later but it turns out that as long as you can prove knowledge of a pre-image of y prime the protocol here is secure so you this that you if you're on this hpi protocol then you basically reduce to proving knowledge uh proving knowledge of some pre-image of y prime and the the whole point is that there exists a public pre-image

okay and that's what will allow us to do public aggregation but it's not important okay that it is exactly equal to the encoding of you and it's not important that that that h is collision resistant there could be many ways of defining h and um you don't have to evaluate you on a random point it's like it's a minor we could evaluate it on a random point it's just it it's um it turns out that we don't need it and it also turns out that in order to prove this generalized this very generalized version of what i would call halo aggregation is uh is this observation that it suffices to

to prove knowledge of a primitive y prime okay so uh to describe public aggregation let's first assume that the commitment scheme implements a homomorphism from z to the d to the g and why that's sort of without loss of generality is because given any additive pcs we can let ci denote commitment to the um to the ith monomial and then define the commitment scheme in terms of a linear combination of these uh base commitments

and so we can define commit in a way that it implements a homomorphism from z to the d to g so then the next step is that um we slightly modify very uh generically how eval star works and so the way that the evaluation protocol will work which will enable us to do public aggregation um and this doesn't uh this the transformation does affect the complexity a bit but it only adds a log overhead um additive log overhead not multiplicative so let's define the homomorphism

um hx of f where it outputs uh first h of f and then also f of x a polynomial evaluated at x okay so the output of h of x is a pair c y where c is interpreted as a polynomial is a commitment and y is the evaluation of f on the point x so eval's star can be re-characterized as proving a knowledge of a pre-image of this homomorphism okay so you're proving that you know f such that h x of f is equal to c y it's equivalent to showing that uh

c is a commitment to f and f of x is equal to y so just as a side note this also shows that given any collision resistant homomorphism we get a generic succinct pcs which just generalizes the bulletproof cc pcs which is uh which is also interesting because it it kind of um gives us other directions for building other polynomial commitment schemes perhaps from lattice assumptions et cetera so then we can run the the hpi proof so the first step is we

define this homomorphism the second step is we run the hpi proof almost all the way but we don't have the verifier do anything the verifier doesn't run the inefficient hpi verification which is linear time we just run the hpi proof to get to get this public um with the they get this public witness sorry this is public pre-image u of c prime y prime such that h of x h x of u is equal to c prime y prime and then we run eval on c prime x y prime so effectively what we've done is we've reduced an eval instance with a private witness to an eval instance with a public witness

so how do we do public aggregation well we take our eval star proofs for c i x i y i and each of those contain an eval proof for some c i prime x i y i prime with a public witness ui and then we run private aggregation but because the witnesses are now public both parties can run the the approver of the private aggregation protocol uh so notes on difference from original halo i kind of alluded to these in the discussion but one it doesn't involve testing u of x at a random point and two it relies on generalized proof of knowledge of homomorphism and

this new analysis um which shows that it's a proof of knowledge that which effectively shows that proof of knowledge for a pre-image of y reduces to a proof of knowledge of a free image for y prime and h doesn't need to be collision resistant and also i'll advertise that i think it's like maybe so far the simplest uh proof of the bulletproof protocol uh is kind of described in a more general way but it's actually much much simpler than the original bulletproof uh protocol proof although this is for the special case it's not for inner products so it's not for quadratic forms it's for

linear forms so putting it together um this is kind of following the same formula at a high level that that halo follows and and as well that [Music] accumulation schemes the paper and accumulation schemes which formalized and and generalized the halo paradigm uh follows uh the main difference from like the accumulation the accumulation scheme paper generalized halo uh without saying whether it it applies broadly to a wide class of polynomial commitment schemes and so

what we're showing here is complementary we're showing that you can apply the halo paradigm with a very broad class of polynomial commitment schemes which we characterize more precisely and happens to encapsulate all the polynomial commitment schemes that we know with the caveat of ivc versus pcd and private aggregation versus public aggregation but putting it together if you have a pcs predicated proof system meaning that the complexity of the proof is dependent on this polynomial commitment scheme predicate um so that the the complexity the the the evaluation is is uh

poly logarithmic plus whatever it takes to verify the polynomial equipment scheme proofs then and you combine that with a public aggregation with a sublinear aggregation verifier public aggregation verifier then you get generalized halo recursive proofs and if you look at the generic public aggregation protocol we just described indeed we have a sublinear vag for any additive polynomial commitment scheme and then we can do the same thing with private aggregation in ibc

or include as a private witness as part of the pcd proof uh thank you so that now that's kind of the end of the presentation but we can do questions and i can pull up a whiteboard or the floor is yours great talk thanks ariel yeah thank you that filled in um a few details that i was a bit hazy on i wanted to add some comments but you said everything so perfectly that i just have nothing to say oh thanks ariel yeah there were also

some really good questions um i really appreciated the question about comparing what you get with this to fractal and uh and that was a very good point about um yeah the subtleties of of uh achieving ibc with private aggregation versus pcd in comparison to the previous ways of doing it and so i think that the next step here is to get a bit more concrete about the part of that is implementation but part of that is actually just analysis one of the things that we need to do

just to kind of look at how much this lowers the recursion threshold for ibc with fri i think that's kind of the really interesting question here how far along are you with that um along it's more just that i [Music] i haven't put in enough time to it but yeah with it's it's a pandemic it's it's good but um uh but also i i thought that there was a uh a more efficient way of doing the linear uh the linear combination scheme for fri then so so basically the the gener the

the simplest way to do the linear combination scheme for fri is to produce a fresh fri commitment to the linear combination of polynomials and then prove uh proximity of the virtual commitment defined by the formal linear combination of input commitments to this fresh commitment and that involves a constant number of queries well i mean proportional to one divided by the the rate and or land the security parameter over the rate and it it's uh it is independent of the of the degree um but that also requires uh using a

proximity parameter that is up half the size because what we want to do is basically invoke the triangle inequality we're saying that if we prove that this fresh commitment is um you know delta over too close to the linear combination of input commitments then if we prove in then we then subsequently run fri um on the fresh commitment and prove that it's dealt over too close to a code word we've proved that the linear combination is of input commitments that virtual a so-called virtual code word or virtual commitment is close to in our is delta close to an rs code word so it

requires using a delta parameter which is of half the size which roughly doubles the aquarius complexity of rye and and also we'd need to compare the concrete number of queries or point queries required to to compare uh uh for basically for that proximity proof of of two vectors uh so asymptotically it's a log d savings but i need to work out the actual concretes i thought that it um would be possible to just run the first round of fri but i was a bit wrong about that what i missed is that there's a subtlety

and fry you first run the protocol to get all the commitments and then you perform queries where the queries to the first round oracle actually deterministically fix queries for the later round oracles so in the vanilla description of fry you have just like a random consistency check per round but actually the way the final protocol is described they're correlated consistency checks and and that uh that kind of ruins the intuition that you can just run the first round of fry to reduce the uh to reduce opening a linear combination to opening

like a single polynomial which put commitment which comes out of the first round of fry um but i think that there's more to look at here just in terms of getting the most optimal linear combination scheme for fri okay yeah are there any other questions or comments ben do you have something that you wanted to whiteboard or did you just sort of want to bring that up no no i just did it yeah i mean i could draw a flower or something but but yeah so so this new fry ibc thing are you

uh is that implemented in in artworks or something uh and will you get numbers as to how fast it is oh yeah well that's what i was just saying that the next step is to first analytically show what the improvement would be and then also to implement it to see we haven't done that yet okay i think you had asked if it would be an arc works is that what you were saying now yes well i know if all you if everyone in um in the bay area is working on that i know patricia's on here no not just in the bay area we uh we submitted the pastor kevs to

yeah are there any other um polynomial commitment schemes than fry that are interesting for this approach i mean i know it works generically but but other other ones that uh i think yeah i think i think fry's so um i think the first thing is that we already we get a nice kind of general result for additive schemes so that you don't have to kind of i think the community kind of had the intuition already that uh halo could be done generically for any additive scheme but this is kind of like a formal proof and uh so we can without worry plug in any additive scheme

but i think that the yeah i think the most interesting new scheme that we would get is from fry and i i can't think of any others yet so we don't have that many polynomial equivalence games actually so i guess i guess the one from dark might be interesting because it wasn't entirely obvious oh yeah yeah right because it's not strictly added if it's only banded that's correct yeah so uh that's another thing that i i wanted to add to the paper um i'll update it at some point which is that um you can improve the public aggregation for for dark but you need to prove that you extract like a bounded size witness and um uh yeah so

so i guess that that also is i think people also had the intuition that you could do halo for dark but uh this is a step to proving that it works for dark uh i've worked it out on paper that it works for dark but i take that with a grain of salt until there's a formal proof in the paper and then it would be interesting to to see how that performs in practice yeah i guess that's because halo just just plain halo is um a stressless setup so halo with dark is only interesting if it's concretely more efficient um

yep cool well if there are any other questions i'd be happy to address also if you have any follow-up questions feel free to send me an email anytime thank you this was great thanks derek oh i was muted thanks so much i started to sort of do our outro here um yeah thank you so much for doing the presentation and um we'll be hopefully seeing more as as it comes out do share anything that you are releasing or any like additional things in the study club so people can oh i have another question um oh

so what's your take on the more recent um paper that um from berkeley folks uh in benedict yes exactly um uh yeah so i uh i so i haven't fully read and digested that paper uh but uh if complementary i think that the key thing that they're focusing on is actually proving that you can do a pcd where you don't have a succinct commitment or snark so in all the things i've described here the um i mean yeah we we describe very general pcds or

ivcs from uh from many instantiations of a polynomial commitment scheme but all of them have to be succinct i mean the concept of of public and private aggregation for your paper made that paper a lot easier to understand i have to say it did i i found that as well and the paper that you're talking about is called proof carrying data without succinct arguments i guess this is the one with benedict alessandro william pratush and nick um i'll add the links to these in the sort of show notes of the youtube uh what do you call those the youtube notes whatever they are but sorry i'm terrible at remembering the titles of papers i just found it um but we actually hope

to do actu i don't know if it's gonna happen but we are hoping to do a study club on this is on that one as well so we can expand on all of this great great so i think if that's it then thank you so much again yeah thanks anna