LatticeFold - Binyi Chen

Transcript

so uh so hi everyone uh thanks a lot for coming today uh at PSC learn and Sh session we are delighted to have B Chen presenting ltis fault and its application to SN sorry sixense Pro System uh beanie has been working on quite a few different projects obious R memory card memory and uh of course lses and snacks uh with lce FS today so thanks l b for being here and for today's presentation yeah thanks Rafael thanks for introduction and yeah it's a really pleasure to be here and I think it's for the third time and uh today I'll present ltis fold which is a new scheme that

allows you to build a suing proof system for really large statements so it is plausibly postquantum secure but even more surprisingly hopefully after this talk I can convince you that it's actually uh very very practical and efficient so let me start with some background on snar suppose there's a verifile like Alice she has an very very old iPhone but she wants to perform some computational expensive tasks uh which also involves some large secret witness that she doesn't have access to for example she may want to ask a chatut some question about her local information um but she doesn't have the large language model that open AI have so in this case what he can do is to send this question to some powerful party and um so I saw a

question in the in the chat uh posibly uh is that we always on some assumption right uh so so that's why but you you can trust me that I think it's it's a postc secure okay so and let me let me uh continue so uh and uh so in this case he sent this question and then um the powerful party will be responsible for computing this function using her large Secret busness and send it back the answer but here the question arise okay so the verifile how does he know that this exactly the correct answer instead of some junk information right and one way to achieve this is to ask the

powerful party to attach some small proofs called Su synct n arguments of knowledge proof so that correct verification of this proof implies that the power party indeed knows the large secret witness and this computation was done correctly and a key requirement for this proof is that it should be very very short so that it's easy to send to the verifile and moreover it should be very cheap to verify uh even if the verify only has a very very old iPhone okay um so uh this is just a to example but in practice there are tons of applications for SN proofs in scaling blockchain and machine learning and fighting this information for photos and videos and

etric and in the recent year there's higher demands for having having a pro friendly snar uh meaning that even if you want to prove some very very large statements uh and very very complex statements we should be able to generate this proof uh relatively efficiently so to do this uh in the in the in the practice in real world I would categorize that there are two classes snarks well I will call this traditional snarks as modelistic snarks which generates this snark proof all at once and in the literature there are many such schemes like gross 16 plun PL Spartan bully proof exentric and even in the postc setting you have some very nice candidates of proof systems like Stark uh and and cetric and in the postc

setting usually they have uh relatively larger proof sizes and also uh for those practical lat Bas proof system they usually have very expensive verifile which is usually linear has linear time complexity but in general for for many of the schemes they are working pretty well for those midlevel size statements like uh aristic circuit for 26 Gates however when it comes to prove some very very large statements like an aristic circuit for two to the 30 Gaye um they have some caveats and there are some limitations there and one of the key limitation here is that you have to fix these statements uh even uh and also get the witness even if you before you start

doing the proving so to illustrate let's consider example well suppose you want to prove the correctness of block of 10 10,000 trans eum transactions are executed correctly with respect to some updated ler States and then as a appr you really have to gather all this 10,000 transaction information and reexecute them and transform this execution transcript into some very very long Vector of extended witness and only after that you can start doing the proving but at that moment you already waste a lot time right and moreover because this weakness is really really large you have to use some really large um like memory machine in order to fit this inputs into the snack machine and

run the SN algorithm and also it's very hard to gets a very nice paralyzation unless this s schem itself is paralyzation friendly so given this an alternative strategy is to construct a piece me snark um that is based on this incremental verifiable computation or proof carrying data so the high level idea is the following say you have some very large uh complex statements the first step is to split these large statements into many chunks of small statements where each statement is for some uh uniform smaller relation uh I will call it R chunk here and in generally we note that there do exist some recent work called mang gr that

tells you that we do have some very efficient transformation from some arbitrary aristic circuit to a boun of uniform statements so this uh this step is actually pretty cheap and efficient to uh to to achieve and to instantiate and after having this many chunk of statements our goal is to prove correctness of all these chunk statements using some recurs recursive recursive strategy to obtain a small snark so specifically let's say we have already split this large statement into many chunks chunk of statements this shaded rectangle here and then one way to do this is that we can build a binary tree for example and design each node of the tree a chunk statement

and moreover for each node of tree we generate some SN proof for the following statements so first we proof that indeed this local chunk of computation statement is correct and second we'll also prove there exist two SN proofs which are the SN proof generated by the two children of this noes and they are correctly verified and here the essential requirements here is that this proof should be very very easy to verify should have some sub linear complexity with respect to the statement size and this is essential to avoid the circuit size blow up when you do the recursion and finally uh when you obtain the SN proof for the root noes and this proof can serve as the snot proof for the

original really really large statements why because this proof implies that this trunk statement at the roots is is satisfied and by the recursive arguments because the two children proof are also verified that means the the chunk statement in left sub tree and chunk statements is Right sub sub tree are all correctly verified and satisfied and that means all the statement in this tree are satisfied and that implies the original large statement is correct so this is the high level strategy and it's obvious that it has the advantage that the memory overhead is much smaller and is very very streaming friendly and this memory size is only proportional to the statement size of this R chunk rather than a original real large complicated relation RC and also in label some very

generic strategy for paralyzation where you can do this uh um compute this uh this tree along with each branch of the tree so it's very paralyzation friendly as well however um in practice uh until very recently there's no one using S strategy why because they introduce some noticeable exra recursion overhead first for each node of the tree you have to generat a separate SN proof and even worse in this SN proof you have to prove something Beyond this local changle statements right you have to verify that these two snack proof are correctly verified and the slack verification circuit actually sometimes very

expensive to represent it in an arithmatic circuit so that's why is actually not that practical if you directly do this so to address this limitation recently there are many Works trying to uh um come up with and build a new scheme or new primitive called folding scheme to reduce the recursion overhead so at a high level this scheme works as follows so say we have some relation well the instance is some short commitments to some witness and this witness also satisfies some other uh predicates and then suppose we have two instance which the pair um C1 W1 and C2 W2 then this folding Pro algorithm will do some computation and output a folded

