zkStudyClub: Gemini - Elastic SNARKs for Diverse Environments (Michele Orrù)

Transcript

today we are for the zk study club we are hearing from mikhail uru who's going to be talking to us about gemini so welcome michele hi hello everyone um my name is michele i am a postdoctoral student at uc berkeley and um in this work uh we try to study um how to prove instances that are very very large uh so we're concerned with the proofing circuits that have a very big size and this is joint work jonathan bruto alessandro and yoon song who so we're going to talk about zero knowledge proofs in particular about succinct arguments so we have this

usual conversation between approver and the verifier and at the end of this protocol the approver should be able to convince the verifier there exists a witness for which the relation is satisfied what does it mean argument it means that we will focus on these kind of dialogues where security will hold computationally and succinct will mean that the verification will be sublinear in the size of the witness actually i will be talking about arguments with preprocessing what does it mean it means that the verification time is even sub linear in the size of the statement so the verifier is like super efficient and um and we're going to focus on again this sort of interactive protocols between improvement and verifier where security holds computationally um

with this kind of argument separate will study no like snarks belong to this uh to this space and uh proving time is either linear or almost linear like i mean n or n log n for most protocols that we deploy in practice verification time is either constant like a constant number of pairings no this is the case of growth 16 or it's like logarithmic this is the case of things like sparkling and however the proving space is still sort of linear and this is not this this linear factor is actually like very large and um in fact if we were to try today uh to prove uh circuits with like billions of gates um on like modern improvers to prove that they've been implemented for the most part they would

sort of start crashing at uh around billions of gates and so there is really no way today to run approver with uh with like for a large circuits and um and that means that for me at least the bigger one of the biggest uh sort of constraints today is not any more proving time or verification time we've been working on that for a long time it's really the space the problem um yeah also for the implementer and try to give more details like when we try to run these instances we also give them like we we've been running them on on like big machines and even running on big machines there um like the kernel just doesn't want to to allocate so much memory for us um even even like relaxing and allowing

for over commit cover commitment to the out of memory manager um as an example on why we're interested in these sort of problems um take for instance like a compression function for uh shutter 56 this is around tens of thousands of gates um if you do it like a hundred times because maybe you're checking a bunch of merkle trees then you're already outside benchmarks that happen in papers if you do it a thousand times then you're far outside modern implementations what what can be handled by other implementations and this is the case for instance of i don't know zika roll-ups no way you have to verify a lot of uh of transactions at

the same time then then you you clearly have a very large circuits and um and it's not clear how to do it in practice so there has been a sort of a quite long literature a quite long line of research on how to make arguments that are space efficient for the most part they are tcc papers so they don't come with an implementation but the sort of i think that the initial line of research was exploiting for the most part recursive proofs what does it mean it means that i there is this idea that i can divide this big circuit into chunks and then prove these chunks singularly and then make a proof that stays statements about the single proofs that

i made on little chunks and with this i can actually build things called complexity preserving snacks that are snarks that preserve both time and space up to logarithmic factors actually poly logarithmic factors and these are this poly logarithmic factor it's not really clear where the like how big they are so it's uh it was mostly theoretical work and more recently there has been this interest in developing provers that are streamable what does it mean for approver that are distributable in practice and this is the way that i wanted to think about it is that you have approver that is reading a file sequentially and it's outputting a proof and it is trying to use as little memory as possible no and the inputs come sequentially like this

that was a nice animation and and then um but in in practice you can also imagine that i'm really downloading this instance from the internet no i'm logging from somewhere else i'm running the approver i want the approver to just go as long as like as long as it can and then output the proof but without like um without using too many resources from my system and i want to be able to sort of fine-tune the approver to that and theory what where the way that we model stream improvers is that we have this string machine that instead of getting us input the witness and the statement the private and uh and the public input it's getting an oracle access to a stream what does it mean a stream it means that this disprover can the stream machine

can ask for this oracle give me the next element give me the next element give me the next element or reset the stream and after running again in logarithmic space it is going to add to the proof it's all clear up to now i see two messages in the chat okay um yeah so in this work the main contribution i think is this idea of elasticity um we define an elastic proof system to be a proof system where you can run both in two configurations one that is time

