zkStudyClub - Quarks

Transcript

good morning slash good evening everyone uh welcome to the latest edition of zk study club today we're excited to welcome cernatheti from microsoft research and he's going to be telling us about quarks uh quadruple efficient transparent zk snarks so uh really excited to have you here sarnath thank you very much for taking the time and with that the mic is over to you thanks alex thanks for having me and this talk is about quadruple efficient transparency snarks uh this is joint work with jonathan lee and uh first let's uh dig into what's what we call a cork uh so first it's it's a transparency case not so

what this means is that uh uh there's no toxic waste and the setup uh uh involves for example picking a group where the discrete logarithm is hard there is no trusted setup uh and all of you uh probably know z case not so it's it's an argument of knowledge uh meaning that it's a protocol between approval and a verifier uh the prover is interested in proving the knowledge of some secret fitness such that some circuit outputs won when given the secret madness and some public input x as an input second uh it's zero knowledge which means that the proof does not reveal

anything about the witness beyond what's implied by the statement third it's not interactive the proven just sends a single message to the verifier uh finally it sucks and there are two forms of success that are generally considered one is that the proof is sub linear in the size of the circuit and the verifiers runtime is also sublinear in the size of the circuit uh so now let's look at what we mean by quadruple efficient and uh naturally there are four uh efficiency measures here uh for a non-uniform circuit of size and we require that the provers time to produce a proof should be a linear number of cryptographic operations here lambda is the security parameter

we also require that the verifier time is logarithmic in the size of the circuit the proof size is also logarithmic in the size of the circuit now finally the verifiers pre-processing time should be linear number of finite field operations um uh in the size of the circuit of course we can desire uh even shorter proofs shorter verified time but we think even achieving this is pretty challenging in this space so we are willing to label this as quadruple efficient so if you look at existing snarks among these four dimensions uh so so for example if we look at the first what i call first generation transparent

snarks uh this includes schemes like ligero hyrax stark bulletproofs and aurora here uh these schemes achieve a succinct verifier meaning that the the time to verify the proof is sublinear or logarithmic in the size of the computation only for structured computations uh for example hyrax requires data parallel circuits start requires a sequence of sub-circuits uh a circuit that's expressed as a sequence of sub-circuits and each sub-circuit should be identical and the remaining systems like ligaro blade proofs and aurora achieve sublinear verifier only if you're verifying a collection of circuits with the same structure at the same time

otherwise they all require linear time verification time uh then there is the second what what i call a second generation of transparent snarks uh these uh schemes achieve a succinct verifier even for computations that have no structure uh for example if you give a non-uniform computation that's completely arbitrary they can still achieve a sublinear verifier one core technique in all of these schemes is that they they introduce a preprocessing step for the verifier where the verifier looks at the description of the circuit and creates some encoding or a commitment to the description of the circuit and then it uses this at some point later when verifying approved so it can achieve uh sublinear verification time

so if you actually take a look at this uh transparency the second generation of these transparency case now it's among the four dimensions that i uh mentioned earlier um uh so uh so for example if you look at the prover time uh spartan actually meets the requirement of a linear number of cryptographic operations both asymptotically and concretely and in terms of proof sizes supersonic meets our requirement both asymptotically and concretely on the very fire time side supersonic meets this asymptotically it has a logarithmic verifier but it's completely very expensive uh so on the pre-processing uh time

spartan meets this requirement but it still requires a linear number of cryptographic operations so in general there is a trade-off between uh whether somebody wants to optimize for the poorer time or they want to optimize for the proof sizes or verifier time and the the the concrete performance that i've depicted here for the is for the case where there are a million r1cs constraints so one natural question that we might wonder is if we can pick uh components from these schemes and combine them uh for example what happens uh uh if uh we pick uh an iop from spartan and combine with

supersonic polynomial commitment scheme uh the resulting snark would have the prover time of supersonic so it wouldn't exactly meet the requirement of a quark or we could also try taking spartans iop and combine with fractals polynomial commitment scheme here the proof sizes and prover time of the resulting stock would be similar to that up fragment so it doesn't quite meet our requirement does somebody have a question oh sorry that was just mr knock i i was uh dara just joined and i said uh feel free to ask questions throughout thanks so it turns out that if you just pick existing

