# Efficient non-native SNARK recursion using bivariate polynomial testing by Ivo Kubjas | Devcon SEA

- Speakers: [Ivo Kubjas](https://streameth.org/speakers/ivo-kubjas)
- Channel: [Devcon](https://streameth.org/devcon)
- Date: 2025-10-09
- Duration: 25:10
- Topics: Science & Technology
- Watch: https://streameth.org/watch/yt-ylmiiUnwhrE
- YouTube: https://www.youtube.com/watch?v=ylmiiUnwhrE

## Description

Efficient SNARK recursion requires switching between pairing friendly elliptic curves. In most optimal approaches these curves would construct a cycle, but there are no such known cycles. Instead, we use non-native arithmetic to brute force the pairing computation at the cycle cut-off.
We describe an approach for combining direct field extension with polynomial-based non-native arithmetic. This reduces pairing computation to bivariate polynomial identity testing using Schwartz-Zippel lemma.

Speaker(s): Ivo Kubjas
Skill level: Intermediate
Track: Applied Cryptography
Keywords: ZKP, Cryptography, SNARK, zk, based, pairing

Follow us: https://twitter.com/efdevcon, https://twitter.com/ethereum, https://warpcast.com/devcon
Learn more about devcon: https://www.devcon.org/
Learn more about ethereum: https://ethereum.org/ 

Visit the https://archive.devcon.org/ to gain access to the entire library of Devcon talks with the ease of filtering, playlists, personalized suggestions, decentralized access on Swarm, IPFS and more.

Devcon is the Ethereum conference for developers, researchers, thinkers, and makers. 
Devcon SEA was held in Bangkok, Thailand on Nov 12 - Nov 15, 2024.
Devcon is organized and presented by the Ethereum Foundation. To find out more, please visit https://ethereum.foundation/

## Transcript

[Music] so today I'm going to talk about um a bit about the optimization techniques what we have done for making the proof cursion uh in linear and also in gar a bit more efficient so I work on Linea and I mostly work on gnark so Gnar is an um End to End Library written in go for writing uh circuits which can be be which can be proven using snark proof systems so you can write circuits you can compile it into uh constraint systems for example R1 CS uh blanish um then you can uh run the thrusted setup particularly for the for the cross 16 uh you can use knar for proving using different uh aration engines so using CPUs gpus finally you can use gar to verify uh the proofs so we have the verifiers written in for example for the native verifier for the mobile verifier it's Al also possible to verify the proes recursively in in another snark or we can also compile uh solid verifier so you can also verify snark proofs chain on ethereum so let's uh set the stage uh before we start so what we want to do let's say we have some kind of statement which can be a mathematical statement or a computer program um and uh we have some some inputs we have the secret input and the public input so so the secret input is something what only the prover knows the public input is is known to everyone so for like as an example what can be a statement a statement can be something very simple for example I know the factorization of RSA primes so I know two factors uh which multiply together uh result in some some uh some prime and so for example I can prove that I know a solution to these RSA factorization challenges and I can I can uh obtain the the challenge money but without uh without revealing what are the particular inputs because like if I would reveal it maybe like someone will front run me and they would um uh try to uh get the money themselves so what happens is that first we take the the statement we possibly we do like some kind of precomputation on that so we we get some expanded statement and then um the the the the Pro run this program so for example theover gets some kind of uh execution troice the uh proves using some technique and we get uh we get a proof and uh what we want to have usually is that the proof is short what what does uh what does it mean for the proof to be short so the proof should be short in the sense of this expanded Trace so the steps all the intermediate uh results of the of the computations so and if it is shorter uh then it means that we have already one so we have some like short proof of this computation and we also want the verifier to be fast so the verifier should run faster than running the computation itself because otherwise like what's the point and uh like complexity wise maybe we we want that the proof and verifier work like it is uh let's say ASM totically faster maybe we want them to be let's say logarithmic in the size of the computation steps or maybe like a square root or it will be very very nice if uh it will be constant size and optionally we we would like to have Z knowledge sometimes but in a lot of applications it's not necessary so let's say some of uh some of the proving schemes so there is the sum check where essentially we if we represent the statement as a multi-linear uh polinomial and the then the pro shows that some let's say some property of this multilinear polinomial holds and it is it doesn't require like some very fun mathematics it's like essentially we just evaluate pols uh the problem with the Su Che based approach is that verifier needs to do the the final EV so it means that verifier needs to evaluate this Su Che multilinear polinomial at some point then we have GK which is very similar to S it's just layered it's it's a bit more structured we have Starks which are based on um on hash functions so we can uh we can can have some kind of polinomial constraints between like different steps and different different columns uh we have cross 16 which is one of the first bearing based systems and the nice thing about the cross 16 is that the proof size is constant and also the ver verifier work is constant but it requires a lot of pre computation it requires per circuit thrust setup and final plon plon is nicer in the sense that it doesn't require par circuit thrusted setup so it can use the University trusted setup there are of course a lot more but uh I say like in the big picture like these are like some nice nice examples so the let's say the the issue is that for the first three schemes uh they are very fast and they do not require like any particular kind of assumptions they only do finite field arithmetic and hashing uh and no assumptions at all so we just have to choose the hash function but the proofs are not that short so for the Su check the proof size is logarithmic in the number of uh let's say in the number of steps uh for Starks I think it's it's it's square root so it is shorter but not but not very short so if the let's say the if the statement input is is huge in like hundreds of millions of uh of steps then the the the proofs are still big for the last two the issue is that um the provs are slower because we use the the fun mathematics called pairings uh and kg commitments but the the proofs are very very short so the the proofs are for example like constant number of uh some group elements and the verifier work is also very short so like if we measure it concretely on a na machine it means that uh the verifier work is for example like milliseconds why we want the verifier work to be efficient and short is that when we go to L1 then uh it concretely uh means that we pay for Less G so what should we do we have fast provs we have fast verifiers we have slow provs we have slow verifiers so we can just combine like different approaches let's say we can uh combine the approaches because like one of the statements what we can prove is uh the verifier implementation for the F proam so let's say if we have some very big statement and we'll just use fast prover first we get some proof which is which is uh let's say not constant but still smaller then we provide this as an input to the slower prover but because the input is already sufficiently small then the slower appr is actually also relatively fast so we can uh we can run it nicely and in the end we get a very small proof very very fast verifier and we we can post this on on ethereum and and we are done so we get both of the best of the Both Worlds we have the fast Brewer we have the fast verifier and we we we we do not pay a lot of money we don't pay a lot of money for verif the proofs we can use the like similar let's say combination techniques uh CK pipeline combination techniques to do uh compute the proofs in parallel so let's say we have uh in the context of roll up we have a a lot of blocks so we can prove actually the blocks in parallel because even the fast provs uh the they are slow so it take to take minutes so we can actually run let's say up to like 400 uh proof proof generation in parallel and then we can aggregate everything into into a single aggregate proof and we post that we can post that onum so this also gives us some like some additional saving uh in uh in boasting the the proes and in finalizing the L2 on ethereum so to summarize a bit uh what different kind kinds of recur recursive proving we have to do uh we have to do the PN 254 BL verification in pls2 377 it's for the pre- compiles and we verify the fast fast proofs The Vortex proofs in uh in PLS 1277 PL then for the proof aggregation we used the PLS 12377 blun proof verification in P6 7761 blun circuit and finally uh because ethereum only supports the BN 254 pre compile then we have to compress it back into into some other curve and for that we need need to use the the the Final Approach so what is the cost in uh or what is the cost in verifying plun proof so there are the different steps so first we need to need to do some hashing get the the random challenges uh we have some exponentiations where the exponent can be a variable or it can be an fixed value we have scalar multiplications and finally the the most complex part is is Computing the pairing and pairing consists of two parts so it consists of Miller Loop and final exponentiation and uh we today's talk we are focusing on the Miller Loop and also final exponentiation so like what what can we optimize so first uh we we work in elliptic like elliptic curves so what does it mean so we have some base field uh so we have coordinates which are defined over a base field what we can think about it essentially they are like some integers module some some prime number and and elliptic curve is all of the solutions to some elliptic curve equation u y like y^2 equal x x Cub plus a X plus b and so the elliptic curve is a solution to like this this equation so we have a lot of points uh and uh there is there's also scalar field so let's say like if you fix a point on on elliptic curve so like all the let's say all the multiples of it so they uh if you we have only a single let's say a single group in the elliptic curve so they they generate uh like it generates um like all of the points and the SCS they also uh they uh they construct a finite field so we have two fields we have the base field the points and we have the scolar field for the scholars in in the elliptic C it's really great if we have some kind of match so right now we are thinking that we are verifying recursively so we are verifying a blon proof inside a PL circuit so all the arithmetic in a plun circuit happens on the scalar field but we need to do arithmetic in the base field in the scalar field so like in in in in different fields so we have some kind some kind of mismatch it it would be really nice if we have a match somewhere so the scalar field corresponds to the base field of some other curve uh and there are like sometimes we have it but most of the times we don't so how how can we fix it we can just use multiprecision arithmetic so we can do it uh like naively as as for like in library so we just split a big value into into limbs so for example we split it into like 64 bit lims so if we do it like this then when we think about the multiplication then we essentially we have to use the the school book multiplication and the school book multiplication the Astic cost of it it is a quadratic in the number of lims so it's it's not super beneficial or it's not super efficient and also consider that we are only doing the the integer multiplication we also have to do the model reduction so we have to do it several times so a bit more clever approach is actually uh to use um the polinomial representation of this multiion integers so it's the same but uh we look at uh we look at the polinomial where the co efficients are the limbs of this multiple integer and in this case uh because in a when we are creating a blon proof then like actually the pro can uh just hint some values the pro can hint the result and also the quotient and then like we can check that this polinomial is is equivalent at some random point so when we compute the paing so the computations in a paing happen in different groups so they happen in the in the group of the points but it also happens in the in the extension fields of the of the base field so we have the G2 GT uh for the bearing and uh so what are the extension Fields so essentially extension fields are a field of pols where the coefficients are defined over the base field and we also have to have like some uh some let's say fixed fixed modulus which is like some irreducible modulus which essentially defines like how we can reduce values uh when they go when they are bigger than than the modules it it's it's a it's a bit simpler to look at the the the extension field elements as vectors and then the multiplication I'm mul multiplication inside the extension field it's exactly as for the multi Precision integers and we just do the model reduction using the the the given modules we have the same problems for the extension multiplication is that the complexity is quadratic so if we have high like high extensions the six degree or 12 degree extensions then it's just like very complex to compute so what uh for optimization we can actually use we can use like towers of extensions so like instead of going to the six extension directly we first go to the cubic extension then we go to the quadratic extension and then the multiplication becomes up somewhat simpler so as a concrete examples let's see like if we consider a quadratic extension or over a cubic extension if you do a multiplication then we first we need to do one let's say uh one cubic multiplication also for for computing the result of the second second limb in the in this six extension we have to do two multiplications uh quad CU multiplications but before we we before we mod reduce we can just add the pols because like if you recall then if you add pols then the degree of the resulting poal it doesn't increase it may it may actually uh I'm sorry if we add two Pol norals then the degree doesn't increase it may have actually like decrease if we if something cancels out so there was a very nice result uh IO by felra Prime and he he actually showed that when we compute the extenstion multiplication then we don't have to do it uh like using the towers we can do it directly and the idea is very simple what we have for the non- native multiplication is that essentially we don't compute the value but the approver provides the value using a hint and also also the quotient we then the verifier provides some kind of challenge using f usually and then we just check that this direct extension multiplication is correct so this should be more efficient and uh we like we wanted to figure it out so we we U uh we found the direct extensions and uh we started to to write out this this equations and we started to to see like how beneficial it is for that so the previous result was only for p and 24 we wanted to implement also for the other curs for so for p p 6 761 and P 12 377 okay let's write it out and so we get something like this so it looks something something simple but the issue is right now that all of these multiplications what we have right uh right here they are nonnative multiplications so like only for the left hand side like we see that we have at least one so we have like 10 or or 11 level nonnative mulp multiplications and if we do the non-native multiplication in this in this way that we provide the result using a hint then uh we have to do a lot of frange checking and uh this is not like that efficient so let's try to improve this approach a bit and so actually you can improve it like very simply I would say uh so when instead in nonnative If instead of the multiplication we want to evaluate something more complex some like let's say some multivariate evalation where like instead of multiplication we have some something let's say a * P plus CMD plus cmf and so on so we have some something more complex then we we see that actually we don't need to compute all the intermediate results so we only need to know what like what is the what is the full result of the of the this multivar evaluation and uh the complexity stays the same regardless if we do non-native multiplication only or if we do this more complex multivariate evoluation and if we implement it this way then actually like evaluating these extensions uh extension pols like it becomes a lot more easier so let's now write write it out again like in full so we have the a b c and n and B so what we do at least in gor is that we do not eval evaluate uh non-native and extension uh multiplication directly we just write it down that uh we need to evaluate them later on and we only provide the result using a hint uh because this allows us to share some of the computations so for example if we instead of like Computing a f challenge for every check we computed uh over all checks like if you f or we hash all of the inputs then we can share this random variable set we can compute all of the powers of set we evaluate uh the P of uh P at the at this one place because it it's shared over all checks we evaluate A and B and uh now we check so we replace this a part the B part uh the uh and also the the P part and uh now we have like this one big thing what we need to evaluate but this is a this um let's say something what we can evaluate with the non-native operation which is which corresponds to a single non-native multiplication and if you count count it so on average let's say if we amortise the the the P part then we actually only have like non-native uh operations and this is very efficient so for evaluating at extension multiplication we only need three non native operations and the main cost here is checking the the range checking the hinted values so actually doing the multiplications themselves it's cheap but it's just like when we work in 64-bit limbs then we have to check them when we look at the Benchmark results so this is the number of constraints in in in blanish so on average we were able to to get 40% reduction um but there there are like still some uh some ideas what we have for improving the performance so the like one of the thing to to notice is that we don't need to actually find every quo just need to like know that there is a quo so if you look at the random linear combination then uh then can also provide the single quent and we can apply it also for the like different operations and we can also apply the the same technique for different curves thank [Applause] you uh thank you Evo for the presentation it was nice are you ready for some Q&A yes so let's look at the questions why do you need four different combinations of PL imp plon yeah it's a it's a very good question uh I ask it myself like many times so we need it because uh we are uh like on one hand we are restricted to what what we already have so for example if you want to verify a BL proof on ethereum then we can only use p and 254 because the this is the only pre-compile which is provided by theum and otherwise if you would like compute a bearing using let's say an imp assembly implementation it will be just expensive uh for proof aggregation uh we we will we would need to have let's say a chain of chain of uh or let's say two chain of Curves where where like the scalar field of one curve corresponds to the base field of the other curve and they don't come like that often so we have to particularly construct construct them and for example because pn24 is already given we cannot construct a two chain for for that um so we and we we also had like some other like uh other way because in linear for example we have to we have to prove uh also like pairings uh so let's say like if if someone calls a paing pre compile on linear then we have to prove it that like it has we have computed correctly so we have to we have to show b54 precompile but the let's say the the curve we are working in is build pls2 377 for aggregation reasons it's yeah it's just is what it is makes sense uh so next question can you show the benchmarks again Yes actually we have like a technical issue can only show the questions at the end yeah but you can take the questions offline with EVO after his talk uh so the next question does it work inside Nova folding step it's a good question uh unfortunately I I cannot answer it uh probably I think it probably would but I I do not know the techniques exactly to to answer it concretely uh next question is how do you generate Randomness in circuits okay that's uh that's a very good question and actually like this is one of the like one of the uh nice improvements what we have so for plon what we do is that we we don't use vanilla blon we use uh Like A variation of blonc where if we want to let's say hash some variable inside the blon circuit then we like copy this this uh this variable into this uh another let's say another column of like of blon so we have a different um uh one more column and then essentially we use the commitment to that column as as the random value so we don't see the next question but I can read it from the phone can you use katuba for direct multiplication instead of school book I think it's for the extension maybe yeah yeah we can and actually like this is uh this is how we did things before uh and yeah and I believe it's going to be some more optimizations than compared to the benchmarks yep yep and why if we take the next question one more yeah can yeah can you use this technique to anything that that can be expressed as polinomial I think you explained it for multiplications yeah yeah we can do it uh so we have a plan to also use it for uh uh let's say elliptic curve operations so for additions doublings scalar multiplications and uh we Al Als already expect to for it to to give like a lot of performance improvements and we have one final question it says can we use the same nonnative field arithmetic mechanism to prove secp 256 K1 operations in B and 254 scal field yes we can uh so actually so we prove secp in PLS 12 377 so on linear again we also have to prove the ecdsa promiles and uh so yeah we can we can do it we can do it fairly efficiently I would say and uh like for us because the all the all of the methods or all of the techniques what we use like they are very generic so we can use the field what we emulate and the field what working so everything's gener generic and it would work very well with respect to this question it means it's already implemented uh yes so it is implemented you can just take it as is okay