efficient and we'll see how how fast it is and when this space efficient at the end of the execution approver outputs the proof this proof is the same the verifier can verify verify this proof and couldn't care less about which configuration has been running the prover on okay so very simple idea and and we show that these things actually work uh like there exists argument satisfied with this property we prove that there exists an elastic argument with preprocessing that is succinct for circuit satisfiability that has true realization one that is a transcendental time and once that runs in lock space okay

and um again this proof will be independent from the programmer configuration and the verification time will run in logarithmic and in size logarithmic with respect to the size of the statement okay can i ask you a question though so by independent you mean it it's um an indistinguishable distribution of proofs with the two cans approver yeah that it i mean that the prover at the end the output of the prover is exactly the same i see okay like the algorithm has admits two different implementations the next message function of this interactive protocol that meets two different uh implementations i see okay so so the whole protocol will be the transcript

will be identical and there is going to be something very cool about our protocol in particular and it's that we will as we will see we will be able to move from the space to the time efficient implementation i'm sort of dropping this idea for now and letting it rest in your mind but the second thing is that specifically the specification prover that um this complexity for running the specification provider was already known in previous literature however we improve on it in that um for specific types of uh circuits that are for instance fine state machines or hash chains then you can um actually get this down to n log n these are this log square factor really comes from

um like weird metrics weird r1c r1cs instances and um i'll get also to what is r1cs in a second um yeah um so you sort of have a time efficient version and a space efficient version and the sort of trade-offs between the two are quite extreme do you also have like everything in between in terms of that trade-off or do you have to go for the extremes so something that's like a little bit time efficient and a little bit space efficient would that be something that you would cover um [Music] we will see how to go to that yeah okay but uh the fine tuning is not asymptotic

however okay and also you're sort of saying yes but you don't necessarily know what the asymptotics are uh no it's it's yes but i'm playing with constants and as we will see constants will be very important with these log factors okay okay and um yeah so i think um if i have to like to place this work among like uh the the sort of various literature we have like different uh sort of uh um abstract protocols no these are what we call iops um sort of i'm going a bit more in detail but then i will i will sort of keep talking high level um so this is a little parenthesis for the

more technical people if i have to um think about the abstract protocols generally we think about queries that can be over vectors no i can make uh inner i have a vector of commitment and i'm asking for inner products or i have a multivariate component scheme or i have a universal scheme asking generating protocols for vectors it is much easier than generating them for univariate however it is much more difficult no sorry yeah yeah yeah and however it is uh like the set of a deficiency changes no like unified protocols are much more efficient and uh in particular we know how to build a system that have like constant number of pairings for uh when

they are univariate but we don't know how to do it for instance with multivirus protocols and up until now like before this paper we knew how to do um succinct arguments that would run in linear time in the multivariate setting but it was not clear how to do it unified this is what we do know we say that we can do a univariate in particular we will build a unified subject that runs a linear time and the verifier will be logarithmic and that's funny because really you can see this trade-off no where the log factor if you accept the fft it goes up to the approver and uh if you don't want to do an fft you want to stay linear then this log factor will be built by the verifier and um

i think there is really like this this trade-off that you're doing where either the analog n is taken care of by the approver or it's taken here by the verifier and in addition yeah i'm slightly confused um isn't the multivariate case a generalization of the univariate case so yeah you would expand it why do you need a new result to get um ps of n and v of o log n because i like if i have a univariate protocol then i can use a multivariate commitment scheme but not vice versa if i have a multivita a multivariate query then i don't know how to translate it into a unified query and we will see later today how to build it and the second thing is about the space

efficient protocol that we knew also how to do it multivariate but we will see how to do it also univariate and um yeah this system will be for r1cs why did we choose our once yes because it's uh like it's one of the i would say most common ways of translating a circuit into an algebraic relation and in particular no like uh the sort of if i have a circuit c then there exists matrices a b and c um for which there is a z like if i know an input then i can find this z such that it's relationally satisfied oops well what does it mean well i guess you're going to go go on to this later but um are you assuming splash

matrices or say it again are you assuming that these matrices are going to be sparse yeah i will clearly assume that these matrices are going to be sparse and um yeah so what what do i mean by this i mean if i have an an arithmetic circuit doesn't mean arithmetic circuit i have additional multiplication over field elements i have n wires and m gates then it is possible to build matrices again a b and c those dimensions will depend on the number of wires and gates such that um and and how do i generate this matrices no i will put in each element each row of a the left input of the um

