Mangrove - Wilson Nguyen

Transcript

hi everyone welcome to today's L session we are very happy to have Wilson green presenting mro won is from Sanford University and has been working on folding uh snacks for a while now uh he has contributed in very interesting papers including revisiting the Nova proof system and accumulation with homeomorphism and today we have been presenting mro with scalable framework for folding based KN so I hope you enjoy and thanks a lot with for being here thank you for inviting me uh so today I'll present Mangrove which is our new scalable framework for constructing folding based snarks this is Joint work uh with my co-authors from

Stanford so let's recap on what a snark is well informally it's a method to efficiently prove the outcome of some competation uh more concretely we'll consider an arbitrary arithmetic circuit c and a public instance X the claim is that there exists some witness W which indeed satisfies the circuit in particular the circuit when evaluate on these inputs evaluates to zero it consists of a collection of algorithms in particular a setup procedure which takes in the security parameter and outputs a structured reference string in a pre-processing step this structured reference string as well as a description of the arithmetic circuit

outputs a proving key and succinct verification key now the prover will output a succinct proof Pi for which the verifier along with thein verification key public inance and this sucin proof will check it and output accept or reject they satisfy several Key Properties in particular the usual Notions of completeness knowledge soundness succinctness and optionally zero knowledge in particular completeness states that for all honest provs the verifier should accept knowledge soundness states that for all malicious provs there should exist a corresponding extractor which if it if

the malicious PR convinces the verifier we should the extractor should be able to succeed in extracting a witness that satisfies the circuit succinctness means that the proof is small in particular sublinear in the size of the circuit and the verifier runs in time uh polinomial in the public instance and also sublinear in the overall circuit size i' would like to reference a quote from a seminal work in 1991 in which the author stated that a snark should allow a single reliable PC to monitor the operation of a herd of supercomputers now while over the past several decades since 1991 we've made

significant Improvement in particular concrete improvements to the performance of snarks were still a long ways from actualizing this dream in particular to do so we would have to prove circuits of incredible size so where do existing constructions of modern sorry existing modern constructions of fici snarks fall short of realizing the Dream well I'll classify these existing concrete snarks as monolithic snarks in particular snarks that operate over the circuit as a whole they require that the pro memory is linear in the circuit description they often times require a

trusted setup which produces a linear size structured reference string now for circuits of very huge size linear approv memory as well as a trusted setup limits the amount of parties that can actually participate in such setup or approving procedure and hence they provide barriers to proving very very large circuits however there have been existing works that produce more efficient provs but the issue is that they require clusters to actually be concretely efficient there are also streaming snarks which do not suffer from this linear Pro memory but indeed have trusted setup and linear size structured reference strings and most importantly their provs are ASM totically and

concretely slow when compared to these other monolithic snarks so is all Hope Loss well there also exists another class of snarks called incremental snarks so these are the usual Notions of incremental verifiable computation or proof caring data they these incremental snarks suffer from none of the drawbacks of Monolithic snarks however there is a huge caveat in particular they're only concretely efficient for very repetitive or uniform circuits so what do I mean by a repetitive or uniform circuit simply that the overall circuit consists oop sorry simply that the circuit consists

of the same subcircuit repeated multiple times in particular they're just the same subcircuit just connected to one each other all the way leading to a single uh circuit output so to illustrate the issue with attempting to use incremental uh snarks when trying to prove circuits consider the following uniform or repetitive circuit right in particular I've just enlarged this image incremental snarks operate by proving each repetitive subcircuit the exact same circuit one by one recursively all the way till the final output however when we consider arbitrary circuits this arbitrary

circuit consists of many distinct subcircuits as well as arbitrary wiring requirements within the circuit and hence applying the same strategy that incremental snarks normally do would not apply in particular it's really hard to partition just arbitrary circuits into a series of identical subcircuits so if only there was some way that we could benefit from incremental snarks while being able to handle arbitrary circuits as other monolithic snarks do and that's exactly what we do and hence we are able to recover all the benefits of incremental snarks so in Mangrove we introduce several new techniques which allow us to

do so we introduce a uniformizing compiler which is able to reduce the satisfaction of an arbitrary circuit to a sequence of identical steps for which we can readily apply incremental snarks particular proof caring data or IVC to prove however there is a major caveat with immediately using the uniformizing compiler it's that each of these steps contains a pretty expensive cryptographic operation which would make this strategy practically infeasible however by simply inspecting each of these steps and treating them as a member of a polinomial relation which we'll discuss further will be able to

