zkStudyClub - Improving performance of non-native arithmetic in SNARKs (Ivo Kubjas, Consensys Gnark)

Transcript

okay hello everyone oh let me introduce you real quick yep hello everyone uh welcome to a another edition of ZK Study Club uh today we're happy to welcome Evo kugas and he's going to be talking about uh some of his recent work at UH consensus canark and I'm excited about this session because usually we focus on a paper and in this uh in this particular instance I think we're gonna be talking about work that's very applied uh to real world deployed systems and so very excited about that and to have Evo here to share some of that work with us so Evo uh over to you yep thanks Alex so hi I'm evokubez I I work as a research engineer at Clark and

so uh a bit less than two years ago when I joined narc I I was asked to to implement non-native arithmetic in uh and uh so like essentially this presentation is like I'm going to introduce like what we did and then like why we did some things what we did and uh like maybe they're like there are some useful techniques also for for others to uh to use so like uh as I said it's uh it's uh it's rather applied so there may be a few more uh let's say uh uh a few Novelties but like mostly it is taking things from like existing uh like existing papers and like trying to implement the Implement them so so when we like when we are talking

about snarks uh so uh like usually like usually we work over uh some let's say pairing friendly uh elliptical and uh like and the operations are defined on on this color field uh like of the uh of the curve so meaning that the so any kind of arithmetic what we do like it uh like it's done in the field and so we like if you do the multiplication like if it overflows let's say the the scholars field then like uh then we well then we like they take the uh then we reduce it by the let's say the native field and uh like we get the we get we get the result so we have to Define let's say the the circuit as operations on on this native

field uh and uh like after we have defined the circuit so like we usually like we arithmeticize the circuit like into like some kind of a representation at some point uh return unless it is a representation into some let's say some some polynomials and then what the proverb has to do the approver has to show that let's say some relations between like this polynomials um stay home so uh for example like if we multiply the polynomials then like we get the resulting polynomial and uh and the yeah this is it so uh so like uh let's say like if circuits are big then so if the circuits are big then it also

means that the like that the polynomials themselves are are quite big so the polynomials are like are of degree like they may be of degree like several several Millions uh and so it like it would be like really like invisible like for the proverb to send let's say the the whole polynomial over to the verifier uh like to verify that let's say this this relation solves so we use something called let's say polynomial commitment schemes uh and in that case what the proverb does is that instead of sending over the polynomials people overall just sends the commitments to these polynomials and then the verifier can ask uh please like please evaluate this polynomial at some particular point and send me send me the result and like if we have this polynomial commitment scheme then like

we can do it like very efficiently and like especially like if we work in this uh something called pairing friendly elliptical group then then we can have like a very efficient polynomial committing scheme so like essentially the opening is is a single group element and this also makes like the snarks like really really really efficient or let's say it makes the very firework like really efficient but it uh we we are we are still like we are still left like with the problem that let's say the approver has to compute let's say the relations between these polynomials so uh like if you have let's say a polynomial of 30 degree one million another polynomial of degree one million and if the Kruger has to compute let's say the product of this polynomial polynomials then if you would do it like

natively or like natively like how uh then we can apply let's say this is a school book like multiplication we take the coefficient or let's say the pairs of pairs of coefficients we multiply them together and then we take let's say some particular uh products we add them together and then we get let's say the coefficients of of the product polynomials and uh like it's like for people moments it is invisible so like if you have a polynomials of degree one million then like it would be like one million times one million uh like uh multiplications and it's like it's just like him like impossible to do so in in many cases uh or like uh like uh how we can solve it is by doing uh something called fds or

entities so it is uh number theoretic transformation so like essentially what it allows to do it allows to us to fairly efficiently uh go from uh go from let's say this coefficient form of a polynomial into evaluation form of polynomial and if we are in a revelation 4 of a polynomial then we can just multiply the evolutions together and then we do the inverse entity and uh then we get back let's say the product polynomial in coefficient form and uh yeah very good so the the so the Brewer work is also um uh small also like to be able to do that uh we need something called like high to edicity so

meaning that we'll like we need to have like some very high uh degree of unity so so that we will be able to do density so we have additional restriction on this elliptical uh what we are working on so that it has to have like this too high I just we also have one more let's say restriction on the elliptic curves uh what we want to use so they have to be secure so they have to be sufficiently secure that the discrete log uh logarithm problem in the curve itself and let's say in the let's say the the G2 or like let's say the the the paired group is also like um it's difficult and also like in the in the Target group so essentially we have let's say three restrictions on this

