Introduction to Verifiable Delay Functions (VDFs) with Joseph Bonneau | a16z crypto research talks

Transcript

uh so welcome to this afternoon's um a6 crypto research seminar uh very happy um that we'll be having jovano just joined as a research partner the research team uh last week and he's going to be telling us about a very important cryptographic primitive which he co-invented verifiable delay functions so joe it's all yours this talk is going to be as tim said about uh vdfs and a slightly more broad theme of time-based crypto um so just to position what's kind of interesting about this uh whole field like traditionally in crypto uh you know there's things that we want to be as fast as possible everything that honest parties do like encrypt things decrypt things sign things

um and then there are a bunch of problems that we hope are intractable as slow as possible so you know brute forcing a key computing a discrete log um and with time based crypto we actually want to design specific uh operations so that they take a specific amount of time so not fast not slow but some specific amount of time that hopefully we can parameterize and and get as close to a specific amount of real-world time as possible and i'll get into the fact that of course we can't really you know we can't design an algorithm that always takes exactly 10 minutes it would be good if we could um the real trick we have is just requiring a specific number of

sequential steps that that algorithm's going to have to take but we use that to sort of approximate real time um so uh vdfs i'll talk the most about but there are a lot of other uh a lot of other tools that fall into this category of being designed to take some specified amount of time rather than just being really fast or really slow so the the idea is pretty old or at least people have been thinking about things along these lines for a long time about inherently sequential puzzles and you know their use in crypto um before i guess 2018 when when we got into the vdf work there were uh a couple of different schemes known and

it's kind of interesting i guess retrospectively looking at it um that they all sort of had three of four uh potential properties but none of them had all the properties at once so the properties being like a kind of a fully public setup without uh without needing a trapdoor so for example time commitments and time lock encryption those somebody would have to basically set up the slow function with a with a trap door that they knew that would allow them to solve it quickly um there are uh you know things that uh didn't admit an efficient verification routine things that you know weren't inherently sequential

proof of sequential work maybe i'll talk a little bit uh later about but it was kind of interesting it sort of seemed like it wasn't clear you could get all these properties at once it turns out uh vdfs are the thing that has all these properties at once so i'll show you how how and why we actually want to do that but i should say that uh i we did not get into this research by drawing that table and asking a theoretical question um it actually started from a really uh practical question i mean i guess you know for those of you who know me i'm not uh really a certainly not a theoretical cryptographer i'm maybe barely an applied cryptographer i've always been much more interested in applications and security problems and

i've gotten uh you know more into crypto than i have on any other problem with vdfs because that's just sort of where solving the the problem took me um and the problem was was generating public randomness or having a verifiable lottery so um obviously a really old problem by the fact that there's a you know tile mosaics of people using dice to try to run the lottery uh still very much a real thing we still run fairly high stakes lotteries trying to to use physical randomness and sometimes i give a whole talk that just talks about kind of the history and the ways that this goes wrong uh you know if you don't know anything about soccer or association football and international tournaments they have to

put all the teams into groups and that's a really big deal uh people often think that the this is not done on the up and up um and in fact uh setbladder who's some would say disgraced former head of fifa um he uh allegedly said that uh the way that they would manipulate this process so it looked random on tv even though it really wasn't um the the process consisted of having these miniature soccer balls with uh different uh different teams names written on them and then a celebrity would draw them out in a random order supposedly um and set bladder said that they would put some of the balls in the freezer before

going on tv so you could reach around and feel for the cold or the warm balls of course on tv you're not going to notice anything so it's just a really simple way that they would try to manipulate this process allegedly but there have been a lot of other examples especially from state lottery drawings on tv um and it shouldn't really be that surprising if you've seen a magic show uh just professionals who are very good at making it look like they chose something randomly when obviously they didn't um so this is uh thinking about this problem and how we could try to generate public randomness in a more verifiable way is what what got me to to vdfs um

and i guess in in lieu of telling you know the whole story um i'll just give you a really simple example of a really old cryptographic protocol that probably a lot of you have i've seen this before but it's a way for a group of parties to to generate a random string together so we could call this whole thing a distributed randomness beacon that's kind of a more modern terminology for it you know cryptographers have thought about this since the 80s is distributed coin flipping or a couple of other names but in kind of in the in the blockchain world people think about distributed randomness beacon so the goal is just that these three parties can cooperate to produce some random output such that you know none of them can control what it's going to be