[Music] of the nth multiplication gate so over here i will put one for zero one for z1 because i will go through additions and then zeros everywhere else over b i will do the same i will put however the right inputs the multiplication gates so i'll put zeros inside sequence of one and one for the two and zero goes elsewhere now if i do this inner product no i get that zero plus the one times the three is equal to time times the two that two is equal to z3 and in c in fact i will put the output gate and i will do so for every multiplication gate and there you go if i have a circuit that is satisfied then i will be able to construct this z such

that this relation is satisfied so our contribution is uh um now like another one of our contribution and and i think it's necessary now when you start talking about streaming is how do you stream these are one cs relation and we sort of try to define it you know and when you stream uh r1cs relation this is really what the prover will get as input note you will get the stream of z what is the stream of z z is a vector so i will give you them element by element i will give you each element in z one by one the matrices a b and c i also want to give you a stream of them and i will give it to you in either row major or column major and there are two ways in

which i can iterate for them on the right because it's like two-dimensional and um and yeah as uh and and i will be i will assume that they will come in a sparse notation you know okay it will be sparse the representation will be sparse finally i will also stream assume the stream of the computation traces what is the computation trace is the product is that bizarre and cz now this clearly i can do it even in linear time if i can if the metric i can make assumptions on the metrics itself the matter is quite simple but otherwise we just assume that this is already pre-computed and the approver just has it as input okay

so the theorem works like this you have an idealized protocol that is uh elastic you take polynomial scheme that is elastic you compose the tune you have an entire snark that is elastic so i'm going to focus now on the idealized protocol and some particular sub protocols that i think is relevant here and then i will go towards the commitment scheme um in particular i will focus on inner products because i think sort of the inner product is the cornerstone of all of these these protocols uh for for building uh r1cs satisfiability because we are always talking about you know over here we're talking only about linear relations so as soon as i prove in a product then i have everything else

um so um there is something that is already elastic in and that we know how to do and um these there are sort of the the sound check family of product and in a lot of these protocols um i am reducing a claim about an inner product from statements of size n to statements of size and divided by two and then i will uh sort of recurse over these instances until i get a statement of sets one for which in a product is trivial and can be immediately checked by the verifier so what do i have i have this protocol that runs log times that runs for local rounds and each round is public coin so at each round the verifier will send me

a random challenge and the verifier will be computing um the next instance and send like some messages along the way but the next thing such a instance can be computed for instance by taking a linear combination of the even and not coefficients or another ways for if it's just the left and right part of the polynomial now note that the left and the right part is not really streaming friendly because i cannot jump around the stream from there and zero coefficient to the end of the virtue even in all this sort of the mode streaming friendly way but anyway there are many ways in which i can fold recursively the stream and if you look how i go to the next step at the end i will end up sort of uh this term that will be sort of

dependent on the randomness of the verifier and in fact the last round can be seen as a motivated polynomial evaluation and yeah so i want to show you how this can be done but uh actually i don't know do you have questions so far okay okay let's let's go ahead and then i'll converge to these if uh i'll i'll go into more detail about the submucha protocol if you want but for now what i want to say is that this we know how to do it in linear time it's

easy to do in it in linear time if i assume random access and that i can store linear memory because i can take the polynomial take the linear combination and then take the linear combination again of the even and not coefficients and how many operations i'm doing i'm doing n divided by 2 plus 10 divided by 4 plus 10 divided by 8 and so on and so forth this is linear and so um the question is now is it n log n because you have log n rounds and is each round o n no because i'm folding once for each round so oops i'm going all the way um yeah and uh and so this is the reason

why subject can be done in linear time and this is also why um i said that we know how to do our proofs in in linear time um now the size of the instance is reducing each time that's fine yeah yeah now the question is how can you do the same in um in a space efficient way what does it mean to do it in a specific way again i have it means that i have this my instance i don't have it as once i have it as a stream no i have so the elements one by one like this and the way to do so is to keep a stack and then i take the elements and i start eating them one by one and as soon as i end up with two elements at the same level i will fold them and i will put only this element in the

stock then i will keep eating elements as soon as i have two elements at the same level that belong to the same sort of polynomial i will fold them together now i'm folding even and add coefficients together and i will replace it here then i will continue folding uh because there are two elements at the same level again and the algorithm goes like this and so on and so forth until i reach the folding that i need and these i can return in a string function now um how much memory am i using i will have at most two login elements in this stack so i'm still logarithmic how many operations am i doing well in order to generate this folding i will have to compute again and divide it by two multiplications plus n divided by four