U commitments and witness and also some uh small proofs and later the fing verifile after U getting the these two input short commitments and this one output commitments and this proof we check that indeed this out commitment is consistent with these two input commitments and by consistency usually would just mean that is some correct linear combination between C1 and C2 um and one important property here is that this not sence property well even for some possibly malicious Pro algorithm if she can come up with some output commitments and the proof such that it passed the verification and moreover if she knows some correct

witness for this 40 commitments that is in the relation that implies there exist some extractor algorithm that given blackbox access to p uh this malicious Prov can actually know and extract some witness W1 W2 for the original input uh commitment for C1 and C2 so in some sense it's kind of a reduction algorithm that that's reduce the checking of two statements into one statement okay so with this scheme in hand let's see how we can constructure more efficient pie me snark but Simplicity let's just assume that there do exist a transformation that split the large statement to into many CH chunks and for now let's just consider a Chan instead of a tree but

that's ideas are similar and now supposed we have folding scheme let's see how we can build a pie M knock so to do this we'll come up with a default commitment openings first which may be some commitment to a zero vector and then we'll continuously uh apply this folding Pro algorithm to merge these online statements C1 C2 to CN onto the like to update it and merge it into the new folded commitments and openings for example in the first step I merg C1 W1 and cfd Z wfd 0 to obtain a new commitment openings which is cfd1 and wfd one and the Second Step I do something similar and obtain the next folded commitment openings and then do

this again and again for end times and finally I will obtain the final merged um single statements here cfdn and wfdm which is the cumulation or the folding of all these online statements that we want to prove correctness for and at this step after doing this it seems that the verify on needs to check the correctness of this final statements that is in this more relation our chunk and the correctness of this implies that all this previous chunks are correct right however I haven't uh like talk about something about the authenticity of this output comit cfdn right so actually I also need to make sure that this prover is giving you correct uh

folded commitments that's consistent with uh with the C1 and CM so basically you want to prove that in each step I do the folding correctly and one naive way to do achieve is to ask the approver to also send these corresponding commitments C1 to CN and also the foring proofs and the verifier will check for each step this uh use uh to call this folding verifi to check that in each step the folded commitments are done are computed correctly from the previous commitments and the uh and online statement CI but this is not efficient right because the communication is linear to the number of U Trunks and a very is also n to the number of chunks

where you have to call this fling verifi for n times so that is not enough for a constructing a real snark but fortunately uh the correct solution is actually not much harder well I'm I'm sorry uh can I ask something sure uh actually you can make uh of square root of n chunks right mm uh and then uh it will give you a snark with uh square root of n uh verifier because you will spend square root of n time to check the uh foldings and then provided your chunk verifier is linear uh it will also take square root of n or all of square root of n right I see I see and this is

actually something which is done uh in uh in Breakdown so breakdown can be looked uh upon as a sort of very riment fing scheme which only FS like like I mean this is also doable I agree I agree yeah that's that's good point good point so I agree that gives you square root n but it cannot I think it cannot do anything better using this strategy right because uh in the last case you do need do Square n and in the middle when you check you also need to do Square n and uh I think our girls to to have a like logarithmic or even constant uh uh uh at some point you will hit recursion

threshold but it will be quite large so ideally ideally you want B yeah yeah I I want better definitely yes but that's a good question I agree that if you you can make n to be square of the statement size then using even using this naive strategy you can get some skirt and uh uh solution but I I want to do better okay so so the way to do better is that you can uh embed this uh folding verification inside the relation you want to fot so basically the only difference here is that the relation you want to fot will be slightly more complicated will be expanded relation that also embeds folding verification okay and then the relation we want to fold is now proving

three things so first the witness is a commitment is an opening to this commitment and second as before we want to prove that local Chun of statements is correct and finally uh that this folding verification was done correctly at each step so because it's already uh embedding this relation we don't need to apply this fing verification by the final verifi anyal and here the key advantage of a recursive snar are two fults so first is that we replace the snap verification in the relation with a folding verifile and this folding verifile is actually much much simpler than SN verifile usually just checking a single L combination of two commitments is consistent with output commitment and

second even better we don't even need to generate the snack proof at each step we don't need to generate any proof in in in each step for prover what he needs to do is just to come up with the instance with a pair for this relation and do folding okay so because of this reason it gives you much much more efficient P mear compared to recursive SAR solution uh and now the the question reduced to how can we construct a very very efficient uh folding scheme so in the literature usually the relation want to fold uh follows this kind of formats with the instance is some short commitments to the long witness that is further nearly homomorphic that means that it's very easy for you to do the uh

commitment folding by doing some Min combinations and uh in all in all previous schemes they are using pison commitments which is not surprising right because it's a n homomorphic it's parent free and it has no trusty setup which are all good features however they still have caveat here so in terms of security they are based on this discrete log assumption which is vulnerable to some Quantum attack and in terms of efficiency um they still has mavas first in order to build a efficient p m Sark they need to use this so-called pair of cycle curves that's a more complicated Implement and also slightly less efficient than some regular Elite curves

and moreover for this for representing this uh circuit for fing verifile even though it's much simpler than snu verifile it still has some uh like overhead there and the reason is the falling because in this folding verifile it usually involves two type of computation the first is this elip curve scal application or group exponentiations which is done over the base field of el curve and beyond that there are also some other field operations that will be done over the scalar field of el curve like like those hash operation or some other field or arithmetics so that means uh you have to do two type of

computation over two different fields but unfortunately an arithmatic circuit can only be over a single field so unavoidably you have to simulate some field operations uh in a different field which is actually pretty expensive and that's also one the main reason that this this recursive circuit for folding is actually not uh super super efficient it's still efficient but still has some overhead and on the other hand we see that there exist no lat space fling scheme in the literature and I want to mention that it's also very uh it's not straightforward to extend those lce based proof system to a folding scheme because all those practical um l space system has Min time verifile but we

already emphasized before that we really need this embedded folding verifile or snu verifile to have sub linear complexity in in order to avoid this circuit blow up size so that's not trivial hence we ask this natural question can we construct a post Quantum secure and concretely efficient uh folding schemes so first we want postc security and second we also want uh it to be concretely very very efficient and the hope is without we don't need to dive into this recursive SN uh route where we have we have to verify some Stark or snark in the recursive circuit and generates recursive proofs so here is our main contribution uh the first

