ZKPodcast: Exploring the Fractal transparent SNARK construction

Transcript

[Music] welcome to zero knowledge a podcast where we talk about the latest in zero knowledge research and the decentralized web the show is hosted by me Anna and me Fredrik in this week's episode we sit down with the guys behind the fractal protocol but before we start up I want to say thank you to this week's sponsor trail of bits now just recently a critical vulnerability was found in the certificate validation functionality on Windows 10 and Windows Server 2016 2019

this bug allows attackers to break the validation of trust in a wide variety of contexts including HTTP and code signing trail of bits has developed a proof-of-concept exploit and put up a website called whose curve is it anyway that lets users test whether or not they're vulnerable the link to this website is added in the show notes now to learn more about this vulnerability and the trail of bits exploit please check out their recent blog post entitled exploiting the Windows crypto API vulnerability and also keep an eye on the trail of bits blog for security news and explanation pieces just like this one it's linked in the show notes as well so thank you again trail of bits and now here's our

episode on fractal so this week we explore the fractal protocol with its authors dev and Nick both students of Alessandro Piazza at UC Berkeley so welcome to the show guys thank you thanks um let's do our quick intros tell us a little bit about who you are and maybe where how you got interested in this particular problem that you want to solve with fractal okay yeah so I'm Nick I'm a PhD student with Alessandro Berkeley and yeah I've basically been interested in more of the kind of theoretical computer science side of things for a long time and this kind of

problem that has very strong links with theoretical computer science with the kind of broader complexity theory okay this is something that the you know made it really appealing to me along with the practical connections I'm Dave I'm an undergrad at UC Berkeley also after Alejandro and I got interested particle because I work on Stark for a while and I thought it'd be very nice to have like a succinct verifier snark previously like Aurora was a linear verifier is fractal replacing this thing called Aurora is that what you've just built or is it what is it what's the relationship and what is or Aurora Aurora is a prior Starck which was for our NCS and I've actually like

under the protocol behind fractal is sort of figured out a way to add pre-processing or holography Toradora which then makes your verify are very efficient and then enables like recursion yeah so you can think of fractal as being a protocol which has the same structure as Aurora and solves the same problem but that's this additional feature that or or doesn't have which is called pre-processing so that was the sort of explicit intent in setting out like you wanted to do something like or about with pre-processing exactly or was there another aspect to it yeah exactly so Aurora already has like a lot of very nice properties it achieves good proof

length but it's not in this class and it has a fairly efficient prover but did not have this kind of nice property of pre-processing which allows you to speed up verification a lot and so fractal was kind of explicit attempt to take all of the good things about Aurora and kind of tack on this this extra feature we obviously want to dig in deeper into this and I don't know how exactly will get there it's a very complicated topic but I think we do it through various angles and means of trying to analyze it but the first thing that came up to me and this is something that's like I noticed as a trend is talking about holographic proofs what is a holographic

proof so a holographic proof is a proof you in addition to having the kind of standard proof conversation like you where you have a proof that is provided by it by the prove it to a verify you also kind of before beginning of time you you would take your input and you encode it using an error-correcting code so you you take an input and you apply some encoding to it the idea of this encoding is that with assistance of the prover the verify anole no longer needs to read the entire input in order to be convinced of the of the statement so I can I take my statement I encode it with an error correcting code and this means that now I don't need to look at the entire

statement noise to be convinced that it's true I can kind of look at some individual positions that I choose at random then I can say with high confidence whether the statement is true or not based on just these positions and my interaction with approver so this leads to pre-processing because what I can then do is I can apply some transformation which takes this this kind of model where I have this encoded version and I can convert it into a pre-processing routine the holographic proof then is not the pre-processing it's preparing it to be processed it's before you add the compaction top so like this is still in the information theoretic or unconditionally sound