elliptical group so it has to be pairing friendly first secondly it has to have like uh too high uh High Duality and finally it has to be so it has to be secure elliptical groups and uh so we we are safe we can do we can do starts but uh if we want to implement let's say if we want to implement some practical applications for example if you want to verify ecds signatures or if you want to verify RSA signatures or or if you want to do uh for example PLS signatures or we want to do like if you want to check uh some pairing like pairing

pairings inside the inside the circuit then like usually the fields what we are what we are working on in the Practical applications they differ from let's say the The Scholar fields of this molecules of the elliptical groups so there may be like uh that like there may be like very small overlap if you have like some let's say two chains or let's change or titles of Curves uh in in what cases uh let's say the the base field uh or uh the scalar field of one ellipt curve is a base field of another elliptic curve so like essentially in that case we like we are able to uh Define a Stark in like in like in in one uh group uh we compute

the the proof and then we can like very efficiently verify it in let's say in this uh out curve uh because like essential load operations are performed on scalar fields and then we can do it like very efficiently but uh like these use cases are I would say uh uh like minor compared to uh compared to the let's say the tradition uh what one to do and so to overcome this problem uh we have to do something called non-native arithmetic so we have to be able to do an arithmetic which is not native to the scholars field of the elliptical and this is what I'm going to explain explain uh like there are several ways to do that so like the the first approach

using the Chinese remainder theorem so uh with this it is uh somewhat related to let's say school book uh like integer multiplication and like additionally using the Chinese remainder theorem like to uh to to allow for like some let's say uh checks uh checks to be done uh I think like this approach is used for uh in in in uh in brettenberg I think uh then uh like second approach is using like this uh casting out primes or nines approach I think like it was proposed by by polygon at some point like essentially it is uh it is a

recursive scheme where let's say that is non-native or the corporations they are deferred into let's say uh later iterations of of this recursion and when they can be done like natively or like let's say more easily so what I'm going to introduce or like the approach we are taking in cloud is is using like a Json style polynomial identity identity testing so let's look like how we can do that so let's set the Let's uh first uh set let's say the environment we are working in so we have let's say we have the native field uh which is defined by the scholars of the of the elliptical and let's say the modulus of the Native

field is is r and then we have the non-native field what we want to amolate and let's say the its model is is q so we are taking I would say like very uh very straightforward forward approach so we are using like let's say let's say this is a multi-precision integer representation of a representation approach so what we do is that let's say like if we have some like long uh let's say if you have some non-native field element so we look at at it as an uh like as an integer and then like if it is an uh if it is a long integer then we can split it up like into let's say into smaller limbs so for example limbs of size 64 bits

assuming that they like that these names like fit into this into the fit into this native field but they usually do because like this elliptical group the fields of of uh good groups uh let's say they are usually like 250 five bits long so we we fit like nicely and we also have like let's say some some spare room for operations when we do this multiplication Precision integer arithmetic so in that case uh so if we split the split it into limbs then uh like we can like let's say from this limb representation go back to this let's say into the integer representation by just

uh but just recombining let's say the limbs with the corresponding coefficients and so we can like shift the limbs back into right places and we get the the initial integer like illustratively like let's say like we have the native field elements and then we have the limb like limbs no native limbs uh like in this native elements so addition what we have to do uh so like if like if in the beginning uh if we split let's say the non-native element uh um into let's say 64-bit limbs or like some fixed fixed length the limbs then after some operations uh we may happen that let's say the value uh like we need

more bits to represent this value so for example like after after addition we need one more bit to represent the result of of addition so additionally of keeping track of the of the uh like of the limbs we also need to keep track of the Overflow of like every limb or like actually like if the if video if we do the Opera operations like limp wise uh and they feel like group multiple limbs then like we can use the same overflow for four different instruments okay so let's uh let's look at the arithmetic how we can do multiplication arithmetic [Music] yeah so let's uh for now uh we just do integer automatic so we do not uh we do

not consider a modular modular reductions for now because like we can do it because uh so if we do Intel like integer arithmetic so at some point uh we can reduce let's say this uh integer like which overflows the non-native modulus we can reduce it back uh to to the non-native field and uh like essentially we can amortize this uh this uh this cost of modular reduction uh and it may save us something so for the for addition addition is simple the what we can do is that like essentially if we have let's say two multiprocessing integers then we just do addition uh lim voice and uh and that's

it so the result uh the limbs of the result they're just like let's say that the sums of the of the of the input and that's it for the Overflow uh like as I said before the Overflow is just one more what was the like maximum overflow of like of the inputs so look this is uh this case and hopefully like everything else is also going to be easy so let's let's look at the subtraction uh let's try to have like a very similar similar approach so we take the multi-precision integer uh but then we subtract limb piling and now we Encounter of the the first problem or yeah the first problem so like

