Episode 280 - ProtoStar with Benedikt Bünz and Binyi Chen

Transcript

[Music] welcome to zero knowledge I'm your host Anna Rose in this podcast we will be exploring the latest in zero knowledge research and the decentralized web as well as new paradigms that promise to change the way we interact and transact online this week we dive back into accumulation schemes with Benedict Bunce and Benny Chen from espresso we chat about the recent protostar work a non-uniform IVC scheme for Planck that supports High degree Gates and Vector lookups in our episode we explore some of the backstory

to these techniques share some definitions for commonly used terms in the accumulation literature and discuss recent works like Nova and hypernova and how these compare to protostar now before we kick off Tanya will share a little bit about this week's sponsor Aztec network is building a Next Generation encrypted blockchain powered by ethereum the team is proud to announce Noir the world's first Universal ZK language Noir makes it safe and intuitive to write ZK circuits and encrypted smart contracts enabling novel use cases like encrypted defy private governance and ZK gaming as a universal language Noir is domain-specific but blockchain agnostic you can build powerful ZK applications compatible with

multiple proving systems and verify your program on any evm chain get started with Noir today at docs.aztec.networkforward slash Noir you can also find the link in our show notes and now here's our episode [Music] so today I'm here with Benedict buns co-founder at espresso systems and Benny Chen Chief cryptographer at espresso systems welcome both of you to the show thank you thank you all right Benedict you have been on the show before we were just before we started reminiscing a little bit about the fact that you'd been on quite early in the show's life uh I think 2018 2019 to anyone who is unfamiliar you're one of the co-authors

of bulletproofs you're one of the inventors of verifiable delay function hyperplunk you have so many works that I think our audience will be familiar with um and if they've heard the episodes before that you've been on they might know a bit about you but still I think it would be great if you can share a little intro to yourself and maybe what you've been working on more recently yeah so I did my PhD at Stanford and then I also co-founded espresso systems um which we'll talk about a little bit but uh in the research space I'm also a research I'm an academic um I'll be starting as an assistant professor at NYU in the fall um and yeah I'm generally interested in a bunch of cryptography that you know

helps and improves blockchains um so zero knowledge proofs uh on the Forefront of that but also uh verified lay functions and and other other just cryptography that helps to make blockchains more private helps make them more efficient helps make them more environmentally friendly so these are the things that get me excited and today we're going to talk about a work called protostar which is sort of in a family of works that I and and many others in the field have been working on over the last couple of years fantastic then you share a little bit about your background or what led you to work on protostar yeah so my name is Bing Yi I do my I'm a chief cryptographer at

espresso system I did my PhD I use SP and I also spend one year at Universe Washington as a visiting PhD scholar and after graduation I spent one year at Google as a cryptography engineer so during my PhD and many working on improving the security of some symmetric uh crypto Primitives like hash functions or memory half functions we are the first one to prove the security of the script which is a very renowned script hash functions and only after the graduation I kind of started working with bantic and Ben and start my journey of exploring the KP field and snarks and starting working on this really intriguing and exciting field and I

guess that's the reason I started working on things like tiger plan and protostar yeah cool what is it about it that got you excited is it because it's very Cutting Edge hard like is what what is it exactly it's too perspective first is that it really involves some really advanced mathematics which make me very interested because I'm interesting probably Siri and Mathematics so you really have some really deep theory on top of it and also it really has really exciting applications for example like blockchain and machine learning so I kind of like the intersection on this kind of two Fields basically you can do

some really cool stuff in Mass but this cool math stuff can have really real impact in the world that can maybe like have real influence to the real applications I think that's the main reason I kind of find it really intriguing and exciting cool actually I just was thinking Benedict you've been in this field for so long I am curious how you feel about its Evolution recently like you you were working in this when it was pretty obscure still I feel yeah I mean I'm I'm I I consider myself like the first generation of PhD students that actually got into cryptography from an interest in blockchain

um so for me like I was like you know I was into blockchain since 2011 like you know when I was barely born uh but you know and blockchains were barely born but like and then I I you know I came to Stanford to do my masters and I took like one cryptography class and with Dan benay and and uh I was really excited about it not just because the subject itself is interesting but because I already knew the application so well but that was at a time where like you know most cryptographers I would say a little bit shunned the field of like the blockchain application because it's you know it's like noisy it's you know like there's a lot of like things going on um but it's not as you know clean maybe as some of the things we have in in

Academia um but I was always excited about that um you know I was excited about like the potential application and also you know that uh there is like you know I mean I I'm not sure how many other cryptographic subfields have their own podcast um you know that's uh like it's a really cool thing and and those are the things that get me excited and another thing that is really cool and interesting to see is that it's now the Innovation is coming not just from Academia but also from industry and like you know I'm not talking about like oh you know sort of better implementations but like you know this kind of whole work of of protostar

and the stuff that we talk about set up with Halo um which was developed by Greg's Hubbard and Sean and yeah and Z cash um who are cryptography engineers and obviously incredibly smart people but it's really cool right like this is really like you know at the Forefront of academic research but the the initial spark I would say came uh from industry and and that like is I don't know I'm still more and more excited about it and I have not yet gotten bored of the field uh in in in any way uh quite the opposite I would say do you think ZK is also breaking out of blockchain a little bit like that's something that seems to

be happening where it started obviously on its own got brought into the blockchain context received a lot of attention and funding and it's like there's this boom of new development like you just described this this connection industry feeding Academia and back and forth is there anything you've noticed with it sort of even expanding past that I think so I mean like I've thought a lot about like why blockchain like why why is your knowledge on blockchain why is this the perfect marriage um and I think like the one of the fundamental answers that I've gotten to is that sort of the properties of of blockchain and the properties of zero knowledge and snarks are sort of a perfect match so what do I mean by that

