zkStudyClub - ARC: Accumulation for Reed-Solomon Codes (William Wang, NYU)

Transcript

so hi everyone welcome to another edition of ZK Study Club it's been a while uh today we're exciting to welcome back William Wong who's been a repeat guest here on the channel so thank you will for coming back to talk about Arc accumulation for re Solomon codes so the work done together with Benedict bus from NYU brat MRA from pen and Wilson inan from Stanford uh so yeah thank you William take it away up to you co yeah um so I just want say yeah first of all it's great to be back um this work is kind of a followup to the the previous work that we talked about in uh like a year ago I want to say at ZK Study Club

um but here we kind of resolved the the main limitation that was there and yeah let's just get started uh oh and one more thing just feel free if you have questions to just unmute yourself and ask at any time through the presentation I'll just pause Okay cool so so let me just first start with a very high level motivation so kind of our overarching goal is to build IVC and PCD so these are cryptographic Primitives that have a lot of applications um including in blockchain systems like rollups zkm and also more abstractly things like paralyzed and Andor low memory

proving okay so as of today I have the most efficient IC and PCD is built from accumulation schemes uh these are also known as folding schemes and I should point out that kind of when you're building IVC and PCD there's always this Baseline solution which is to use um recursive snarks and so whenever I talk about accumulation or folding kind of implicitly I'm assuming that we're talking about some sort of non-trivial accumulation scheme uh that does better than a than a snark wood Okay so ation schemes are typically based on some sort of group based or lattice based cryptography uh where they take advantage of the the underlying

mathematical structure of the Assumption and in this work we're going to be looking at how to build hash based accumulation um and our approach works for many different constraint systems uh in this talk I'll just focus on R1 CS okay so why is Hash based accumulation useful or interesting well there's I think two main reasons one is uh it's arguably a much more conservative assumption than a lot of these other public key assumptions it's also postquantum secure and the second reason is that we can kind of hope to achieve some of the benefits that normal hash based proof system have uh specifically like a very fast

Pro okay and I should also mention that in our previous work we also look at building hash based accumulation but we kind of have this this un fortunate restriction uh which is that we can only achieve like a weaker form of accumulation which we call bounded depth accumulation uh which kind of hinders the the Practical efficiency of that work so here we're actually just focused on building a standard full-fledge accumulation scheme that has unbounded depth and is also hash based okay so this is really the last time I'll mention IVC and from now on I'll kind of focus on accumulation schemes as the sort of central object of interest in this talk so what is an accumulation

scheme I think it's just helpful to view it as a pair of reductions so you have an initial reduction which um takes your relation of Interest let's say your favorite NP complete relation like R1 Cs and converts it into a statement for a central relation which I've called R here and the second component is a many to one reduction which takes multiple statements in R and compresses it into a single statement in R okay so the way that you would actually see uh accumulation scheme in action is let's say you have some R1 CS instance you're going to use the initial reduction to convert it into a like a central instance and then you're going to repeatedly compress it with an existing

like running instance and you can do this over and over again right so if I have a new R1 CS instance I first convert it into R and then I compress again and I can do this for an unbounded number of times okay and just for some context in a folding scheme like Nova for example um the central relation here is what they call relax committed R1 CS which in some sense is basically equivalent to R1 Cs and so for Nova kind of this initial reduction is Trivial and really you would be talking about this many to one reduction as the folding scheme um whereas for us I think it will be useful to explicitly distinguish between these two compon on of the accumulation

scheme okay so I've been talking about reductions and now I want to formally Define what an interactive reduction is so an interactive reduction is from one relation R to another relation RP Prime and it's an interactive protocol between a prover and a verifier so the prover receives some statement and the verifier receives the the instance and they engage in some sort of interactive protocol such that at the end the prover outputs a new witness and the verifier outputs a new instance and just like in interactive proof or an interactive argument there are two Key Properties so the first is completeness um if the statement original statement was in the relation then the new statement will be in the

new relation and the second property is soundness which basically says if the original statement is not in the language then the new statement will also not be in the language with high probability uh no matter what a malicious PR might try to do okay so in this work we consider a very closely related model which we introduce and call Interactive Oracle reductions so intuitively you can imagine that interactive Oracle reductions are sort of the reduction version of interactive Oracle proofs um where the verifier instead of reading the Prov message in full now gets to uh query the the Prov messages at very specific locations and