essentially the problem is that let's say if the value we are subtracting like if the limb is bigger than the value that we are subtracting from so like this means that we get underflow in the native field and this like this message is like everything up the picks like our assumption is that the limbs are of some particular like particular resistance if we like if you're underflow then this assumption doesn't hold anymore but luckily we can we can somewhat easily overcome this uh this problem so like essentially what we have to do we have that we have to add something what I at this call subtraction padding so like this is uh like particularly

constructed value which is a multiple of non-native field and uh like and it is constructed in a way that every limb is strictly larger than the value we're subtracting so like this means that we we do not like underflow the native field so instead of uh instead of a subtraction um we add the subtraction padding and then we do the subtraction uh limb and uh then all is good now uh let's uh let's uh look at the multiplication like similarly as for a polynomial multiplication uh we can like we can

also do let's say an uh like integer multiplication uh how it works is that like essentially we have inputs A and P which consists of Limbs and then we have to compute the limbs of the like of the product until to compute the limbs of the product we just have to take the corresponding limbs over the indices add together to the in the index of the limb we are we are Computing and then we like then we take we complete the product we add them together and then we get let's say the name of the uh of the product like we can see that if the number of

let's say if the number of Limbs of the inputs is n then the number of Limbs for the result is like is 2N and to compute every limb uh like we have to do up to like um uh up to n multiplications so this means that like essentially in circuit complexity of multiplication like naively will be N squared uh like it may or it may not not be a problem if if any small but uh let's like let's try to improve this approach specifically for cases where the field what we want to emulate it is Big so let's say like if uh if the field we

want to emulate this for example several thousand Bits And if we split it into like 64 bit limbs then like it means that the the number of Limbs is like it is uh it's many and like this the quadratic complexity there like it uh like it's it's really bad so there was a really nice operation just to clarify your uh Evo so that so n here in terms of the you're talking about complexity is is referencing the number of Limbs is that yes okay cool I got it um so what the the authors of XJ snark paper uh like they observed is that like we can also uh have let's say a

polynomial representation of uh like often a multi-precision integer and so like essentially we have a polynomial but the coefficients are actually the limbs and like in that case like if if we evaluate this polynomial at like at the basis at the basis uh let's say that this uh multiplication basis then we get back the the like initial integer but uh for now we like we're just in like interesting like in the polynomial itself and so what they proposed is that instead of doing let's say in circuit multiplication uh we compute let's say the the limbs of the product uh also like outside of the circuit computational or advice like uh however

however anyone calls it and then we have to show uh then we have to show that let's say the product of the polynomials uh corresponds to the product of uh corresponds uh like to the resulting polynomial or the polynomial which represents the product of uh of the input integers and like usually like usually like if you have like this kind of let's say polynomial like relation we can use a like a short simple so like uh we can evaluate the volume like polynomials at only at a single point and then we compare like get anyway multiply the the evaluations and then we just compare like that all is good but we really like uh I would say by

default we really cannot do that because we don't have Randomness since records uh and that's select and uh but and that's a problem but uh luckily because the number of limbs or number of limbs or also the degree of the polynomial uh what like this multiplication integers I represent it is relatively small then like actually we can we can just evaluate these polynomials that let's say some constants and some small number of constants so like for degree n polynomial it is sufficient like that we evaluate them at n plus one uh points and then we are we we have to check like this uh this relation there

uh and what is like really nice in in r1cs uh so uh is that like actually um a multiplication by constant it is kind of free so it doesn't add let's say it doesn't add complexity to the to the approver and also additions are free so actually like evaluating these polynomials it is like it is free so we're we are only left with the of uh of this uh Computing the product of the revelations and also like this assertion so essentially it means that pair like pair input value we only have two constraints what we have to check and like if the number of Limbs

is constant so this is like essentially two two n uh constraints of what we what we have to add um so we get the of n multiplication complexity but this is in r1cs so in Blanc Blanc it doesn't work that well I'm sorry yeah all good I was actually about to ask that question what you're saying but what can you just describe what the slide you have T and C apply I guess what is uh can you just Define with that that yeah so datums and conditions applied so it doesn't it doesn't apply for Blanc

multiplication complexity let's say the proper complexity is still o of N squared so let's uh let's see like if we can fix it like in like in the future uh I also have a I have an equation like how we can compute the Overflow of the of the of the product uh so just we can keep it in mind it's not important uh but what is important and what I like very smoothly uh went over is that like actually we have to also a rain check um the limbs what we got like from the hint because otherwise let's say the Brewer provides a limbs or let's say values which have bigger width than than what