components in these existing schemes and then try to combine them in different ways we don't quite meet the the requirement that i described earlier in the talk so also and it's also unclear how to reduce this pre-processing time a priori because all of them sort of require looking at the description of the circuit and doing some number of cryptographic operations for each gate in the circuit so our scheme kyphos is the first quadruple efficient transparency case now and it supports r1cs uh and it has this efficiency features it performs a linear number of cryptographic operations it produces logarithmic sized proofs

verification time is also logarithmic and the very fast preprocessing time is a linear number of finite field operations uh crucially there are no uh the verifiers pre-processing involves only a logarithmic number of cryptographic operations in terms of concrete performance it offers the fastest verification time uh uh and in terms of proof sizes the proof sizes are competitive with supersonics group sizes uh which offered the prior shortest transparent snarks and the prover time is faster than every transparent snark but it's about two three to four times slower than spartan which offers the fastest uh

snark including the snarks that might require a trusted setup so there are actually and it also offers the lowest pre-processing costs for the verifier so to achieve this there are four ingredients that we put together so the first ingredient is uh the spartans polynomial polynomial iop for argentius uh then we combine this with the dory and there are two variants of dory one is the dory uh the the the dory polynomial commitment scheme that works with dense polynomials and then we also transform the scheme to handle sparse polynomials efficiently using a compiler that we call spark

and i would say that this is the most uh important ingredient in this entire composition and we also have a technique that allows the verifier to delegate pre-processing work to some untrusted entity which we call an assistant and uh it turns out that this technique applies to any other zika snark so any other transparency case marks that we know of so i think this technique itself is general on its own there are also some other techniques that are in the paper that i'm not going to go into details of these reduce concrete costs this includes things like folding polynomial evaluation for example in spartan's iop the prover needs to prove

about four polynomials so it's going to fold all those polynomial evaluation proofs into a single polynomial evaluation proof and there is also a a more efficient secret transform that we discussed in the paper so one question that people might ask is like why why one should build on spartan's polynomial why not use other iops that exist for example plonk or marlin that's possible in fact it would actually reduce kyphosis proof size by constant factors i think it's about a factor of two but it also uh brings additional cause for example if the if you use if you build on block or marlin's iop it would require ffts and this introduces an asymptotically

higher cost and it's also in general i think hard to paralyze compared to uh parallelizing a multi exponentiation but what if you uh um you sort of you use say plonk iop but you do you do like in the last part you do a sum check right in the part where you you have to instead of computing the quotient you you know you reduce it to a randomized sum check so could you still get the 2x and the not have the fft um i think uh um [Music] yeah that's a good question so uh at least the the univariate you're talking about using the univariate sum check right

oh right right right right right so so you don't you don't have yeah we don't have a univariate sum check without fft which is a great open question so yeah cool yeah i think i think there is some work uh i haven't thought about whether it's possible to um use that directly in this context uh there's some work that i think by uh brian pano and students that try to avoid effectives oh is that published already because uh or uh there is an eprint uh i can i can maybe send you offline uh oh excellent thanks yeah yeah it's possible there is a way to combine that iop but we haven't looked

at that okay so in the next part of this talk i'm going to just uh go over these four different components that i've depicted here okay uh so the first uh component that i'm going to describe is the spartans polynomial and i'm first going to show a very simple description and then i'm going to unpack this so the the uh at a very high level this part of the polynomial is quite simple it can actually be depicted with three steps in the first step the proof so the actually before i describe this polynomial the problem that we are interested in

is given three matrices abc uh the prover wants to prove the knowledge of c such that this relationship depicted on the slide holds and this is the standard r1cs relationship so to do this the proverb would just send a polynomial that encodes the z and then the program the verifier would uh run the subject vertical i'll come back what this actually means and it runs the subject protocol in a very specific polynomial that's on the slide i'll explain why uh the polynomial looks like this in the next few slides and then the verifier makes one query each two four of those polynomials three polynomials depend on the description of the statement and one depends on the provers

