ZKPodcast: Exploring VDFs with Joseph Bonneau

Transcript

welcome to zero knowledge a podcast where we explore the latest in blockchain technology and the decentralized web the show is hosted by me Anna and me Fredrik this week we dive into PDFs with Joseph Bono assistant professor at NYU we chat about what they are how they were developed and what they can be used for [Music] before we start we want to say thank you to this week sponsored trail of bits trail of bits recently released a blog

post that might be interesting to our listeners who are concerned about privacy the post is about the concept of Safe Browsing Safe Browsing claims to protect users by providing them with something called K anonymity however recent security news has highlighted some privacy concerns the trail of its blog post outlines how the Safe Browsing protocol works and describes why K anonymity is insufficient in protecting users privacy for more on their deep dive into this issue and to learn about their other work on privacy security and more visit blog trailer bits com I will be sharing the link to this post in the show notes so thank you again trail of bits and now here's our interview with Joseph Bono so today we're sitting with Joseph Bono

who is an assistant professor at NYU and was previously part of the Stanford Applied crypto group welcome to the show Joseph thanks a lot for having me and we also have Frederick with us hello hello so we're gonna have an exciting episode talking about PDFs which is an interesting topic that it's getting a lot of getting a lot of attention lately I think and definitely it in my opinion something that like I don't know enough about and feel like I should so I'm really glad to have you on the show to talk to us today great well I hope I can help so I think as we're kind of meeting for the first time I'm very curious to hear like where did you get started on this track towards

blockchain slash PDFs like where would you put the beginning of your journey oh I guess those are two different questions cuz I was interested in watchings from Wow eight nine years ago that started when I was in grad school I was a PhD student at the University of Cambridge over in the UK and I guess like a lot of research groups the Bitcoin white paper sort of crossed our desk or email list it was emailed around actually my supervisor for my PhD Ross Anderson he assigned he basically ordered me to read the white paper one day because we were supposed to we had a group meeting every Friday and research would always be presented and we were

supposed to have a speaker come one week and the speaker cancelled so the day before my supervisor said okay we need something to fill in the group meeting so why don't you read this Bitcoin paper that we've heard about so that you can tell the group what it is and I remember thinking this shouldn't be that bad it's only about a nine page paper and then it took you know hours because once I read it I wanted to go online and fill in some of the details it's it's famously a little bit vague about a lot of technical points about how Bitcoin works and then I presented at the group meeting the next day and I said you know this is a simple paper but I really think there's actually something new and interesting and tried to convince a roomful of ten or fifteen other

researchers that this was really an interesting topic I actually think most of the room rolled her eyes a bit and said well we've been hearing about digital currency and ecash for decades and nothing's ever really come of it this is probably gonna be another entrant in the graveyard eventually but I was taken so I kept working on it kind of as a side bites in my main work I finished my PhD I went to Google and was working on the security team and Bitcoin was still a hobby so it wasn't until 2014 when I went to Princeton as a postdoc where I said part of part of the goal of going to Princeton was to try and work on Bitcoin full-time as a researcher and just see is there enough here to write papers and really have an academic research career

and I guess I have to credit my supervisor at Princeton Arvind Noreen and who really said you know I think this is gonna be a big topic but a lot of academics are gonna focus on so we should start we should try to be the first we should teach a class teaching that class led to us writing a textbook oh wow what's that called Bitcoin and cryptocurrency technologies which is cool it's published by Princeton University Press the the best thing about I think is that it's freely available online at least the the pre professionally typeset and copy edited version as you can see basically that the author's pre-draft online so that that's helped it spread a lot I we have a list online but it's being used in

dozens of different university courses now so that's been great I meet people all the time at conferences who said they picked up the book or they watch there's some lectures that are on YouTube that accompany it so that was one of our first big projects was just putting these materials out we talked quite a lot to Dan Bonet about education and like you know that the state of blockchain education what what do you think of that and like is it in a good State or does there need to be more education where are we well there's an old saying that the easiest way to start an argument at a university is to ask the question what should an educated person know and people have really strong opinions about what's important

and what's not important to teach students I mean I've taught watching courses at three universities now Princeton Stanford and NYU kind of roughly the same template following the textbook focusing mostly on Bitcoin and aetherium I've seen other courses of different universities that take a totally different track they teach hyper ledger or some other system so I think we're still in the state where it's very much unclear what it means to have a class where you learn about block chains or crypto currencies what should be taught what are the important systems and some people take an opinion that it's not worth teaching Bitcoin at all because they think it's not sustainable it's not gonna be around

in ten years so it's a waste of time I think conservatively Bitcoin is the most sensible to teach not just because it was first but because since it inspired most of the other systems there's sort of pieces of Bitcoin everywhere so while I kind of agree that Bitcoin might be gone in ten years maybe even less time than that I think that we're more sure that the traces of Bitcoin will be around and if you decide to teach another system you know if you wanted to teach hyper ledger or tender mint or algo Rand or whatever entrant you have we have sort of less certainty about you know what's gonna be long-lasting and influential there so there's pretty widespread disagreement about you know

what are the basic fundamentals of the field that people should learn but besides learning cryptographic primitives which hopefully everybody teaches in their courses we don't really know what it means to be you know a educated person in the blockchain space it's it's kind of interesting as well to think about you know whether you're teaching a specific protocol or like the general system and taking it to like computer science some schools like just refuse to teach programming because they think that's like a vocational school activity and you should be teaching you know math and computer science from core principles in the same way like teaching Bitcoin or teaching a theorem it's like