avoid this expensive cryptographic operation and be able to recover an efficient snark finally we introduce folding schemes for polinomial relations in particular we're able to reduce the task of proving many of these identical steps to the task of proving a single step now we can readily apply incremental snarks to repeatedly execute these fooling schemes and we're able to recover our overall Mangrove snark so what do these techniques actually get us well by applying these tricks and techniques plus existing incremental snarks we're able to obtain the mangrove

snark a snark that has a constant size transparent common reference string so in particular we do not require a trusted setup it maintains a linear proving time particular a linear number of field and group operations it requires only constant proven memory it can be viewed as a streaming algorithm which only takes two passes over the input data it's readily Parable and hence readily distributed and also most importantly has great concrete performance which I'll discuss a little further at the end so how does this uniformizing compiler work well let's take a detour into our

interpretation of plish arithm isation this was introduced by the pl paper in 2019 in particular let's consider this arbitrary circuit here which has uh pin values which are field elements and also wiring constraints here I denoted the wiring constraints as different colors in particular we would want W1 to equal to W5 and W6 W7 equal W8 and so on and so forth let's see how we can somehow encode this arithmetic circuit as concrete vectors in particular here I've laid out all of the gates one by one we can encode the type of gate using a

selector Vector in particular one for a multiplication gate or zero for an addition gate furthermore I've laid out all the pin values as this Vector Z which I'll refer to as the extended witness Vector particular consists of the instance and also the extended witness now if the selector Vector is one we would expect that the corresponding Tuple satisfies a multiplication constraint while if it's the selector value is zero we would expect the corresponding twool to satisfy an addition constraint okay but how do we actually encode these sort of copy constraints or these sort of wiring within the arbitrary circuit

well the plunk paper made a key Insight that when you want to check that W1 is equal to W5 equal W6 it suffices to actually check a cyclic permutation is equal to itself in particular notice I have a tuple here here with the three pin values and all I've done is applied a cyclic permutation now it turns out that checking that this tupal is equal to this tupal suffices to check that they're all equal to each other particular we apply a cyclic permutation here and furthermore to check that these uh pin values are equal to each other similarly we just check a cyc permutation and also furthermore we check another cyclic permutation so in order to check that

the extended Vector satisfies all these sort of copy constraints or these wiring constraints we simply have to check that the extended rightness Vector is equal to this following permutation of itself particular that Z is equal to a permutation of Z here the permutation just consists of each of the cyclic permutations composed of each other so what we've done is we reduced these sort of copy constraints to simply just a permutation check to checking that this extended witness Vector is equal to a permutation of itself so one example of a concrete encoding of a permutation is simply just the permutation of the corresponding indices so here I just have an inex

counter which counts from 1 to 12 and by applying the permutation we now have a concrete representation of the permutation Vector particular all we've done is just permuted these indices okay so in total what is the plation so here I've just stacked all the corresponding vectors on top of each and segmented them into four different chunks the number of chunks here is just arbitrary the plish circuit encoding in particular consists of just a selector vector and a permutation Vector as well as a corresponding gate polinomial which checks the sort of addition or

multiplication constraints uh for those who are more familiar with plish ionization this can also just cover any custom Gates so this extended witness Vector satisfies the pish erization if and only if Z is equal to a permutation of itself so these are to handle the copy constraints but also that the gate checks are satisfied in particular uh for every uh selector chunk the gate polinomial when evaluate on the respective chunk of the extended witness Vector evaluates to zero so this will simply just check the multiplication or addition constraints now if we look at the plish circuit encoding it seems to already have a very

uniform structure which may suggest that maybe we can just partition these vectors and then immediately obtain something we can apply an incremental start to however there are a couple barriers but first off let's consider the gate checks right so here I've simply just partitioned the extended witness vector and the selector Vector into distinct chunks of course these chunks are arbitrary you could consider where it spans two chunks or three chunks or four chunks checking each of the gate the gate pols uh equal to zero is independence of every other chunk and so we can just do this one by one going down the uh xend witness and select your vctor so gate checks don't actually provide a barrier to viewing this as a

uniform computation however the real issue is when we deal with copy constraints in particular if we try to apply a similar strategy of partitioning this extended winess Vector checking the permutation check or checking the copy constraints would require very non-local checks in particular we would have to check some wire value or some pin value is equal to another pin value way off into the other side of the extended witness Vector so going one by one won't allow us to actually recover a very repetitive circuit that check copy constraints so if only there was a way that we could just check these somehow Global copy constraints but only by doing a computation that is like chunk by chunk