this allows the verifier to be succinct uh in the overall proof length Okay so the cool thing in an i is that the instances themselves can also have oracles inside of them that the verifier can query and additionally the verifier can output oracles as part of the new instance so these oracles are must be selected from one of the PR's uh uh message oracles or maybe the old instance oracles okay and IRS can be compiled into standard Interactive ructions uh essentially by using Merkel commitments and this is analogous to how iops can be compound to succinct arguments uh using like the BCS

transformation cool so now that uh I've defined the model I just want to give a quick overview of what I'm going to be talking about in the rest of this uh presentation so our goal will be to kind of construct interactive Oracle reductions um for accumulations schemes which minimize the query complexity of the verifier and this sort of translates into a more efficient accumulation verifier and hence more efficient IVC scheme so as a stepping stone we're going to first construct a many toone interactive Oracle reduction for read Solan proximity claims uh I'll Define what a proximity claim is in the next slide and the key feature of our

reduction is that the verifier makes uh o of Lambda queries where Lambda is the security parameter um now in contrast the best known read Solon proximity tests like stir and were make o of Lambda time log log nqu so we're shaving this factor of log log n um in practice so obviously it depends on how you set the parameters but in practice this can be quite significant um and I should say that an i for proximity claims is different from a proximity test and and that it performs a different uh it has a different guarantee but in the context of the accumulation uh their verifier efficiencies are comparable um because they both translate into what the

accumulation verifier would look like okay I should also mention here that there's also two concurrent works I think they're called boil and deepy that also show this sort of stepping stone result um and our main result is that we construct a full-fledged hash based accumulation scheme for R1 CS um but I'll get into that later and give some comparisons at the end of the talk okay so let's just focus on what with those concurrent works again uh one is called boil b o i l and the other one is called Deep Ali and they both they both also make this odd preservation uh that you can get a many to one interactive Oracle reduction for

read Solon proximity claims where the verifier makes of of Lambda queries yeah thank okay so yeah so for now let's focus on the stepping stone and then we'll get to like the the main result afterwards so first of all um just for some background I want to Define what a read Solomon proximity test is and what a read Solomon proximity claim is so just laying out some notation I'm going to let C be some arbitrary read Solomon code and then I'm going to let F be some arbitrary uh Vector so you can think of this read Solomon code c as a subset of the set of all possible length n vectors in particular it will be a linear

Subspace um okay and the goal of a readman proximity test is to verify a proximity claim that f is uh Delta close to C that's what this notation means um and in words basically I'm saying uh there exists a code word in uh in the subset c read Solomon code which uh disagrees with F at at most a Delta fraction of points so if we set Delta to be like 1/4 that I'm saying that there exists some code word c which agrees with f on at least 75% of points so they're close to uh they're close in terms of Hamming distance okay and read Sol and proximity tests are a very common object in the pr systems literature um so some pretty well-known

examples are of course fry and more recent ones like stir and were and they're used to construct snarks uh essentially uh by this recipe so you first have your NP relation of Interest like R1 Cs and you have some initial reduction which converts it into a read Solomon proximity claim and then afterwards you run the read Solomon proximity test to verify the readed Solomon proximity claim so really this the snark recipe can be thought of as having two ingredients the initial reduction and then the proximity test okay so for us when I talk about readed Solon proximity accumulation what I'm talking about is a many to one reduction for read Solon proximity

claims and the hope is that this reduction can be cheaper than a proximity test right the fact that it's cheaper means that we can get more efficient like a non-trivial accumulation scheme and this is what the accumulation recipe would look like so we have R1 CS instances we use the initial reduction to convert it into rman proximity claims and then we just repeatedly compress it using our many to one reduction for the proximity claims okay and I should note here that all of these uh proximity bounds these Delta values are the same and I'll refer to this as like a distance preserving reduction so whereas in our previous work um accumulation without homomorphism uh Delta kind of degrades

over time so Delta becomes Delta minus Epsilon minus 2 Epsilon with every step um and this is what leads to this restriction of having a bounded number of accumulation steps uh here our distance bound of the proximity claim will always be Delta and therefore we can continue to accumulate as much as we'd like Okay so let's take a look at how we can construct uh this many to one reduction so for our first attempt uh we have approver and verifier the verifier receives as input the two uh input vectors F0 and F1 and the natural strategy would be to do some sort of batching of the proximity claims so this