protocol and then you add cryptography in order to get a thing you can actually stand sheet so holographic proof is like the theory that allows pre-processing well yeah we're still in the random Oracle model at that point yes so this is a calligraphy is like the idealized model that allows you to do pre-processing where did that term come from is this a long-standing cryptography term or is it pretty recent that people are using it so it's actually fairly old it came from I think this paper from 1991 by Fort know and lund where they're setting up this whole area of ECP's and program checking and all of this stuff like it's like right

back there at the roots of this problem see checking literature and they were interested in precisely this problem of like if I have an input which is really long but I want to verify I wanted to check its validity very quickly how can I do that and you can show that it's if not possible to do it unless you have this kind of additional capability of encoding it with an air parroting code before you stop I think actually that paper you just mentioned it rings a bell I think we talked about that in the first episode who did with Ariel Gabi son I think he brought that paper up I remember trying to find it like looking it up it's kind of one of the classics it's like a very extremely

influential paper and thank you everything that we that we're talking about kind of all of these ZK stocks they all owe a great debt to this this particular work was it actually did it use the term holographic proof back then or was it the concept was introduced back then because I've understood that the word holographic proof as far as I understand there's something like that in plunk but they don't call it holographic proof they call it something else oh yeah so I think they call it holographic yeah in in this bfl paper this is the the term comes from that it's we didn't kind of just come up with this okay and then what is what are other terms that are used to describe

this exact or something similar to this they call it's a an algebraic interactive proof or something like that I think yes there's like three concurrent works roughly like plunk Marlin and darks and everything they all call it something different it looks like they just as far as I can tell looks like they're just looking at security the algebraic group model against algebraic adversaries they're talking about also some idealized proof system model they're not explicitly focused on pre-processing so what the what they are talking about actually is more of a being coding during the protocol rather than before rather than

of the input so what they mean so they they use the the term polynomial protocol anomaly what they mean by that is that what the prover is saying in the protocol is guaranteed to be encoded as a polynomial this is sort of orthogonal to the holography aspect so the holography aspect says that I also am allowed to assume that the input is encoded using a low degree polymer so the notion of algebraic holographic proof which is was what is used in Milan combines both of these things it says it says that the input is incredible using a polynomial and also all of the previous messages are encoded using

limits you just mentioned another paper there Marlin which I don't think we've actually talked about yet on this episode we've definitely mentioned in the past maybe give a little bit of background on what Marlin is when it came out and how it relates to your worker so Marlin came out rough at the same time as fog did and it's it's using holography with these Panama commits essentially improve upon sonic so it's in the same setting of having an updatable trust uh and so in fact will we improve upon that the Marlins electric holographic proof and convert it to the RSI LP setting sort of the setting that we use for these darks did

you say RS what did you just say RS io p yeah so these stars are quite modular there's an RSI o P which is when you talk about using air cracking codes and so you strict everything to reed-solomon codes this is an air connection code where you have a polynomial oh and you've committed say a degree D polynomial and you come into more than D points this gives you some error correction properties then in IOP is where you're just talking about rounds and messages and you get a stark at the end when you add photography what does IOP stand for interactive Oracle proof yeah so so IOPS are kind of the basis for all of these proof systems in this

family the fractal belongs to so an IO P is a generalization of stands for internal proof is a generalization of an earlier notion called a PCP or probabilistically checkable proof just probably come up before I guess I don't sure yeah yeah but just I guess just to recap so a PCP is essentially a proof string where I have random access into the string as verify I can look at the string and I can choose kind of random places in the in the string to query and I can find out what the value of the string is at this point and these were developed also in this paper this bfl paper to kind of

understand program checking and then they became very very important in complexity theory but the reason that interesting to us is because of this paper is Silvia McCauley in 94 where he explains how you convert a PCP into a snack so this was actually the first construction of snacks called CS proofs and an IOP is kind of a generalization of PCPs and what IOPS are attempting to do is to kind of fix the deficiency in this construction law it may be a difficulty in this construction like what was the problem with VCS proofs why don't we use them for everything it's because PCBs are extremely complicated so si has proofs actually like a super