particular independent of the other chunks well the plun paper has this beautiful theorem which it's in the appendex in particular let Z and uh the the permutation Vector just be some vectors of field elements in particular where the permutation Vector actually encodes a permutation then Z is equal to a permutation of itself if and only if the following products are equal as pols in particular we can notice that a product has a very very um local or repetitive structure in particular it ends up being each step of the product

ends up being independent of the rest of the steps particular we don't have to Lo gather local values sorry sorry Global values so let's see how we can recover sort of a uniform or repetitive set checks just from this sort of permutation argument well let's query this identity over a random Alpha Beta now this reduces to a concrete product in particular we have to check that one is equal to the following product the key Insight is that we can arbitrarily partition this product in particular if this product is over n elements why don't I just do five

elements five elements five elements and so on until I obtain the overall Grand product so we can just partition the product into a series of local products which I'll denote by P1 through PC to denote C chunks now all we have to do is calculate this local product one by one and also calculate the overall Grand products by multiplying P1 by P2 by P3 all the way to the end and checking that the overall Grand product is equal to one so now we have enough to discuss how the uniform compiler operates in particular here we have the arbitrary circuit as

before in a pre-processing step will actually commit to chunks of the plish circuit coding so here what I've done is I've Chunk Up the plish circuit en coding which consists of the selector vectors the permutation Vector Etc and also chunked up the extended witness Vector so now in a pre-processing step the verification key simply just consists of a streaming friendly commitment to each of these chunks in particular you can consider like a Merkel tree or a Merkel Damu hash in the first step the prover similarly commits to its extended witness Vector using a streaming friendly

commitment the verifier will apply back with the random challenges we stated before and now this is literally the uniform compiler in particular by introducing one more round here we've effectively reduced the satisfaction of this arbitrary circuit to just a series of repetitive checks in particular All That Remains is that the prover will just send over the candidates uh plish circuit encoding as well as the extended witness vector and the verifier just has to perform the following checks so here f is simply just a polinomial map you can think of this as just a multivariate map which consists of just a bunch of multivariate pols for

each index of the vector now this polinomial map will simply just calculate the gate check uh that corresponds to that particular chunk as well as just computes the partial product so for all the chunks we just check that this polinomial map evaluates to zero uh furthermore we have to make sure that for each of these partial products if we take the grand product over them it's equal to one and also we'll have to recompute the commitments to the C encoding as well as the extended witness vector and check that they do indeed align with what we saw in pre-processing as well as aligns with the commitment that we saw in the PR's first

message now this is already a series of repetitive checks however the issue here is that sending these vectors not naely right incurs linear Communication in particular the circuit encoding is just the size of the overall circuit and the extended witness Vector is the size of the instance plus the witness so by itself this here does not actually recover a snark when inste recovers a narc so basically a non-interactive argument of knowledge that is not succinct however as Illustrated before these set of checks are incredibly uniform in particular just very repetitive checks so we might actually be able to apply an incremental snark so IVC or proof carrying data to

actually just prove knowledge of this corresponding message uh that satisfies these checks instead of actually just sending these vectors in the clear so let's see a first attempt at constructing a snark so the goal is to construct a repetitive circuit such that it takes in as input these uh corresponding chunks and outputs the overall commitments to the P coding the extend winess Vector as well as computes the overall Grand product okay also additionally checks that the polinomial maps evaluated to zero so this is a just a repetitive

circuit so what does this repetitive Circuit look like well it consists of a bunch of subcircuits just repeated over and over and over again in a tree like manner so in the base case we check that the polinomial map evaluates a zero on the corresponding chunk input as well as we compute a sub commitment to each Chunk in particular like we yeah we'll produce subc commitment uh to a chunk of the P occurring as well as a chunk of the extended witness vector and then in the recursive case in particular the subcircuit uh recursive subcircuit we'll just simply recursively compute a Merkel tree over these subc commitments as well as compute uh recursively compute the

overall Grand product so in particular if we take in L input uh nodes so this is like a overall this is just a tree which has lity we just compute a hash over the sub commitments and also just take a product of all the products we've seen so far and So eventually at the very top node we'll eventually just compute the overall commitment to the pl coding the extended witness vector and also the overall Grand product uh so what goes wrong now if we just use an incremental snark to prove this repetitive circuit well it turns out that we'll actually obtain a snark that meets all of our ASM totic requirements however it would be completely infeasible to run this snark