witness that's it and it does some local computation using these queries and then accepts the proof if those checks pass and to compile this to snarks uh the in the first step the proverbs send some polynomial uh instead of that we the proverb would just send a polynomial commitment using a a polynomial commitment scheme and then in the last step when we makes queries to the polynomials the prover would send evaluations of those polynomials along with the proofs and then finally uh this entire protocol is public kind so it can be made non-interactive using the fiat xiaomi transform and it's it's that simple uh but uh the the crux of this construction

is why uh this equation looks the way it is and that's what i'm going to come back next um so a little more detail on r1cs so uh so we are given three m cross and matrices abc and the problem asks does there exist a vector z such that uh a times c uh hadamard with b times z equals c times e where c is this entry wise multiplication of vectors and the high level idea here is that we can view these matrices and vectors as functions for example z the vector z can be viewed as a function that maps some aspect strings

to elements of a finite field where s is logarithmic in the dimension of the vector and similarly abc can be viewed as a function in 2s bit elements to something that maps to a finite field element then once we view these as functions we can actually construct multilinear polynomials out of these functions what i mean by this is that there exists some polynomial i'm going to denote these polynomials as uh with the tilde on top of the variable uh so for example z tilde y would agree with z of y uh for all values of y or the boolean hypercube

and similarly uh there exist a unique multilinear polynomials that match the underlying functions or the boolean hypercube so once we have these multilinear polynomials there exists a special function that i denote here with f and there is a unique property about this function which is that the function evaluates to zero if and only if the r1cs instance is satisfiable and it's actually pretty uh easy to look at uh uh this equation and see why this is true it's it's just checking uh each of the each of the constraints in the original r1cs it just multiplies those matrices and then it checks if each constraint is

satisfiable um so this this we aren't quite done here because we need a uh we need an instance for which we can directly apply the subject protocol so what we do is we take this f and then we take evaluations of f and take a weighted sum with another polynomial that i denote here by e e tilde and there's a unique property about the sum which is that except for a small soundness error or the choice of this tau the sum is zero if and only if f of x is zero over the entire boolean hyper cube 0 comma 1 s [Music] and e here is a unique multilinear

polynomial that evaluates to 1 if the arguments are equal and 0 otherwise over the boolean hyper cube so the reason we are actually interested in this particular sum is there is a uh a code primitive that spartan employees called the subject protocol uh and it's an interactive proof system for uh some check instances of this form uh where g is a multi multivariate polynomial in l variables and t is some target value uh in the finite field and the prover and it's an interactive proof system where the prover can prove that this polynomial g sums to this target value or the boolean hypercube and in this protocol there are l rounds where l is the number of variables in

the polynomial uh and in each round the prover sends one the verifier sends one random field element to the approver the prover responds with a short message and the messages of size d where is d is the degree of the polynomial in any variable and then in each round v performs a small number of finite field operations uh and the at the end of the subject the the verifier must evaluate this polynomial g at a random point where r is chosen by the verifier over the course of the protocol so there are several advantages of using this subject protocol as a code building block one of them is it requires no trusted

setup second it's public kind in each round the verifier is just uh sampling a random field element and sending it so it can be made non-interactive in the random oracle model finally it turns out that for many uh many uh polynomials uh so for example if g can be broken down into a set of multilinear polynomials the prover can be implemented in linear time by linear time i mean the prover only uses a linear number of finite field operations during the entire protocol there's one disadvantage which i'm not depicted on the slide which is that it requires a logarithmic number of uh rounds compared to something like the univariate subject protocol which is uh

just a single round but the the united states protocol at least the ones that i've seen would also require the prover to run in super linear time so it would require uh something like n log n finite field operations rather than n finite field operations well i think sometimes maybe like the interesting question is can you uh say for some constant number of variables can you get uh so yeah universe maybe is the hardest but for some constant number of variables can you get uh linear uh proof of runtime right that we divide it into a cube of like length n to the one over d