so classic way you do this uh everybody commits to their own random contribution so they just use you know really any cryptographic commitment function um so everybody has to commit by some specific deadline and then of course once everybody's committed everybody can reveal uh they can only reveal the number that they committed to of course that's what the commitment function is supposed to get you and then somehow you combine everybody's contribution and there's a lot of ways to do that you could run them all through a hash function or xor them all together so the the details aren't that important there and this it's a really simple protocol but it's actually really powerful

because it it guarantees you that as long as one party is honest and contributes something truly random the output should be truly random so every participant in the protocol kind of like sarah said yesterday as long as you trust yourself you should trust the outcome of this since you know you were able to participate and contribute good randomness but there's a classic flaw if one of the parties is malicious they wait until everybody has revealed so they they want to be the last last party to reveal and notice that if everybody else is revealed obviously this malicious party who hasn't revealed yet they can compute

what the final output's going to be because they have seen everybody else's random contribution and of course they know their own so they can predict at this point what the final result's going to be nobody else knows yet because they don't know what the last participant's contribution was and if the last revealer doesn't like this they can just refuse to reveal so they can abort or drop out of the protocol and uh you know in if you're designing this on a blockchain platform the answer might be that you punish them you uh they forfeit some bond or you you kick them out and don't let them participate again um and there's been a lot of

examples of this being built on top of blockchains where that happens where you try to to punish the party that aborts but it does give them some ability to you know they get at least one bit of manipulation of what the random output's going to be so it's a bit of a tricky problem um there's a whole stack of papers i have a with a an nyu student i'm working on a survey of this whole space right now um but there have been like at least 30 papers in the last three years that uh have extensions to this problem so uh distributed randomness beacon is a pretty hot topic for the research community at least um

so obviously you can't uh you know tell you what all these different protocols do but i can give you like a the high level flavor is that they involve the different participants in the protocol publishing enough extra information so the pvss is publicly verifiable secret sharing um so they uh kind of before you publish your contribution you you secret share it to the rest of the participants so that if you drop out some quorum of the other participants can recover and they can reconstruct what your contribution would have been if you didn't drop out um and there are a lot of other variations of this but they all sort of have the you know generic problem that if if the protocol

can recover from f parties uh aborting then that necessarily means that uh you know n minus f parties can simulate what the outcome would have been if those parties didn't abort um so you're sort of left with like a trade-off either you know you um if you want you know the n minus one trust that you know the commit reveal gives you then you can't really recover from many aborts and if you want to recover from lots of parties dropping out then a smaller and smaller quorum is able to uh to collude and predict the outcome early like this was the problem we were working on that led to vdfs but since then we've looked at auctions and you know like i'll show a couple of other examples but but yeah this this general

theme of like anything with a commit reveal where people are dropping out um yeah vdfs are potentially a solution it's so it's it's a pretty gender like we've discovered more generality since since doing the work okay so a much much simpler protocol that fixes the problem adds a delay function so i'll uh this is we'll get to a verifiable delay function in a second but for now it only needs to be a delay function um and i'll just say informally that's some function that nobody can compute in less than some minimum amount of time so how does the protocol look if you

have a delay function uh it's amazingly simple now there's no commit reveal it's really just reveal so everybody publishes their contribution before a deadline there's only one deadline now because it's you know it's only a one-phase protocol and the secret is that you combine everybody's input and then you pass it through this delay function and that's what the final distributed randomness beacon output is so why is that delay function so helpful well it's really only helpful if you ensure that the minimum time that anyone can compute the delay function is longer than the window that everybody has to

contribute randomness to the protocol okay and the reason that that uh kind of fixes the problem if you have a malicious participant who's trying to wait you know until the the very last minute to choose their contribution and even assume that they can see everybody else's contribution they can choose you know whatever they want based on that um you know they can uh they can think about different potential choices for their contribution and they can try and compute what the final result is going to be but they won't have time to actually finish so the delay function the one property it's supposed to give you is just that they

they can't compute it within the time window that they have to make a contribution um so they have no idea what the impact of any contribution that they choose to the the protocol is going to be or not and that basically fixes the problem i mean you you can give the attacker the ability to publish last in response to what everybody else has done and they they still can't evaluate what's a good or a bad choice um so it's it's quite a powerful idea um you kind of get back to the trust model of only needing one uh honest participant you don't need some mechanism to punish aborts or some other you know kind of blockchain based infrastructure the only kind of extra assumption you

need over standard crypto assumptions is that these delay functions exist and that we can we can build them it turns out for other types of randomness generation it's it's also a really powerful idea to add delay functions so i'll show you two other examples um which maybe you've uh seen or heard of before um so there's another idea which is uh also quite old actually i mean this this idea is kind of cool actually because this is how organized crime did uh illegal lotteries in like the 1910s in the uh the old-timey like pre-prohibition gangster era um but it's actually a serious idea that people still think about