in practice in particular representing the commitment or the subc commitments to each chunk would be incredibly expensive in particular we would have to represent the commitment algorithm as a concrete circuit so imagine doing a hash for every single field element in the chunk or doing a Peterson commitment for every single element in the chunk so it turns out that this will have like hundreds to thousands of times overhead over our ultimate final solution and so in fact uh we're not going to do this because this would be incredibly efficient inefficient instead maybe we'll find some way that we can actually avoid doing this commitment operation and replace it with a much cheaper operation

so let's see if we can somehow avoid this expensive commitment operation well in order to actually discuss what we replace it with I'll have to take a brief T detour or review of folding schemes in particular the task of the folding scheme is to reduce the task approving L statements to the task of proving a single one so what does that end up looking like here I have a folding prover and a folding verifier the folding will take L instance witness pairs of a relation and the verifier will simply only take the corresponding L instances after some interactive

protocol the folding prover will take its original inputs as well as the transcript and output a single witness correspondingly the folding verifier will just output a single instance X now at some later Point theover can send over this witness and the folding verifier simply just has to check that this instance witness pair belongs to the original relation now what are the key properties that a folding scheme must satisfy in particular if we view the folding prover plus this additional last message as an argument for the relation repeated L times and and we view this folding

verifier plus this final check some people refer to this final check as the deci these can both be viewed as aover and a verifier for the argument for the repeated L relation in particular this will end up being a complete and knowledge sound argument for the relation where we repeat it l times so the issue with um folding schemes is that in order to represent these sort of schemes or algorithms in a circuit we'll actually have to have an explicit description in particular we won't we won't be able to just obtain an argument in the random Ora model and use

this in a circuit so what we'll have to do is somehow obtain a folding scheme in the standard model so what we can do is apply Fiat Mir to this interactive protocol to produce a non-interactive folding scheme so first now instead of interacting the folding prover will just simply output a witness W and a folding proof pi and the folding verifier will take in this folding proof pi and also output a single instance X however this is in the random Oracle model so we can't represent it as a concrete circuit so we'll apply a hortic assumption in particular all prior works on incrementally verifiable computation as well as recursive snarks and proof carrying data all make this horis

assumption in particular by instantiating an argument in the random Oracle model with a concrete hash function so replacing a random Oracle with a concrete hash function they assume that they'll still maintain a knowledge sound uh argument and so we'll just simply just replace this random Oracle with a concrete hash function and now we'll obtain a folding Pro and a folding verifier that could be represented concretely as a circuit so what we'll end up actually doing is replacing this commitment procedure with just a cheap folding verifier so instead of the following repetitive circuit which takes in just

the chunks of these vectors recomputes the commitments as well as the overall Grand product we instead have a repetitive circuit that takes in commitments to each of these Trunks and then just computes the same exact U overall commitment and also partial product but now we have an additional folded instance X for which the prover can finally provide a witness and so in particular we'll be able to move the commitment operation to outside the recursive repetitive circuit so what do these instances actually look like well let L be some linearly homomorphic commitment you can think of a Peterson commitment for

example uh Additionally the repetition of a Peterson commitment is also just a linearly homomorphic commitment so here uh instead of the uh inputs to the circuits being these chunks instead is a linearly homomorphic commitment to the chunks and now the witness values are simply just the chunks themselves the requirement of this relation is that the polinomial map will evaluate to zero as well as the instance being the linearly homomorphic commitment to the witness and so now instead of having this uh expensive commitment operation will instead add to the

recursive case a folding verifier and now in the base case we don't do a full commitment uh to a sub commitment instead we just do a constant number of hashes in particular we just uh check that one field element is equal we take a hash of a single commitment so you can imagine this being a group element so a single hash of a group element and another hash of a single group element so now the overall repetitive circuit will actually be independent of each chunk size so the recursive overhead will end up being independent of the size of the vectors and so we can just choose the size of vectors which meet our particular memory requirement or optimize our proving speed so indeed with this repetitive

circuit it's completely feasible and actually incred efficient just to apply an incremental snark to prove this procedure in particular all we need to do is just compute a bunch ofing verifiers calculate some products and take uh just calculate a Merkel tree over the inputs so it's very very cheap so what is actually this computation at the nodes so I briefly eliminated that this instance is simply just a commitment and the witness is just the just the raw vector uh however it satisfies other requirements in particular so what we saw before the instance is just a linear homic commitment to the witness which is just a vector we required that the