teaching programming but what are the underlying things that you like what are the commonalities that you teach it's a tricky question I think that we you know a similar thing in the blockchain space is some people think it's really important to teach practical skills like how to spin up a Bitcoin note and sync it with the network or how to submit a transaction to the Bitcoin network really kind of low-level hands-on stuff and others say well that's kind of all details and you really should be learning how zero knowledge proof swirl or different signature schemes so it's really it's such a big space we haven't really at all standardized what what's important to know so let's go back to your story you were at Princeton what

happened after that well I came out to the Bay Area and was at Stanford for two years and was working with a Stanford crypto group looking for new research projects and that was around the time I think I'd had the idea of vd apps without before the name existed and that while I was at Princeton and when I came out to Stanford talking to Dan talking to others said you know this is always that if we had this thing of EDF protocols would really be a lot better so I sort of described this is usually how cryptographers start working they describe some functionality that they'd like to have sometimes they even describe it as what's called an ideal functionality or

sort of as an Oracle first and say if we have this magic thing we could build protocols out of it or do some other cool thing now we just have to realize figure out how to realize it so you know vdf definitely started that way I said if we had this function that had these exact properties then you know it would be really great and we worked on it for you know the better part of two years at Stanford before we had a paper to put out there and just you know obviously led to a lot of follow-up work so this it sounds like this video idea was really coming from you but you're the paper ends up having a bunch of co-authors how does that work so yeah I think you can you can trace the idea to a paper that an unpublished paper just

available online that I wrote while I was at Princeton with 200 two co-authors with Jeremy Clark and Stephen goldfeder and that paper was about generating a random to speakin or a lottery using the blockchain and we were looking at the idea which a lot of people had at the time this was 2015 of extracting randomness from block genes basically by just hashing the most random block in the chain and saying it's fairly hard to predict what the next block is going to be I wouldn't say that was our idea it was happening in practice at the time a lot of people were using this as a sort of quick and dirty way to get some unpredictable randomness from the blockchain we we wrote a paper analyzing

whether or not this was secure and different attacks that could be done by miners or others to try to manipulate the randomness and there's about two paragraphs in that paper where we say you know boy if you could slow down the process of extracting randomness if you could pass it through some function that was slow it would make these attacks a lot more difficult so that was kind of the germ of the idea where we said if we had this slow function we could stick it in here and it would strengthen this protocol you know when I showed up at Stanford I was talking to Dan and others about some problems we could potentially work on and I sort of went back to that and said when we were writing this paper there was kind of his gap where we said you know if we if we had

this thing this would really be a lot better so let's sit down for a while and see if we could build that thing then did you get other researchers to join you on it or are you using pieces of their work in it like how does that work it's a pretty nebulous process it works differently with different people and different institutions how academics form teams and write papers there's actually been some some meta-analysis of in lots of different fields of how collaboration networks form but it's very informal so you know I was talking about this problem to Dan we talked about it with many other students and people who are around people always say oh what are you working on and you'll

sort of fill him in on ideas and progress some of the students you know heard it didn't continue to work on it and it turned out that Ben fish and Benedict boone's who were both dance students also thought this is a really interesting problem ended up saying yeah we're interested we want to work on this with you we had a bunch of meetings but yeah it wasn't a more formal process than talking to them about it you know over lunch at the white board them getting interested having ideas that you know contributed a lot to the paper so that was how that you know group of four people writing the paper came about so I think we should definitely define now what a vdf is we've talked a lot about the process of making the research but

what is a vdf sure so I'll add one more side note which is that it took us a long time just to name this thing we went through lots of different names you know a slow function a delay function a unique proof of sequential work we ended up settling on verifiable delay function and I think it's turned out to be a really good name because there's three words and each one of them is really important basically say exactly what it is so start with the word delay it's a function that's designed to be slow to compute and you have to make a distinction between slow to compute and difficult to compute slow to compute

really means that it it's slow even if you have a lot of computers at your disposal okay so there are some things that are difficult like finding a block finding the next block in the Bitcoin blockchain but they aren't inherently slow because if you could throw an enormous amount of computing power you know you would make it faster and faster so the the slowness the delay really comes from the fact that it's an inherently sequential problem which means that more computers won't help you a faster computer with a higher clock speed will help a little bit but just adding computers working in parallel shouldn't help make it faster okay so that's the delay part this sequentiality slowness even with a lot

of computers working in parallel I have a slight follow-up question on the delay which is is the property just that it's slow like under undefinable slow or is the delay also a specific delay like is it and in here in part of a PDF to say I want to delay by 10 seconds yeah so that's a great question and it is it should be parameterize Abul so you should be able to specify about how long you want the delay to be now in practice you know it's very difficult to say we want the delay to be exactly 10 seconds or 10 minutes or a specific amount of time because people can always come up with a slightly faster computer with a higher clock speed that can eat into

that so usually the parameter is the number of steps of computation that you have to take and the wall clock time the real-world time that those take is gonna vary depending on what your what your computer is but that is very important that you can adjust the delay you know per different protocols might need a different length of delay alright so let's move on to verifiable sure so is that the next word yeah so the verifiable part means that it's easy for somebody else to evaluate the result of this slow function and check that it's correct often that's going to require providing an extra proof but a verifiable delay function has the property that you can efficiently prove