is allowed then like if if you would keep track of the overflows then at some point like we can overflow the native field and uh and we don't have Sound Circuit anymore so like actually we also have to do the rain checks and now finally uh reduction so right now the multiplication was integer multiplication so there's a result is big it is a it's way big so we have to like occasionally reduce the uh this big interest back into like into the into the economical representation um I say that we can amortize let's say a multiplication so we do not have to uh reduce them all the time but like in

practice like heuristically at least my experience is that like it always makes sense to reduce after after every multiplication and the and why like we need to do that essentially is because like the number of Limbs like let's say the number of uh like input limits is n so the number of let's say the result the the number of names for the result is 2N and like if we will multiply two two and limb uh integers together then the the result has four end Limbs and like it the number of Limbs actually occurs exponentially and it's not good like even if you have like let's say this linear linear multiplication complexity so we should always model this

how uh like how we're doing more introduced so it's uh like it is also uh let's say on High level it is simple so let's say we have some like let's say value which overflows the the modulus and to overflow to mod reduce it so we have to show the that the reduced value so the difference of the value we are reducing and the and the reduced value so it is uh it is um let's say a multiple of the non-native modules so let's say that that there has to exist Alpha such that the difference uh like the difference uh is uh Alpha times uh non non-native modulus

uh like this um a quality check is for multiple multi-precision integers meaning that like we have to be able to like uh check that the like two multiplication integers they are equal to each other like somehow let's try doing it the limp wise again as we did for additional subtraction but but the problem now like is that let's say the overflows or let's say the excesses of the of the limbs may be different but like actually like this is something what we can solve quite uh like in a straightforward manner so we can carry the excess access of a limb which has let's say which is wider uh to to the

next length so we just partition The Wider limbs so that the the results will have the the the same width and we carry it access over to the next limb and so so and so on and then we can do element wise comparison so maybe uh like one thing what we what we observed is that like if we have let's say this polynomial representation of the uh of the uh elements and also like if we construct a polynomial representation of these excesses or so we have a polynomial where the coefficients are a zero a one and so on can check the quality like using this

polynomial polynomial relation so like we have this coefficient uh let's say coefficient uh 2B so it's the basis for multiple Precision integers so like essentially this multiplication by this constant like it just shifts uh this uh this uh value like let's say to the end of the like to the top bit of uh like all of the limp and like multiplication by ax like it just moves Texas to the next line so we can have I would say this nice representation for uh for uh checking to uh multi-processing integers

but as as I said before it makes sense to do multiplication and the modular reduction like at the same time so if we combine multiplication model of reduction uh like enter into the same object into the same check then you get something like this so we represent the multiplication integers as polynomials and then we have to check this relation on uh I would say uh some number of constant points and then like then like if this holds then the mole mod is is correct so like similarly similarly as for uh plane multiplication it is quite good

for uh for r1cs because uh multiplication Point constant is free also addition is free it is slightly or it's a lot a lot worse in Block but like actually we can avert I would say like some Badness in Blanc because like we can do a lot of caching we can do with caching because in a lot of cases the let's say the output or let's say the residue C it is an input to some other check whether it's either a or b so like actually like we can cache the this polynomial Revelation so we are we usually we only have to evaluate polynomial C we have to evaluate this polynomial Alpha and also

polynomial e now because the queue is like Q is a 80 static overall checks and we cached A and P so uh it's it's not that it's not that bad it but it's still it could be better okay um so we have optimized the more mod and actually I would say the result is quite good so let's say if we have uh if we have if we work on a pn254 and we want to emulate the 256-bit field like on 64 bit limbs then like it's a like in it's approximately I know 14 uh let's say uh 14 constraints like

in plonk like if we like if you if you use caching so it's it's not that bad uh but like we have to rain check so we got the values or let's say the limbs of of the polynomial uh C Alpha and the like from from hint so we need to rain check them and actually like if we like if you do naive rain checking then this means that like we have to rain check or we have to compose uh like the element into bits we have to show that every bit is actually a bit like using this this check and then we have to show that they're like these bits add back together like to this value like what we what we obtained

uh like from the hint and like in practice like this is like this is actually like where like most of the cost is so it doesn't it uh like uh like in a big picture it doesn't like really make sense to optimize you know a few constraints like in in more mode when like in the end uh for rain checks we have to do 600 700 uh uh checks like uh to ensure that what what we received from like from from the is correct let's let's try to start optimizing the the rain checks first we we looked at uh at Ultra long so Ultra blank essentially it is vanilla