well in blockchains you have one person who creates a transaction and then everybody has to verify it right everybody runs the uh like all the nodes all the full nodes run this smart contract that checks this transaction so this is in some ways it's like very redundant but also inefficient right because it's like one person you know creates something and then everybody has to check it and so there's kind of a one-to-many and snarks have interestingly have exactly the sort of the opposite properties where one person creates the proof and everybody who checks it it does much less work right so you can kind of level the playing field there by using zero knowledge proofs by saying like yeah okay now one

person creates something but they can attach a snark to it like they can create you know a roll-up block uh even though multiple people have to check that snark each individual person does a lot less uh less work and so that's a perfect match and the question is like you know where else do we see uh these applications I think you know very recently there's been a lot of hype I mean there's always hype about AI but you know maybe there we get similar scenarios where you know you have one person who has some model uh and wants to you know assert that you know some properties like you know this text really comes from chat GPT and then everybody has to check it and and if we can find scenarios like that I think

this will lead to newer applications and uh so that's one angle and then the the cool thing is you know with the blockchain adoption just so much more maturity in in software libraries and new research and all of that has come that and I think this this also enables new applications so yeah very helpful um it's not quite there yet I would say for other applications but very very hopeful that this is going to come over the next five to ten years cool then you I actually Wonder from your perspective like having worked at Google was it at your time at Google where you started to learn about this stuff no I start after that I see okay mostly working on General cryptography rather than just the CK's RX that is like after that I'm

I talked to Benedict and Ben and start to get interesting zika snacks because already know the notion and some very classical papers during my PhD I just didn't um like didn't touch much on the Practical side of it but after that after meeting with panic and Ben started to to walk more deeper into it and become more interesting in it yeah cool are you also observing it sort of branching out even further yeah so like my conjecture is that it can be really useful in any scenarios that has become asymmetry uh like class right well basically there's a one party which has really big Power and has a lot of computational power and wants to prove

uh like prove something some computation is correct and this all happens in blockchain field as long as in in like llm like chatter CBT which uh in the machine learning field well some company they have a lot of machine to to train some really powerful model but they can provide services to average people and in this kind of scenario I totally believe that csnar can be really useful and and not only the scenario any scenario that can has this kind of similar environment will will be getting like benefits from CK Starks I think so cool I was uh just thinking you know like one I mean there's also like then you know so there's this General

Paradigm but then there's also other cool applications uh that are popping up like um I think recently uh Trisha data and and then Renee had a had a real world crypto they had um this this cool idea which existed before um which is that you know now again it's it's related to AI but it's not really AI it's like you want to know that the photo that you know some like someone posts a photo on on Twitter and you want to know whether this was AI generated or real right and um the actually there is some solution which is that your phone your iPhone or Android phone actually signs cryptographically signs uh the the the

the photo that you take but the problem is like you don't want to just post that photo you might want to crop it right like you might want to do some small edits that don't significantly alter the Integrity of the photo um and you don't want to you know uh like you want to say that basically this used to be an original photo and then I've done these like very small edits to it and now it's still a valid photo and it turns out that you can use zero knowledge proofs to actually do this and do it like very practically um and that's you know yet another cool application yeah of sort of giving journalistic Integrity through uh through zero knowledge proofs Benedict I

actually want to tell you about something that we're working on which is with Daniel Kang who has also done some work in that direction where we're looking at a very similar thing for audio so audio provenance because we created zkpod.ai which is like a copy of my voice answering questions how do you actually prove the difference besides the fact that that voice knows everything that's ever been spoken about on the show and I wouldn't necessarily be able to say it so succinctly um but yeah um that's awesome yeah I love that you're really cool yeah photo audio video Everything [Music] but the one thing we're still missing is a tested sensors for all of those things if you really want the end-to-end proof at this point the experiment we're doing

there is no attested microphone that we know of so we're sort of like emulating that with an early signature so we should introduce the audience to Espresso and what your company is working on I want to do a very very quick intro to it now focus on protostar and then cut back to it at the end of the episode but yeah share a little bit about what espresso systems is and maybe I will note we did do an episode on the project last year I think or 2021 so I'm going to add a link to that also in the show notes if people want to find out more so at espresso systems we're developing products and infrastructure to sort of make blockchains better and so in particular we have two products

um one of them is called Cape which gives you customizable privacy for ethereum assets so it allows you to specify what kind of privacy your ethereum asset should have and the other like distinct product these are two distinct separate products is called the espresso sequencer so this is um allows you to sequence transactions for these Roll-Ups so either ZK Roll-Ups or optimistic roll ups and it's a decentralized and shared sequencer which means that multiple rollups can use this sequencer and it's not controlled by a single party like current sequencers which could then sensor transaction and

charge higher fees but it is instead decentralized which is kind of a big issue right now right like this has come up this idea this need for decentralized sequencers or lay at least some criticism of some of the Roll-Ups for not having those yet I think every roll-up project at least suggests that that's on the road map I think that's correct but like how they actually get there is not necessarily clear yet exactly everybody has it on the room it because everybody knows that this is neat um but we're sort of providing it first and also the idea is to have a shared sequencer that that multiple uh Roll-Ups can use together but also as part of you know of our company we have you know many amazing people like like viney and and others at the company and

and we're also doing some research and our goal is to put that research out this is you know not even necessarily directly related to what we do but our goal is to help this space um because we're very you know involved and active in in the space so our goal is to make this research sort of give back to the community and make it public and and accessible for for everyone and protostart Falls exactly into that category cool and I think this is a perfect time to jump into protostar I feel like as a as a primer I will suggest that folks listen to a previous episode we did maybe two or three episodes ago with srinath seti about Nova Supernova hypernova as well as like