to somebody that you've done this correctly which is important in all sorts of distributed protocols because I deal you want only one person to have to compute the vdf and then they can just prove that the result is correct to everybody else and they don't have to re-execute the computation and then the third word is function function just meaning that there is a unique answer so for any given input there's only one output that it can produce there's not multiple different ways to compute one thing you kind of mentioned in the history of how this came to be was like this idea of randomness where does randomness and vdf connect because what you just described does not sound like random at all sure

yeah it's actually the opposite it's a deterministic function but why don't we talk about the lottery application or the extracting randomness from the blockchain because I think that will illustrate why it's important that this function be deterministic go back to that basic idea of hashing the most recent block in a blockchain and using that as an unpredictable random beacon okay so you know we could say say the three of us wanted to do a lottery between us and pick you know one of us to be the leader of the podcast no we could say the next block that's found in Bitcoin we're gonna hash it and we're

gonna take the result mod three and you know we would pre agree when we know if it's a zero I win if it's a one you win and if it's a - Fredrik wins at first glance that's a reasonably secure protocol it's difficult for us to influence what the next block that's found in the Bitcoin chain is going to be and it certainly would be hard for us to find one specifically that has the property that it you know it's hashes zero mod 3 but there is an attack on this and the attack would be if you are a minor you could find a block you could check what result it would give for the lottery and if you don't like that result you don't have to publish the

block you can just withhold it forever kind of throw it away wait for somebody else to find a block and the more powerful version of that maybe you're not a miner but maybe you're able to talk to all the miners and tell them if you find a block that doesn't produce the lottery outcome that I want I'll pay you more than you'll earn from publishing the block if you don't publish it and if you're really sophisticated you could set up a smart contract on a cerium that would reward the Bitcoin miners so there's been some interesting work about ways you could do this Ribery but that's the idea is that you know miners have the ability to not publish blocks that they find and that's one way to try and manipulate what the

next block will be and get a favorable lottery outcome so obviously this is fairly expensive Bitcoin blocks generate a lot of revenue each block so you know if you're gonna provide a bribe that's worth more than the block reward it's gonna get costly but it's it's possible if this lottery had millions of dollars riding on it it would be you know worth your while possibly to try to bribe miners in the network to to withhold and to try to bias the outcome so here's where the delay part comes in let's say that we say the result of the lottery is going to be the hash of the next block in the chain then run through a delay function that we believe will take a half an hour to compute okay then it's

not really possible to bribe miners to withhold a block that doesn't produce the outcome that we want because they'd have to find the block compute this function that takes a half an hour and then they'll know what the result would be and we decide whether or not to bribe them but of course after half hour is passed probably another block will have been found and published anyway and at that point it's too late for them you know to decide to publish you're not based on the outcome so this is what you mean it's this sort of makes sense so like the work was more unlike randomness and then you realized that there would be this technique that could potentially make randomness more secure and and like prevent this attack or this this lottery is it called like a lottery attack what

would you call that uh I would probably call it a withholding attack so it would prevent the withholding attack yeah or at least make it much much more difficult so this is exactly where it came from we were reasoning about this attack and we said if there was a way to make evaluating the the what we call the extraction function that generates the lottery result from the block if we if there was a way for for us to make that slow then it would prevent miners from being able to make a decision about whether or not to withhold until it was too late so we we started very much with that problem we just want to make randomness extraction from a block slow and then we kind of isolated it into the specific

cryptographic primitive that is a PDF and we that's where we said well it has to have a delay right for this whole thing that makes sense we want it to be verifiable so that all of us the participants in the lottery can quickly check the result is fair we don't have to do the delay function ourselves and here's where hopefully you can see why it has to be a function it has to be deterministic so that there's only one possible winner of the lottery right if there's more than one way to evaluate the vdf then the same block you know it could be evaluated different ways which would lead to different lottery results and that would be another avenue for potential manipulation the example you just gave the lottery example this is

like where the idea came from but PDFs sound like they're a lot more general like I feel like you could use this for all sorts of things and I'm surprised that this did this not exist before like was there nothing like this in cryptography yeah it's a really good question I mean that's always the hope is that you can you find you find a primitive a cryptic cryptographic primitive while trying to solve one problem and it ends up being useful for other people's problems as well which which has happened for the VBF there have been some other things some historical antecedents that are quite similar in our paper we actually talked about how if you take any of the three

properties away VD or F that that was another thing that already existed that people had worked on before so there's the D F and a VD yeah and a V F but not the three so they're exactly they're not called that the the VD the verifiable plus delay is called a proof of sequential work just as one example and I believe that was first published 2011 or 12 so yeah that was an object that had been studied and that has some applications but you know not the determinism part if you take away that you know delay it it's just a verifiable difficult function that's basically proof of work right which is used in Bitcoin and all sorts

of other places and just a delay function that's not verifiable that well I mean we proposed that in the 2015 paper because that was we didn't know how to do the verifiable part but that's also very easy to build you could just take a hash function take sha-256 you know well-known one in the blockchain space and if you just compose it so you say compute sha-256 and million times in a row on the same input now that gives you a delay function we just don't have any trick to verify that it was computed correctly so let's try to dig into how they actually work because when I first heard about it like a year ago or something it just it didn't register

