Episode 329 - Building Cryptographic Proofs from Hash Functions with Alessandro Chiesa & Eylon Yogev

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 Nico and I chat with alisandra kza associate professor at epfl and Elon yogev professor of computer science at Baran University about a new book they've recently published called building cryptographic proofs from hash functions the book is a

comprehensive and rigorous exploration of cryptographic proof constructions using ideal hash functions also known as random oracles they cover notable constructions of snars that is succinct non-interactive arguments and something I didn't get to mention in this episode Alesandra kza is known for having formalized important snark Concepts such as the concept of iops during his work at Berkeley and this was one of the first steps to make ZK systems more modular this step actually resulted in an explosion of innovation and breakthroughs in improving ZK systems I just wanted to highlight why these attempts to standardize parts of snarks or snarks can be deeply impactful I realized at the end of the episode that we hadn't quite highlighted that

correctly uh even though actually in a previous episode episode 200 I think we did go deeper into it now before we kick off I want to let you know about an upcoming event that may be relevant for you that is ZK hack Montreal happening August 9th through 11th 2024 in case you don't know ZK hack is another project that I'm involved in it's a hub for ZK learning which is very much Community Driven and as part of that we produce IRL ZK focused hackathons that bring together builders in the space to hack on ZK tools the next of these is ZK hack and that's bringing the event to my hometown ZK hack Montreal will be happening as mentioned on August 9th through 11th and it promises to be a

very special one being the first time we host our hackathon Series in North America applications are open and I hope you'll join us we have some amazing judges and partners lined up so keep an eye on ZK montreal. comom the website for the event or the ZK Haack Twitter account for more info about it I've added the link in the show notes as well you can apply directly from there now t will share a little bit about this week's sponsors Alo is a new layer one blockchain that achieves the programmability of ethereum the privacy of zcash and the scalability of a rollup driven by a mission for a truly secure internet Alo has interwoven zero knowledge proofs into every facet of their stack resulting in a vertically integrated layer one blockchain that's

unparalleled in its approach Alo is ZK by Design dive into their programming language Leo and see what permissionless development looks like offering boundless opportunities for developers and innovators to build ZK apps this is an invitation to be part of a transformational ZK Journey dive deeper and discover more about Alo at al.org namada is the shielded asset Hub rewarding you to protect the multi-chain built to give you full control over sharing your personal information namada brings data protection to existing assets applications and networks namada ends the era of transparency by default enabling shielded transfers and shielded cross-chain actions to protect your data even when interacting with transparent

chains namata also introduces a novel shielding rewards system by holding your assets in a shielded set you help strengthen nada's data protection guarantees and collect n rewards in return namada will initially support IBC and ethereum based assets but will ultimately serve as a single- shielded hub for all assets across the multichain learn more and follow namada mainnet launch at n.net and now here's our episode [Music] so today Nico and I are chatting with alesandro kza associate professor at epfl who's running a group there called the laboratory for computation security and Elon yogev professor in the computer science department at Baran University

Welcome both of you to the show thank you thank you hey Nico hi Anna hi Alexandro hi Alon so I want to start with you alesandro it's wonderful to have you back on the show this is your at least Le third time here um I did go back and listen a little bit to our past episode and it was episode 200 so it was quite a special one you came on for that and in that what we talked about was education in the snark world I know that talking to you at that time you highlighted that because things had been moving so fast it was really hard to kind of like completely define any part of it at that time um but also had

already voiced to me around then that you were you had this ambition to write a book and that's really what we're going to be talking about primarily today but I don't know if you can just share with us a little bit of what's happened in that time since episode 200 which by the way was like October 2021 yeah so back then I was uh already uh discussing for some time the idea of a pedagogical effort around snars with alone we had been working already on uh SAR related topics for a number of years and uh while it is true that the snar Escape has been evolving very fast I think it became clear at some point in 2021 that pieces of it were perhaps ripe

for systematization and Exposition in a more accessible way that is not just some quickly put together monograph or research papers and uh we started uh yeah now it's over three almost three years ago an effort to Define what would be like a reasonable scope because uh an effort of a book uh if you are too ambitious you just never get to the end of it and nobody can benefit from it so the first uh thoughts that we had in discussions were okay where do we draw the line for what to put in the book and what keep outside of it and how do we stay true to these lines nice um something I didn't just mention too and I think folks maybe

were familiar with a lot of your previous work before joining epfl you were at Berkeley and you were the professor I mean you were puses Howards there's like a lot of people who've come through this show and who are now kind of top Engineers top Founders in the space and then you made the move to epfl I think when we met you hadn't yet joined epfl I'm not sure but what's it like what's the change like I mean you're you're now you know a professor in a new space you're right I joined epfl in uh in September 2021 so that was shortly after we last uh talked yeah and uh it's been a wonderfully smooth transition of course there's been some

uh work to rebuild a group and a pipeline and uh get used to the new kind of hiring workflow for PhD students and postdocs but it's been easy and pleasant was very happy about uh seeing this and actually I can say that tfl is a wonderful place and uh I'm kind of at least as happy as I was that you see Berkeley in terms of uh the strength of students uh of colleagues the research environment and on top of that I'm closer you know to home so overall I'm happy about that nice and the research I guess has been continuing very well reflecting the overall happiness of doing research there can you share a little bit about the new group like the