elegant construction they are known to be post quantum secure they only use symmetric key cryptography so they're really fast cryptographically the problem is that the underlying object this PCP is extremely difficult to construct it's a it's an enormous ly complicated object and what I Oh peas are an attempt to do is to basically say okay we don't know how to get to our PC peas but we can build essentially the same thing using a very similar construction from this thing called an IO P and what our peas add to the mix is interaction so a PCP is kind of a fixed string and it just you know it the prover writes it down he goes away the

verify can look at an io p adds interaction to this so the proof can write down a string the verify can then send a challenge and then the prover can write down another string and so on and so forth this can repeat for some number of routes and this additional power allows you to design much more efficient protocols and then what you can do is you can use kind of established cryptographic techniques to squash this interaction into a non-interactive which is well you non-directive argument which is what you wanted to begin with that's interesting so it sort of went like static to interactive to non interactive and is the RS io P the non interactive version or is the RS part something else

there this is reed-solomon I believe what you just said yes so the RS io P is sort of akin to these other things like HP and polynomial protocols and stuff it's like a more idealized model you can convert from an RS io P into an IO P and the way that you do that is called low-degree testing which i think is something that ellie talked about in his episode so you have a protocol which allows you to basically take an RS io P and enforce the the RS io P model in the IOP set when you said PCBs are difficult to construct do you mean that it's difficult like for a human to express

the computation they want in that piece be more computationally difficult I mean computationally difficult so actually PCPs can support the the same expressive languages as other things so it's like circuits and rank one constraint systems all of these things the trouble is that when it comes to designing the PC P you're really fighting against this non interactive nature and this means that actually writing code to build a PC P is very difficult and the resulting thing will be extremely inefficient right in the words that make up I owe P an interactive Oracle proof you've sort of

covered a little bit of the interactive and proof sort of understood but why the term Oracle and just the reason I mentioned that two years like Oracle has different meanings in different contexts I imagine unless it's the same actually yeah I'm curious to hear what what is the Oracle part of that mean why is it working so so here you talk about other context your friends like the d5 Oracle may be a similar idea where like in Oracle just think that exists and you can ask get give me the value of the article at some point the DPI contacts the point is generally time here it's at some like element in a in a field and then the Oracle gives you the result and idea of

the Oracles it's like can't be tampered with it's like once you give the Oracle it's set in stone forever and so in the IOP model you talk about these Oracle's with the prover will give you an Oracle and they can't touch it later on in the protocol and then there's a question how do you actually like materialize the Oracle and so this is even an interactive model this is still idealized cuz like how do I give you an Oracle and you see you need kapag rafi even in the interactive setting to actually send the oracle oh and the way you do that in Starks is you make a Merkle tree you say that you're only gonna you're only allowed to look at the oracle and on these points and so then

we can make a Merkle tree of those different points and then I give you the merkel route and when you want to look at the oracle at some point you just take them I give you the evaluation and a Merkle tree authentication path so I think that is the same or similar to Oracle's as people might know it from my blockchain context but in large chains do you typically talk about a trusted Oracle or an untrusted Oracle but in untrusted Oracle is just like I don't know I user if it's a weird thing and yet typically Oracle means that it's just some some source of info you can trust but in this case it's you know you can trust it because you're actually

providing Merkle proofs of the thing that the Oracle was giving you I've always understood Oracle is also kind of like a reflective of real-world information it being brought but maybe it's just this one case of an Oracle or like something in the real world is brought in I think that's specific to the blockchain context because Oracle's are only used to get data that is off chain anything on chain we don't need an Oracle for so it's kind of automatically becomes that in the blockchain world okay I don't think it's necessarily alike a property over yeah so here the previous is giving you Oracle so sort of the point of the protocol is that if they give you an incorrect particle on external sorry incorrect Oracle or just garbage the