Blanc with custom Gates and plookup so uh what does it mean is that like essentially in Ultra plant like it's possible to tag some elements what we want to check in the in I'll say in a proof system or that the elements um let's say the the variables what we had tagged attack uh they are in somewhat or or in some lookup table and the lookup table like what we will construct is essentially a list of all allowed values so it is from zero to to the to the 16 up to the 64.

so whatever is uh is the width of the of the limbs what we want to allow we didn't take the server they we didn't take this approach because like this approach isn't really good with with the cross 16. um and uh for plonk uh or so it's not good for processing like essentially because I wasn't able to figure out like how to make it work with cross 6 16. so maybe it's possible I I wasn't able to figure it out uh for plonk uh it would have worked I think it would have worked nicely but at least my in my impression was that it the it would have integrated let's say the front end so let's say the

like how we write circuits and the back end so how the proverb computes the proof uh like it would have integrated them a bit because like essentially we would have to carry over like let's say this information about what the variables we are we are rain checking like what are the rain check values and so on and so and we didn't want to do that so we want to keep the front end and back end somewhat I would say somewhat uh clearly separated so for example like this allows to have let's say different front ends for Mark so for example like there is also like Noir front-end partner so it's possible to write circuit in R and prove it in ignore and I think it's it's really nice to have

like this compatibility second approach uh what we we looked into is is using something called a permutation Network so we looked into arbitrary size Waxman presentation Network and in this approach uh what we would have done is that like essentially if we have some some variables what we want to rain check then we uh then we fill in the values what parent train checked in the let's say in the allowed range then we permute all these Arrangement values into into order and then like after the permutation network if the variables are all in let's say in

increasing order then we can add constraint that like every sequential value is either the previous one or one more than the previous one and then like then if all these constraints hold then it also means that the inputs were also all in let's say in this permitted range um actually we implemented implemented this approach but it didn't give uh I would say significant Improvement so it didn't give significant Improvement in in the sense of the number of constraints uh what we have like in circuit and also it was quite difficult to compute let's say the values of the

switches if like every switch in the permutation Network are either swaps or doesn't swap the the the wires so it the overhead was quite significant and so finally we thought about like using let's say a multi-set multi-set using uh local integrative argument this present result but for this like we need like for this we need randomness and then like and in this approach so let's say we have a lookup table and in the lookup table we have all the parametric values so they're all values in the in like in the range uh what we

want to arrange in so uh these values in the in the tables are FIS and then we have the histogram so like how many times every value in this table is is squared like these are this let's say uh coefficients or let's say that the histogram kis and finally we have the lookup SJ but for for this to work like we have like we need to have some randomness or we need to have let's say random verify challenge and like how like how can we solve how can we get uh very far random verified

challenge which depends on something like on some inputs so very I would say uh very straightforward approach would be to use like 30 mil and Cashmere in circuit um uh so and like how like how it would work is that like essentially let's say we would hash all the inputs into like uh into this uh and then we get some random challenge we we use this random Challenge and all is good the the problem with this approach is that like actually like hashing in circuit is expensive so like if the let's say the cost of hashing like in

circuit it depends on the number of inputs uh like uh to hash and it's uh like it is at least I would say a few hundred uh constraints uh like per input and so it doesn't like really make sense so it's uh so uh like compared to this uh uh log derivative argument itself like the cost of doing theater in circuit like it was like it was too expensive so it didn't make any sense so maybe we can do theater outside of circuit so like essentially the program will just provide let's say the the elements to to Hash to the verify the verifier computers the virtual map Challenge and like this challenge can be

used like in circuit like as a randomness but this puts a very big cost uh for the verifier and also like uh it causes uh it causes a privacy loss so because the prover has to provide all the inputs to the very first to to compute the achievement challenge and so uh like in in for something unrelated like uh we we were using like um The Lego star commitments and uh like actually we uh we realized that this is something uh what we can use so what is uh Lagos narc style uh commit and Care scheme

like essentially it is an uh it is an extension of cross 16 where it's possible to let's say commit to some values uh let's say Fitness like Fitness element values yeah like uh and uh to use this commitment in some other circuits so essentially it allows to modularize uh different cross 16 instances and to share some witness values like between let's say these different different modules modules uh but we what we realized that like actually like this commitment can be used as uh as uh let's say it is a verified challenge inside the circuit so Lego snack so what is the difference

between cross 16 and the and let's say augmented clock 16 as defined in Lego smart paper so like essentially in vanilla across 16 we have the Prof LMC a b and c and they added like additional elements T and T Prime what is actually like it's uh very similar to C so essentially it's splitting C computation of C like into parts and the T Prime this is necessary to to be able to uh for the Brewer to show that the prover actually used let's say the um The Proven key or let's say the commitment key for computing this team the verified work uh what the uh what's