that you generate a randomness beacon by taking a bunch of asset prices so say you pick a basket of stocks on you know new york stock exchange or some other large stock exchange these are large cap stocks that are very difficult to manipulate the prices of and you say we're going to you know take the closing price of all these stocks and and hash it or run it through an extractor function at the end of the day and that will be our random output the attack on that which is it's conceptually very similar to the last revealer attack is that some attacker looks at what the market is immediately before the market is set to close and then they can kind of test a lot of

scenarios for very small market manipulations that they could make which are maybe cheap enough to do like they could change the price of a specific stock by one penny maybe that's feasible you just need to push a few extra trades through before you know trading ends i know this is like a incredible oversimplification of how stock markets work and how closing prices are quoted um but you know uh just abstracting a little bit uh imagine if the attacker can just you know has the ability to push stock prices by a small amount so the attacker can simulate like well if i you know there's a lot of different small trades i could make and those would all lead to different randomness outputs so i can sort of pick the one

that i like the most and then i can try and force the market into that that closing configuration um so uh that's what you know an attacker could do if you did kind of the the simple choice here you'd be vulnerable to a high frequency trader trying to do this but you know you can probably predict uh solution if you uh hash you know all those stocks and run them through a delay function you get the exact same security property that the attacker is not able to to simulate you know the effects of any of these manipulations so they can't uh they can't determine what what strategy they should take before hopefully before the market has you know closed for the day and everybody's gone home and and

you know we're stuck with whatever outcome we got um so that's uh you know another another beacon idea that also benefits from delay functions um and the third one which is uh also kind of a popular idea that a lot of um applications that try to do lotteries in the block space blockchain space have done is to just hash blocks in the in the blockchain same idea difficult to predict you know future blocks in the chain if it's a proof of work chain especially you obviously at least can't predict the solution to the proof of work puzzle um but that's also sort of vulnerable to manipulation

by miners so you know imagine that you're just going to hash the block that occurs in this at this slot or this depth in the chain and generate a lottery outcome as a result an attacker can look at that if there's a block collision and they can try and choose one of these two branches to promote right so it could be that this attacker has a lot of mining power and they can switch you know from one chain or another to to try and make that chain be the eventual longest chain they might not have any mining power they might just be bribing the people who do and say you know i'd really rather you promote this one chain or another it could be that most of the miners don't have any preference between the two chains so any small amount of bribe will be enough to push you know mining

power onto one chain or another um and of course you know if you uh the way to prevent this manipulation add a delay function and then hopefully by the time the attacker has figured out which branch they would even want to promote again you know the very consistent theme here it's like too late for them to act by the time they figured out what they even want to do oh uh yeah i mean you know like the idea is like you'd be just hashing this block in the chain to pick the winner of some lottery so it could be like that this this block means they win the lottery

and this block means they lose the lottery uh right or some you know whatever application you're built i was kind of describing it in terms of like building an application layer uh lottery on top of what's happening on the consensus layer which people have done um but yeah with with with proof of stake you know it's like purely within the consensus layer you might want to manipulate who's on the next committee or who's you know chosen as a block producer and same idea applies

um okay so uh you know these are thinking about all these problems made us realize these you know delay functions are potentially really useful um and we wanted to add the property that they're efficient to verify which just makes it much more practical in all these cases that you know somebody has to compute a slow function then everybody else can can verify that it's been computed correctly um so uh without getting into the full crypto formalism um a verifiable delay function is supposed to have three properties two of which are pretty straightforward uh the the v the verifiability just means that it's efficient to verify

solutions you don't have to repeat the slow computation to to check that the result is correct which means hopefully only one party has to actually do it and everyone else can just do a verification which is cheap at a technical level by efficient we mean that it's like either constant time or uh you know poly logarithmic in the delay parameter okay so if uh it's it's not taking more and more time the longer that the delay is to actually verify it um the delay part uh the d property um is that we don't know any way to actually solve or to run this evaluation algorithm

without taking at least t sequential steps and t is a parameter so when you set this whole thing up you can specify t how how many steps you wanted to uh you know to require to solve um and then the security property the vdf is supposed to ensure that we don't know of any algorithm that can solve it in uh you know fewer than t steps and of course there's a slightly more you know detailed crypto definition which has you know some epsilons and gives you know like a slight uh you know percentage that the attacker can go a tiny bit faster but that's kind of all we'll we'll tolerate um like cryptographically the only thing that we can really guarantee is that it takes two steps how long those