contribution is that we introduced lce vot which is the first lce based voting scheme um that's based on some rather standard latest assumption called module shortest integer solution assumption and even more surprisingly we actually achieve very competitive efficiency versus those top fre condom folding schemes and along the way we also um introduce some many folding techniques for Life space commitments which might be of depend the interest uh so now for now any questions I saw there is many chats in the in the chat but I have I cannot see this um rafle you want to mention any other question um it's not really questions

it's more remarks on uh on Research so left was talking about the fact that uh there is a monomorphic uh folding uh I see weeks I actually I will talk about that in the end of the talk so yeah yeah cool okay so let me get started to the uh technical meet now and for for easy illustration I'll consider a simpler problem here where I just need to fold this commitment opening relation rather than the the relation I mentioned before but that already CS most of high level ideas so let me quickly recall um the some backgrounds so recall that in this relationship with folded usually the

incidence is some short commitment that's need homomorphic and now since we are now in the latest world the first scheme come to mind is this atack compact commitments or atti hash functions introduced by ATA in 1996 and I want to highlight here that this this is actually very very efficient so with appropriate implementation and optimization you can actually uh approach the performance of some widely used hash function like posidon hash function um so it's like I would call it the almost symmetric crypto um and uh so how does it work so let's say we we are working over some ring like integer is a ring but now we

consider some polinomial ring like a ring of integer for this SE atomical field and you can understand it as just some polinomial with integer coefficients and each elements will be a ring elements and now suppos we have a message Vector W which is of lens n where each um and moreover we have to constraint that for each element in the in this Vector they have a really really small rather small Norms meaning that the integ coefficient shouldn't be too large and for this message to commit it we just multiply it by some random public random Matrix a here that has very very narrow uh like very few number of Co rows but uh and columns and this will gives us a very short commitment C

uh that is independent on the length of N and as a commitment had to satisfy this binding property right so that means it should be hard to find two messages in the message space that leads to the same commitments and this is true in for at under some standard lce assumption called modul assumption uh intuitively it means that given some public random Matrix you should be hard to find a small nor Vector X such that ax equals zero and to see why this leads to The Binding property is that supposed for contradiction you have two small messages W1 W2 that gives you the same commitment C then if you subtract them together W1 minus W2 is another small

Norm message that is a solution to modu C right so then you can break the modu Assumption so that gives us the binding property of this tic commitments and beyond that you also satisfy really nice mly homomorphic property for small no messages uh that means given the addition like the addition of two commitments can also be understood as the commitments to the addition of the the corresponding openings such as so long as these openings are small no messages this follows directly from the nin homeomorphic property of matrix multiplication okay so that's some background about art commitments um and we will use these commitments uh in our folding operations and now the question

is how can we fold this kind of commitment opening relation so I would can I can can I ask a quick question mhm so um as far as I understood uh the commitments are for integer vectors right so they're commitment is not integer vectors can I go back wait yeah yeah yeah yeah so the the message is some integer or like some ring elements that has integer coefficients that has small norms and this Matrix a is over RQ you modular some prime modulus Q here and so so they're actually also over AR and Q is larger than this Norm bound

yeah C has no A and C both have no nor Bond we only have nor bond for w which is some ring elements polinomial elements with IND coefficients so this integers should be very very small and uh every a and every C are over RQ and Q is some modulus that has no um no Norm constraints it can be over RQ elements but it must be larger than your Norm bound yes yes can be larger can possibly larger yeah definitely be larger Q is larger than this nonbound yes exactly okay U Does this answer your question yes okay thank

you cool so now uh yeah so the the commitment opening relation we want to prove is the following so given a tople a commitment C and an opening w we want to it is in this relation if Cals a * W modular q and also the norm of this W Vector is small and here I will use this infinite Norm which means is the maximal of the coefficients of every elements here and it should be smaller than this uh parameter capital B here which is also smaller than this modulus q and some B is some parameter bond that we can choose so now given two committ openings in this relation

um the naive way to merge them into a single statement is the just to use random combination right which which is exactly the H of idea of all the previous pre content folding schemes so now what we do is just we use this random scaler in RQ to merge these two openings into one and hopefully that it can will still be in the relation however the key Point here is that in the last World this can become problematic and this folded opening may not be in the relation anymore the main reason is that after this folding the norm of this message can be much larger uh and this can hold even if this R this random scaler is small for

example even if you just do an addition the the the norm of the this wfd can now becomes 2B because W1 W2 can be as large as B here and then because it's larger than b is no longer this r b relation and you may wonder why can't we just uh adjust this parameter B here after each folding step so after each folding step I will set a larger B for this relation but this is not desirable in the folding scenario because that means after several folding steps this non Bond will blow up really quickly and at some point we exceed some thresholds and after exceeding this threshold this commitment will no longer be binding and secure so

that's not good enough and therefore I'm sorry uh I also this is also a thing that I don't not exactly understand uh if for example like I I know that in your paper you actually use quite small q in practice but uh imagine your Q is I don't know uh few hundred bits and this R is 128 bits or something like this then uh if you're doing linear uh folding not uh not three line but uh along a chain of foldings then you can fold in quite a lot of uh

moderately like vectors with some moderate bound because the the the things that are folded in are always 128 bits plus Norm of the non- relaxed uh non- relaxed instance right that is not uh that's not that simple because first B here usually is much much smaller than uh than Q in order to obtain the security level like modu C assumption requires this spe to be really really small usually should be as like much smaller than Q so my question is can it be larger than 128 bits significantly larger than 128 bits which is required for you mean you mean b or you mean uh the norm bound the the

norm bound at which your commitments are yeah the norm bounds the norm bound usually is can can be much much smaller than q and uh say for example if you choose R to be some 128 bit scaler then it's very easy for you to to fold and then the bond will be as large as 128 bit scaler right and uh and usually it's very in insecure like basically in that cases like for example you use 2 250 six bit uh modular CU you sometimes us really need some B to be as small as to do the 32 or to do 64 and uh that means after like very few number of falling step you can blow up