polinomial map F evaluates zero and also that this commitment relation actually holds up well we can view this uh more abstractly as the following relation in particular the witness is just a vector over the field the instance is just any linearly homomorphic commitment of the of of the witness and also just that you have any arbitrary polinomial map F and that the polinomial map F evaluates to zero on the witness now the issue with this sort of relation is that we won't actually be able to design a folding scheme for it so we actually have to consider a generalization which in in instead of

checking that the polinomial map EV Valu to zero we'll have to actually handle arbitrary evaluations uh in particular instead of checking that the polinomial map evaluates zero we'll actually check that the commitment to this evaluation is equal to a commitment in the instance so now the instance consists of two commitments one to the witness Vector but also a commitment to the evaluation or the claimed evaluation and it turns out that this sort of polinomial relation will actually be able to design a folding scheme for it and also in particular this polinomial relation will actually be General enough to capture a lot of the other existing schemes so for example

like hypernova or protostar and so indeed this is a pretty powerful generalization of existing sort of relations that folding schemes fold so uh how can we actually construct a folding scheme uh for these polinomial relations uh first off I just want to say that uh folding seames by themselves are a pretty active area of research in particular in the last couple years we've seen a Cambrian explosions of works all starting from the original BMS paper which introduced accumulation schemes but also really took off when Nova occurred so Nova introduced the

first folding scheme for committed to relax rncs and since then there have been made consistent improvements to the efficiency of these folding schemes but but the issue is that we need folding schemes in particular for polinomial relations not the exact relations that were provided in these prior works and what's interesting is that by designing a folding scheme for polinomial relations we actually be able to recover a lot of these prior works so indeed it is a sort of generalization so in order to cons uh discuss or construct a fing scheme for polom relations we'll actually have to go over some background so the construction I present here will

actually be a generalization building upon recent work particular accumulation without homeomorphism and also the Proto Galaxy work the issue is that uh these uh specify very restricted structures but we'll need ones for polinomial relations in particular we'll need it just to hold for arbitrary linear Maps so I'll try to more generalize these prior constructions so let H be a subset of the field in particular you can consider any arbitrary subset that just has L inputs you can imagine just one two three for all the way to l v is the corresponding Vanishing polom for the set in particular it's the polom

of least degree that just vanishes on every point in this subset furthermore we'll let L1 through LL denote the corresponding lrange basis uh for uh for this Set uh we'll need the following theorem to actually prove sorry for we'll need the following theor to actually discuss how the folding operates in particular let F be any arbitrary polinomial map or degree D you can imagine this being like some rncs relation or CCS relation uh for all X1 through XL so these are simply just vectors over the

field there exists course responding vectors Q such that the following expression holds over indeterminate y now at first glance uh this may seem pretty opaque uh but we'll break it down into its individual components in particular what we've done here is we evaluated the polinomial map on another polinomial map uh of the XI in particular we can see that this individual polinomial evaluates to XI on every hi so when we evaluate on H1 for example this overall expression will evaluate to

f of x X1 similarly here we can see that this expression here will evaluate to F of XI on hi and so when we consider H1 through H2 all the way to HL this whole entire expression on the left side will actually just vanish on every point in h and hence we'll actually be able to derive these coefficients simply by just dividing by The Vanishing polinomial repeatedly for every index of the polinomial map and so these qjs will simply just be the coefficients of the corresponding quotient pols so now we have enough to actually

discuss how we can concretely construct these folding schemes in particular we'll derive the vectors q0 through q d lus one L which in particular are just the coefficients of the quotient pols we'll send over commitments linearly home commitments to these quotient coefficients the folding verifier will send back just a random field element R and now the folding will simply just output the corresponding random linear combination of its witness inputs particular just the evaluation of that polom and the folding verifier will similarly just take a random linear combination of the corresponding input commitments and now the fing improver

will simply just send over this corresponding instance and we'll just check that the instance witness pair belongs to the original polinomial relation so now what we've done is we've actually just constructed a folding scheme for polom relations and now we can actually concretely put this folding verifier into our repetitive circuit so uh what's the analysis of this protocol well let's define the maps as before and remember we just we described how to construct an argument uh for the polinomial relation from the fing prover and fing verifier as before it turns out that if you take the Fiat