laboratory for computation security Is this different from the lab that you were running before it does it have a similar theme and spirit it's a just a continuation the only difference is that at tpfl for bureaucratic reasons you are required to uh give a name and enshrine your group behind some label okay and uh this was a I think sufficiently nice and interesting label that I found but otherwise it is the the kind of the usual life of a professor you you hire PhD students you advise them for X years until the graduate and you keep recruiting you know every year whichever strong students you're able to attract

and it continues this way just in a new place okay great Elon I want to hear a little bit from you this is the first time you come on the show can you share a little bit about your work and what led you to also work on this book yeah hi it's great to be on the show I've been studying interactive proofs and snarks and other friends I guess for the past decade or so and uh in general being in field of cryptography for more than that I attended the semester at the Simons Institute in Berkeley where I kind of already knew Alexandro from before but you know I had an opportunity to really spend some time there and uh talk to him and

connect and uh we kind of started talking about you know what what open problems are there in this area uh if I remember correctly we already started writing papers like during the semester this was right before the pandemic began so after the semester I kind of joined Boston University but then the pandemic started and I kind of physically came back to Israel MH and uh I guess it was kind of crazy times like everybody was at home and me and Alia just you know we established this connection and this

base of questions that we wanted to pursue and I think for the entire time of the pandemic we kind of talked I would say every day and I'm not exaggerating I'm including holidays Saturdays and stuff like that what were you talking about just a research research like just every day either what we discovered yesterday coming with new conclusions what we're going to you know focus on on tomorrow first for me it was great cuz you know the pandemic wasn't fun yeah and so that really kept me uh going and uh second of all we had like I don't know a lot of luck and we kind of

managed to publish a lot of papers in that time and at some point we kind of noticing that you know what else can we do except write new papers and uh how can we you know expand this knowledge to other people and at some point we started talk about potentially writing a book I admit it seemed like a dream like you know what do you mean write a book that's like a you know a multi-year effort right it's not like a paper which you know usually is within one year you finish a paper okay this is like a multi-year project writing a book unclear exactly as Al said what is the

scope and what we should write about and I'm kind of very excited and happy that we're here today you know fast forward after this actually have the book online and I'm just so pleased with it also yeah I know that you have also produced a lot of research work before we jump into the book I just want to just highlight a few of these things like you talk about some of the work you were doing over the pandemic are there any key works that you would highlight that came out of that time um that's a good question that's it's hard to choose between your children but in the context of interactive proofs okay because I also did I have a lot of work like in very very different

let's say cryptographic areas but in the context of interactive proofs and and their knowledge proofs I have one paper that I really like where we kind of studied what is the weakest assumption possible to construct a a interactive sucin interactive argument and so kind of from this What's called the Kean result we know how to do this from a collision of distant hash and it only needs three rounds three messages and uh if the question if we can do it from oneway function is still a completely open problem what we kind of did we established a new primitive called the multicollision assistant hash this is a weaker primitive than a collision

assistant hash but a longer primitive than oneway function It's A Primitive where maybe it's very easy to find collisions but it's hard to find a ky collisions meaning K elements that all hasch to the same value and we build a suin argument from this weer primitive and kind of the main obstacle is of course you cannot do mer trees because if you do a mer Tre actually there's like millions of collisions and somehow you have to overcome this one other example that I want to give is the interactive proofs for social graphs so in this context you have aover theover is like a strong entity like as always but the verifier now is not just uh one computation device but

like a distributed Network okay so the verifier is like all Twitter users let's say these are the verifier and theover is you know Elon Musk okay or just Twitter itself and the Twitter wants to prove you know something about their Network oh we have this and this monthly active users we have you know some other health measures of the of the network proving that they're you know uh maintaining the health of the network and the users they're not you know biasing users to see specific news and and so on so they want to give some proof on the network H but the network is of course huge and kind of we want the community

to uh to verify this proof and this is this is what we did in that paper interesting is that the community as a whole or each individual of the community as a whole as a whole okay yeah otherwise we're back to the sort of one one verifier model okay okay so like individual user of Twitter cannot very verify a claim about the entire NE because like it never sees the it cannot even like the input here is so huge it's not not defined for specific user but it just the input is distributed among all users one other paper that I do want to just highlight here also for our listeners is Stir because we just recently had your other two co-writers on the show and so it was the four of

you who put together the stir work I think we might get a chance to come back to this later in the episode because we definitely want to dig into like where where that work may lead but yeah I just want to sort of mention that for anyone listening why don't we start with just the topic of the book what is this book about and kind of what part of the stack are you focused on Our intention with the book was to systematize and digest a piece of the snark Escape in detail so we aimed for comprehensiveness rigor and depth at the expense of breadth uh that is distinct goal from a survey or a overview of the whole landscape right and why because we wanted to empower

other people uh not in direct contact with us uh whether they are PhD students uh ambitious undergraduate students or just practitioners in Industry to really understand and be able to manipulate and apply in detail security definitions and the security analysis of constructions that are used in practice and for that we need to in some way cut ourselves out of the loop so they should be able to do that without access to alone without access to alandro all right and for that we we have to provide a resource that is sufficiently comprehensive and precise

it communicate the things are in our heads and uh not in the research literature which is fragmented and incomplete and usually written in a hurry I have to say this is something that I myself have been struggling with a lot finding the right definitions because there are so many variants of the same definitions because these things do change slightly over time as we learn about them so to me this is a a gold mine of Precision essentially I mean even in the term that you're using the snar like this might be something we want to just kind of highlight as well so you don't say snark St I mean you you may say it later but like the the term that you're using to kind of Define this overall class is snar so I'm wondering if we should just kind of redefine that for for The Listener as well sure I was