and exceed the threshold and this modulis assumption will longer help you to obtain The Binding property and actually there are some other also some other solty so usually um I I believe that if you like you relax this uh restriction it would be very hard for you to obtain a secure scheme in the folding scenario so I think that you really need to the best thing you can do is you really need to make b as small as possible and uh oh not as small you really need to be to be fixed and then this this enables you to do folding for infinite number of times rather than just very few number of times yeah which is very important okay yeah and but thanks

thanks for the question it's a really nice question so uh so now uh to okay to to uh to address imentation uh and obtain a folded witness that's still in this relation our first idea is to um massage this input opening a little bit okay so how to do that uh and the idea is to uh in order to merge two statements into one statement our idea is to do it in two sequential steps well the first step we split a vector of Norm B into multiple Vector that have even smaller Norms like this small B that's even smaller than b here and the hope is that after this

decomposition uh then we can do the folding and as long as we are using very small scaler and the after the folding the the fold statements now we have some opening that's still smaller than this capital B so we can still obtain the same statement in the same relation so that's a high level idea but however to um like to argue it more formally and clearly uh let me digress a little bit to introduce this notion of reduction of knowledge which is introduced by Kap Pani and Bri panel in 2023 so the idea is the following uh the initial supposed the initial goal is to check some statements in some complicated relation R1 and to do this we'll run some intermediate protocol Pi that after

running Pi is suffice to check some other statements in is in some simpler relation R2 and this is why so-called reduction of Knowledge from R1 to R2 more precisely say we have some public commitment C1 and uh the approver also additionally has some witness W1 for C1 in the relation R1 and then we run this protocol and after this protocol if verifile accepts we outp put some update commitments and if prover is honest and knows the witness W1 they should also be able to obtain a corresponding witness W2 such that C2 W2 is in the relation R2 and this is what the requirement called

completeness requirements and the interesting property here is that it also needs to satisfy this knowledge sness meaning that uh suppos for a possibly malicious Prov if she can obtain a witness W2 for the update commitment C2 then that means he also knows the corresponding witness W1 for the input commitment C1 that's in the relation R1 okay so that's why it's called reduction of knowledge and there are many special cases for this notion including arguments of knowledge and folding schemes for example folding schemes just can can be understood as that the R1 is just the product of two relation R here and R2 is the single relation R and it goes to reduce the tracking of two

statements in R into one statements in R and the nice property here is that this notion allows very easy composition for example suppose you have protocol that reduce R1 to R2 and the redu and the protocol that redu R2 to R3 then if you compose them together okay then you can obtain a reduction of knowledge protocol from R1 to R3 and which is seems very is very natural uh but we that this paper has formally proved that this is the case and this is very useful in our setting and now let me uh rephrase our highight idea in the in the language of reduction knowledge so now remember that our end goal is to reduce the checking

of two statements in this uh relation into one statement in this relation and we achieve this by uh by constructing two reduction of knowledge protocol and compose them together to obtain what we want okay so the first protocol is this So-Cal decomposed protocol that reduce the statements uh checking of the two statements in r b to the checking of multiple more statements in R small B and then after that I'll construct another folding protocol which is the another reduction knowledge that reduce the checking of these many statements into the check of these single statements in r capital B and the composition is exactly what we want so now it reduced to question how can we

instantiate this decomposed protocol and folding protocol efficiently so let's start with this decomposition um and for Simplicity let's just see how to split a single Vector into two Vector with smaller Norms but idea can easily generalize so recall that uh in this opening of I capital B we have some input vectors openings which is a vector of ring elements where each ring elements is just a polinomial with integer coefficient that's in the range between minus capital B and B okay and the way to split it into two Vector is the following well for each single integ coefficient of single ring elements will represent this integ coefficients using

this Bas decomposition representations for example if B equals 2 this is basically just a binary representation or B composition of integer and we'll do this decomposition for every integer coefficient of the vector to illustrate let's consider very tall example well say this Vector is only of length one and there's one single polinomial 7x plus eight which have relatively large uh coefficients that's less than nine I want to split into two polinomial that have even smaller coefficients that's smaller than small base three and then we can easily do this uh decomposition and split into two small pooms 1 x + 2 and 2x + 2 and the nice thing about

about this splitting is that if you multiply a matrix a on both sides this equality will still hold that means the other commitment the corresponding other commitments also satisfy this n combination relation uh so this leads to a very natural way to do DEC composed protocol with Hest Pro if she has a correct witness F then he can do this splitting algorithm and including the two even smaller Norm Vector F1 F2 and then your compu the corresponding it commitments and uh the verifile uh before before outputting the updated commitment C1 C2 we do a one last sanity check checking that C1 and C2 is consistent with commitment C here okay if this is the

case he output C1 and C2 so it's easy to see that this this protocol has the completeness because honest prover will output correct opening F1 F2 with C1 and C2 and it's also easy to see that also have noise sness because as long as some malicious approver outputting some F1 F2 that is with very small norm and correct opening of C1 C2 then we can extract something like fub1 + B * FS2 which is the correct opening of the commitment C1 + B * C2 right and also because verif far already checked that this equal C we obtain some valid open opening for the input compliment C that has a norm uh that's smaller than capital B so this is

indeed a reduction of knowledge um so that's that's this uh and then U that's about decomposition and uh after that the folding part um and the other part is the folding scheme which is I think is more more interesting part um to do this to do this let's uh consider a simple example well we just to want to fold two vectors into one okay and uh now we are in a slightly better situation because these input opening are having Norm that's much smaller than before they have a Norm that's smaller than a small B here and um now the the idea to rescue this

naive idea is to set R to be some very very small random scaler and hopefully because initially they are very very small and also R is very small then after folding this commitment opening can still be as small as capital B even though it's larger than small B but still smaller than capital B so the good thing here is that now completeness holds because we can always guarantee after folding is still in this relation R Ty B however there are some issue in terms of knowledge extraction the main issue is that um to see what's the issue let me illustrate by see how we typically extract a witness Okay so let's even consider simpler problem let's for Simplicity assume that

malicious prover is a perfect malicious prover that always give you some correct output witness for the folding commitments and in that case we can fit it into two different random scaler and and he output two different valid openings for these commitments okay namely W FDX and wfd Y for the folding commitment cfd X and cfd Y and um our idea is falling so given this we can build a system of linear equations where we set this W1 and W2 to be some variables using coefficient RX R1 r y and the value WF DX and wfd Y and then we can solve these linear equations