bare version fail like it's going to TechEd this what we mean by by Oracle in this particular setting really is just a very large string on database that you can like look into and you are guaranteed that it doesn't change over time like once if you it can't kind of adapt to the queries that you're making to it it's fixed over time yeah so this is the usual notion of Oracle and kind of theory decides I guess maybe there are other other ideas of what an Oracle means but in the ISM and rhetorical proofs the important thing is that the

Oracle is not able to kind of cheat adaptively so it you can write down whatever you like but once it's written down it's written down and not allowed to change it as a malicious as an adversary determine a hp's you also just mentioned that what does that stand for a sense for algebraic holographic proof oh yeah so it's a very similar to a holographic IOP which is the thing that we use in fractal really there's not a like from a high level there's no difference between them you should think

about them as being the same thing so holographic IOPS and HP is pretty much the same holographic RS IOPS and HP's are pretty much the same so did they both represent kind of the same demands on your proof system the only real difference is kind of the in for an a HP you care about what happens when you turn it into a stock using polynomial commitment scheme whereas with a holographic RS IOP you care about what happens when you turn into a stock using this combination of a low degree test and this hash-based cryptographic compiler cool well I think that's really

good on definitions there so let's take slight step backwards and talk about fractal and high level you know abstract level what is fractal and what did you actually achieve with this okay so freckle is a transparent pre persisting stock which is also post quantum secure and aim with fractal was really to solve this problem of transparent percussion so there has also been other work on transparent recursion using a different approach which came out kind of concurrently with fractal but the the intention was to be able to do recursion without trusted set up what

was the other work so that there was also this recent work Halo jutsu shown Bojack broken there are hopwood where they also achieve some kind of transparent recursion they use very different techniques to fractal and this is kind of concurrent with with us so the thing I will say about that is that it is not post quantum secure fractal is and there are some other sort of smaller technical differences if you want to use it but that's where it sits in relation to hailer so this was yeah so our intention was was to enable you to do recursion without a trusted set up halo-halo is also as I've understood it in a comparable camp

- what SuperSonics from beneficent phonetic bun says but fractal I never here kind of put in that same category so is SuperSonics dealing is it comparable to Halo at a different point or would you say fractals also comparable to the SuperSonics work or the darks hmm so yes handling SuperSonics have similar group sizes is they're both trying on discrete log s assumptions and I guess they also have similar graphic assumptions whereas fractal as much larger proof sizes because of making fewer assumptions and is it the only one that would be post Quantum's cure yes and are you like have you also

I mean what were the what are the other features of halo and it's like Universal I mean halos Universal recursive is faster like what was transparent oh it's transparent then you guys are too so actually would you be considered in the same kind of category as those two or more in the same categories halo same categories hail SuperSonics don't recurse or not no one's like we don't know they have a mission recursion okay got it so yeah like there's two thoughts that immediately come to mind for me one is I want to break down these like we've already talked about holographic proofs pre-processing and like digging more

into how that actually makes recursion and like I want to touch on that but just before that like transparent post quantum secure and all these things kind of make me go isn't this what Starks are and why do Starks exist now then yeah okay so so Starks also one of these IOP based stocks and so they have many of the same properties that fractal does so the difference between fractal and Starks and kind of way you would use fractal over the Starks comes in the kind of computation that you're trying to do Starks are very

strong at doing very structured computation kind of repetitive computation for example if you wanted to evaluate a hash function over and over again and probably a stock is what you want a fractal is very good at unstructured computation this is something that stocks are not very good at and they a lot of the properties of stocks they are so wonderful for structured computation just don't carry over to the unstructured case so if you just have an unstructured computation then fractal will work much better and the reason is this pre-processing right that's interesting yeah that makes sense so let's talk about the pre-processing