with me like how would I write a function like this and it kind of felt like magic like how can I write something that is sequential that will take a really long time to evaluate but I can verify that the computation is correct you know the two didn't add up for me but then you know I think your analogy to proof of work is really good because it is essentially like proof of work but instead of having a massively parallel iced workload it's a sequential workload but I still don't really know like how you actually write this one yeah so I should say you know you shouldn't feel bad that it's not obvious how to write it we had multiple academic cryptographers you know not not working full-time but spending a fair amount of

time thinking about this for over a year before we really came up with anything that worked and in fact as soon as we published our vdf paper to other researchers you know solve the problem in a different way that in many ways has some advantages over our approach so it's it's highly non-obvious how to solve this problem although I think that's true for most of the great primitives in crypto history you know the first time you hear about public key encryption or signatures they sound like they should be not possible I think that's a lot of people's experience taking a crypto course the first time they see how signature scheme works for public key encryption there's

kind of a feeling of wow I might not have thought of that you know in a long time but thinking about it but once you see it it it kind of makes sense so there are generic ways to do this using any proof system that provides two synced proofs you know you may be familiar with some succinct proving systems like you know snarks that show up in a lot of different places in the block chain space and generically we know how to provide a succinct proof for any long-running computation okay so this is used for a lot of different applications around the cryptocurrency space so you can build a vdf that way by taking a delay function which like I said could be as simple as iterating a

hash function many times in a row and then you could take any system that provides succinct proofs and just provide a proof that this long chain of hash functions was evaluated correctly so like running Lake 2,000 times inside a snark would be a beat that would be of ADF yeah that should at least you know give you a hint that this is possible it's turns out not to be a very efficient vdf for a couple reasons you know for it to provide an adequate delay a thousand iterations of Blake is probably to Hue you'd probably want at least on the order of billions because a computer can you know a fast ASIC can certainly compute those in you know in

seconds so when you start thinking about how big the circuits going to be to prove that you've correctly done a billion iterations of Blake using a snark the numbers get really really massive it would take a very very long time to compute that proof everything would work it would actually still be a succinct proof that was fast to verify but the proving time would be really really large can I ask can I ask something the is totally like a 101 question and it might just be that my brain isn't working but when you use the word succinct I don't always understand what that means like it's used all the time but what what is the synced uh yeah so there's there's kind of a technical definition you know the high-level

definitions the sink just means short so we do some really big computation and provide a very short proof but it's correct there is a technical definition in crypto of how short it has to be to be no succinct but probably suffice is here to just say it means that there's a short proof of correctness okay and the size of the proof grows only extremely slowly relative to the size of the computation so you know you could basically think of doing any computation imaginably and the proof would still be very very small cool right so so you might ask given the fact that you know I just told you that the generic construction for trying to build a vdf ends up having a very long proving time

you know what can you do about this so in our 2018 paper we described a lot of tricks and ways to make this generic vdf idea more efficient and those included you know breaking up the chain of iterated hash functions into pieces and computing the proofs separately so that you can use some parallelism on them as the prover they included using a very special function so not Blake but much more efficient one way function that does well within a proving system but the most competitive vdf that we've seen were published very quickly after our paper came out by two different

researchers who are independently interested in the same problem and both of them used the same they use the same algebraic option which is swearing in a group of unknown order who are those researchers right so I guess I wanted to provide a URL VBF research org which is a very nice page that has a list of all the important papers that have been written on PDFs and it gets a little confusing because they have very similar names so the paper that we published in 2018 and by we that was myself Dan Bonet Benedict Koontz and Ben fish is just called verifiable delay functions and you'll note on the website that we

published on June 12th on June 20th there was a paper by Ben Wesolowski called efficient verifiable delay functions and on June 22nd so this all happened within ten days there was a paper by Christoph Peter Zach I hope I'm pronouncing his name correctly but it's a difficult one called simple verifiable delay functions and then since then there have been papers called continuous verifiable delay functions and tight verifiable delay functions but just to talk about the two papers that followed up on ours very closely the efficient and the simple usually they're actually just these constructions and those papers have sort of been named after the

authors now so there's the Wesolowski construction and the Peters Act construction but both of them are based on the same idea for building a delay function we'll get to the verifiable part in just a second but that's to take the operation of repeated squaring and a group of unknown order and so what does that mean what is a group of unknown order it turns out it should be very familiar to people who have crypto background any group that is used in RSA cryptography so just a large composite number product of two large primes provides a group of unknown order so this has been the basis of RSA cryptography signing an encryption for a long time and I should say RSA

cryptography even though it was it's very old it's been used widely on the Internet and lots of other places the RSA construction is has not traditionally been used in block chains right Bitcoin uses ECDSA not RSA signatures so RSA may be for people who got into cryptography in the BOK chain age not something that they're familiar with I think am I wrong here or does RSA basically require a trusted set yeah so it does require a trust is set up to generate this number that's the product of two large primes nobody knowing the two crimes the factorization but we should circle back to that because

there's a way to use these constructions without the trusted set up so sort of put a pin in that imagine that we have this large number n which is a product of two large primes and nobody knows the primes the basic step that's used to build a delay function in both the the Wesolowski the peters at construction you take a number mod n and you square it and then you square it again and every squaring is one step in your PDF so it's a very very simple function you just take a number you square it you reduce mod N and then you square it again and you do as many squarings as you think you need to induce the delay that you want so if you want to delay on