you know some ideas for what a future protocol could look like I've understood protostar as sort of a continuation at least partly of this kind of line of thinking I'll add the link to that in the show notes but before I even jump into protostar I wonder if it would make sense for us to kind of refresh some definitions and things that those works I just listed brought to the table so maybe we can start with the one that comes up the most which is folding or accumulation maybe a first question is do you see a difference between folding and accumulation schemes from my understanding uh is basically just the kind of different description to the same abstract object I would say okay yeah so what voting is saying that they

are folding some statements and there are some weakness behind it and the checking of weakness in the in the accumulation language is exactly the decision so basically in the accumulation language there are three steps first is accumulate accumulation and the second like accumulation proofing and accumulation verification and deciding and accumulation verifying is very similar to what folding scheme it is for folding to MP statements or r1cs statements interesting and to check the correctness of this witness or statements at the end and the last step is basically equivalent to the decision step in accumulation can you list those

again accumulation you sort of said it it was like yeah the first one is gathering accumulation includes like accumulation proving and and accumulation verifying and accumulation verifying is very similar to the folding of the statements in the following scheme and accumulation proofing is very similar to the folding of the entire like both statements and the weakness of the MB statement or r1cs statements in the floating language interesting and finally there is a deciding algorithm in accumulation which basically I think is similar to checking the correctness of these statements with respect to certain weakness in the folding language okay why consider that split split language is it because of

different papers and groups that are working on the same thing but just describing it differently or is it like there was an older definition that has been re revamped no it's essentially it's a it's a it's a paper thing different papers that sort of uh yeah everything okay um I can give you like you know the precise history it's like uh or it's it started with Halo um you know which introduced this concept of delayed sort of verification so you know when I do these recursive snarks the idea is that instead of fully checking the entire snark I'm going to postpone some of these checks I'm gonna like batch them or fold them or accumulate them

with other checks right all the same things and uh then basically check them later yeah and uh so this this idea was introduced by Halo and then we formalized this in a works I was one of the co-authors of that together with produce Mishra and Nick Spooner and Alexander keza and we formalized this and sort of showed that like um gave like very precise proves that this really gives you you know the same thing as recursive snarks what was that paper um it's called you know you get you get you the

criticized whether you have you know you come up with some fancy name and then you get ridiculed for it and you don't come up with a fancy name and then and everyone forgets the paper okay no I think uh it's not quite true but there's something so the paper is called proof carrying data from accumulation schemes okay and then actually later on uh that same year I think this is 2020 we had a paper showing um that you know this was all based on kind of these these bulletproof inner product arguments like that's where both Halo and this paper were based on um and then later on uh there was a paper by actually uh Ben Fish and and Dan Bernay and and others um that caught

was called Halo infinite that sort of extended this to arbitrary polynomial commitment schemes okay so it doesn't have to be the bulletproof polynomial commitment scheme but it can be arbitrary polynomial commitment scheme and around the same time slightly afterwards um I had another paper with with the same qualities of the accumulation scheme paper which sort of gave the first accumulation scheme for r1cs okay so this is basically just directly saying okay here's your circuit written as an rncs and you know how can we give a folding scheme and it was very efficient it has you know three group operations and then after that shortly after that Nova came out and brought it down from

three to two and they also gave it a new name calling it folding schemes okay um which admittedly is a better name like I think it's like you know they could have used their name like I I have to say accumulation schemes as the name was there first folding teams is just a better name I completely admitted maybe we should just use folding schemes but it's now like a little uh a little academic flip there but good to know wow that's fascinating and do you think I mean so the Nova breakthrough then was using something that you're saying was kind of introduced in this previous work but did it become more efficient did it become like more tangible with Nova um I mean it gets down from like

regroup operations to two group operations which is fifty percent better I think like our scheme before was also already absolutely practical okay I think they you know they um I think they they would say that their work was concurrent they were working on it on at the same time um so it was like I would say you know those works you can put into the same basket I would say you know like they sort of they're very similar to be honest but you know like two is better than three yeah in this world we want smaller numbers um so you know yeah that work that you're describing that came before what's the name of that paper is that the infinite or is that something else it's called proof carrying data without succinct arguments and the because the Innovation you know sort of there is

that previously we've gotten like recursive snarks from snarks right so you know there had to be something Snorks the essence snark stands for succinct right so you have to start with a succinct proof something that is very short in order to do this recursion and and it seemed to be like you know that there's an inherent reason for that but it turns out that with these folding and accumulation schemes we can actually build sort of these recursive proofs or these These Chains of proofs from something that isn't even like where the proof isn't even short as long as basically we have an efficient folding scheme for that proof

system so that's kind of the the the you know sort of when we look at it not in terms of concrete numbers but in terms of like you know fundamentally what is the new innovation is like it's it's kind of amazing how little we need in order to get this really really powerful thing that previously we only got from recursive uh snarks and that distinction between accumulation and recursion is that distinction made because of where this sort of combining is happening is like recursion I always thought of that like the end of a full snark process you then combine those and do it again whereas the folding seems to be happening at an earlier stage like

within a snark I don't know if that's the right mental model but yeah I think so that's that's correct basically the idea of accumulation is that basically you just uh um folding this list of statements into your merge statement and just check it at the last step that's very similar to what Halo like in philosophically is very similar to the idea of Halo but recursive snark is very different like basically every step we verify this not directly in the Square case but that makes his much less efficient because person because basically you need to verify this narc in the circuit and that requires the cycles of pairing friendly curves or or mostly you you might also