is a very common technique the idea is that the verifier will just sample a random challenge Alpha and then will output uh the random combination of F0 and F1 under Alpha okay so let's quickly analyze this um for completeness like if these two input uh vectors are indeed code words then since the code is linear uh the random combination will also be a code word so we're happy um and for soundness if either of the inputs are far from the code then resolvement codes exhibit this property which is uh called a proximity Gap and basically this proximity G Gap guarantees that with high probability right over the choice of alpha the

random combination of uh oh this should be F0 and F1 the random combination will be Delta far from the code okay and so that's good as well so we've satisfied both completeness and soundness um but there is a problem which is that we haven't really shown how the verifier outputs this new Vector G so clearly the verifier cannot literally compute G itself because it needs to be succinct uh and the length of G is just uh too too long um instead what the verifier can do is it can output the two instance oracles like F1 and F2 I should say F0 and F1 as well as the scalar Alpha and this virtually defines G in the sense

that whenever you would query G you can just query uh F0 and F1 at the same location and then compute the combination um locally now the issue is that this is not allowed in accumulation um intuitively because now the size of this new instance is two vectors and if we continue this process of accumulating more and more things the number of vectors um the the size of the material in this instance G will continue to grow over time and in in some sense we have not actually achieved any sort of compression um because the because our instance is virtually defined over many things things and this is not allowed in accumulation schemes so uh to get around

this issue we're going to rely on this uh this very common technique in rol and proximity tests which is called quotienting so quotienting originated from the deep friy protocol and now it's used uh elsewhere such as in stir uh and here so I've explicitly defined quotients here um so given some Vector F and some scalers XY we we say that the quotient of x under XY uh is also a vector and it's defined according to this equation so I don't want to like go too much into the specifics but for completeness basically we can observe the following uh given a valid code word a valid read Solomon code word the quotient uh of f under X and its

evaluation at X will always be in the code uh for any choice of uh X and for soundness we have this observation that gives an arbitrary um Vector F uh letting U be the the code word which is uniquely Delta close to F here I'm assuming that Delta is at most the unique decoding radius of the code um If U of X is not equal to Y then the quotient will be Delta far from the code okay and quotients also generalized to more points so if I I can quotient F by a bunch of XI y points and if you disagrees with any of the XI Yi then I get that the quotient is Delta

far from the code cool so the way that we're going to use quotients in our protocol is uh Loosely inspired by um stir so stir also uses quotients and the intuition in both cases is that we're going to translate a proximity Claim about a virtual combination of vectors like we had in the many to one reduction and we're going to convert it into a proximity Claim about a single Vector which is amenable to to repeated accumulation so the idea is that the prover is going to actually recommit to this random combination f um and then the verifier is now going to quotient F uh by some points X iyi to

define the new instance and these points the the XI are obtained by randomly sampling locations in the vector and then the verifier actually queries F0 and F1 to compute what uh Yi should be okay um and yeah the output claim is that this new quotient G is going to be Delta close to uh the code okay and I should note that stir also uses this sort of recommitting strategy but in some sense for a qualitatively different reason um in stir you kind of recommit over a larger domain and they do this to kind of improve the efficiency of their

proximity test whereas for us we're just recommitting over the same domain um and the only reason why we care about this is that we need to actually achieve some form of compression this is necessary in accumulation um and it's actually very important that we recommit over the same domain because this is what allows us to kind of uniformly continue to um accumulate more and more things okay so let's take a look at how batching and quotients can be used together to give us our many to one reduction so it's the same setup as before can I ask a question please sorry y sorry just go back uh a slide real quick

yeah okay so verifier defines quotient G but but G is still virtual and depends on F0 and F1 right so how have we made progress um yeah so you're right that g is virtual but G is virtual virtually defined only over F not F0 F1 um well Pro it recommits to yeah so this this F is now sent as a new Oracle um and the quotient is now defined over a single Oracle which means that it's oh quotient F by X and Y but the x's and y's come from from F0 and F1 but f is is the recommitted thing um okay

interesting um yeah I mean I think it'll also be clear uh with this visual um so the verifier samples the challenge now the prover is yeah going to send over the claimed random combination as a new Oracle F so at this point we don't actually know like for a dishonest prover we don't actually know if f is equal to the random combination or not but we're going to use this quotient to somehow enforce consistency between F and the random combination the verifier is going to randomly choose a bunch of indices it's going to query the original oracles at those indices and then it uses this information to Output the quotient uh