merely highlighting the succinctness of it uh the K at the end would have been highlighting the knowledge and ZK in front would have been highlighting the zero knowledge part I would say maybe the the knowledge soundness part the K at the end almost always is needed though the Z part only sometimes but what makes it most interesting of course is the succinctness to begin with but we could have also said snark Escape maybe without ZK without necessarily highlighting it I see I see so we wanted to cut ourselves out of the the loop and enable others to um kind of have access to full details and definitions and elen and I having written a number of papers uh both together and you know separately on these topics we have seen a lot of

variations a lot of different notation a lot of different uh strengths of definitions and so and also we were aware of which parts of literature are in complete and lacking so we had a good view through all of this experience how to select the right level of strength of definitions to not make them overly cumbersome while on the other hand make them sufficiently strong to be relevant to practice and uh now delineate a particular subset with the snar snar scape ripe for a digestion systematization and specifically uh we focused on the setting of snars that are built from hash functions okay

specifically cryptographic hash functions these are hash functions that are modeled as random oracles maybe a let alone highlight why this is a particularly interesting and exciting uh subset of snogs yeah so the book is about you know how to build snog from a hash function we curved out a part of the landscape of snogs that is kind of stable today so what we want from this book so the general landscape of snogs is kind of changing every year rapidly but hash based snogs and the part that we focus the book on come to a point where we feel that it's very stable and it's going to remain very similar in the next 10 maybe even 15 100

years can you share an example of one of these hash based snarks are we talking Starks mostly here or things like Starks yeah Starks and things like stars is an example great okay these are snugs that are um usually built from an IOP and then compiled to a snar or snar using a transformation that is based on solely on hash functions got it no bilinear groups or other assumptions and actually in one of our papers you know with Al what we showed is kind of that you can take an IOP you can compile it and get a

snark in the random Oracle model and what we showed is that actually any snark in the random Oracle model you kind of can apply a reverse transformation so you can take that snar and you can extract back an IOP so what happened is we we used to have What's called the mikali transformation which build a PCP and compile it to a snar a PCP is just a one round IOP that's all and then we kind of introduced the notion of iops and said oh now let's just compile iops multi round pcps okay into snugs why we because we can do that because anyway we can compress rounds using What's called the F transformation so one could say

okay you know we build snugs you know we build hash B snugs first from pcps then we build them from iops no let's wait 10 or 20 years you know and we'll build them from some other three letters okay and kind of our answer is no any snark in the Rome we can distill back an IOP that has like very similar corresponding parameters and so we know that you know this is what you need you know they're necessary insufficient so this is like some fix point of hash based snogs and uh and thus of course up to smaller order optimizations that that might come kind of this is now looks

like something in stone and uh and we should write a book about it I want to ask what is not a hash-based snar like what kinds of systems that we've maybe heard about on the show would be excluded from this kind of model like would something like plon still work in here are pairing based systems still included in this yeah anything that uses algebra so for example bulletproofspeaking.com so you can have ltis based snarks again

you have a different type of structure it's uh at the intersection of uh number Theory and geometry where you talk about the length of uh integer kind of combinations of uh uh kind of vectors over certain rings so all of these have some structure that comes that come along with the snark and you exploit it on the one hand for sometimes very often for better efficiency compared to the case of uh um hash Bas snarks maybe smaller proof size most notably right in particular the smallest argument sizes for snarks are known from bilinear Maps Okay but then the the structure that comes along and helps you with this or that

parameter sometimes also back kind of backfires and makes the underlying assumptions more exposed so in particular for instance the Assumption assumptions that underly a bullet proofs and uh pairing based snarks will fall eventually if a large scale quantum computer will be built um the same we don't know whether it's the case for laes or not but nevertheless the structure of latices makes it quite complicated and error prone to specifically set parameters in practice on the other hand if you don't rely on any structure whatsoever you just use on exactly the lack of structure an ideal hash function okay then in this case you kind of put

yourself in this almost information theoretic setting it's almost no longer cryptography and here in this Ideal World you can quantify security very precisely uh with explicit constants explicit security reductions and you can really understand in extreme level of detail what's happening there and in the real world you make theistic uh step an assumption you conjecture that things like shat 56 and KATU uh for all we know essentially behave like an ideal hash function m yeah you have an expression that I really loved in the book which is the pure ROM we work in the random Oracle model and just that nothing else that's right uh we should highlight that

the random Oracle does play a essential role in many snark constructions in addition to other structure so for example in the non-interactive version of bulletproofspeaking.com and in a subsequent step you rely on the random Oracle model to compile this interactive protocol into a non-interactive one and at the end you rely on both the structure of cic groups and the help from the random Oracle whereas what we focus on in the book is the help that comes from the random Oracle and only the help of the random Oracle that's it so it's kind of use and only use hash functions nice can we

Define random Oracle model I know you've just said it a couple times but if if we are talking pure random Oracle model what is that so we can so you should think of a random function that you know is just is sampled and sits in the sky so this is a function that for every input X you sample a truly random output y you do this for all pairs so for every input X you sample something completely random to just to represent you know this mapping this is like an exponential size mapping so no party of the P or verifier can hold this mapping so you just assume that this function appears in the sky and the p and verifier just