need to trusty setup so on and so forth yeah so I guess your understanding is correct well the distinction between accumulation scheme and snark is like that yeah and run the recursion right um a few more definitions we might want to cover IVC incrementally verifiable computation what does that refer to is that what you fold so I think IVC is kind of different it's like a very very useful crypto Primitives for proving the correctness for multiple iterative execution of some Sam function same step functions for example we can't understand the set function as a single op code in evm for example or a single iterate functions in the variable viable

delay function but here the key requirements of IVC is that the proof size as well as the verifier course of IVC should be independent of the number of these executions of these single step functions that makes this much useful than naively using a ZK snark for proving the correctness of this entire gigantic computations so that's general idea of what Ivy says and I think it has white applications like verifiable delay functions and succinct blockchains like Mina and also uh tkevm which I think is one of the most intriguing uh applications of IVC I guess and I guess the work you're doing like anytime you're doing folding this

is what we learned on a previous hypernova episode which was if you have these kind of repetitive processes that become something that you would want to use one of these works on so one like this is really actually cool thing about incremental via variable computational like I encourage the readers to read the first paper on incrementally verifiable computation which is I think from 2008 oh wow and it's like the introduction is great um because it has sort of this you know there's perhaps the simplest way to introduce the computational program investor is we address it as like there's a human motivation and the computational setting and the human

motivation is like imagine Humanity it's it's literally um the uh what is it Hitchhiker's Guide to the Galaxy thing so imagine you know we have the super computer that computes the answer to everything you know for like what is it exactly it's it's 42. it's everything in the universe and exactly and it's 42. so but it runs for like you know multiple centuries in order to compute that answer but the problem is you want to know like you want to like stop it in the middle and check that like you know so far it's been doing the correct thing and you also want to be able to hand off this computation so say you have some newer like Hardware you want to hand it off on the next computer but like you want to basically be sure that the computation so far was correct without having to

rerun it and this is exactly incrementally verifiable computation it's computation that runs like almost indefinitely but at every single step I can check that the computation was correct right I can stop at any step and I can see okay currently this is you know the the computation and it's so far it's been correct and okay you know one natural application is is you know Beenie was talking about ckbn but like you know one another one is is similar to what Nina is doing is these these succinct blockchains where every block like a blockchain is an infinite computation right that just adds block to it but at every block I want to check that so far everything's all the transactions were valid without having to go through the entire history and

that is IVC and folding an accumulation allows us to build IVC which is something that previously we needed recursive structure so it's the hammer or the I don't know like the tool that we use to build IVC right okay so IVC is almost like the The Meta architecture like The Meta concept you're trying to achieve with all of these different the goal yes exactly the ultimate application you want to build I see cool okay one more definition and then we're going to move on to protostar properly um error vector or slack vector this seems to have something to do with folding what is this and are they the same thing

so it's um yeah I think they're the same thing I've also heard cross terms you know it's essentially uh the way that a lot of these these um folding schemes work and one of the main things for shattering the one of the main things we do in protostar is generalize the recipe of how to build these things is that you have two statements and you take a random linear combination between them and then you multiply some things together you know which gives you some polynomial so it has multiple coefficients or terms but you only care about two of them like you know you care about the smallest one and

the largest one and then there's a bunch of middle one ones in the middle and essentially those are the error terms or the slack terms and this is an idea and you what you do is like you essentially you send these error terms in the first step and then you get a random Challenge and then you can check sort of the correctness by evaluating the polynomial at this random challenge so there's kind of this two-step process I first sent the error terms and then I send the The Challenge and then I check that you know these error terms are are correct and this is a general technique that you know appears all over the place so you can understand uh bulletproofs in that way you can understand many prior Works

in that way many many many following Works uh they all kind of use this technique of committing to some some error terms and then evaluating a polynomial at a random Point each step of the folding though are you using the same error terms is it sort of like a one-time thing that will be used for all of the steps or is it just done once I have trouble visualizing this still like I kind of follow the other stuff but this one's tricky yeah it has different intermediate cross factor in each step of folding well it basically it's just what we call accumulation uh proof but you also need to maintain a single error Vector commitment which is part of the folding statements or accumulation

that's why also why Nova they introduced the so-called relaxed r1cs statements because traditionally you can understand the r1cs statement as some MP statement that has no Arrow right and this area is just zero but you can definitely generalize that to make it a relaxed unless CS statement so that it adds some slack Vector so that it both covers the original non-aero mnp statements but also cover the one that's that statements being built after a folding and the reason it has this slack Factory exactly what band explains when you multiply two things there are some the first term and the higher degree term

but also there are some intermediate terms that cause this kind of errors I think maybe one one way to understand this is that say I have two multiplication you know I have two simple multiplications right and I want to check that both of them are correct so I want to check that 3 times 5 is equal to 15 and uh four times two is equal to eight um and what I can do then is is I take sort of you know I want to combine them into one so I I take some linear combination between three and four and five and two the problem is that then you know so then I get essentially you know I get some some result of this I

get both you know like this small coefficient is going to be the the three times five multiplication and the large coefficient is going to be the four times two multiplication so those I can check the problem is that in the middle you know everything gets kind of mixed up like you know I get three times two and four times plus four times five so I somehow need to you know cancel those out that is kind of those are the area or the slack terms those things need to be canceled out and they need to be canceled out in a way where the proverb cannot cheat and so what it does is it essentially sends this this cross product or this uh error term slack term beforehand because it can compute beforehand what it's going to be and

that basically cancels it out in the final process it's not that like when it says slack or error it's not that it gives like a wider range of correctness it's not that it's like when when you say relax it's not that okay you're actually just removing that messy part yes it's exactly removing the messy part uh canceling out the messy part it doesn't give you a wider range of correctness yeah cool all right that helps actually thanks Benedict thanks vignette I think we're getting somewhere cool that's awesome okay so one of the things that I guess over the last month or so that had been kind of coming up was this you know excitement around folding and there was sort of another Camp who were excited