different from like from a vanilla Pro 16 is essentially um what one garment application one addition and one more petting check so it's one like the most it cost is one additional petting check so the commitment so like we saw that actually it is a Peterson Vector commitment scheme and uh with uh with the part of the Brewing key as a spaces for the commitment scheme um and so the security in the paper as like as I understood or at least how I uh how I um like I'm imagining imagining it is like essentially that this let's say it

is augmented cross 16 it is very similar to cross 16 and if if the commitment wouldn't be binding then this also means that the the this uh the initial across 16 instance like it would be possible to compute the let's say multiple weaknesses uh to a particular uh let's say circuit instance so it means that the circuit itself wouldn't be sound so if the circuit is sound if it is well defined then it means that also the commitment itself it is binding Additionally the approver is not able to let's say predict the the commitment because like this this would mean that the Brewer will be able to solve discrete law so it is a very good uh very good uh I would say

um think choose for for a challenge in like inside the circuit so additionally what we have to do is that we have to Hash uh this let's say group element into into this color field and then we can use it as a as additional public input I promised in the description that like this technique I would say on High level also works for Planck so not not precisely uh like using this let's say augmented uh scheme as in Cross 16 but essentially for long while like what we

did is that we created a custom gate where we Mark some variables uh to be committed to and then we represent like these variables as a polynomial uh uh and the commitment to it we use as a random challenge inside the circuit so if we have let's say a Randomness inside the circuit what can we do uh so uh first of all we can extend this single commitment uh into multiple commitments uh so like in essence we can compute multiple commitments like inside our like using this commitment scheme what we do not really want to do that because like this would mean that like every additional commitment but we

compute in in the proof system it requires additional pairing check by the verifier so we consume we can we can extend some commitment inside the circuit like using caching we just split the commitment into let's say a domain separated like as values or we can use it for example for folding uh like inputs uh what we are like using in the in the lookups or we can also like we can construct using this log derivative argument in like in addition to uh let's say in addition to rain checks we can do like arbitrary uh table lookups and like using these table lookups we can also do

let's say Boolean functions so we we pre-compute the the let's say that the whole table of some like polar function on let's say 8-bit inputs and the pre-populate the stable and then we can instead during the computation we just look up the values and also like uh we can fix the problem or let's say the quadratic complexity problem of mole mode in Block because like now we have a random Challenge and so instead of needing to do multiple checks uh in in Block we can only do it on on this random like random value and so in Blanc we also have now a linear complexity let's say linear complexity to check the modular

multiplication so uh from practical point of view so let's say the protocol itself is sound but we also want to like ignore we wanted to make it let's say sound for users to write circuits in so we have range X here and there for example uh we have to arrange check the inputs we have to reject the output so we have to range check the let's say values provided by the by the hints so we hide like we hide all this complexity and like like even more so uh we don't just hide it we do not allow the users to let's say avoid some rain checks what needs to be done so at least let's say from from some GitHub issues or like some discussions so like people

were proposing like removing some checks like to have more efficient prover time but uh like we want to completely avoid like uh uh to to to prevent some some checks to be done so like instead of like having something like this we just do everything automatically so we drag all the inputs uh for example and if some input that's more non-native input is encountered in some operations then you automatically arrange check all the inputs uh like what have to arrange it so for like for user like it it should be like really straightforward um in regards of let's say composability let's say we have a multiple instances of ecdsa we have like several and non-native fields we are emulating uh so

like everywhere we have to let's do the rain checks and every like every everywhere we have to initialize the the this rain jacket Gadget and then like finally we have the final like finalize we have to compute let's say this log derivative argument uh so that like everything sound we added I'll say some some lazy methods so that everything is done automatically the let's say a rain checking instances are cached so every time uh like uh somewhere we need rain check then actually like we are collecting everything into one big let's say instance and so that the this allows to optimize the range X what we have to do because um there is some I would say constant

overhead of initializing a ranging table which is constructing the the let's say the left-hand side of the log table argument okay and finally we also do let's say automatic table size computation so depending on the number of rain checks the size is the rain check range we automatically compute like what is the what is the width uh we are in checking so like usually like like if we need to range like 64 bits then like we cannot like we cannot build table of size 64 bits so 2 to 64 bits so like actually we partition like this input into let's say into smaller groups and then we arrange it the rain check