individual steps take in in the real world on real hardware that's not a crypto problem that's like a you know security problem and i'll you know i'll talk about how we would actually reason about that but that is like a very tricky thing like kind of translating between the two um but yeah it's obviously like we wish that instead of saying like t sequential we could say it takes t seconds to solve but like we we definitely can't do that so um okay so that's uh the delay property and then uh the f property the fact that it's a function just means that there's only one output which you know may seem kind of obvious but it's actually you know

there's proofs of sequential work which i think are on the next slide which don't have that property and don't work obviously if we're using it in some kind of lottery application and there's multiple ways to solve it that would be different you know possible lottery outcomes so that wouldn't be good we want to ensure that there's only one one output to this thing um okay so uh if that makes sense i can sort of show how we build these things cryptographically this is just kind of the api for the the vdf as a cryptographic object um so uh there's some setup where you pass in a security parameter and a delay parameter t

um and then you get some public parameters out and i'll talk about later but that might be a trusted setup for some constructions which obviously is a potentially big concern you know might might be a public setup which is great and then there's this evaluation function that takes an input and produces an output and a proof so that pi is just the proof and that the the proof kind of drives this efficient verification algorithm that checks if your input output pair x y is correct it just gives you kind of a yes no answer um some schemes potentially don't require an extra proof but i think most most do so the proof like maybe could theoretically be null but in in practice

we need it one one comment actually is like the the attacker may not care about the proof like they may just want to know what the result is and they don't care if they can prove it to anyone else so there might be like an eval prime that just produces the output y and not the proof which is useful to an attacker so they can figure out like what what to manipulate um whereas like the the good guys the honest solvers have to actually produce a proof so they can prove to to everybody else fortunately for the constructions we know of there aren't like huge shortcuts if you don't like it it is extra work to produce the proof i'll talk about that a little bit but it's not too much extra work but yeah that's uh i guess to drive the

point home this ideally this eval is kind of run by one party um and they don't have to be trusted since they're producing a proof you just want somebody to do it and then verify is the the thing that everybody will run to actually verify that the lottery was was computed correctly um okay so like i said earlier if you take away any of these three properties it's kind of a known construction if you just want to build a delay function that's not efficiently verifiable that's really easy you just take you know kind of any one-way function iterated a bunch of times and that will take you know you iterate it t times and it will take t steps to evaluate and you're sort of done but that doesn't

necessarily give you an efficient way to verify that this was done correctly um if you don't care about a delay a sequential delay there's all sorts of problems that have this property but can be parallelized like a simple example is just solving a discrete log that's you know it's efficient to verify and it's a function at least you know modulo the group order but it's there's no kind of minimum number of steps to compute that because you can parallelize computing discrete logs um and then the the trickier one that's not as well known is a proof of sequential work uh which is verifiable and requires a fixed number of steps

but it doesn't have a it's not a function it doesn't guarantee a unique output probably not worth i guess i could explain that kind of offline if anyone's interested in how it works it uses depth robust graphs and it's it's actually a very interesting construction um but i'm not sure it's really used anywhere because uh it turns out like the modern vdf constructions are more efficient than this anyways so it doesn't seem like there's too much advantage to this construction even though it's really interesting um okay so before i show like the vdf constructions i'll make a point that it's not actually clear that you always need an efficient verification algorithm

so uh solana uses um what they call a proof of history they've been using the term vdf more now um but you know arguably they kind of like came upon the idea independently but they just use an iterated chain of sha256 and they call it proof of history somewhere there's a forum with them arguing with benedict about whether or not this qualifies as a vdf and they said like we we think it's a bdf uh and benedict said well you can kind of call it whatever you want but it's not not verifiable um but the way they verify it so they compute this long chain of two five sixes and then uh they verify it kind of in parallel by

breaking the chain up into pieces and then you know you can you can verify it a lot faster than computing it by if you have parallelized them for the verifier because you can just have different threads verify different parts of the chain um so they've basically said that that's sufficient for their purposes and they're not really interested in a fancier vdf construction um so just kind of interesting that you know this ideas popped up there and they seems like they're they're fine living with it um but uh oh i guess one more before i get to actual vdf so this will be you know useful in explaining our vdf construction this is an old idea i guess that's

hidden there but that's should say 92 but this is it's kind of like a proto vdf or we call it a weak vdf in the the paper but the function's really simple uh you're just computing square roots mod p um so this doesn't even have to be a really big prime number it doesn't have to be like a you know 1024 bit you know diffie-hellman size prime it can really be anything um and if you want to compute the square root of some you know uh element in the group mod p it's just you know a one modular exponentiation okay so it's like roughly