more about some checks and there's almost like a verses happening between these two camps and then hypernova comes out and uses both techniques I thought when protostar came out that it also Incorporated some check and folding but I just heard that that might not be true so tell me a little bit about what protostar is doing and maybe help us like you know we've been sort of following the Nova hypernova trajectory where does it differ yeah sure I think first the goal of both hypernova and the protest is very similar the goal is basically to support like high degree gaze really efficiently without the use of like large heavy cryptography

operations so before that we see that there's actually some new work close sangria that kind of achieve this they support Planck relation but when they generalize Nova to the high degree case there are some caveats basically the proverb complexity and also the recursive circuit size are both proportional to the gate of the degree so both hypernova and the protostar wants to minimize this one to enimlate this cost okay so that's the basically the the same goal for both protostar and and hypernova but the the groups to solve this is kind of different what hypernova did is that they use a new accumulation scheme or new folding

scheme that afforded two empty statements in a different way using some check protocols but our skin basically doesn't use some check protocol at all okay for folding the folding is very similar to Nova but it's a generalization to Nova the key here is that we change the relation to be folded in into a new relation so that the check used is a compressed check so that basically there's only one equation to be checked in this relation and this makes the arrow Vector commitment which Bandits already mentioned before to be much much easier so basically okay before in the in the traditional case what you do is need to check attack and

gaze right you need to check n equations where each equation is a d gate and to cover that you need to commit to some error Vector whose length is number of case basically n okay so that's the reason why you need to commit a lot of error terms basically uh proportional to d as well as to the number of gates and that was expensive right that's what it's inclusive this is what was making a lot of this kind of like clunky right right is it slow or is it just costly cost very costly especially if you want to use really high degree Gates like d equals like 100 okay and it was because you're creating lots of error vectors because when we talked about this there was like one general error Vector but

there was also like these smaller the general vectors yeah when the degree becomes D the error Vector becomes from change from one to D okay and basically in hypernova this deal has this large Vector but what they do is they use a sum check to do this folding so that there's doesn't involve any group operation at all for that but what we did is quite different basically we merged this kind of engage into a single gate so basically there's only one equation to be checked so that means there's only one error elements for each error Vector so a commitment to a single elements can just be a trivial identity function rather than a group based homomorphic Vector commitment so that's our trick isn't that what the subject is

supposed to do isn't it supposed to combine it into one like what did you use if not that I would say I mean yes so exactly completely right um I think like to some degree you could say that the subject isn't Overkill here um so you know the subject protocol again you know also allows the you know it's it's it's like a snark almost in itself right it's uh uh like it has it makes the verifier efficient and it has short proofs but it turns out that you know what sort of these folding schemes and these accumulations in the verification showed us is that it's okay to sort of do more expensive things as long as you can delay them as long as

you can push them to the end right so when what we do is no fancy subject protocol we just take uh what is called a random linear combination like you know we just batch them all together in sort of the most trivial way and uh the amazing thing is that that if you did this this would not give you a snark for this statement but we don't care because we can delay the check of this random linear combination until the very end we can push that until the very end and yeah what is I think what is really nice like uh what I'm quite proud of and and protostar is that we kind of usually there's there's two things you know you can build something very general that works for a lot of protocols but you might give up on you know sort of some

features or some efficiency and what we do is we like extract this very very general recipe like we really break it down into building blocks like okay you start with like you know your most simple like a recipe would totally explains like sort of it exposed explains how you could get Nova from uh something like Nova or something like sangria but we both do this General recipe but it's also practically extremely efficient so so it has better parameters than hypernova it's like sort of the best folding scheme that is out there um because sort of once you break it down into these very simple building blocks it's very easy to think about them and and sort of come up with with

very efficient building blocks and and this gives us a very efficient scheme so I think that like it's a sum of things but it's it's not a some check uh or yeah I would say yeah the subject is is the overkill here interesting um yeah and also this also adds some efficiency uh Advantage because basically uh this in the sum check we need to do some hashes and number of hashes is really related to the number of gates and we eliminate those hashes basically we are reducing to the number of hashes as well as the field operations by a factor of log n in the circuits cool so you would sort of mentioned that Nova had originally been built really with like r1cs in mind I know sangria came along and enabled more of a plonk like

arithmetization I think to be used with it I don't know if I'm saying that right um what is protostar used with like where does it fall on that is it also r1cs or something else no it's something else before that I really want to highlight the general recipe we have as bandico set so basically these kind of General framework for building IVC skin is really really useful for us to build a new IVC skin that supports really fancy and advanced Gates Okay the reason of that is that this kind of modularity can very easily incubate new IVC Innovations because we can kind of abstractise a lot of steps into a general compiler so basically now if you

really want to build an IBC scheme it becomes a really easy problem in our framework what you do is just you need to come up with some so-called special sound interactive protocols for these Target relations and these relations can be r1cs can be Planck relations can be turbo Planck can be Archer Planck or like plus plus lookup or even the recently uh introduced customized constraint system by I think personals yeah and for all these kind of relations you only need to give a very naive and simple interactive protocol for that most of the scheme are just just basically letting the prover send the entire weakness of these statements and verify just check that this witness is

correct with respect to this statement we don't have any kind of succinct requirements or non-interact requirements for this and this makes this much easier to design this kind of scheme for these kinds of very complicated relations like look up Planck and after that after having this relation uh having this protocol for this relation we just edits into our very generic compiler and boo you get a new IVC scheme that satisfies some new very cool features interesting and also with great efficiency so so just as an example of that right like so we originally wrote it with Planck in mind the plunge arithmetization I'm also supporting lookup Gates really really efficiently we can talk about that also