divided by eight so on and so forth so it will be n the complexity in this case for a single round no so i will have a proving algorithm that for generating in terms of space it will run like um in linear time for each round so overall and logan time and there is a particularity however here and i guess in this general structure of the samsung protocol is that i can fix a memory budget no i can fix a threshold and say okay i'm going to run the approver in the space efficient manner until i reach a certain threshold where the instance can fit in memory and then i'm going to switch to the time efficient approver because the configuration is the same the output

messages of the approver are the same and then i will continue running with the time efficient one so i will have at the end some check protocol that we run as efficient as state-of-the-art um for like normal instances and if the instances are larger then i will have to resort to this sort of streaming techniques and so we end up with a pre-system that is again as fast as we know how to do it but it also you can just let it run if you have a larger instance so once you build this idealized protocol no and you have at the end i said one of these multivariate evaluations to deal with and um but i told you that i have a unified protocol and in fact what we do is um

the way that you sort of formalize this node is that you have an idealized protocol where you have this multivariate query in reality what how this is done you take a multivitamin scheme the approver commits to it at the beginning and then you ask for an evaluation of it what we show in the paper is actually how to reduce this query into a unified query and in reality you will just have to use a univariate commitment scheme why is this useful why do we care about this because we know how to build very efficient unified polynomial commitment schemes and verification for instance in a univariate commitment scheme is a is like two pairings whereas in the multivariate scene it's like log and

parents so um we're really changing a lot in the constant terms over here and i want to show you how this is done and so to maybe i want to open a small parenthesis on here on this um [Music] so i will stop sharing then i will [Music] start sharing from here okay so um when you have a multivariate when you have a vector

um you have these coefficients that i can write as in as bits so like this does it make sense and when you ask for a multivariate evaluation f evaluated in r1 r2 r3 and so on and until rn you're essentially um considering the sum over i of of all the bits b sorry you're as you're summing over f and then i have all the little bits here so i have b1 h2 b3 up until bn

and then i have r1 that is taken or not depending on the bit true that is taken or not depending on the bit and so on and so forth okay this is what i mean by a multivator evaluation this thing can also be written as the inner product between a vector f and this tensor product what is this guy this product 1rj is equal to 1 r1

r2 r1 r2 et cetera et cetera and you see um i have that one goes with the constant term r1 goes with this term r2 will be this term r12 goes with this other term and that's exactly what i have written here okay so if i go back uh if i were to go back to the slides like what i'm actually asking with the with the multivitamin evaluation it's uh it's really how to how to deal with this case so let me stop over here and shut the screen again [Music] okay

so this is the way that i'm mapping it as a sort of as a relation between vectors and again this is the way what i mean by this uh tensor product and the question is how do we implement it with universal numbers and uh the basic the idea is pretty simple actually um i can take a polynomial and i can split it into even order coefficients now if i think of the even and not coefficients the out coefficients are the one that will be multiplied by r1 no there will be one for which that bit is set and in addition to that um even no they have a half the degree and this is why what allows me also to do folding and in particular they can be obtained in this sort of well-known no already like that we use these tricks a lot in

the community that you can obtain an evaluation of even another polynomial by using an evaluation of f in plus and minus x a univariate evaluation of f okay and so in order to compute the folding i can compute it by asking evaluations of f in plus and minus x i can ask evaluations of f prime by relying on evaluation of f plus and minus x what does it mean it means that i can check and multivariate evaluation but in the following way i send you commitments to all of the foldings of the polynomial so that even a nod folding that i showed before then the verifier will send me a

challenge and i can the very the approver will have to check that then the first folding is generated correctly from the first one how by asking evaluation in plus and minus beta a random point and then i will do so on and so forth until i reach the last uh or the last folding and the last folding is really the is a constant polynomial so that will be the multivariate evaluation that i am looking for now this protocol is uh why does this buy as anything because in kcg i know how very well how to batch multiple polynomials evaluations over multiple polynomials and over multiple points here i'm doing three points and i have log n polynomials but the proof