to obtain some witness W1 and W2 that satisfy this linear equations and then by the linear homomorphic property of matrix multiplication we can actually easily argue that C1 equal a W1 C2 equal a W2 and that is with with no problem but the key issue here is that the solution we find may not have small Norms it's totally possible that this Norm of this extracted witness can be very very large it's much larger than this small base B the reason is that in this first term uh even the first term the WD FDX wfd y can be as large as capital B so their difference might be

as large as 2B and even worse the right hand side this term is some inverse of some differences and we have no control of the norm of the inverse of this uh of these elements so in general um to recap we cannot this naive solution doesn't work the main reason is that very hard for us to extract some witness that's valid but also have very very small Norm namely even smaller than this capital B and this seems inherently hard right without doing anything else because what we start with is already some witness that is can be as large have nor as large as capital B so now the key key question is how can we uh address this limitation and idea

is to add some extra procedures here for example to let approver to additionally prove okay I I indeed know some witness F1 FS2 that is uh very very small and moreover this small Vector F1 F2 is indeed the commitment to this C1 and C2 that satisfy this Matrix relation and one naive way to do this is just to directly ask the prover to send this witness F1 F2 in the clear to the verifile as a folding proof okay and the verifile we just checked F1 F2 are indeed with more norms and there are indeed uh the matrix multiplication with respect to C1 and C2 and this works well for obtaining structure but it's not

very well in terms of efficiency because now the for verifile has linear time complexity because the F1 F2 has linear lens right the lens is is is linear to the number of uh witness elements and as we mentioned before we really need some verifile that has sub linear complexity in order to obtain pie M snark and moreover this complexive verifile is very very related to the recurs recursive verifile CC sizes so now the question is that this naive protocol doesn't work how can we efficient efficiently instantiate this R check or nor constraint protocol so to do that uh our ideaas to use the stum check to recap our main

problems the following say we have some commitment short commitment that commit to some Oracle vectors F and uh the Prov wants to know that wants to show that he knows this vector and for every entry of this Vector is this very very small norm and now for Simplicity let's just assume uh that every entry is just integer rather than a polinomial with integer coefficients but idea is similar okay and now the problem is to check that for every entry of this Vector which is an integer every entry is in the range between minus B and B here okay and our first step is to transform this Norm constraint check to some algebre check

uh meaning that we want to prove that for each entry this HFI equals zero and HFI is defined as following it's defined as a product of many terms related to fi okay uh and you can see if this entry fi is indeed in this range between minus B and B then exactly one term here will be zero so the product will be zero and if it is not in this range then none of the term will be zero so the product will also not be zero so that means these two uh problem is equivalent and and this transformation has no problem and now everything every asthmatic is over the integer but we can for efficiency you can map them to the to

some prime prime Fields with respect some prime modulus Q here uh and uh this argument we still host as long as the prim modulus Q is larger larg enough namely larger than 2B is already enough and after that we can do some syntactical change to change this Vector uh algebra check to some polinomial check so we can embed this elements HFI to the bulling hyper cube of some multivari polinomial by multivari polinomial I mean it's a polinomial with many formal variables like X1 * X2 is the two variable pooms and now after embedding this value in B hyper Cube the problem becomes to check that for some Oracle polinomial which is committed in

some commitments this Oracle polinomial satisfy the evaluation of the Boolean Hy Cube R are zero everywhere and this is so-call polinomial zero check problem and with uh with some tricks used by some previous work like hyper plun and Spartan we can transform them into a very famous protoc U problem called polinomial sum check problem and the goal is to prove that for this Oracle polinomial the sum of the evaluation on some buing on this bulling hyper Cube equal some clam value s public clam value s so to recap what we have done is that we transform the original n constraint check problem into a new problem that is a famously known uh

which is the the Su check problem and the for the nice thing here is that we do have very famous and and classical protocol called Sam protocol dating back to L Forno and kov and Nissan in 1992 and subse subsequently there are many Works to improve the concrete efficiency of it so the pro time is actually very very efficient linear to n and verifi complexity is logarithmic to n where n is the vector lens and also proportional to B but B is something we can set because the small base B is something we can set ourselves usually we can just set it to be less than four or less than two so this is actually very very efficient and in some sense this some check protocol is some

reduction uh from this from this Su check clam to this evaluation clam basically finally you still need to check some uh evaluation statements with respect to some Martin polinomial as some random point that if this holds true then with with high probability with overwhelming probability the Su check claim will also hold true so the final question is who will be responsible for checking this right one option is to directly ask this ran check verifile or folding verifile to check this but unfortunately that's too expensive because a single Martin evaluation already takes you o time complexity so it's not affordable for folding verifile if you want to

achieve very efficient folding VAR complexity but fortunately the key observation here is that this evaluation statement itself is actually pretty easy to fold if you understand this evaluation statements as a a relation what this evaluation points are and this uh claim evaluation value T to be the commitments or the instance of this relation and the the witness to be this um polinomial it's actually very easy to fold for example consider simple case where you have two evasion statements with the same point evaluation points then you only need to fold and do a randomly combination on the evaluation value T here and delay the evaluation check here the very end and suppose you

have two evalion statements that have different evalion points which is slightly more complicated but you can trust me that you can run another sum check to reduce it to a single evaluation check uh in uh so you can merge two evalation check to one evalion check and no matter what is the case you can always preserve this complexity folding complexity to be logarithmic to M so this leads to our final solution where our idea is to expand this commit opening relation a little bit to also include this evaluation statement inside which is also easy to fold and in each step you just fold this evaluation statement and commit opening relation but delay the raction check to the very end and in this cases the folding verifile can still Preserve this very

comp uh very very efficient complexity which is logarithmic to n okay so that's the H idea in order to make it work however and work it very nicely there are many sties to solve the first thing is that previously I I'm cheating a little bit and saying that every element is just an integer but for efficiency reason and for some security reason we do have to walk over some ring r q here and that means uh we can no longer run Su check over a prime field we have to run a s check over a vector space of prime field or equivalent some ring but uh uh fortunately as observed by by some previous work we can run some