and in a previous episode I wonder if we talked about this both with Plunkett and with Kota but I know we talked about it in the recent episode with Kota is I asked the question what is the trade-off with recursion why can't every snark recurse and the answer is well you need this pre-processing trick and what what is that trick really then and like how that how does it lead to recursion we already talked about what it is but how does that make recursion efficient so what you need to do recursion is you need the verify when verifying a circuit to run faster than

the size of the circuit that you're verifying this is the essential thing that you need for rakesh n' and the reason for this is that if you think about what happens when you recut when you recurse you're approving a statement about the verifier accepting a proof so now your statement the the circuit in your statement is the verifier itself if it's not the case that the verifier is smaller than the statement then as you recurse the circuit that you're trying to check will grow and grow and grow and this will become unsustainable so in order to keep the circuit size small it must be the case that the verifier is

smaller than the circuit that it's checking or runs faster than the cycle is checking in order to do this so initially this should sound impossible because the verifier in order to check a circuit should know what the circuit is that it's checking it needs to be able to read it and if you don't have any additional assumption then that this is actually impossible so one way of getting around this is to use this pre-processing so you take your circuit and you condense it into some small digest using pre-processing and then you can achieve this property of having the verify be smaller than the circuit is

check well that's cool yeah that makes sense I don't really have any followers okay are there other techniques that people are exploring to make recursion more efficient besides just the pre-processing part and this making the verifier more efficient so there are a lot of interesting things that happen when you recurse because what you're doing is you're taking your your verify which is checking the computation and now you want to verify the computation of the verifier which means you need to think about things

that you otherwise wouldn't think about yeah so like one example is that with fractal we're assuming your initial computations very unstructured and I guess most process parts that's what you do but in fractal the verifier still has a decent on structure to it one example is Merkel tree education paths you have to verify a lot of these but emerges education path itself is very structured you take a hash function and you each apply it like a bunch of text and a hash itself is very structured you take a round function and apply in function types so this means that there's you can probably exploit this somehow when you recurse so that oh that could be another kind of chance that would be another place to look for in order to make

recursion better right yeah I didn't say that well but words yeah another really good example of this happening so you've probably heard of stark friendly hash functions so one of the big applications of stock for any hash functions is that if your verify needs to evaluate a hash function as I verify it does because it's doing these merkel treats then you're going to want that hash function to be stark friendly or fractal friendly it's basically the same thing because you're going to want to prove that the

hash function is correctly evaluated so this like completely changes the trade-offs in designing verification algorithms because now it doesn't really matter how fast your hash function is on your computer what you care about is how fast your hash function is inside of the snap going back to that question that Frederik you just asked about what does that mean for Starks like if you're able to take advantage of the pre-processing idea you're able to take advantage of these hash stark friendly hashes yeah how does how does fractal then differentiate itself from Starks still so Starks are still starting from a highly structured

computation and this actually lets you get better constants like by leveraging the structure directly you don't take a blow by converting to a generic form at the generic mark being Arwen's yes and so this lets you hit a better proving time constants which also can lead to better proof sizes or verifier times but it's very like context dependent because like it's hard to talk about or comparison representation in stark so like a pre-processing start in general because it depends on how succinct or like how structured your problem is you care about something we haven't explained very well or dug into very much on the podcast is the the structure

of computation the way you express your program in a Stark we have talked quite a lot about our 1cs but so is the difference essentially that in fractal you're using our 1 CS and that's your your unstructured computation and then in Starks you have you know as sort of Stark where people have explained they have this VM model essentially and that at each step of the computation it outputs some some additional you know bit of proof and so in this vm model it you can efficiently exploit the fact that it is a structured computation and

so does it boil down to these two like computational models or the cryptography and proving structure that sits atop them if you know what I mean so they don't have your thuggin or for example like re I'll talk about this a bit in the pump thing but turbo Punk is sort of and this custom gate final work is taking our 1 CS or something Oren's yes unstructured like and then saying can we add custom gates but can we add or start like logic on top and this is something you can similarly do with like fractal nicely what's cool so you could kind of mix the two computational models yeah we also have a work which does