uh log of p steps to do this so uh you know the larger p is the more steps it is to actually compute this square root um whereas to verify it it's always just one squaring right it's very verifying the square root it's easy you just square and see if you get the result that you want so this is kind of like almost good enough to be a vdf the problem you can say like why this is it gives you like this asymmetric delay so why is this not enough um the problem is it doesn't really allow you to scale the number of sequential steps to solve this to be as as large as you want like if you want it to take more steps to solve you have to choose a bigger and bigger prime

um and that kind of eventually gets unwieldy uh so if you wanted to take like two to the 40 steps to solve which is like a practical parameter that people think about now uh you know you you end up using some enormous prime number that you know obviously the uh the result gets really really big and it's not not very convenient to work with so that's kind of the limitation but i'll show you how we we use this to build something that is kind of scalable um okay so the construction our 2018 paper uh well first we sort of made a simple observation um that you can sort of just take any delay function and you know use a snark and then it's a verifiable delay function so that's kind

of obvious this might not actually be very efficient for the prover um but kind of generically you can just take that you know chain of one-way functions just you know run it through any system that gives you succinct proofs and then it's verifiable again probably not very practical because the the proving time is probably going to be relatively large and concrete terms relative to the time to evaluate but this kind of shows that it's possible and the trick we introduce that makes this actually practical we compute a chain of modular square roots um so that's kind of the the iterated

one-way function it's not just kind of any one-way function like a hash but it's a modular square root um and then instead of uh instead of verifying the forward direction we verify the reverse direction which is much faster um so we actually verify using our succinct proof system um is the reverse chain that if you take you know y and square it a bunch of times you get back to x so you know obviously that's uh you know this is a much simpler uh you know it's much faster to go in this direction than this direction but the the really kind of powerful observation

is that you can just sort of run two threads in parallel uh one thread is evaluating in the forward direction so it's it's iteratively taking modular square roots and then you have another thread that's chasing it that's computing bits of proof that's kind of doing the reverse direction so every time the evaluation thread does one more modular square root the proving thread computes a little bit more of the proof circuit that just proves the squaring in the reverse direction um and it turns out that you can you you can achieve this goal of having the proving thread keep up with the evaluation thread so there's almost no extra time to compute the final proof uh

and of course the you know one of the the tricks to get this to work is that you you do this all in like the the base field for the proof system so that you know uh just proving one squaring is like you know one one uh one gate in the circuits like ends up being really really cheap um yeah oh so t here is like the number of steps in this chain yeah um so we're not like we're not we're we're only requiring uh the prime to be big enough basically so that there's a big enough gap between

these two that the proving thread can keep up with the eval thread but the t comes from the number of steps in this chain so you can make that as long as you want different modulus same modulus yeah i'm leaving out a detail which is like you kind of re-randomize between each of them but yeah it's it's you're working on same same modulus each time yeah and it's a very specific modulus that's like you know the the really efficient one it's like it's you know it's the the field that the proof system's operating over well i mean

yeah uh like it's it's in the yeah like it you could sort of collapse the chain if you didn't do anything between them yeah you know our construction in the 2018 paper [Music] and this has been built out so uh starkware had a project to implement this using using starks obviously um they were running it i think that they've stopped running it but i mean the code and everything is still available but they were actually running this and verifying the vdfs on ethereum so this is you know it's it's practical to do it works with stark so it's even like post quantum which is great

um and this is one way to get a vdf there's some other ideas in uh in our 2018 paper too like using incrementally verifiable computation so instead of like one big proof that you're kind of computing pieces of um you have you know proofs that verify a proof from the last step and you you know you iterate so if you're doing t steps you actually have t proofs and each proof verifies the previous one and there's some kind of related ideas with proof aggregation and things like that um that i'll i'll move on and talk about the rsa-based ones but i'll just say that there's like a couple of different flavors of these proof-based vdfs that we talked about in in the paper

um the uh other kind of like main family of uh vdfs that was developed like right around the same time as our paper came out um i guess 2018 like summer of 2018 was a hot time for vdfs because our paper came out and then two different papers from two different researchers independently coming up with ways to build a vdf in a totally different way with squaring mod n so this delay function is really really simple you take your input you work uh modulo and rsa number n so this is you know a large number it's a product of two