have Oracle access to this function so what they can do they cannot know the entire function f okay if we call it f what they can do they can send to the sky this some query X and they get back the answer F ofx equal Y and what we do we measure how many queries they perform and so we want constructions to be efficient meaning for example that the verifier is just going to perform a few queries to this function in the sky and when we want security then we say oh we have a cheating P we have some adversary and we're only bounding the adversary by the number of queries it performs to the random

Oracle other than that the the adversary is actually computationally unbounded so he he can you know factor numbers he can break anything okay he can compute discret logs the only thing he cannot do is you know he's limited there's some parameter t for the number of queries he performs and he can perform any queries that he want Even adaptively and that's it so in that sense really the proof that we get in the random Oracle model is really information theoretic it's a mathematical proof has relies on no assumptions at all no cryptog the only crypto part comes when you say oh I don't have a totally random

function in the sky right like who does MH and uh so you have to choose some concrete hash function for example sh to 56 ketu and and all these and you're saying I'm going to humanistically replace the construction I have where every time they do a query to this random Oracle they're just going to do a query to the hash function that I chose and to in the to link it to kind of real world things a stark is an example of a succinct on interactive argument in the roral model that has been heuristically instantiated using samash function okay so the security analysis of a stark happens and only happens in the random

oracal model and subsequently you do this suristic step described by Alon how big of a leap of faith is this well It's a Wonderful question we know it is a leap of faith because there are constructions that are secure in the random Oracle model but are definitely not secure no matter which H function you prove MH now these constructions are set up to fail they're kind of artificially assembled but for the constructions that we know and love like uh the M Construction the F Shir transformation the BCS construction which is M extended multiple rounds for iops we are not aware of any such

pathologies uh and so but but it is a leap of faith uh and uh nevertheless in terms of things that can fail um the random Oracle is used in a similar ways in many other places of cryptography that is deployed in the real world already for many years just not about snars for example the Fiat Shamir parad is used Elsewhere for reasons having nothing to do with Starks okay and people are very comfortable with that there so we're not really introducing that much that is new in practice okay a lot of signature schemes also rely on run right so yeah yeah and no one flinches I wanted to highlight before maybe we move on uh so we we we highlighted so far that the random

Oracle model is this uh uh setting with no structure that it is uh rip for systematization but there are other very compelling and uh exciting properties of the random moral model so one of them is deployability every sucin interactive argument in practice must have a setup but the question is what kind of setup in the case of random Oracle choosing the hash function is the setup so that is a very easy setup to have so a system declaring to its users guys are instantiation of the random orle is going to be shat 56 that is the action

of having a setup you don't need any complicated cryptographic ceremonies to create the setup choosing the hash function is the setup and that's super easy to do in practice so they're very nice from the perspective deployability mhm another wonderful um property is the fact that these constructions like the micali construction in the Run memoral model are known to be secure even if the adversary is a Quantum algorithm namely queries the random Oracle in superposition this is known as a Quantum random oracal model and we have proof that uh both for example constructions of starks and similar things are secure

in Quantum random models so not only this area of the snar Escape is ripe for systematization but after being systematized it has a pretty good chance to remain relevant and secure for potentially a very very very long time so that's something I think that as a scientists we feel pretty excited about because we you know we make this effort multi-year effort to systematize digest and present useful constructions that are useful today but in our view are going to be useful potentially when we are no longer around period And so that is I think you know some some sort of impact that has a high high chance of transcending you know our own you know

lifespan right which may not be true of some constructions that for example are prequantum I have another comment on hash based snugs so even if you're kind of you know you want The Snug to be very very succin very small and so you're willing to use bilinear maps you are willing to be not post Quantum secure maybe you're willing to do a trusted setup so you can use other snugs that are you know much smaller bulletproof C 16 and and others even in that setting what's happening today there's kind of a big race of you know optimizing the per side so you want to create a proof as

fast as possible you want it to be like very like near real time and uh one way to do that if if you just use like bilinear maps for the entire construction typically this tends to to be slight slightly slower and the hash Bas snogs because they use this very easy primitive such as you know ketchup or stuff like that they have the potential to be very very fast however you get something that is not small okay relatively bigger might be you know 50 kilobytes not 1 kilobyte so in practice uh something that is commonly done is that first you create a proof very very

quickly that might be 50 or 100 kilobytes and then you recursively give a proof that you know a poof okay so you do recursive recursive composition and for the second scheme you use something that is small so you start with something that is fast and big and then compose it with something that is slow but small and then overall you get something that is fast and small so even when you are interested in something small and not hash based in many cases the first step is actually a hash-based proving system the thing is you you just talked about alesandro this like postquantum the queries and I think

you said super Posta how did you pronounce that superposition superposition does that mean like unlimited queries you talked a bit about like there's a limit to the number of queries that a malicious actor could make I was kind of curious how that's chosen and when you say this queries in superposition does that mean unlimited what does that actually mean in that context yes so in the random Oracle model you consider as Alon mentioned earlier adversaries that make at most some number of queries to the random morical for example you're going to set this bound T to be I don't know 2 to the 128 okay in the quantum case an algorithm has an additional power it can uh not just ask hey what's the answer to

query X and the Oracle answers y mhm but it can ask what is called a superposition query so indeed it can ask many many X's all at once with different amplitudes and it will receive a corresponding answer with corresponding amplitudes this is different from asking many many queries at the same time because it it only gets as an answer a superposition of the answers and then it has to measure and it will only get one answer sampled according to the amplitudes of the answer nevertheless it is a strictly more General type of query and in the quantum random Oracle model you consider Quantum adversaries that