something more stark like for our 1cs so you can essentially design your computation in a non CS model and if it's sufficiently structured you can still do kind of stark like things with it the format is not necessarily the the question it's more like what like what does your computation look like kind of at a fundamental level is it structured or is it not structured if it's structured then you can avoid kind of the overhead that is associated with processing it and there is some and if it's unstructured then there's nothing you can do you kind of have to pre-process just fractal borrow from any other protocols or any other concepts that have come before it when you guys

were developing it it builds on Marlins protocol Marlin itself like figured out how to add pre-processing to rora to get a sink pair fire this is like this is a breakthrough in this particle design and then for fractals actual like IOP protocol we then like took Marlins AHP and then like compared to the RSI Opie setting because there's some subtle differences that make the protocol as specified in the paper have very bad constants in the our SOP setting and then we found this like sort of trick to reduce one round off that particle what does that work look like I'm always fascinated by this say you want to take the HP from over here and convert it to

the RS IOP setting over here and like do you sit down in front of your computer and Google that like how do you actually do that work I guess you you take some people who have a lot of experience in designing RSI Opie's and you you know look at the eyes the you look at the HP over here and do you you think okay what would that look like if it were an RSI tepee these things are very similar in a lot of ways and so this is the the hard part was sort of already done by marlin like the creative part of actually coming up with this protocol was was mostly done by Marlin the kind of technical work from

moving from HP to RS io PETA IOP was something that we'd already had some experience in from writing the Aurora paper and so you know the steps uh maybe not straightforward but at least kind of they were set out already in this previous work how much time does it take like you know from this initial idea of I think we should you know do this - you had the paper done what's the time like having a paper done was that a lot longer because like the key contribution of the paper was less of this particle more so like recursion and all the steps to inform elations to get it yeah so I

guess we were done in about six months maybe less than that yeah I don't recall exactly when when the thing officially started I remember this we had a working particle like the day befores econ one start this is like when we had the rational some checkout unifix the quadratic trajectory yeah so I mean it depends on how much care you would take when you when you write things you're publishing for academic conferences then you have to be you know very careful when you're writing you have to write a bunch of definitions and proofs and things like that it's very time-consuming so probably from from idea to paper takes probably like three months from like well-formed idea to

written paper but as dev said there's a lot of stuff besides the protocol that goes on in this paper so we take another look at recursion from a formal cryptograph perspective we prove that everything works we prove that everything also works and the presence of quantum computers this is a kind of something that hadn't really been looked at since the first paper on recursion which was in 2013 or something like that yeah yeah that I think that's what Isaac actually highlighted in that episode was that in the in the fractal paper you have a very clear clarification about what makes recursion work and that was something he highlighted and I guess this sounds like

that was a lot of your work then it was more like researching and checking why I guess if and why this works yeah so actually we we had one particular goal in mind which was so to date essentially the only approach to recursion that has worked is this pre-processing type approach so there are other ways that you could try to achieve it but somehow you know the only thing that's really made it to practice is is pre-processing and we wanted to pin down some formal mathematical reason why that's the case and this is what we do in fractals so we show that basically pre-processing gives

you an asymptotic improvement over other methods of potential methods generation something that I've always been curious with the recursion and then I've gotten mixed messages on is whether or not it worsens the security of the set up so there's some arguments for you have to use a smaller key length or something for it to be practical and so it's like breakable or whatever or like and then there's another argument unlike the deeper you recurse the more insecure the whole construction becomes and then you have other people who say no no this is not all at all the case and I don't know

like it shouldn't be less secure what's your guys's take on this what how does recursion affect security so okay so from a cryptographic like provable security perspective there is something that happens when because which is quite technical but essentially insight in the proof went you the the deeper you recurse kind of the more you need from your underlying cryptographic primitive in order to make things work this doesn't translate into an attack like we don't know how to exploit this in any way but there is some kind of artifact of the proof that poses that this to happen in terms of this stuff