the order of seconds maybe you compute a billion squarings if you want to delay on the order of minutes you know you might need a trillion squarings or more that provides a delay function without knowing the order of the group we don't know a more efficient way to compute say a trillion squarings in a row and you can also express you know a trillion squaring 0 is saying you know take your input and raise it to the power 2 to the 4t or whatever your whatever your choice is for your delay parameter and I could say here as a historical note that this idea of squaring mod n and using it as a delay or a function that's sequential

that is an old idea dating at least to the 1990s so there was a proposal in the 1990s called time lock encryption and the idea was that you would encrypt some data with the property that you wanted people to be able to read it in the future but not now so you want anybody be able to be able to read it in the future but it to be a secret for now and the way that time lock encryption was was built the construction that was provided was also based on squaring mod n so you basically provided a number and you said if you square this number a trillion times maybe more than a trillion times then the result you get will be a key that is used to decrypt the data and

again that had a trusted setup to build so you know very different than the vdf setting but using the same basic idea of squaring mod n squaring in a group of unknown order as as a slow function okay so that idea was old you know our group at Stanford was also well aware that this was a good candidate for building a delay function the part that we didn't know how to do and nobody knew how to do publicly at least that we know about until June of 2018 was to make that verifiable okay so how can I take a number square it a trillion times mod n and prove to you that I did every one of those squarings correctly

it's very interesting because we now know two different ways to do this proof that work very differently under the hood and have different properties and they were proposed at least officially within two days of each other by two different researchers and you know since then a lot more people have looked at the problem and we have some tricks around those two constructions but that's basically it we know two ways to do it and you know essentially no other ways to do it so as a very very exciting time June of 2018 where we learned so much about PDFs in a short period of time I'm super curious to hear more about how these proofs actually work or

like what proofs they are even if it's just like where do I find more info on it so so what are these proofs and and maybe how did they differ from okay sure so I should preface by saying that both are they're somewhat complicated to get your head around I had to stare at both papers for quite a few hours to feel like I really understood what was going on even though both can be described in only a couple of pages maybe I'll start with the the Peters Act proof it has so I should say both of these proofs are very ad hoc they exploit specific algebraic properties of working in a group of unknown order so they're quite

different from generic zero knowledge proof techniques like snarks that you you know may have seen that work for any statement this is a very specific proof that is designed you know only to prove that a number was squared a certain number of times mod n so the basic idea behind the Peters act proof is you take the midpoint of the computation so you know you're taking an input X and you're squaring it a trillion times mod n there's some value call it Y that is X to the half a trillion or x squared half a trillion times and if you take that number and square it half a trillion times you get to the output so the Peter Zack proof

exploits this algebraic structure that there's a similar relationship between X and the midpoint and between the midpoint and the output and that you can actually verify that both of those two pairs of numbers X and the midpoint and the midpoint and Y have this same relationship and this could be checked efficiently using only half a trillion squarings okay so the prover actually provides a few numbers that would let the verifier check that both numbers have the same relationship only doing half a trillion squarings instead of doing all trillion squarings themselves so that's the basic idea is that you can reduce the amount of work to verify by half but then the beautiful part that gets you to a nice

efficient proof is that you can actually recursively do this so once the verifier has to check that this pair of numbers each has this half a trillion squarings relationship you can do the same proof technique again to get it down to a quarter of a trillion squarings and eventually you get it down to just one squaring that you have to do and it only requires a logarithmic amount of work by the prover to keep basically dividing the amount of work that the verifier has to do in half that makes sense and so the size of that proof ends up being logarithmic so if you're verifying two to the forty squarings you need to send on the order of 40 things to the verifier so it's

it's fairly short but it it grows you know slowly with the difficulty of the vdf that you're verifying if I can change gears and talk about the Wesolowski proof which is quite different it's very very elegant when you see it written out because the prover only has to provide I believe two things to the verifier so the basic idea of the Wesolowski proof it's easier to think of in terms of an interactive proof where the verifier is actually asking random questions of the prover I'll imagine that you're the prover so you claim that some value y is equal to x squared a trillion times mod M and I say okay well you know if that's

really true I want you to provide X to the trillion or x squared a trillion minus some random number squarings and then all do the rest of the computation myself so the basic idea is I query you on a random point in this chain of values that you get by repeatedly squaring so you don't know in advance which value I'm gonna ask for which means you have to have stored all of these values but then I can sort of quickly check that this value gets to the end point and that's why it's a very very short proof you basically just have to provide this one thing so cryptographers know a generic way to make any interactive proof

non-interactive it's called the fiat samir transformers sometimes the Fiat Jameer heuristic and the way it works is the prover simulates having this verifier by taking their answer hashing it and using that result to choose you know a random query that they then have to answer and that's nice because then it provides a proof that you can just publish and anybody can can verify so the advantage of the Wesolowski proof construction is that the proof is much shorter and the proof is actually a constant size no matter how difficult the PDF was so no matter how many squarings you've done it's always the same amount of information that you have

to provide to prove it the downside is that if you do it simply it requires you not only square say a trillion times but actually to remember every intermediate result in the computation so that no matter which one you're asked for you're able to provide it to the verifier in in practice there have been a lot of improvements made to this since the original publication and you know the the published paper by Wesolowski has most of these improvements so you don't have to have to actually have memory equal to the number of steps in the computation cool so yeah I mean there there's all these media competitions around as well that both you know you