G okay and again G is virtually defined over the new Oracle F so if we Analyze This protocol go uh how big are the um xon to XT oh yeah so T here I should have yeah I probably should have clarified this T will be um kind of a linear in the security parameter so you can think of t as Lambda I see yeah okay um so for the analysis right if for completeness it's the same as before um if the two inputs are in the code then the combination will be in the code and since the honest prover commits to the same

combination uh the quotient will OB always be in the code as well now for soundness again it's the same as before if either of the input vectors are far from the code then the proximity Gap guarantees that the combination is far from the code and now letting you be the unique code word which is Delta close to the the recommitment F if it exists we know that U is going to be Delta far from the random combination right because this random combination is Delta far from the code and therefore with high probability the quotient of the new Oracle by the the values computed from the old oracles will be Delta far from the

code okay and then we're so really there are two cases right there is the case that F0 and F1 or or F1 are far and thus their combination is and and thus um right but but they could also be close and then F just be close to a different code word something like that right yes but um sorry could you could you say that last sentence again um so so it could happen that F0 and F1 are are close to the code or let's say they're even code words or something right um and then their combination is of course also close but

then f f could just be close to a completely different code word I mean that's another thing the prover could do badly in which must which would also get caught in other words it looks like you're only you only you're only analyzing the case where F0 and F1 are far there's another there's another way to for the pr to to to be malicious which is inconsistency sure yes um yes I guess I've kind of overlook this but uh in the slide here but kind of you will you will always be since the combination is far from the code any possible code word it will be

far from any possible code word regardless of what the Prov chooses if if it if F and f0o or F1 are are far but again that that's just one way for the pro to be to be bad the other way is for them to be close and then for f to be close to something else different a code word different than the one that their combination is close to yeah but I I guess we don't really care about this in the in the soundness case right like for soundness we want to assume that like it's only proximity you oh oh okay sorry sorry it's only proximity that you actually care about my bad yeah um so it will be a bit more interesting when we get to the main accumulation scheme um but for now yeah we only care about proximity yeah yeah yeah

sorry okay um and finally I just want to yeah reemphasize this fact the verifier its output really is a proof Oracle F which is just taken from like selected from the previous message as well as the scalers X iyi and this virtually defines G and and since G is only virtually defined over a single Oracle um we've achieved compression okay and and all of this just generalizes to like a many to one reduction not just to a two to one okay so let me zoom out a bit um so actually what we have already is enough for an accumulation scheme like a non-trivial accumulation scheme the idea is okay we have a read solement proximity accumulation like this many

to1 reduction and then we can kind of reuse any existing initial reduction from R1 CS to read Solon proximity claim like from snarks um and this gives us an I guess interesting accumulation scheme which has ASM totically fewer queries than um it snark counterpart uh now the downside of this approach is that this initial reduction still involves quite a bit of snark Machinery um roughly speaking this initial reduction will correspond will usually correspond to some sort of polinomial I um and the prover is and I've kind of omitted detail here but typically this proximity claim the vector that we want to claim proximity to the code for is actually virtually

defined itself over like K different Oracles uh where the K oracles are sent in the initial reduction and therefore the verifier actually is making K times o of Lambda queries like o Lambda queries to each Oracle in order to um uh query like the virtual combination of so the natural question is can we do better and indeed our main result shows that we can kind of get a direct accumulation scheme for R1 CS or whatever constraint system You' like um where you don't have this sort of like multiplicative overhead of K stemming from um like the snark machinery and it's Direct in the sense that it looks

very similar to kind of existing accumulation schemes like Nova protostar Proto Galaxy where kind of all the does is commit to the witness here intuitively all theover is going to do is commit to an encoding of the witness okay so the high level approach is that we're going to Define these things which I call like an algebraic proximity claim so intuitively like not only do you want to claim that f is close to the code a vector f is close to the code but we also furthermore want to claim that f is close to a valid encoding of the winess so the specific code word that f is close to decodes to a valid R1 CS witness right so recall that W is a valid R1 CS witness if this uh Matrix

equation holds um where Z is the concamin of the instance and witness vectors and what we can do is we can kind of Define a subset of the code uh which I call like the subcode C subx which consists of all of the encodings of valid Witnesses valid R1 CS Witnesses okay and if we could construct a many to one reduction for algebraic proximity claims so of the form that f is Delta close to C C subx then we're done um I claim that we're done like we have a very cheap initial reduction to an algebraic proximity claim and then we can just run this many to one reduction okay um so actually what we're