about key lengths I think this is maybe to do with a specific approach to recursion using elliptic curves like prior to fractal and Halo there was really only one way to practically achieve recursion which is to use these think schools cycles of pairing friendly elliptic curves so this is an object which it so it's sort of hard to find algebraic object and I think today we only know of one class of these it's the MN t46 cycle on earth it means I think but essentially this it's not very not ideal so because that you have a much larger field which then means that your

snark running time is much slower and if you're doing like cryptography and stuff on this your public keys have to be much bigger normally you do look like her photography over say a 256-bit field slash curve so then that's you know 20 56 bits per key now we're at around say 700 ribbits but that's more due to like sort of the algebraic object you need to recurse that setting not that recursion itself lower security right yeah so in particular with the type of percussion that we do in fractal you don't need to worry about these things you can choose your field as you like the only thing that you really have to worry about is kind of the algebraic complexity of your

hash function over that field well and as a practical matter sort of the running time your hash function this ends of mold-making you're Cooper time so one thing that I think I saw is that this is actually implemented as well and that you've been running Spearman's with it and actually trying to use this in practice it's not just a paper there are some code attached to that as well yeah codes online live I repeat our work vivo and was that code that you wrote for this paper is it like you're modifying something or you know and what quality is that code is it something that you would go out and recommend that that a block chain be used uh like based on today or is it like I you know I

could be me a code it's definitely like a academia code like there's been no code on it yet I think if there was one then maybe it'd be suitable for walking fighting on their security preferences the library stuff we've built for leaps are built to measure performance of these starts but the verifier the circuit is actually not too large so this is a potentially auditable code bath what language is it written in C++ it's it was sort of inheriting from a bunch of the live snark work like the finite fields and etc and like FF keys and it was started before the rust snarf ecosystem really like blue lab were you

I guess you were you developing this as you're writing the paper is this something you write the paper and then you do an implementation so for fractal we actually started the implementation in parallel to like working out the details of the idea does it is that how most of these papers are actually written like do you often need to be seeing it in action in a weird way or like putting the pieces together in order to actually know if you're on the right path that really depends on what you're aiming to say so it's perfectly reasonable to put out a paper with no implementation if what you're trying to say is something kind of you know

cryptographic and theoretical here we wanted to demonstrate the feasibility of something on a real computer and to give numbers and kind of we we had some illness to compare to some you know competing works and to do that you really need to have an implementation when you publish I like that this narc world has has moved to kind more of this tone of having code being able to run it maybe it's because it's a more competitive space I don't know but there's many areas of academia where if there is anything called wish it's like not usable code at all it's not not intended to be used just like some throwaway Python code or whatever to prove that it's possible to write an

implementation so it's nice that like there exists code and and it's actually like runnable what are you guys what are you like what do you want to see happen with fractal do you see fractal as sort of like a piece of research to be worked on and pushed forward with the next sort of protocol proposal or do you want to see this be built for real like what yeah what would you envision for this well from my perspective I think that fractal is not the end of the road for this type of protocol I am hoping that somebody possibly us or someone else

will build kind of a fractal Plus that improves it from the parameters and fractal and so yeah I think that where fractal sits is that it demonstrates that something is possible but there is a lot of scope to improve upon it I'm just wondering if it's like should we be looking at Alessandro's research team for future iterations of this or could it be found anywhere so I think in terms of the expertise that exists I think Alessandra has amassed a fair amount of it and in the content of the people who would be able to improve upon fractal a lot of them work with Alessandra directly and but I mean oh there are there are plenty of talented people in

the space and it could come from any of them I suppose fractal in particular because it's a little bit more like of a distant research direction in particular because we're kind of focusing on the post quantum aspect then I would imagine that it's more likely to come from within academia than from industry it's sort of unclear so far how the constants are gonna compare between sort of fractal or start constructions and these parent based constructions and you know what their rate of development on all in both research and actual code writing the frontier change is so quick so I think it'll be a couple years if we actually have a definite answer like which