Shamir of this argument you'll end up recovering a non-interactive argument in the random Ora model for the polom relation repeated L times so this is what we stated before about the properties of folding schemes now it turns out that this is sufficient to recover a folding scheme for polinomial relations and now by applying an incremental snark in particular proof carrying data implemented with our particular folding scheme will be able to obtain the main grow snark but all is fine and dandy sure we recover a snark but how does it actually perform concretely well we looking discuss a

couple performance metrics in particular this is estimated performance so basically I just constructed uh subcircuits sorry I constructed circuits for the um uh for sorry the subcircuits of this repetitive circuit and just recorded the cost of proving these individual subcircuits uh for the mang Grover in particular with estimates from a MacBook Pro for two to 24 constraints the mro approver will take 2 minutes and under 400 megabytes of memory while for two to 32 constraints it will take eight hours under 800 megabytes of memory now this is all fine and dandy independently how do we know whether this is congruently fast or slow well it turns out that this is

actually Improvement on existing um monolithic spks in particular uh we actually improve uh the the proving cost for circuits that the Spartan can actually prove now it's a little bit hard to do these sort of comparisons because when considering circuits of incredible size uh most monolithic snarks just simply run out of memory so we simply just can't Benchmark according to those sizes but there does exist one monolithic snark which is a streaming prover with low memory however it's sort of an apples to oranges comparison in particular Gemini requires trusted setup but also a structured reference string of linear size so if you had a 2 to the 50 size circuit you would also need a

corresponding two to the 50 size structured reference string uh but this will just provide a sort of comparison uh between our approver so Gemini running on a ec2 large instance for two to the 24 constraints will take 19 minutes and 1.2 gigabytes of memory while for two 32 constraints it will take over 80 hours with 1.35 GB of memory so even when comparing to other existing streaming Starks the mango approver already has an order of magnitude Improvement in terms of proving speed uh so but alas how do our proof sizes compare well if you take a look at our uncompressed proof sizes they'll

actually be incredibly large uh but it's okay using similar techniques uh to the original Nova paper will just be able to compress the proof size using an existing transparent snark consider Spartan you may similarly use a non-transparent snark sort of like plunc and Marlin to also compress but here we wanted to keep the sort of transparency requirements so we used uh uh sorry we used sparton to sort of compress the proofs and so we end up looking at like around 13 to 14K uh kilobytes in terms of the proof size so the key takeaways of our Construction is that we designed a uniformizing compiler which is able to reduce the task of proving an arbitrary

circuit to a sequence of identical steps by really treating these identical steps as a member of a polinomial relation we'll actually be able to avoid the expensive cost of of committing Within These recursive circuits and finally we designed a folding scheme for polinomial relations which uh we can readily apply an incremental snark to obtain our overall uh main grow snark and that's my presentation however uh there will be updates soon in particular the uh we do not discuss the generalizations of accumulation of that horm and protostar currently in the version of the paper Additionally the

benchmarks are with respect to a more inefficient concretely but ASM totically more efficient uh folding scheme in particular we actually construct a tree sort of folding scheme in the original paper however my belief is that um by incorporating the sort of generalization of Proto Galaxy and um and accumulation without homm will actually be able to obtain a more even more concretely efficient prover in particular we'll have to perform half the number of group operations and so my prediction is that the subcircuits will end up being a lot smaller and so we'll have improved uh memory performance as well as concrete proving performance so look out for updates soon

that's uh that's thanks for this presentation it was great uh I need to dive much more in your paper uh I have to confess and I will do so because I'm really interested about your poal folding scheme um I had a couple of questions if you don't mind some might not be exactly about folding but i' I think that interested um so a third question I have is I don't know if you read uh Ramen pasta It's a folding paper uh that's quite recent uh uh they introduce a notion of conditional folding uh and they do so to be able to remove the real

from the verification from the decision step um I don't know if you had a look at this paper I I did yeah so I had so I did uh try to look at the paper so they do Target the first thing is that they target a different setting so it's a little bit hard to compare uh but it'd be interesting to see uh so I think by removing the random Oracle Outside of the outside of like the folding step they actually require an additional argument to somehow you know perform these random Oracle calls outside so I'm not to I think they end up not recovering a succinct argument in terms of the number of random oracles but I could be mistaken the pro the the paper

is quite dense so it's a little hard to to to read thoroughly so I'm not sure uh what they ultimately recover um I thought it was quite interesting and so I was wondering if you thought that uh conditional folding could be could be applied more gener uh in most schemes including us or not but I I agree with you the the P is quite dense so it's not it's it's not an easy question uh yes because I believe at the end they state that they somehow use some other existing Works to obtain like um uh to to obtain sness but I'm not sure if this means proof sness or verification sness because when you