the smaller groups and we also assert that these groups are back together to this value what we're rain checking and uh like if we are like if we can optimize the size of the lookup tables then it means that they're like the these groups or partitions are larger and then we have like lesser partitions and then we have lesser constraints but we have there so finally um uh Benchmark wise or let's say runtime wise uh like I think like the the first thing to keep in mind is that it's it's not really it doesn't really make sense to compare the number of constraints because like every outside like every uh snark framework is slightly different and like it's it's not possible to have

like let's say apple slap in this comparison if you just kind of like compare the constraint numbers so I think I I think it's like really good like initiatives where um let's say the where uh like different snark Frameworks are compared to each other like on the same systems on the same uh same types of circuits on the same same groups and so on and so that it would be so it's possible to like have some kind of like comparison like hold like who is good in like in in what aspect but like just for uh just for completeness I yesterday I I ran like some benchmarks like using all these these techniques and like these are some results uh like what I had on like on my

Mac so uh we we improved everything on pin 254 and like this time for like solving to witness and also like proving so for ecdsa or uh or let's say a Bitcoin curve or a Bitcoin uh coverable ethereum curve it's a approximately approximately 1.3 seconds and so on so you can see it in table I also I tried running the benchmarks for plant but uh like when like after the after the second Benchmark I realized that I had like introduced some like let's say memory some issue in the in the plant proverb so like actually like this uh run times they were a bit off so I didn't complete the the benchmarks and like hopefully we

get we get the the the the blog prover fixed soon and then we can also provide the benchmarks for uh plot brackets and that's it thanks thanks for listening a quick question sorry on this slide what is the number of parenthesis uh so there are a number of constraints uh okay let's say that can train number gotcha okay okay cool awesome very helpful people like to compare the number of constraints but uh yeah I guess it's maybe useful within the context of a single proof system as opposed to like a cross proof systems Maybe yeah so like it makes it makes kind of sense for auto and CS because you know foreign

this is a great presentation thank you very much for sharing this I mean again I like this because there's a lot of this is very applied in terms of practical problems I mean we talk a lot about Theory uh in this in this in this group and that's obviously very important as well but but application is uh is equally important so and obviously you have Z prize highlighted here which is another initiative that I run and I think Gautam is on the call and you guys worked on a uh team in general submitted a a very good submission which I I don't know how much of that submission was based on this presentation but it was the winning submission for the mobile MSN prize and I guess I do want to just mention that for this coming year we're actually having a signature verification category for pcdsa SEC b256k1

um to be you know for uh inside of a inside of a Marlin snark um Marlin plus plus technically we have a new a slight tweak to the proof system maybe pratige can mention some of those tweaks um if he's interested but in general this is very relevant for this year's e prize I think this is one of the things we want to focus on so hopefully you'll be able to you'll have a chance to apply some of this knowledge in that context um I have a bunch of questions but I'll pause and see if anyone else wants to add a comment ask a question the score is open okay maybe I'll ask my question then to

kick things off uh here let me see if I can get back I need to fix the view options real quick okay great now we can all make sure all the all the cameras are in the right spot here okay great um my question was going to be you're talking uh well is one way to think about this as an optimization problem I guess one way to think about this is as an optimization problem and one question that I have is are you really trying is the core Improvement here about reducing this the number of limbs or is that not relevant to actually having a higher performance I guess I'm trying to like map back to the earlier parts of the presentation about you know the limbs and how many Limbs and the potential complexity which

grows in the number of Limbs so is it really about reducing the number of limbs or is it about other techniques that that really make that dominate the problem uh I I think like it's a let's say the complexity is dominated by by the rain checks it's like like even if like even if the if we do like let's say this table based train checks then uh like it's still like it's still a majority of the cost so it's uh uh so when like when I I have tried out then like uh for example uh uh so for example for ecdsa uh over like SEC p256 K1 so like actually it makes more sense or it's slightly better like if you have four teams like compared to three so

like theoretically we can fit into like three limbs uh but in practice it doesn't give better results because uh so uh for example like for addition uh like it still makes sense to amortize the model reductions and let's say if we have let's say more room so if we are using like 64-bit rims then actually like we have more rooms to do let's say like this amortized operations we have before we have to model it just so it is like slightly slightly slightly better like if you use for limbs then if you're using three limbs but like there is a like a small difference gotcha so it sounds like it's a little more complex but the range checks is really the

dominating Factor here one other question that I have and I think it's actually kind of answered by this slide of benchmarks but I was going to ask how uh how specific um you know to each non-different type of non-native operation is any given implementation here so I guess like how General are these techniques when applied across all non-native arithmetic operations you could imagine as opposed to like specifically SEC p256 K1 like are you do you imagine like or I guess I'm I'm just trying to understand like the level of specificity um that goes into each one of these implementations or is this just kind of a general technique that works across the board it looks like from these Benchmark so that it seems like there is quite a bit of