for some d and we have d uh you know for constant d and and uh can you still get prover con uh linear run time that's what i that's something i wonder yeah so you think d is constant these these you typically assume to be constant here so d sorry no i use d for i meant the number of variables so so l yeah like can you do l is i don't know three or five uh yeah and so instead of zero one you'll have like n to the one over l as the domain and can you still get linear proof of runtime i think that's a really good great question yeah i think i think that's a good question so you're saying

instead of looking at or the boolean hypercube we look at a larger space and then make the number of variables yeah i think i think actually i think the original subject protocol was actually not described over the boolean hypercube impacted so it uses h which is a subspace that can be arbitrary i think uh i i haven't looked at uh whether it reduces it can all these uh uh the linear time results can be applied in that context i think it's an interesting question now yeah i think i think there is some properties of the multi-linear polynomial that gets exploited in this particular construction but you're right uh that's an interesting question to look at that can greatly reduce the rounds which in turn

reduces the proof sizes so so now if i come back to the slide that i depicted earlier this equation is essentially checking this equation on the second bullet is the sum check instance that i just unpacked so in the first of the prover sensor polynomial and then the the core of the protocol is running the sum check protocol using this equation using this polynomial that we devised and then in the end the verifier just queries four of those polynomials at one location each uh so a core uh so if once we have this polynomial iop so to get a snark we need

a polynomial commitment scheme so in kai force the polynomial commitment scheme that we use is dory so here is one slide that i made on dory and i personally think this is a breakthrough result in the space of polynomial commitment schemes and i've compared dory's asymptotics and concrete cost with two other schemes two other transparent polynomial commitment schemes one of them is uh the polynomial commitment scheme called higher the scheme that's in hydrax which is also used in spartan and then the second row depicts the cost under supersonics polynomial commitment scheme called dark uh and i've taken five different metrics that are normally considered polynomial

commitment scheme i think there are a couple of key takeaways here which is dory has better asymptotics than dark and with significantly better concrete performance on almost all of the aspects uh second uh dory also has better asymptotics than higher access polynomial commitment scheme and it outperforms that scheme even at the small polynomial sizes for example uh the the the pro so the sodory's commitment time is slightly larger by a constant factor but for example if you look at the commitment size it's constant sized uh the prover time is a linear number of

finite field operations in both dory and higher access polynomial commitment scheme but as n increases i think uh as an increases that the dory paper shows that the prover time under higher access polynomial commitment scheme and dory approach the same value proof sizes are slightly larger under dory than higher access polynomial commitment scheme because in high ranks it uses bullet proof's commitment which has a very short both are logarithmic but there is a larger constant associated with dory but the very fire time even though at least at n equals 2 to the 20 uh it's higher under dory than high ranks but as n increases higher access polynomial commitment schemes costs increase pretty quickly so uh i think that about

n uh equals to the 24 it completely outperforms higher access polynomial commitment scheme on most of the aspects but compared to supersonics polynomial commitments came even at small polynomials degree outperforms and all uh aspects depicted here so apply so we can take this dowry polynomial commitment scheme and directly apply to spartan's iop it almost works but there is one caveat which is these abc polynomials that i showed in the iop are actually sparse polynomials what i mean by this is that these abc matrices are sparse matrices ah so in practice the number of non-zero

entries in this matrices is linear in the matrix dimension whereas the total number of entries in the matrix is quadratic so if we directly apply dory it would incur quadratic costs for both creating commitments and producing evaluation proofs what i'm what this means is that in the smart context the prover would be quadratic in the statement size so spartan already had a solution to this problem uh the solution is that uh it is what we call the spark compiler so it takes an existing polynomial commitment scheme designed for multilinear polynomials and it gives you a polynomial commitment scheme for sparse multi-linear polynomials and

both the commitment time and the proving sparse evaluations are efficient and there are two key techniques here one is that it creates commitments to dense representations of sparse polynomials so for example if we are given a sparse polynomial in this matrix form it creates three dense multilinear polynomials uh we call call val and each of these polynomial is proportional to the number of non-zero entries uh uh what they encode is that the the row polynomial encode the indices the row indices at which the there are nonzero entries and column polynomial encodes the column indices at which the