remove the random oracles outside of these arguments you'll have to actually perform the random Oracle call somewhere right and if you do if you do recursive proof system or folding to do these random Oracle calls then indeed you've already just you're doing folding anyways and so there somehow these these random or calls have to be instantiated so I'm not I'm not totally sure but you know I think it'll take take some more time to digest work thanks a lot um so the question that is a bit tangent to folding uh is because I worked a bit on it a while ago uh in your in your first uh third of your presentation you were talking about the difficulty of having so many commitments uh I think it was just slide 19 when talking about your

Universal compiler yeah uh oh slide sorry 192020 yeah about here sorry what there's a lot of animations okay here yes yeah yeah um so uh it is not really it's not folding but it's aggregation which is not so there is a small intersection between the two so I if you don't know it's not a problem uh uh a few years ago there was a paper called snack back uh which was looking at accumulation and so we treated this problem of uh commitments um by using basically some check some check protocols um to aggregate different

instances of the same Pro system so I was wondering if if here we could do something similar of course it wouldn't be on different instances but on different chunks uh and so yeah uh wait so are you saying that um so instead of doing yeah so instead of doing a folding instead of doing folding from now on uh because he wants to reduce the number of commitments uh there could I I could see potentially another another thing we could do which would be not folding but aggregation uh on the chunks uh by using uh techniques such as sback it would still be quite expensive because in

snackpack you're using uh commitments of commitments uh you're using basically um oh I know what you're referring to you're referring to like the um it's like the doubly doubly homomorphic Comm or something where it's like you do it's like pairing based right yes yes that's what I was going so it's quite expensive because you you're going to have to GT elements uh but uh I thought that this could be a good Avenue to look at if you're interested in aggregation uh yeah so the thing is though in order to gain a benefit for this so what's nice right is that in this sort of description of this current inefficient snark each subcircuit can be evaluated independently of the other one

and so when you start aggregating the cost of commitments you'll have just one commitment being a commitment to like multiple sort of sub chunks um and so then you you sort of like what's nice right is that the memory requirement can just be you know the least number of these sort of subcircuits so you have to keep in memory um that's one comment another comment is that um what uh when you operate over these pairing uh using a pairing based commitment scheme you have to operate over a cycle of Curves which is caring friendly so that also introduces an overhead in terms of the size of the fields but also the group elements um and in addition it's not just the task of sort of proving that this commandment operation is satisfied

but also the corresponding um uh polinomial F check and so what's interesting is that in the ultimate circuit that we recover so just go here what's interesting is that in the ultimate C circuit we recover uh you won't actually have to prove the execu of the function within the sort of recursive circuit itself this is sort of handled inductively by the folding scheme and so it's I I think like uh being able to maintain sort of um paing friendly field sorry paing friendly free fields for example like the posa cycle uh but also like you know being able to handle each subcircuit independently is a a sort of nice aspect um and so what's yeah what's kind of

what's kind of interesting is that this recursive subcircuit actually ends up being independent of the chunk size and so you can sort of scale the chunk sizes also similarly um without actually affecting the the overall recursive cost yeah uh yeah that's would have been my last question about the chuning strategy but uh I guess the smaller chance you have the more efficient you you get but uh you would have to consider I'm not sure how you would tweak the security parameters to increase the depth of your recursion uh uh oh sorry uh the depth so so yeah so currently um in order to be actually knowledge sound for polinomial length um for polinomial length extended witness

vectors you'll always have to have the recursion depth um in particular the depth of this uh repetitive circuit to be constant and so in order to have a constant depth you'll actually have to have an aity of the recurs circuit particularly if you view the circuit as a tree uh to be linear in the security parameter and so that can ALS you know and then what people consider to be linear in the security parameter is also a matter of like sort of uh you know concrete preference uh but in particular this sort of um sorry let me get to it this sort of aity so here we included the tree aity as this sort of member K what's interesting is that um the aity

doesn't actually concretely affect the the pring performance that much um it's because they ends up ends up being that these the cost of representing the group elements for these sort of recursive circuits ends up being like pretty large in terms of like a constant overhead uh and so minimizing these things will actually create a more gap between different arities but what different aties provide is they provide a better sorry what better parallelism particular if your aity is 32 then you can actually just have 32 independent subprocessors um just like Computing the snark and so TR off with the aity is that sure you get a higher memory requirement because each like recursive