a little bit um uh so you know sort of just supporting the latest state of the art of of of Planck uh plunker's constraints but then you know sort of uh hypernova and these customize the constrained systems came out uh so Selena has had this you know really cool new arithmetization which which might have some significant advantages of a plug that's still to be seen a little bit but um at least he would claim it has significant advantages and uh we then you know like very quickly we were like oh let's see you know whether this works with our compiler so we sort of press that through our compiler and Bam you know like it takes um like sort of the proof of security is like uh a couple lines and and we sort

of now put that into the appendix of the paper because it turns out that you can get exactly the same efficiency benefits and the same uh sort of other benefits by using now customizable constraint system and even in a year someone comes out with I don't know air plus plus CCS whatever you know like the coolest newest constraint system as long as it has like you know the right sort of properties and uh it most likely will fit into the the compiler and you know give you a new folding scheme I just want to like you just sort of mentioned is constraint systems almost a category of itself in this modular stack that you describe like we have the folding accumulation schemes we have the lookup tables is this a third the constrained

systems that one should sort of be looking at development yeah I would say so and like what is interesting you know what what oftentimes happens in in this field is um that you know sort of in the beginning people design you know schemes sort of like more monolithically um you know I'm thinking you know like sort of the first cash or zerocoin yeah exactly yeah they they built like you know one big snark you know that like does the air with monetization and does everything and does you know like one pulley and then you know sort of like people pull them apart um and say that oh actually like we can view them as modular components so you

know you can swap out the polynomial commitment you can use the arithmetization from Planck but you can replace uh you know the kzg polynomial commitment scheme with like in in a product based polynomial commitment scheme or with a fry base yeah commitment scheme and this gives you something new and you can give it a new name but it's really just like you know taking the Lego pieces and putting them together and then you know you can add lookup uh you know like in the beginning maybe we thought of look up as like being part of Planck but really no it's it's kind of separate and and and you know it's very important and and to to sort of pull these pieces apart because then like Innovation can happen more quickly because uh you know an innovation on one Lego piece sort of

innovates the whole stack and yeah one thing that that uh and absolutely true like if it should now think of the arithmetization as something separate wow you know and then sort of our compiler gives you an a folding scheme for uh that arithmetalization exactly so I just want to sort of repeat because I've pulled out four things from what you described there there's constraint systems lookup arguments uh accumulation schemes and arithmetization or like versions of it I would say constrain system and and arithmetization are that's the same pretty similar okay yeah I would say it's the same although you know like maybe someone pulls you know the things apart there so like you never know right is there anything there's

always more to do is there anything else that we should be on the lookout in terms of that like mod like modules that you think I mean you just maybe that could be one but is there anything else that you're examining that you might be able to distinguish and start optimizing one thing that is kind of cool is that so um I think you know one of the things that Nova did originally is that you you at the end you have this decider and right like we said like you know the whole idea is we don't need succinctness anymore we don't need snarks anymore and it turns out that this is true to some degree you don't need succinctness in the recursive uh step anymore but at the end of the day right like at the end

you know like uh you you then might get like if I do these this IVC for say A blockchain you get a proof that is about as large as one block right that has the size of one block so you might still want to you know compress that proof right like maybe even one block is too large if you're downloading this on on your phone right so you might still want to attach a snark at the very end right like you can always do that like you know throw a strike at it at the very end and so that's you know yet another component um this is recursion in a way or this is the depression it's it's it's I would say compression is a better word at the very end right like it's it's only we

don't do this like multiple times anymore we only do it once sort of uh we plug the hole at the end like um and and Nova for example introduced like a very efficient snark for their folding scheme like for example we did not do this for our skin like we left this as kind of you know you could throw some generic snark in it but like there's more work to be done to make this like you know very efficient and specific and you know like looking at it uh precisely um but this is again like the reason why we left this sort of out of uh is is because it's modular right like someone you know like uh again like other like this is a separate work almost how close to implementable is protostar like would

you say it's built in a way like in the way you you've described it could someone already turn this into a VM or do you think that we're sort of like still on the lookout for some monster protocol that brings all of this new research together I'm kind of wondering just in the same way like Planck sort of like it grabbed mind share for a period of time and then Halo 2 I feel his grabbed mind share do you think protostar could be that or do you think that there's like work still coming that unifies some of these things I think for uh first for implementation I think it's very close to to be able to implement as long as we write a monolithic like combine all these modulus tasks in integrate into a

single protocol then I think can be like very efficient to implement and in certain scenarios I do think that it can be very very advantages over other kind of uh approaches like directly using a snarks for example if you want to prove some evm transactions right which involves a lot of op codes then our scheme is really fit for that because basically it it supports highly gaze and it's a full lookup and moreover it supports some kind of non-uniform computations what it means is that you can select which circuit to run or to prove at run time like for example in evm there is a hundreds of op code right

and in a traditional way what you do is you want me to capture the proving of these hundreds of your code in one single small circuit but that's really expensive because you almost embed all the costs for every op code rather than the op code cause first for the one that you run at the step but we have a very really simple way to get around this and basically the circuits in each step is only proportional to the cost or complexity of a single op code rather than multiple opicos and this makes him very very advantages for solving this kind of problem compared to the monolithic CK snark scheme actually this made me wonder is there a specific

lookup argument that goes well with protostar you sort of say it's modular but does it use I don't know if this is described but as far as I know some of the most advanced lookup arguments are reliant on kzg's homomorphic additiveness what was it again this property so does does protostar have that characteristic is it working with something like kcg or is it something else uh I guess we do have a lookout protocol for for our protostar but you can plug into arbitrary vect commitments if you want like you usually won't like um Palace and commitment is fun and using kdg is also fun and the key okay Innovation here is we do have a new