the non-zero entries appear in the original matrix and the val polynomial encodes the coefficient in those non-zero entries and then the second part of spark is how to prove these parts polynomial evaluations and there are two uh aspects here one is uh we devise an efficient polynomial iop for proving sparse polynomial variations and then we com compile it to smart using polynomial commitments so to go into a little bit more detail on how we produce parts polynomial evaluations uh at a very high level we express uh in size parts polynomial evaluations as a weighted inner product using these three dense multi-linear polynomials rho

call val and it's given by this equation so uh so for example if a tilde is the multilinear polynomial and we are evaluating it at rx comma ry so it's given by the weighted sum of these three components e tilde evaluated at rx comma rho of i uh multiplied with e tilde of ry evaluated at column of i and then the weight uh for this the inner product is given by val of i and there are only n terms in this sum and the core idea is that we can treat the first entry in this product as a memory lookup

where the memory is of size n and it's initialized evaluations of this e tilde of rx comma j for all j so we take so we can treat uh the uh and we can also do the same for the second entry in the product so we take the valuations of v tilde at all possible points that somebody might want to query and then create this memory and and to do this weighted sum we just do n memory lookups for each of these tables and then do a weighted sum and one of the key techniques that we use here is that uh we can we transform this correctness of proving memory lookups to

multiset equality check using offline memory checking and this is a technique from the early 90s that we use and this particular technique was first used in the context of snarks for proving concurrent executions in a multi-writer database um and then uh in spartan we transform this multiset equality check into proving grant product relations and uh in kai force we provide a special purpose not for proving these grand product relations using dory as the commitment scheme and the main improvement here over spartan is that it produces logarithmic size proofs instead of poly logarithmic size proofs that was

the case in spartan so finally the the fourth technique that i want to uh describe a little bit detail uh is uh the how how kai force outsources verifies pre-processing work so in spartan supersonic are fractal the very fire in a pre-processing step it reads the r1cs instance or a circuit uh it encodes the circuit into a set of polynomials for example in this part in spartan's case it's a set of multi-linear polynomials and then finally uh the verifier would create commitments to these polynomials

using some public parameters whereas in high force we introduced the notion of an untrusted assistant so this untrusted assistant could be played by anyone including the brewer uh so in kai force in a pre-processing step the assistant and the verifier would just read and encode this instance into a set of polynomials and then the assistant uh would uh send to the assistant would actually just take only the assistant would execute the commit operation and sends those commitments to the verifier uh the verifier then sends to the assistant a random challenge assistant then replies to the verifier

with an evaluation of those committed polynomials at the challenge point uh chosen by the verifier and then the verifier evaluates the original polynomials at the random challenge point and checks if the evaluation matches uh the provers claimed evaluation along with checking the evaluation proof provided by the brewer sorry the assistant and the upshot here is that the untrusted assistant creates cryptographic commitments which is the most expensive part and the very first cost is linear number of final finite field operations and the cost to verify the polynomial evaluation proof which is just a logarithmic number of cryptographic operations and uh we think

this uh technique applies to most of the other universal snarks out there to reduce pre-processing cost to the very fire so sorry so could you remind me so what is the verifier pre-processing cost in the supersonic uh i think uh it requires linear number of cryptographic operations to uh create commitments to the polynomials oh and you're saying here it's a linear number of field operations yes okay because the assistant actually creates those commitments and then the verifier's job is just to verify polynomial evaluation and evaluate the polynomial at one point i guess if you were using this for

something like a smart contract then whoever is preparing the contract would act as the assistant yeah that makes sense okay so we implemented all of these techniques uh uh uh by extending spartan and here is one slide that depicts the performance that a million r1cs constraints and the depicted performance is on a single cpu core and i think all of the schemes can be parallelized to reduce this proven time but this comparison is still fair because all of them are run with one cpu core there are a couple of key takeaways here

which is a kyphosis brewer is fast but it's not the fastest uh the primary difference between the kaifos and spartan which gives you the fastest prover is the the difference in performance between bls 12 381's uh g1 and restricted to fifi because kyphus requires dory uh uses dory and dory in turn requires a pairing friendly curve uh but kai force is faster than all other snarks depicted here uh kyphos offers the fastest by fire uh kyphosis proof sizes are competitive with supersonic corpus which is a small variant of kyphos shortens