know try to find better research but I guess mostly find efficient implementations and something I want to switch to it in a little bit as well but I I think there's also a competition for providing an efficient PDF in a class group instead of a group of unknown order what's the difference great so a class group actually is a group of unknown order it's just a different construction so the downside of working in you know what we call an RSA group is that it relies on a trust is set up somebody is supposed to choose two large random primes multiply them together publish the result and then throw away the primes so that nobody knows the

factorization of n and the vdf falls apart and becomes very quick to compute if you know the factorization of n if you know the order of the group and the technical reason for that is that you can take this large exponent like 2 to the 4t and just reduce it modulo the order of the group and then do a much shorter exponentiation so it's much simpler to describe it's much more intuitive for people to think about squaring mod n but algebraically the important thing is that you're squaring within a group of unknown order the interesting thing is that we know this one other construction of a group of unknown order which is called a class group that can be created with no trusted set up so the trusted set up

problem goes away now the algebra gets a little bit more complicated it's certainly less intuitive and familiar to people but we know how to do it and we know that the math works out and I guess the downside is that the implementation of operations in a class group are really slow currently so I guess though that's what the competitions are about to speed those up yeah so it's interesting it's not a problem per se that operations in a class group are slow because the whole point of a vdf is to be slow so that the slowness isn't the issue the issue is that we don't know how much faster they can be made to be with an optimized implementation RSA cryptography has been

around for a very long time people have thought a lot about how to square mod and efficiently there's been a lot of work on efficient implementations especially in hardware so we have more confidence that we can reason about how quick this can be made to be whereas for class groups they haven't really been used in practice for anything as far as I know the implementations are all sort of researched quality code there hasn't been a industrial implementation or a hardware implementation so we don't know how much faster a well resourced attacker could make class group arithmetic and this is interesting because when you use vdf in practice the interesting security question is always

how fast can my attacker compute this function and you want a reason about some speed that you don't think it's practical for an attacker to go faster than and the better you're able to estimate that the more secure the vdf is in a sense because you have more confidence that if you think that this function can't be computed in less than 10 minutes and an attacker shows up and can compute it in one minute because they have some algebraic speed up for the arithmetic that you didn't think about that might really change you know the security properties of whatever protocol you're using the vdf for yeah I think this is a problem or like a thing that I hear a lot and a lot of confusion

about with PDFs is say that VDS existed when Bitcoin was first built and deployed and they included a vdf that should take ten minutes and now ten years later CPUs are somewhat better maybe even implementations and code is so much better this thing now just takes one minute to compute or whatever like what's the impact of time you know a long time years on how long a vdf actually takes to like should blockchains be worried about this and redeploy or reconfigure their vdf software Euler intervals or now what does it take to actually use one in practice yeah so VTF there there's this parameter of the number of steps the

number of squarings for example that you take so you can always make that larger to keep up with Moore's law and to keep up with better technology making faster processors so that part's fairly easy if computers get twice as fast you require the vdf to tick twice as many steps you know that the difficult part is what if your adversary has a better computer than you do or a better implementation they have some algebraic tricks to speed up the computation that you don't know about that allows them to compute ten times faster than you and that's why I think the perception is that an RSA base vdf is more it's certainly easier to

reason about and is a more conservative choice right now because we have more confidence that there aren't big speed ups to be found algebraically and in squaring mod n and that's also where the contest comes in people who are interested in using vdf in avoiding the trusted set up for an RSA group and so therefore using class groups they hope that by having these contests to encourage people to come up with optimized implementations we'll get a better understanding of how fast you can make this go yeah make sense so I wanted to add about the trusted setup requirement for an RSA base vdf there is another way to potentially get around

this besides using class groups which is to use secure multi-party computation to choose to choose and to choose the the modulus of the group so secure multi-party computation allows a group of people to compute a function and as long as one of them is honest they don't all collude with each other you could compute that number n and nobody would know that prime factors this generic technique was already used for Z cash for example to do the trusted set up for the snark system that they were using which was done in a ceremony with many participants with the hope that they would all have to be compromised for the trusted set up to be undermined so there

has been some work this is something that's never been done in practice before choosing an RSA modulus via secure multi-party computation but there are a group of researchers working on this to think that it's within reach it's something that we could do you know in the next year and that would be a way to avoid the trusted set up at work and the slightly more well-known RSA groups cool I also just struck me that speaking about all these contests and speeding things up and the time-lock puzzle thing that you mentioned earlier I believe I read somewhere there that it was some University someone put out one of these

high Mach puzzles that were supposed to take like 40 years to unlock and some group of people who were designing a 6 4 4 V DFS figured out a way to unlock it and like the next six months or something yeah I believe it was MIT who did this and that's where the original research on time walk encryption happened in general I would say it's much more difficult to reason about an adversaries computing ability over a span of decades fortunately for most of the applications of EDF you really only need to reason about it on the span of minutes or hours where we have hopefully a much better idea of what what an attacker is able to do there is always

in any vdf system it's an unknown question how quickly an attacker is able to compute the function all we can really do is estimate and hopefully we can say an attacker is not able to compute it in less than a minute or less than 10 minutes even if it takes an honest party say an hour if that's the best known implementation we know of we hope that an attacker doesn't have some much much fancy hardware that lets them go and under a minute or whatever parameter we need but figuring out that gap the gap between the adversaries computing speed and the honest parties computing speed that's kind of the big unknown question with V DFS it's much more of an art than a science right now reasoning about this nebulous