variation depending on the specific arithmetic that you're doing but I'm curious your thoughts there so actually actually it's like that was like that was Article so like uh so when I when I looked at the outside like other implementations then I would like at least my impression was that for example for each DSA like they were like really tailored like tailor-made for uh secretary 256k1 um and uh like our approach like it is complete General so like for example like if I show like uh if I show like these lights so like we can like really easily like initialize let's say this non-native automatic on like on every field uh so uh what we have to Define is the number of Limbs uh like how many

bits or like how many bits we need to like uh to represent the each limp and uh what's the modulus and that's it so like actually we we are also tracking uh we're also tracking the gift module is uh is is prime or not so we can also do let's say we can also do like ring operation so if we don't have like immersions or like divisions so we can do like any like any kind of a field where I I I haven't tested on let's say very big on very big fields but at least uh like let's say um like like I I think it also works up to let's say 4K like bit modulus like it's slow but it should work uh but for

example like like what it works for like a it definitely it works for I think for uh bit level six uh six seven one I think so it's uh like it has 600 later eight one bit uh limbs so like for that it works and it's actually like it's it's it's quite good got it so actually it's so it turns out so I guess what you're saying is the absolute what I was saying which is that really sounds like this work is really about generalizing a lot of very specific techniques that have been applied in different problem instances before yep yep and like if you look at the let's say the equation what we're checking so like we have like let's say this non-native modulus and uh we're just like replacing this one and uh like theoretically like theoretically so right now like we like we fix it at

compile time like but it like it isn't uh I would say an assumption we can also like do it uh let's say a runtime so it's uh so in the context of let's say of ckvm for example we can we can use the same approach for for modeler modeler experimentation and in that case we just take the cube like from there let's say from the from the mod call uh pre-compile call and we we can use it like as is like it has slightly more complexity but uh but uh like not much got it um and then the last question I have is what what we talk you know you have like the benchmarks in terms of latency and you mentioned using an M1 but I guess there's some discussion in here around caching values and stuff and so I'm curious like what's the memory profile

look like I mean his memory come up as a constraint at all or is the is is the bottleneck entirely on the on the on the Computing side or on the execution side so like actually let's say uh like we separate let's say we have the front end we have the back end so like all this stuff happens like in the front end so like we do the old and let's say this uh this uh let's say caching so like like what does it mean that we cache so like like essentially like like if we catch something like 10 let's say in constraint system it means that like actually we're just referencing to like some previously known variable uh and uh like it doesn't

you're not talking about caching in terms of like memory you're actually just referring it to inside okay gotcha okay that's a hopeful clarification yeah so this is so this is not so I guess maybe just ask more specifically this is not a like you know applying these techniques that you're you're this is not really memory you're not memory constrained effectively this is this is really um no these techniques are oh my God so like if you have let's say like if you have like very big circuits like in like Blanc then like uh or let's say memory like we are memory Bound by like entities so but that's that's that's independent of like this work though this is just about that's about the context of block okay cool that's helpful um

awesome thank you this is really super cool stuff like I said I'm excited and obviously given like I mentioned already my interest in zprize I'm excited to see more work like this come out and I think it really is going to help this is like the Practical stuff that moves the space forward so thank you very much for working on this galaxy you probably um are on the call you probably you know contributed or at least reviewed some of this too so thank you and I guess maybe Gautam actually since I just referenced you and you're here do you have any uh anything else to add uh to the presentation any any just personal comments about this work uh if you'd like to add anything feel free oh you can't turn on his mic classic um well anyway uh it is important to note that I guess maybe for folks who

are going to watch this YouTube video later Galton beltrell also on the consensus can Arc team um you know and and a great contributor to uh to Z prizes I mentioned already uh before we conclude does anyone else have any questions comments oh I think there's some chat oh all right now it's just got them saying hi okay well Evo thank you very much this is awesome um uh thank you for coming and presenting it today's CK Study Club and I guess do you have any parting words before we conclude or actually any maybe maybe actually maybe actually I'll just turn this into a final question um where where are the horizons from here what's the next step how do we get this down to being even more performant

or make this this even more performant [Music] so it's like we're trying out like five different things like uh like at the same time because you know most of things doesn't work fair enough okay cool well hopefully next time we have you back on we'll we'll we'll know what the uh what the most fruitful of those five directions uh will have been so um okay great well Kevo thank you very much for being here really appreciate it and thank you everyone for uh for tuning in