uh kyphus proves but it requires a slower verifier both asymptotically and concretely and the technique that i described for out speeding up uh the very first pre-processing cost uh reduces pre-processing time significantly the the ratio between the um kaifas and spartan prover times the is a little bit larger than i would expect for the difference between uh restricted 255 and bls 123.1 um how was the arithmetic for bls 12 381 optimized um does it it looks like um

a factor of four there and i would expect something like three or less yeah so for for blf stall 381 we used the blasters library uh for restrictor we used car2519 dialect with cmd optimization so it's included and i don't believe uh bls implementation uses smd instructions okay that probably explains it yeah that makes sense okay um yeah and to summarize the kuipers provides the first quadruple efficient transparency snark and um in terms of concrete performance it has a fast verifier

uh shutter proofs uh proven time is fast but it's not the fastest with that i can take additional questions uh what was the ratio of prove the costs between say spartan and gross 16 again yeah sorry i did not depict here but um iran growth 16 has implemented in lip snark with bn256 curve i think it's about um 70 seconds or 75 seconds if i remember correctly

so spartan is a factor to faster uh right okay yeah because the the bn254 curve is yeah about the same size as restrato okay we started two five five wait i'm i thought you said uh spartan uses dory oh no kaifos uses dory okay um you said uh something that you have uh you improved the grand product uh argument from uh log squared to vlog improver time maybe you can

say a few words about uh that yes so it's the improvement was in proof sizes uh so so in the original grand product argument um uh so it it used a layered sum check so for example if you have a vector of size and at each step it would reduce it to a vector of size n divided by two and it goes all the way to one and then uses the subject protocol repeatedly recursively to go from the output to the input so you can think of it as applying the gkr protocol for the specific relation and at each step uh the original protocol required logarithmic size proof so overall it takes log square size proofs uh so in chi force what we did was we

created a single sum check instance that can prove the grand product relation so what we do is we take the original vector and then extend it with uh all the intermediate products i think this is something similar to what happens in block uh so the so you have the in size vector so we augment this with uh another inside vector that carries all the uh intermediate products and then we have a single sum check that checks this product relation across the entire vector at once and because we apply a single sound check it has just log n cos in terms of group sizes

uh yeah right so if you do multi right it's multivariate so you need to uh write it in in plonk there's a simple a generator that gets you to the to the next point uh for the multi multivariate thing right so you need and get you need some something that gets you to the neck that goes over all the cube i'm guessing right so what so yeah something what what is this thing that uh how does it look like in them like multivariate case this thing that gets you to each time to the next point yeah yeah so actually we don't do the uh the next uh so we we have a special polynomial that

essentially checks um one product at a time so we we we have a a polynomial that essentially uh computes a product of two entries in the vector and compares it with another entry on the second half so so there is a polynomial that picks one of the entries in the second half of the vector and two entries in the first half and then checks if the the first entry is the product of the two entries and there are n such checks that need to happen and we just combine all of them into a single check by using the subject protocol so

you can think of uh for example let's say somebody gave you a an in size vector then we recursively computed the grand product and we recorded the trace of this computation in the second half of the vector uh there exists a a a polynomial that can actually check this uh the the computation that was performed by the original circuit uh in with n checks on this uh two n size vector uh and then uh we can check this relationship or the boolean hypercube by uh just using some standard tricks that i depicted in one of the earlier slides using the c tilde polynomial so yeah you're saying it sounds like you're

in the univariate plonk you you sort of accumulate the grand product just one element at a time here it's more like a tree uh that yeah and maybe that's more convenient for the multivariate uh case yes yeah and it also does not require uh multiplicative subgroups for instance so it works over any fight field though so so you can do it you can do a grand product over just any set like h to the n where h doesn't need to have any special uh structure yeah although we rely on the boolean hypercube so we so you're given a

a vector of finite field elements um we just uh treat that as a polynomial uh evaluated over the boolean hypercube and then we compute the product i'm just looking at the performance figures for laconia um in the paper um they seem quite impressive um yes so laconia also sorry i did not depict this on the slide so laconia is not similar to uh kyphos except uh it does not