check over Rings easily with some slight modification without loss of many efficiency however uh if you run naively for this protocol in order to make it work you really have to use a very very large P Prim modulus Q which can be as large as 200 50 60 bit Prime modulus the main reason is that in the sum check of over Rings the verifile has to example some challenge in each run which is INS inside some subset of RQ and the subset has to be really really large and also need satisfy certain invertible property which works for which holds for free in Prime field but not over ring so therefore in order to satisfy this

requirement the easiest thing we can do is to set this que to be really really large if you say Q to be really really large you can easily achieve this property however in practice we want some very small Prime modulus uh Q like 64 bits Prime modulus or 32bit Prim modulus q and in that case uh the reason we want this is that we can represent every zq elements in a single word in CPU or GPU and avoid big number aritic uh arithmetics which is quite expensive but fortunately with some optimization we can do achieve this and use some Prim modulus Q uh that it can be as small as 32 bits or 64 bit primes but I want to note here that you really cannot use

very very small q like like binary like two or three or something because as I said before in order to make the modules assumption hold you still have to choose some Q to be relatively large and the nor Bond will be even smaller than this Q significantly smaller so that's it uh however as I mentioned before this is just the toy example um but in order to obtain a pce me snark we really need to uh to fold some relation that's more complicated so beyond proving this commit opening relation we also have to prove this uh uh like other statements which is local computation chunks is correct and folding verifi is correctly verified and therefore that means in this relation we

also represent and express this kind of computation statements beyond the commitment opening relation so that requires us to augment this relation to also support some MP complete language to represent this computation and our solution is to support this so-called customized constraint system relation introduced by shras uh Justin Taylor and real wabby in 2023 so in general this is just a generalization of the traditional R1 CS constraint system that allows you to use high degree gaze and the nice thing about is it allows you to express arbitary MP computation efficiently in some relations or in some circuits and after that we'll also obtain the

folding scheme for that uh which is not much harder than the commitment opening relation folding uh and the key highlight here is that we are we can reuse this decomposition plus folding framework here and I think that's a really useful frame mode okay so finally let me uh focus on uh give you a little bit information how efficient it can be I think this is one of the most important slides I want to I want to say about in this talk is that first you can see that in this last folding scheme We have replaced those pison commitments with these Adda commitments that means we have to replace remove those uh group exponentiations with some ring operations over RQ and as I mentioned before with a with a correct

implementation and optimizations this at commitments can actually be really really fast even in CPU can approach some performance of some hash functions and even better we see that there are tons of optimizations and very very fancy implementations of FH in in this FH industry and the good thing is that they are exactly doing the same operations uh here right is some like NT or very fast operation over some RQ so that means we can reuse all of this Hardware optimizations or implementation from FG and make them very very efficient for ltis v as well so I think this is really promising and uh uh in some sense in the future I think it can

be blazingly fast and the second in terms of this recursive folding verifi circuit our circuit is dominated by the s s check verifile which has involves logarithmic number of hashes and ring operations uh but the key highlight here is that compared to those pre- condom schemes we don't have uh we don't need any cycle of rings ory which is in in their case they need cycle curse and all operations in this recursive circuit is over the same uh ring RQ so every operation can be natively represented in charismatic circuit instead of instead of being uh simulated in a different field which is the case in for those preon schemes and that is also one of

the main reason that we can actually obtain very competitive recursive circuit sizes and finally let me uh have one word about this P me snark proof sizes so when you when you do this P me snark compilation naively finally you obtain a final folding uh instance and witness pairs and the folding instance can actually be very really small but the issue is about this folding weakness say you have some aristic surus over two to 30 gaze you want to proof which is really really large and in practice usually you want you don't want to split into too many chunks right because every chunks uh still incur some extra overheads because you have to generate

this folding verified circuits so it's more reasonable to consider to split into a reasonably large number of chunks for example 10,000s or uh like less definitely definitely less than 100,000 and in that case each trunk statements even though much smaller than before can still have a large weakness can have like T of megabytes uh weakness size which is still pretty large but the the nice thing here about about here is that you can easily compress one thing further and make the proof much smaller the idea is to finally use a single postc secure model lis snark to further compress this folding uh instance with

par checking statements and delegate this checking to the prover and let Prov to generate stock proof for this and the nice thing about this is that with the recent Advance this stock proof can be as small as less than 100 kilobytes and moreover it should be very very easy to verify uh verify this proof and in general after combining this piece me Sark with this final uh compression method we can obtain a very very efficient snar proof that has very efficient Pro very small proof sizes and very fast verifile and it's postc secure so that's the um like the Hal idea of how efficient it could be and that's basically it and in summary we introduced the first last space folding

scheme based on the a commitments which gives you a memory efficient and Poston secure snark that has fast provs and along way also introduce many generic techniques for folding last space commitments uh that means it not only works for arti it works for almost all kinds of Life space commitments um and one last thing is here that I want to mention a concurrent work I think also someone has uh has uh has U mentioned this so recently there's a new work um that uh that that is uh authored by Benedict pratus Wilson and William they have build a new folding scheme that purely from hashing which is really

great there's no even no need for ltis crypto even though I mentioned this lat crypto is almost symmetric Lattis crypto because ad has function is also very fast but if without it it can be even faster which is nice and they also mention some general optimization techniques for this pie mear compilation that actually can also works for Lattis V and further improve the the efficiency of ltis v and compared to our work the trade of their work is that first they have a larger recursive verifi circuits because they need to perform many hash operations significantly more hash operation in the recursive circuits so that's why they have much larger recursive verifi circuits and on the other hand they only support bonded like

constant number of folding steps and compared to our that we can support unbounding number of folding steps and in particular they also mentioned there exist an concrete attack in their cases if you fold for more than some a constant number of folding steps that's the trade of these two Sig GES and finally let me also mention some we believe that can also be able to folding this table lookup relation um which is a relation that's proven some witness in inside some pre tables and recently there's an elegant word colasso that's VI a lookup arguments from some Che and we believe that can be easily

integrated into our setting because is very like srack friendly very smart srack friendly and I think the second is that I think highlight here I we really hope that can be some very very efficient and very very uh optimized industry level implementation for L fult um and I I'm looking really excited to see how it performs and hopefully that can can can possibly be a g game changer uh for proving really really large statements by combining all kinds also of techniques and also combining those really elegant stock proof uh together uh yeah that's that's basically it and now I'm happy to answer more questions I

