ZK Paris: Panel on Folding Schemes with Nico Mohnblat, Justin Drake, Benedikt Bünz.

Transcript

okay uh up next we have our first panel of the day on folding schemes uh with moderator and panelist Nico monblatt from geometry and panelists Justin Drake from the ethereum foundation and Benedict buns from espresso systems [Music] hi thank you very much thanks for the

intro Chloe so I am Nicholas momblad I'm a cryptographer at geometry and I have here today Justin Drake and Benedict Bunce joining me on the panel so we're going to be talking about the folding schemes I have a pretty sort of ambitious uh schedule for us up ahead so covering the basics what folding schemes are talking about performance talking about security I would also try to talk about like what's beyond and what what are the alternatives and hopefully have a bit of an open q a uh before we dive into all this can I ask you both to introduce yourselves to the audience and actually to myself because I don't think we've met in person Benedict I'm Justin Drake from dfm Foundation um I do a lot of research on upgrading

ethereum and making it more secure the layer one um and I guess we might use folding in the context of vdfs at layer one as well as for snarkifying evm basically making the evm and then try and roll up yeah my name is benign bins I'm the chief scientist and co-founder of espresso systems we work on decentralized shared sequencing but I also have uh I'm a researcher working on zero knowledge proofs in in recent Years A lot of my focus has been on folding schemes so I think Justin you started touching upon this already um why are we interested in folding schemes sort of what are the the

motivating problems that we've seen in the world that led us to think about these problems right I mean the the big thing the big primitive that we're interested in is snarks and I think uh folding schemes bring us to a point of optimality uh in many ways uh on the one hand um there they tend to be extremely simple so like called Moga of complexity uh tends to be very low um they seem to reach uh you know Peak Performance just be optimal from a constant standpoint even if you're assuming uh elliptic curves um and um yeah I mean this has all sorts of consequences for example the fact that

we've reached a point of optimality it might mean that we can finally standardize right because every six months we come up with a new Improvement but since we've reached the end of the road then now maybe we can start building uh folding A6 and whatnot would you like to add anything or yeah I know I mean I think that uh folding schemes they give us this primitive called IVC called incrementally verifiable computation which is a computation that sort of runs forever so think of a blockchain it's a computation that runs forever but at every step I can actually give you a proof that the computation was done correctly up to this point and

like sometimes this is referred to as recursive snarks this is actually not quite correct recursive snarks give you IVC but folding schemes are something actually much simpler and weaker that still give you IVC and IVC itself has many applications succinct blockchains vdfs but even like you can build a snark right because you can just like formulate your computation as a machine like as a turing machine right this does computation steps so it just gives you a snark itself um and uh yeah I think what Justin said about like the constants just being sometimes one is is very very intriguing and I I guess

um one of the things that you can do is like because the contents are so good and the cost of direct the overhead of recursion is so low you can have real time proving so the the end game that I'm that I'm thinking is you have a CPU and then you have some sort of co-processor right next to it and within one millisecond it gives you a proof of whatever you've proved on the CPU and another really interesting aspect of IBC is this um distributed proving with untrusted provers um so you could have proofers all around the world for example on the blockchain and they're all working together and they don't have to trust each other okay um I'll actually come back to that a bit

later maybe like towards the end of the discussion for the sort of Beyond folding we've said folding a good dozen time if not more uh I think it's time for us to sort of Define what we mean and sort of explain what it is um yeah Benedict maybe do you want to take it yeah sure um I I guess we'll we'll get into the naming discussion but the the idea of uh a folding scheme is that essentially it's about batching um you know that's yet another name that they've never used but maybe that should have been the name it's instead of normally when I have a proof um I verify it but what if instead of verifying the entire proof I could take

two proofs and just badge the verification together and what I have to do and normally in these these Ivy C schemes I prove that I've checked a proof but now with folding schemes I just prove that I've correctly batched the proofs together and this gives me some new batched object some some accumulator is also what it's called and and then at the very end of the chain I just checked that the accumulator is correct and the important property of these following schemes is that if I check the final accumulator is correct then this implies that all of the previous things that I I folded into this one accumulator

we're valid we're valid proofs so I reduce basically the the the the the um uh checking many proofs into checking one proofs but the important thing is that I can do this kind of in this iterative manner and and I iteratively prove that each folding step was correctly each batching step was done correctly I mean I would go in even further in saying that um yeah it is true that we technically you know batching these proofs but the proofs are the most naive proof you could think of which is like the the raw witness like the instance itself so really I think of it as uh you know batching the instances themselves the witness