primes and nobody should should know these two primes and the delay is just that you take your input and you square it t times really really simple just just t t straight squarings or you could think of it as raising it to one exponent you know two to the t the reason that this only works uh mod n you need it to be a group of unknown order if you know the group order then you can reduce this large exponent mod the group order and you know you can always always do it in you know maximum like uh you know log n multiplications um so this you know the the unknown order part is really important for making this actually uh

inherently sequential um so we knew that this was a delay function for a long time this this idea was originally in uh the this rsw paper in the mid 90s for time lock encryption um so we knew that this was a you know a good candidate for an inherently sequential uh problem the question that we didn't know how to solve until 2018 is how you actually verify that somebody's computed that correctly and it turns out like i said you know two different papers showing two very different proofs is really really interesting they work in kind of completely different ways which i'll show you um and they came out around the same time

okay so how do we prove that you've actually done this large squaring in a group of unknown order so this is weslowski's proof and i'll show it to you as an interactive proof even though of course most people do it non-interactively with fiat shamir so the approver you know claims that they've computed this correctly the output is y um the uh challenger sends them a random prime so this is kind of important actually because this is like the big performance bottleneck and verifying these proofs on the blockchain and other places is that if you're doing this with fiat shamir you have to have a hash function whose output is a prime

which is like pretty ugly to actually verify like you can do it but it's kind of expensive so that's like a limitation of this this proof you need hash to prime but anyway the challenger picks a random prime number um and then the prover this is like done over the integers the prover represents this large exponent as they basically do long division so they get some quotient if you divide the large exponent by this prime l and then there's a small remainder and they send this value back to the verifier which is kind of almost uh x to the the two to the t it's this very

large number but there's still this small kind of remainder left okay so this is a very very large number it's not as big as 2 to the t but it's like almost all the way there [Music] and then the challenger just does like one multi-exponentiation i guess where they they take this value sent by the approver they raise it to the power l and then they you know they they add in the remainder kind of manually so they're not doing like the huge exponentiation themselves they're just doing like a very small exponentiation uh which is like at most the size of the prime l and how big does that prime have to be it just has to be so big that the

the challenger has no chance of predicting it in advance so like 128-bit prime number is is like there's a lot of details about how this works and that the security assumption even though it's like very very elegant um if this if you've never seen this before and it doesn't make sense like this it took me a long time staring at this to feel like i had an understanding of what was going on um but just to show you this is like a really really great discovery it's really elegant uh really elegant way to do this proof really simple and notice that the proof is constant size you always just send this one value no matter how big the exponentiation was so it's a constant size proof it's very you know cheap to verify

so it has some really really nice properties there is a question of you know if the the prover has to compute this value um and then you know they know this almost as big value they have to compute how do they actually compute that efficiently the naive solution is like they basically start again and compute another big exponentiation and it takes almost twice as long obviously that's not very good so there's some optimizations where you store points along the way um sends r yeah uh no i think the challenge the verifier recomputes r like i think the you know the challenger picks l and then once you've picked l

like uh r is like uniquely specified once you've picked l two to the t is public so once you've picked l like q and r are uniquely specified yeah uh yeah so you so that doesn't have to be sent one point to make here is that it this we have a way of making it a zero knowledge proof but by default like it's it's a bit strange it's not a zero knowledge proof and it's something that the challenger could compute themselves if they spend enough time right there's no secret that they don't know okay so that's uh weslowski's proof um and then a totally different way of doing it which i actually think is more intuitive maybe this is uh peter zach's

uh proof um so this uh i think it's more intuitive you basically take this long exponentiation and you break it in two so you pick kind of the midpoint like think if you're doing t squarings to get from x to you know to y or x to the two to the t um you pick this value in the middle which is when you've done t over two squarings right so you pick this halfway point in the chain um and you uh so he calls the halfway point v halfway between u and w and then if uh if v is actually uh supplied correctly so you know basically the

uh the prover supplies u and v and w and claims that it's you know uh the halfway point on the chain um and t prime is this you know big exponent here uh so the the prover makes this uh claim um that you know these are picked in this special way so then this kind of relationship will hold where u times v raised to the power 2 to the t over 2 should equal v times w and that's just like guaranteed to hold if this chain was set up correctly so the challenger can actually just pick any

values a and b and this relation will still hold you know even if you raise uh you know if you if you add these random exponents so you sort of like randomize it and check that um so this is just kind of a way of checking that you've actually supplied the correct midpoint of this chain so why is that useful you know you've only like uh you've just proven what the midpoint is and the proof strategy is that you do that and then you sort of like recursively do it now for so if like if you only did one step um the