think in the chat there might be some question I haven't look at yet now maybe I can answer them yeah thank you so much thanks uh yeah there was a question that I missed uh when you were talking about the uh decomposition uh so to be able to uh change from uh relations on capital B to uh small B uh you were talking about uh scalar between uh yeah there was a question whether the de composition had to be unique or not um because uh de composition has to be unique or not oh I see so de composition because of

negative numbers it might be not unique as at least as as you stated that Al so you are saying basically integer right integer whether yeah I mean there is BAS B composition is not unique for numbers bounded from minus uh B to the power K to B to the power K that multiple the compition oh that that's is actually unique because every it's not zero to the B it's minus small B to Min to small B right for example if you have seven it will be correspond to 111 correct right seven is 111 yes but it will and if it's minus 7 then is minus one minus one minus one no no please please hear me

out uh B minus one is both B minus one and minus one + B okay it's not unique the my point is that it is not unique uh Bas B de composition of B minus one can be both one I'll write it in chat I'll write it in chat to be precise no not B minus one over P so that's a basee is 1 1 b b squ B3 so on so forth right suppose B is two okay B for example if suppose B is two then every for every integer that's less than say uh than less than eight right and let's

say small B to be two right and seven has his unique representation to be uh 1 Time 1 * 1 + 1 * 2 + 1 * 4 correct no why not incorrect this is another representation of seven please take a look oh I see I see I see your points I mean the decomposition algorithm itself is unique you understand so so yeah I'm saying that the composition is not unique uh oh I see oh I see you oh I think you are maybe it's not a problem for you I point I see points you are not talking about this algorithm is deterministic you are saying that they have different

decompositions I see so let me let me uh that's a good question and it's not a problem in our case indeed so uh let me see if I can reshare my [Music] slides okay did I stop sharing okay let me share okay here yeah yeah so yeah that's actually pretty good question so I I I kind of miss On Studio meaning so I saw you mean that this algorithm is non deterministic this algorithm is deterministic but you are

right the for a single value they might have different decompositions right but what we need is just we only need some valid opening by what valid opening it means that is that Matrix rep matrix multiplication relation and have some small Norms that's enough and The Binding the uniqueness is not information theoretic you just by some computational computational assum assumption by modu C so as you see here um like first completeness host I think you what you concerned about is about the nor soundness right and here this nor sound is when you extract you can see here when you extract this F1 plus bf2 even though it's not the only uh

decomposition for C1 plus bc2 definitely is not because information theoretically can be it cannot be possible to be unique but it still satisfies Matrix relation right satisfies the matrix multiplication relation and it's also having small norm and this binding property now is computational not information theoretic because we are relying on some lce assumption there to to argue this uh this binding property and uh still you can see here the relation statement itself is just saying that it's in relation as long as C is a matrix multiplication of a f star and F start is having small Norm that's the only requirement we need right so it's still a correct valid witness for the

input relation yeah so that's it but it's a really good question uh and sorry I Mis mised initially but now I think you you now are clear about this okay yeah thank you so much yeah yeah I'm also uh so uh do I understand correctly that if we are cons so I I actually have a lot of questions to be honest may maybe I could just ask them after if it's maybe somebody else wants to ask something because I could I think easily consume all remaining time and my questions so uh maybe anybody else if you don't mind I would also like to ask a couple of questions uh so here thanks a lot for

your talk uh here you've been talking about using as commitments but um I'm aware that there are other commitments uh I think there's a paper for 2018 uh on um ltis Bas knowledge proofs that that been using combinations of Ash and U bdop commitments I yeah so I was wondering if you also looked at Old commitments or because I commitments are are quite old uh yes yes that's a good question a very good question so the reason we choose arai first is because of is efficiency I think it's actually very very efficient and compared to this bdp ments one of the key advantage of Ali is that is very

very compact it's like no matter how large the witness it is the commitment itself is always a constant but I think the BD commitment I think has some Minar complexity like at least is not independent with M message Vector lens and it can be long relatively long compared to the message size so that's one of the reason we choose arai and uh yeah and in arai the tradeoff is that witness should have some small normal constraints but it turns out it's actually pretty it's not that hard to deal with in the following scenario but that's the main reason we choose out High yeah yeah know uh in this paper they they talk about the same problem and that's why I think they combined the

two commitment schemes uh to try to to be able to work on larger modulo thanks to the BD AP scheme but still maintain smaller size uh I'm not very I see I may be wrong but that's interesting yeah and I want to add one more thing here you are right the the advantage of BD is that support larger Pro larger message size uh space but a really nice thing about here is that in a folding scenario we actually don't need such a property uh I didn't mention this but uh uh basically in this final folding uh oper uh scheme for this CCS

relation the the witness in CCS relation is actually can have arbitrary large Norms it's arbitrary ring elements but the nice thing here is that we can still commit the RTI using the small Norm messages which is the some composition decomposition of this large witness and the the only thing we will need to further prove is that there exist some um like um um matrix multiplication relation resecting some Gadget Matrix between the CC s relation and and uh and this uh um this small messages and as long as small messages fixed then this CCS relation is also fixed and this uh The Binding of this mono messages is is

achieved using this binding property of modul C or at commitments so in our case we actually don't need have that stronger property for commitment schemes yeah yeah thanks L yeah so I think I have I have formulated the question that I want to ask so um considering K commitments uh so uh when we are looking on uh pedon based commitments one of the very desirable properties of the folding schemes uh is that uh because you are not actually doing snarks you can use the fact that uh small values are uh easier to commit to so like it's it's faster to commit to

small values L And as far as I understand commitments do not have this property right uh commitments is kind of hard to say because like you already have the constraints that the message itself should be small right no no no I mean uh I mean to to be precise uh I have some trouble with uh so so basically when you have a large statement you so I mean if you have large coefficients you represent there a lot of small like Bas B small uh individual commitments and so you're paying for each of them the full commitment cost

right so if for example your base B should be like really small for for some check to be efficient uh like it should be base three or base five something like quite small actually actually you have to remember there are two B here right yes B small I'm talking about B small for for yeah the small B has nothing to do with other commitments right no it has it has it has can you can you open the slide uh can you open the slide uh about about like your the previous one I think I I know what you mean here is that I mean that your fing procedure requires you to communicate this pieces it is pieces and