again special sound interactive protocol for lookup relations and that's something new and that's something really really useful because basically with these new kinds of protocol which by the way is inspired by some previous work called the logarithmic derivatives by hapok I think which is really a great work and it inspires our protocol design and the resulting IVC prover for lookup now is only related to the number of lookup gates in this lookup relation but independent of the lookup table size this is some like kind of feature that also achieved by some other lookup argument like CQ but we are

really in a very different flavor like we understand basically more relative to the IVC framework so the unique lookup argument part of this and the interesting thing is that it's both like it has Better Properties like asymptotic properties than like something like CQ it sort of is completely independent of the table size it's you know completely linear versus CQ is has some n log n factors but it doesn't even require the pairings of kzg so you might ask yourself like how is this possible Right like how can it achieve more and and sort of require less well the idea is that again we can delay some of the verification right we're in some ways in in an easier

setting where we can delay the check you know we can fold the check of this lookup argument itself wow and and and uh so basically at the very end of the cycle like where at the very end of the recursion you need to do work that is linear in the size of the table that you're looking up in and and yeah the size of the table that you did your lookups in but the thing is you only have to do this once you don't have to do this every step so in every step your work is very cheap in every step the work is only like lit proportional to the number of lookups you do not the table size and only at the very very end we push that work until the very end either the work that is linear in the

table and this is why we get basically a lookup argument that is both simpler like sort of you know you can you don't need pairings you can do this without pairings without ffts you know without all of those Shenanigans and and still has Better Properties but that's because we're basically playing a different game got it yeah I want to just quickly can you please fix what I said before when I said homomorphic additiveness what was I trying to say attitude I think it's a homomorphic additiveness or additive homomorphism both of those are correct okay anyway but actually actually it's I think it's the multiplicative homomorphism like there's both additive and some multiplicative yeah that's the

partial thing that I think yeah partial yeah exactly partial multiplicative homomorphism that uh these lookup arguments take advantage of I see but it's yeah so I think what you described though is that like you have a almost bespoke look up argument that's so built in it's built into the folding in a very different way and makes use of those properties that's cool right but it inspired by you know uh this this uh logarithmic derivatives work um I mean of course like you know we didn't you know come everything we do is inspired by yeah some prior Works uh the shortage of giants we stand on yeah I want to ask you about security assumptions made on some of these different protocols or constructs

how should we think about that in this case like is there a ranking or like yeah how do you kind of place protostar uh I think for uh if I understand correctly so basically currently almost all the IV scheme are from some like heuristic security assumptions because the basically because you most of the scheme are proving in the random Oracle model but in the recursive circuit you have to instantiate this hash in the circuit but it's never possible to instantiate a random Oracle in the circuit so what we have assumed is that heuristically we assume that after we extension random Oracle or the hash in the circuit is still secure so from that point of view like you

can't stand that uh um like there's no standard model security for all the Privacy scheme yet but still they give you some like confidence why it is secure um Beyond this this part Beyond this age that's also why when we say that when we get an accumulation scheme when we get the IVC scheme accumulation scheme we are assuming some conjecture from like the on the secure assumptions yeah I think it's it's a very actually it's an interesting question because I would have answered it completely differently and it really depends on who you ask if you ask a theoretician so this is the theory answer so like in cryptography we sometimes fall into Theory and and apply it research and and people do both right

like I think Vinnie and I both you know fall somewhere in the middle and so the theory answers exactly what benue said that the security of of these IVC schemes is is really difficult to prove and and we don't really know like we need to sort of some like it's essentially related exactly to what Binya said and the recursive stuff that we don't really know how to like fully give a security proof but then there's also the Practical thing which is you know for example what kind of elliptic curves do you need to use and it turns out that all of these like since Halo kind of all the work that followed so all the Nova work all the accumulation for work are supportive star um basically is able to build this

without pairing friendly curves and so just you know sort of like curves that don't even have a pairing and why is this better well it's better for two reasons a we have slightly more you know pairings are great because they give you a functionality but they are slightly less secure like right they they you know there's like it's appearing is almost like a vulnerability in the pairing in in the security that we can take advantage of like this partial multiplicative homomorphism and so not having to rely on pairing friendly curves is better from a practical security perspective also it's better from an efficiency perspective because like pairings are expensive and and sort of these curves

are are are slightly more expensive like you know they might be affected five or ten or I don't know more expensive so from a practical perspective I would say that these IVC schemes actually have better security than you know sort of like a plunk snark or like garage 16 start interesting from a theoretical perspective though it's it's really weird because we have to rely on these heuristic assumptions and we don't know how to prove security so interesting yeah both are true yeah one more word in in a theory perspective like in Syria you can also instantiate this Vector mittens using lattice based hash functions or even hash like in that case it's even post Quantum secure I guess in that part compared to the pairing based

commitment schemes I'm not sure that this is actually quite true because you know you uh like or it's difficult at least to do because in these letter schemes you have some error and if you do the recursion over and over again the error grows so I don't think we quite know how to do this oh that's an open question it's an open question of how to do this sort of post Quantum secure so it's secure against Quantum uh uh cryptography Quantum adversaries yeah and but a very important one you know like uh can we do this yeah where uh because everything we do so far is yeah is broken by quantum computer but maybe

maybe in the future we can build something that is insecure against quantum computers I want to ask a last question a lot of the folding work has been focused on this like repetitive computation things that also look identical being folded in together but what happens if that isn't the case of the underlying data is there any work or exploration of like a more yeah like a more variant underlying computation yes I think so actually there's a like kind of pattern you can use if you want to do that for this kind of tasks if the task itself is not repetitive right for example if you want you're building a snark for a program execution or like circuit what you can do is what you do