going to work with is like a compressed version of these algebraic proximity claims which kind of batch together all of the readall all of the R1 CS constraints so for each row of the all right so like let AI be the I row of a The Matrix a and let B I be the I of the Matrix B and C analogously um what we can do is we can Define this polinomial um which you can just imagine as like batching all of the R1 CS constraints by taking a random combination with r and the point is that if r that is a valid R1 CS instance or R1 CS witness if and only if this polinomial if you fix

the X and W um is identically equal to the zero polinomial because each coefficient of this polinomial would just be zero okay now we can Define like this subcode C sub rxe which consists of all valid encodings of W uh such that P of RX W is equal to E okay so um intuitively you can just think of this as a compressed version of the of the subcode that I um talked about in the previous slide and our goal to be will be to construct a many to one reduction for these algebraic proximity claims okay so the initial reduction is

now quite straightforward um from R1 CS to an algebraic proximity claim uh so the prover gets the the R1 CS instance and Witness the verifier gets the instance and now all the Prov is going to do is it's going to send in EN the encoding of the winess as an oracle F and the verifier is now going to just sample random challenge R and it's going to Output the claim that f is a Delta close to uh this subcode c r c sub rx0 okay so let's analyze this um so for completeness if W is a valid witness then um as I said before this polinomial

once you fix X and W is identically equal to the zero polinomial and therefore no matter what random challenge you choose F will be in the in the in the induced subcode okay now for sadness If X is not in the language then there's no satisfying witness um so again like letting you be the code word which is DOA close to F if it exists then p with high probability um or I should say this polinomial is now identically not equal to the zero polinomial right because uh the decoding of you cannot be a valid witness since X

is not in the language and with high probability over the choice of the random challenge R um f will be Delta far from this subcode okay and again it doesn't uh yeah here I'm just assuming again that the Delta is at most the unique decoding radius of the code okay so with that let's get to our our main construction which is this accumulation scheme this many to one reduction for algebraic proximity claims so okay we have two input claims first that F0 is Delta close to some subcode and also that F1 is Delta close to some subcode

and we're going to follow kind of this uh the accumulation strategy uh according to Proto Galaxy but really like I want to emphasize that this is not really specific to any any one folding scheme you can kind of instantiate this sort of idea with things like Nova or protostar or other things um but here we're just going to use Proto Proto Galaxy's rough accumulation protocol as the kind of skeleton of the construction so we're just going to interpolate our inputs um yeah we're going to just Define polinomial to interpolate RX uh the witness and the error error value e and then Proto galaxies basically says we can run a univariate sum check for this

um this polinomial identity claim so it's kind of a univariate sum check um and this yields a new claim that um this composition PR rxw evaluated at Alpha is equal to some new value e uh where Alpha's randomly sampled okay so I've kind of glossed over a lot of details here but really this is this part is not important um to our construction like it's I would view this more so as like kind of Proto Galaxy protocol and the observation here is that this new claim looks like a new um new algebraic claim and what we can have the prover do is we can have the prover recommit to this this new new witness um

and by linearity you can actually see that this is a random combination of the input code words F0 and F1 and the verifier is going to Output the claim that this new Oracle f is Delta close to the subcode um induced by uh the the new sum check claim okay so the other thing that we have to do is that we need to enforce consistency as before between the virtual combination um 1 - Alp * F0 plus Alpha * fub1 and the Prov recommitment F because right now in in the previous slide there's no

reason for the prover to have to recommit to the the actual combination and so naturally we could try to just use the quotienting strategy that we had before um but the issue is here that the the quotient doesn't really play well with algebraic proximity claims and this sense that even if uh this Vector f is a valid code word in this subcode it doesn't necessarily mean that it's quotient is also in the subcode so in some sense like the quotient does not preserve the the algebraic structure that we're we're checking so the way that we solve this problem is to in some sense accumulate the proximity claims for quotients

separately from the the main algebraic proximity claim in particular the verifier is going to output both an algebraic proximity claim that f is Delta close to the subcode as well as a standard proximity claim uh that the quotient of F at some random points is uh Delta close to the the overall read Solon code okay so if we look at the this Construction in action uh we're going to have a two to one reduction for uh both algebraic proximity claims and um standard prox proximity claims simultaneously so the verifier receives four claims in total two algebraic one two

