Verifiable Delay Functions - Dan Boneh

great okay excellent yeah so this is a there's a pretty diverse group so so let's see so right so all mathematicians to cryptographers to hardware folks it's a pretty pretty broad area so I guess just to kick things off what I'll do is maybe just kind of give an overview of what vdf Saar just to make sure everybody's on the same page I imagine it's gonna be stuff that many of you already know but I think it's good to just make sure everybody knows what it is we're talking about and then we'll dive into the details and the subsequent talks okay good so the goal of a vdf is basically to slow things down yeah this is kind of what Joe taught me and so the question is how do we slow things down verifiably so let's define what is a vdf again I won't give very precise definitions you can look at the various papers for that but just to get to get the idea across let's start with a high level definition so a vdf basically is a function that's about oh yes yes okay good back on excellent but it slows out that exactly something that my talk the vdf to talk okay so it's a function is supposed to take T steps to evaluate and the point is it should take these tips to evaluate even if the adversary or you know even the honest parties have unbounded as too much have polynomial parallelism so if even if you have polynomial processor put many processors you shouldn't be able to speed up the evaluation and the point is once you have computed that you've you've spent the T steps to value the function it's easy to verify that the output was computed correctly okay so it's a little bit more precisely so there are three algorithms to set up the vowel and the verify algorithms so set up will take a security parameter lambda a time bound T and will produce the public parameter as P P which we'll talk about more about the setup procedure later in the day this might involve these multi-party computation steps and so on so that's the setup once we've done set up the evaluation algorithm takes the public parameters and an input X and it produces an output Y as well as a proof and this evaluation is the same thing that's supposed to take T steps even if you have a parallel computer okay so parallelism does not speed up the evaluation as the points and there's a verification algorithm that takes the public parameters the input X the ALPA Y and the proof and quickly very quickly says whether Y is a correct value is a correct evaluation of the vdf so that's syntactically syntactically what a vdf is so now let's talk a little bit about the security properties so there are sort of two security properties the first one well one is I guess still a syntactic requirement is uniqueness it's crucial that these things are unique so what is uniqueness mean so given a particular value X there should only be one Y that convinces the verifier in particular if if you can construct a weina weina proof and a Y Prime and another proof that convinces the verifier in both cases then it must be the case that Y is equal to Y Prime you notice you notice by the way that it's okay to have more different proofs for this for the same y yeah okay if there's Y pi and Y Prime you just shouldn't be able to convince the verifier that there are two valid Y's so that's the uniqueness property and the more important property is this this sequentiality property which is even if the adversary has a parallel machine so polynomial e-mini processors if the adversary adversary runs in time 1 minus epsilon T so a little bit less than time T even such an adversary can't distinguish the output of the vdf from a random value so unless you spend time T the output of the vdf was completely random to you yeah that's kind of the so we call this epsilon sequence yeah obviously it's parameterize this properties parameterize by Epsilon and we'd like to achieve epsilon sequentiality for the smallest possible value of Epsilon all right that's as formal that's as formal as I'm gonna get yeah so hope this is clear enough for everybody so what do we need these things for so let's see so let me start with a picture that I stole also from one of Joe's slides which is this lottery question so you want to generate verifiable randomness in the real world and why is this what is it so the point here is that you notice only three balls came out of the little vats but all five numbers are already displayed on the bottom so so clearly clearly clearly something went wrong in this in this video so this is not very convincing that the randomness is unpredictable and the question is is there a way to verifiably generates randomness okay so so let's see a broken way to generate randomness so this is kind of crypto 101 so if you want to generate have n parties generates a random value which is kind of the main blockchain application I guess the beacon chain is kind of has a random as beacon in it which is why it's called a beacon chain so here's a dumb way to do a beacon chain to general randomness which nobody should use yeah so we have our participants everybody posts a random value to the bulletin board and the output is just the XOR of all the posted random values yeah so this looks like it's random but of course it's completely broken and the reason it's broken is because the last participant Zoey can just choose her RZ so that the output comes out to be whatever she wants okay so everybody knows this so there are a lot of solutions to a lot of attempts at fixing this problem you're a forest all familiar with commit and reveal or everybody commits and then some people ruin everybody reveals the problem with commit and reveal is that people might refuse to reveal and you can't it's kind of people keep asking me this why why can't if someone iike refuses to reveal why can't you just ignore their commitment and only XOR the the values that that that that of the people that actually open the commitment and the answer is that's insecure you can't just reveal you can't just ignore the values that were not open because if 20 people collude they could choose not to open any subset any subset of 20 of them and in doing so they basically get to they get to to the 20 possibilities for controlling the final output yeah so committing to reveal that is insecure if you just ignore the values that were not there were not opened yeah yeah but then it now it's just a game between how many how many players you have colluding yeah potentially I don't know so four bits flippin we know the four yeah this is the different story 4-bit flipping we know this is not possible in a fixed number of rounds but this is not a bit flipping this is just randomness yeah so randomness you can do in in constant rounds yeah okay but anyhow this is not commit so there other product committed reveals it requires multiple these these two rounds are problematic we'd like to do things in just a single round yeah just like here yeah you just post it you just post and you're done and nobody needs to come back and do anything else to get the randomness that's kind of the goal yeah so this basic mechanism doesn't work and so the question is what to do and so there's this beautiful beautiful idea that says what we would do is basically what we did before except now you know obviously we would hatch the outputs that everybody contributed so this by itself is not enough to ensure randomness because again Zoe still has a lot of control over what the final output is she's the last one to contribute she can just try lots of our Z's until the hash comes out to be something that she likes but instead what we're gonna do is we're gonna introduce another no another video yeah there you go just as I said it we're gonna introduce another and we're gonna introduce a vdf and the output will be the output that comes out of a computation so you notice there's no need for anyone to come back the vdf kind of guarantees the properties that we need so let's think through why this is a good idea why does this work why does this produce an by a simple randomness well so first of all let's just talk about mechanically how this works so we'll say everybody starts start submitting your your randomness at noon and then at noon at 12:10 whoever submitted that's that those are the people that participate in the protocol and then the vdf daily is gonna be more than 10 minutes yeah let's just say it's 20 minutes or something so now the sequence she ality property of the vdf ensure zowie can't try lots of possible inputs of the protocol because she can't compute the output of the vdf yeah so she contributes she contributes something to the VDS and she has no idea what the output is this is gonna take her more than 10 minutes to compute the output now this is where you guys come in right we have to make sure it really takes her more than 10 minutes to compute even if she has like you know gallium arsenide Asics and all sorts of the latest latest hardware technology if the vdf time bound is set to 20 minutes it really needs to be the case that in ten minutes she cannot predict the outputs yeah and I guess that's kind of where we need all the hardware help so you guys looked into kind of all the fancy gallium arsenide technologies that could come into play here right it's not it's not just ASIC you can imagine there's a lot of money gonna be at stake here so you know with enough money you can spend a lot of research on building faster VLSI with with fancy technologies all that has to be taken into account Thanks faster so instead so if ten if I the example here instead of 10 minutes it would be so if it takes 10 minutes to submit then you would want it to take a thousand minutes to break the vdf to scale down to whatever parameters you want 10 minutes 1000 minutes is the honest part yeah yeah exactly what I mean so the honest party will take a thousand minutes in this example yeah yeah good good yep all right sounds good yes oh yes yes absolutely absolutely absolutely yeah yeah so Justin was saying that if you're in would likely set the parameter for the vdf to be 100 X so if you want so if what is it if the if you need a delay of 10 minutes you would set the parameter to be 100 X 10 times 10 minutes for the honest guys well this capital T in there's Epsilon yeah that's capital T that's the protocol yeah that's a property of the protocol yeah yeah so yeah so we're good yeah all right very good so sequentially basically ensures that Alice can't buy Zoey can't buy us the output because she doesn't she can't choose an RZ and just try things out because it takes her more than 10 minutes to cook to calculate and uniqueness basically ensures that yeah there's no ambiguity about the output yeah there's no ambiguity about the output so once once the output is produced people can't go back and say oh no the randomness should have been something else the proof actually guarantees that the output is unique and it's very interesting again Joe makes this really nice point that if you remove any one of these requirements then constructing vdf becomes easy that's really the combination of all these requirements the sequentiality and uniqueness that makes vdf construction difficult ok so that's what that's why they're so useful and this is what we're trying to construct so now let's walk through a few constructions that that we can consider so the first construction that comes to mind is just using Hardware in claves ya know then there's this very paper on the proof of sequential work that I just uses just uses depth robust graphs no it's a but it doesn't require any fancy techniques it's just having just hash functions and therefore bus graphs that's it yes that's easy no easy meaning no known techniques okay fair enough I wasn't saying I was saying that these are known techniques we don't need we don't need to have multiple vdf workshops if we remove uniqueness we already know how to do video so if we remove uniqueness that's right that's right that's right that's all I was saying all right good gotta be gotta be careful with my words in this crowd all right ok good so right so now let's walk through a couple of a couple of constructions so the first construction is you know if we had Hardware enclaves then constructing vdf is actually quite easy basically so what is a hardware claves we can store cryptographic keys inside of the in clave and then we use that and clave we use those keys to basically generate the vdf so what we would do the public parameters would be the signature for for a public key scheme yes a PK is public and then when an input comes in the the end clave enforces a time delay and when it's done it produces you know some Mac some some PRF of the input X and then it also signs the outputs and the signature guarantee that the vdf was computed correctly by the hardware and of course a PRF is unpredictable so that's all that's really all that we need yeah so if we had a hardware in clave then vdf constructions are quite easy but of course if you ever steal the H max secret key then all the vdf guarantees go out the window yeah because now anyone can compute the vdf instantly so there's no more time delay and you cannot imagine how many people come and ask if we can use Hardware assumptions for consensus and I think it's a terrible idea yeah so if there's a lot of money writing on the security of these consensus protocols with enough money any hardware and clave can be can be broken that's my position it's fine to use it to protect data so for privacy it's fine to use enclaves for consensus where the we're breaking consensus means loss of money that's where it becomes dangerous to use to use enclaves ok good so that's that's problem number one that's something any comment anyone want to comment on that is there general agreement about this or okay haha okay I see I see all right fair enough but at least the main points seems like there's consensus on the main points yeah all right good so the next approach is to use to try build a vdf from a hash function and that what you could do is you basically kind of use do the vdf in the most natural way which is the public parameters will be a parameters for a snark and then the vdf is just defined as a hash chain where presumably you know excel evaluating sha-256 repeatedly is going to take time T even if you have a parallel computer the question is how do you verify that the Apple was computed correctly and that's where the snart's come in and so I guess we it's not so easy turns out to get this to work correctly so the proof pi would be a snark that the hash gene was computed correctly it's not so easy to get that right because computing the snark takes more time than computing the chain so you have to do something to counteract that and it turns out so so there's a paper I guess me and Joe and Benedict and Ben Ben fish let's show how to kind of do this how they kind of do this well so that you can generate the proof well fast enough yeah so the verification basically would just be verification of a snort proof and I do I did want to mention that we also had these ideas for using building vdf form permutation polynomials that somehow that really hasn't taken off yet but maybe I'll just mention that as a possible direction for future vdf so a permutation polynomial is a polynomial that's a permutation on the finite field yeah so in other words it's a polynomial defined over a finite field and such that for any two points x and y in the field the polynomial f of x is not going to be equal to f of y yeah so it's a permutation of the field and then the the property that this uses the property that this construction uses is the fact that finding roots of a polynomial so the input X is going to be the image of the polynomial and the value of the vdf would be would be a value of the polynomial I so that f of y is equal to X yes so let me say that again so the the input so the input to the VD F is a value X and the goal is to find an input to the polynomial that when you evaluate that input at the polynomial it evaluates to the given value X so we want to find the Y so that F of y is equal to X in other words we want to find the roots of the polynomial F minus X yeah F minus X will be zero at the point y and the question is can we find a root of that polynomial because it's a permutation polynomial we know that there is a unique such roots and if the polynomial is easy to evaluate like it's a sparse polynomial then checking that the roots was computed correctly is is easy you just evaluate the polynomial and you see that you get zero and the point here this use of the fact that finding roots of polynomials essentially the the practical way to do it is by some sort of a GCD computation and GCD computations are inherently sequential yeah so that's kind of the idea there we don't know so the question is are there good permutation polynomials for which there are no shortcuts the best way to find a roots is via a GCD computation and that's kind of the question yeah so it's another valid direction for does that make sense it's another valid direction for constructing PDFs but the chat the research challenge is are there good permutation polynomials that a are easy to evaluate so there's sparse polynomials or they have short straight-line programs and the best way to find a root of the polynomial is via GCD computation and there's no other shortcuts okay so that's that's another approach just keep that in mind and then the third approach was it was actually the most exciting I think and that's I think the direction we're all headed in is basically these algebraic constructions and so the algebraic construction starts from a group from a finite cyclic group yeah so this is the group 1 G G square G cubed and then the assumption is that the group has unknown order so nobody knows what the order of the group is in other words nobody knows how many elements are in the group and then the public parameters are going to be some hash function into the group some from from our input space X into the group and the way we define the evaluation of the P of the vdf is based take your input X hash it on to the group and then raise the result to the power of T two to the T and that inherently requires T squarings yeah so this is kind of again this has been used many times before in cryptography for the what is it for proofs of time proofs of time and time lock time block puzzles what is it Rivest Shamir not Rivest Shamir and wagner yeah RSW so this this kind of function has been used quite a bit the problem has always been how do you verify that the output is correct yeah so how do you know that once you've computed the function you actually got the correct output and here it is really really beautiful work of Benjamin and Kristoff really these are really beautiful protocols that allow you to quickly verify that the function was was computed correctly I'll mention you can read the papers to see how the protocols work I guess yeah I guess we wrote a survey paper on this - that kind of describes the two schemes together in one place if you want to see that and I guess we're even going to hear later today about hybrid schemes that kind of combine the two proofs to maybe make the proof generation a little faster than what we have today so you Benjamin you're gonna talk about that cool all right so that's kind of the algebraic construction there's one issue here which is you notice I said the complexity assumption is that the group has unknown order again I'm being a little vague will here exactly what the complexity assumption later is later on so let me talk a little bit about what does this mean that the group has unknown order first of all why do we need the group to have unknown order well if the group has known order suppose there was no order order D then evaluation becomes trivial it what I will do is I will just compute two to the T mod D that takes very little time to to the team ID and then it will just raise H of X to that power but now that's a very small power so if I knew the order of the group I could accelerate the evaluations from T squarings to basically almost logarithmic time in T from T squarings to log T work yeah so that's kind of the that's why we have to have this group this group has to have unknown order so the challenge then is how do we generate groups of unknown order yeah so nobody should know the order of the group and like I said this is crucial for vdf security vdf would simply be insecure if we could compute the order of the group so what are the candidate groups of unknown order that we have so the first one everybody knows this is the RSA group right so you generates two integers P and Q multiply them and the order of the group is unknown unless you can factor the modulus all right so the issue here is anyone who knows the factorization will know the order of the group and we'll break the vdf so we have to be able to construct this n in a way that nobody knows the factorization so this for efficiency this requires a trusted set up I'll mention that I guess at some point we all we also discussed just choosing a random large enough n yeah but it turns out like n would have to be something like 40,000 bits or so so that the factorization is unknown it's too big that's I think it's 33 to 40000 I wouldn't okay we can talk about whether it's safe to go below that but it would still need to be quite large if you choose a random number it would need to be quite large for the factorization to be unknown so it's for efficiency purposes we'd like to generate a random RSA modulus presumably 2,000 bits or 4,000 bits for which nobody knows the factorization yeah of course yeah of course of course of course of course but I also heard efficiency right I mean so if you start if you start concatenated that's gonna slow you down linearly that's right that's right actually yeah okay well we can talk about that later but anyhow so so so the problem with this group is that we need to have this trusted set up and so the way this would work and I guess we're gonna have a whole breakout session on this we're gonna run the questions how do you generate run a protocol that generates an RSA modulus so everybody's convinced that the modulus is in fact a product of two large primes and nobody knows the factorization yeah so that's what this requires yeah yes please oh you mean well I mean the parameters basically say so does limiting the domain of the function in statistics didn't matter well so what happens is oh you're saying rather than hashing on to the whole group you will just hash into a 256 bit space so the requirement is is just that you see you shouldn't be able to find three images in the hash function say that that what is it that multiplied to one another so you shouldn't be able to find X 1 X 2 and X 3 such that H of X 1 times H of X 2 is equal to H of X 3 because if you could you could evaluate the vdf at H of X 1 a value of d Vidia that H of X 2 and trivially that will give you the evaluation of the vdf at H of X 3 so the hash function needs to be resistant to these multiplicative collisions and as long as that's fine we're good yeah and so 256 bits that's on the border of what's what's secure there so I'd suggest hashing to more then 256 bits but in principle it's only this kind of multiplicative collisions that we need to worry about yeah know that okay absolutely right absolutely right so let me explain what let me let me just repeat that so the issue is so there's another attack it's not just multiplicative collisions so imagine imagine H of X mapped to a number that happened to be a product of only small primes yeah so happens to be only 3 times 5 times 7 let's just say this 3 times 5 times 7 you can pre-compute the vdf at 3 at 5 and at 7 and that would let you quickly evaluate the vdf at a number that the number H of X that happens to be a product of small Prime's so it's important that H of X not be only a part of the small Prime's because that would enable enable pre-computation and so yeah so the answer is no so the answer is 256 bits is definitely not enough yeah so you would need to avoid these smoothness attacks that's where you would need probably the output to be at least 2,000 bits or so yeah so that's okay we know how to do that so just you know use a hash function that outputs outputs more more than 256 bits it's a good point thanks mention all right good all right so groups of unknown order so we talked about RSA so the issue is we have to have this trusted setup procedure the other group that has unknown order this is kind of a magical group it's called a class group of an imaginary quadratic order I want to find what that is but what's but the amazing thing about this is this group is specified by a prime so literally you just choose a prime that happens to be 3 mod 4 and then boom you have a group defined by this prime and the amazing thing is if the prime is large enough let's say a thousand bits nobody knows how to calculate the order of that group yeah it's just the best algorithm that we have for calculating the order of the group essentially runs in sub exponential time so we actually can't run the algorithm to calculate the order of the group so this is kind of a remarkable group in that you pick a prime you get a group of unknown order and you can use it for a vdf the problem with it so the benefit is that there is no set up the problem is it that the operation in a class group is relatively slower than in an RSA group and yeah and to be honest we actually don't know how much slower so I talked to Bram yesterday and he was telling me that or two days ago he was telling me that they from the competition that they ran it looks like now the implementations they have are actually much better than their initial implementations so maybe now the relation between RSA operations and class group operations it used to be like a factor of 20 it looks like it's now reduced to like a factor of 5 so class groups are 5 times slower than RSA groups but to be honest we still don't know the answer there so these group that implementations still need to be optimized lots of comments yeah well because the Verret you're slowing down the verifier yeah I mean so we want to verify it to be oh and we don't know that the issue is we don't know how much it can be parallelized right yeah it could be that the group operation itself can be paralyzed and that's an issue yeah oh yeah that's my second point exactly Justin you had another commenter yeah nobody's ever done it's right right so we don't know what the AC performance would be for for class groups yeah we had yet yeah fair enough fair enough yeah yeah for sure fair enough how parallel it is right I know I don't totally agree so so actually the real question is yeah absolutely so how parallel how parallelizable is the group operation and obviously we'd like the group operation we'd like to understand we like to basically extract all the parallelism that we can as a group operation so that we we know how long the bad guys would have to run no that's the class groups are they have been proposed in crypto I guess in the mid-1990s but they have never been deployed so this is kind of virgin territory yeah there's a lot I think it's interesting yeah there's a lot of a lot of interesting work to do here but there's work to do for RSA I totally agree there's a lot more that's known yeah the interesting thing is because it's so easy to generate these groups you can actually switch groups every couple of minutes just generate a new primer every few minutes and not a lot that means that in the RSA case we have to generate the parameters to be large enough to not be breakable in 50 years yeah for class groups we just have to generate a parameter is large enough to not be broken in like a minute or if you generate a new one every ten minutes not to be broken every ten minutes so that allows us to shrink the parameters and in principle who knows maybe we can shrink them enough that maybe they even become faster than the RSA operation we just don't know so yeah so what do we do about attacks on RSA groups or scoops no class groups computing the size of a class group this is a very fundamental question in an algebraic number theory so there are a lot of people who worked on trying to come up with better algorithms for computing class groups the best algorithms right now are kind of index calculus tights algorithm type algorithms they run in time l 1/2 or as factoring runs in time l one-third but it's not there's a lot of work that's gone into trying to come up with better algorithms for computing class groups this is not a new problem this has been studies quite a bit yeah because it's a very it's a very fundamental problem in number theory yeah yeah this is why so there's two benefits right so a the problem seems to be harder so even even if we had to be secure for 30 years it looks like a 2,000 bit modulus is sufficient for 4 class groups whereas 4000 bits are needed for RSA but the other benefit of course is we can switch very quickly so we can shrink the parameters even more yeah and well yeah so we'll need to come up with a number so Chia is gonna be using this yeah so we're gonna need to come up with a number to to to say what is the right modulus size to use here okay so let me end up let me end here just with a couple of open problems so first of all I don't know that there are not other groups so this is a question for the mathematicians there could be other groups of unknown order right so we have two examples and they each problematic for different reasons yeah one has a slow group operation or I should say parallelizable group operation potentially and the other one has a trusted setup and so you know there could be other groups of unknown order so you know please this is a wonderful question think about yeah and maybe we can have a larger variety to choose from the other problem is that all these algebraic vdf construction is actually not post quantum secure I don't know if we need to worry about that now you know my calculation is it's 30 years away so we'll worry about it you know in the future but why is it why is it not post Quantum secure and the answer is Shor's algorithm for factoring actually it's good at finding periods of funk sorry it's good it's good at finding the order of a group so no group of unknown order is gonna be secure against the quantum attack so the whole algebraic approach in some sense is inherently not post quantum secure and so the question is you know is there a way to do post quantum secure vdf efficiently we can go back to the hash based systems but those require you know these recursive snarks and so on the question is is there a clean very clean and simple vdf that also will remain secure in the presence of a quantum computer wait so that's what I wanted to say and I guess I'll stop here so thank you yeah and looking forward to the conversation is during the day