will still be a single group element and verifying the proof will still be very efficient and this is sort of the big advantage that we have over multivariate techniques and also to say something more interesting you know if i have a multi uh multivariate iop if i have a multivariate protocol i said before it's easy to build a univariate one now we show that you can also do the vice versa and um and this is also again more efficient that what we knew so far in the literature if you think about other polynomial commitment scheme that are multivariate and that allow for a trusted setup um you still have lock-in pairings and in this case um you have only a constant number of pairings and it's interesting to well

going very technical um in pst the proof is works by um reducing the reminder over and over whereas in this case we're reducing the quotient over and over i'm i'm handling having an idea here but like there are relations between the univariate and very quote and at least for me it has been fun to explore them in this project and um and all these these foldings they can be done using a single passover initial stream why if i think about space efficiency whenever i'm building the end folding i have to go through the height folding like i all the previous foldings i have to generate them in memory so i might as well like use them and start committing to them or start working on the opening proof so i need only a

single pass over the stream in order to make all of these okay now from this you can climb up and yeah i have one quick question you would mention pst what does that stand for i forgot it's um no you just you just mentioned it just now right yeah it says it's the name that we use problem within scheme i forgot i don't know i honestly don't know where the acronym comes from it's a signatures of correct computation i think the paper that displays it okay thanks uh i don't know what is the acronym for but yeah the red the correct reference is a signatures of correct computation

and i mean you can once you have inner product as i mentioned before it's it's pretty easy to climb your way up to r1cs and uh whenever you have to have to deal with holography you have additional protocols um sort of a technical note here is that when you try to do streaming over um instances for like some sub protocols it is really non-trivial for instance when you try to build processing there are these luca protocols that are extremely useful and there are i would say two big protocols for doing lookups that we use today one is loop cup and one is memory checking vlookup we know how to do it in a strong fashion um

memory checking we don't know how to do it in a streaming fashion and um yeah it's uh it's it's not evident how to how to do this protocol in this way and i can go into oh thanks i see now the question um i can go into more detail if you want about this but for now um i just want you to sort of i just want to take like a sort of a bird's-eye view and you we built this sort of idealized protocol and now we we want to compile it down with uh with a polynomial scheme and we want to build it in such a way that it is elastic and we end up using kdg and kdg it has a it can be built in a streaming fashion again as a reminder in kzg you have this

commitment key which has like these consecutive powers and um in order to commit to an element you are just taking the linear combination of the coefficients of f with all these powers how do you do it in a string fashion well again f you have the coefficients one by one and um the commitment key also you have the coefficients that come like the elements that are coming one by one and uh it's easy to build a commitment in this case no you take the elements you multiply them take the elements you multiply them and so on and so forth the real problem is how to build an opening proof in case the g on opening proof is the quotient the euclidean quotient of f with the polynomial x minus alpha no if you consider this equation the remainder

here is f evaluated in alpha and the quotient is uh the commitment to the quotient is what constitutes the proof and then this proof will be checked in uh in the group um but how do we build this question and this we know how to do it's essential it's essentially what we call ruffini law to be fancy but it's like pen and pencil uh sort of a division because if the polynomial has low degree polynomial division can be done efficiently in a strong fashion how do you do it you take the stream of f again the coefficients one by one and then you keep the stream of the quotient by holding the last element and the the first the leading coefficient is also the first element of

the quotient and then by computing this formula which is again is roofiness law for uh computing the next element and then you throw um the previous coefficient as a as a stream and then so you need to keep only one element in memory so again you're keeping a very low memory footprint in all of this um you can also do batching and this is sort of uh related to a more recent paper of uh bonnie justin drake and others um when instead of considering the evaluation by the division of uh like our degree one polynomial no you consider the division by um the polynomial that is zero in all of these points and the area is the same

you just have to keep track of or more coefficient and in our case we remember that we need to evaluate only on three points so again this is also these batching techniques can also be used in our case and can also be done in a certain fashion once we built all of these we have been trying to implement this down like and in rust and we um we built in into artworks and this was quite an engineering effort because we had to build like uh all of these things into polynomial maintenance schemes you know we had to build kcg we have some students working on pst right now and um and and on the top we have to build like this tensor check know and all these

protocols are built in a modular fashion so that can be reused by other people for instance also in kzg we have these batching techniques that were not previously developed and um then on the top of it you need to build this sort of inner product no univariate inner product that we have and um from here you can build a snark or you can go up and build a pre-processing snark um and that's what we do so you end up having to build also luca protocols and ground product protocols we also have memory checking on the way and um and all of these know you don't have to implement it only once you have to implement it twice one time efficient and one space efficient and then you have to find a way of switching from one or to the other in the middle of the