is do just split this circuit into some like a lot of parts and prove them separately and combine them using PCD or IVC that can also help you with proving something that's non-repetitive and so that's why it's also useful in this kind of scenario I think that you know one interesting thing to think about is that um well how do computers work well um they have some you know at the end you have some program and that gets compiled down into instructions and actually like you chip right like it doesn't know at you know sort of at the beginning like how to execute all different programs it only knows how to

do some basic instructions like adding and multiplying as sure exactly all of these things and you know like modern CPUs do do quite a bit more things and and similar like the evm right as has been you had been has mentioned multiple times right like it has different op codes right for for how it gets up so it turns out that if you actually can do you know just some of these basic instructions that's actually enough to do like all of computation and one thing that sort of you know Supernova did this first uh but you know we also sort of support and protostar very very directly is what if I want to support multiple kinds of instructions

so you know not like multiple op codes one way to do this is just to have you know one circuit that does like instruction one instruction two you know does all of them in parallel and every single time that executes you know sort of all of them and but like really only one of them counts but the problem is then you work like you know then you have to in every step work as much as you know like say you have a thousand different op codes you have to work as much as your thousand op codes so what what Supernova did first and we do like very natively and very directly in in protostar is so-called non-uniform IVC so we're able to support different instructions and but the work is only proportional to the instruction that you

actually execute not all of the instructions that ever exist um I wanted to bring this back to Espresso and I wanted to ask you you know this work protostar is there a connection to any of the work that you're doing at espresso yeah I mean I think that that again right it's it's really important to point out that this is you know open research and and the main purpose is giving back to the community but of course you know long term like it's it's not what we directly work on so it does not have direct immediate impact on on the products that we work on but you know long term um for example you know the the the we also benefit from the Innovations and zero knowledge proofs so for example uh in in Cape we use some you know we

currently are using a Planck as our proof system and maybe in the future we'll use something that is based on protostar if that develops more and more or um you know for for the sequencer you might you know like have a smart contract that officially you know verifies your consensus and that could be easily done you know using like something like producer but that's more far out um and and right now it's it's really you know for the community to give back cool I was curious like in the stage of development that both of those products are do you sort of build them just using some proving system something that you could potentially swap out does it not matter really because you're going to be using some existing proving system and

instead you're working on like the architecture around it or does the proving system have a deep impact on how you have to build these architectures I mean this is like an engineering right question where where like in theory yes we can swap out the proving system always uh you know uh but in practice of course you know like the the specific efficiencies have have impacts down the line and you know like uh uh impact how much gas you know you're burning um so of course like I think in practice these things have have real real uh impacts and and matter and but you know of course we're also trying to build things modular enough that we're able to respond to to Innovation coming from inside and outside of the company cool I

could talk about sequencing all day it's like you know something the the main thing we're working on and you know maybe we should have a separate podcast on this uh yeah but it's uh there's like really cool and interesting stuff happening there and but you know we're building a sequencer that is agnostic to uh the Roll-Ups that are using it so it's a sequencer for different Roll-Ups um and different Roll-Ups you know both optimistic or ZK Roll-Ups could use it and and yeah the sequencer does not care what kind of uh proving system is being used for it I see I see I think I already said I was gonna say a last question but I have one more last question which is about the names that we use in this space um protostar

following hypernova and Nova also Planck and sangria I feel like uh Nico has Nico who is actually the co-host on the srinath episode um on hypernova he had sort of made some sort of Venn diagram of like the what is it ZK protocol names that are about alcohol about space and then I don't know what he called this but basically have the words hyper Proto Turbo Ultra so it seems to be I almost feel like we're one step away from being able to make like I don't know if you ever saw these like Indie band name generators which would just be like combining like

I feel like we're getting close to being able to do it for us um directionally where do you think we should go if we want to introduce a new Canon of naming things [Laughter] I don't know when you do have ideas like uh ask chat GPT could be biology.ai yeah it's like apple right like at some point they switched from like uh big cats to like places in California right totally I think they ran out of like big cats and then um yeah I mean producer like I mean we were thinking like is there something combining alcohol and uh you know the Galaxy and whatever but

this is like a tiny bit of like meaning to the name right because it's like we were like hypernova you know that's very at the end of of the star live yeah I think um and so we're going like back to the beginning but because it's also like because it's yes it's like a new protocol and improves on it but it also explains sort of like you know where these stars come from like the the the explains how these folding schemes work in the different building blocks and so that was like the you know nice The Meta Meta idea behind it um but yeah cool I don't know yeah maybe we got to go back to earth like uh maybe but like the galaxies like there's huge

like you know there's many names there there's many names in the Galaxy but also I mean I I would also keep an eye out for what uh Zach comes up with because recently he created Goblin plonk he went way off card so it would be interesting to see what else comes out there oh he's got Goblin plonk and honk so we'll have to see where that where that goes [Music] like I'm all for like creativeness and naming um as a frequent offender myself like uh I think it's you know it's great like you know and it's like it's like yeah it's it's kind of fun and a little bit silly but it also like you know makes people remember yeah it's really helpful I think it

really is but yeah that's one of the funniest thing in the favorites yeah for getting a members for getting cool in the empress yes exactly cool all right I want to say thank you to both of you for coming on the show and sharing with us sort of the background to protostar all about protostar and yeah how this relates to what you're doing thanks so much for coming on thank you so much thank you yeah thank you cool and I want to say thank you to the podcast team Henrik Rachel and Tanya and tour listeners thanks for listening foreign