are allowed to make up to T superposition queries so there is still a resource bound except that now the type of query is slightly richer and it requires different tools and different analysis and potentially something that was Secure in the random orle model may not be secure in a quantum run model and there are separations including unconditional ones in particular there exists a snar that is secure in the random Oracle model just not in the quantum random Oracle model fortunately that snar again it's a kind of a pathological and it's artificially set up to fail it's nontrivial to set it up to fail H but constructions that we have that are not pathological like the

mikali construction the BCS construction one can show that uh even T superposition queries are not enough to break it got it thanks for that clarification Nico I know you about to ask another question please go ahead yes I was going to talk about or ask you to talk about the contents of the book which I was saying is sort of f so this idea of replacing interaction with a verifier by random Oracle and Merle trees or mirle commitments which allows you to take a long message and have something small instead and essentially it's the book goes through different types of proof and using these tools right to make snorgs yeah so the book starts with you know introduction definitions as as you said this is

already like a very non-al step to set down definitions absolutely um that we all agree on we all like H and are actually strong enough to serve you know practical purposes once again thank you so much for these because it's again a gold mine yeah um it also has many like small lemas that serve as like examples for the reader to kind of exercise the definitions and so which definitions imply what other definitions and so on so after we settled you know the the Common Ground we kind of start building things and the first thing we build is this F transformation we have a version for Sigma protocols these are just three

message protocols this is like the most more common and easier one to prove and then we go and Advance it to F for multi round protocols which is also like required in many settings for example the bulletproof proof systems actually needs it and this becomes much more uh complicated actually while WR while writing the book we kind of observe that there's a big difference between a few different flavors of the F chamir transformation so when you do fiir for multi round there's two versions where we call a slow version and a fast version in the slow version every time you feir around you kind of

just put in all the history all the you know all the transcript up to that round inside the F query and that is very secure of course and and much easier to analyze in practice that is slower okay than the fast fear CH transformation where instead of putting the entire transcript in the F chir query you every time you just hash this the transcript and you create this hash chain where you just Tagle a hash of the last transcript and only this you put inside so when the number of rounds become slightly bigger this is actually you know a crucial optimization and this optimized version

of the F Shamir is actually much more complicated to precisely analyze so throughout the book The bounds that we give are are very precise so meant to serve you know they're meant to help PR practitioners set parameters in practice so losing you know seven bits of security is not something that we could just you know allow us to do an approve H even if it kind of helps helps the argument we kind of wanted to be precise we lost a bit of security only when we had to in many parts actually even for the merries in many parts we lose some bits of security

and it's kind of remains an open problem if that is necessary or not so not all losses are are clear but in any place that we could you know find an argument to get something squeeze out a few more bits you know in practice that could be a lot so we really aimed for that I do want to add to your point of this hashchain optimization of fat Mir is a lot harder to analyze it's also a lot harder to implement and it's been a recurring source of bugs in implementations and there are often like write ups I think every year every year and a half coming out saying like hey some people forgot to Hash the final round or um some people weren't hashing the group description or stuff like that so Elon talked about the multi fet

Shamir but as some of you may be familiar with multi round fat Shamir is only about removing interaction from a protocol Su arguments need a second different in some sense orthogonal ingredient something that is going to take a long string like a PCP or an IOP and squeeze it down into a short commitment and that is this wonderful data structure of Merkel trees or Merkel commitments these are short commitments to Long strings that enable you to subsequently open a small number of locations of these long strings like the queried locations right and certify that

the values you're open to the verifier are indeed consistent with the previously uh given uh so-called Merkel rout okay the commitment to the long string and wonderfully these meracle trees can be constructed just from hash functions specifically around the morle right and uh so the next part of the book goes into extreme detail uh articulating the properties of Miracle commitment schemes in the random Oracle model so talking about uh how they are binding but also how they are so-called extractable which means that uh when an adversary gives you a commitment you can already tell from the behavior of the adversary what are all the possible

answers it can give you and these answers are kind of unique determined by the the commitment also how you can make them hiding so that the commitment and the corresponding openings later don't reveal anything other than what is revealed to you this is important for zero knowledge snarks so we have a whole chapter that uh it's in the first time actually where in the literature we we take and analyze extreme detail the the Standalone properties of the commitment scheme which I as I will get to in a moment we use in later parts of the book to construct sucin arguments so in the introduction the of the book you you do mention that you want to systematize and actually prove results that are sometimes forgotten or inexistent from

the literature was this one of the cases where result was missing in this Cas it wasn't necessarily missing it was uh perorally proved for example in the BCS paper uh by Alon myself and Nick Spooner where we introduced iops and showed how to construct a snarks uh in the random Oracle model from iops we did have some uh statements about Merkel trees in the random Oracle model but you know they weren't very ergonomic um usable they were particularly tailored to to that one proof that we were that we needed in that paper to prove BCS secure H but in the book we had higher aspirations to

provide uh uh properties that uh could simultaneously serve multiple different uh constructions and potentially even beyond the world of snarks right because Merkel trees are used in a number of other settings not just snarks and uh so we we had higher aspirations for a easy to articulate uh intui and flexible definitions that could be applied in this or that setting without having to reopen up and analyze mer trees which which El I can tell you is very painful and Annoying It's very technical uh everything is kind of intuitive at the end but really making precise statements and being clear and comprehensive does involve a lot of