protocol and so i guess like uh the out big outputs of this is that now like some parts of it we are we have been pushing them into artworks and uh one of the um one of the side effects of this is that for instance right now into the polynomial commitment library in artworks you have three different implementations of kcg um and one project for novices that would be fun i think is to try to merge them and to find like what can be moved into a single library uh that can have also streaming functionalities and batching on the top of what is for instance already used in marlin and the second thing that i wanted to share about implementation is

that down down to earth like to be like very concrete at the end of the day all of these streams are just iterators so you're literally embedding uh like when you end up working with them in rust and you want to keep a few use dynamic dynamic types then you end up having to embed the entire computation that you make in the tree in the type so it is a bit of a pain to get this done correctly but uh we you essentially have zero overhead for like composing streams and so for instance you end up having streams that belong to a matrix that you metrics that you multiply by other vectors over which are doing for instance algebraic cache and so you end up composing these strings and you end

up with these huge types but that is the price for having a very efficient protocol there are other implementations of space efficient provers however they rely more on the streaming um functionalities of asynchronous rust and that is uh is a bigger overhead and so we've been running some benchmarks and this sort of uh perhaps uh is sort of also related to the question mary gave at the beginning oh there is a question oh right okay thanks um so in practice while i would say that a lot of works in the past we're stopping at like uh

i don't know uh millions of gates um in our case we can go up until two to the 37 so we're talking about hundreds of billions of gates and um even if we try in uh with our own implementation to just run like a time efficient improver on a very large machine we cannot go further than two to the 27. so all of what you see over here is space that can be harvested only by using streaming techniques we also do it the same and if we run it for preprocessing we stopped a bit before two to the 34 but the morale is sort of the same but i wanted to sort of uh focus on one thing and that's that despite the time is a quadrat like there is this log squared factor at the end of

the day um that the graph is linear and it's linear for a reason because the bottleneck in all of these protocols are really the committed schemes um the group operations are really the public operations are really was taking most of the time and the log factor i don't even see it for these huge sizes and the same can be said for memory uh despite the memory it grows logarithmically once i set a good budget in this in our case was like one gigabyte you can um you can just let the prover run for whatever instance you care about and uh the spider is the login factor the the memory will stay very much constant and so um yeah um this is this is it so

wrapping up um we contribute with this idea of elasticity where you have an efficient prover and a specific improver and you can sort of merge them together and have something that can be um done for very large instances but can also run very fast i have a look at those performance graphs again yeah oops ah that is with parallelism yeah so how much parallelism uh is there a way of doing an apple

comparison with other implementations i don't remember i would say that this in terms of speed this is pretty much the same as spartan and in terms of parallelism i would say it's uh i don't know wait i i would say we're around 30 cpus okay so so not a a consumer accessible cpu okay yes if i have to i run benchmarks on my macbook pro 2019 over this and i'm like twice as low so if i go i would say that if i were to go for an m1 m2 i would get similar performances to these okay thanks that's the question um yeah i think i

think there is a there is uh there are some things that are really hard with streaming and one of them is for instance even just the order of folding is not is not immediate um again um folding by now i guess we know that even an odd and left and right is pretty much the same but if your implementation is already using uh left or right then there is no way i can do the tip streaming another another scenario is when you do kcg let me go back over here um [Music] when you do kcg and you're building the quotient um you need to start by the leading coefficient

because otherwise there is no way i can compute the division in a nice way in a streaming fashion what does it mean it means that all the vectors need to be streamed by the most significant degree to the least significant degree and these paradoxically for instance affects also the entry product protocol where in the entry product protocol in what is also called the grand product protocol i have to send you this vector of accumulated uh products no i start from uh the first one and then i multiply the two and then three and then so four and so on and four then i prove something about the last one um in these cases if i start from the most significant one then i have also put up

the entry product protocol so that the accumulated protocol doesn't start the accumulated product does not start from the least significant efficient but must also start from the from the most significant one so there is also some uh in that there there are really some some things that you need to think about streaming that really affects different protocols at the same time and um but if if you wanted for example to implement a scheme that was compatible with yours but that didn't need the large instances um then you you could have a simpler scheme that was compatible that was basically just the um the um just the the algorithm that you're using