standard and then it's going to run the sort of P Galaxy style accumulation scheme um to reduce or compress these two algebraic claims and the Prov is going to recommit to what the random combination of the two input vectors should look like okay and then the verifier outputs this um proximity claim for f being Delta close to the sub new subcode and additionally uh the verifier is going to Output uh it's going to forward both of the initial standard proximity claims as well as this new proximity claim for the quotient of F and now what we can do is actually we can run our original men many to one reduction for uh read solement proximity

claims to compress these three things into one okay and as a result we end up getting a single standard proximity claim a single algebraic proximity claim uh which we can continue to accumulate in the future okay so completeness is fairly similar to uh the protocol I described earlier so I won't really talk about it instead I want to really focus on this um a sketch of the soundness proof uh which I think is a bit more interesting um so the point is if either all right so first of all

if either uh g0 or G1 is delta formed from the code these are like the input standard proximity claims then our proximity accumulation scheme guarantees that uh the new Vector G will be Delta far from the code so that case is handled we also need to consider the case where either um F0 or F1 are far from their respective subcodes so these are the algebraic proximity claims then what we can say is that the proximity Gap uh plus the sum check guarantees that this random combin of the input vectors F0 and F1 is Delta far from uh this new subcode okay so do you need oh sorry for the second uh bullet point uh do you need to use like a

proximity Gap resolved for like General codes like not the readed Solomon one uh no yeah so we we rely on just the proximity gap for read Solomon codes um in some ways it yeah I guess the proximity gap for these subcodes would naturally follow from that um but yeah it's a bit the analysis is a bit more complicated because you kind of have this uh the random challenge Alpha is both functioning as a proximity Gap challenge as well as the sum check challenge so you need to um like oh you're saying yeah oh sorry

sorry to yeah okay maybe I you're saying in general a proximity Gap result it it also implies the same result for any like Subspace oh okay yeah then that makes sense thanks yeah so actually like our um yeah yeah exactly um okay so so there are two cases now uh first of all if f is if the new Oracle that the Prov committed to is far from the subcode then we're done right because this new instance is invalid so now we just need to consider the case where the prover is trying to cheat right the Prov is trying to cheat by committing by by recommitting to some

new Vector F which is actually Delta close to uh the subcode so in this case letting U be the the code word which is uniquely Delta close to F we can observe that you is actually a member of this subcode CR e and since the random combination is Delta far from the subcode we know that you must be Delta far from this random combination right and now we can just use the fact that the quotient in this case must be Delta far from the code and therefore the proximity accumulation guarantees that g will be Delta far from the code so to summarize kind of we've taken

the I've highlighted in red all of the possible bad inputs and we showed that in all possible cases we uh our reduction leads to a blue like what's highlighted in blue which corresponds with the new input being um the new output being far from the code either the proximity the standard proximity claim does not hold or the algebraic proximity claim does not hold okay I have a question yeah so regarding this proximity gaps with respect is like subop code of r0 x0 e0 using srack so in that case do you still have the same

Bond like a regular resol code like the Johnson Bond or is actually the same bond for example as base fold which is double Johnson Bond so like yeah okay so I guess right now uh the soundness sketch that I've put up here I'm assuming that Delta is that almost the unique decoding radius of the code first of all um so in terms of the soundness error because we're using the proximity Gap we're using the same challenge for the proximity Gap and the and the sub check um the overall soundness error of this step would be like the sum of those two errors so it' be the sum of the proximity gap for just read Solomon

codes don't worry about the subcode business plus um the error uh incurred via some check I so you are directly using the unique decoding uh Bond not not Johnson Bond at all just just the the safest B you are saying in this slide yes um I'll get to optimizations on the next slide okay yeah thank you yeah okay so yeah so we also have some optimizations that we talk about in the paper so the first is yes like so far in this talk I've only focused on Delta being uh within the unique decoding radius of the code but we can also support um a proximity bound Delta up to

a list decoding radius of the code assuming that a suitable proximity Gap exists and in this case it's a bit more complicated but roughly it's still the same as before the soundness error is just the proximity Gap error for read Solon codes up to uh like that that list decoding radius um plus the sum the sum check error so there's no special error corresponding to the fact that like we're talking about subcodes uh really the fact that we're talking about subcodes is just uh related to the sum check error okay I don't know if that answered your question

um I guess the question is uh so so basically you are using the like the um the best listic coding Bond radius uh in the in the yeah I mean you can you can instantiate with um yeah whatever proximity Gap result yeah I'm not fully sure I follow because for example baseb doesn't have the best Bond compared to fry because like because the Su check so best result we can get is like a 1.5 listic holding bound not oh I see yeah so okay there two yeah so there are two options so in the paper we like um yeah okay so the protocol is more complicated basically we need to do like some