potentially really well-funded attacker that can do things like use exotic semiconductors right not just a silicon semiconductor but these fancy really expensive ones that need to be supercooled and can run it really fast clock speeds it's an area that certainly cryptographers haven't really worried about very much before in most areas of cryptography we worried about a well-funded parallel attacker who might use a million computers to try to compute discrete logs or crack an AES key or something like that for vdf so we have to worry about you know a attacker who's constructing one computer that's designed to run at a

really really high clock speed to speed up the VBF and it's just sort of an exotic attacker model that the community hasn't really had to deal with before so in some ways we're sort of lacking expertise and even in some cases the sort of language and definitions to reason about such an attacker I want to I actually want to definitely spend some time talking about the ways that vdf are actually being used because so far we've focused a lot on the definitions and some of the challenges but like you know we started back at that example the lauter example that one was very clear that's kind of where this idea came from but like what what is it being used for

now because you hear that you kind of hear talk of vdf syn all these different contexts so where are the big groups you see it being used right now so the simplest answer to where V the apps are being used right now is nowhere as far as I know as far as I know there isn't today October 2019 there isn't a practical protocol that is using VDS and kind of the modern sense on it on a deployed basis I think there's a lot of people who speculate to use or like have to some degree said that they will use VD F's I mean there m2 is one example gia wants to use them in some way I have

an interesting case that we were toying with as well on how to use them yeah so there are they're showing up in a lot of people's white papers they're in a lot of designs but as far as I know they're not deployed anywhere one reason for that is that you really want a hardware implementation available for the honest users of the system before you deploy because if you assume that the adversary can build hardware to compute the PDF but you don't have Hardware yourself then the gap between your computation speed in the adversaries is going to be really really big so that's why for etherium in particular also I believe protocol labs have been interested in

funding a consortium to actually build some vdf hardware so that it can be used with more confidence knowing that you know there's hardware available to honest parties to evaluate this thing but that was just kind of my general disclaimer that as far as I know people aren't using them in practice yet but they are showing up and lots and lots of there are lots of use cases where people are planning to use them ok with the caveat that it's explorative kind of speculative there are a lot of other interesting use cases so we talked about using a vdf to generate random beacon or to run a lottery using using a blockchain and to prevent attacks where blocks are withheld or other

manipulation is attempted this also comes up a lot in proof of stake protocols and other similar things which really are running a lottery under the hood so in a lot of proof of stake protocols there's a sort of built-in lottery that randomly selects from among a group of validator is to find blocks or beyond a committee or otherwise have a specific role in a protocol so that's kind of an immediate jump to say we can use vdf to strengthen sort of internal lotteries that select protocol participants to have a certain role there's also lotteries not using blockchains at all so there's a famous very old idea over a century old to

generate a lottery result based on asset prices based on stock prices so the idea is basically we want to run a lottery what we'll do is we'll take all of the closing stock prices and then you know say the new york stock exchange or maybe some selection of large cap stocks it's very difficult to predict what all those stock prices will be tomorrow so we can take all those stock prices hash them and use that as the lottery result there's some very interesting history this was done in many different cities in America by organized crime who were running local lotteries I learned a lot about the history of this actually actually after getting into vdf but state lotteries mostly were created in the 1950s and later so prior to that

people have always liked to gamble and lotteries were mostly run by organized crime in different cities of course they had the problem of convincing all of the players that they were actually picking the winners randomly so what they did is they would usually pick a couple of stocks and they would use the last digit of the stock price and the paper the next day as the the numbers that would win the lottery so you can read all about this it was usually called the numbers game or the numbers racket and it was a very clever way for an illegal lottery that didn't have the force of law to verify that it was being done correctly to convince everyday users on the street that something random was

actually happening but you can think about using this idea and maybe a more modern setting to convince people that you're generating a random number and you could think about using a hash function taking more stocks and hashing that the stock prices and then you can say what what's the attack if you wanted to manipulate this if you were a stock trader how would you do it it's conceptually very similar to manipulating the blockchain based lottery you would wait until the very end of the trading window 4:59 p.m. you would look at what the lottery outcome is about to be if there's no further movement in any stock prices and then you could say maybe I could execute one more trade and I could push the price of

various stocks up or down by a penny or two and that would generate a totally different lottery outcome and if you happen to be some high-frequency traders with the ability to make the last trade of the day you would then have a lot of options for what the lottery outcome would be but basically the same defense using a vdf would work here if you take all of the stock prices hash them run the result through a PDF that takes an hour then that trader sitting there at the end of the day wouldn't be able to evaluate what different manipulations of stock prices would actually do right by the time you've computed the results of any manipulation it would be far too late to make a make a trade and actually manipulate the thing so I think it's

very interesting that this totally different source of randomness you know from the real world not block chains but stock markets you could also protect using the same idea just run the thing through a PDF in a way though like it's going back to this for a use case question what it sounds like is if you need real randomness that couldn't you really want to make sure that it couldn't be affected then a vdf could come in handy as sort of like another technique in order to promote that or to provide that yes actually we have a whole episode just on randomness with Justin Drake that we can link to but for this episode maybe we should just say quickly like we're in the sort of constructions do we see randomness being