verifier would have to actually manually verify that you know v is really u raised to the power two to the t over two um but the observation is that you can just prove that it's the midpoint and then you can recursively do the proof uh you know from the beginning to the midpoint and you can do this as many steps as you want and then eventually you you cut it off and you manually verify the rest probably at least to me this was the much more intuitive way to do it but you can maybe sort of see the downside is that you uh if you're doing this interactive interactively you have to do like a logarithmic number of steps to keep cutting the distance down so instead of having a constant sized proof you have like a logarithmic size proof just show you like a couple of

interesting properties comparing the two i think that the main thing to remember the wesolowski proof is [Music] it's kind of optimal for the size of the proof which is constant size so if you have to post this proof to a to a blockchain or anywhere else wesolowski proofs are kind of the best but they're actually more expensive to compute so it's it's much cheaper and you know takes less space to compute the petersack proof and it has some other nice properties like it relies on a strictly weaker assumption it's uh it's still a sound proof even if the group order is known this is actually kind of like a subtle distinction that i think gets lost a lot the um

the weslowski proof is totally unsound uh if the if the group order is uh known and the petersack proof is unconditional so even if the group order is known it's actually still a valid proof which is kind of very interesting that these two things emerged and kind of both of them are used in different applications just to give you like a small flavor of all the work that's happened you know the last four years as cryptographers like to do you know once came up with the idea of vdfs people have proposed all sorts of extra properties that vdfs might have and that's led to like a lot of follow-up papers so you know all of these i'd be happy to talk to you about the watermarking one is kind of interesting because it's very useful

and there's a construction that it's not has there's no security proof so we don't know if it's actually like a secure uh watermarking scheme or not so that's like kind of an interesting area to work on um the decodable vdf thing is more of like a dream where we wrote about it in the original paper you could build really useful stuff if you had it but we sort of don't really know where to start and the rest of these you know have all been been worked out and then in addition to the randomness application that originally got us interested in this people have proposed vdfs for all sorts of other applications in the blockchain space out of the blockchain space depending on i might be like up against time but i can talk about any of these depending on

what i'll show the the front running prevention one because this comes up in in blockchains a lot um so there's kind of you know front running probably everybody's seen it if you have like some name registry thing and someone publishes a message to the network saying like i want to register this new name for my new brand that i'm launching the concern is that some attacker will see that that that attempt to register a new name and then they'll try to sneak their own claim in for the name right before it can get confirmed on chain so the idea with vdfs is that uh you know when you broadcast something like this and again there's kind of a relation to commit reveal because people use commit reveal for front running

prevention sometimes but you'd basically you know publish your claim to the new name and your key and then some vdf that you've evaluated on top of that information um so that kind of proves like i've wanted to register this name for at least 10 minutes or whatever and then if an attacker tries to front run they don't have enough time to basically like compute a vdf on top of a claim to the name for their their identity so hopefully if you parametrize this correctly they're just not able to front run because they can't compute it in time so it's kind of an interesting application there's some startup called slow swap that's trying to do this for kind of like a decentralized exchange and there's been a couple of other

papers discussing it the flaw in this well not in this example but the flaw that can come up obviously if an attacker can pre-compute vdfs on tons of possible orders then this is no longer secure so the assumption is like the attacker doesn't know what front-running transaction they want to make until after they've seen yours otherwise if you know they can just sort of pre-compute every possible order and if it's a small finite set so if you go back to like this example like the attacker could just use a different 1048 bits of randomness right like i guess depending on what it's actually like the point is like the attacker shouldn't be able to predict what the thing is going to be right

yeah decodable vdfs maybe zard problem but i do think that we could make some work on uh the watermarking scheme um there's a whole i didn't talk about class groups but it's an alternative way to get a group of unknown order besides rsa groups that uh you know we believe can be done with a public setup with no trusted setup no one's really done figured out in practice how to choose those yet so these are kind of like the theory questions um and then on the the practical side um there's like the biggest question is really like how efficient you can make solvers and how fast these things go in practice right what the relationship is between the number of sequential steps

that you pick as a parameter and actual clock speed in the real world so there remains like a lot of questions about how fast you can go on fpgas on asics whatever hardware you have available and i think this is really good kind of hands-on implementation work and it'd also be great to have kind of like standard software that evaluates these things and verifies them with all the different variants that we know uh verifiers that work in smart contracts so you know we we have done some vdf verifiers that that run in solidity run on ethereum obviously like other platforms we haven't done yet and also verifying these things within uh within circuits for proofs is another like hands-on area