themselves and you're doing almost well no pre-processing on that there's no proving step really the proving step is delayed to the very end where you want to compress this folded instance to something that's maybe constant size yeah I think I've heard you talk about these schemes in the terms of like uh approving preprocessor likes yeah some work you do and eventually do the proving right um so batching accumulator lots of I guess words that come through this line of work do they all mean the same thing when we say accumulation schemes Blitz accumulation schemes or are there my new differences do we care about these

differences um yeah of course there's many differences I don't think that most of them are not that important um uh it's just historically like um we had these papers in 2020 about accumulation schemes well first of all there was Halo which sort of started this this work um this whole idea that you could delay some of the verification and then we had these works on accumulation scheme and then afterwards Nova came out um but there is one difference and this is relates to what you just said it's so oftentimes like folding really talks in in this language of relations um where I fold the witness of a relation and most of the time that is

enough most of the time I will just fold the relation and accumulation team schemes we do talk about oh I'm gonna badge the proof verification and there are schemes like in in protostar we had this really efficient lookup protocol and where the the usually this works all of this works and for schemes that are algebraic and low degree so where the verification is um you know some low degree verification for r1cs for for Nova this was RN or NCS which is just a quadratic check so degree 2 equation and then later works um have extended this to to sort of arbitrary degree D equation but then we also have things like lookup which isn't

inherently a low degree check but it turns out through one round of interaction we can turn this into a low degree check and then accumulate that and so that's something that's one example and and maybe there are more where you do actually you don't fold sort of like one witness but you actually fold a proof and and I do think we should like most of the time the proof is Trivial and and I agree with that but I think just just looking at sort of this language of relations does seem to be at least we have one good example where it is where it is limiting um but you know folding is definitely a better name than accumulation I mean yeah yeah sounds better okay glad to see we can convert our

folding actually to your point now I've been giving this mental model usually now for folding schemes where it's sort of this reduce and combine approach so you sort of have a strict instance your the problem you start with and you want to make it into something foldable right so in the case of Nova it was relaxed r1cs in the case of protostar hypernova we now see this thing where you do work through some of the steps of your protocol and only then do you start accumulating um no question there so just like going your point um I want to talk a bit about performance of these things so we said right uh were optimal down to constant and even the constants themselves are

optimal how did we get there that sounds crazy right no you don't seem surprised yeah it does seem too good to be true I mean what happened for me as a story is um I kind of discovered Nova you know almost at the very beginning a couple years ago and um you know they were very very useful for vdfs and really got us the performance that we wanted but no one was looking at them and the reason no one was looking at them is that they had well maybe that's an exaggeration but few people a few practitioners were looking at them it was you know they were using

Halo 2 graph 16 you know fry whatever and I think part of the reason is that they had they had all sorts of constraints like on paper um they were not really snarks right because you had to do this final compression step um and the verification time was not very good because the the paper described this compression scheme which reduced the size of the proofs but the verification time was still in there in in one step um it was only compatible with r1cs which was not very attractive and had various other kind of annoying things and I think the way that I saw it as this kind of this this rough diamond that needed polishing and over several

years I guess a couple years we've managed to to fully polish it and now I think we have something which is which is production grade there's also a case of like applications and use cases because I think Nova was advertised talking about vdfs and so IVC the average practitioner isn't building an IBC system right if I'm building just an application I just need one snark to verify um I think most practitioners will move towards irisc okay for every kind of application oh many applications okay yeah um I mean I think the primary application in blockchains is just the ZK VMS and once you have that primitive you can do so many things

um and I think like maybe a slightly different perspective on why it's sort of what has enabled this like from a mathematical perspective to be so damn efficient is is um that and we show that this actually works for like it works for any protocol it's literally all you need to do is take a random linear combination like that is that is all you need to do um is is uh you take a random linear combination of of your accumulator and and uh your new proof or relation or whatever right so that's literally this is why the constant is one uh you take one of them and then you somehow deal

with kind of what comes out of it but um it's like the Primitive what is just so beautiful is that the Primitive is so damn simple but it gives you something so powerful and the Primitive that we're relying upon is this additively homomorphic Vector commitment which is kind of the the simplest kind of thing which has like a little bit of additive structure and that gives us actually hope that we can patch maybe the last final weakness of folding schemes which is that they're not Quantum secure um and so we basically we just need a Quantum secure attitude Factor commitment and then we'll be able to

just reuse all the technology that we've that we've built I'll answer that it I don't know if it's the final hole in this polish Diamond there's also this thing that we have to use curve Cycles right which can be quite annoying to either find or work with or Reason about right um Alpha League there is a paper coming out soon okay that improves things um before we so I do want to talk about curve cycles and the bug that was recently uh shown in the Nova implementation before we get there I also want to talk about more specifics about the performance it seems like