committing to each piece might be hard like I mean there are a lot of pieces that you need to communicate I see I see I see very I see your point so like you are saying that in this deom decomposed protocol you exactly talking about this decompos protocol the Prov needs to compute this C1 and C2 here and in this case F1 F2 are actually small Norm right and and and you're saying that you have to commit many of this and uh and P cases if if F1 F2 is very really small then actually can be much more efficient than com to some large scalers I think and you are questioning why can we have a similar optimizations for here uh in AR cases right U and

that's very good question I haven't thought about this deeply um so I guess your question is like suppose we have a really really like binary Vector for example binary Vector of f can we yeah and can we compute ATA even more efficiently right I think that might be that might be possible because that's basically uh just some like if binary then it's just some combination a sum of some Columns of of this a matrixes right and this is much this even this can be much faster than just Computing some RQ multiplications so you might we might be able to have some similar optimizations in the a cases yeah I mean I am just

trying to understand so what is compared to what so for example if if we are not doing this optimization so my question is was like do you know if this optimization exists because if it would exist uh then like if it doesn't exist then we are not uh comparing the cost of one commitment uh on the side of like Pon world to the uh to to one commitment in the uh a world but uh we are comparing like uh logarithmic amount of this like mag log of magnitude of this commitments to a single commitment in a p I see I see your point very very very good question so you are

saying in the pon cases because we don't have this splitting um process you only need to compute a single commitment for a long vector and in our cases we actually committing to the Beyond this commitments we also need in the decomposition scenario we also need to commit something else right which add some extra overheads and if you don't have this op ization you are saying that we're actually comparing to committing uh logarithmic or like at least the like k k commitments versus committing one commitments right um that's a very good question I think we do we should be able to have some optimizations for very very small scalers I would also expect it should exist I would also expect you you

are doing something linear after all uh linear of of what I I mean the the the operations that you are doing are already multiplications which use bit the comp you could like do the bit composition of the right side oh actually actually actually let me let me rephrase a little bit actually uh I'm thinking actually don't need to do uh many commitments actually to be honest uh the reason is that I think you can directly decompose using C you don't need to recompute these commitments this is just for illustration purpose and there has some simple simpler uh I think so right no no you can't you you need to decompose your original Vector but but

multiplying by small numbers is faster than using constant uh like I mean it it it still should be faster than like this naive expectation yes yes yeah I've just looked into similar uh like when I've read your paper I actually uh walked back to Pon world uh and uh like uh uh did some like uh research on like uh using this to improve range checks in Pon world and actually it it it looks even better there I see I see you're saying that you use this trick for a r check trick for pison uh and obtain a similar scheme for pis I guess right you

say so actually actually I still wonder if you could like for L's fault if you could do multiple multiple foldings without doing this split and merge uh thing um like if you could uh if you could do multiple fings without your Norm bound overflowing uh if if you could do this it would be uh like great but uh there are some subes there but for in Pon world it is doable like but pis in pison there's no basically there's no normal constraints on unless

you want to um have some optimizations in terms of scaler there is there is Norm constraint in the sense that uh uh you you want your limbs to not overflow uh you still want your limbs to not overflow uh so you canot do it infinitely I see but but but uh uh because my my purpose was actually doing nonnative arithmetics in in but uh probably it is also applicable to this mhm mhm I see and actually that's a very good interesting so I want to add one more thing here is that uh um first um even you do pison you have this tricks you

still again it's still discrete log assumption is definitely not postom secure right if you consider postom security definitely you should do attack course of course yeah and right right right and uh yes I think you mention a really good question whether we can remove this splitting uh procedure um but I think if you want to do infinite number folding in the latest word this seems quite hard but maybe there's a there's a way to do that maybe two to the power four fing is enough maybe you don't need maybe you don't need infinite maybe two to the power four is yeah yeah um yeah and also actually quite quite interesting thing that uh Starks

are also I mean f based or uh like eraser code based stuff is also evolving to the um uh to to the question how to uh how to compress uh low low magnitude low modulus uh values into um into higher uh in in more efficiently like uh for example there is a recent work on uh which uses uh extension of F2 uh and as a base layer it uses uh breakdown and I think that uh breakdown

is directly analogous to the recent work of uh is directly analogous to the recent work on uh folding without homomorphism by B and others so breakdown is like square root of N Style Construction uh analogous to the folding uh construction that uh buun satal recently suggested so this F2 extension technique can be also used in it so like like like actually a a lot of folding schemes are like uh converging to the idea that you should use a small base

decomposition uh and now somehow can somehow uh uh ensure that your Pro System uh handles it like fast enough like uh that your that your commitment scheme allows you to commit faster to the small vales so what I see so what's the general question here you want you compare no it's not okay I have no more questions I see I see I see it's a comment I see that agree yeah so I guess uh I I think one interesting question here is that uh where we can support this kind of extension of binary fields in the latest word which I think is pretty pretty hard because usually uh because if you

supposer you are using this modules assumption you really need this Prime modul Q to be usually relatively large like uh usually at least 32 bits like um that means that you might be able to use meren prime Fields but uh I don't see it how it can be easily used this binary field it should it seems quite hard uh in the last for setting but as think even using mercen mercen prime Fields can be can be quite fast in the last word as well yeah yeah yeah thank you thank you for question and comments yeah that's quite helpful um oh I have I have one addition one addition by the way if you somehow

if you somehow ensure that your sorot is has small uh small values then there is actually quite an easy construction which allows you to uh compute your intermediary intermediate uh commit okay maybe not no no never mind never mind uh but but there are definitely optimizations for small values I see yeah yeah I I agree I believe that for example I think in lasto they also mention a lot of optimization with respect to small scalers yeah okay uh any other questions um no I don't see any other questions uh I had one but it's very general but I'm not sure if we have time

uh so I will just send it to you offline if you don't mind so thanks a lot SP for coming today and for this presentation was very interesting and uh we've had you free time so I'm sure we're going to have you another time soon than again and thanks a lot for joining us yeah thank you so much for the invite and yeah it's uh is a happy experience yeah thank you