attention to detail I would just give a very small example for mle trees let's say for hiding you kind of it's not too hard to show that you know one node of the tree is hiding and has some small statistical error and then when you want to conclude about the entire tree you kind of Union bound over the entire tree and uh you know you accumulate all the errors of all the nodes in the tree and uh that works that is kind of common in many papers and is kind of you know not optimized for practice and if you want to not to lose this huge Factor where

the tree can be kind of huge right could be like you know billions of of nodes in the tree you prefer a slightly you know smarter analysis that only pays let's say according to the depth of the tree and uh these are things that we kind of put a lot of effort into so now that we have this tool what else can we build I think there's a few more chapters in the book right after Miracle commitments yeah after the um now that we have in hand Miracle commitment schemes in the random Miracle model and we separately understand that the F transformation the first thing that we do is we analyze this wonderful beautiful construction the mikali snark this was the first

snark uh ever constructed how does it work you commit to a PCP you get a miracle route you stick it back into the random Oracle fat Shamir style that gives you Randomness to run in the PR's head the randomness the PCP verifier which determines certain locations which tells you which parts of the PCP to reveal and to certify via so-called authentication paths or the Merkel tree and so the first snark that we analyze in the book is the M Construction we give uh you know very careful analysis for soundness knowledge soundness and zero knowledge and this is kind of the first real snark in the book and to some extent this is kind of the

the beautiful and thing beautiful construction that you would want to deploy sadly we do not have practically efficient pcps okay and so this motivates uh the next chapter which deals with constructing snarks from multi-round pcps also known as interactive Oracle proofs iops luckily iops we actually do have you know a long line of research now of more and more practical schemes so these things are very very practical very very fast and uh becoming even you know faster every day and what you do you want to simulate the M

Construction H just you want to do this for every round so you have the first round of the IOP you're going to run the miracle tree compress it to a root you're going to put this root in the r the morle and get the randomness of the verifier for the next round then you can the PO in his head can feed itself this Randomness and derive the second message of the IOP and in the second message he compresses this again gets a root puts it in the fiir query wait here you know bugs happen so when you put it in the F query you should put also the first root right so you should put in the entire history or a hash of the entire history okay and how to do this properly is a

you know well defined in the book so you can take a look there and you continue to do this for every round until you finish and eventually when you're done you see all the queries that the verifier wants to do for all the rounds and then you open all of these together and everything you send to the verifier this is you know the entire proof so this is almost the last part of the book I just want to say something before we move on you could ask why do we even write a part of the book on the mikali construction so the mikali construction is like a simpler version of the IOP one

okay we have when is that from it's older right it's a like 96 very much older okay we have no practical constructions of pcps even to date okay not not just back then and so potentially we could have you know removed this part from the book however it serves I think two main purposes first it's a extremely good warmup to the BCS construction okay so if you read that part you kind of you know then you only have to read the Delta the difference to the IOP based one and that's good because the entire construction the BCS transformation you know relying on IOP is actually hard it is complicated it's hard and so it's

excellent to have you know a warm up second there's another purpose if you're thinking of some improvement you know you have some idea to optimize things okay which you know happened to me Ali in many cases and you want to test them you want to see if the proof Works kind of it's almost impossible to do it directly for iops so the starting point would would be oh let's just imagine that our IOP has one one round one message okay which is the mikali transformation and do it there and then there's kind of a lot of technical work to actually make it work for many rounds so this is kind of a crucial you know stepping stone toward there what you

really want the the BCS construction is kind of the climax of uh the kind of the technical buildup that incorporates you know all of the features and ideas ER into a protocol that is deployed in practice and we want people to be able to understand and reason about we also added another part of the book that uh is not about other constructions is more about uh in some sense understanding better what happened for example how do you set parameters you know what does it even mean to have a a security level uh you of 128 bits of security what does that mean turns out that cryptographers have not been great at uh formalizing what this means

precisely so we do a rather systematic and uh comprehensive discussion that uh puts forward some precise definitions for the case of arguments and says look these are reasonable definitions you could use here's how you use them here here is how you set parameters we go through actual examples of numbers that take the theorems that we prove and shows how to set security levels according to this or that definition and show the computations that a practitioner may have to do to determine what is the output size of the random Oracle what is the salt size to achieve a certain level of Z knowledge what is the soundness error that you need for the underlying PCP for example so we go

through all of this and we discuss other things that are important in practice for example Merkel trees are rarely used as out of the box for example you when you have many locations that you reveal to the verifier you try to prune away redundant information but this uh tree pruning actually changes the construction it means that potentially the security has changed and so we we explain why it's okay it's fine we also put on more precise terms what what is what is this optimization of pruning and what guarantees does it give you efficiency wise and we are able for the first time to articulate this in precise terms um and then we talked about we

talk about other maybe more technical uh matters that I'm not sure this is the best venue to get into but um briefly when you do multi round fet Shamir the underlying interactive protocol has to be particularly secure to allow for f Shamir to happen and that is because after F Shamir an adversary can replay the protocol in its head and attack it multiple times with different kind of continuations which means that the original protocol that you started from should have been able to withstand that to begin with and this is something known as state restoration soundness it's a notion of soundness that was introduced in the BCS paper with this BCS construction and pointing out that