additional rounds of outof domain sampling in order to get the full um bound the other option is to um rely and this like I guess slightly makes it makes the protocol more ugly and I guess a bit less efficient um so I would I would say like we can talk about this later as well um but then the other option is you can use like some sort of U Mutual correlated agreement which is uh a more recent notion of proximity Gap um and that would also work but as you said right like I don't know if we've actually proved like Mutual Coral agreement up to list decoding Bound for read Solon codes

yeah but in that case if you use if you assume Mutual correlated agreement then the protocol is a lot simpler um you just do like one round of out of domain sampling similar to something like St I see yeah that makes sense thank you okay um okay the other optimization is that we can kind of reorganize our protocol so that the prover sends the Oracle FNG simultaneously as like a single like as a single interleaved Oracle um and the point here is that we can kind of reduce the Merkle tree openings once you uh compile this interactive Oracle reduction to a standard reduction okay but yeah both of these

things um you can just see them main paper Okay so finally I just want to give a very high level comparison between our hash based accumulation scheme and the prior best known approach to constructing like full-fledged unbounded hash based accumulation which would be just to use a snark like the the Baseline solution okay so if you were to use a snark then your initial reduction um from R1 CS or whatever constraint system to a read solement proximity claim uh would consist of like uh the Prov sending like let's say k oracles where in practice like K is like at least

three let's say um followed by a proxim a read solement proximity test where the Prov sends some additional smaller oracles which um don't really matter and the verifier makes uh o of Lambda queries to each of the K oracles plus an additional o of Lambda time log log n ques okay um now in our accumulation scheme it's uh both of the reductions are different right so our initial reduction is R1 CS to an algebraic proximity claim not a read Solon proximity claim and in this case the reduction is quite simple the pr literally sends one

Oracle just a commitment to the encoding of the witness and then we also have like this algebraic proximity accumulation like this many to one reduction where the prover sends one Oracle if you incorporate the optimization and the verifier only needs to make o of Lambda queries to its um two inputs okay so as you can see across the board um our approver is sending less oracles right sends two in total between the reduction and the many the initial reduction and the many to1 reduction and we have like a Asm totically and quite concretely smaller um accumulation verifier um due to the fact that in the snarks you typically

have like many oracles that you need to uh combine in order to run a proximity test over the virtual combination okay so f one more question sorry sure yeah seems that there also intermediate solution you mentioned initially right well initially you do a reduction from um RSS to RS proximity glim and then you use your um uh like your Arc folding scheme or reduction of knowledge to to do the rest instead using ster word so how how about the that one like the what's the performance comparison for that that kind solution yeah so yeah so this is like this sort

of approach would is also what is looked at in like the concurrent works like this this many many to one reduction for rment proximity claims um yeah so I guess the cost would look some what similar so first of all the initial reduction would be the same as for the hash based snark so prens K oracles and then in that case uh in the proximity reduction the many to1 reduction the prover does not need to send any additional smaller oracles it actually just sends one Oracle and then the verifier would make um o of Lambda queries to the k+ one oracles so the K Oracle from the initial reduction and then the additional Oracle sent by the Rover in the many to1 reduction so it' be k + 1 * of Lambda

and then there wouldn't be this additional Lambda time log log n queries as essentially if K is larger than three is still think the the the right right um right mod schemes is the most efficient one yes yeah I I would say that like if you were to just use the um the the the intermediate solution um like you would proa you would get some savings depends on like what K is and it depends on how the parameters on are concretely set in terms of this this log log n Factor um but I think it's clear like morally speaking I think this this accumulation scheme is like it's a

proper accumulation scheme whereas the other one is more of a this one this thing on the right is more of like a folding scheme whereas the the intermediate thing is I would consider less less useful Okay cool so um just to wrap things up so in this paper we we gave the first full-fledged in terms of unbounded depth hash based accumulation scheme um uh which achieves a Asm totically smaller verifier than the Baseline approach which would be to use a hash based snark and the one of the core components in our in our protocol is