necessary because I imagine in those places VDS will also be useful but in the blockchain context we mentioned POS but I feel like there's other stuff too yeah so I mean proven work kind of elegantly gets the randomness from everybody randomly searching for a solution you know proof of work doesn't explicitly need randomness in the same way even in some non proof of stake some more static Byzantine consensus protocols there are things like random elections of a leader and those can be you can use BBFS to make that random selection much more difficult to manipulate there's

obviously many uses of randomness in applications so not on the blockchain like not on layer one or whatever you want to call it but in the application itself so like one use case that we have is you want to hold a candle auction so that this is another super old concept where there used to be auctions and you wanted to prevent price sniping and you would light a candle and by the time the candle it burnt out that's when the auction ended and so that's how the auctioneers got randomness and you want to do if you want to do the same in an online context or like on unboxing then what is your candle what only it can be

a video that's such a nice metaphor I like that yeah that's really interesting it's not totally clear to me that the PDF applies directly to this example because we think about PDFs usually is having a deterministic number of steps yeah but you could so if you run your auction you run your auction for let's say 20 blocks then you start your vdf and vdf it gives you a number between 1 and 5 and that's how many blocks from the end your auction ends I see yeah that's really interesting I hadn't thought of that application before but that makes a lot of sense if you want some basically random result you know

how much extra time to add and you want the you want it not to be available until a point in the future yeah that's quite elegant I was gonna say for the record I didn't think of it websi Foundation researchers did okay I could also add that there are some applications of ETFs that don't have to do with randomness so one that I've heard more and more about recently in the last year is using vdf to prevent front-running so the problem with front-running usually is that I see you trying to place some order and then I try to quickly generate another order and broadcast on the network ahead of you and there's the idea if you

require every order to be broadcast along with a BBF designed to take five or ten minutes then you can prevent or make front-running much more difficult because when I see the order that you're trying to make I can't quickly produce another order with a PDF that took five minutes so to rush onto the network ahead of you right by the time I see your order decide the order I'd like to replace it with the vdf will take so long that I'm not able to get my order in ahead of you so I think this is a really interesting idea there is an important caveat to it to doing this securely which is that the attacker can try and precompute DVF's for different

types of orders and then decide which one to broadcast so for example you know if you're just going to broadcast something very simple like buy or sell and I know that I will either broadcast my own order that says buy or sell based on what you did then I can just beforehand compute the vdf on buy and on sell right I can do two of them in parallel and then I can have both orders ready to go and based on whatever you broadcast I can still try to front run you so this anti front-running idea it sort of requires something so unpredictable that I can't pre compute all you know plausible values I can't

pre compute the vdf result for them but aside from that caveat it's a very very interesting idea to use vdf to prevent front-running by essentially sort of proving that whatever order you're broadcasting you had in mind for some period of time right before broadcasting it there's another idea which is to use VBS for time stamping so for example say I had a secret idea and I wanted to prove that I had the idea a year ago I just didn't tell anybody about it I could broadcast the idea today along with a vdf that was computed on some hash of the idea say a hash of a PDF describing the idea

and if the vdf delay parameter was chosen so long that you were convinced it would take a year to compute then I could publish the idea along with the PDF proof and that would be sort of a non-interactive proof that I had this idea a year ago this conceptually is a really interesting idea because you can do time stamping in a purely computational way without relying on any trusted third parties or any time stamping service I don't think it's the most convincing real-world application of a VBF and the reason is that your uncertainty about computation speed becomes really important right if I actually computed it three months ago

that would have very different implications than a year ago so maybe like a factor of two or four speed-up that I have that you don't know about really changes the properties of the system whereas in most of the other cases we've talked about in the randomness case we can build some safety margin into the protocol and say well you know even if the attacker can go twice as fast it still won't be fast enough to actually manipulate the blockchain so that's okay but for the time stamping application you have to nail it basically you have to know exactly how fast the fastest implementations can go and know faster or else you really don't have that much confidence about you know the exact age

of something and it also might not be the most compelling application because we do have other ways to timestamp things right you can publish a commitment to them on the blockchain and just not tell anybody about it it's a little bit less elegant and pure than this you know computational time stamping idea with PDFs but you know it's it's possible we know how to do it well you never know - like I think even exploring these use cases these even if they don't seem pragmatic right now there could be some application where it is yeah that seems to happen yeah I think there we still don't know I think there will be a lot of other

applications of ETFs I hope so because they're kind of an interesting and fun thing to think about and it's certainly been the case to store quickly with cryptography that people came up with hash functions say a long time before people said well they can be used for proof of work and they can be used for authenticated data structures and that means block chains and cryptocurrency and everything else I hope you DFS will be around for a long time and people will come up with a lot of use cases for them that we haven't thought of yet cool thank you so much for coming on to the show and talking about VDS that's been super interesting I think it's been really enlightening to actually dig in and explain how these things work so thank you very much

yeah thanks so much for having me this is a this is a lot of fun what where should people go if they want to find out more I think that the best one-stop site to go to is vdf research to work and there's links to the most important papers in the space and also a lot of talks so you can see some talks that actually go through the algebra explain how the constructions work explain how some of the protocols work with fun animations and that's a great way to get a better feel for it well listen thanks so much for coming and chat and sharing all this and to our listeners thanks for listening thanks for listening you