below the memory threshold yeah yeah yeah for sure and i think uh yeah and i think really the contribution is for whatever is after that in any case of course yeah yeah it's just besides things like standardization you you um it might be useful to ah yeah yeah yeah and i think the only traditional thing is uh uh yeah the only additional thing is this translation this tensor check how to translate multivariate queries into univariate one that is uh yeah i guess uh some somewhat general and that you could do with or without streaming in a nice way yeah

yeah i guess um okay it seems like it seems like this like the idea of streaming i guess i think i like streaming across the internet like if you have a client that wants to use a powerful server to be approved for them i kind of like what kind of bandwidth and other requirements are required for the client in this case oh nice question um i think uh i don't know what kind of bandwidth requirement would be needed what i know is that you will need to make log passes over the initial streams so if you are taking instances that are this large you're probably transmitting gigabytes in terms of memory in terms of in terms of data

does this answer the question like yeah i have like i have to make log passes over the initial stream in order to perform a proof i think i guess you can you can stream it to some storage device that is close to you and then streaming and login times yeah and i think this log factor like i think it's really it would be very hard to imagine a protocol that does not need to stream over the instance multiple times no there is something about this proof that is also like binding to the fact that uh it cannot be extended no i have to make multiple passes over it to make sure

that this thing is not being extended further the proof cannot be changed on that side i don't know if this makes sense yeah that makes a lot of sense yeah cool um i i mean i guess the verifier has to check that it's actually getting the the stream the same stream multiple times but it can do that using commitments on the very fire is actually not needing any the very fire we didn't even care about doing streaming because the very fire is already succinct that's one of the pros so it's only the proof where that needs to do that and the prover needs to deal

with its own yeah so yeah the very fire has long memory and has low ground time because it's with pre-processing right so we don't even care about it i guess you also mentioned that i see this was about our r1cs but did you consider other authorizations other administration i think you're i guess i'm guessing you're thinking of plonk and in plank it's funny because in if i have to think about that then i have these matrices that are generally like thin but very long

so um i think all the protocols that would be in plank are somewhat already dealt in here in this pile of things uh so i thought about it i didn't work out the detail i would suspect that it would work okay and also that streaming might be even less uh less of a pain in the sense that with r1cs you take care of these uh you get additions for free but you get them for free because you're doing these matrix vector products inside the protocol and so i'm guessing that some of these uh these things will uh like you have um smaller matrices when you when you're doing plonk and and it seems easier to

do like matrix vector products and it seems also easier because you have so much redundant information in planck uh for working with so i don't know that i haven't worked out the details i had this little bug in my mind and uh this is the only thing that i can share it seems doable in any case i would be surprised that this this cannot be done does that answer the question oh yeah definitely so so what's the largest um sort of

kind of realistic circuit that you've tried this on not realistic we've been uh i've been trying to have students write hash chains because as chains you can very easily stream them but we're not still there for now we're just making dummy instances and uh and just like running them i see it yeah uh but it would be i think hash chains are sort of the sort of the shortest uh useful thing that you what you want you might want to test in the two battle tests so so what's the practical size of a

proof um i would have to check right now but we're talking about uh log group elements and uh with pre-processing i mean you mean yeah yes um let me open the paper we're talking about two to the 35 instances that take 27 kilobytes

okay yeah and then it's uh yeah it goes a bit linearly so yeah well with the log it yeah it goes say it again so so that's kind of comparable to bulletproofs or something like that yeah yeah yeah yeah there is this love factor that is always there i guess that um [Music] yeah but if you're doing pre-processing then you need all that additional load from other

subjects yeah okay uh i don't know if you saw the question in the chat ah no um oh you did already okay yeah yeah is there any chance your results could be extended to be backwards compatible with other schemes or why is it hard and yeah that was the answer that i gave before about

um i think it's really hard and there are like protocols where like really it depends on like you have to think about what ordering does one need with respect to the other for instance this was the case of the polynomial commitment scheme when i do streaming i need to keep in mind that i will be going big endian and uh when i'm using other protocols for instance the entry product protocol then i need also to build the state the proof keeping in mind that it's going to be beginning and the streaming part so yeah i don't know it's a difficult question i don't know how to do it are there any other questions i think if not

then i think we can wrap up thank you so much for the talk and sharing with us gemiini thank you thank you yeah thank you cool cool thank you