uh uh it does not have the prover proof evaluations of a tilde b tilde and c tilde so the verifier is evaluating those three polynomials so it's in analogous to bulletproofs where the verifier is reading the circuit and computing with the description of the circuit so so would it be possible to have a hybrid where you have an assistant that um expands a laconia proof um and then the verifier has to process a larger proof but it's

less expensive uh is there is there one um one instance or multiple instances in this case uh either um let's assume that um we have a fixed circuit uh yeah i think i think um if there is only one instance um i think if if anyone asses tries to assist this verifier by proving abc evaluations it would uh sort of look like kyphos uh because that entity would incur the cost of proving evaluations of this particular number so the cost would

go from whatever we depict for laconia to kaifos but it's possible to monetize that cost for example if the verifier is evaluating uh or verifying a proof for the same circuit multiple times uh uh so this cost i i guess in some sense it's sort of like sonic's help mode right so the the the work could just prove it once so and the verifier the cost of the proverb would get also amortized across n instances okay thank you awesome yeah thanks for not so i i actually have a question

um on a slightly different theme that i think may be interesting to folks who are viewing this video um you know with that are maybe more more kind of you know general have general knowledge but maybe not as specific knowledge as some of the prior questions they've been asked so my question is on the topic of um basically the future of snarks in an era where quantum computers become you know a you know a reality and i encourage by the way everybody all the smart people in this uh in in the chat here to chime in but you know obviously you know snarks rely on cryptographic assumptions that may or may not hold well likely will not hold uh in the world of quantum computers whereas starks seemingly for example starks and other schemes you know

will potentially hold in that world and so i'm curious for not just from your perspective as a researcher in the space you know how i guess how much does it make sense to push these forward especially in light of the fact that snarks are very efficient uh compared to those other schemes i mentioned um but i guess how much does it make sense to push it forward without considering the potential world in which they may or may not actually be secure yeah yeah i think i think i think if you're worried about post quantum security i think i think some of this work could still be relevant because there are two as i mentioned there are two components here one is the the iop uh which is information theoretically secure so it's secure against quantum computers and

then there's this polynomial commitment scheme uh so uh you so there are ways to make a polynomial commitment scheme out of protocols like fri or even ligero polynomial commitment scheme uh that you can combine with this iop to get a post quantum secure snark uh i think i think um maybe uh this modular approach of investigating most efficient iop and most efficient polynomial commitments because all the cryptographic assumptions are inherited from the polynomial commitment scheme so if if one desires say post quantum secure smart they could use a post quantum secure polynomial commitment scheme uh i think uh uh uh this modular approach i

think still has value to uh even in the post quantum world yep i i was going to say the same thing that's my opinion as well awesome yeah thank you both you know i know it's a question a lot of people have honestly when they first come into the space and they they kind of get an overview of the landscape and obviously that the question i had was based on kind of a simplistic understanding but thank you guys for uh for kind of shedding some more light on on your view yeah i i mean as saran says um part of the work is reusable and people can work on the polynomial commitment side and the iep side independently which is great

and i think actually so things like fractal um are already practical for some applications so um it's definitely worth considering them deploying them does anyone know if practical has been deployed at any real world protocol not that i know of okay i mean i know the marks are being i don't know if freckle has been deployed but i just wanted to comment that uh all these all these uh constructions that don't rely on only hash functions help us post quant researchers try to

find the right mathematical tools and so maybe we can find a post-quantum translation of pairings that works even against formal computers so yes it's definitely worthwhile continuing this this that's interesting i'd kind of assumed that pairings were too structured in a sense to um to admit a post quantum solution but i could be completely wrong there well as soon as you have a group then you can use short's order finding algorithms right exactly but doesn't um varying that doesn't come with a group structure

i thought that um that a bilinear map kind of implied a group but maybe there's a way to relax well in the same sense that that you can do dizzy hellmann with only group actions you don't need a proper group for it and so the the object that your actions are acting on is not itself a group and so maybe there's there's a way to lift this to pairings whereby you can combine that object once but not twice and then you would have a group action that supports one pairing but not two pairing computations