look you really need the IOP to be State dation sound but it's not a very convenient notion to use in practice you typically prove that Protocols of Interest satisfy stronger Notions of soundness than that for example R around soundness and so in the in the book we explain how stronger Notions such as round around soundness special soundness imply State duration soundness so you don't have to think about it ever again some sense right so for for Protocols of Interest all you really need to do is just prove rown soundness interesting so I guess one thing to say about the book is if you're a practitioner and you've deployed hash based snark and your construction somewhat is different from

what is described in the book please double check your work cuz probably something is off but moving sort of almost beyond the scope of the book iops are often applied with also um error correcting codes and then we do a test of proximity to these codes and this seems to be sort of ubiquitous in most of the efficient snars we've deployed is this something that you considered to include in the book I know you mentioned it in stir as well you have compilers for these types of proofs yeah is this something you've considered in the book yeah so the book is kind of about the part of the literature that is stable so the book is saying okay you know you give me an IOP you give me a PCP or you

give me an interactive wolf and I will show you how to compile them to a snar a snar okay with zero knowledge without zero knowledge and all these variants um what it doesn't describe it does a a small survey but it doesn't go into technical details of how to construct these pcps or iops and how to construct this proximity tests and all of that H so first the book is like a big enough project as is without this part okay is first second that part we feel is very unstable so we feel that if we would let's say start today to write a book

about it it would be outdated by the time that it's published yeah and so uh I think uh that should wait maybe a few more years and then we you know potentially can consider to see you know how stable things are mhm um but with all these new developments of of new proximity tests new iops that's a shame I was looking forward to a a standardized definition of IOP of proximity so I'd like to add something to that so indeed uh we had we we drew this very strict line of you know what's in the book what's not in the book and and then we decided we are not going to open up and tell you how to cook probabalistic

proofs while that's on the one hand maybe a shame because that you know still leaves people out hun for resources for probalistic proofs there are still nevertheless good things that come out of it first the background to digest the book in its current format is rather limited like throughout the book you really need to only understand the script probability discrete math really what is just a random function there is really not even complexity theoretic background you don't need to understand the N reductions you don't need to understand finite Fields you don't need to understand polinomial you need to understand a lot of let's say fancy math or more advanced math so uh we feel like it makes the book not only a good scope

but also a pleasantly limited background to really understand what's happening in these compilers now separately of course the problem of uh teaching and spreading the word of how to cook pluralistic proofs remains but it's not something that we are indifferent to um so both L and I teach a course that does open up uh probalistic proofs and talks about uh you know how you cook these things what are the ingredients what are the fundamental paradigms and what are intuitions and uh on the one hand some fundamental ideas are stable yeah these are not the things that people necessarily use in practice but to

understand the things that are used in practice these stable concepts are the things you should understand first like linearity testing arithmetization basic results in pcps even though they're not practical understanding them will put you long ways towards what's state-of-the-art so we do have a each of us have been kind teaching a course and uh some of these resources are publicly available so for example last summer summer 2023 Alon a student um gal Arnon two of my students uh jako FY and Z Guan and myself we ran a summer school called in how you make probalistic proofs and

the resulting lectures are recorded and homeworks are available online amazing and so people can open up and we feel like maintaining and updating a course is currently a better um trade-off rather than working on a book which indeed might get uh updated a bit too fast for our taste there are other resources as well there is the wonderful survey of many different actual constructions of snarks including puristic proofs by Justin Tyler yeah it's a great book that takes in some sense an orthogonal approach to what we did it takes a breath and a lot of context for practitioners and specific

protocols that people use in practice with wonderful intuitions about you know why they're secure right so nice just a quick note to listeners if you're not aware there's a theor book club actually over in the ZK hack Discord and Ali and Elon I don't know if I mentioned this to you yet but we're very likely going to be hosting a study group about your book as well in the Z hack Discord so this will be like a group of people who are going to go through it chapter by chapter um it's not announced yet maybe by the time this this airs we will have some more info about it but if people are interested they should head over to the ZK hack Discord that's wonderful you know we'll be happy also to be kept in the loop and maybe we can find some way to help as well so far we haven't taken

any specific actions in that direction we're still in the recovery phase post post publishing exactly yeah um but the book itself is also very it's available right anyone can access it I saw it when it was shared in our groups so this is open and free for people to use right so we took this uh maybe modern approach rather than uh going straight to a publisher uh in the traditional way which we might still do some years from now for now the decision that we took was to publish the PDF and the latek source code uh and put them both online available for free under a rather permissive license so that others can not only access the PDF and uh and use

it as they c fit but also it is easy for others to file pull requests and suggestions for big and small things and and also potentially reuse a stic source code for you know whatever they need in their life just being able to reuse the definitions and the notation I think goes a long way to standardize efforts I did want to ask one thing since we said all these beautiful things that the ROM can do what can the random oracal model not do a good question so I would say first at least today it cannot give us a very very small snugs okay they are still order of magnitude bigger than snugs

based on you know bilinear maps and other assumptions second of all there's kind of a a tension between the fact that a hash based you know a random Oracle like a hash is unstructured which makes it very very secure and postquantum secure Etc but since you lack structure you cannot H construct things that are for example homomorphic so maybe you want a homomorphic commitment I want to commit to X and commit to Y and then you know create a commitment to X+ y these are typically things that uh cannot be constructed from you know unstructured assumptions so anything in that area I