this many to one reduction for re Solon proximity claims uh which relies on a cting strategy that's um inspired by stir but used for a slightly different purpose okay and then we use this many to1 reduction for read solman proximity claims uh to bootstrap to a many to1 reduction for just general algebraic proximity claims and this is what what's lets us like get something more interesting than um hash they just hash Bas snarks okay and finally I just want to mention some uh up coming work of ours which should hopefully be on ePrint soon um so in that work we kind of tackle this question where so first of all like Arc is very specific to read Solomon

codes because um uh this questioning strategy is unique to read Solomon codes so I guess a natural question would be um can we do some sort of accumulation where you can instantiate the the linear code with any code of your choice for example like a linear timing codeable code um and if so can you also make this resulting accumulation scheme linear time uh so yeah this is uh we so we we address both of these questions in this new work which uh hopefully should be online soon and yeah that's all I have thanks thank you very much William yeah

maybe you'll come back for present this new work in a in a few month that would be fun uh before we wrap up uh does anyone maybe uh still has a question about uh Williams presentation maybe me I give you a few seconds I know we had a few during the presentation so I expect that was kind of it but uh so one one question do you have uh how do you think the in terms of practical performance uh this compares to this a new work you uh you just mentioned um yeah so I would say that

the new work is um a strict Improvement because you could always instantiate the new protocol with Reed Solomon code and then for other reasons it's uh the verifier is the verifier makes the same number of queries but in terms of field operations it's smaller um and the prover also is linear time outside of like encoding so so res encoding takes like quasi linear time but the rest of the protocol uh in in this new thing um the prover would take linear time as well so um I would say that this new work probably just

supersedes this one um but in terms of like comparison between using a read Solomon code and like a your time encodable code for accumulation schemes uh it's less clear to me um what the the performance difference would be I mean it's a bit hard to say right because like like typically like the linear time encodable codes um start to outperform read Solon codes in terms of R time like you you need you need the size of your statement to be large enough for this this the ASM totic cic in um well this recent like uh Blaze one I think it's supposed to be better than

read Solomon for any n or reasonable really okay I I think they say in the paper the encoding time is 8 n so yeah okay yeah I guess I can't speak on that oh so maybe they're saying that the okay so if indeed it's true that like this encoding time is just better and you also factor into the okay so the other issue is that like like for example displays code the distance is like not is is worse right than like a readed Solon coulde for the same um same size so you also have to factor that in but okay assuming that the encoding time if you control for the distance is better then yeah the the new protocol should

just work very nicely I guess I should also like I there like another nice tidbit um in our new in our new work um we actually try to do straight line extraction uh even if the underlying code does not have like an efficient decoder like it is for um a lot of these practical linear time and codable codes so there's kind of across the board no drawbacks to to doing that then uh how much this have you implemented is are the kind of performance conclusions are they theoretical or you done experiment about about this paper or yeah this paper well

well both so this one we don't have an implementation I mean in terms of like the prover cost I think part of it is that it would look very similar to you can imagine that our our prover is kind of running a subset of something like stir like it's running the first round of stir and nothing else and you can think of the verifier as kind of being a subset of the stir verifier so if you just compare the two then like like clearly the subset will um will be better the question is how much better um yeah yeah yeah the question the question was directed how much

better I believe you this better um yeah um yeah so we don't have an imp implementation yet for the for the new protocol um this is something that I want to work on if uh but at the moment we also don't have an implementation for that so in the new work does that mean you do need proximity gaps for General codes or or how does that work yeah so you you need a corresponding proximity gap for the code so this exists for all codes obviously with like a worse bound but your proximity parameter is limited to D over3 case right

um yeah so so I mean there's also been some more recent results that actually show proximity gaps um past the uni unique decoding radius like up to some like one like one one 1.5 Johnson bound or whatever for General codes yeah for General codes can you share that yeah there's two um one is from it's called botum k h a t m and the other one unfortun I don't remember the authors but it's cited like it's cited in Cotton um so both of them I think get I think they get slightly different

results but um the other important thing is that in our new work we also rely on Mutual correlated agreement uh but both of these works also prove that so it's like a stronger version of approxim cap uh proximity gaps and interl codes uh icr um 2024 3051 it's that the one um yeah I can can just check right now um no uh D that that's my I think that's

my paper with with Angus um that is not that that does not have anything to do with Beyond oh okay the unique decoding radius actually the point there is is for tensor combinations I can explain but but WR paper yeah yeah yeah okay this is um okay I can I can post the the links in the T after this after this call thank you perfect sounds good so yeah thank

you everyone for for joining and thank you very much William for the for the presentation and yeah I guess we'll see you guys at the next session thank you very much