oh i see okay i'm not likely sufficient well i think maybe right there's the this stuff i don't know it well but that correct gentry started with based on lattices maybe it's sort of like a group but that the addition is not always defined because sort of he does these operations on noisy vectors from lattices and then the addition result is remove the noise to find the closest lattice point but if the noise is too large then you won't find a point so maybe it sort of corresponds to a a air group with error where the addition of some elements is not defined

maybe something like that would be easier to do this quantum resistance if your group actions hold with only one minus epsilon probability that you are computationally speaking still a group but it might be enough to break shore's algorithm and so if that were possible you could recycle all of group based cryptography because it works in practice and it only destroys schwarzenegger do we know that schwarz algorithm is uh the only uh quantum approach to

um breaking this kind of structure though i mean for grover's algorithm we have i think a proof of optimality um in the black box model but um don't think we have any similar proof for sure's algorithm that's my knowledge and there are definitely other hard problems which you might or might not be able to use for cryptography but computationally hard problems out there where the best known one computer is exponentially more powerful than the

best known classical algorithm i i think you can characterize schwarz algorithm as a special case of that but i don't know i i mean i i may be biased here having developed a hash based press quantum signature scheme but i tend to think that the most trustworthy post-quantum algorithms of the hash based ones awesome well yeah thanks everyone's

fascinating conversation uh so thanks a lot for weighing in i'm sure um other folks on the channel as well as the youtube channel will appreciate that insight um are there any other questions for so not on the topic of uh quirks uh so what's what's the next step what are the open problems that um we should look at yeah at least at least here i think i think the process as you can see it's still large um i don't know if there's a ways to make it shorter i think um supporting maybe more custom gates in this model whether

it's possible i think i think it is possible but i guess there is it hasn't been explored of course making the crew as fast as possible is another i guess question uh because it's not the fastest as depicted here uh yeah i think maybe um supporting lockups um would be as useful as custom gates um and maybe that's simpler yeah look ups are somewhat supported already in the sense um for example our grand product argument or the the sparse polynomial evaluation relies on a memory lookup i think

the same approach could be exposed to the programmer where the the the it exposes this operation and then inside the proof system it's proven using the special purpose memory checking algorithm but it hasn't been fully explored yeah i think i think r1cs plus lookups is an underexplored way of writing circuits and would be a very nice model yeah yeah we we had some work that um that still required the so this was the sagl 18 that i depicted earlier in one of the slides where we use multiset hash function so it's still required um

uh encoding a public hash function so there are no secrets but uh uh using a randomized version which is what we do in spartan and kyphos it does not require really representing a multiset hash function it's just a fingerprinting function now uh which is sufficient for lookups could be exposed uh to the programmer so so um if i'm saying correctly both kyphus and copis [Music] coppice require um pairings and if you want to do recursion in the straightforward way that means an mnt4 mnt6 cycle

is there any way to do it using just a half-pairing cycle yeah yeah that's a good question i think it is possible by uh so for example um uh what uh uh nova calls folding or uh what's uh called called as accumulation scheme i think the same applies here because the commitments are uh elements of gta you can accumulate them by doing one operation then gt uh so you i think uh half pairing might be sufficient but i'd like to think more to say or confirm that yeah definitely worth exploring

okay i would just mention sort of going to that that uh sort of because ultimately we're building on top of dory here um and dory matches very efficiently uh sort of almost everything you have to do is gt arithmetic and then you have to do sort of four pairings at the end um but if you want a batch if you want to defer all that computation you can um and it may be the case that you can you can efficiently use pairing cycles to clean that up quite substantially awesome uh if anyone wants to use um half-herring cycles by the way i um should probably plug the half cycle

half-pairing cycle that i generated um pluto iris which is a 448 bit um cycle with one bn curve that has some nice engineering properties thanks awesome um any other questions uh first or not there's not any any thing you'd like to close with or yeah concluding comments no thank thanks everyone for all the great questions thanks for inviting me to speak here yeah thank you