would say would be a limit to the random Oracle model just another example we do not know how to construct public encryption from a random orle I would say that there's actually many things you cannot construct from a random Oracle and the fact that we can construct snugs only using a hle it's kind of magical and it just you know we're kind of Lucky we're so lucky with that we can do it that we you know we should study this part and and you know enjoy the fact that there are very important constructions that only use a you know hash functions I was also trying to hint at something we mentioned

earlier in the show which is the difficulty of doing recursive proofs Maybe of you wants to give a brief overview of what the problem is there the problem is a little bit uh circular and confusing but let's let's give it a shot okay one of the things that you do when you have a snark is sometimes you run the snark to prove computations that involve the snark own verifier this for example happens rather naturally when you have everlasting computations that you're going to prove one piece at at a time as the computation unfolds like in a blockchain for example right H so snark of snarks is a very kind of natural uh thing that you might do the unfortunately H before you heris toally instantiate the random

Oracle into the real world with a concrete hash function now you're left with you have an ideal world where now computations potentially might involve the random oral itself so for example a computation that says please do blah blah blah and then among other things run the snark verif fire on this proof that's verifier is going to say y hey you know I want to query the random Oracle and now you want to prove correct a computation that involves the random Oracle and that's something that uh we don't know how to do but in fact we provably don't know how to do precisely for the same reason that the random morle is so unstructured that queries to the random Oracle don't really fit with the techniques like error correcting codes

and property testing and things like that and you know one can actually prove that and it's a bit unfortunate and this kind of leads you into an area that is called relativization relativized snarks These are basically snarks that can prove things there are snarks that that are in an in an oracle model that can prove computations about that Oracle itself right and uh you know sadly we don't know how to do this formally but it this doesn't stop us from doing things in the real world that still seem to make sense uh because you can just say you know what actually I don't have roral anyways so whatever I'll just prove correct the computation of the actual hash function the annoying thing is that now your

security analysis is kind of interrupted in the middle you don't have an ideal primitive that is about recursion you have to first instantiate your primitive juristically and then analyze it which is a bit annoying uh nevertheless there are some ways around this despite the relativization barriers and actually in a work together with Alon and um other students and uh wonderful engineer at starkware we proposed some way to somehow kind of do some double dipping and still even though you have these relativization barriers you can still somehow say something semi-interesting about the security of uh recursive Starks let's say for example in practice

uh but it might be a bit too technical to unpack here but these are like wonderful questions and uh they're you know they they have very relevant uh practical motivations because people really do have to set par in the real world about recursive stacks for example so now that I mean this book is finished and I know you're doing ongoing work but what's next for you in terms of a part of the snark scape that you might want to formalize or standardize like is there another area that you think may become stable enough in the next I don't know 3 to 5 years that it would be worth keeping an eye on and potentially doing another book thank you for encouraging us to write another

book writing a book is a huge amount of effort it is not like writing a research paper where vaguely put writing a research paper is kind of a linear thing where we just you know if it's 40 pages you just write one by one and you're over it and a book is kind of a quadratic process where everything you do you have to go back and make sure that it you know maintain everything systemized make all the notation align and everything yeah I guess the next step would be to talk about IOP constructions and IOP proximity tests specifically low degree tests and uh and uh compiling NP language NP

complete languages uh to low degree tests so these are two areas that uh are still in development but I guess could use a lot of effort to standardize some of the parts even if you know later on things you know continue to develop it seems that we do have some themes coming back again and again uh for example the Su Che I don't know protocol okay and knowledge about polinomial and read Solomon codes so these things would be very nice to to have a book about I agree with Alan and uh indeed we have ongoing pedagogical effort efforts there particularly around these two courses

we've been teaching that not only cover something about snars from hash functions but mostly focus on constructing probabalistic proofs and there even though the exciting envelope of knowledge moves and things change there indeed there are recurring paradigms and design patterns and so a lot of the kind of classical material has been digested over the past uh you know 10 years and it's becoming you know in better and better shape in a sense that it becoming more and more accessible gone through several kind of a iterations together of lectures that illustrate these ideas also this is connected to the book right because this kind this is the missing part right and

systematization of probalistic proofs would provide the right compendium to the first book to provide a like a a unit of something that has been fully standardized and uh again will be with us for a long period of time I'd like to conclude also by mentioning that you know we're very excited that uh things that we've been working on are now exciting new technologies but what I think is even more exciting is things that we've worked on to become established technologies that is being new is not as cool as being established and old right at some point these snarks will transition from hey you know it's

so cool new and fresh of depresses deployed new capabilities to just used and boring yeah and that is the place where we would like to be in some years and to get to that place we cannot keep knowledge at the in the research literature the knowledge has to migrate and mature into canon in books and uh so that's also one of the aspirations of this effort is to move snarks in at least some of the snar Mars into just all the things that everybody understands and they're just widely taught and understood and Alexander and Alon are just no longer needed for for those M that material well you'll be

working on something else important I'm sure by that point as well very cool I want to say a big thank you to both of you for coming on the show and sharing with us a bit of the motivation that led to this work how it came together and then yeah Nico thanks for these great questions digging into the work itself thanks for thank you maybe I just say that the book is available at snugs book.org and I would also want to take this opportunity to thank our sponsors the ethereum foundation H protolabs H pel and for as well as starware who was as well as starware yes yeah thank you for having us uh we're

very happy to share our excitement about the conclusion of this uh project thanks so much both of you for being on the show it was a pleasure chatting cool and I want to say thank you to the podcast team Henrik Rachel and Tanya and to our listeners thanks for listening