subcircuit has to handle like a folding of like 32 instances for example uh but you get more parallelism so this is like a sort of trade-off Factor but what's interesting is that um the the sort of first order uh impact sorry the thing that like affects the proving performance the most is simply just the size of each chunk um because each chunk uh the sorry I say it the less chunks you have overall because the the greater the size of chunk the smaller the overall recursive tree will end up being like it's like a direct order of magnitude smaller and so larger chunks the more efficient so you'll be able to recover a more efficient snark but then the proof sizes are larger because we did the sort of bowling scheme but then

you can always apply um The Spar compression and so the the gap between these proof sizes is not so large so it's it seems like the best strategy is just to have um a very large chunk size and then just choose the corresponding a parameter that matches your your best setup and awesome thanks a lot uh we have a question from zans what implications do you think Mong grve has for zml and privacy preserving machine learning tasks oh sorry give me one moment here sure trying to see so trying to see the chat okay so what implications uh implications do you think that main grow will have for zkl and privacy preserving machine Lear test

uh well I guess it depends on what type of circuits you're considering to prove in zkl in particular if you have a very very large I don't know like matrix multiplication or a very very large overall circuit for I don't know proving that you've trained over some committed data uh then you can just use Mangrove to to prove this computation in a way in which uh you can actually uh have lower memory requirements and so I am not sure what the overheads are for zkl uh but in general if you have some very large circuit uh that you can't keep in memory then this will allow you to do so yeah in my experience memory is

uh is the next difficulty with uh with proving time I'm part of the ZK VM project uh and we we have a a ciruit of size 2 2068 uh some in this order of magnitude uh and I think we are using 10 terab of Ram uh so it is uh there's no optimizations at the moment uh but uh it is wow yes uh so your order of magn slower than that uh so it is quite interesting uh proof size as you shown and as research have has shown the past few years is not so important because you can always um add an extra snack on top of it to to compress your proofs and

uh proof uh proving time uh more and more people are releasing uh linear Pro uh linear proving time and I think that's the best way we we can reach uh so yeah uh memory I think is the next uh Dimension that people should be looking at and that's why this paper is so interesting right now yeah I think there's there's tons of improvements that can be made to the existing uh existing like sort of benchmarks of Mangrove in particular I just sort of generalize um what we had in the revisiting uh Nova paper in particular where we just cycle between the two curves uh and so I believe you guys

recently implemented cycle fold and so with psycho fold and also with the sort of the generalization of Proto of Galaxy that we consider I believe Mangrove can actually be very very competitive in particular uh by doing this sort of cycle we also introduce more memory overhead right because you have to represent uh accumulators of or I guess some people call them accumulators some people call them committed Ines right of the curve one over curve and also curve two so we have to sort of carry that uh up the proving tree um but um if we use cycle fold we'll be able actually minimize probably overall C circuit size also what's sort of killing us is that um in the current Benchmark we use tree

folding and so we have to pay for the random work calls as well as the sort of all the levels of this sort of folding tree well Proto Galaxy is just a single round and so I I do think that there's actually going to be a pretty big Improvement in performance but you know updates soon so we have to sort of try out those benchmarks yeah s oh I was just saying we we'll be definitely looking forwards to it yes yeah so oh man I feel like uh someday hopefully we'll be able to prove circuits of very very very large size like I'm kind of impressed that um a two to the 26 or two oh I guess it makes sense those are very very large numbers and so monolithic snarks don't immediately like scale very very well so

the terabytes is kind of understandable yeah it's a very large unoptimized cits for zvm so we we have hundreds of uh hundreds of columns selectors uh so it is uh the dkm projects are monstrosity for for snacks uh so it is a special case yeah so here I I presented um yeah so here I presented the case in which we just have uh one selector Vector of course you can just imagine that uh the chunks are merely just chunks of the multiple selector vectors and then the gate polinomial just takes in each of the selector vectors yeah particular so yeah so here it's just we presented just in

our paper the simplest version of PL generalization but of course you can immediately generalize if you have like more columns and so it seems like it's it's almost readily just like uh you know any system that use sort of plation you know it seems almost like readily like fitting so it's quite it's quite close yeah so I don't see any other questions in the chat so thanks a lot for coming with we we're really happy to have you today we'll be looking forward to your updates and your next papers and thanks for for being here have a good day okay C