right now the state of the Arts is kind of hypernova and protostart as far as I understand and it seems to be like two camps oh you don't agree with the or I just think protostar is better but it's uh no so there seems to be two camps the sort of the some check camp and the kind of randomly linear combination approached is there a superior approach you just said you think protostar is better yeah I mean you can just look at the constants um and so I think the the right like this whole idea in in folding schemes is to do as little as possible and

um the what you can do is you can formulate so the the some check you can view everything as a some check you know like if you any random linear combination is is essentially some form of a sub check the question is basically do you run the so-called sub check protocol which is this famous protocol from I think 1992 and which is like is extremely verify efficient right it allows you to do some some check over some where the verifier only works logarithmic and like it allows you to do a random linear combination where you know like sweeping a lot of things in

the rack but the verifier is logarithmic um but that is not what we need in in um in folding schemes we don't actually need that to verifier is efficient we only we can do that at the very very end we can push that to the decider so um in uh protostar we don't run the subject protocol there's still like some sum over a bunch of terms that's the random linear combination but you you just you don't have to do that you can kind of fold that in I guess um where are these things compatible well at the very end you get something you get some big proof and you might want to Outsource checking that proof or

deciding that proof is is what it's sometimes called and this is where we can use standard snark techniques and some check is a beautiful standard stock technique that has many applications and is perfectly suitable for um for these kind of settings and so that's I think where these things are compatible okay um I think that was a good time to move back to the point I just mentioned of curve cycles and the the recent bug um I think is either one of you able to give a brief overview of what happened or I mean the non-technical overview is that

um three enough didn't prove the scheme with the Cycles he only proved the the non-cycle scheme and and then he just said okay the cycle is an optimization I won't even bother proving it now I have another story to share which kind of led to a similar bug which was um actually with RSA based vdfs we were going to do this amazing kind of MPC with a thousand parties and and and we basically the authors of this this amazing paper kind of had proofs in the base case and then there was like two or three optimizations that kind of left almost as an exercise to the reader and it turned out that the optimizations completely broke the scheme and so I guess the the moral of the story is always prove the dam optimizations

it's it's just to be like very precise what is important is the Nova paper itself actually does not have a bug because it does not describe this scheme and neither does like you know info like fairness needed as our work on accumulation scheme our work on protostar or um the the Halo work so none of these schemes describe it or any other work that I know like uh um sangria or none of these works I think really describe it formally or improve it the the chain of cycle curves uh case they all just mentioned it and then in the implementation of Nova uh he obviously you know as soon as obviously uses it that a chain of like a cycle of Curves

and then there is you could colleges an implementation pack but I think that would be wrong because it's well where does it come from well it comes from being under specified and then it's very easy to to get wrong and there was some additional data and this additional data allows you to to break the skin so we agree prove the damn thing as you just said Justin who who's responsible for this who like as in no but not to point fingers but it's more saying like who should be doing this do we expect academics to actually prove every single like optimization that's going to be implemented or do the implementers need to actually turn to the papers and

extend the proofs that are already out there do we need some kind of collaboration yeah I mean I think definitely I think like it's hard right because the easy answer is like oh you know you should prove everything and you know blah blah but then like you know we probably don't get like five folding schemes papers a year right like there is a trade-off here of of you know trying to make schemes simple to describe and easy to understand versus like like ideally right like you give a full specification of your skin and academic papers are not full specifications or schemes we definitely still need that set and it's sometimes a little bit of a thankless step

um and that is an issue right it doesn't get the the sort of it doesn't get the um attention or the um like you don't get the reputation from it that that maybe it deserves um although there's right like there are great you know I think the Z cash service does an amazing job of giving like very detailed specifications and I mean this leads people to use their libraries um so I do think yeah it probably should be a collaboration I also think that you know this specific specific case like is a great opportunity for someone to give like you know some generic compiler which is almost essentially what they did in in the in the nugen Bonet uh seti paper this this one they not just what they

did which is good they didn't just show like he was a buck they also said here's the actual proof of how it is secure and um yeah I mean that is one saving Graces like like for me the Saving Grace is like do it you know people always complain about peer review and they say like well peer review doesn't find bugs and you know it's like what are like all this academic stuff is like nobody finds and to some degree that's true but if something is important enough then it will get more attention right like you don't have to just sit let it sit and marinate a little bit and eventually someone like will will find the the the bugs I think that yes the more proving you know things in