um so yeah i can take questions and these are all like you know things i'd be interested in uh working with on on the theory side or the application side as well as i should say there's probably a lot of other applications of vdfs and questions about the incentives and who computes them and how they you know they interact with the economics which would also be good to work on there was this paper at what last year on delay encryption yeah and that uses a misogyny-based pdf is i mean this is just a boring question i'm trying to remember is that construction like does it require an isolation based pdf or would any video work um it's a good question i remember like i remember seeing that paper when it

came out but i never understood the details of it so i don't know if they fundamentally need the uh the isogeny based construction um decade or so there's been a lot of work on cryptographic watermarking what about [Music] here it's a good question um this might mean something like slightly different than traditional watermarking what you're actually watermarking is the proof so someone evaluates the vdf and

then the proof actually embeds a watermark like the provers identity um so i think it's sort of different than like general cryptographic watermarking because it's very specific to in this case you're watermarking a proof so you're like entangling the provers identity into the proof itself uh hopefully in a way that you can't take that and produce another valid proof i should show you the watermarking scheme because it's pretty simple and i'm not sure it's secure but it's it's very simple and if there is a connection to something else we that we already know more about that'd be great but i'm i'm not sure like i think it might be kind of kind of different yeah but i also probably don't know the the classic watermarking stuff well

enough basically on like a good laptop you can do if you're if you're doing like a 2048 bit rsa modulus which is kind of standard like a fast laptop can probably do about a million squarings per second and there's a paper with an fpga implementation that did like two to the 24 squarings per second so you get kind of like an order of magnitude on fpga and that paper which was it was written by some uh some researchers from intel they they estimated that you would do about two to the 28 on asics with like reasonable kind of like uh feature sizes so maybe like another order magnitude speed up from asics um so like

roughly you probably go like 10 times faster with fpga and another 10 times faster with asic but obviously like the details might matter a lot well uh like the assumption and this the assumption was like that the good guys will have asics too so there's this project like ethereum put some money in to try to develop asics that would be like publicly available um and then there's kind of a theory that the attacker can't go too much faster i had a slide somewhere ah yeah there's like this big conjecture which we can't really prove that um basically like you can always go faster if you have a bigger budget but hopefully there's like

pretty strongly diminishing returns like that if you want to go you know 10 faster you have to spend like way way more money um but obviously this curve is just like scribbled by me this is not based on any data so we have no idea in practice what the shape of this curve is like or like be interesting to see but i'm not a hardware person so i'm a little bit at lost to give you a better answer than that um i'm yeah it's a good question like t definitely could change over time um so for all of the unknown order things it's like uh they're like technically we call them incremental

vdfs but you don't have to specify t at parameter setup time so they're really easy you can change t to b whatever you want um you can even change it like on the fly while you're in the middle of solving it for some of the proof-based ones you do have to bake tea in a little bit more but then you just do like well we had you know whole talk yesterday about structured reference strings so like maybe you have a universal one or maybe you have to redo the setup if you change t is it incorrect to model uh hardware differences as like one entity is faster in evaluating one step of the thing and then the advantage compounds as t grows or is that

like that well it shouldn't compound it should be linear right like if you go 10 faster on one step you should go 10 faster on yeah yeah um no this isn't this this chart is very very abstract this is supposed to be conceptual but uh this is i mean this is the evaluation speed for one step or for the whole computation right uh i mean it's just a chain of things so if you speed up each one it should be like a proportional speed up there's a lot of talk about graphic attacks in 2018 uh and it seems like the

kind of theory around that time was that like you were saying a6 needs to be in the hands of everyone um and i'm curious if there's ever a uh construction that would eliminate the possibility of grounding attacks or if we had previously so i'm not sure i understand your question you're asking about grinding attacks yeah certainly for example uh with mbes if there is a [Music] if someone has a lot more a lot more powerful heart than everybody else they can uh and specifically in the

construction of ethereum like you could uh you could increase the difficulty required to compute some pdf by making t increase over time and then go online such that it completely slows down the system or you can pretend that you have less power than you do and then actually have more and uh affect the last yeah i guess like with vdfs it's like the amount of computing it's very different because

it's not like you can just like take you know with with asics it's like you can take some of them offline it's like it's a highly parallel thing so you can reduce the amount of parallelism and change your performance with with asics with for vdfs it's probably like you have one asic computing it at a constant speed and like it's either online or it's not right you can't like take part of it to do some other problems so um yeah so i guess it's it's true that if you have some like really fast solver who then goes offline like maybe you get into trouble but i guess the assumptions like that once you've built once you built an asic that solves it fast you probably have it forever all right