approach gets us faster or more production-ready cook would you say there's a lot of borrowing between different departments from these different schools because like I mean right now when I was over NSF there was clearly like there's the Dan Bonet crew and then there's the Berkeley crew and then there's the halo people and then there's the start folks and the Technion folks and like would you say that there's like a ton of overlap or cross kind of pollination between these groups I know that everybody knows each other and I'm sure that there's definite sharing of ideas so to some extent there is a a theme that kind of each group works on and they're distinct in that

but there is a lot of cross-pollination I mean I I've worked a lot with with Le Pen's asan and you know we are working at the moment with Ben degrees from Stanford so I think there's definitely not isolated but there is sort of a somehow a culture in these things that like different groups work on different things yeah is it competitive at all this is like this time Berkeley is gonna have like we're you gonna have the better paper yeah go bad so maybe a little bit in a friendly sort of wait but thankfully the things that we work

on it Oakley and the things that are worked on at Stanford sort of complementary to each other so it actually you know we're not working on exactly the same stuff and I think this is helpful because this means that we can you know have a lot of collaboration without worrying about stepping on each other's toes nice so I do wonder I've become a little bit curious at times about like the motivation of some of the people that work on these technologies and these protocols like do you feel I'm kind of asking both of you do you feel that you come to this because the science is neat because the math is challenging or are there some other kind of visions you see for these types of protocols or some like maybe

societal impacts that influence you and maybe encourage you to work on it so perhaps dev and I have different answers yeah so I personally as I alluded to at the beginning I'm really interested in this because of the kind of mathematical implications because of their relations to theoretical computer science and there's like this idea that we're exploring the notion of proof which is very exciting I also like find it very fulfilling to work on these problems and you know that they're mathematically interesting and the deep and kind of the practical applications are sort of an icing on the cake

all right you I got started with this stuff and I find it fun because I get to do a lots of like fun math but I think there's a lot of things I find fun and have fun math the reason I think either special is that they have these sort of meaningful applications all over the place like I think it's a society where we use fluidity proofs everywhere is much better than one where we have trust faked in cool so to wrap up I'm curious what's next for you guys this paper has been published what are you working on now and in the short term foreseeable future well one thing we work on is a cleaning up the code for fractal-like we've released the pre-processing barians code and now we're cleaning up the recursion code then we'll do a final

release with that then another thing we started looking into is and now we have recursion how can we sort of bootstrap off recursion to further improve these starts what else can we do then just saying they have a recursive snark can we actually use the fact that we can encourage to improve these asymptotics or constants this is something that's like evidence from PCP is like the famous PCP theorem is achieved by doing a similar recursion of two different types of PCP so maybe something similar can hold first starts yeah so the what I'm working on at the moment and thinking about the cryptographic implications of snugs there's a lot of interesting kind of cryptographic foundations behind stocks for example

there was a paper in 2011 that said that essentially stocks are impossible people built them anyway and there's a lot of like interesting questions about kind of what is the limits of provable security force nots and also for one-round arguments which is you know the thing kind of above snarks like you have a little bit of interaction but not very much these questions are kind of vary in some sense they're not particularly practical because no matter what the answer is to them people will continue doing the same thing in the real world like we believe that all of these constructions are secure and we have no evidence to think otherwise but somehow there is in the in the underlying kind

of cryptographic theory that there are some holes and there is a there are a lot of things that we don't know and so I'm interested in trying to sort of plug some of these gaps really cool well good luck on that like and thank you so much for coming on the show and helping us get a little bit more of a sense for fractal and also helping us with some of these definitions that you've just given us these terms we've been using we've been hearing the IOP use the a hp's I think it was really nice to clarify that yeah thank you very much thank you Thanks well and to our listeners thanks for listening thank