your paper and especially if you describe it in your paper then uh you should be uh like then you should prove it like you shouldn't have I mean there's another story I think from the the one of the snarks that the Pinocchio or one one of the other snarks that they use in Z cash and the zcash implementation I think the Z cashback was also like you can trace it back to some protocol in the appendix which didn't have a proof right so this happens over and over again you should probably shouldn't have extra protocols in the appendix without a proof and you should also be ideally like very specific about what you do and what you don't do so for example if you say like oh you can optimize this with uh with cycles of

Curves then like say specific that like in theory like you could or like we suggest that it might be possible that it's likely possible to use cycles of Curves and this is not yet proven we leave this for future work right I think this would be a good intermediate step I mean in terms of reflecting of like how can I kind of try and and and and help um avoiding these bugs I think one of the things one of the powers that we have as blockchain projects is the the power to Signal kind of what is important and so we can say Okay Nova unfolding schemes or a protostar these are important things you know please go break them I think we also have the capital to have uh you know bug bounties um

and I think you know as you said with Z cash you know they have this kind of this really strong internal cryptographic team and I think we've tried to do the same thing at the FM foundation and I think part of the role of this internal team is to bridge the gap between the academic paper and the final implementation okay I now want to move away a bit from folding a sort of look Beyond folding or what are the other options uh because we've said the One requirement we have is additively homomorphic commitments um the problem is those right now based on discrete log require large fields right um there's a whole other approach which is let's forget about all this fancy folding let's go Brute Force full

recursion but let's do this with very small fields and very efficient um like Hardware efficient Primitives do we have any way of comparing so here I'm talking about like the plonky 2 type stuff like long plus fry and recursion do we have any way of comparing these approaches other than just implementing benchmark and for comparing I would say that implementing Benchmark is is uh is the gold standard I think that's definitely true I I do want to say that you know like sort of uh go back it wasn't quite the question you asked but like the question that begs itself is like does folding really like and even elliptic curve based folding

really have to use large fields and I think the answer is not necessarily right so we talked about these constants the main like the main cost of folding is committing to the witness but what is really interesting is you pay um cost that is linear in literally like the bit size of the witness so if your witness is smaller like let's say each element is only 32 bits well then you will only pay like that constant Factor right like you don't pay for the um you don't like in in any other proof system that we know like even if you start with small inputs eventually things will get large and and there's

almost like there's no saving of of having you know like small Witnesses so maybe we can you know simulate smaller field operations right especially with techniques like lookups we could like even even simulate like uh you know 16-bit operations so like have something that looks very similar to our CPU or like a CPU from many years ago um but yeah like you sort of simulate like these small failed operations in a bigger field and um then only pay you know these very very small costs so you're saying pack more witness bits per field element I don't even need to do that just have smaller I mean just have like like you have a full field but if all of

your elements are in the witness of everything in the witness is just 16 bits then I don't pay like 256 times group operations I pay 16 times group operations so I do um and this is like very specific about you know these these this is where the the small constants really help for these folding schemes where I don't have to pay for you know like no matter how small your Witnesses I pay some big uh like I pay full Fields exponentiation per element I guess uh holding us accountable for you know what we just said prove it is there any security issue there if we restrict you know our witness to be on a specific

part of the field and maybe I don't know like this is I'm not saying this is the same right like I'm saying that there isn't this fundamental barrier of of using small uh field elements yeah absolutely like we should like this is not uh this is future work section I mean one thing I'll say is that on the hardware side of things um we're paying a big penalty because the CPUs haven't implemented these uh these large multipliers and once you go in the Asic land then the Delta between a 64-bit multiplier and a 256 multiplier is like much much smaller um so this this will be bridged to an

extent with with A6 um and I guess there's there's another kind of uh paper that's coming out of the second alphabetic I guess which um also intends to bridge this Gap using using lookup tables nice thank you both for answering me questions I kind of want to open the floor to the audience um if there are any questions I see some raised hands already yeah thank you for the discussion I have a question about uh soundness so when we fold instances together we introduce some kind of knowledge soundness error and my question is uh how do these accumulate and if they do accumulate

does this impose come like a practical limit on how deep we can go in IVC using folding um yeah sure so there's a theoretical and a practical answer the theoretical answer is uh it's a massive problem like you can sort of the the errors multiply so even if like the size of the extractor like grows so if even if it grows by a factor of two you can only do like you know less than 100 recursion steps uh and suddenly you have something that is exponential and we cannot prove or say anything this is the theoretical answer the Practical answer is like there's no attack we have no like there's probably

not an issue at all um the theoretical and maybe even practical solution to this is uh to build things in more of a tree-like manner where like the the issue is the recursion depth right how many like how deep is the recursion um so if I if I fold the recurs or do IVC and this is true for all IVC this is true for recursive snarks folding everything um if I build things in a tree-like manner um I can get sort of the same number of items at the bottom but like only the logarithmic depth there um and this tree structure is also the thing that's friendly to distributed and

massively paralyzed proving thank you first things for the Wendy for panel um I have I do want to challenge a little bit about why we're using IVC as a framework right so I think there is another way of thinking this which is proof carrying data which is by our originally by like Alexandra chiasa he if you read his like original uh like paper right he spent some times talking about the negative effect about like why IVC shouldn't be the framework of

thinking this right I guess to me it seems that the PCD is actually kind of more General things of thinking about like especially if you have like a heterogeneous instances of from from different parties right would love to like learn your you guys ideas about this do you want to answer I mean I think I think I mean in my mind um the the distinction between IBC and PCD is that with PCD you have these untrusted approvers but my understanding is actually like these following scenes are pcds they have this untrusted prover aspects of different untrust approvers can all collaborate um

I mean I I think of it as so you're completely right but PCD is the more General primitive uh the way that I think of it is or I think the way it has been described is that IVC kind of works for line grass and PCD works for arbitrary graphs but um you can actually build folding you can build PCD from folding schemes like we did this in back in 2020 the the split accumulation scheme works perfectly fine for um PCD Ariel very recently had some work extending kind of protostar to to be able to handle more inputs but even if you just have a binary input you can just you know like make your like arbitrary degree dag d-dag into a degree

2 DAC but just stacking things so it's um this is yes PCD is really the Primitive that we want it's the more General but we can get PCD from folding so there's um but obviously it's simpler to think about that's the only reason I would say this is also maybe something that I got a lot just in calling everything folding folding originally like the paper specifically considered the two to one case right you have two things you fold them into one the not predecessor let's say uh split accumulation considers this many to one case and considers PCD specifically um yeah and there's also I mean you know like then something that's not been worked on so much recently but we did

work on an original split accumulation paper and I'm sure was would be possible to get back is there's a very strong notion about zero knowledge in uh for PCD which is that at any step of the computation you can continue the computation without even knowing any information about what has happened in the past right it's like it's not just that you can con it's untrusted what has happened in the past you don't even need to know really leak any information about it the current folding schemes I think like mainly for Simplicity are really not described as zero knowledge schemes um but I'm sure we'll soon see you know someone adding zero knowledge back um and yeah PCD is sort of the end

primitive that we want with all the nice features it's just simpler to describe and it's a stepping stone yeah I just want to add a little bit because from the many distributed system like researchers and practitioners right I can see a PCD more useful in terms of like Beyond blockchain use cases right maybe we even want to like integrate PCD into our distributed system like cloud computing cluster so that it's more like a resilience at least intuitively to me yeah yeah that would be amazing I think there's one way in the front here thanks for the talk

um I was wondering what are your thoughts on like using uh folding for virtual machine type of circuits like non-uniform computations instead of just focusing on circuits right um I mean there's there's um what is it called Supernova uh that basically allows you to have um multiple circuits that you're accumulating and so if you have a virtual machines with lots of different up codes you might think of like one one circuit per op code kind of thing um yeah I mean I think we're more I mean people are trying to build like a ZK VM I'm using using foldings

and more we have we have techniques like like Supernova whatever techniques we have we have the auto star also has uh a different way of achieving uh you know non-uniformity so I have the high degree Gates now we have the CCS um we um we have all sorts of lookup tables so we we're starting to get all the little gadgets that we need to build very very complicated um you know circuits yeah one one interesting thing about you know the constraint systems is actually that um you don't even need um like a plan and all of the other constraint systems they have a lot of structure but it's you know like you can

in in these following schemes it actually suffice us to literally just describe completely different uh verification equations per gate right you can just describe an arbitrary degree D polynomial and they have to be in no way uh connected right normally you know in in plunk we have to do um I don't know there's like sort of different gadgets and you have to formulate your equation as part of these Gadgets in following schemes it seems like you don't even need to do that so it's a very intriguing way and yeah one more thing I'll add and correct me if I'm wrong I think with protostar the cost of doing this non-uniform ABC is like at each step you'll pay for your biggest opcode is that correct yeah I think uh I okay we need

to look in the details and again you know no unproven things but I think uh you I think you literally only pay for what you're doing um not just the biggest one not just the biggest one you're doing specifically okay I mean I think we we described as as if they're all the same size so it's a little bit more complicated but yeah yeah um in that case maybe the point is moved but I was going to say it might sort of change the way you want to make your circuits for your VM you might not want to do one circuit per op code you might want to pack them into similar size circuits to sort of spread out this cost cool thanks okay that was awesome thank you very much Nico Benedict and Justin

foreign